Definition of Interval Routing

The underlying topology is a symmetric digraph G = (V,E), V being the set of routers of the network, and each bidirectional link between the nodes x and y is represented by two opposite arcs of E: (x,y) and (y,x). We denote by $\deg(x)$ the number of neighbors of x. For the routing problems, we will also assume that the graph is always finite and connected; moreover it has no loops and no multi-arcs. Although in the common model, the graph is undirected, Interval Routing can be applied to general digraphs. The definition quoted below holds for weighted graphs. The distinction between weighted and unweighted graphs will be relevant later in Section 2.2 when the length of the routing paths induced will be taken into consideration.

¹

Sometimes the set $\{0,\ldots,\vert V\vert-1\}$ is used for the definition of the node-labeling $\cL$. Note that any ordered set can be used as well.

An IRS on G induces a routing function on G, which is a function that returns for every source-destination pair (x,y) a path from x to y defined by the sequence of nodes of Condition 3. Such a path is called a routing path. When a pair $(\cL,\cI)$ of labeling satisfies Conditions 1 and 2, it is called an Interval Labeling Scheme (ILS for short). An ILS on G is not necessary an IRS on G. In particular, Condition 3 fails if there exists a z, for some edge {x,y}, such that $z \neq x$, $z \neq y$ and $z \in \cI(x,y) \cap \cI(y,x)$. In this case we have an infinite loop between x and y whenever the destination of the message is z. Note that some label $\cI(x,y)$ may be empty, and the link (x,y) not used. An IRS on a graph is a valid ILS, that is an ILS satisfying Condition 3. For the routing problem, we are only interested in valid ILS. The validity of every ILS (Condition 3) can be checked in O(n²) time [vLT86], where n is the number of nodes of the graph.

Figure 1: A valid interval labeling scheme for a path.

We can check that Condition 1, 2, and 3 for the example of Figure 1 are satisfied. Of course many different labelings are possible for the same graph.