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

• US 6,594,261 B1
• Filed: 12/22/1999
• Issued: 07/15/2003
• Est. Priority Date: 12/22/1999
• Status: Expired due to Fees

• Current Assignee: Aztech Partners, Inc.
• Original Assignee: Aztech Partners, Inc.
• Inventors: Cruz, Rene L., Lipp, Robert J., Boura, Younes
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Fox, Jamal A.
• Application Number:
  US09/470,144
• Time in Patent Office: 1,301 Days
• Field of Search: 370/217, 370/218, 370/219, 370/220, 370/225, 370/389, 340/2.23, 340/2.27, 714/4
• US Class Current: 370/389
• CPC Class Codes: H04L 41/0654 using network fault recovery ring fault isolation or reconfiguration in loop networks without recovery actions by a network management system H04L12/437
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/557 Error correction, e.g. fault recovery or fault tolerance

Abstract

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.

Claims

1. An adaptively-routed interconnection network comprising:

a plurality of ingress ports for receiving packets;

a plurality of egress ports for transmitting packets;

a plurality of switches, each switch having;

input links for receiving packets from other switches in the network;

output links for sending packets to other switches in the network;

a packet memory for storing packets received from the input links until transmission over the output links;

wherein each packet stored in the packet memory has a header that includes;

a destination address of a destination switch in the plurality of switches, the destination switch coupled to a destination egress port in the plurality of egress ports that the packet is to be transmitted out of;

a random address of a random switch;

a phase indicator for indicating a first phase when the packet is forwarded to the random switch, and for indicating a second phase when the packet is forwarded to the destination switch;

a routing controller, reading the header of a packet for storage in the packet memory, for determining a selected output link in the plurality of output links to send the packet over;

wherein when the random address read from the header matches an address of the switch, resetting the phase indicator to indicate that the packet is in the second phase and no longer in the first phase;

(1) when the phase indicator indicates that the packet is in the first phase, using the random address from the header to determine the selected output link, the selected output link being in a route toward the random switch;

(2) when the phase indicator indicates that the packet is in the second phase, reading the destination address from the header to determine the selected output link, the selected output link being in a route toward the destination switch;

wherein the packet is sent over the selected output link on the route toward the random switch when the phase indicator indicates the packet is in the first phase, but the packet is sent over the selected output link on the route toward the destination switch when the phase indicator indicates the packet is in the second phase;

wherein the packet is removed from the network by the destination switch and transmitted over the egress port coupled to the destination switch when the destination switch determines that the destination address in the header matches the address of the destination switch,

whereby packets are routed to the random switch during the first phase, but routed to the destination switch during the second phase after the packet reaches the random switch.

2. The adaptively-routed interconnection network of claim 1 wherein the output links and the input links of switches form a multi-dimensional network topology,

wherein the network has multiple disjoint interconnections between nodes.

3. The adaptively-routed interconnection network of claim 2 wherein the random address stored in the header is randomly generated by a scattering function to select as the random switch any switch in the network, including switches that are not on the route to the destination switch;

wherein the scattering function is random with respect to the destination switch, wherein the random switch is selected from the group consisting of a pseudo-random selector, a true-random selector, and a round-robin cycler,

whereby packets are first routed to a random switch within the network before being routed to their destination.

4. The adaptively-routed interconnection network of claim 3 wherein a different random address is generated for each packet received by the network through an ingress port,

whereby network congestion is reduced as packets are dispersed to random switches within the network before routing to destinations.

5. The adaptively-routed interconnection network of claim 4 wherein a source switch coupled to an ingress port that receives the packet is identified by a source address, the source address being stored in the header,

whereby the header stores switch addresses for the source, destination, and random switches.

6. The adaptively-routed interconnection network of claim 4 wherein the scattering function selects a random switch from a universe of random switches that is less than a complete universe of switches in the network.

7. The adaptively-routed interconnection network of claim 6 wherein the universe of random switches is a function of a relative location of the source and destination switches whereby the link utilization is reduced.

8. The adaptively-routed interconnection network of claim 1 wherein when a packet'"'"'s output links are congested, and a packet'"'"'s waiting time in a switch exceeds a threshold value:

