Abstract:

On the communication network, QoSbased routing has become the hot technique in order to fulfill the requirements of multimedia communications. Generally, finding a path in the network that satisfies multiple independent constraints is known to be NPcomplete. In this paper, we discuss the multiconstrained path (MCP) problem. By transforming the problem to discrete dynamic networks, which is acyclic, we propose a more efficient heuristic algorithm for QoS routing. The running time complexity is reduced from O(Tmn) to O(Tm), where m is the number of edges and n is the number of nodes, T is an integer defined by the algorithm. Further more, we theoretically prove the correctness of the algorithm. In the end, some experimental results are presented to show that the proposed algorithm performs better than other algorithms when used to solve the MCP problem. This improved heuristic algorithm can also be used in largescale networks.

Key words: QoS routing;path selection;multiconstraints;heuristic algorithm;MCP