Chaos router: Architecture and performance

Abstract

The chaos router is an adaptive, randomized message router for multicomputers. Adaptive routers are superior to oblivious routers, the state-of-the-art, because they can bypass congestion and faults. The chaos router has reduced the complexity along the critical path of the routing decision by using randomization to eliminate livelock protection. The foundational theory for chaotic routing, proving that this approach is sound, has been previously developed by the authors (1990). The authors present the complete design of the router together with (simulated) performance figures. The results show that the chaos router is competitive with the simple and fast oblivious routers for random loads and greatly superior for loads with hot spots.