The chaos router is a randomizing, nonminimal adaptive packet router for use in the communication networks of parallel computers. Invented at the University of Washington in 1989, the chaos router is a promising replacement for state-of-the-art oblivious routers.
Adaptive routing has long been cited as a good idea since it allows packets to bypass congestion in a network and speeds delivery through the use of alternative paths. Adaptive routers divide into two classes, minimal and nonminimal, depending on whether or not they are restricted to sending packets only along shortest paths to the destinations. Since packets in minimal routers can only go forward, they often discover congestion "too late," i.e. when there are no other forward paths, and so have not provided as much performance as hoped. Nonminimal routers are in principle able to give good performance, since they can "back up" and move around congestion, but this ability to take circuitous paths means that messages could livelock, i.e. move around the network forever without getting delivered. Previously, adding livelock protection to nonminimal routers increased their complexity so much they could not operate fast enough to compete with the very fast state-of-the- art oblivious routers.
By randomizing the path selection and the derouting decisions, the chaotic router does not need livelock protection. The chaotic router is not deterministically livelock free by this technique, but it is probabilistically livelock free, which is equivalent in all practical cases. Without the added complexity of livelock protection, chaotic routers can be fast and thus realize the potential of adaptive routing.
Besides developing the theoretical foundations and running an enormous number of simulations to compare the chaos router with other routing approaches, the project has produced a working CMOS chip in 1.2u scalable design rules. Continuing work is ongoing to improve the hardware implementation by adding fault-tolerant capabilities to it. Because the Chaos router can deliver packets out of order, a reordering network interface is currently being designed. Also, the project encompasses a large number of different theoretical and simulation projects that explore different aspects of the router design space including packets vs. worms, minimal adaptive schemes, and other non-minimal router designs.
Principal Investigators: Bolding, Ebeling and Snyder.