The turn model for adaptive routing

A model for designing wormhole routing algorithms that are deadlock free, minimal or nonminimal, and maximally adaptive is presented. The model is based on analyzing the direction in which packets can turn in a network and the cycles that the turns can form. Prohibiting just enough turns to break all of the cycles produces algorithms with the above properties. The two most common network topologies for wormhole routing, n-dimensional meshes and k-ary n-cubes, without extra channels, are considered. In an n-dimensional mesh, just a quarter of the turns must be prohibited to prevent deadlock. The remaining three quarters of the turns permit partial adaptiveness in routing. Partially adaptive routing algorithms are described for 2-D meshes, n-dimensional meshes, k-ary n-cubes, and hypercubes. Simulations of partially adaptive and nonadaptive routing algorithms for 2-D meshes and hypercubes show that which algorithm has the lowest latencies and highest sustainable throughput depends on the pattern of message traffic. For nonuniform traffic, partially adaptive routing algorithms perform better than non-adaptive ones.