Patent ID: 8243604

Claim:
A method comprising: simultaneously computing a shortest path and backup path through a network between a source node and a destination node, the network having a plurality of nodes, in a single pass of a greedy search algorithm over the nodes of the network, wherein: computing the shortest path and the backup path comprises: computing respective path costs for each of a plurality of candidate paths between the source node and the destination node based on respective link costs of one or more links within each candidate path; selecting as the shortest paths the candidate path having a lowest computed path cost; selecting as the backup path the candidate path having a lowest computed path cost of the candidate paths that does not overlap with the shortest path, including comparing a potential backup path to the shortest path and determining that the potential backup path overlaps with the shortest path, and in response, discarding the potential backup path as a possible backup path; verifying that the backup paths are loop-free and will not lead to a micro-loop in response to a failure of a link in the network; and routing packets through the network using at least one path selected from among the shortest paths and the backup paths.