Bubbles: Adaptive Routing Scheme for High-Speed Dynamic Networks
Authors:
- Shlomi DolevSDShlomi Dolev
- Evangelos KranakisEvangelos Kranakis
- Danny KrizancDKDanny Krizanc
- David PelegDPDavid Peleg
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 29 (3) , 804-833
Abstract
This paper presents the first dynamic routing scheme for high-speed networks. The scheme is based on a hierarchical bubbles partition of the underlying communication graph. Dynamic routing schemes are ranked by their adaptability, i.e., the maximum number of sites to be updated upon a topology change. An advantage of our scheme is that it implies a small number of updates upon a topology change. In particular, for the case of a bounded degree network it is proved that our scheme is optimal in its adaptability by presenting a matching tight lower bound. Our bubble routing scheme is a combination of a distributed routing database, a routing strategy, and a routing database update. It is shown how to perform the routing database update on a dynamic network in a distributed manner.Keywords
This publication has 17 references indexed in Scilit:
- New models and algorithms for future networksIEEE Transactions on Information Theory, 1995
- Routing with Polynomial Communication-Space Trade-OffSIAM Journal on Discrete Mathematics, 1992
- Improved routing strategies with succinct tablesJournal of Algorithms, 1990
- A trade-off between space and efficiency for routing tablesJournal of the ACM, 1989
- Paris: An approach to integrated high‐speed private networksInternational Journal of Communication Systems, 1988
- Complexity of network synchronizationJournal of the ACM, 1985
- Labelling and Implicit Routing in NetworksThe Computer Journal, 1985
- Universality considerations in VLSI circuitsIEEE Transactions on Computers, 1981
- Optimal clustering structures for hierarchical topological design of large computer networksNetworks, 1980
- Hierarchical routing for large networks Performance evaluation and optimizationComputer Networks (1976), 1977