Bubbles: Adaptive routing scheme for high-speed dynamic networks

This paper presents the first dynamic routing scheme for high-speed network s. The scheme is based on a hierarchical bubbles partition of the underlyin g communication graph. Dynamic routing schemes are ranked by their adaptabi lity, i.e., the maximum number of sites to be updated upon a topology chang e. 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 net work it is proved that our scheme is optimal in its adaptability by present ing a matching tight lower bound. Our bubble routing scheme is a combinatio n of a distributed routing database, a routing strategy, and a routing data base update. It is shown how to perform the routing database update on a dy namic network in a distributed manner.