US6061736A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Routing over similar paths
Assignee: HP Inc
•
Filing: 1998-03-13
•
Granted: 2000-05-09
•
Expires: 2018-03-13
Abstract
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.
Inventors
- 👤 Haim Rochberger
- 👤 G. Paul Koning
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 22:04
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/12
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
244 words
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.
Claim 2
Independent Claim
244 words
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.
Claim 3
Dependent Claim
58 words
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.
Claim 4
Dependent Claim
65 words
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.
Claim 5
Dependent Claim
17 words
A method in accordance with claim 3, wherein: said counting starts from a number greater than one.
Claim 6
Dependent Claim
78 words
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.
Claim 7
Dependent Claim
79 words
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.
Claim 8
Dependent Claim
47 words
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.
Claim 9
Independent Claim
212 words
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.
Claim 10
Independent Claim
212 words
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.
Claim 11
Dependent Claim
97 words
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.
Claim 12
Dependent Claim
58 words
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.
Claim 13
Dependent Claim
68 words
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.
Claim 14
Independent Claim
125 words
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.
Claim 15
Independent Claim
125 words
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.
Claim 16
Dependent Claim
58 words
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.
Claim 17
Dependent Claim
69 words
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.
References Cited (Backward Citations)
US5117422A
Cited
US5251205A
Cited
US5481604A
Cited
US5854899A
Cited
US5940396A
Cited
US5964841A
Cited
US5946295A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-09 | 2003-11-08 | 2004-05-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-09 | 2007-11-08 | 2008-05-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-09 | 2011-11-08 | 2012-05-09 | $7700.00 | Window Closed / Lapsed |