Routing over similar paths
First Claim
Patent Images
1. A method for determining routing paths in a computer network, the method comprising the steps of:
- providing a plurality of nodes with a plurality of links, each of said plurality of links having a metric;
selecting one of said nodes as a root node;
labeling all nodes directly connected to said root node by said links as tentative nodes;
labeling a most optimum link connecting said root node to said tentative nodes based on said metrics as a routing path;
changing said tentative node connected to said root node by said routing path to a path node;
labeling all non-path nodes directly connected to said path node as tentative nodes;
for each of said nodes twice labeled as tentative nodes, determining a difference between two most optimum paths of said links connecting said root node to said each twice labeled tentative node, when said difference is above a predetermined difference amount a most optimum path of said two most optimum paths is labeled as a routing path, when said difference is below said predetermined difference amount one of said two most optimum paths is randomly labeled as a routing path;
labeling a most optimum link connecting said root node to said tentative nodes as a routing path based on said metrics;
changing said tentative nodes connected to said root node by said routing paths to a path node;
repeating the method steps from said twice labeled tentative node until no tentative nodes are present.
6 Assignments
0 Petitions
Accused Products
Abstract
The routing paths are determined in a step-by-step nature. A Dijkstra algorithm is used and before labeling a link as a routing path, all possible routing paths which are within a predetermined range are compared. One of the paths in the range are chosen at random to be the routing path.
-
Citations
14 Claims
-
1. A method for determining routing paths in a computer network, the method comprising the steps of:
-
providing a plurality of nodes with a plurality of links, each of said plurality of links having a metric; selecting one of said nodes as a root node; labeling all nodes directly connected to said root node by said links as tentative nodes; labeling a most optimum link connecting said root node to said tentative nodes based on said metrics as a routing path; changing said tentative node connected to said root node by said routing path to a path node; labeling all non-path nodes directly connected to said path node as tentative nodes; for each of said nodes twice labeled as tentative nodes, determining a difference between two most optimum paths of said links connecting said root node to said each twice labeled tentative node, when said difference is above a predetermined difference amount a most optimum path of said two most optimum paths is labeled as a routing path, when said difference is below said predetermined difference amount one of said two most optimum paths is randomly labeled as a routing path; labeling a most optimum link connecting said root node to said tentative nodes as a routing path based on said metrics; changing said tentative nodes connected to said root node by said routing paths to a path node; repeating the method steps from said twice labeled tentative node until no tentative nodes are present. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method for determining routing paths in a computer network, the method comprising the steps of:
-
providing a plurality of nodes with a plurality of links, each of said plurality of links having a metric; selecting one of said nodes as a root node; labeling all nodes directly connected to said root node by said links as tentative nodes; labeling a most optimum link connecting said root node to said tentative nodes based on said metrics as a routing path; changing said tentative node connected to said root node by said routing path to a path node; labeling all nodes directly connected to said path node as tentative nodes; determining a difference between two most optimum paths of said links connecting said root node to said tentative nodes, when said difference is above a predetermined difference amount a most optimum path of said two most optimum paths is labeled as a routing path, when said difference is below said predetermined difference amount one of said two most optimum paths is randomly labeled as a routing path; changing said tentative nodes connected to said root node by said routing paths to a path node; repeating the method steps from said labelling of all nodes as tentative nodes until no tentative nodes are present. - View Dependent Claims (9, 10, 11)
-
-
12. A method for determining routing paths in a computer network, the method comprising the steps of:
-
applying the Dijkstra algorithm to a root node and a plurality of other nodes connected by a plurality of links; for each of said nodes twice labeled as tentative nodes by the Dijkstra algorithm, a difference between a set of most optimum paths of said links connecting said root node to said each twice labeled tentative node is determined, when said difference is above a predetermined difference amount a most optimum path of said set of most optimum paths is labeled as a routing path, when said difference is below said predetermined difference amount one of said set of most optimum paths is randomly labeled as a routing path. - View Dependent Claims (13, 14)
-
Specification