Premium
Greedy online algorithms for routing permanent virtual circuits
Author(s) -
Havill Jessen T.,
Mao Weizhen
Publication year - 1999
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(199909)34:2<136::aid-net7>3.0.co;2-6
Subject(s) - computer science , greedy algorithm , electronic circuit , routing (electronic design automation) , algorithm , routing algorithm , distributed computing , computer network , routing protocol , engineering , electrical engineering
We analyze the competitive ratio of two greedy online algorithms for routing permanent virtual circuits in a network with arbitrary topology and uniform capacity links. We show that the competitive ratio of the first algorithm, with respect to network congestion, is in $\Omega(\sqrt{{\cal D}m})$ and $O(\sqrt{{\cal DL}m}),$ where m is the number of links in the network, is the maximum ratio, over all requests, of the length of the longest path for the request to the length of the shortest path for the request, and ℒ is the ratio of the maximum‐to‐minimum bandwidth requirement. We show that the competitive ratio of the second greedy algorithm is in Ω( d + log( n − d )) and min{ O ( d log n ), $O(\sqrt{{\cal DL}m})\}$ when the optimal route assignment is pairwise edge disjoint, where n is the number of network nodes and d is the length of the longest path that can be assigned to a request. It is known that the optimal competitive ratio for this problem is Θ(log n ). Aspnes et al. designed a Θ(log n ) competitive online algorithm that computes an exponential function of current congestion to make each decision. The greedy online algorithms, although not optimal, make each decision more quickly and still have good competitive ratios in many nontrivial situations. © 1999 John Wiley & Sons, Inc. Networks 34: 136–153, 1999