Technique for protecting against failure of a network element using Multi-Topology Repair Routing (MTRR)

• US 20080049622A1
• Filed: 08/28/2006
• Published: 02/28/2008
• Est. Priority Date: 08/28/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Shand, Ian Michael Charles, Bryant, Stewart, Ward, David D., Vasseur, Jean-Philippe, Previdi, Stefano B.
• Granted Patent: US 8,374,092 B2
• Time in Patent Office: Days
• US Class Current: 370/237
• CPC Class Codes: H04L 41/0668 by dynamic selection of recovery network elements, e.g. replacement by the most appropriate element after failure
• CPC Class Codes: H04L 41/5003 Managing SLA; Interaction between SLA and QoS
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/247 using M:N active or standby paths
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

A technique protects against failure of a network element using Multi-Topology Repair Routing (MTRR) in a computer network. According to the novel technique, a protecting node (e.g., a router) maintains Multi-Topology Routing (MTR) databases for a first topology and at least a second topology. The protecting node determines whether any acceptable repair paths are available in the first topology for a protected network element (e.g., node, link, etc.) of the first topology. If not, the protecting node may establish a repair path (e.g., for Fast ReRoute, FRR) in the second topology for the protected network element.

Claims

1. A node for use with protecting against failure of a network element using Multi-Topology Repair Routing (MTRR) in a computer network, the node comprising:

one or more network interfaces;

a processor coupled to the one or more network interfaces and adapted to execute software processes; and

a memory adapted to store at least one Multi-Topology Routing (MTR) database for a first topology and at least a second topology, the memory further adapted to store an MTRR process executable by the processor, the MTRR process configured to;

i) determine whether any acceptable repair paths are available in the first topology for a protected network element of the first topology, and ii) if not, establish a repair path in the second topology for the protected network element.

2. The node as in claim 1, wherein the protected network element is selected from a group comprising:

a node, a plurality of nodes, a link, a plurality of links, and a shared risk link group (SRLG).

3. The node as in claim 1, wherein the second topology is statically configured as a suitable topology for repair paths.

4. The node as in claim 1, wherein the MTRR process is further configured to:

dynamically discover the second topology as a suitable topology for repair paths and an alternative to the first topology.

5. The node as in claim 1, wherein the MTRR process is further configured to:

receive advertisements containing a status of at least one link or node of the network, the status corresponding to the usage of links and nodes in repair paths.

6. The node as in claim 5, wherein the advertisements are embodied as Interior Gateway Protocol (IGP) messages.

7. The node as in claim 5, wherein the status is selected from a group comprising:

whether a link is available for use in a repair path, for which topologies a link is available for use in a repair path, for which topologies a link is not available for use in a repair path, under which conditions a link is available for use in a repair path, under which conditions a link is not available for use in a repair path, a length of time a link is to be used in a repair path, whether a node is available for use in a repair path, for which topologies a node is available for use in a repair path, for which topologies a node is not available for use in a repair path, under which conditions a node is available for use in a repair path, under which conditions a node is not available for use in a repair path, and a length of time a node is to be used in a repair path.

8. The node as in claim 1, wherein the MTRR process is further configured to:

determine that no acceptable repair path is available in the first topology based on a policy to use the second topology.

9. The node as in claim 1, wherein the MTRR process is further configured to:

determine that no acceptable repair path is available in the first topology based on a preferred repair path in the second topology.

10. The node as in claim 1, wherein the MTRR process is further configured to:

determine the bandwidth availability of a possible repair path; and

not selecting the possible repair path in the event the bandwidth availability is below a configurable threshold.

11. The node as in claim 1, wherein the MTRR process is further configured to:

determine that acceptable repair paths are available in multiple topologies; and

selecting a repair path in a topology having a best repair path based on one or more metrics.

12. The node as in claim 11, wherein the metrics are selected from a group comprising:

cost, delay, link load, bandwidth availability, link load per topology, and link load per class-of-service.

13. The node as in claim 1, wherein the MTRR process is further configured to:

detect a failure of the protected network element; and

in response reroute traffic originally utilizing the protected network element onto the corresponding repair path.

14. The node as in claim 13, wherein the MTRR process is further configured to:

manipulate the rerouted traffic for use by intermediate nodes of the second topology.

15. The node as in claim 14, wherein the MTRR process is further configured to:

encapsulate the traffic with an encapsulation usable by intermediate nodes of the second topology.

16. The node as in claim 15, wherein the encapsulation is adapted to be removed by a remerge point of the repair path to reveal the first topology, the remerge point routing the traffic based on the first topology revealed by removing the encapsulation.

17. The node as in claim 14, wherein the MTRR process is further configured to:

apply an address of a remerge point that identifies the first topology to the remerge point and that is usable by intermediate nodes of the second topology.

18. The node as in claim 13, wherein the MTRR process is further configured to:

reroute traffic in accordance with Fast ReRoute (FRR).

19. A method for protecting against failure of a network element using Multi-Topology Repair Routing (MTRR) in a computer network, the method comprising:

maintaining at least one Multi-Topology Routing (MTR) database for a first topology and at least a second topology;

determining whether any acceptable repair paths are available in the first topology for a protected network element of the first topology; and

if not, establishing a repair path in the second topology for the protected network element.

20. An apparatus for protecting against failure of a network element using Multi-Topology Repair Routing (MTRR) in a computer network, the apparatus comprising:

at least one Multi-Topology Routing (MTR) database for a first topology and at least a second topology;

means for determining whether any acceptable repair paths are available in the first topology for a protected network element of the first topology; and

if not, means for establishing a repair path in the second topology for the protected network element.

21. A computer readable medium containing executable program instructions for protecting against failure of a network element using Multi-Topology Repair Routing (MTRR) in a computer network, the executable program instructions comprising program instructions adapted to:

maintain at least one Multi-Topology Routing (MTR) database for a first topology and at least a second topology;

determine whether any acceptable repair paths are available in the first topology for a protected network element of the first topology; and

if not, establish a repair path in the second topology for the protected network element.