The efficiency of greedy routing in hypercubes and butterflies
George D. Stamoulis, John N. Tsitsiklis · IEEE Transactions on Communications · 1994
We analyze the following problem. Each node of the d-dimensional hypercube independently generates packets according to a Poisson process with rate /spl 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/sup k/(1-p)/sup d-k/. Packets are routed under a simple greedy scheme: each of them is forced to cross the hypercube dimensions required in increasing index-order, with possible queueing at the hypercube nodes. Assuming unit packet length and no other communications taking place, we show that this scheme is stable (in steady-state) if /spl rho/>