Routing algorithms for switching networks with probabilistic traffic

Routing algorithms for switching networks with probabilistic traffic

0.00 Avg rating0 Votes
Article ID: iaor2002383
Country: United States
Volume: 28
Issue: 1
Start Page Number: 21
End Page Number: 29
Publication Date: Aug 1996
Journal: Networks
Authors: ,
Keywords: communication
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.