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

• US 6,751,746 B1
• Filed: 07/31/2000
• Issued: 06/15/2004
• Est. Priority Date: 07/31/2000
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Jain, Bijendra N., McCloghrie, Keith
• Primary Examiner(s): LE, DIEU MINH T
• Application Number:
  US09/629,585
• Time in Patent Office: 1,415 Days
• Field of Search: 714/4, 714/3, 714/47, 714/712, 714/748, 370/235, 370/252, 370/217, 370/244, 370/394, 370/428, 370/218
• US Class Current: 714/4.12
• 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 of operating a fault tolerant connection in a network, wherein said network comprises a plurality of network elements and each one of said network elements is coupled to at least one other of said network elements by at least one of a plurality of links, comprising:

identifying a first path, wherein said first path is between a first one of said network elements and a second one of said network elements;

identifying a second path, wherein

said second path is between said first one and said second one of said network elements, and

said first path and said second path are disjoint;

sending a packet from said first one of said network elements via said first path using a label-switching protocol;

sending a duplicate packet from said first one of said network elements via said second path using the label-switching protocol, wherein said duplicate packet is a duplicate of said packet,

receiving at least one of said packet and said duplicate packet at said second one of said network elements; and

discarding one of said packet and said duplicate packet, if both said packet and said duplicate packet are received at said second one of said network elements,

wherein said first path and said second path are node-disjoint,

wherein said identifying said first path and said identifying said second path comprise;

storing cost and topology information representing said network in a sparse matrix;

storing identifiers in a heap data structure, wherein each one of said identifiers represents a corresponding one of said network elements;

identifying ones of said network elements in said first path using identifiers stored in said heap data structure;

removing ones of said identifiers corresponding to said ones of said network elements in said first path from said heap data structure; and

identifying ones of said network elements in said second path using identifiers still stored in said heap data structure.

2. The method of claim 1, wherein said sparse matrix is stored in an AVL binary search tree.

3. The method of claim 1, wherein said first path is a shortest node-disjoint path and said second path is a second-shortest node-disjoint path.

4. The method of claim 3, wherein said identifying said ones of said network elements in said first path and said identifying said ones of said network elements in said second path are performed using an open shortest path first (OSPF) algorithm.

5. The method of claim 1, wherein said first path and said second path each include ones of said network elements and said links.

6. A method of operating a fault tolerant connection in a network, wherein said network comprises a plurality of network elements and each one of said network elements is coupled to at least one other of said network elements by at least one of a plurality of links, comprising:

identifying a first path, wherein said first path is between a first one of said network elements and a second one of said network elements;

identifying a second path, wherein

said second path is between said first one and said second one of said network elements, and

said first path and said second path are disjoint;

sending a packet from said first one of said network elements via said first path using a label-switching protocol;

sending a duplicate packet from said first one of said network elements via said second path using the label-switching protocol, wherein said duplicate packet is a duplicate of said packet,

receiving at least one of said packet and said duplicate packet at said second one of said network elements; and

discarding one of said packet and said duplicate packet, if both said packet and said duplicate packet are received at said second one of said network elements,

wherein said first path and said second path are link disjoint,

wherein said identifying said first path and said identifying said second path comprise;

storing cost and topology information representing said network in a sparse matrix;

storing identifiers in a heap data structure, wherein each one of said identifiers represents a corresponding one of said links;

identifying ones of said links in said first path using identifiers stored in said heap data structure;

removing ones of said identifiers corresponding to said ones of said links in said first path from said heap data structure; and

identifying ones of said network elements in said second path using identifiers still stored in said heap data structure.

7. The method of claim 6, wherein said first path and said second path are node-disjoint.

8. The method of claim 6, wherein said first path is a shortest link-disjoint path and said second path is a second-shortest link-disjoint path.

9. The method of claim 8, wherein said identifying said ones of said network elements in said first path and said identifying said ones of said network elements in said second path are performed using an open shortest path first (OSPF) algorithm.

10. The method of claim 6, wherein said sparse matrix is stored in an AVL binary search tree.

