Fault tolerant network routing

• US 7,796,503 B2
• Filed: 09/03/2002
• Issued: 09/14/2010
• Est. Priority Date: 09/03/2002
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Czezowski, Peter J., Su, Ching-Fong, Hamada, Takeo
• Primary Examiner(s): Rao; Seema S
• Assistant Examiner(s): Wu; Jianye
• Application Number:
  US10/234,308
• Publication Number:
  US 20040042418A1
• Time in Patent Office: 2,933 Days
• Field of Search: 370/256, 370/225, 370/228, 714/4
• US Class Current: 370/225
• 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/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

A network provides fault tolerant network routing by identifying root nodes that provide cover against a particular type of fault. Nodes then route copies of packets through these root nodes such that an occurrence of the particular type of fault will not disrupt delivery of the packets.

Claims

1. A method for fault tolerant packet routing, the method comprising:

generating a packet within a network node coupled to a plurality of other network nodes, the packet for delivery to a destination one of the other network nodes;

identifying a plurality of root ones of the other network nodes, the root nodes providing cover against a class of fault within a network segment formed by the network node and the other network nodes; and

tunneling a copy of the packet to each of the root nodes.

2. The method of claim 1, further comprising:

receiving a tunneled packet from one of the other network nodes;

extracting an encapsulated packet from the tunneled packet;

selecting a link for transmitting the extracted packet based upon a destination address of the extracted packet; and

transmitting the extracted packet on the selected link.

3. The method of claim 1, further comprising:

receiving a plurality of packet copies communicated from the root nodes;

determining that the packet copies are duplicates of each other; and

discarding extra ones of the packet copies.

4. The method of claim 3, wherein determining that the packet copies are duplicates comprises comparing TCP/IP sequence numbers of the packet copies.

5. The method of claim 1, wherein the network segment is at least a two connected network, and the copies of the packet are transmitted from the network node on at least two links from the network node.

6. The method of claim 1, further comprising:

identifying a routing path from the network node to the destination network node; and

transmitting the packet on the identified routing path.

7. The method of claim 1, wherein each node within the network segment uses a minimum hop routing tree to route packets to each other node within the network segment.

8. The method of claim 7, wherein the routing trees from the root nodes provide cover against any single link fault within the network segment.

9. The method of claim 7, wherein tunneling a copy of the packet to one of the root nodes comprises:

encapsulating the copy of the packet within a tunneled packet; and

transmitting the tunneled packet on a path to the root node that reverses the routing tree from the root node to the network node.

10. A network node comprising:

an interface operable to couple to a plurality of other network nodes forming a network segment, the interface further operable to link directly to at least two of the other network nodes; and

a processor operable to generate a packet for delivery to a destination one of the other network nodes and to identify a plurality of root ones of the other network nodes, the root nodes providing cover against a class of fault within the network segment, the processor further operable to tunnel a copy of the packet to each of the root nodes using the interface.

11. The network node of claim 10, wherein:

the interface is further operable to receive a tunneled packet from one of the other network nodes; and

the processor is further operable to extract an encapsulated packet from the tunneled packet, to select a link from the interface for transmitting the extracted packet based upon a destination address of the extracted packet, and to transmit the extracted packet on the selected link.

12. The network node of claim 10, wherein:

the interface is further operable to receive a plurality of packet copies communicated from the root nodes; and

the processor is further operable to determine that the packet copies are duplicates of each other and to discard extra ones of the packet copies.

13. The network node of claim 12, wherein the processor is further operable to determine that the packet copies are duplicates by comparing TCP/IP sequence numbers of the packet copies.

14. The network node of claim 10, wherein the network segment is at least a two connected network, and wherein the processor transmits the copies of the packet on at least two links from the interface.

15. The network node of claim 10, wherein the processor is further operable to identify a routing path to the destination network node and transmit the packet on the identified routing path.

