Determining rerouting information for single-link failure recovery in an Internet protocol network

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 portion of the network, to reach a destination node in the event of a single link failure, the method comprising:

a) accepting network topology information defining the survivable portion of the network;

b) accepting a routing path graph consisting of the elements of the survivable portion of the network, and 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

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

I) assuming that a link terminated by a primary port of 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 a sub-graph, and

2) determining the backup port for the first router by examining the sub-graph with respect to the first part of the routing path graph in the context of the network topology information accepted,

wherein the routing path graph including the destination node is a routing path tree rooted by the destination node, and wherein the sub-graph is a sub-tree.

2. The method of claim 1 wherein the act of determining the backup port includes

A) determining an exit link from the sub-graph to the first part of the routing path graph,

B) determining a backup path from the current router of at least a part of the routing path graph, to the exit link, and

C) if the first router is on the determined backup path,

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.

3. The computer-implemented method of claim 2 wherein the act of determining a backup path from the current router to the exit link uses the accepted routing path graph.

4. The method of claim 1 wherein the act of determining the backup port includes

A) determining an exit link from the sub-graph to the first part of the routing path graph,

B) determining a backup path from the current router to the exit link, and

C) for each router on the determined backup path,

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

2) assigning the determined port as the backup port of the router.

5. The computer-implemented method of claim 4 wherein the act of determining a backup path from the current router to the exit link uses the accepted routing path graph.

6. The computer-implemented method of claim 1 wherein the act of determining, for each router of at least a part of the routing path graph, the backup port for the first router by examining the sub-graph with respect to the first part of the routing path graph includes finding one network link, from the second part of the routing path graph to the first part of the routing path graph, which is not a part of the routing path graph.

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

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

9. 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.

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

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

12. 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.

13. 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.

14. 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.

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

a) means for accepting (1) network topology information defining the survivable portion of the network, and

(2) a routing path graph consisting of elements of the survivable portion of the network and 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,

I) for assuming that a link terminated by a primary port of 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 a sub-graph, and

2) for determining the backup port for the first router by examining the sub-graph with respect to the first part of the routing path graph in the context of the network topology information accepted,

wherein the routing path graph including the destination node is a routing path tree rooted by the destination node, and wherein the sub-graph is a sub-tree.

16. The apparatus of claim 15 wherein the means for determining the backup port include

A) means for determining an exit link from the sub-graph to the first part of the routing path graph,

B) means determining a backup path from the current router of at least a part of the routing path graph, to the exit link, and

C) means, if the first router is on the determined backup path,

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

ii) for assigning the determined port as the backup port of the first router.

17. The apparatus of claim 15 wherein the means for determining the backup port include

A) means for determining an exit link from the sub-graph to the first part of the routing path graph,

B) means for determining a backup path from the current router to the exit link, and

C) means, for each router on the determined backup path,

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

2) for assigning the determined port as the backup port of the router.

18. The apparatus of claim 15 wherein the means for determining, for each router of at least a part of the routing path graph, the backup port for the first router by examining the sub-graph with respect to the first part of the routing path graph include finding one network link, from the second part of the routing path graph to the first part of the routing path graph, which is not a part of the routing path graph.