11. A computer system comprising:

a processor;

a network interface, coupled to said processor and to a network, wherein said network comprises a plurality of network elements and each one of said network elements is coupled to at least one other of said network elements by at least one of a plurality of links;

computer readable medium coupled to said processor; and

computer code, encoded in said computer readable medium, configured to cause said processor to;

identify a first path, wherein said first path is between a first one of said network elements and a second one of said network elements;

identify a second path, wherein

said second path is between said first one and said second one of said network elements, and

said first path and said second path are disjoint;

send a packet from said first one of said network elements via said first path using a label-switching protocol; and

send a duplicate packet from said first one of said network elements via said second path using the label-switching protocol, wherein said duplicate packet is a duplicate of said packet,

wherein said second one of said network elements is configured to receive at least one of said packet and said duplicate packet,

wherein said second one of said network elements is further configured to discard one of said packet and said duplicate packet, if both said packet and said duplicate packet are received at said second one of said network elements,

wherein said first path and said second path are node-disjoint,

wherein said computer code configured to cause said processor to identify said first path and to identify said second path is further configured to cause said processor to;

store cost and topology information representing said network in a sparse matrix;

store identifiers in a heap data structure, wherein each one of said identifiers represents a corresponding one of said network elements;

identify ones of said network elements in said first path using identifiers stored in said heap data structure;

remove ones of said identifiers corresponding to said ones of said network elements in said first path from said heap data structure; and

identify ones of said network elements in said second path using identifiers still stored in said heap data structure.

12. The computer system of claim 11, wherein said sparse matrix is stored in an AVL binary search tree.

13. The computer system of claim 11, wherein said first path is a shortest node-disjoint path and said second path is a second-shortest node-disjoint path.

14. The computer system of claim 13, wherein said identifying said ones of said network elements in said first path and said identifying said ones of said network elements in said second path are performed using an open shortest path first (OSPF) algorithm.

15. The computer system of claim 11, wherein said first path and said second path each include ones of said network elements and said links.

16. The computer system of claim 11, wherein said first one of said network elements comprises said computer system.

17. A computer system comprising:

a processor,

a network interface, coupled to said processor and to a network, wherein said network comprises a plurality of network elements and each one of said network elements is coupled to at least one other of said network elements by at least one of a plurality of links;

computer readable medium coupled to said processor; and

computer code, encoded in said computer readable medium, configured to cause said processor to;

identify a first path, wherein said first path is between a first one of said network elements and a second one of said network elements;

identify a second path, wherein

said second path is between said first one and said second one of said network elements, and

said first path and said second path are disjoint;

send a packet from said first one of said network elements via said first path using a label-switching protocol; and

send a duplicate packet from said first one of said network elements via said second path using the label-switching protocol, wherein said duplicate packet is a duplicate of said packet,

wherein said second one of said network elements is configured to receive at least one of said packet and said duplicate packet,

wherein said second one of said network elements is further configured to discard one of said packet and said duplicate packet, if both said packet and said duplicate packet are received at said second one of said network elements,

wherein said first path and said second path are link disjoint, wherein said computer code configured to cause said processor to identify said first path and to identify said second path is further configured to cause said processor to;

store cost and topology information representing said network in a sparse matrix;

store identifiers in a heap data structure, wherein each one of said identifiers represents a corresponding one of said links;

identify ones of said links in said first path using identifiers stored in said heap data structure;

remove ones of said identifiers corresponding to said ones of said links in said first path from said heap data structure; and

identify ones of said network elements in said second path using identifiers still stored in said heap data structure.

18. The computer system of claim 17, wherein said first path and said second path are node-disjoint.

19. The computer system of claim 17, wherein said sparse matrix is stored in an AVL binary search tree.

20. The computer system of claim 17, wherein said first path is a shortest link-disjoint path and said second path is a second-shortest link-disjoint path.

21. The computer system of claim 20, wherein said identifying said ones of said network elements in said first path and said identifying said ones of said network elements in said second path are performed using an open shortest path first (OSPF) algorithm.

