QRP02-4: Probabilistic Path Selection under Inaccuracy via Augmented Shortest Path Algorithms

Not all network applications can make do with the best-effort service of the original Internet design. Many new applications, including multimedia and mission-critical ones, require a certain level of service from the network to operate properly. The difficulty of finding such preferential paths is compounded by the intrinsic inaccuracies of the network state information maintained by the nodes that have to make such decisions. We choose a stochastic framework to select paths for applications that want more cooperation from the network to operate satisfactorily. We represent the stochasticity of links by means of a new composite metric composed of an interval with a lower and upper bound and an associated probability. The interpretation and relevance of our metric is such that in the next decision time period the expected value of the resource is between the upper and the lower bound with the associated probability. Simple and straightforward methods of computing our composite metric are presented. An algorithm, called Augmented-Dijkstra, with the same complexity as the standard Dijkstra, provides an effective solution for statistical bandwidth guarantees. Simulation results evaluate and confirm the effectiveness of our approach.