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

• US 20070038767A1
• Filed: 01/09/2003
• Published: 02/15/2007
• Est. Priority Date: 01/09/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bryant, Stewart, Filsfils, Clarence, Harper, John, Previdi, Stefano, Miles, Kevin, Charles Shand, Ian
• Granted Patent: US 7,707,307 B2
• Time in Patent Office: Days
• US Class Current: 709/230
• 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 from a repairing node in a data communications network having as components nodes and links defining a network topology, around an adjacent component, comprising the steps of:

deriving from the topology a first set of nodes reachable from the repairing node without traversing the adjacent component;

for a neighbor node of the adjacent component, deriving from the topology a second set of nodes from which the neighbor node is reachable without traversing the adjacent component; and

constructing a backup route to the neighbor node via an intermediate node in an intersection of the first and second sets of nodes.

2. A method as claimed in claim 1, further comprising the step of pre-computing the backup route for each adjacent component.

3. A method as claimed in claim 1, further comprising the step of constructing the backup route for each neighbor node of the adjacent component 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 the step of tunneling data traffic along the backup route from the repairing 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 forwarding 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 data traffic 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 further comprising the step of deriving the first or second set of nodes only until an 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 repairing 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 medium comprising one or more sequences of instructions 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, which instructions, when executed by one or more processors, cause the one or more processors to perform the steps of the method of any of claims 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 or 13.

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 from a repairing node in a data communications network having as components nodes and links defining a network topology, around an adjacent component, which instructions, when executed by the processor, cause the processor to perform the steps of the method of any of claims 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 or 13.

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

means for deriving from the topology a first set of nodes reachable from the repairing node without traversing the adjacent component;

means, for a neighbor node of the adjacent component, for deriving from the topology a second set of nodes from which the neighbor node is reachable without traversing the adjacent component; and

means for constructing a backup route to the neighbor node via an intermediate node in an intersection of the first and second sets of nodes.

16. An apparatus as claimed in claim 15, in which the backup route is pre-computed for each adjacent component.

17. An apparatus as claimed in claim 15, in which the backup route is constructed for each neighbor node of the adjacent component 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 tunneling data traffic along the backup route from the repairing 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 forwarding 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 data traffic 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 further comprising means for deriving the first or second set of nodes only until an 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 repairing 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.