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

Regular two-dimensional architectures are being considered as alternat ives to the linear topology metropolitan area networks (MAN's) that ar e popular today. Deflection routing is an adaptive routing strategy th at performs well on such architectures. We have developed a general an alytic model to study the performance of buffered deflection routing i n regular networks. The Manhattan Street Network, the ShuffleNet, and the Shuffle Exchange Network have been studied as candidate two-connec ted networks with different topological characteristics. The results s how that deflection routing performs well on both the Manhattan Street Network and the ShuffleNet, even under heavy load, while on the Shuff le Exchange Network it does not perform as well. The introduction of j ust a few buffers provides significant improvement in the delay-throug hput performance over unbuffered deflection routing, especially in net works with large propagation delays. The analytic results are found to match the simulations very closely in most cases.