A Survey on Interval Routing
We survey in this paper the classical results, and also the most
recent results, in the field of Interval Routing, a well-known
strategy to code in a compact way distributed routing algorithms.
These results are classified in several themes: characterization,
compactness and shortest path, dilation and stretch factor, specific
class of graphs (interconnection networks, bounded degree, planar,
chordal rings, random graphs, ...), and the other recent extensions
proposed in the literature: dead-lock free, congestion,
non-deterministic, and distributed problems related to Interval
Routing. For each of these themes we review the state of the art and
propose several open problems.