QoS routing in networks with uncertain parameters

We consider the problem of routing connections with quality of service (QoS ) requirements across networks when the information available for making ro uting decisions is inaccurate Such uncertainty about the actual state of a network; component arises naturally in a number of different environments, 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 guarantee s, this problem is intractable. However. we show that by decomposing the en d-to-end constraint into local delay. constraints, efficient and tractable solutions can be established, Moreover, we argue that such decomposition be tter reflects the interoperability between the routing and reservation phas es. We first consider the simpler problem of decomposing the end-to-end constra int into local constraints for a given path. We show that, for general dist ributions, this problem is also intractable. Nonetheless, by defining a cer tain class of probability distributions, which includes typical distributio ns, and restricting ourselves to that class, we are able to establish effic ient and exact solutions. We then consider the general problem of combined path optimization and delay decomposition and present efficient solutions, Our findings are applicable also to a broader problem of finding a path tha t meets QoS requirements at minimal cost, where the cost of each link is so me general increasing function of the QoS requirements from the link.