QoS routing in networks with uncertain parameters

Publisher Website
Google Scholar
Abstract
This work considers the problem of routing connections with Qo!3 requirements across networks, when the information available for ma:king routing decisions is inaccurate. This uncertainty about the actual stale of a network component arises naturally in a number of different en- vironments, 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 re- quirements. 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 ancl delay decomposition. We present an efficient solution scheme for the abo,ve class of probability d~tributions. 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.

This publication has 4 references indexed in Scilit: