Fast computation of alterative packet routes

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

2. The method according to claim 1 , wherein respective link costs are assigned to links connecting the nodes in the network, and wherein finding the shortest paths and the backup paths comprises, in the single pass over the destination nodes:

identifying multiple paths between the source node and each of the destination nodes, each path comprising one or more of the links;

computing respective path costs for the multiple paths based on the respective link costs of the one or more of the links comprised in each path; and

choosing two of the paths between the source node and each of the destination nodes as the shortest path and the backup path responsively to the respective path costs.

3. The method according to claim 2 , wherein routing the packets comprises transmitting the packets over the shortest path as long as there is no failure among the links in the shortest path.

4. The method according to claim 3 , wherein designating another of the paths as the backup path comprises verifying that the backup path does not overlap the shortest path.

5. The method according to claim 1 , wherein finding the shortest paths and the backup paths comprises:

placing the nodes of the network in a queue;

in the single pass, removing each node from the queue in succession and searching outgoing edges of the node; and

terminating the greedy search algorithm when the queue is empty.

6. The method according to claim 1 , wherein routing the packets comprises conveying traffic from the source node to the given destination node over both the shortest path and the backup path so as to balance a load of the traffic between the shortest path and the backup path.

7. Apparatus comprising:

a routing engine, which is configured to:

simultaneously compute a shortest path and a backup path through a network between a source node, the network having a plurality of nodes, in a single pass of a greedy search algorithm over the plurality of nodes of the network;

compute the shortest path and the backup path by:

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 path 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;

verify that the backup paths is loop-free and will not lead to a micro-loop in response to a failure of a link in the network; and

a switch, which is coupled to route packets through the network using at least one path selected from among the shortest path and the backup path.

8. The apparatus according to claim 7 , wherein the switch is configured to transmit the packets over the shortest path as long as there is no failure among the links in the shortest path.

9. The apparatus according to claim 7 , wherein the routing engine is configured to verify that the backup path does not overlap the shortest path.

10. A computer software product, comprising a non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to simultaneously compute a shortest path and a 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 plurality of nodes of the network, wherein the shortest path and the backup path are computed by:

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