OPTIMAL-ALGORITHMS FOR MULTIPACKET ROUTING-PROBLEMS ON RINGS

Authors
MAKEDON F SYMVONIS A
Citation
F. Makedon et A. Symvonis, OPTIMAL-ALGORITHMS FOR MULTIPACKET ROUTING-PROBLEMS ON RINGS, Journal of parallel and distributed computing, 22(1), 1994, pp. 37-43
Citations number
16
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Journal of parallel and distributed computing → ACNP
ISSN journal
07437315
Volume
22
Issue
1
Year of publication
1994
Pages
37 - 43
Database
ISI
SICI code
0743-7315(1994)22:1<37:OFMROR>2.0.ZU;2-W
Abstract
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 numb er of packets per processor, is at most 2. We also give an algorithm t hat tightens this lower bound. For the case where k > 2, the lower bou nd 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. (C) 1994 Academic Press, Inc.