A RANDOMIZED ALGORITHM FOR MULTIPACKET ROUTING ON THE MESH

In this paper we present a randomized algorithm for the multipacket ro uting problem on an n x n mesh. The algorithm completes with high prob ability in at most kn + o(kn) parallel communication steps, with a que ue size of k + o(k). The previous best known algorithm (Kunde and Tens i, J. Parallel Disfrib. Comput. 11 (1991), 146-155) takes (5/4) kn + O (kn/f(n)) steps with a queue size of O(kf(n)) (for any 1 less than or equal to f(n) less than or equal to n). The algorithm that we will pre sent is optimal with respect to queue size. The time bound is within a factor of 2 of the known lower bound. (c) 1995 Academic Press, Inc.