QoS routing in networks with inaccurate information: Theory and algorithms

This paper investigates the problem of routing flows with quality-of-servic e (QoS) requirements through one or more networks, when the information ava ilable for making such routing decisions is inaccurate. Inaccuracy in the i nformation used in computing QoS routes, e.g., network state such as link a nd node metrics, arises naturally in a number of different environments tha t are reviewed in the paper, Our goal is to determine the impact of such in accuracy on the ability of the path-selection process to successfully ident ify paths with adequate available resources. In particular, we focus on dev ising algorithms capable of selecting path(s) that are most likely to succe ssfully accommodate the desired QoS, in the presence of uncertain network s tate information. For the purpose of our analysis, we assume that this unce rtainty is expressed through probabilistic models, and we briefly discuss s ample 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 s pecial cases of interest and develop useful heuristics.