TR-95-18: Lower Bounds for Compact Routing
ÐÓ°ÉÔ´´ University
Technical Report TR-95-18
July 1995
Lower Bounds for Compact Routing
Abstract
In this paper we present lower bounds for compact routing schemes. 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/logn) 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 Ω(n2) 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 Ω(n2 / log n) (resp. Ω(n2/ log2 n)) memory bits.