Probabilistic quickest path algorithm

Due to the increasing role of quickest paths for on-demand routing in computer networks, it is important to compute them faster, perhaps, by trading-off the quality for computational speed. We consider the computation of a quickest path from a source node to a destination node for a given message size in a network with n nodes and m links each of which is specified by bandwidth and delay. Every known quickest path algorithm computes m shortest paths either directly or indirectly, and this step contributes to most of its computational complexity which is generally of the form O(m²+mnlogn). We present a probabilistic quickest path algorithm that computes an approximate quickest path with time complexity O(pm+pnlogn) by randomly selecting p≤m bandwidths at which the shortest paths are computed. We show that the delay of the computed path is close to optimal with a high probability that approaches 1 exponentially fast with respect to p/m. Simulation results indicate that this algorithm computes the optimal quickest paths with p/m<0. 1 for almost all randomly generated networks with n>40. We also present an algorithm to compute the path-table consisting of these approximate quickest paths with the same time complexity of O(pm+pnlogn).