Method for determining a best path between two nodes

Claim 2

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.

Claim 3

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.

Claim 4

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.

Claim 5

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

Claim 6

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

Claim 7

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.

Claim 8

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.

Claim 9

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.

Claim 10

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

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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

Claim 15

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

Claim 16

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

Claim 17

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

Claim 18

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

Claim 19

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.

Claim 20

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.

Claim 21

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

Claim 22

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.

Claim 23

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.

Claim 24

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.

Claim 25

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

Claim 26

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.

Claim 27

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

Claim 28

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