An analysis of deflection routing in multi-dimensional regular mesh networks

A Markov Chain based analysis for deflection routing in n-dimensional regular mesh networks is presented. Detailed analyses are given for the 2D mesh, and a generalization to higher dimensions is outlined. Analytic results are shown to agree very closely with simulations. A basic routing scheme in which all packets have equal priority and a priority scheme in which packets with fewer alternative routes are given priority are proposed and analyzed. Results show that the priority scheme gives higher maximum throughput and lower average packet delay than the basic scheme by reducing average deflections under heavy loads. With the priority scheme, the network performance is almost identical to that of the optimal diagonal routing scheme. By doubling the number of links the throughput is always more than doubled. The authors conclude that in the 2D case, bidirectional links are more cost-effective than unidirectional ones assuming the cost is the number of optical transceivers