The compactness of adaptive routing tables

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 labelled 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. While many works studied 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 α of routing directions. We prove that every n-node network supports shortest path routing tables of compactness at most n/α for an adaptiveness parameter α, whereas we show a lower bound of n/α^O(1).