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.

Additional Metadata
Keywords Adaptability, Communication network, Dynamic, Fiber optics, Routing
Persistent URL dx.doi.org/10.1137/S0097539797316610
Journal SIAM Journal on Computing
Citation
Dolev, S. (Shlomi), Kranakis, E, Krizanc, D. (Danny), & Peleg, D. (David). (2000). Bubbles: Adaptive routing scheme for high-speed dynamic networks. SIAM Journal on Computing, 29(3), 804–833. doi:10.1137/S0097539797316610