(1) the routing controller sets the phase indicator to indicate the first phase;

(2) the routing controller randomly generates a new random address of another random switch;

(3) the routing controller over-writes the random address in the header with the new random address; and

(4) the routing controller uses the new random address from the header to determine the selected output link, the selected output link being in a route toward the another random switch,

whereby the network avoids congested links by re-routing to the another random switch.

9. The adaptively-routed interconnection network of claim 1 wherein when the selected output link is connected to a faulty switch or a faulty link, the routing controller selects a different output link on a different route toward the random switch when the phase indicator indicates the first phase, or selects different output link on a different route toward the destination switch when the phase indicator indicates the second phase,

whereby the routing controller adapts routing to bypass the faulty switch.

10. The adaptively-routed interconnection network of claim 9 wherein when the selected output link is connected to a faulty switch or faulty link, and the routing controller cannot locate a different output link on a different route toward the random switch when the phase indicator indicates the first phase, or cannot locate a different output link on a different route toward the destination switch when the phase indicator indicates the second phase:

(1) the routing controller sets the phase indicator to indicate the first phase;

(2) the routing controller randomly generates a new random address of another random switch;

(3) the routing controller over-writes the random address in the header with the new random address;

(4) the routing controller uses the new random address from the header to determine the selected output link, the selected output link being in a route toward the another random switch,

whereby the network is fault tolerant since the faulty switch is bypassed by re-routing to the another random switch when only routes through the faulty switch are available.

11. The adaptively-routed interconnection network of claim 10 wherein the routing controller further updates a history field in the header when the faulty switch is the destination switch or the faulty link is a link connected to the destination switch and the phase indicator indicates phase two and wherein the phase indicator is a flag bit in the header or a special encoding of another field in the header.

12. A fault-tolerant method for adaptively routing packets in a multi-dimensional network comprising:

injecting a packet into the network at a source switch;

writing a destination identifier for a destination switch in the network to a header for the packet, the destination switch being connected to a destination port that the packet is being sent to;

randomly generating a random identifier for a random switch within the network;

writing the random identifier for the random switch to the header for the packet;

indicating in the header that the packet is to be routed to the random switch;

sending the packet from the source switch to an intermediate switch on a route to the random switch;

in the source switch and in each intermediate switch, when the header indicates that the packet is being routed to the random switch, determining a next switch in a route toward the random switch using the random identifier;

sending the packet to the next switch, including sending the packet from the intermediate switch to the random switch;

comparing, in the intermediate switch and in the random switch, the random identifier stored in the header to a current identifier for a current switch, and when the current identifier matches the random identifier, indicating in the header that the packet is to be routed to the destination switch;

in the random switch and in each intermediate switch, when the header indicates that the packet is being routed to the destination switch, determining a next switch in a route toward the destination switch using the destination identifier;

sending the packet to the next switch; and

comparing, in the intermediate switch and in the destination switch, the destination identifier stored in the header to a current identifier for a current switch, and when the current identifier matches the destination identifier, removing the packet from the network and transmitting the packet out the destination port;

whereby packets are sent to the random switch and then to the destination switch.

13. The fault-tolerant method of claim 12 further comprising:

when the next switch from a current switch is a faulty switch;

determining another next switch in a different route toward the random switch using the random identifier when the header indicates that the packet is being routed to the random switch;

or

determining another next switch in a different route toward the destination switch using the destination identifier when the header indicates that the packet is being routed to the destination switch; and

sending the packet to the another next switch,

whereby packets are routed around the faulty switch by choosing another route.

14. The fault-tolerant method of claim 13 further comprising:

when the different route is not found or all alternate routes are faulty, routing from the current switch to a second random switch by;

randomly generating a second random identifier for the second random switch within the network;

writing the second random identifier for the second random switch to the header for the packet;

indicating in the header that the packet is to be routed to the second random switch;

determining another next switch in a route toward the second random switch using the second random identifier when the header indicates that the packet is being routed to the second random switch; and

sending the packet from the current switch to an intermediate switch on a route to the second random switch by sending the packet to the another next switch,

