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 cannot implement a universal routing scheme with less than a total of Omega(n(1+1/(2s+4))) memory bits for any given stretch factor s greater than or equal to 1. We improve this bound for stretch factors s, 1 less than or equal to s <2, by proving that any near-shortest path universal routing scheme uses a total of Omega(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(nlogn) bits for the local minimum memory requirement of universal routing scheme of stretch factors s, 1 less than or equal to s <2. More precisely, for any fixed constant epsilon, 0 <epsilon <1, there exists a n-node network G on which at least Omega(n(epsilon)) routers require Theta(n log n) bits each to code any routing function on G of stretch factor <2. This means that, whatever you choose the routing scheme, there exists a network on which one cannot compress locally the routing information better than routing tables do.