Bubbles: Adaptive Routing Scheme for High-Speed Dynamic Networks (Extended Abstract)

) Shlomi Dolev Evangelos Kranakis y Danny Krizanc y David Peleg z 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 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 data-base, a routing strategy and a routing data-base update. It is shown how to perform the routing data-base update on a dynamic network in a distributed manner. Department of Mathematics and Computer Science, BenGurion University of the Negev, Beer-Sheva 84105, Israel. Part of this w..