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

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.