TITLE: The Compactness of Interval Routing for Almost All Graphs
AUTHORS: Cyril Gavoille and David Peleg
ABSTRACT:
Interval routing is a compact way for representing routing tables on a
graph. It is based on grouping together, in each node, destination
addresses that use the same outgoing edge in the routing table. Such
groups of addresses are represented by some intervals of consecutive
integers. We show that almost all the graphs, i.e., a fraction of at
least 1-1/n2 of all the n-node graphs,
support a shortest path interval routing with three intervals
per outgoing edge, even if the addresses of the nodes are arbitrarily
fixed in advance and cannot be chosen by the designer of the routing
scheme. In case the addresses are initialized randomly, we show that
two intervals per outgoing edge suffice, and conversely, that
two intervals are required, for almost all graphs. Finally, if the
node addresses can be chosen as desired, we show how to design in
polynomial time a shortest path interval routing with a single
interval per outgoing edge, for all but at most
O(log3n) outgoing edges in each node. It follows
that almost all graphs support a shortest path routing scheme which
requires at most n+O(log4n) bits of routing
information per node, improving on the previous upper bound.