TITLE: The Compactness of Adaptive Routing Tables
AUTHORS: Cyril Gavoille and Akka Zemmari
ABSTRACT:
The compactness of a routing table is a complexity measure of the
memory space needed to store the routing table on a network whose
nodes have been labeled by a consecutive range of integers. It is
defined as the smallest integer k such that, in every node
u, every set of labels of destinations having the same output
in the table of u can be represented as the union of k
intervals of consecutive labels. If lot of works were done to study
the compactness of deterministic routing tables, few of them tackled
the adaptive case when the output of the table, for each entry, must
contain a fixed number a of routing directions. We prove that
every n-node network supports shortest path routing tables of
compactness at most n/a for an adaptiveness parameter
a, whereas we show a lower bound of
n/aO(1).