QoS-Based Routing in Networks with Inaccurate Information: Theory and Algorithms

We investigate the problem of routing connections with QoS requirement s across one or more networks, when the information available for making routing decisions is inaccurate and expressed in some probabilistic manner. This uncertainty about the actual state of a node or network arises naturally in a number of different environments, that are reviewed in the paper. The main focus is to determine the impact of such inaccuracies on the path selection process, whos e goal is then to identify the path that is most likely to satisfy the QoS requirements. We indicate that this impact is minimal for connections with only bandwidth requirements. However, when end-to-end delay requirements are consider ed, the problem becomes intractable. Nonetheless, we obtain efficient solutions by exploring several practical approaches. We consider two models for providing del ay guarantees, a local delay model and a rate-based model, that are representative of two popular frameworks being considered for providing such guarantees. For both models, we identify a number of approaches that have reasonable complexity and l et us identify ``good'' paths for connections with end-to-end delay guarantees.