US 6,301,244 B1Granted

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

AssigneeNortel Networks Limited

InventorsKaiyuan Huang, Gang Luo, Jianli Wang

Life of this patent

Estimating the term…

Loading patent…

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.

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

7 more elements

Abstract

Claims8