-
- Turgay Korkmaz
- Dept. of Elec. & Comp. Eng., University of Arizona, Tucson, AZ
-
- Marwan Krunz
- Dept. of Elec. & Comp. Eng., University of Arizona, Tucson, AZ
-
- Spyros Tragoudas
- Dept. of Elec. & Comp. Eng., Southern Illinois University, Carbondale, IL
抄録
<jats:p> One of the key issues in providing end-to-end quality-of-service guarantees in packet networks is how to determine a <jats:italic>feasible</jats:italic> route that satisfies a set of constraints while simultaneously maintaining high utilization of network resources. In general, finding a path subject to multiple <jats:italic>additive</jats:italic> constraints (e.g., delay, delay-jitter) is an NP-complete problem that cannot be exactly solved in polynomial time. Accordingly, heuristics and approximation algorithms are often used to address to this problem. Previously proposed algorithms suffer from either excessive computational cost or low performance. In this paper, we provide an efficient approximation algorithm for finding a path subject to two additive constraints. The worst-case computational complexity of this algorithm is within a logarithmic number of calls to Dijkstra's shortest path algorithm. Its average complexity is much lower than that, as demonstrated by simulation results. The performance of the proposed algorithm is justified via theoretical performance bounds. To achieve further performance improvement, several extensions to the basic algorithm are also provided at low extra computational cost. Extensive simulations are used to demonstrate the high performance of the proposed algorithm and to contrast it with other path selection algorithms. </jats:p>
収録刊行物
-
- ACM SIGMETRICS Performance Evaluation Review
-
ACM SIGMETRICS Performance Evaluation Review 28 (1), 318-327, 2000-06
Association for Computing Machinery (ACM)
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1360574094325393664
-
- NII論文ID
- 30025061007
-
- ISSN
- 01635999
-
- データソース種別
-
- Crossref
- CiNii Articles