Potential function analysis of greedy hot-potato routing
Amir Ben‐Dor, Shai Halevi, Assaf Schuster · 1994
We study the problem of packet routing in synchronous networks. We put forward a notion of greedy hot-potato routing algorithms and devise techniques for analyzing such algorithms. A greedy hot-potato routing algorithm is one where ffl The processors have no buffer space for storing delayed packets. Therefore, each packet must leave any intermediate processor at the step following its arrival. ffl Packets always advance towards 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 towards their destinations. We use potential function analysis to obtain an upper bound of O(n p k) on the running time of a wide class of algorithms in the 2-dimensional n \\Theta n mesh, for routing problems with total of k packets. The same techniques can be generalized to obtain an upper bound of O(exp(d)...