Method for determining a best path between two nodes
First Claim
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.
6 Assignments
0 Petitions
Accused Products
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.
-
Citations
25 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. - View Dependent Claims (2, 3, 4, 5)
-
-
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. - View Dependent Claims (7, 8)
-
-
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. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25)
-
Specification