Selecting alternate paths for network destinations

• US 20050073958A1
• Filed: 11/19/2004
• Published: 04/07/2005
• Est. Priority Date: 10/03/2003
• Status: Active Grant

• Current Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Avici Systems Inc.
• Inventors: Atlas, Alia Karin, Torvi, Raveendra
• Granted Patent: US 7,719,960 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

Network traffic is sent via alternate paths in cases of network link or node failure. An alternate node responds to U-Turn traffic from a primary neighbor to select a further alternate. An algorithm for determining the alternate paths is provided to select loop-free neighbors.

Claims

1. A method of minimizing path values associated with paths in a network comprising:

storing a data structure defining a network of nodes and links where the links have at least one weight between nodes;

storing plural data sets, each data set corresponding to the paths that yield the solutions of a minimization function, and each element of the data set containing a path value that corresponds to the solution for a particular node of the network for that minimization function; and

for the plural data sets, maintaining a common set of candidate nodes having path values to be inherited by other nodes; and

successively selecting nodes from the set of candidate nodes and computing path values of nodes neighboring the selected nodes from path values of the selected nodes and weight values from functions of the traversed links; and

updating any path value which has been further reduced for a node neighboring the selected node and then adding that node to the common set of candidate nodes if that node is not already in that set.

2. A method as claimed in claim 1 wherein, an element of a data set corresponding to a starting node other than the source node is initialized to a value from a function which is dependent upon the node characteristics.

3. A method as claimed in claim 2 wherein the starting node is a potential alternate to a potential U-turn alternate node.

4. A method as claimed in claim 3 wherein the path value to the starting node is initialized to a value which results in minimization of the difference between the distance from the alternate node of the U-turn alternate node to a destination node and the distance between the alternate node of the U-turn alternate node and the source node for all potential alternate nodes of that U-turn alternate node.

5. A method as claimed in claim 1 wherein a change flag is provided with respect to each path value and a path value of a neighbor node is only computed when the flag indicates a change in the path value to be considered for inheritance.

6. A method as claimed in claim 1 wherein plural data sets of path values correspond to plural potential loop free alternates.

7. A method as claimed in claim 1 wherein plural data sets of path values correspond to potential U-turn alternates.

8. A method as claimed in claim 1 wherein plural data sets of path values correspond to primary paths and reverse paths.

9. A method as claimed in claim 8 wherein, in a subsequent process, plural data sets of path values correspond to potential loop free alternates and potential U-turn alternate paths.

10. A method as claimed in claim 1 wherein the candidate nodes are ordered by minimum path value for a path that has been updated since the latter of when the node was last removed from the set of candidates and the start of the algorithm.

11. A method as claimed in claim 1 wherein potential primary fields are associated with the nodes to allow correct selection of a U-turn breaking alternate without requiring any specific policy of selection between next-hops for equal-cost paths.

12. A method as claimed in claim 1 wherein a neighbor'"'"'s visited field is associated with each node to allow correct identification of a neighbor node which can provide link-protection for broadcast or NBMA links or node-protection, said identification being used to correctly select a U-turn breaking alternate or failure protecting alternate..

13. A method as claimed in claim 1 wherein a penultimate node field is associated with each node to determine whether the node is a potential U-turn neighbor.

14. A method as in claim 1 for selecting a U-turn alternate neighbor in a network comprising:

identifying plural potential U-turn neighbors;

applying the method of claim 49 to determine the set of viable U-turn alternates from the set of potential U-turn neighbors for each node in the network; and

applying selection criteria to the results of the processing.

15. A method as claimed in claim 14 wherein the starting node is a potential alternate node of a U-turn alternate node and the path value to the starting node is initialized to a value which results in minimization of the difference between the distance from the alternate node of the U-turn alternate node to a destination node and the distance between the alternate node of the U-turn alternate node and the source node for all potential alternate nodes for that particular U-turn alternate node.

16. A method of minimizing path values associated with paths in a network comprising:

storing a data structure defining a network of nodes and link where the links have at least one weight between nodes;

storing plural data sets, each data set corresponding to the paths that yield the solutions of a minimization function, and each element of the data set containing a path value that corresponds to the solution for a particular node of the network for that minimization function; and

processing a Dijkstra algorithm with respect to the plural data sets of path values by selecting nodes from a common set of candidate nodes having path values to be inherited by other nodes as the plural data sets are processed together in accordance with the Dijkstra algorithm where the weight used is a function of the link characteristics; and

updating any path value which has been further reduced for a node neighboring the selected node and then adding that node to the common set of candidate nodes if that node is not already in that set.

17. A router within a network comprising:

a data structure defining the network of nodes and link weights between the nodes;

plural data sets, each data set corresponding to the solutions (which will be referred to as paths in the remainder of the claims) of a particular minimization function, and each element of the data set corresponding to the computation of the solution for a particular node of the network for that particular minimization function; and

a set of one or more processors that, for the plural data sets, maintains a common set of candidate nodes having path values to be inherited by other nodes and that successively selects nodes from the set of candidate nodes and computes path values of nodes neighboring the selected values from path values of the selected nodes and weight values based on functions of the traversed links.

18. A method of identifying whether a neighbor node is a U-turn alternate neighbor relative to each node in a network comprising:

storing a data structure defining a network of nodes and link weights between nodes;

providing a data set of path values, each element of the data set corresponding to one of the nodes of the network;

identifying plural potential alternate nodes of the neighbor node;

with respect to each of the potential alternate nodes of the neighbor node, successively computing path values of neighbor nodes by adding link weights to already computed path values, newly computed path values replacing prior corresponding path values where the prior values are larger.

19. A method as claimed in claim 18 wherein the starting node is a potential alternate node of a U-turn alternate node and the path value for the starting node is initialized to a value which when done for all such starting nodes results in the minimization of the difference between the distance from the alternate node of the U-turn alternate node to a destination node and the distance between the alternate node of the U-turn alternate node and the source node for all potential alternate nodes for that particular U-turn alternate node.

20. A method of selecting a U-turn alternate neighbor in a network comprising:

identifying plural potential U-turn neighbors;

applying an algorithm that determines the set of viable U-turn alternates from the set of potential U-turn neighbors for each node in the network; and

applying selection criteria to the results of the processing.

21. A method as in claim 20 where the algorithm is at least one application of the Dijkstra algorithm, where each application is on an altered network.

22. A method as claimed in claim 20 wherein the starting node is a potential alternate node of a U-turn alternate node and the path value to the starting node is initialized to a value which results in minimization of the difference between the distance from the alternate node of the U-turn alternate node to a destination node and the distance between the alternate node of the U-turn alternate node and the source node for all potential alternate nodes for that particular U-turn alternate node.

23. A router within a network comprising:

a data structure defining the network of nodes and link weights between the nodes;

a data set of path values, each element of the data set corresponding to one of the nodes of the network; and

a processor that identifies plural U-turn alternates and applies selection criteria to obtain a subset per set of nodes.

24. A method of selecting alternate paths comprising:

storing a data structure defining a network of nodes and link weights between nodes;

processing the data structure to identify a first set of alternates from the node; and

processing the data structure to identify a second set of alternates that can be used when a U-turn data packet is received at the node.

25. A method as claimed in claim 24 wherein the alternates include loop free alternates and U-turn alternates.

26. A method as claimed in claim 25 wherein the data structure is processed using a Dijkstra algorithm.