TITLE:Universal Routing Schemes AUTHORS:Pierre Fraigniaud and Cyril Gavoille ABSTRACT: 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 {\em universal\/} routing scheme is a scheme that applies to all $n$-node networks. In~\cite{PU88}, Peleg and Upfal showed that one can not 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 \geq 1$. We improve this bound for stretch factors $s$, $1 \leq 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(n\log{n})$ bits for the {\em local\/} minimum memory requirement of universal routing scheme of stretch factors $s$, $1 \leq s < 2$. More precisely, for any fixed constant $\varepsilon$, $0 < \varepsilon < 1$, there exists an $n$-node network $G$ on which at least $\Omega(n^\varepsilon)$ 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 can not compress locally the routing information better than routing tables do.