TY - JOUR
T1 - Conditions that impact the complexity of QoS routing
AU - Kuipers, F.A.
AU - Van Mieghem, P.F.A.
PY - 2005
Y1 - 2005
N2 - Finding a path in a network based on multiple constraints (the MCP problem) is often considered an integral part of quality of service (QoS) routing. QoS routing with constraints on multiple additive measures has been proven to be NP-complete. This proof has dramatically influenced the research community, resulting into the common belief that exact QoS routing is intractable in practice. However, to our knowledge, no one has ever examined which ¿worst cases¿ lead to intractability. In fact, the MCP problem is not strong NP-complete, suggesting that in practice an exact QoS routing algorithm may work in polynomial time. The goal of this paper is to argue that in practice QoS routing may be tractable. We will provide properties, an approximate analysis, and simulation results to indicate that NP-completeness hinges on four conditions, namely: 1) the topology; 2) the granularity of link weights; 3) the correlation between link weights; and 4) the constraints. We expect that, in practice, these conditions are manageable and therefore believe that exact QoS routing is tractable in practice.
AB - Finding a path in a network based on multiple constraints (the MCP problem) is often considered an integral part of quality of service (QoS) routing. QoS routing with constraints on multiple additive measures has been proven to be NP-complete. This proof has dramatically influenced the research community, resulting into the common belief that exact QoS routing is intractable in practice. However, to our knowledge, no one has ever examined which ¿worst cases¿ lead to intractability. In fact, the MCP problem is not strong NP-complete, suggesting that in practice an exact QoS routing algorithm may work in polynomial time. The goal of this paper is to argue that in practice QoS routing may be tractable. We will provide properties, an approximate analysis, and simulation results to indicate that NP-completeness hinges on four conditions, namely: 1) the topology; 2) the granularity of link weights; 3) the correlation between link weights; and 4) the constraints. We expect that, in practice, these conditions are manageable and therefore believe that exact QoS routing is tractable in practice.
UR - http://resolver.tudelft.nl/uuid:0d97a48b-4445-4e2b-bb48-87e50e3f5085
U2 - 10.1109/tnet.2005.852882
DO - 10.1109/tnet.2005.852882
M3 - Article
SN - 1063-6692
VL - 13
SP - 717
EP - 730
JO - IEEE - ACM Transactions on Networking
JF - IEEE - ACM Transactions on Networking
IS - 4
ER -