Bounds on the Greedy Routing Algorithm for Array Networks

摘要

We analyze the performance of greedy routing for array networks by providing bounds on the average delay and the average number of packets in the system for the dynamic routing problem. In this model packets are generated at each node according to a Poisson process, and each packet is sent to a destination chosen uniformly at random. Our bounds are based on comparisons with computationally simpler queueing networks, and the methods used are generally applicable to other network systems. A primary contribution we provide is a new lower bound technique that also improves on the previous lower bounds by Stamoulis and Tsitsiklis for heavily loaded hypercube networks. On heavily loaded array networks, our lower and upper bounds differ by only a small constant factor. We further examine extensions of the problem where our methods prove useful. For example, we consider variations where edges can have different transmission rates or the destination distribution is non-uniform. In particular, we study to what extent optimally configured array networks outperform the standard array network.