Title :
An overview of constraint-based path selection algorithms for QoS routing
Author :
Kuipers, Fernando ; Van Mieghem, Piet ; Korkmaz, Turgay ; Krunz, Marwan
Author_Institution :
Delft Univ. of Technol., Netherlands
fDate :
12/1/2002 12:00:00 AM
Abstract :
Constraint-based path selection aims at identifying a path that satisfies a set of quality of service (QoS) constraints. In general, this problem is known to be NP-complete, leading to the proposal of many heuristic algorithms. We provide an overview of these algorithms, focusing on restricted shortest path and multi-constrained path algorithms.
Keywords :
computational complexity; quality of service; telecommunication network routing; NP-complete problem; QoS constraints; QoS routing; constraint-based path selection algorithms; heuristic algorithms; multi-constrained path algorithms; quality of service; restricted shortest path algorithms; Approximation algorithms; Cost function; Delay; Heuristic algorithms; NP-complete problem; Polynomials; Proposals; Quality of service; Routing; Upper bound;
Journal_Title :
Communications Magazine, IEEE
DOI :
10.1109/MCOM.2002.1106159
