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.

By: Roch Guerin and Ariel Orda (Technion, Israel)

Published in: Proceedings of Infocom '97. Los Alamitos, CA, IEEE Computer Society Press, 1997. p. 75-83, 1997 and IEEE/ACM Transactions on Networking, vol. 7, no. 3, June 1999, p. 350-64, IEEE in 1996

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .