Gd. Stamoulis et Jn. Tsitsiklis, THE EFFICIENCY OF GREEDY ROUTING IN HYPERCUBES AND BUTTERFLIES, IEEE transactions on communications, 42(11), 1994, pp. 3051-3061
We analyze the following problem: Each node of the d-dimensional hyper
cube independently generates packets according to a Poisson process wi
th rate lambda. Each of the packets is to be sent to a randomly chosen
destination; each of the nodes at Hamming distance k from a packet's
origin is assigned an a priori probability p(k)(1 - p)(d-k). Packets a
re routed under a simple greedy scheme: each of them is forced to cros
s the hypercube dimensions required in increasing index-order, with po
ssible queueing at the hypercube nodes. Assuming unit packet length an
d no other communications taking place, we show that this scheme is st
able (in steady-state) if rho < 1, where rho=(def)lambda p is the load
factor of the network; this is seen to be the broadest possible range
for stability. Furthermore, we prove that the average delay T per pac
ket satisfies T less than or equal to dp/1-rho, thus showing that an a
verage delay of Theta(d) is attainable for any fixed rho < 1. We also
establish similar results in the context of the butterfly network. Our
analysis is based on a stochastic comparison with a product-form queu
eing network.