CONSTRUCTING REPAIR PATHS AROUND MULTIPLE NON-AVAILABLE LINKS IN A DATA COMMUNICATIONS NETWORK

• US 20090207728A1
• Filed: 02/15/2008
• Published: 08/20/2009
• Est. Priority Date: 02/15/2008
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Charles Shand, Ian Michael, Bryant, Stewart Frederick
• Granted Patent: US 7,852,751 B2
• Time in Patent Office: Days
• US Class Current: 370/225
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

A data processing apparatus is configured for initiating a not-via approach for creating repair path information for a first link between the first network node and a second network node; creating a list of other network nodes that the not-via repair path traverses; creating and storing entries in the FIB identifying repair addresses for the network nodes and that cause (a) packets directed to all addresses normally reachable through the first link to be encapsulated to the second node not via the first node, (b) packets directed to a not-via address that is normally reachable through the first link to be encapsulated to the second node not via the first node, and (c) dropping packets directed to a not-via address that is normally reachable through the first link when the not-via address is in the list; repeating the preceding steps for all other links of the first network node.

Claims

1. An apparatus comprising:

one or more processors;

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

memory coupled to the processors and comprising a forwarding information base (FIB) for a routing protocol;

logic operable in a network as a first network node and coupled to the one or more processors and comprising one or more stored sequences of instructions which, when executed by one or more processors, cause the one or more processors to perform;

initiating a not-via approach for creating and storing repair path information for a first link between the first network node and a second network node;

creating and storing a list of other network nodes that the not-via repair path traverses;

creating and storing entries in the FIB identifying repair addresses for the network nodes and that cause (a) packets directed to all addresses normally reachable through the first link to be encapsulated to the second node not via the first node, (b) packets directed to a not-via address that is normally reachable through the first link to be encapsulated to the second node not via the first node, and (c) dropping packets directed to a not-via address that is normally reachable through the first link when the not-via address is in the list;

repeating the preceding steps for all other links of the first network node.

2. The apparatus of claim 1, wherein the logic further comprises instructions which when executed cause the one or more processors to perform:

determining from entries in the FIB one or more pairs of mutually incompatible link failures;

advertising the one or more pairs as secondary shared risk link groups, using the routing protocol.

3. The apparatus of claim 1 wherein the logic further comprises instructions which when executed cause sending network traffic destined for a repair address via a corresponding repair path.

4. The apparatus of claim 1 wherein the logic further comprises instructions which when executed cause:

determining that a simultaneous failure of the first link and a second link has occurred;

determining that a first repair path for the first link traverses the second link, and that a second repair path for the second link traverses the first link;

determining that a packet drop count is greater than a specified threshold value, that a hold-down step is in use with respect to re-convergence, and that a loop-free convergence mechanism is in use;

in response to the ultimate determining step, sending an “

Abandon All Hope”

notification to logic implementing the routing protocol for forcing normal re-convergence to begin.

5. The apparatus of claim 2, wherein the logic further comprises instructions which when executed cause the one or more processors to perform determining, for each neighbor node, a list of node pairs that are traversed by each repair path;

performing a shortest path first (SPF) calculation rooted at a first node of each pair with a link to the second node removed;

determining whether a resulting path includes the first link.

6. The apparatus of claim 1 in which the first network node comprises a neighbor node, acting as a repairing node, and wherein the logic further comprises instructions which when executed cause the repairing node to identify, for a destination address of the second network node, a repair address as an encapsulation repair endpoint for a repair to the destination address in the event of non-availability of the second network node.

7. The apparatus of claim 1 wherein the network includes multi-homed prefixes and wherein the logic further comprises instructions which when executed cause determining if an attachment point to a multi-homed prefix is reachable without a repair path and encapsulating a packet to the attachment point if so;

and if an attachment point to the multi-homed prefix is only reachable via a repair path, encapsulating traffic to the corresponding repair address.

8. The apparatus of claim 1 wherein the routing protocol is any of a link state routing protocol, MPLS routing protocol or distance vector routing protocol.

9. The apparatus of claim 1, wherein the first link is in a shared risk link group.

10. The apparatus of claim 1 wherein the logic further comprises instructions which when executed cause decapsulating the packets at a preceding node to one of the repair addresses.

11. The apparatus of claim 1 wherein the packets comprise multi-cast traffic.

16. The computer readable storage medium of claim 11, further comprising instructions which when executed cause the one or more processors to perform determining, for each neighbor node, a list of node pairs that are traversed by each repair path;

performing a shortest path first (SPF) calculation rooted at a first node of each pair with a link to the second node removed;

determining whether a resulting path includes the first link.

21. The apparatus of claim 1, comprising any of a packet data router, or a switch for a packet-switched network.

22. The apparatus of claim 1, wherein the logic further comprises instructions which when executed cause:

determining one or more additional repair paths by performing an SPF calculation rooted at each of the other nodes in the list;

creating and storing entries in the FIB that cause dropping packets directed to not-via addresses that are in the one or more additional repair paths if the first network node is in the one or more additional repair paths.

23. The apparatus of claim 1, wherein the logic further comprises instructions which when executed cause recursively repeating the steps of claim 22 for each of the one or more additional repair paths.

24. The computer readable storage medium of claim 11, further comprising instructions which when executed cause the one or more processors to perform:

determining one or more additional repair paths by performing an SPF calculation rooted at each of the other nodes in the list;

creating and storing entries in the FIB that cause dropping packets directed to not-via addresses that are in the one or more additional repair paths if the first network node is in the one or more additional repair paths.

25. The computer readable storage medium of claim 11, further comprising instructions which when executed cause the one or more processors to perform recursively repeating the steps of claim 24 for each of the one or more additional repair paths.

