We study the complexity of compact routing on arbitrary networks. We give (1) networks on n vertices which for any interval routing scheme, Ω(n) routers of the network require Ω(n) intervals on some out-going link and (2) for each d≥ 3, networks of maximal degree d which for any interval routing scheme, Ω(n) routers each require Ω(n/ log n) intervals on some out-going link. Our results give the best known worst-case lower bounds for interval routing. For the case of universal routing schemes we give (3) networks on n vertices which for any near-optimal routing scheme with stretch factor<2 a total of Ω(n 2) memory bits are required, and (4) for each d ≥3, networks of maximal degree d for which any optimal (resp., near-optimal) routing scheme (resp., with stretch factor <2) requires a total of Ω(n 2/log n) (resp. Ω(n 2/log 2 n)) memory bits.