Rerouting for double-link failure recovery in an internet protocol network

• US 7,801,031 B2
• Filed: 11/02/2007
• Issued: 09/21/2010
• Est. Priority Date: 11/02/2006
• Status: Active Grant

• Current Assignee: Polytechnic Institute Of New York University (New York University)
• Original Assignee: Polytechnic Institute Of New York University (New York University)
• Inventors: Chao, Hung-Hsiang Jonathan, Xi, Kang
• Primary Examiner(s): Sheikh, Ayaz R
• Assistant Examiner(s): Hsiung, Hai-Chang
• Application Number:
  US11/934,213
• Publication Number:
  US 20080130489A1
• Time in Patent Office: 1,054 Days
• Field of Search: 370/401, 370/228
• US Class Current: 370/228
• 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/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/48 Routing tree calculation

Abstract

A router in a survivable portion of a network may forward packets to a destination node even in the event of a double-link failure. For a given destination node, the router has previously been configured with a primary port, a primary backup port, and a secondary backup port. The router receives a packet addressed to the destination node within the survivable portion of the network, wherein the packet includes information indicating that the packet has encountered a failure. The router then selects one of (A) the primary port, (B) the primary backup port and (C) the secondary backup port on which to forward the received packet, such that a backup path with no dead loops is defined. The router may obtain a recovery distance of at least one of (A) the primary backup port based on a backup path to which it leads, and (B) the secondary backup port based on a backup path to which it leads, and may further obtain counter information in a packet indicative of a failure distance. In this case, the router may select a port whose recovery distance is greater than the failure distance. The router may identify a pattern of the failure. In this case, the router may make its selection using a forwarding policy associated with the identified pattern.

Claims

1. For use by a router in a survivable network portion, a computer-implemented method comprising:

a) receiving a packet addressed to a destination node within the survivable network portion, wherein the packet includes an information indicating that the packet has encountered a failure; and

b) selecting one of (A) a primary port, (B) a primary backup port and (C) a secondary backup port on which to forward the received packet, such that, in the event of a double link failure, a backup path with no dead loops is defined,

wherein the act of selecting one of (A) a primary port, (B) a primary backup port and (C) a secondary backup port for local rerouting includes

1) identifying a pattern of the failure; and

2) selecting, using a forwarding policy associated with the identified pattern, one of (A) a primary port, (B) a primary backup port and (C) a secondary backup port to use for forwarding.

2. The computer-implemented method of claim 1 wherein the pattern of the failure indicates that a second link failure does not affect a backup path used by a sub-graph 3 defined by a first link failure.

3. The computer-implemented method of claim 1 wherein the pattern of the failure indicates that a second link failure is on an exit link of a backup path used by a sub-graph defined by the first link failure.

4. The computer-implemented method of claim 3 wherein the pattern of the failure indicates that first and second link failures create two sub-graphs separated from a graph which includes the destination node, and wherein the two sub-graphs are separated from each other.

5. The computer-implemented method of claim 1 wherein a first link failure defines a graph including the destination node and a disconnected sub-graph, and wherein the pattern of the failure indicates that a second link failure creates a further sub-graph within the defined sub-graph.

6. For use by a router in a survivable network portion, apparatus comprising:

a) means for receiving a packet addressed to a destination node within the survivable network portion, wherein the packet includes an information indicating that the packet has encountered a failure; and

b) means for selecting one of (A) a primary port, (B) a primary backup port and (C) a secondary backup port on which to forward the received packet, such that in the event of a double link failure, a backup path with no dead loops is defined,

wherein the means for selecting one of (A) a primary port, (B) a primary backup port and (C) a secondary backup port for local rerouting include

1) means for identifying a pattern of the failure; and

2) means for selecting, using a forwarding policy associated with the identified pattern, one of (A) a primary port, (B) a primary backup port and (C) a secondary backup port to use for forwarding.

7. The apparatus of claim 6 wherein the pattern of the failure indicates that a second link failure does not affect a backup path used by a sub-graph defined by a first link failure.

8. The apparatus of claim 6 wherein the pattern of the failure indicates that a second link failure is on an exit link of a backup path used by a sub-graph defined by the first link failure.

9. The apparatus of claim 6 wherein the pattern of the failure indicates that first and second link failures create two sub-graphs separated from a graph which includes the destination node, and wherein the two sub-graphs are separated from each other.

10. The apparatus of claim 6 wherein a first link failure defines a graph including the destination node and a disconnected sub-graph, and wherein the pattern of the failure indicates that a second link failure creates a further sub-graph within the defined sub-graph.