QoS routing in networks with inaccurate information: Theory and algorithms

This paper investigates the problem of routing flows with quality-of-service (QoS) requirements through one or more networks, when the information available for making such routing decisions is inaccurate. Inaccuracy in the information used in computing QoS routes, e.g., network state such as link and node metrics, arises naturally in a number of different environments that are reviewed in the paper. Our goal is to determine the impact of such inaccuracy on the ability of the path-selection process to successfully identify paths with adequate available resources. In particular, we focus on devising algorithms capable of selecting path(s) that are most likely to successfully accommodate the desired QoS, in the presence of uncertain network state information. For the purpose of our analysis, we assume that this uncertainty is expressed through probabilistic models, and we briefly discuss sample cases that can give rise to such models. We establish that the impact of uncertainty is minimal for flows with only bandwidth requirements, but that it makes path selection intractable when end-to-end delay requirements are considered. For this latter case, we provide efficient solutions for special cases of interest and develop useful heuristics.