Method and apparatus for simplifying the computation of alternate network paths
View Patent ↗An alternate path calculation process may be terminated after considering some of a source node's neighbors and without considering each of its neighbors, to reduce the amount of processing required to perform the alternate path calculations. The neighbors may be ranked according to the number of alternate paths that the neighbor has historically been able to provide on the network. The influence of historical success or failure may degrade over time so that the rankings may be adjusted to reflect changes in network topography. A given source node, when computing alternate paths through the network, may preferentially select neighbors to perform alternate path calculations on historically higher scoring nodes before performing calculations on historically lower scoring nodes. Several different criteria may be used to stop the alternate path calculation process before considering all neighbors. The neighbors may be loop free neighbors or U-turn neighbors.
1. A method of calculating a set of alternate paths on a network to a plurality of destinations at a node of the network, the method comprising:
calculating alternate paths through only a subset of neighbor nodes of the node, the subset being selected based on respective numbers of destinations that can be reached via the neighbor nodes;
determining the respective numbers of destinations that can be reached via the neighbor nodes using the alternate paths; and
ranking the neighbor nodes based on the respective numbers of destinations that can be reached via the neighbor nodes using the alternate paths.
2. The method of claim 1 , wherein the subset of neighbor nodes is selected based on the respective numbers of destinations that can be reached via the neighbor nodes determined during previous calculations of alternate paths through the neighbor nodes.
3. The method of claim 1 , comprising storing rankings of the neighbor nodes for use in the subsequent calculations of alternate paths.
4. The method of claim 1 , wherein calculating the alternate paths through only the subset of the neighbor nodes of the node, the subset being selected based on the respective numbers of destinations that can be reached via the neighbor nodes, comprises calculating alternate paths for only a subset of nodes having the largest numbers of destinations that can be reached via the neighbor nodes.
5. The method of claim 1 , wherein calculating the alternate paths through only the subset of the neighbor nodes of the node, the subset being selected based on the respective numbers of the destinations that can be reached via the neighbor nodes, comprises:
calculating alternate paths through only a subset of neighbor nodes ranked highest based on the respective numbers of the destinations that can be reached via the neighbor nodes.
6. The method of claim 1 , wherein calculating the alternate paths through only the subset of the neighbor nodes comprises:
calculating alternate paths through the subset of the neighbor nodes until at least one stop criterion is met; and
stopping calculation of alternate paths when the at least one stop criterion is met.
7. The method of claim 6 , wherein calculating the alternate paths through the subset of the neighbor nodes until the at least one stop criterion is met comprises calculating alternate paths for one selected neighbor node after another in decreasing order of the respective numbers of the destinations that can be reached via the neighbor nodes until the at least one stop criterion is met.
8. The method of claim 7 , wherein the neighbor nodes have been ranked according to the respective numbers of the destinations that can be reached via the neighbor nodes and calculating the alternate paths for the one selected neighbor node after another in decreasing order of the respective numbers of the destinations that can be reached via the neighbor nodes comprises calculating the alternate paths for the one selected neighbor node after another in order of decreasing rank.
9. The method of claim 8 , comprising re-ranking the neighbor nodes according to the respective numbers of the destinations that can be reached via the neighbor nodes according to the calculated alternate paths for use in subsequent calculations of alternate paths.
10. The method of claim 6 , wherein the at least one stop criterion comprises at least one of:
whether the calculated alternate paths provide alternate paths to all destinations in the network;
whether computation time spent on calculating the alternate paths exceeds a threshold;
whether a number of neighbor nodes for which the alternate paths have been calculated exceeds a threshold; and
whether a number of additional alternate paths obtained for a last considered neighbor node is below a threshold.
11. The method of claim 6 , wherein the at least one stop criterion comprises more than one of:
whether the calculated alternate paths provide alternate paths to all destinations in the network;
whether computation time spent on calculating the alternate paths exceeds a threshold;
whether a number of neighbor nodes for which the alternate paths have been calculated exceeds a threshold; and
whether a number of additional alternate paths obtained for a last considered neighbor node is below a threshold.
12. The method of claim 11 , wherein the more than one stop criteria are applied sequentially until the at least one stop criterion is met.
13. The method of claim 12 , wherein the neighbor nodes have been ranked according to the respective numbers of the destinations that can be reached via the neighbor nodes and calculating the alternate paths for the one selected neighbor node after another in decreasing order of the respective numbers of the destinations that can be reached via the neighbor nodes comprises calculating the alternate paths for the one selected neighbor node after another in order of decreasing rank, the method further comprising, after the at least one stop criterion is met, re-ranking the neighbor nodes according to the respective numbers of the destinations that can be reached via the neighbor nodes according to the calculated alternate paths for use in subsequent calculations of alternate paths.
14. The method of claim 1 , wherein the network is a packet switched network and the alternate paths are for routing packets through the network.
15. The method of claim 1 , wherein the network is a link state protocol controlled network.
16. The method of claim 1 , wherein the method is initiated responsive to a link failure on the network.
17. The method of claim 16 , wherein the link failure is on a link between the node and a neighbor node.
18. The method of claim 1 , wherein calculating the alternate paths comprises calculating loop-free alternate paths.
19. A method of calculating a set of alternate paths on a network to a plurality of destinations at a node of the network, the method comprising:
calculating alternate paths through only a subset of neighbor nodes of the node, the subset being selected based on respective numbers of destinations that can be reached via the neighbor nodes;
ranking the neighbor nodes of the node based on the respective numbers of destinations that can be reached via the neighbor nodes; and
calculating alternate paths through only a subset of neighbor nodes ranked highest based on the respective numbers of the destinations that can be reached via the neighbor nodes.