Method and apparatus for constructing a backup route in a data communications network

• US 7,707,307 B2
• Filed: 01/09/2003
• Issued: 04/27/2010
• Est. Priority Date: 01/09/2003
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Previdi, Stefano Benedetto, Harper, John Anthony, Shand, Ian Michael Charles, Miles, Kevin George, Filsfils, Clarence, Bryant, Stewart Frederick
• Primary Examiner(s): Abdullahi; Salad
• Application Number:
  US10/340,371
• Publication Number:
  US 20070038767A1
• Time in Patent Office: 2,665 Days
• Field of Search: 709/239, 709/242, 709/238, 709/241, 370/223, 370/256, 370/475, 370/252, 370/470, 370/238, 370/229, 370/232, 370/235
• US Class Current: 709/239
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/484 using multiple routing trees
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

A method is disclosed for constructing a backup route from a source node around an adjacent component. The source node derives a first set of nodes reachable from it without traversing the adjacent component and a second set of nodes from which a neighbor node of adjacent components is reachable without traversing the adjacent component. The source node then constructs a backup route via an intermediate node in the intersection of the first and second sets.

Claims

1. A method of constructing a backup route for a primary route in a data communications network, said data communications network having as components nodes and links defining a network topology, said primary route including a first node, an adjacent component that is adjacent to the first node, and a second node that neighbors the adjacent component, the method comprising:

(a) deriving from the topology a first set of nodes reachable from the first node without traversing the adjacent component, wherein the first set of nodes is different from the primary route;

(b) deriving from the topology a second set of nodes from which the second node is reachable without traversing the adjacent component, wherein the second set of nodes is different from the primary route;

(c) determining an intersection of the first set of nodes and the second set of nodes, the intersection comprising an intermediate node, wherein the intermediate node is neither the adjacent component nor in the primary route; and

(d) constructing the backup route via the intermediate node;

wherein the backup route includes the first node and the second node, but does not traverse the adjacent component;

wherein the backup route is different from the first set of nodes and the second set of nodes;

wherein the method is performed by one or more computing devices.

2. A method as claimed in claim 1, further comprising the step of constructing at least one backup route around each component adjacent to the first node prior to any of the components adjacent to the first node failing.

3. A method as claimed in claim 1, further comprising the step of constructing a plurality of backup routes, each of said plurality of backup routes including a different neighbor node of the adjacent component that would be normally reached via the adjacent component.

4. A method as claimed in claim 1, further comprising carrying out the step of applying the backup route around the adjacent component in the event of at least one of adjacent component failure, adjacent component de-activation or adjacent component overload.

5. A method as claimed in claim 4 further comprising causing data to follow the backup route instead of the primary route by tunneling the data from the first node to an endpoint comprising the intermediate node.

6. A method as claimed in claim 5, in which the reachable nodes include all nodes that are reachable via a routing mechanism and additional nodes that are reachable therefrom via a forwarding mechanism without traversing the adjacent component.

7. A method as claimed in claim 6, in which the tunneling mechanism comprises one of directed forwarding or multiple tunneling, or loose or strict source routing.

8. A method as claimed in claim 7, in which the data is tunneled unless the intermediate node is a neighbor of the first node and the predetermined forwarding mechanism is not required.

9. A method as claimed in claim 1, in which the reachable nodes include nodes reachable from a neighbor node of the repairing node without traversing the adjacent component.

10. A method as claimed in claim 1, further comprising the step of deriving the first and second sets of nodes using a link state routing protocol.

11. A method as claimed in claim 10, in which the first and second sets of nodes comprise forward and reverse spanning trees respectively.

12. A method as claimed in claim 1 wherein the steps of deriving the first set of nodes and the second set of nodes are performed by iteratively adding nodes to the first set of nodes and the second set of nodes until the intermediate node is identified.

13. A method as claimed in claim 1 where the adjacent component comprises one of an adjacent node and an adjacent link between the first node and the adjacent node, and further comprising the steps of:

