QoS routing in networks with uncertain parameters

This work considers the problem of routing connections with QoS requirements across networks, when the information available for making routing decisions is inaccurate. This uncertainty about the actual state of a network component arises naturally in a number of different environments, which are reviewed in the paper. The goal of the route selection process is then to identify a path that is most likely to satisfy the QoS requirements. For end-to-end delay guarantees, this problem is intractable. However, we show that by decomposing the end-to-end constraint into local delay constraints, efficient and tractable solutions can be established. We first consider the simpler problem of decomposing the end-to-end constraint into local constraints, for a given path. We show that, for general distributions, this problem is also intractable. Nonetheless, by defining a certain class of probability distributions, which posses a certain convexity property, and restricting ourselves to that class, we are able to establish efficient and exact solutions. Moreover, we show that typical distributions would belong to that class. We then consider the general problem, of combined path optimization and delay decomposition. We present an efficient solution scheme for the above class of probability distributions. Our solution is similar to that of the restricted shortest-path problem, which renders itself to near-optimal approximations of polynomial complexity. We also show that yet simpler solutions exist in the special case of uniform distributions.