Compact Routing Schemes for Dynamic Ring Networks

We consider the problem of routing in an asynchronous dynamically changing ring of processors using schemes that minimize the storage space for the routing information. In general, applying static techniques to a dynamic network would require significant re-computation. Moreover, the known dynamic techniques applied to the ring lead to inefficient schemes. In this paper we introduce a new technique, Dynamic Interval Routing, and we show tradeoffs between the stretch factor, the adaptation cost, and the size of the update messages used by routing schemes based upon it. We give three algorithms for rings of maximum size N: the first two are deterministic, one with adaptation cost zero but worst case stretch factor \lfloor N/2 \rfloor, the other with worst case adaptation cost O(N) update messages of O(log N) bits and stretch factor 1. The third algorithm is randomized, uses update messages of size O(k log N), has adaptation cost O(k), and expected stretch factor 1+1/k, for any integer k ≥ 3. All schemes require O(log N) bits per node for the routing information and all messages headers are of O(log N) bits.