Determining rerouting information for single-node failure recovery in an internet protocol network

• US 20080232347A1
• Filed: 04/10/2007
• Published: 09/25/2008
• Est. Priority Date: 04/10/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: Xi, Kang, Chao, Hung-Hsiang Jonathan
• Granted Patent: US 7,876,672 B2
• Time in Patent Office: Days
• US Class Current: 370/351
• 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/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

For a survivable portion of a network, a backup port for a first router of the survivable network, to reach a destination node in the event of a single node failure, may be determined by (a) accepting a routing path graph having the destination node, wherein the routing path graph includes one or more links terminated by one or more primary ports of the first router; and (b) for each router of at least a part of the routing path graph, (1) assuming that the current router is removed, defining (A) a first part of the routing path graph including the destination node, and (B) a second part of the routing path graph separated from the first part wherein the second part defines one or more sub-graphs, and (2) determining the backup port for the first router by examining at least one of the one or more sub-graphs to find a link to the first part of the routing path graph.

Claims

1. For use with a survivable portion of a network, a computer-implemented method for determining a backup port for a first router of the survivable network, to reach a destination node in the event of a single node failure, the method comprising:

a) accepting a routing path graph having the destination node, wherein the routing path graph includes one or more links terminated by one or more primary ports of the first router; and

b) for each router of at least a part of the routing path graph,

1) assuming that the current router is removed, defining

A) a first part of the routing path graph including the destination node, and

B) a second part of the routing path graph separated from the first part wherein the second part defines one or more sub-graphs, and

2) determining the backup port for the first router by examining at least one of the one or more sub-graphs to find a link to the first part of the routing path graph.

2. The method of claim 1 wherein the act of determining the backup port includes, using a breadth-first search of the second part but excluding the current router,

A) determining an exit node with a link to the first part of the routing path graph,

B) determining which of the one or more sub-graphs includes the exit node,

C) determining a backup path from a root of the determined sub-graph to the exit node,

D) if the first router is on the determined backup path, then

i) determining a port of the first router on the backup path, and

ii) assigning the determined port as the backup port of the first router,

E) redefining the first part of the routing path graph to include the determined sub-graph and redefining the second part of the routing path graph to exclude the determined sub-graph, and

F) while there are any sub-graphs remaining in the second part, continuing acts (A) through (E), otherwise terminating the breadth-first search.

3. The method of claim 1 wherein the act of determining the backup port includes, using a breadth-first search of the second part but excluding the current router,

A) determining an exit node with a link to the first part of the routing path graph,

B) determining which of the one or more sub-graphs includes the exit node,

C) determining a backup path from a root of the determined sub-graph to the exit node,

D) for each router on the determined backup path,

i) determining a port of the router on the backup path, and

ii) assigning the determined port as the backup port of the router,

E) redefining the first part of the routing path graph to include the determined sub-graph and redefining the second part of the routing path graph to exclude the determined sub-graph, and

F) while there are any sub-graphs remaining in the second part, continuing acts (A) through (E), otherwise terminating the breadth-first search.

4. The computer-implemented method of claim 1 further comprising determining the accepted routing path graph using a shortest path first algorithm.

5. The computer-implemented method of claim 1 further comprising determining the accepted routing path graph using Dijkstra'"'"'s algorithm.

6. The computer-implemented method of claim 2 wherein the act of determining a backup path from the root of the determined sub-graph to the exit node uses the accepted routing path graph.

7. The computer-implemented method of claim 3 wherein the act of determining a backup path from the root of the determined sub-graph to the exit node uses the accepted routing path graph.

8. The computer-implemented method of claim 1 wherein the act of assigning the determined port as the backup port of the first router includes adding the backup port as a routing table entry.

9. The computer-implemented method of claim 8 wherein the routing table includes an Internet Protocol address prefix, the primary port and the backup port.

10. The computer-implemented method of claim 8 wherein the routing table includes an Internet Protocol address prefix, a next hop, the primary port, a backup next hop, and the backup port.

11. The computer-implemented method of claim 1 wherein the routing path graph including the destination node is a routing path tree rooted by the destination node, and wherein each of the one or more sub-graphs is a sub-tree.

12. The computer-implemented method of claim 1 wherein the routing path graph including the destination node is a multi-path routing graph in which at least one of the routers includes more than one primary port for reaching the destination node.

13. The computer-implemented method of claim 1 wherein the at least a part of the routing path graph consists of a primary routing path graph between the first router and the destination node.

14. The computer-implemented method of claim 1 wherein the at least a part of the routing path graph excludes at least some of the routing path graph.

15. The computer-implemented method of claim 1 wherein the at least a part of the routing path graph includes the entire routing path graph except for the destination node.

16. For use with a survivable portion of a network, apparatus adapted to determine a backup port for a first router of the survivable network, to reach a destination node in the event of a single node failure, the apparatus comprising:

a) means for accepting a routing path graph having the destination node, wherein the routing path graph includes one or more links terminated by one or more primary ports of the first router; and

b) means, for each router of at least a part of the routing path graph,

1) for assuming that the current router is removed, defining

A) a first part of the routing path graph including the destination node, and

B) a second part of the routing path graph separated from the first part wherein the second part defines one or more sub-graphs, and

2) for determining the backup port for the first router by examining at least one of the one or more sub-graphs to find a link to the first part of the routing path graph.

17. The apparatus of claim 16 wherein the means for determining the backup port include, means, using a breadth-first search of the second part but excluding the current router,

A) for determining an exit node with a link to the first part of the routing path graph,

B) for determining which of the one or more sub-graphs includes the exit node,

C) for determining a backup path from a root of the determined sub-graph to the exit node,

D) for, if the first router is on the determined backup path, then

i) determining a port of the first router on the backup path, and

ii) assigning the determined port as the backup port of the first router,

E) for redefining the first part of the routing path graph to include the determined sub-graph and redefining the second part of the routing path graph to exclude the determined sub-graph, and

F) for while there are any sub-graphs remaining in the second part, continuing acts (A) through (E), otherwise terminating the breadth-first search.

18. The apparatus of claim 16 wherein the means for determining the backup port include, means, using a breadth-first search of the second part but excluding the current router,

A) for determining an exit node with a link to the first part of the routing path graph,

B) for determining which of the one or more sub-graphs includes the exit node,

C) for determining a backup path from a root of the determined sub-graph to the exit node,

D) for, for each router on the determined backup path,

i) determining a port of the router on the backup path, and

ii) assigning the determined port as the backup port of the router,

E) for redefining the first part of the routing path graph to include the determined sub-graph and redefining the second part of the routing path graph to exclude the determined sub-graph, and

F) for, while there are any sub-graphs remaining in the second part, continuing acts (A) through (E), otherwise terminating the breadth-first search.