Adaptive fault-tolerant switching network with random initial routing and random routing around faults

摘要

An interconnection network routes packets among switches connected in a multi-dimensional network of links. Each packet contains a header with an address of a source switch connected to an input port that receives the packet, and a destination switch connected to an output port that transmits the packet. Each packet header also contains a random address of a random switch in the network. The packet is first routed from the source switch toward the random switch. Then a phase flag in the header is cleared by the random switch, and the packet is routed toward the destination switch. If a faulty link or switch is encountered, and no known routes are available to the destination, the phase flag is again set and another random address generated. The packet is then routed to a new random switch, bypassing the fault.