An Efficient Approximate Algorithm for Finding Paths with Two Additive Constraints

• FENG Gang

  the Department of Electrical and Computer Engineering, University of Miami

• DOULIGERIS Christos

  the Department of Informatics, University of Piraeus

抄録

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.

収録刊行物

• IEICE transactions on communications

  IEICE transactions on communications 85 (6), 1143-1151, 2002-06-01

  一般社団法人電子情報通信学会

キーワード

• quality of service
• QoS routing
• multi-constrained path
• additive QoS constraints
• high-speed networking

詳細情報

• CRID: 1570854177489069056
• NII論文ID: 110003219442
• NII書誌ID: AA10826261
• ISSN: 09168516
• 本文言語コード: en
• データソース種別:
  • CiNii Articles