Introduction

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 $y \in I$.

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 $a \leqs y \leqs b$. 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).