TITLE: A Space Lower Bound for Routing in Trees
AUTHORS: Pierre Fraigniaud and Cyril Gavoille
ABSTRACT:
The design of compact routing schemes in trees form the kernel of
sophisticated strategies for compact routing in arbitrary graphs.
This paper focuses on the space complexity for routing messages along
shortest paths in trees. It was recently shown that the family of
n-node trees supports routing schemes using addresses and
routing tables of size O(log2n/loglogn) bits
per node, if the output port numbers of each node are chosen by an
adversary. This paper shows that this result is tight, that is the
sum of the sizes of the address and of the local routing table is at
least Omega(log2n/loglogn) bits for some node
of some tree.