16. The network node of claim 10, wherein each node within the network segment uses a minimum hop routing tree to route packets to each other node within the network segment.

17. The network node of claim 16, wherein the routing trees from the root nodes provide cover against any single link fault within the network segment.

18. The network node of claim 16, wherein the processor is further operable to tunnel a copy of the packet to one of the root nodes by:

encapsulating the copy of the packet within a tunneled packet; and

transmitting the tunneled packet on a path to the root node that reverses the routing tree from the root node to the network node.

19. The network node of claim 10, further comprising a memory maintaining a list of the root nodes and a routing table implementing a routing tree from the network node.

20. A non-transitory computer readable medium storing logic for fault tolerant packet routing, the logic operable when executed to perform the steps of:

generating a packet within a network node coupled to a plurality of other network nodes, the packet for delivery to a destination one of the other network nodes;

identifying a plurality of root ones of the other network nodes, the root nodes providing cover against a class of fault within a network segment formed by the network node and the other network nodes; and

tunneling a copy of the packet to each of the root nodes.

21. The non-transitory computer readable medium claim 20, further operable to perform the steps of:

receiving a tunneled packet from one of the other network nodes;

extracting an encapsulated packet from the tunneled packet;

selecting a link for transmitting the extracted packet based upon a destination address of the extracted packet; and

transmitting the extracted packet on the selected link.

22. The non-transitory computer readable medium of claim 20, further operable to perform the steps of:

receiving a plurality of packet copies communicated from the root nodes;

determining that the packet copies are duplicates of each other; and

discarding extra ones of the packet copies.

23. The non-transitory computer readable medium of claim 22, wherein determining that the packet copies are duplicates comprises comparing TCP/IP sequence numbers of the packet copies.

24. The non-transitory computer readable medium of claim 20, wherein the network segment is at least a two connected network, and the copies of the packet are transmitted from the network node on at least two links from the network node.

25. The non-transitory computer readable medium of claim 20, further operable to perform the steps of:

identifying a routing path from the network node to the destination network node; and

transmitting the packet on the identified routing path.

26. The non-transitory computer readable medium of claim 20, wherein each node within the network segment uses a minimum hop routing tree to route packets to each other node within the network segment.

27. The non-transitory computer readable medium of claim 20, wherein the routing trees from the root nodes provide cover against any single link fault within the network segment.

28. The non-transitory computer readable medium of claim 20, wherein tunneling a copy of the packet to one of the root nodes comprises:

encapsulating the copy of the packet within a tunneled packet; and

transmitting the tunneled packet on a path to the root node that reverses the routing tree from the root node to the network node.

29. A network node comprising:

means for generating a packet within a network node coupled to a plurality of other network nodes, the packet for delivery to a destination one of the other network nodes;

means for identifying a plurality of root ones of the other network nodes, the root nodes providing cover against a class of fault within a network segment formed by the network node and the other network nodes; and

means for tunneling a copy of the packet to each of the root nodes.

30. A method for fault tolerant packet routing, the method comprising:

in a first mode of operation,

generating a packet within a network node coupled to a plurality of other network nodes, the packet for delivery to a destination one of the other network nodes;

identifying a plurality of root ones of the other network nodes, the root nodes providing cover against a class of fault within a network segment formed by the network node and the other network nodes, wherein each node within the network segment uses a minimum hop routing tree to route packets to each other node within the network segment and the routing trees from the root nodes provide cover against any single link fault within the network segment; and

tunneling a copy of the packet to each of the root nodes;

in a second mode of operation,

receiving a tunneled packet from one of the other network nodes;

extracting an encapsulated packet from the tunneled packet;

selecting a link for transmitting the extracted packet based upon a destination address of the extracted packet; and

transmitting the extracted packet on the selected link; and

in a third mode of operation,

receiving a plurality of packet copies communicated from the root nodes;

determining that the packet copies are duplicates of each other; and

discarding extra ones of the packet copies.