Method and apparatus for simplifying the computation of alternate network paths

• US 8,254,263 B2
• Filed: 04/25/2006
• Issued: 08/28/2012
• Est. Priority Date: 04/25/2006
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Rockstar Bidco LP (Rockstar Consortium Inc.)
• Inventors: Yin, Guoli, Zhang, Hong, Ashwood Smith, Peter
• Primary Examiner(s): Moore, Jr., Michael J
• Application Number:
  US11/410,747
• Publication Number:
  US 20070248016A1
• Time in Patent Office: 2,317 Days
• Field of Search: 370/238, 370/230, 370/352, 370/355, 370/392, 370/395.2, 726/1, 726/17
• US Class Current: 370/238
• 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 network paths to a plurality of destinations on a network, the method comprising the steps of:

ranking, by a node on the network, a plurality of neighbor nodes to prioritize the neighbor nodes for alternate path processing based on historical abilities of the neighbor nodes to provide alternate paths to the plurality of destinations on the network during previous iterations of the method of calculating alternate network paths to the plurality of destinations on the network;

selecting, by the node on the network, a highest ranked neighbor node and calculating, for the highest ranked neighbor node, how many destinations the highest ranked neighbor node is able to reach via loop-free alternate network paths through the network;

determining, by the node on the network, whether a stop calculation criterion has been met;

selecting, by the node on the network, a next highest ranked neighbor node and calculating, for the next highest ranked neighbor node, how many destinations the next highest ranked neighbor node is able to reach via loop-free alternate network paths through the network;

iterating, by the node on the network, the steps of determining and selecting next highest ranked neighbor nodes until the stop calculation criterion has been met;

terminating, by the node on the network, calculating loop-free alternate network paths once loop-free alternate network paths to a sufficient number of destinations has been calculated if the stop calculation criterion has been met before considering all neighbor nodes; and

wherein the stop calculation criterion is a percentage of a total number of destinations on the network fewer than 100% of possible destinations on the network.

2. The method of claim 1, wherein the step of calculating generates a number indicative of how many destinations the highest ranked neighbor node is able to serve as a loop-free alternate network path.

3. The method of claim 2, wherein the number is used to rank neighbor nodes for subsequent loop-free alternate network path calculations.

4. The method of claim 2, wherein the historical ability is associated with how many destinations the highest ranked neighbor node has been able to reach via loop free alternate network paths during earlier loop-free alternate network path calculations, each loop-free alternate network path calculation being implemented after a change in network topology causes the plurality of neighbor nodes on the network to calculate a new set of shortest paths through the network.

5. The method of claim 1, wherein the stop calculation criterion is based on a number of times the step of iterating has been performed.

6. The method of claim 1, wherein the stop calculation criterion is based on an amount of computation time expended in connection with the loop-free alternate network path calculations.

7. The method of claim 1, wherein the stop calculation criterion is based on whether a number of new loop-free alternate network paths for destinations not previously found to be reachable via the loop-free alternate network paths through other previously considered higher ranked neighbor nodes being found for each new neighbor node being considered has passed below a threshold.

8. The method of claim 1, further comprising the step of re-ranking, by the node on the network, the neighbor nodes upon determining that a stop calculation criterion has been met.

9. The method of claim 1, wherein the step of determining whether a stop calculation criterion has been met comprises determining whether at least one of a plurality of stop calculation criteria has been met, and wherein the step of iterating comprises iterating until at least one of the stop calculation criteria has been met.

10. The method of claim 1, wherein at least some of the loop-free alternate network paths include U-turn alternate network paths.

11. A method of computing alternate network paths on an Internet Protocol (IP) network by a node on the network, the method comprising the steps of:

ranking, by a node on the network, a plurality of neighbor nodes to prioritize the neighbor nodes for alternate path processing based on historical abilities of the neighbor nodes to provide alternate paths to the plurality of destinations on the network during previous iterations of the method of calculating alternate network paths to the plurality of destinations on the network;

selecting, by the node on the network, a highest ranked neighbor node and calculating, for the highest ranked neighbor node, how many destinations the highest ranked neighbor node is able to reach via loop-free alternate network paths through the network;

determining, by the node on the network, whether a stop calculation criterion has been met;

selecting, by the node on the network, a next highest ranked neighbor node and calculating, for the next highest ranked neighbor node, how many destinations the next highest ranked neighbor node is able to reach via loop-free alternate network paths through the network;

iterating, by the node on the network, the steps of determining and selecting next highest ranked neighbor nodes until the stop calculation criterion has been met;

terminating, by the node on the network, calculating loop-free alternate network paths once loop-free alternate network paths to a sufficient number of destinations has been calculated if the stop calculation criterion has been met before considering all neighbor nodes; and

wherein the stop calculation criterion is a percentage of a total number of destinations on the network fewer than 100% of possible destinations on the network.

12. The method of claim 11, wherein the step of ranking comprises causing historical contributions associated with the historical abilities to decay over time.

13. A network element configured to compute alternate network paths on an IP network, the network element containing a computer readable memory containing control logic which, when loaded into a processor, configures the processor to implement a method comprising the steps of:

ranking a plurality of neighbor nodes to prioritize the neighbor nodes for alternate path processing based on historical abilities of the neighbor nodes to provide alternate paths to the plurality of destinations on the network during previous iterations of the method of calculating alternate network paths to the plurality of destinations on the network;

selecting a highest ranked neighbor node and calculating, for the highest ranked neighbor node, how many destinations the highest ranked neighbor node is able to reach via loop-free alternate network paths through the network;

determining whether a stop calculation criterion has been met;

selecting a next highest ranked neighbor node and calculating, for the next highest ranked neighbor node, how many destinations the next highest ranked neighbor node is able to reach via loop-free alternate network paths through the network;

iterating the steps of determining and selecting next highest ranked neighbor nodes until the stop calculation criterion has been met;

terminating calculating loop-free alternate network paths once loop-free alternate network paths to a sufficient number of destinations has been calculated if the stop calculation criterion has been met before considering all neighbor nodes; and

wherein the stop calculation criterion is a percentage of a total number of destinations on the network fewer than 100% of possible destinations on the network.

14. The network element of claim 13, further comprising:

a data plane configured to handle IP packets on the IP network, and wherein the processor is configured to cause the loop-free alternate network paths to be programmed into the data plane for use upon occurrence of a failure on the IP network.

15. The network element of claim 13, wherein the control logic is configured to stop calculating loop-free alternate network paths by applying a plurality of stop calculation criteria.

16. The network element of claim 15, wherein any one of the plurality of stop calculation criteria will cause the control logic to stop computing loop-free alternate network paths, and wherein the criteria comprise:

whether a computation time has exceeded a first threshold;

whether a number of neighbor nodes considered has exceeded a second threshold; and

whether loop-free alternate network paths for fewer than all destinations but more than a third threshold number of destinations have been found.

17. The network element of claim 13, wherein the control logic is configured to re-rank the neighbor nodes according to a new number of destinations the neighbor nodes are able to reach as loop-free alternate network paths as determined in a most recent process of computing loop-free alternate network paths.

18. The network element of claim 13, wherein at least one of the loop-free alternate network paths is a U-turn alternate network path.