22. A computer program product encoded in computer readable media, said computer program product comprising:

a first set of instructions, executable on a computer system, configured to identify a first path, wherein said first path is between a first one of said network elements and a second one of said network elements;

a second set of instructions, executable on said computer system, configured to identify a second path, wherein

said second path is between said first one and said second one of said network elements, and

said first path and said second path are disjoint;

a third set of instructions, executable on said computer system, configured to send a packet from said first one of said network elements via said first path using a label-switching protocol; and

a fourth set of instructions, executable on said computer system, configured to send a duplicate packet from said first one of said network elements via said second path using a label-switching protocol, wherein said duplicate packet is a duplicate of said packet,

wherein said second one of said network elements is configured to receive at least one of said packet and said duplicate packet,

wherein said second one of said network elements is further configured to discard one of said packet and said duplicate packet, if both said packet and said duplicate packet are received at said second one of said network elements,

wherein said first path and said second path are node-disjoint,

wherein said first and said second sets of instructions each comprises;

a first sub-set of instructions, executable on said computer system, configured to store cost and topology information representing said network in a sparse matrix;

a second sub-set of instructions, executable on said computer system, configured to store identifiers in a heap data structure, wherein each one of said identifiers represents a corresponding one of said network elements;

a third sub-set of instructions, executable on said computer system, configured to identify ones of said network elements in said first path using identifiers stored in said heap data structure;

a fourth sub-set of instructions, executable on said computer system, configured to remove ones of said identifiers corresponding to said ones of said network elements in said first path from said heap data structure; and

a fifth sub-set of instructions, executable on said computer system, configured to identify ones of said network elements in said second path using identifiers still stored in said heap data structure.

23. The computer program product of claim 22, wherein said sparse matrix is stored in an AVL binary search tree.

24. The computer program product of claim 22, wherein said first path is a shortest node-disjoint path and said second path is a second-shortest node-disjoint path.

25. The computer program product of claim 24, wherein said identifying said ones of said network elements in said first path and said identifying said ones of said network elements in said second path are performed using an open shortest path first (OSPF) algorithm.

26. A computer program product encoded in computer readable media, said computer program product comprising:

a first set of instructions, executable on a computer system, configured to identify a first path, wherein said first path is between a first one of said network elements and a second one of said network elements;

a second set of instructions, executable on said computer system, configured to identify a second path, wherein

said second path is between said first one and said second one of said network elements, and

said first path and said second path are disjoint;

a third set of instructions, executable on said computer system, configured to send a packet from said first one of said network elements via said first path using a label-switching protocol; and

a fourth set of instructions, executable on said computer system, configured to send a duplicate packet from said first one of said network elements via said second path using a label-switching protocol, wherein said duplicate packet is a duplicate of said packet,

wherein said second one of said network elements is configured to receive at least one of said packet and said duplicate packet,

wherein said second one of said network elements is further configured to discard one of said packet and said duplicate packet, if both said packet and said duplicate packet are received at said second one of said network elements,

wherein said first path and said second path are link-disjoint,

wherein said first and said second sets of instructions each comprises;

a first sub-set of instructions, executable on said computer system, configured to store cost and topology information representing said network in a sparse matrix;

a second sub-set of instructions, executable on said computer system, configured to store identifiers in a heap data structure, wherein each one of said identifiers represents a corresponding one of said links;

a third sub-set of instructions, executable on said computer system, configured to identify ones of said links in said first path using identifiers stored in said heap data structure;

a fourth sub-set of instructions, executable on said computer system, configured to remove ones of said identifiers corresponding to said ones of said links in said first path from said heap data structure; and

a fifth sub-set of instructions, executable on said computer system, configured to identify ones of said network elements in said second path using identifiers still stored in said heap data structure.

27. The computer program product of claim 26, wherein said first path and said second path are node-disjoint.

28. The computer program product of claim 26, wherein said sparse matrix is stored in an AVL binary search tree.

29. The computer program product of claim 26, wherein said first path is a shortest link-disjoint path and said second path is a second-shortest link-disjoint path.

