####
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.