AbstractNetwork throughput can be increased by allowing multipath, adaptive routing. Adaptive routing allows more freedom in the paths taken by messages, spreading load over physical channels more evenly. The flexibility of adaptive routing introduces new possibilities of deadlock. Previous deadlock avoidance schemes in k-ary n-cubes require an exponential number of virtual channels [Linder and Harden, 1991]. We describe a family of deadlock-free routing algorithms called planar-adaptive routing algorithms, that require only a constant number of virtual channels independent of networks size and dimension. Planar-adaptive routing algorithms reduce the complexity of deadlock prevention by reducing the number of choices at each routing step. In the fault-free case, planar-adaptive networks are guaranteed to be deadlock-free. In the presence of network faults, the planar-adaptive router can be extended with misrouting to produce a working network which remains provably deadlock free and is provably livelock free. In addition planar-adaptive networks can simultaneously support both in-order and adaptive, out-of-order packet delivery.
Planar-adaptive routing is of practical significance. It provides the simplest known support for deadlock-free adaptive routing in k-ary n-cubes of more than two dimensions (with k > 2). Restricting adaptivity reduces the hardware complexity, improving router speed or allowing additional performance-enhancing network features. The structure of planar-adaptive routers is amenable to efficient implementation.
Simulation studies show that planar-adaptive routers can increase the robustness of network throughput for nonuniform communication patterns. Planar-adaptive routers outperform deterministic routers with equal hardware resources. Further, adding virtual lanes to planar-adaptive routers increases this advantage. Comparisons with fully adaptive routers show that planar-adaptive routers, limited adaptive routers, can give superior performance. These results indicate the best way to allocate router resources to combine adaptivity and virtual lanes.
Planar-adaptive routers are a special case of limited adaptivity routers. We define a class of adaptive routers with f degrees of routing freedom. This class, termed f-flat adaptive routers, allows a direct cost-performance tradeoff between implementation cost (speed and silicon area) and routing freedom (channel utilization). For a network of a particular dimension, the cost of adaptivity grows linearly with the routing freedom. However, the rate of growth is a much larger constant for high-dimensional networks. All of the properties proven for planar-adaptive routers such as deadlock and livelock freedom, also apply to f-flat adaptive routers. Copyright 1995 by ACM, Inc.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: B.4.3 [Input/Output and Data Communications]: Interconnections (subsystems); C.2.1 [Computer-Communication Networks]: Network Architecture and Design
General Terms: Algorithms, Performance, Reliability
Additional Key Words and Phrases: Adaptive routing, fault tolerance, interconnection networks, multicomputers, packet routing, parallel processing, transmission-order preservation