Average case analysis of greedy routing algorithms on arrays
Frank Thomson Leighton · 1990
In this paper, we analyze the average case behavior of greedy routing algorithms on arrays under a variety of assumptions.Overall, we find that certain greedy algorithms perform surprisingly well on average.For example, given an N x N array or torus where every node starts with one packet headed for a random destination, we show that some (but not all) greedy store-andforward algorithms route every packet to its destinrt, tion with only O(log N) delay per packet and maximum queuesize 4 with probability near 1.Moreover, the expected delay per packet is only a small constant, independent of N. We also extend the analysis to a steady state model of routing in which packets enter the network at random times.Provided that the overall arrival rate of packets to the network is less than 100% of the network capacity, we show that any packet encounters at most O(log N) delay with high probability.In addition, we show that the maximum size of a queue over a time span of T steps is O(e) with high probability.The results can also be extended to analyze the average case behavior of cut-through (or, flit-serial) routing under lighter loading.and NOO014-89-J-1988,