Patent ID: 7738365

Claim:
For use with a survivable portion of a network, a computer-implemented method for determining backup ports for a first router of the survivable network, to reach a destination node in an event of a double link 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; b) for each router of at least a part of the routing path graph, assuming that a link terminated by a primary port of the first router is removed, 1) defining A) a first part of the routing path graph including the destination node, wherein the first part defines a graph, and B) a second part of the routing path graph separated from the first part wherein the second part defines a sub-graph and includes the first router, 2) determining two exits for the sub-graph to reach the graph, wherein each of the two exits includes an exit node and an exit link; and 3) determining, for the first router, using the determined two exits, a primary backup port and a secondary backup port; c) receiving with the first router, a packet destined for the destination node and which indicates that it has encountered a failure in the survivable portion of the network; and d) selecting, with the first router, one of (A) a primary port, (B) a primary backup port and (C) a secondary backup port for local rerouting, such that 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) obtaining 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 2) obtaining counter information in a packet indicative of a failure distance, wherein the act of selecting selects a port whose recovery distance is greater than the failure distance.