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
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
is used for the definition of
the node-labeling
.
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
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
,
and
.
In this case we have an
infinite loop between x and y whenever the destination of the
message is z. Note that some label
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(n2) time [vLT86], where n is the number of
nodes of the graph.
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.