Chaos router
Smaragda Konstantinidou, Lawrence Snyder · 1991
The Chaos router is an adaptive, randomized message router for multlicomputers.Aclaptive routers are superior to oblivious routers, the state-of-the-art, because they can by-pass congestion and faults.unlike other adaptive routers, however, 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 de~-eloped [1 1].In this paper we present, the complete design of the router together with (simulated) performance figures.The results show that, the Chaos t-outer is competitive with the simple and fast obli~ious routers for random loads and greatly superior for loads with hot spots. 1 Non-nliuimal, adaptive routers, as shown by our simulat ions, have the potential of outperforming minimal, adaptive routers, especially under non-uniform traffic.Their disad~ant,age though is their difficulty in guarant wing freedom from ltrc lock.L,6.guarantee that, no message will fail to be deli~"ered because it is repeatedly derout ed.The well known solution to this problem is priorit ~-routing, where messages are assigned a timestamp upon injection into the network.JYhen multiple messages require the same channel the oldest one is selected.Priority routing is known to be expensive, not only because it increases the message length in order to incorporate the timestamp, but, even more so because