Optimal-Algorithms for Multipacket Routing Problems on Rings
Fillia S. Makedon, Antonios Symvonis · Journal of Parallel and Distributed Computing · 1994
We study multipacket routing problems on rings of processors. We prove a new lower bound of 2n/3 routing steps for the case that k, the number of packets per processor, is at most 2. We also give an algorithm that tightens this lower bound. For the case where k > 2, the lower bound is kn/4. The trivial algorithm needs in the worst case k⌊n/2⌋ steps to terminate. An algorithm that completes the routing in kn/4 + 2.5n routing steps is given.