Abstract
We study the problem of packet routing in synchronous networks. We put forward a notion of greedy hot-potato routing algorithms and devise tech- niques for analyzing such algorithms. A greedy hot-potato routing algorithm is one where:
• The processors have no buffer space for storing delayed packets. Therefore, each packet must leave any intermediate processor at the step following its arrival.
• Packets always advance toward their destination if they can. Namely, a packet must leave its current intermediate node via a link which takes it closer to its destination, unless all these links are taken by other packets. Moreover, in this case all these other packets must advance toward their destinations.
We use potential function analysis to obtain an upper bound of O(n k 1/2 ) on the running time of a wide class of algorithms in the two-dimensional n × n mesh, for routing problems with a total of k packets. The same techniques can be generalized to obtain an upper bound of O(exp(d) nd-1 k 1/d ) on the running time of a wide class of algorithms in the d -dimensional n d mesh, for routing problems with a total of k packets.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received December 1993, and in final form March 1997.
Rights and permissions
About this article
Cite this article
Ben-Dor, A., Halevi, S. & Schuster, A. Potential Function Analysis of Greedy Hot-Potato Routing. Theory Comput. Systems 31, 41–61 (1998). https://doi.org/10.1007/s002240000076
Published:
Issue Date:
DOI: https://doi.org/10.1007/s002240000076