Patent ID: 7876672

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