Carleton University
Technical Report TR-253
September 1994
Bubbles: Adaptive Routing Scheme for High-Speed Dynamic Networks
Abstract
We present the rst dynamic routing schemes for high-speed networks. The scheme is based on a hierarchical bubbles partition of the underlying communication graph. We rank dynamic routing schemes by their adaptability, i.e., the maximum number of sites to be updated upon a topology change.We consider the case in which each node in the network may be directly connected with at most δ neighboring nodes. An advantage of our scheme is that it implies small number of updates upon a topology change. In particular, for the case of constant δ we prove 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. We show how to perform the routing data-base update on a dynamic network in a distributed manner.