Universal Routing Schemes

In this paper, we deal with the compact routing problem, that is implementing routing schemes that use a minimum memory size on each router. A universal routing scheme is a scheme that applies to all n-node networks. In [31], Peleg and Upfal showed that one can not implement a universal routing scheme with less than a total of \Omega\Gamma n 1+1=(2s+4) ) memory bits for any given stretch factor s 1. We improve this bound for stretch factors s, 1 s ! 2, by proving that any near-shortest path universal routing scheme uses a total of \Omega\Gamma n 2 ) memory bits in the worst-case. This result is obtained by counting the minimum number of routing functions necessary to route on all n-node networks. Moreover, and more fundamentally, we give a tight bound of \Theta(n log n) bits for the local minimum memory requirement of universal routing scheme of stretch factors s, 1 s ! 2. More precisely, for any fixed constant ", 0 ! " ! 1, there exists an n-node network G on which at least \O..