GREEDY DYNAMIC ROUTING ON ARRAYS

We study the problem of dynamic routing on arrays. We prove that a lar ge class of greedy algorithms perform very well on average. In the dyn amic case, when the arrival rate of packets in an N x N array is at mo st 99% of network capacity, we establish an exponential bound on the t ail 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 proba bility. 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 t he one-dimensional array, and for the ring when the arrivals are Poiss on. (C) 1998 Academic Press.