S. Rajasekaran et M. Raghavachari, A RANDOMIZED ALGORITHM FOR MULTIPACKET ROUTING ON THE MESH, Journal of parallel and distributed computing, 26(2), 1995, pp. 257-260
Citations number
12
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
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.