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(2) + mn log n). We present a probabilistic quickest path algorithm that computes an approximate quickest path with time complexity O(pm + pn log n) by randomly selecting p less than or equal to 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 0(pm + pn log n). (C) 2003 Elsevier B.V. All rights reserved.