26
The Chaos Algorithm
•The
Chaos router directs packets according to the following scheme
–0
Transmit packets with virtual cut-through
–1 Send packets along a random shortest-path whenever
possible, i.e. when traffic is light
–2 Wait
briefly inside the switch (no store-and-forward) when traffic is moderate
–3 In
heavy traffic when there is no more space in the switch to wait, “deroute”
some (randomly chosen) waiting packet
Derouting (probably) takes a packet further from its destination