Routing algorithms for switching networks with probabilistic traffic

Switching networks with probabilistic traffic are positioned prominently in communication engineering. Measures of performance for such a network include the blocking probability of the network and the time for the routing algorithm to establish communication paths. Although literature exists concerning blocking probability, little theoretical progress in efficient routing algorithms has been made. Since the network is under a probabilistic traffic, it is meaningful to measure the routing algorithm by its expected running time. In this paper, we consider routing algorithms for a class of networks known as series-parallel networks. We first prove a lower bound for the expected time for any routing algorithm to establish a communication path and then present an algorithm that has an expected time within a constant factor of the lower bound, thus establishing the optimality of the algorithm. © 1996 John Wiley & Sons, Inc.