Patent ID: 7869348

Claim:
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.