Method and apparatus for uninterrupted packet transfer using replication over disjoint paths

• US 7,373,543 B1
• Filed: 04/08/2004
• Issued: 05/13/2008
• Est. Priority Date: 07/31/2000
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: McCloghrie, Keith, Jain, Bijendra N.
• Primary Examiner(s): LE, DIEU MINH T
• Application Number:
  US10/820,257
• Time in Patent Office: 1,496 Days
• Field of Search: 714/4, 714/47, 370/218, 370/217, 370/351, 709/238, 709/239
• US Class Current: 714/4.4
• 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/24 Multipath
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

A method of operating a fault tolerant connection in a network is described. The network includes a number of network elements and a number of links. Each of the network elements is coupled to at least one other of the network elements by at least one of the links. The method identifies a first path and a second path. The first path is between a first one of the network elements and a second one of the network elements, as is the second path. Moreover, the first path and the second path are disjoint. This disjointedness can be any difference between the two paths (e.g., any combination of different network elements or links). A packet is sent from the first one of the network elements via the first path, while a duplicate packet is sent from the first one of the network elements via the second path. The duplicate packet is a duplicate of the packet. Once these packets have been sent, at least one of the packet and the duplicate packet are received at the second one of the network elements. If both the packet and the duplicate packet are received at the second one of the network elements, one of the two is discarded (e.g., by simply ignoring the last one received).

Claims

1. A method comprising:

identifying a first network component in a first path using a first identifier stored in a heap data structure, wherein the first path is between a first node and a second node;

removing the first identifier from the heap data structure;

identifying a second network component in a second path using a second identifier stored in the heap data structure, wherein the second identifier remains in the heap data structure subsequent to the removing the first identifier, the second path is between the first node and the second node, and the first path and the second path are disjoint;

sending a packet from the first node via the first path; and

sending a duplicate of the packet from the first node via the second path.

2. The method of claim 1, further comprising:

identifying a plurality of network components in the first path using identifiers stored in the heap data structure; and

removing the identifiers corresponding to the network components in the first path from the heap data structure.

3. The method of claim 2, further comprising:

storing the plurality of identifiers in the heap data structure, wherein each one of the identifiers represents a corresponding one of a plurality of network components.

4. The method of claim 1, wherein the first and second network components are nodes.

5. The method of claim 1, wherein the first and second network components are links.

6. The method of claim 1, further comprising:

removing the second identifier from the heap data structure;

identifying a third network component, in a third path between the first node and the second node, using a third identifier stored in the heap data structure, wherein the third identifier remains in the heap data structure subsequent to the removing the second identifier, and the first path, the second path, and the third path are disjoint.

7. The method of claim 6, further comprising:

sending an additional duplicate of the packet from the first node via the third path.

8. The method of claim 1, further comprising:

associating a sequence number with each of the packet and the duplicate of the packet.

9. The method of claim 8, further comprising:

receiving both of the packet and the duplicate of the packet at the second node; and

discarding one of the packet and the duplicate in response to the sequence number associated with each of the packet and the duplicate.

10. The method of claim 1, wherein the identifying ones of the network elements in the first path is based on an Open Shortest Path First (OSPF) algorithm.

11. The method of claim 1, wherein the packet is a Voice over Internet Protocol (VoIP) packet.

12. The method of claim 1, wherein sending the packet comprises sending the packet according to a label-switching protocol.

13. The method of claim 1, further comprising:

storing cost and topology information, wherein

the cost and topology information is used to identify the first path.

14. A computer readable storage medium storing program instructions executable by a processor to:

identify a first network component, in a first path between a first node and a second node, using an identifier stored in a heap data structure;

remove the identifier corresponding to the first network component from the heap data structure;

identify a second network component, in a second path between the first node and the second node, using a second identifier stored in the heap data structure, wherein the second identifier remains in the heap data structure subsequent to removal of the first identifier, and the first path and the second path are disjoint;

send a packet from the first node via the first path; and

send a duplicate of the packet from the first node via the second path.

15. The computer readable storage medium of claim 14, wherein the program instructions are further executable to:

identify a plurality of network components in the first path using identifiers stored in the heap data structure; and

remove the identifiers corresponding to the network components in the first path from the heap data structure.

