TY - JOUR
T1 - Quality of service routing
AU - Van Mieghem, P.
AU - Kuipers, F. A.
AU - Korkmaz, T.
AU - Krunz, M.
AU - Curado, M.
AU - Monteiro, E.
AU - Masip-Bruin, X.
AU - Solé-Pareta, J.
AU - Sánchez-López, S.
PY - 2003
Y1 - 2003
N2 - Constraint-based routing is an invaluable part of a full-fledged Quality of Service architecture. Unfortunately, QoS routing with multiple additive constraints is known to be a NP-complete problem. Hence, accurate constraint-based routing algorithms with a fast running time are scarce, perhaps even non-existent. The need for such algorithms has resulted in the proposal of numerous heuristics and a few exact solutions. This chapter presents a thorough, concise, and fair evaluation of the most important multi-constrained path selection algorithms known today. A performance evaluation of these algorithms is presented based on a complexity analysis and simulation results. Besides the routing algorithm, dynamic aspects of QoS routing are discussed: how to cope with incomplete or inaccurate topology information and (in)stability issues.
AB - Constraint-based routing is an invaluable part of a full-fledged Quality of Service architecture. Unfortunately, QoS routing with multiple additive constraints is known to be a NP-complete problem. Hence, accurate constraint-based routing algorithms with a fast running time are scarce, perhaps even non-existent. The need for such algorithms has resulted in the proposal of numerous heuristics and a few exact solutions. This chapter presents a thorough, concise, and fair evaluation of the most important multi-constrained path selection algorithms known today. A performance evaluation of these algorithms is presented based on a complexity analysis and simulation results. Besides the routing algorithm, dynamic aspects of QoS routing are discussed: how to cope with incomplete or inaccurate topology information and (in)stability issues.
UR - http://www.scopus.com/inward/record.url?scp=35248857064&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35248857064&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-45190-7_3
DO - 10.1007/978-3-540-45190-7_3
M3 - Article
AN - SCOPUS:35248857064
SN - 0302-9743
VL - 2856
SP - 80
EP - 117
JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ER -