We study the complexity of compact routing on arbitrary networks. We give (1) networks on n vertices whic for any interval routing scheme, #OMEGA#(n) routers of the network require #OMEGA#(n) intervals on some out-going link and (2) for each d>=3, networks of maximal degree d which for any interval routing scheme, #OMEGA#(n) routers each require #OMEGA#(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 #OMEGA#(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 #OMEGA#(n~2/log n) (resp. #OMEGA#(n~2/log~2 n)) memory bits.
展开▼