12. A computer readable storage medium comprising one or more stored sequences of instructions which, when executed by one or more processors of a first network node in a network, cause the one or more processors to perform:

initiating a not-via approach for creating and storing repair path information for a first link between the first network node and a second network node;

creating and storing a list of other network nodes that the not-via repair path traverses;

creating and storing entries in a forwarding information base (FIB) for a routing protocol that identify repair addresses for the network nodes and that cause (a) packets directed to all addresses normally reachable through the first link to be encapsulated to the second node not via the first node, (b) packets directed to a not-via address that is normally reachable through the first link to be encapsulated to the second node not via the first node, and (c) dropping packets directed to a not-via address that is normally reachable through the first link when the not-via address is in the list;

repeating the preceding steps for all other links of the first network node.

13. The computer-readable storage medium of claim 12, further comprising instructions which when executed cause the one or more processors to perform:

determining from entries in the FIB one or more pairs of mutually incompatible link failures;

advertising the one or more pairs as secondary shared risk link groups, using the routing protocol.

14. The computer-readable storage medium of claim 12 further comprising instructions which when executed cause sending network traffic destined for a repair address via a corresponding repair path.

15. The computer-readable storage medium of claim 12 further comprising instructions which when executed cause:

determining that a simultaneous failure of the first link and a second link has occurred;

determining that a first repair path for the first link traverses the second link, and that a second repair path for the second link traverses the first link;

determining that a packet drop count is greater than a specified threshold value, that a hold-down step is in use with respect to re-convergence, and that a loop-free convergence mechanism is in use;

in response to the ultimate determining step, sending an “

Abandon All Hope”

notification to logic implementing the routing protocol for forcing normal re-convergence to begin.

17. The computer-readable storage medium of claim 12 in which the first network node comprises a neighbor node, acting as a repairing node, and further comprising instructions which when executed cause the repairing node to identify, for a destination address of the second network node, a repair address as an encapsulation repair endpoint for a repair to the destination address in the event of non-availability of the second network node.

18. The computer-readable storage medium of claim 12 wherein the network includes multi-homed prefixes and further comprising instructions which when executed cause determining if an attachment point to a multi-homed prefix is reachable without a repair path and encapsulating a packet to the attachment point if so;

and if an attachment point to the multi-homed prefix is only reachable via a repair path, encapsulating traffic to the corresponding repair address.

19. The computer-readable storage medium of claim 12 wherein the routing protocol is any of a link state routing protocol, MPLS routing protocol or distance vector routing protocol.

20. The computer-readable storage medium of claim 12, wherein the first link is in a shared risk link group.

26. A computer-implemented method, comprising:

initiating a not-via approach for creating and storing repair path information for a first link between a first network node and a second network node;

creating and storing a list of other network nodes that the not-via repair path traverses;

creating and storing entries in the FIB identifying repair addresses for the network nodes and that cause (a) packets directed to all addresses normally reachable through the first link to be encapsulated to the second node not via the first node, (b) packets directed to a not-via address that is normally reachable through the first link to be encapsulated to the second node not via the first node, and (c) dropping packets directed to a not-via address that is normally reachable through the first link when the not-via address is in the list;

repeating the preceding steps for all other links of the first network node.

27. The method of claim 26, further comprising determining from entries in the FIB one or more pairs of mutually incompatible link failures;

advertising the one or more pairs as secondary shared risk link groups, using the routing protocol.

28. The method of claim 26, further comprising:

determining that a simultaneous failure of the first link and a second link has occurred;

determining that a first repair path for the first link traverses the second link, and that a second repair path for the second link traverses the first link;

determining that a packet drop count is greater than a specified threshold value, that a hold-down step is in use with respect to re-convergence, and that a loop-free convergence mechanism is in use;

in response to the ultimate determining step, sending an “

Abandon All Hope”

notification to logic implementing the routing protocol for forcing normal re-convergence to begin.

29. The method of claim 27, further comprising determining, for each neighbor node, a list of node pairs that are traversed by each repair path;

performing a shortest path first (SPF) calculation rooted at a first node of each pair with a link to the second node removed;

determining whether a resulting path includes the first link.

30. An apparatus, comprising:

means for initiating a not-via approach for creating and storing repair path information for a first link between the first network node and a second network node;

means for creating and storing a list of other network nodes that the not-via repair path traverses;

means for creating and storing entries in the FIB identifying repair addresses for the network nodes and that cause (a) packets directed to all addresses normally reachable through the first link to be encapsulated to the second node not via the first node, (b) packets directed to a not-via address that is normally reachable through the first link to be encapsulated to the second node not via the first node, and (c) dropping packets directed to a not-via address that is normally reachable through the first link when the not-via address is in the list;

means for repeating operation of the preceding means for all other links of the first network node.

31. The apparatus of claim 30, further comprising means for determining from entries in the FIB one or more pairs of mutually incompatible link failures;

means for advertising the one or more pairs as secondary shared risk link groups, using the routing protocol.

32. The apparatus of claim 30, further comprising:

means for determining that a simultaneous failure of the first link and a second link has occurred;

means for determining that a first repair path for the first link traverses the second link, and that a second repair path for the second link traverses the first link;

means for determining that a packet drop count is greater than a specified threshold value, that a hold-down step is in use with respect to re-convergence, and that a loop-free convergence mechanism is in use;

means for sending, in response to the ultimate determining means, an “

Abandon All Hope”

notification to logic implementing the routing protocol for forcing normal re-convergence to begin.

33. The apparatus of claim 31, further comprising means for determining, for each neighbor node, a list of node pairs that are traversed by each repair path;

means for performing a shortest path first (SPF) calculation rooted at a first node of each pair with a link to the second node removed;

means for determining whether a resulting path includes the first link.