QoS-oriented one-to-all route selection method for communication networks

• US 6,301,244 B1
• Filed: 12/11/1998
• Issued: 10/09/2001
• Est. Priority Date: 12/11/1998
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Wang, Jianli, Luo, Gang, Huang, Kaiyuan
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): NGUYEN, BRIAN D
• Application Number:
  US09/208,980
• Time in Patent Office: 1,033 Days
• Field of Search: 370/351, 370/352, 370/355, 370/356, 370/395, 370/229, 370/230, 370/231, 370/235, 370/238, 370/252, 370/254, 370/255, 370/256, 370/401, 370/406, 370/407, 370/408, 709/232, 709/238, 709/241
• US Class Current: 370/351
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/124 using a combination of metrics

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.

Claims

1. 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).

2. 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.

3. The method of claim 2 wherein step (a) is performed using Dijkstra'"'"'s algorithm.

4. 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.

5. The method of claim 4 wherein step (d) is performed using Dijkstra'"'"'s algorithm.

6. 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.

7. 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.

8. 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.