QoS routing in networks with inaccurate information: theory and algorithms

Reviewer: Hosam M. F. Abo El Fotoh

The authors present a number of theoretical results on the effect of uncertainty of information about the available link bandwidth and link delay on routing decisions for flows that require QoS guarantees in terms of bandwidth and end-to-end delay. The notion of uncertainty is captured via weighted probabilistic graph models. The paper establishes two important results. First, if the uncertainty of the link bandwidth is expressed using a probability distribution function, an efficient algorithm exists. Second, the uncertainty in link delay yields an NP-hard problem. Two delay-related problems have been shown to be NP-hard, the first—where the delay is a function of the available link bandwidth (rate-based)—via a reduction from the shortest-weight-constrained-path problem, and the second (delay-based) via a reduction from the k th-largest-subset problem. The paper investigates some special cases where the complexity of the delay-related problems can be reduced. For example, efficient algorithms are presented for the cases of identical delays, identical PDFs, and exponential distribution. Also, near-optimal and pseudopolynomial algorithms are presented for the delay problem. The practicality of these results depends on the possibility of making estimates of the delay and bandwidth probabilities that truly capture the inaccuracy of the information about the network links. The paper would be of interest to both theoreticians and network designers.