Heuristic and Exact Algorithms for QoS Routing with Multiple Constraints(Regular section)

概要

論文の詳細を見る
The modern network service of finding the optimal path subject to multiple constraints on performance metrics such as delay, jitter, loss probability, etc. gives rise to the multiconstrained optimal-path (MCOP) QoS routing problem, which is NP-complete. In this paper, this problem is solved through both exact and heuristic algorithms. We propose an exact algorithm E_-MCOP, which first constructs an aggregate weight and then uses a K-shortest-path algorithm to find the optimal solution. By means of E_-MCOP, the performance of the heuristic algorithm H_-MCOP proposed by Korkmaz et al. in a recent work is evaluated. H_-MCOP only runs Dijkstra's algorithm (with slight modifications) twice, but it can find feasible paths with a success ratio very close to that of the exact algorithm. However, we notice that in certain cases its feasible solution has an unsatisfactorily high average cost deviation from the corresponding optimal solution. For this reason, we propose some modified algorithms based on H_-MCOP that can significantly improve the performance by running Dijkstra's algorithm a few more times. The performance of the exact algorithm and heuristics is investigated through computer simulations on networks of various sizes.
社団法人電子情報通信学会の論文
2002-12-01