TITLE: Space-Efficiency for Routing Schemes of Stretch Factor Three
AUTHORS: Cyril Gavoille and Marc Gengler
ABSTRACT:
We deal with deterministic distributed routing algorithms on
arbitrary n-node networks. We want to minimize, for each
router, the amount of routing information that needs to be stored in
order to implement the local routing algorithm, even if the names of
the routers can be chosen in advance. We take also into account the
length of the routing paths and consider the stretch factor
which is the maximum ratio between the length of the paths computed by
the routing algorithm and the distance between the source and the
destination. We show that there exists an n-node network on
which every routing algorithm of stretch factor s < 3 requires
at least a total of Omega(n2) bits of routing
information. We show a similar result for networks of diameter 2.