A Survey on Interval Routing

Cyril Gavoille

Abstract:

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.