whereby packets are routed around the faulty switch by routing to the second random switch.

15. The fault-tolerant method of claim 14 wherein sending the packet from the intermediate switch to the random switch includes sending the packet through other intermediate switches.

16. The fault-tolerant method of claim 15 wherein indicating in the header that the packet is to be routed to the random switch comprises setting a flag bit in the header, and

indicating in the header that the packet is to be routed to the destination switch comprises clearing a bit in the header.

17. The fault-tolerant method of claim 15 wherein indicating in the header that the packet is to be routed to the destination switch comprises over-writing the random identifier in the header with an illegal value that does not indicate any switch in the network.

18. The fault-tolerant method of claim 15 further comprising:

dividing a data stream received by the network into packets;

writing a sequence number to the header of each packet;

re-ordering packets received by the destination switch into an order determined by the sequence number in each packet header,

transmitting data from the packets in the order determined by the sequence numbers as an output data stream transmitted out the destination port,

whereby the data stream is packetized for routing through the network and re-assembled.

19. A fault-tolerant packet-switching network comprising:

ingress port means for receiving packets;

egress port means for transmitting packets;

a plurality of switch means for switching packets, each having;

input link means for receiving packets from other switch means in the network;

output link means for sending packets to other switch means in the network;

packet memory means for storing packets received from the input link means until transmission over the output link means;

wherein each packet stored in the packet memory means has header means for storing;

a destination address of a destination switch means, the destination switch means coupled to a destination egress port means that the packet is to be transmitted out of;

a random address of a random switch means;

phase indicator means for indicating a first phase when the packet is forwarded to the random switch means, and for indicating a second phase when the packet is forwarded to the destination switch means;

routing controller means, reading the header means of a packet to be stored in the packet memory means, for determining a selected output link means in a plurality of output link means to send the packet over;

wherein when the random address read from the header means matches an address of the switch means, resetting the phase indicator means to indicate that the packet is in the second phase and no longer in the first phase;

(1) when the phase indicator means indicates that the packet is in the first phase, using the random address from the header means to determine the selected output link means, the selected output link means being in a route toward the random switch means;

(2) when the phase indicator means indicates that the packet is in the second phase, reading the destination address from the header means to determine the selected output link means, the selected output link means being in a route toward the destination switch means;

wherein the packet is sent over the selected output link means on the route toward the random switch means when the phase indicator means indicates the packet is in the first phase, but the packet is sent over the selected output link means on the route toward the destination switch means when the phase indicator means indicates the packet is in the second phase;

wherein the packet is removed from the network by the destination switch means and transmitted over the egress port means coupled to the destination switch means when the destination switch means determines that the destination address in the header means matches the address of the destination switch means,

whereby packets are routed to the random switch means during the first phase, but routed to the destination switch means during the second phase after the packet reaches the random switch means.

20. The fault-tolerant packet-switching network of claim 19 wherein when the selected output link means is connected to a faulty switch means, and the routing controller means cannot locate a different output link means on a different route toward the random switch means when the phase indicator means indicates the first phase, or cannot locate a different output link means on a different route toward the destination switch means when the phase indicator means indicates the second phase:

(1) the routing controller means sets the phase indicator means to indicate the first phase;

(2) the routing controller means randomly generates a new random address of another random switch means;

(3) the routing controller means over-writes the random address in the header means with the new random address;

(4) the routing controller means uses the new random address from the header means to determine the selected output link means, the selected output link means being in a route toward the another random switch means,

whereby the network is fault tolerant since the faulty switch means is bypassed by re-routing to the another random switch means when only routes through the faulty switch means are available.

21. The fault-tolerant packet-switching network of claim 20 wherein the routing controller means further includes means for attaching an identifier of a faulty output link means to a history means within the header means,

whereby packets destined for faulty switches are identified for elimination from the fault-tolerant packet-switching network.

22. The fault-tolerant packet-switching network of claim 19 wherein a probability of dropping a packet is minimized such that a mean time between dropping packets exceeds a life time of the fault-tolerant packet-switching network, wherein the probability is a function of network topology, link bandwidth, and a maximum amount of time that a packet can live in the network.