Patent US6301244B1 successfully refreshed from Google Patents.
US6301244B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
QoS-oriented one-to-all route selection method for communication networks
Assignee: RPX Clearinghouse LLC
•
Filing: 1998-12-11
•
Granted: 2001-10-09
•
Expires: 2018-12-11
Abstract
Abstract A method is described for one-to-all route selection in Communications Networks with multiple QoS metrics. This method takes a first metric (say, delay) as a constraint and a second metric (say, cost) as an optimization target. A potential objective is to find a path between a source node and each node in a communications network such that the delay of the path does not exceed a path delay constraint and the cost of the path is minimized. The method selects a first path which is a shortest path from a source node to each node in terms of the first metric using Dijkstra's algorithm. A reachability graph is then constructed based on the first metric path constraint. Within the reachability graph, another path is found, which is a shortest path from a source node to each node in terms of the second metric, using Dijkstra's algorithm. Any path to a particular node selected within the reachability graph replaces the first path to said particular node. This method can guarantee to find a nearly optimal path with the given constraint satisfied as long as there exists such a path.
Inventors
- 👤 Kaiyuan Huang
- 👤 Gang Luo
- 👤 Jianli Wang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 21:28
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/12; H04L45/124
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
396 words
In a communication network comprising nodes interconnected by links to form paths, wherein each of the links is associated with a primary and secondary quality of service (QoS) metric, each of the primary and secondary QoS metrics being additive, a method for selecting an optimal path between a source and a destination node comprising: (a) selecting a first path between a specified source and a specified destination node from a plurality of possible paths, wherein for each of the plurality of possible paths the sum of the primary QoS metric associated with each of its corresponding links is calculated, and wherein the selected first path corresponds to the shortest calculated path; (b) eliminating a selected destination node associated with a selected one of the plurality of possible paths for which the primary QoS metric constraint is not met, the primary QoS metric constraint being compared to the shortest calculated path of each of the plurality of possible paths; (c) constructing a reachability graph comprising one or more of the plurality of possible paths, wherein a selected one of the plurality of possible paths is included in the reachability graph if the calculated primary QoS metric sum is less than a primary QoS metric constraint; (d) selecting a second path between the specified source and the specified destination node from the included paths in the reachability graph, wherein for each of the included paths the sum of the secondary QOS metric associated with each of its corresponding links is calculated, and wherein the selected second path corresponds to the lowest calculated secondary QoS metric sum; and (e) replacing the first path with the second path if the second path is different than the first path; wherein step (c) further comprises using an iterative process to calculate the primary QoS metric sum beginning at the source node and continuing with a respective neighbour set of nodes until all of the nodes have been evaluated; and wherein each iteration comprises: (a) selecting each destination node which is directly connected to the source node by one of the links, wherein a respective destination node is deemed reachable and selected if d(u)+d(u,v)<≦D where d(u) is the primary QoS metric for the source node, d(u,v) is the primary QoS metric for the respective link, and D is the primary QoS metric constraint; and (b) setting the respective selected destination node to d(u)+d(u,v).
Claim 2
Dependent Claim
396 words
In a communication network comprising nodes interconnected by links to form paths, wherein each of the links is associated with a primary and secondary quality of service (QoS) metric, each of the primary and secondary QoS metrics being additive, a method for selecting an optimal path between a source and a destination node comprising: (a) selecting a first path between a specified source and a specified destination node from a plurality of possible paths, wherein for each of the plurality of possible paths the sum of the primary QoS metric associated with each of its corresponding links is calculated, and wherein the selected first path corresponds to the shortest calculated path; (b) eliminating a selected destination node associated with a selected one of the plurality of possible paths for which the primary QoS metric constraint is not met, the primary QoS metric constraint being compared to the shortest calculated path of each of the plurality of possible paths; (c) constructing a reachability graph comprising one or more of the plurality of possible paths, wherein a selected one of the plurality of possible paths is included in the reachability graph if the calculated primary QoS metric sum is less than a primary QoS metric constraint; (d) selecting a second path between the specified source and the specified destination node from the included paths in the reachability graph, wherein for each of the included paths the sum of the secondary QOS metric associated with each of its corresponding links is calculated, and wherein the selected second path corresponds to the lowest calculated secondary QoS metric sum; and (e) replacing the first path with the second path if the second path is different than the first path; wherein step (c) further comprises using an iterative process to calculate the primary QoS metric sum beginning at the source node and continuing with a respective neighbour set of nodes until all of the nodes have been evaluated; and wherein each iteration comprises: (a) selecting each destination node which is directly connected to the source node by one of the links, wherein a respective destination node is deemed reachable and selected if d(u)+d(u,v)<≦D where d(u) is the primary QoS metric for the source node, d(u,v) is the primary QoS metric for the respective link, and D is the primary QoS metric constraint; and (b) setting the respective selected destination node to d(u)+d(u,v).
Claim 3
Dependent Claim
37 words
The method of claim 1 wherein the primary QoS metric is delay and wherein each of the links is weighted with respect to the delay and wherein the primary QoS metric constraint is a maximum allowable delay.
Claim 4
Dependent Claim
13 words
The method of claim 2 wherein step (a) is performed using Dijkstra's algorithm.
Claim 5
Dependent Claim
25 words
The method of claim 1 wherein the secondary QoS metric is cost and wherein each of the links is weighted with respect to the cost.
Claim 6
Dependent Claim
13 words
The method of claim 4 wherein step (d) is performed using Dijkstra's algorithm.
Claim 7
Dependent Claim
38 words
The method of claim 1 wherein if there is more than one source node linked to a respective destination node, the value assigned to the destination node, is the maximum of d(u)+d(u,v), providing d(u)+d(u,v) does not exceed D.
Claim 8
Dependent Claim
44 words
The method of claim 1 wherein if there is more than one node linked to a respective destination node, a selected one of the interconnecting links will be chosen if the selected link is the minimum of d(u)+d(u,v), providing d(u)+d(u,v) does not exceed D.
Claim 9
Dependent Claim
55 words
The method of claim 1 wherein a max link qualification rule and a min link qualification rule are used in a preselected sequence in constructing the reachability chart, the max link qualification rule and min link qualification rule being used when there is more than one of the nodes linked to a respective destination node.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-10-08 | 2005-04-09 | 2005-10-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-10-08 | 2009-04-09 | 2009-10-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-10-08 | 2013-04-09 | 2013-10-09 | $7700.00 | Window Closed / Lapsed |