UNIVERSAL ROUTING SCHEMES

In this paper, we deal with the compact routing problem, that is imple menting routing schemes that use a minimum memory size on each router. A universal routing scheme is a scheme that applies to all n-node net works. In [31], Peleg and Upfal showed that one cannot implement a uni versal routing scheme with less than a total of Omega(n(1+1/(2s+4))) m emory 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 u ses a total of Omega(n(2)) memory bits in the worst-case. This result is obtained by counting the minimum number of routing functions necess ary to route on all n-node networks. Moreover, and more fundamentally, we give a tight bound of Theta(nlogn) bits for the local minimum memo ry requirement of universal routing scheme of stretch factors s, 1 les s than or equal to s <2. More precisely, for any fixed constant epsilo n, 0 <epsilon <1, there exists a n-node network G on which at least Om ega(n(epsilon)) routers require Theta(n log n) bits each to code any r outing function on G of stretch factor <2. This means that, whatever y ou choose the routing scheme, there exists a network on which one cann ot compress locally the routing information better than routing tables do.