
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

An Efficient Approximate Algorithm for Finding Paths with Two Additive Constraints
Gang FENG Christos DOULIGERIS
Publication
IEICE TRANSACTIONS on Communications
Vol.E85B
No.6
pp.11431151 Publication Date: 2002/06/01 Online ISSN:
DOI: Print ISSN: 09168516 Type of Manuscript: PAPER Category: Network Keyword: quality of service, QoS routing, multiconstrained path, additive QoS constraints, highspeed networking,
Full Text: PDF>>
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 multiconstrained 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.

