Method and apparatus for simplifying the computation of alternate network paths

• US 9,124,512 B2
• Filed: 08/27/2012
• Issued: 09/01/2015
• Est. Priority Date: 04/25/2006
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Inventors: Smith, Peter Ashwood, Zhang, Hong, Yin, Guoli
• Primary Examiner(s): Moore, Jr., Michael J
• Application Number:
  US13/595,011
• Publication Number:
  US 20120314582A1
• Time in Patent Office: 1,100 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04J 3/14 Monitoring arrangements for SDH/SONET rings H04J3/085
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/247 using M:N active or standby paths

Abstract

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.

Claims

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.