Method for determining a best path between two nodes

• US 5,521,910 A
• Filed: 10/05/1994
• Issued: 05/28/1996
• Est. Priority Date: 01/28/1994
• Status: Expired due to Term

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Original Assignee: Cabletron Systems Incorporated (Extreme Networks, Inc.)
• Inventors: Matthews, Wallace
• Primary Examiner(s): Kizou, Hassan
• Application Number:
  US08/321,038
• Time in Patent Office: 601 Days
• Field of Search: 370/54, 370/60, 370/60.1, 370/94.1, 370/94.2, 370/94.3, 370/14, 370/58.1, 340/825.02, 340/825.03, 340/826, 340/827, 379/220, 379/221, 364/284.4, 364/242.94, 395/200
• US Class Current: 370/256
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 2012/5626 Network management, e.g. Intelligent nets
• CPC Class Codes: H04L 2012/5631 Resource management and allocation
• CPC Class Codes: H04L 2012/564 Connection-oriented
• CPC Class Codes: H04L 2012/5645 Connectionless
• CPC Class Codes: H04L 2012/5665 Interaction of ATM with other protocols
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/36 Backward learning
• CPC Class Codes: H04L 49/203 ATM switching fabrics with multicast or broadcast capabilities
• CPC Class Codes: H04L 49/256 Routing or path finding in ATM switching fabrics
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method for determining a best path from a source node to a destination node using a breadth first recursive search in parallel. The determination is based upon a plurality of metrics which are set by the system. A path'"'"'s metrics are compared to respective threshold values and paths are discarded if the metrics values do not each exceed respective thresholds. In addition, if a path has no metric which is better than one of the already completed paths, the path is discarded.

Claims

1. In a method of breadth-first searching to build a spanning tree, wherein a plurality of traversals are made of different paths moving outwardly from a starting point in a search to find an optimum path to a destination point based on a plurality of metrics, the improvement comprising:

initializing a vector of metrics at the starting point where a value of each metric in the vector is a best value;

traversing an arc to a next node along a path from the starting point to the destination point; and

at an end of each traversal, modifying the vector of metrics to produce a traversal value which accumulates from a best value to a worst value, comparing the values of the metrics and eliminating the paths which are not best or do not pass a threshold level in at least one metric.

2. The method of claim 1, wherein the comparing and eliminating step further comprises eliminating a path which is not better, in at least one metric, than an already completed path from the starting point to the destination point.

3. The method of claim 1, wherein the comparing and eliminating step further comprises eliminating a path which is not better than or equal to, in at least one metric, an already completed path from the starting point to the destination point.

4. The method of claim 1, wherein the method is used for routing in a communications network.

5. The method of claim 1, wherein all of the respective vector metric values and paths for a given traversal are stored and processed together.

6. In a method for routing data packets through a mesh of nodes and arcs, the improvement comprising:

a) selecting a plurality of (n+1) metrics and designating a plurality of possible values for each metric from best to worst;

b) selecting a minimum acceptable value for each metric;

c) assuming an initial set of values for the metrics;

d) starting at a source node, determining a plurality of possible paths by discovering all immediate neighboring nodes and determining a traversal set of metric values for each path;

e) repeating step d) for each discovered node and continuing until a destination node is reached; and

f) eliminating certain traversal sets of values during the repeating step e) in accordance with the following rules;

1) if a path discovers a node already within the path, terminating the path;

2) if a path discovers that its traversal value vector is not best in any of (n+1) metrics, terminating the path;

3) if a path has no metric which is better than one of the already completed paths, terminating the path;

4) if a path discovers a defective arc or node, terminating the path;

5) if a path has a metric value which does not satisfy a threshold level, terminating the path; and

6) if a path discovers an end node which is not the destination node, terminating the path.

7. The method of claim 6, wherein the nodes include switches in a data communications network, the arcs include links between the switches, and the method is used for determining the optimum path between a source switch and a destination switch for routing a data packet.

8. The method of claim 6, wherein the metrics are chosen from the list of cost, bandwidth, policy and loss.

9. In a method of concurrent breadth first searching in order to build a spanning tree through a mesh of nodes and arcs, wherein a plurality of traversals are made of different possible paths moving outwardly in rings from a source node to successive groups of neighboring nodes in a search to find an optimum path to a destination node based on a plurality of metrics, the method comprising:

initializing a vector of metrics at the source node where a value of each metric in the vector is at a best value;

starting at the source node, determining a plurality of potential paths to a first group of neighboring nodes and modifying the vector of matrices to produce a transverse set of metric values for each potential path, repeating the determining and modifying step for each successive group of neighboring nodes and continuing until the destination node is reached to obtain a completed path;

applying a choke for eliminating a potential path which is not likely to produce the optimum path; and

for each group of neighboring nodes, comparing the values of the metrics of each potential path to a given node within the group of neighboring nodes and eliminating a potential path which is not better in at least one metric than another potential path to the given node in the group.

10. The method of claim 9, wherein the chokes include one or more of:

a) eliminating a potential path which returns to a node previously covered in the same potential path;

b) eliminating a potential path which reaches a disabled arc or node;

c) eliminating a potential path which reaches an end node which is not the destination node;

d) eliminating a potential path if at least one metric value of the potential path fails a threshold level; and

e) eliminating a potential path if at least one metric value of the potential path is not better than a metric value of a completed path to the destination node.

11. The method of claim 10, including all of the chokes.

12. The method of claim 11, wherein the choke (d) is applied to the potential paths to the given node after the comprising step.

13. The method of claim 10, wherein the choke (d) is applied to the potential paths to the given node after the comparing step.

14. The method of claim 9, wherein multiple optimum paths are determined and saved.

15. The method of claim 9, wherein multiple potential paths are saved.

16. The method of claim 9, wherein one of the metrics is designated a primary metric and the completed path having a best relative value for the primary metric among the completed paths is selected as the optimum path.

17. The method of claim 16, wherein one of the metrics, different from the primary metric, is designated a secondary metric which in the event two or more completed paths have equal values for the primary metric, the secondary metric is used to select the optimum path.

18. The method of claim 9, wherein the choke requires that a potential path have at least one metric value which passes a threshold level.

19. The method of claim 9, wherein the choke requires that a potential path have at least one metric value which is better than or equal to a respective metric value of another potential path.

20. The method of claim 9, wherein the choke requires that a potential path have at least one metric value which is better than a respective metric value of another potential path.

21. The method of claim 9, wherein the nodes include switches in a data communications network, the arcs include links between the switches, and the method is used for determining the optimum path between a source switch and a destination switch for routing a data packet.

22. The method of claim 21, wherein the initializing step is provided by a network management system.

23. The method of claim 9, wherein the optimum path is optimal for one metric and passes a set of threshold tests for the other metrics and the search to find an optimum path is completed within a given time constraint.

24. The method of claim 9, wherein the method is used for ATM route determination.

25. The method of claim 9, wherein the method is used for routing in a communications network.