identifying as an unavailable node any neighbor node of the adjacent node for which a backup route is unavailable,

treating the adjacent node as the adjacent component, deriving from the topology a third set of nodes reachable from the repair node with the adjacent node removed, and

if no unavailable node is included in the third set, constructing a backup route treating the adjacent link as the adjacent component.

14. A computer readable storage medium comprising one or more sequences of instructions for constructing a backup route for a primary route in a data communications network, said data communications network having as components nodes and links defining a network topology, said primary route including a first node, an adjacent component that is adjacent to the first node, and a second node that neighbors the adjacent component, which instructions, when executed by one or more processors, cause the one or more processors to perform:

(a) deriving from the topology a first set of nodes reachable from the first node without traversing the adjacent component, wherein the first set of nodes is different from the primary route;

(b) deriving from the topology a second set of nodes from which the second node is reachable without traversing the adjacent component, wherein the second set of nodes is different from the primary route;

(c) determining an intersection of the first set of nodes and the second set of nodes, the intersection comprising an intermediate node, wherein the intermediate node is neither the adjacent component nor in the primary route; and

(d) constructing the backup route via the intermediate node;

wherein the backup route includes the first node and the second node, but does not traverse the adjacent component;

wherein the backup route is different from the first set of nodes and the second set of nodes.

15. An apparatus for constructing a backup route for a primary route in a data communications network, said data communications network having as components nodes and links defining a network topology, said primary route including a first node, an adjacent component that is adjacent to the first node, and a second node that neighbors the adjacent component, the apparatus comprising:

(a) means for deriving from the topology a first set of nodes reachable from the first node without traversing the adjacent component, wherein the first set of nodes is different from the primary route;

(b) means, deriving from the topology a second set of nodes from which the second node is reachable without traversing the adjacent component, wherein the second set of nodes is different from the primary route;

(c) means for determining an intersection of the first set of nodes and the second set of nodes, the intersection comprising an intermediate node, wherein the intermediate node is neither the adjacent component nor in the primary route; and

(d) means for constructing the backup route via the intermediate node;

wherein the backup route includes the first node and the second node, but does not traverse the adjacent component;

wherein the backup route is different from the first set of nodes and the second set of nodes.

16. An apparatus as claimed in claim 15, further comprising means for constructing at least one backup route around each component adjacent to the first node prior to any of the components adjacent to the first node failing.

17. An apparatus as claimed in claim 15, further comprising means for constructing a plurality of backup routes, each of said plurality of backup routes including a different neighbor node of the adjacent component that would be normally reached via the adjacent component.

18. An apparatus as claimed in claim 15, further comprising means for carrying out the step of applying the backup route around the adjacent component in the event of at least one of adjacent component failure, adjacent component de-activation or adjacent component overload.

19. An apparatus as claimed in claim 18 further comprising means for causing data to follow the backup route instead of the primary route by tunneling the data from the first node to an endpoint comprising the intermediate node.

20. An apparatus as claimed in claim 19, in which the reachable nodes include all nodes reachable via a routing mechanism and additional nodes reachable therefrom via a forwarding mechanism without traversing the adjacent component.

21. An apparatus as claimed in claim 20, in which the tunneling mechanism comprises one of directed forwarding or multiple tunneling, or loose or strict source routing.

22. An apparatus as claimed in claim 21, further comprising means for tunneling the data unless the intermediate node is a neighbor of the first node and the forwarding mechanism is not required.

23. An apparatus as claimed in claim 15, in which the reachable nodes include nodes reachable from a neighbor node of the repairing node without traversing the adjacent component.

24. An apparatus as claimed in claim 15, further comprising means for deriving the first and second sets of nodes using a link state routing protocol.

25. An apparatus as claimed in claim 24, in which the first and second sets of nodes comprise forward and reverse spanning trees respectively.

