Routing over similar paths

• US 6,061,736 A
• Filed: 03/13/1998
• Issued: 05/09/2000
• Est. Priority Date: 03/13/1998
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Rochberger, Haim, Koning, G. Paul
• Primary Examiner(s): Rinehart, Mark H.
• Application Number:
  US09/042,162
• Time in Patent Office: 788 Days
• Field of Search: 709/241, 709/238, 709/242, 709/243, 370/380, 370/392, 370/396, 370/406, 370/409
• US Class Current: 709/241
• CPC Class Codes: H04L 45/12 Shortest path evaluation

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.

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.

2. A method in accordance with claim 1, further comprising determining an average maximum acceptable deviation for a metric of a routing path to differ from a most optimum routing path;

determining an average number of links in said routing paths;

dividing said average maximum acceptable deviation by said average number of links to determine said predetermined difference amount.

3. A method in accordance with claim 1, further comprising determining a desired maximum acceptable deviation for a metric of a routing path to differ from a most optimum routing path;

counting a number of links in each said routing path;

dividing said desired maximum acceptable deviation by said counted number of links to determine said predetermined difference amount for each said twice tentatively label node.

4. A method in accordance with claim 3, wherein:

said counting starts from a number greater than one.

5. A method in accordance with claim 1, further comprising determining a desired maximum acceptable deviation for a metric of a routing path to differ from a most optimum routing path;

determining an average number of links in all said routing paths present when operating on a twice tentatively labeled node;

dividing said desired maximum acceptable deviation by said average number of links to determine said predetermined difference when labeling a routing path for a twice tentatively label node.

6. A method in accordance with claim 5, wherein:

a default number of links is determined;

when said default number of links is greater than said average number of links, said predetermined difference is determined by dividing said desired maximum acceptable deviation by said default number of links;

when said default number of links is less than said average number of links, said predetermined difference is determined by dividing said desired maximum acceptable deviation by said average number of links.

7. A method in accordance with claim 5, wherein:

a default number of links is determined;

during a first labeling of a routing path of a twice tentatively labeled node, said predetermined difference is determined by dividing said desired maximum acceptable deviation by said default number of links.

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.

9. A method in accordance with claim 8, wherein:

for each of said nodes twice labeled as tentative nodes by more than one path node, a difference in metrics is determined between two most optimum paths of said links connecting said root node to said each twice labeled tentative node, when said difference is above said 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.

10. A method in accordance with claim 9, further comprising determining an average maximum acceptable deviation for a metric of a routing path to differ from a most optimum routing path;

determining an average number of links in said routing paths;

dividing said average maximum acceptable deviation by said average number of links to determine said predetermined difference amount.

11. A method in accordance with claim 9, further comprising determining a desired maximum acceptable deviation for a metric of a routing path to differ from a most optimum routing path;

determining an average number of links in all said routing paths present when labeling routing paths;

dividing said desired maximum acceptable deviation by said average number of links to determine said predetermined difference when labeling a routing path.

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.

13. A method in accordance with claim 12, further comprising

determining an average maximum acceptable deviation for a metric of a routing path to differ from a most optimum routing path;

determining an average number of links in said routing paths;

dividing said average maximum acceptable deviation by said average number of links to determine said predetermined difference amount.

14. A method in accordance with claim 12, further comprising

determining a desired maximum acceptable deviation for a metric of a routing path to differ from a most optimum routing path;

determining an average number of links in all said routing paths present when labeling a routing path;

dividing said desired maximum acceptable deviation by said average number of links to determine said predetermined difference when labeling a routing path.