TITLE: Local Memory Requirement of Universal Routing Schemes AUTHORS: Pierre Fraigniaud and Cyril Gavoille ABSTRACT: In this paper, we deal with the compact routing problem, that is the problem of implementing routing schemes that use a minimum memory size on each router. A {\em universal\/} routing scheme is a scheme that applies to all 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 routing scheme satisfying that the maximum ratio between the lengths of the routing paths and the lengths of the shortest paths, that is the {\em stretch factor}, is bounded by~$s$. In~\cite{FG95a}, Fraigniaud and Gavoille improve this bound by proving that universal routing schemes of stretch factors at most~2 use a total of $\Omega(n^2)$ memory bits in the worst-case. Recently, Gavoille and Pérennès~\cite{GP95b} showed that, in fact, in the worst-case, $\Theta(n)$ routers of an $n$-node network may require up to $\Omega(n \log n)$ memory bits for shortest path routing. In this paper, we extend this result by showing that, for any constant $\varepsilon$, $0<\varepsilon<1$, $\Omega(n^\varepsilon)$ routers of an $n$-node network may require up to $\Omega(n \log n)$ memory bits even if each routing path is of length up to twice the distance between its source and its destination.