26. An apparatus as claimed in claim 15 wherein the means for deriving the first set of nodes and the second set of nodes derive the first set of nodes and the second set of nodes by iteratively adding nodes to the first set of nodes and the second set of nodes until the intermediate node is identified.

27. An apparatus as claimed in claim 15 where the adjacent component comprises one of an adjacent node and an adjacent link between the first node and the adjacent node, further comprising means for identifying as an unavailable node any neighbor node of the adjacent node for which a backup route is unavailable, treating the adjacent node as the adjacent component, deriving from the topology a third set of nodes reachable from the repair node with the adjacent node removed, and if no unavailable node is included in the third set, constructing a backup route treating the adjacent link as the adjacent component.

28. An apparatus for constructing a backup route from a repairing node in a data communications network having as components nodes and links defining a network topology, around an adjacent component, the apparatus comprising:

a processor;

a network interface communicatively coupled to the processor and configured to communicate one or more packet flows among the processor and a network; and

a computer readable medium comprising one or more sequences of instructions for constructing a backup route for a primary route in a data communications network, said data communications network having as components nodes and links defining a network topology, said primary route including a first node, an adjacent component that is adjacent to the first node, and a second node that neighbors the adjacent component, which instructions, when executed by the processor, cause the processor to perform;

(a) deriving from the topology a first set of nodes reachable from the first node without traversing the adjacent component, wherein the first set of nodes is different from the primary route;

(b) deriving from the topology a second set of nodes from which the second node is reachable without traversing the adjacent component, wherein the second set of nodes is different from the primary route;

(c) determining an intersection of the first set of nodes and the second set of nodes, the intersection comprising an intermediate node, wherein the intermediate node is neither the adjacent component nor in the primary route; and

(d) constructing the backup route via the intermediate node;

wherein the backup route includes the first node and the second node, but does not traverse the adjacent component;

wherein the backup route is different from the first set of nodes and the second set of nodes.

29. An apparatus as claimed in claim 28, further comprising sequences of instructions which when executed cause constructing a plurality of backup routes, each of said plurality of backup routes including a different neighbor node of the adjacent component that would be normally reached via the adjacent component.

30. An apparatus as claimed in claim 28, further comprising sequences of instructions which when executed cause applying the backup route around the adjacent component in the event of at least one of adjacent component failure, adjacent component de-activation or adjacent component overload.

31. An apparatus as claimed in claim 30 further comprising sequences of instructions which when executed cause data to follow the backup route instead of the primary route by tunneling the data from the first node to an endpoint comprising the intermediate node.

32. An apparatus as claimed in claim 31, in which the reachable nodes include all nodes that are reachable via a routing mechanism and additional nodes that are reachable therefrom via a forwarding mechanism without traversing the adjacent component.

33. An apparatus as claimed in claim 32, in which the tunneling mechanism comprises one of directed forwarding or multiple tunneling, or loose or strict source routing, and further comprising sequences of instructions which when executed cause tunneling data traffic unless the intermediate node is a neighbor of the first node and the predetermined forwarding mechanism is not required.

34. An apparatus as claimed in claim 28, in which the reachable nodes include nodes reachable from a neighbor node of the repairing node without traversing the adjacent component.

35. An apparatus as claimed in claim 28 wherein the steps of deriving the first set of nodes and the second set of nodes are performed by iteratively adding nodes to the first set of nodes and the second set of nodes until the intermediate node is identified.

36. An apparatus as claimed in claim 28 where the adjacent component comprises one of an adjacent node and an adjacent link between the first node and the adjacent node, and further comprising sequences of instructions which when executed cause:

identifying as an unavailable node any neighbor node of the adjacent node for which a backup route is unavailable,

treating the adjacent node as the adjacent component, deriving from the topology a third set of nodes reachable from the repair node with the adjacent node removed, and

if no unavailable node is included in the third set, constructing a backup route treating the adjacent link as the adjacent component.