30. The computer program product of claim 29, wherein said identifying said ones of said network elements in said first path and said identifying said ones of said network elements in said second path are performed using an open shortest path first (OSPF) algorithm.

31. The computer program product of claim 26, wherein said first path and said second path each include ones of said network elements and said links.

32. The computer program product of claim 26, wherein said first one of said network elements comprises said computer system.

33. An apparatus for providing a fault tolerant connection in a network, wherein said network comprises a plurality of network elements and each one of said network elements is coupled to at least one other of said network elements by at least one of a plurality of links, comprising:

means for identifying a first path, wherein said first path is between a first one of said network elements and a second one of said network elements;

means for identifying a second path, wherein

said second path is between said first one and said second one of said network elements, and

said first path and said second path are disjoint;

means for sending a packet from said first one of said network elements via said first path using a label-switching protocol;

means for sending a duplicate packet from said first one of said network elements via said second path using the label-switching protocol, wherein said duplicate packet is a duplicate of said packet;

means for receiving at least one of said packet and said duplicate packet at said second one of said network elements; and

means for discarding one of said packet and said duplicate packet, if both said packet and said duplicate packet are received at said second one of said network elements

wherein said first path and said second path are node-disjoint,

wherein said means for identifying said first path and said means for identifying said second path comprise;

means for storing cost and topology information representing said network in a sparse matrix;

means for storing identifiers in a heap data structure, wherein each one of said identifiers represents a corresponding one of said network elements;

means for identifying ones of said network elements in said first path using identifiers stored in said heap data structure;

means for removing ones of said identifiers corresponding to said ones of said network elements in said first path from said heap data structure; and

means for identifying ones of said network elements in said second path using identifiers still stored in said heap data structure.

34. The apparatus of claim 33, wherein said sparse matrix is stored in an AVL binary search tree.

35. The apparatus of claim 33, wherein said first path is a shortest node-disjoint path and said second path is a second-shortest node-disjoint path.

36. The apparatus of claim 35, wherein said means for identifying said ones of said network elements in said first path and said means for identifying said ones of said network elements in said second path employ an open shortest path first (OSPF) algorithm.

37. An apparatus for providing a fault tolerant connection in a network, wherein said network comprises a plurality of network elements and each one of said network elements is coupled to at least one other of said network elements by at least one of a plurality of links, comprising:

means for identifying a first path, wherein said first path is between a first one of said network elements and a second one of said network elements;

means for identifying a second path, wherein

said second path is between said first one and said second one of said network elements, and

said first path and said second path are disjoint;

means for sending a packet from said first one of said network elements via said first path using a label-switching protocol;

means for sending a duplicate packet from said first one of said network elements via said second path using the label-switching protocol, wherein said duplicate packet is a duplicate of said packet;

means for receiving at least one of said packet and said duplicate packet at said second one of said network elements; and

means for discarding one of said packet and said duplicate packet, if both said packet and said duplicate packet are received at said second one of said network elements

wherein said first path and said second path are link-disjoint,

wherein said means for identifying said first path and said means for identifying said second path comprise;

means for storing cost and topology information representing said network in a sparse matrix;

means for storing identifiers in a heap data structure, wherein each one of said identifiers represents a corresponding one of said links;

means for identifying ones of said links in said first path using identifiers stored in said heap data structure;

means for removing ones of said identifiers corresponding to said ones of said links in said first path from said heap data structure; and

means for identifying ones of said network elements in said second path using identifiers still stored in said heap data structure.

38. The apparatus of claim 37, wherein said sparse matrix is stored in an AVL binary search tree.

39. The apparatus of claim 37, wherein said first path is a shortest link-disjoint path and said second path is a second-shortest link-disjoint path.

40. The apparatus of claim 39, wherein said means for identifying said ones of said network elements in said first path and said means for identifying said ones of said network elements in said second path employ an open shortest path first (OSPF) algorithm.

41. The apparatus of claim 39, wherein said first path and said second path each include ones of said network elements and said links.

42. The apparatus of claim 37, wherein said first path and said second path are node-disjoint.