Greedy dynamic routing on arrays
Nabil Kahalé, Tom Leighton · 1995
We study the problem of dynamic routing on arrays. We prove that a large class of greedy algorithms perform very well on average. In the dynamic case, when the arrival rate of packets in an N \\Theta N array is at most 99% of network capacity, we establish an exponential bound on the tail of the delay distribution. Moreover, we show that, in any window of T steps, the maximum queue-size is O(1 + log T= log N ) with high probability. We extend these results to the case of bit-serial routing, and to the static case. We also calculate the exact value of the ergodic expected delay and queue-sizes under the farthest-first protocol for the one dimensional array, and for the ring when the arrivals are Poisson. 1 Introduction Many parallel machines, such as the MPP, Ametek and Intel Touchstone are configured as a low-dimensional array containing a large number of processors. These machines generally route packets using simple greedy algorithms. While these algorithms tend to behave well experi...