TITLE:Memory Requirement for Routing in Distributed Networks AUTHORS:Cyril Gavoille and Stéphane Pérennès ABSTRACT: In this paper, we deal with the compact routing problem on distributed networks, that is implementing routing schemes that use a minimum memory size on each node. We prove that for every shortest path routing scheme, for any constant $\varepsilon$, $0 < \varepsilon < 1$, and for every integer $d$ such that $3 \leq d \leq \varepsilon n$, there exists an $n$-node network of maximum degree $d$ that locally requires $\Theta(n\log{d})$ bits of memory on $\Theta(n)$ nodes. This optimal lower bound means that whatever you choose the routing scheme (interval routing, boolean routing, prefix routing, \ldots), there exists a network on which one can not do better than routing tables.