Premium
Routing algorithms for switching networks with probabilistic traffic
Author(s) -
Lin Geng,
Pippenger Nicholas
Publication year - 1996
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199608)28:1<21::aid-net4>3.0.co;2-f
Subject(s) - computer science , static routing , probabilistic logic , destination sequenced distance vector routing , routing (electronic design automation) , equal cost multi path routing , link state routing protocol , algorithm , multipath routing , blocking (statistics) , upper and lower bounds , distributed computing , computer network , mathematics , routing protocol , artificial intelligence , mathematical analysis
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.