Method and apparatus for simplifying the computation of alternate network paths

• US 20070248016A1
• Filed: 04/25/2006
• Published: 10/25/2007
• Est. Priority Date: 04/25/2006
• Status: Active Grant

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Zhang, Hong, Yin, Guoli, Ashwood Smith, Peter
• Granted Patent: US 8,254,263 B2
• Time in Patent Office: Days
• 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 alternate network paths on a network, the method comprising the steps of:

selecting a first neighbor for alternate path processing based on a historical ability of that first neighbor to provide alternate paths to destinations on the network;

calculating whether the first neighbor is able to provide an alternate path to any destinations;

determining whether a stop calculation criterion has been met; and

iterating the steps of selecting, calculating, and determining for other neighbors of the node until the stop calculation criterion has been met.

2. The method of claim 1, wherein the step of calculating generates a number indicative of for how many destinations the first neighbor is able to serve as an alternate path.

3. The method of claim 2, wherein the number is used to rank neighbors for subsequent alternate path calculation processes.

4. The method of claim 2, wherein the historical ability is associated with how many destinations the first neighbor has been able to provide during earlier alternate path calculations.

5. The method of claim 1, further comprising obtaining a ranked list of neighbors, said ranked list being sorted according to the historical ability of the neighbors to provide alternate paths to destinations on the network.

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

7. The method of claim 1, wherein the stop calculation criterion is based on an amount of computation time expended in connection with the alternate path calculation process.

8. The method of claim 1, wherein the stop calculation criterion is based on whether alternate paths have been found for a sufficient number of destinations.

9. The method of claim 1, wherein the stop calculation criterion is based on whether a number of new alternate paths being found for each neighbor being considered has passed below a threshold.

10. The method of claim 1, further comprising re-ranking the neighbors upon determining that a stop calculation criterion has been met.

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

12. The method of claim 1, wherein the alternate path is a U-turn alternate path.

13. A computer implemented method of computing alternate network paths on an IP network by a node on the network, the method comprising the steps of:

ranking, by the node, neighbors according to the number of destinations the nodes are able to reach as alternate paths;

preferentially selecting neighbors with a relatively higher ranking for initial processing when computing alternate network paths on the IP network.

14. The computer implemented method of claim 13, wherein the step of ranking comprises considering historical abilities of the neighbors as alternate paths on the network.

15. The computer implemented method of claim 13, wherein the step of ranking comprises causing the historical contribution to decay over time.

16. A network element configured to compute alternate network paths on an IP network, comprising:

a processor containing control logic configured to;

rank, by the node, neighbors according to a number of destinations the neighbors are able to reach as alternate network paths;

preferentially select neighbors with a relatively higher ranking for initial processing when computing alternate network paths on the IP network.

18. The network element of claim 16, wherein the control logic is configured to stop computing alternate network paths by applying a plurality of stop calculation criteria.

19. The network element of claim 18, wherein any one of the plurality of stop calculation criteria will cause the control logic to stop computing alternate network paths, and wherein the criteria comprise:

whether a computation time has exceeded a first threshold;

whether a number of neighbors considered has exceeded a second threshold; and

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

20. The network element of claim 16, wherein the control logic is configured to re-rank the neighbors according to the new number of destinations the neighbors are able to reach as alternate, paths as determined in a most recent process of computing alternate network paths.

21. The network element of claim 16, wherein at least one of the alternate network paths is a U-turn alternate network path.

17. The network element of claim 17, further comprising:

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