AN APPROXIMATE ANALYSIS OF THE PERFORMANCE OF DEFLECTION ROUTING IN REGULAR NETWORKS

Regular two-dimensional architectures are being considered as alternatives to the linear topology metropolitan area networks (MAN's) that are popular today. Deflection routing is an adaptive routing strategy that performs well on such architectures. We have developed a general analytic model to study the performance of buffered deflection routing in regular networks. The Manhattan Street Network, the ShuffleNet, and the Shuffle Exchange Network have been studied as candidate two-connected networks with different topological characteristics. The results show that deflection routing performs well on both the Manhattan Street Network and the ShuffleNet, even under heavy load, while on the Shuffle Exchange Network it does not perform as well. The introduction of just a few buffers provides significant improvement in the delay-throughput performance over unbuffered deflection routing, especially in networks with large propagation delays. The analytic results are found to match the simulations very closely in most cases.