The Turn Model for Adaptive Routing

The Turn Model for Adaptive Routing

1992 | Christopher J. Glass and Lionel M. Ni
This paper presents a model for designing deadlock-free, livelock-free, minimal or nonminimal, and maximally adaptive wormhole routing algorithms. The model is based on analyzing the directions in which packets can turn in a network and the cycles that these turns can form. By prohibiting just enough turns to break all cycles, the model produces routing algorithms that are deadlock-free, livelock-free, and maximally adaptive. The paper focuses on two common network topologies for wormhole routing: n-dimensional meshes and k-ary n-cubes. In an n-dimensional mesh, prohibiting a quarter of the turns prevents deadlock, while the remaining three quarters allow partial adaptiveness. Partially adaptive routing algorithms are described for 2D meshes, n-dimensional meshes, k-ary n-cubes, and hypercubes. Simulations show that partially adaptive algorithms perform better than nonadaptive ones for nonuniform traffic patterns. The turn model is unique in that it does not rely on adding physical or virtual channels but instead analyzes packet turning directions and cycles. The model produces partially adaptive routing algorithms for various topologies, including mesh-connected, k-ary n-cube, hexagonal, octagonal, and cube-connected cycle networks. Adding extra channels allows for fully adaptive routing, which is discussed in a future paper. The paper also describes specific partially adaptive routing algorithms for 2D meshes, n-dimensional meshes, k-ary n-cubes, and hypercubes. These algorithms are deadlock-free, livelock-free, and maximally adaptive. The paper concludes that the turn model is effective for designing adaptive routing algorithms without the need for extra channels.This paper presents a model for designing deadlock-free, livelock-free, minimal or nonminimal, and maximally adaptive wormhole routing algorithms. The model is based on analyzing the directions in which packets can turn in a network and the cycles that these turns can form. By prohibiting just enough turns to break all cycles, the model produces routing algorithms that are deadlock-free, livelock-free, and maximally adaptive. The paper focuses on two common network topologies for wormhole routing: n-dimensional meshes and k-ary n-cubes. In an n-dimensional mesh, prohibiting a quarter of the turns prevents deadlock, while the remaining three quarters allow partial adaptiveness. Partially adaptive routing algorithms are described for 2D meshes, n-dimensional meshes, k-ary n-cubes, and hypercubes. Simulations show that partially adaptive algorithms perform better than nonadaptive ones for nonuniform traffic patterns. The turn model is unique in that it does not rely on adding physical or virtual channels but instead analyzes packet turning directions and cycles. The model produces partially adaptive routing algorithms for various topologies, including mesh-connected, k-ary n-cube, hexagonal, octagonal, and cube-connected cycle networks. Adding extra channels allows for fully adaptive routing, which is discussed in a future paper. The paper also describes specific partially adaptive routing algorithms for 2D meshes, n-dimensional meshes, k-ary n-cubes, and hypercubes. These algorithms are deadlock-free, livelock-free, and maximally adaptive. The paper concludes that the turn model is effective for designing adaptive routing algorithms without the need for extra channels.
Reach us at info@study.space