Patent ID: 6301244
Filing Date: 2001-10-09
Classification: H04L

Abstract:
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)<.ltoreq.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).