An Efficient Approximate Algorithm for Finding Paths with Two Additive Constraints

Gang FENG  Christos DOULIGERIS  

Publication
IEICE TRANSACTIONS on Communications   Vol.E85-B   No.6   pp.1143-1151
Publication Date: 2002/06/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Network
Keyword: 
quality of service,  QoS routing,  multi-constrained path,  additive QoS constraints,  high-speed networking,  

Full Text: PDF>>
Buy this Article



Summary: 
The problem of finding a path with two additive constraints, in particular finding a path that satisfies both the cost and the delay constraints, is called multi-constrained path (MCP) problem in the literature. In this paper, we explore the MCP problem based on the idea of single mixed weight --a mixed weight for each link is first obtained by combining its delay and cost, and then Dijkstra's algorithm is used to find the corresponding shortest path. Given two infeasible paths, it can be theoretically proved that a better path can possibly be found if we choose an appropriate parameter to construct the mixed weight. An approximate algorithm is thus proposed to solve the MCP problem. Theoretical analysis demonstrates that this algorithm can make a correct judgment whether there is a feasible path or not with a very high probability even in the strict case where the delay bound is between the delays of the least delay path and the least cost path, while the cost bound is between the costs of the two paths. On the other hand, the time complexity of this algorithm is very small since it only needs to execute Dijkstra's algorithm a limited number of times. The excellent performance of the proposed algorithm is verified by a large number of experiments on networks of different sizes.