TITLE: Routing in Trees
AUTHORS: Pierre Fraigniaud and Cyril Gavoille
ABSTRACT:
This article focuses on routing messages along shortest paths in tree
networks, using compact distributed data structures. We mainly prove
that n-node trees support routing schemes with message headers,
node addresses, and local memory space of size O(logn) bits,
and such that every local routing decision is taken in constant
time. This improves the best known routing scheme by a factor of
O(logn) in term of both memory requirements and routing
time. Our routing scheme requires headers and addresses of size
slightly larger than logn, motivated by an inherent trade-off
between address-size and memory space, i.e., any routing scheme with
addresses on logn bits requires \Omega(\sqrt{n}) bits of
local memory-space. This shows that a little variation of the address
size, e.g., by an additive O(logn) bits factor, has a
significant impact on the local memory space.