Research Article
Solving the multi-constrained path selection problem by using depth first search
@INPROCEEDINGS{10.1109/QSHINE.2005.57, author={ Zhenjiang Li and J.J. Garcia-Luna-Aceves}, title={Solving the multi-constrained path selection problem by using depth first search}, proceedings={2nd International ICST Conference on Quality of Service in Heterogeneous Wired/Wireless Networks}, publisher={IEEE}, proceedings_a={QSHINE}, year={2005}, month={12}, keywords={}, doi={10.1109/QSHINE.2005.57} }- Zhenjiang Li
J.J. Garcia-Luna-Aceves
Year: 2005
Solving the multi-constrained path selection problem by using depth first search
QSHINE
IEEE
DOI: 10.1109/QSHINE.2005.57
Abstract
An extended depth-first-search (EDFS) algorithm is proposed to solve the multi-constrained path (MCP) problem in quality-of-service (QoS) routing, which is NP-Complete when the number of independent routing constraints is more than one. EDFS solves the general k-constrained MCP problem with pseudo-polynomial time complexity O(m2 middot EN + N2), where E and N are the number of links and nodes of a graph respectively, and m is the maximum number of feasible paths maintained for each destination. This is achieved by deducing potential feasible paths from knowledge of previous explorations, without re-exploring finished nodes and their descendants in the process of the DFS search. One unique property of EDFS is that the tighter the constraints are, the better the performance it can achieve, w.r.t. both time complexity and routing success ratio. Analysis and extensive simulation are conducted to study the performance of EDFS in finding feasible paths that satisfy multiple QoS constraints. The main results show that EDFS is insensitive to the number of constraints, and outperforms other popular MCP algorithms when the routing constraints are tight or moderate. The performance of EDFS is comparable with that of the other algorithms when the constraints are loose