The turn model for adaptive routing

Abstract

This paper presents a model for designing wormhole routing algorithms, A unique feature of the model is th~t lt is not based cm adding physical or virtual channels to direct networks (although it can be applied to networks with extra channels). Instead, the model is based [In analyzlng the directions in which packets can turn m a network and the cycles that the turns can form. Prohibiting just enough turns to brezk all of the cycles produces routing algorithms that are deadlock free, livelock free, mmimal or nonminimal, and highly adaptive. This paper focuses on the two most common network topologies for wormhole routing, ~z-dimensional meshes and k-ary /z-cubes without extra channels. In such networks, just a quarter of the turns must be prohibited to prevent deadlock. The remaining three quarters of the turns allow routing to be fidaptwe, Adaptive routing algorithms are described for two-dimensional meshes, n-dimensional meshes k-my ~t-cubes, and hypercubes. Simulations of adaptive and nonadaptive routing algorithms show which algorlthm has the lowest latcncies and highest sustainable throughput depends on the pattern of message traffic. For nonuniform traffic, adaptive routing algorithms generally perform better than nonadaptive ones.