16. The computer readable storage medium of claim 15, wherein the program instructions are further executable to:

store identifiers in the heap data structure, wherein each one of the identifiers represents a corresponding one of a plurality of network components.

17. The computer readable storage medium of claim 14, wherein the first and second network components are nodes.

18. The computer readable storage medium of claim 14, wherein the first and second network components are links.

19. The computer readable storage medium of claim 14, wherein the program instructions are further executable to:

associate a sequence number with each of the packet and the duplicate of the packet.

20. The computer readable storage medium of claim 14, wherein ones of the network elements in the first path are identified based on an Open Shortest Path First (OSPF) algorithm.

21. The computer readable storage medium of claim 20, wherein

the packet is a Voice over Internet Protocol (VoIP) packet.

22. The computer readable storage medium of claim 14, wherein the packet is sent according to a label-switching protocol.

23. The computer readable storage medium of claim 14, wherein the program instructions are further executable to:

store cost and topology information, wherein

the cost and topology information is used to identify the first path.

24. A system comprising:

means for storing a heap data structure;

means for identifying a first network component in a first path using an identifier stored in the heap data structure, wherein the first path is between a first node and a second node;

means for removing the identifier corresponding to the first network component from the heap data structure;

means for identifying a second network component in a second path using a second identifier stored in the heap data structure, wherein the second identifier remains in the heap data structure subsequent to removal of the first identifier, the second path is between the first node and the second node, and the first path and the second path are disjoint;

means for sending a packet from the first node via the first path; and

means for sending a duplicate of the packet from the first node via the second path.

25. The system of claim 24, further comprising:

means for identifying a plurality of network components in the first path using identifiers stored in the heap data structure; and

means for removing the identifiers corresponding to the network components in the first path from the heap data structure.

26. The system of claim 25, further comprising:

means for identifying a plurality of network components in the first path using identifiers stored in the heap data structure; and

means for removing the identifiers corresponding to the network components in the first path from the heap data structure.

27. The system of claim 24, further comprising:

means for storing identifiers in the heap data structure, wherein each one of the identifiers represents a corresponding one of a plurality of network components.

28. The system of claim 24, wherein the first and second network components are nodes.

29. The system of claim 24, wherein the first and second network components are links.

30. The system of claim 24, further comprising:

means for associating a sequence number with each of the packet and the duplicate of the packet.

31. The system of claim 24, wherein ones of the network elements in the first path are identified based on an Open Shortest Path First (OSPF) algorithm.

32. The system of claim 24, wherein the packet is a Voice over Internet Protocol (VoIP) packet.

33. The system of claim 24, wherein the packet is sent according to a label-switching protocol.

34. The system of claim 24, further comprising:

means for storing cost and topology information, wherein the cost and topology information is used to identify the first path.

35. A system comprising:

a first node;

a second node;

a first path between the first node and the second node; and

a second path between the first node and the second node, wherein the first node is configured to;

identify a first network components in the first path using a first identifier stored in a heap data structure,

remove the first identifier from the heap data structure,

identify a second network component in the second path using a second identifier stored in the heap data structure, wherein the second identifier remains in the heap data structure subsequent to removal of the first identifier, and the first path and the second path are disjoint,

send a packet via the first path, and

send a duplicate of the packet via the second path.

36. The system of claim 35, wherein the first node is configured to:

identify a plurality of network components in the first path using identifiers stored in the heap data structure; and

remove the identifiers corresponding to the network components in the first path from the heap data structure.

37. The system of claim 36, wherein the first node is configured to:

store identifiers in the heap data structure, each one of the identifiers representing a corresponding one of a plurality of network components.

38. The system of claim 35, wherein the first and second network components are nodes.

39. The system of claim 35, wherein the first and second network components are links.

40. The system of claim 35, wherein the first node is further configured to:

associate a sequence number with each of the packet and the duplicate of the packet.

41. The system of claim 35, wherein the first node identifies the ones of the network elements in the first path based on an Open Shortest Path First (OSPF) algorithm.

42. The system of claim 41, wherein the packet is a Voice over Internet Protocol (VoIP) packet.

43. The system of claim 35, wherein the first node is sends the packet according to a label-switching protocol.