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 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).