A Randomized Algorithm for Multipacket Routing on the Mesh
S. Rajasekaran, Mukund Raghavachari · Journal of Parallel and Distributed Computing · 1995
In this paper we present a randomized algorithm for the multipacket routing problem on an n × n mesh. The algorithm completes with high probability in at most kn + o(kn) parallel communication steps, with a queue size of k + o(k). The previous best known algorithm (Kunde and Tensi, J. Parallel Distrib. Comput. 11 (1991), 146-155) takes (54) kn + O(kn/f(n)) steps with a queue size of O(kf(n)) (for any 1 ≤ f(n) ≤ n). The algorithm that we will present is optimal with respect to queue size. The time bound is within a factor of 2 of the known lower bound.