*Interval Routing* is a way of implementing routing schemes on
arbitrary networks. It is based on representing the routing table
stored at each node in a compact manner, by grouping the set of
destination addresses that use the same output port into intervals of
consecutive addresses. A possible way to represent such a scheme is to
use a connected undirected labeled graph, providing the underlying
topology of the network. The addresses are assigned to the nodes, and
the sets of destination addresses are assigned to each endpoint of the
edges. The routing is computed in a distributed way with the following
algorithm: at each intermediate node *x*, the routing process ends if
the header *y* corresponds to *x*, otherwise it is forwarded with the
message through an edge labeled by a set *I* such that .

As originally introduced in [SK82], the scheme required each set
of destinations to consist of a single interval. So, the message is
forwarded through the edge labeled by an interval [*a*,*b*] such that
.
The main advantage of this scheme is the low memory
requirement to store the routing: *O*(*d*) integers (the boundaries of
the intervals) for each node of degree *d*. Early works appear also
in [vLT83], and the first article to be published
was [SK85]. This scheme was subsequently generalized
in [vLT87] to more than one interval per edge. The Interval
Routing method is implemented in the INMOS C104 router [MT90],
and in the RCube router [ZRP$^$96]. A performance study (by
simulation) of the C104 router is given in [HKR91].

A short survey has already been presented in [vLT94]. Since then, a lot of work in the field has been done.

The paper is organized as follows: itemize Section 2 introduces the formal definition of Interval Routing, and its different related notions: compactness, dilation, stretch factor, and some basic characterizations. Section 3 presents a large collection of results concerning specific classes of networks: interconnection networks, chordal rings, planar, treewidth bounded, random graphs, and other classes of graphs and graph operators. A summary ends the section. Section 4 presents several extensions of the standard model of Interval Routing: non uniform cost link models, and the hierarchical results, deadlock-free, non-deterministic, and congestion of Interval Routing, and also the recent use of Interval Routing for solving several distributed tasks. itemize

Each paragraph ends with some open questions and conjectures. Several
new results are added: the coding of Interval Routing
(Paragraph 2.3, Theorem 1 and
Theorem 2), a lower bound concerning the treewidth
(Paragraph 3.5, Theorem 34), and a
lower bound for *K*_{n} under the dynamic link-cost model which implies
some hierarchical results of Interval Routing classes,
(Paragraph 4.1, Theorem 47 and Corollary 1).