Bandwidth-delay constrained path selection under inaccurate state information

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.