Bounds on the greedy routing algorithm for array networks
Michael Mitzenmacher · 1994
We extend previous work on greedy routing for array networks by providing bounds on the average delay and the average number of packets in the system. We analyze the dynamic routing problem, where packets are generated at each node according to a Poisson process. Each packet is sent to a destination chosen uniformly at random. Packets are routed greedily, first moving to the correct column and then to the correct row. Packets require unit time to travel across a directed edge between nodes; only a single packet can cross an edge at any given time, and packets waiting for an edge are buffered. Our bounds are based on comparisons with computationally more simple queueing networks, and the methods used are generally applicable to other network systems. A primary contribution of the paper is a new lower bound technique that also improves on the previous lower bounds by Stamoulis and Tsitsiklis for heavily loaded hypercube networks. [11] On heavily loaded array networks, our lower and upper bounds differ by only a small constant factor.