TY - JOUR
T1 - Bandwidth-delay constrained path selection under inaccurate state information
AU - Korkmaz, Turgay
AU - Krunz, Marwan
N1 - Funding Information:
Manuscript received February 4, 2002; revised July 24, 2002; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor J. Rexford. This work was supported by the National Science Foundation under Grant ANI 9733143, Grant CCR 9979310, and Grant ANI 0095626, and by the Center for Low Power Electronics at the University of Arizona under NSF Grant EEC-9523338.
PY - 2003/6
Y1 - 2003/6
N2 - One of the key issues in any quality-of-service (QoS) routing framework is how to compute a path that satisfies given QoS constraints. In this paper, we focus on the path computation problem subject to the bandwidth and delay constraints. This problem can be easily solved if the exact state information is available to the node performing the path computation function. In practice, however, nodes have only imprecise knowledge of the network state. The reliance on outdated information and treating this information as exact can significantly degrade the effectiveness of the path selection algorithm. To address this problem, we adopt a probabilistic approach in which the state parameters (available bandwidth and delay) are characterized by random variables. The goal is then to find the most-probable bandwidth-delay-constrained path (MP-BDCP). We provide efficient solutions for the MP-BDCP problem by decomposing it into two subproblems: the most-probable delay-constrained path (MP-DCP) problem and the most-probable bandwidth-constrained path (MP-BCP) problem. MP-DCP by itself is known to be NP-hard, necessitating the use of approximate solutions. By employing the central limit theorem and Lagrange relaxation techniques, we provide two complementary solutions for MP-DCP. These solutions are found to be highly efficient, requiring on average a few iterations of Dijkstra's shortest path algorithm. As for MP-BCP, it can be easily transformed into a variant of the shortest path problem. Our solutions for MP-DCP and MP-BCP are then combined to address the MP-BDCP problem by obtaining a set of near-nondominated paths. Decision makers can then select one or more of these paths based on a specific utility function. Extensive simulations are used to demonstrate the efficiency of the proposed algorithmic solutions and, more generally, to contrast the probabilistic path selection approach with the standard threshold-based triggered approach.
AB - One of the key issues in any quality-of-service (QoS) routing framework is how to compute a path that satisfies given QoS constraints. In this paper, we focus on the path computation problem subject to the bandwidth and delay constraints. This problem can be easily solved if the exact state information is available to the node performing the path computation function. In practice, however, nodes have only imprecise knowledge of the network state. The reliance on outdated information and treating this information as exact can significantly degrade the effectiveness of the path selection algorithm. To address this problem, we adopt a probabilistic approach in which the state parameters (available bandwidth and delay) are characterized by random variables. The goal is then to find the most-probable bandwidth-delay-constrained path (MP-BDCP). We provide efficient solutions for the MP-BDCP problem by decomposing it into two subproblems: the most-probable delay-constrained path (MP-DCP) problem and the most-probable bandwidth-constrained path (MP-BCP) problem. MP-DCP by itself is known to be NP-hard, necessitating the use of approximate solutions. By employing the central limit theorem and Lagrange relaxation techniques, we provide two complementary solutions for MP-DCP. These solutions are found to be highly efficient, requiring on average a few iterations of Dijkstra's shortest path algorithm. As for MP-BCP, it can be easily transformed into a variant of the shortest path problem. Our solutions for MP-DCP and MP-BCP are then combined to address the MP-BDCP problem by obtaining a set of near-nondominated paths. Decision makers can then select one or more of these paths based on a specific utility function. Extensive simulations are used to demonstrate the efficiency of the proposed algorithmic solutions and, more generally, to contrast the probabilistic path selection approach with the standard threshold-based triggered approach.
KW - Lagrange relaxation
KW - Multiobjective optimization
KW - Quality-of-service (QoS) routing
KW - Stochastic shortest path
UR - http://www.scopus.com/inward/record.url?scp=0038155502&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0038155502&partnerID=8YFLogxK
U2 - 10.1109/TNET.2003.813047
DO - 10.1109/TNET.2003.813047
M3 - Article
AN - SCOPUS:0038155502
SN - 1063-6692
VL - 11
SP - 384
EP - 398
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
IS - 3
ER -