Non-Deterministic Interval Routing Schemes

The study of *non-deterministic* IRS has been suggested
in [vLT86]. It consists in relaxing Condition 2b in
Definition 1 in Paragraph 2.1, a destination may
belong to several arc-labels of a given node. In this case, the
routing process can choose at random, or following some static rules,
a link to forward the message. This allows more flexible routing for
dynamic traffic of the network. An IRS in which the arc-labels overlap
is so-called *multipath* IRS. An *all-shortest paths* IRS
denotes an multipath IRS that encodes in every source node *u* all the
possible shortest paths from *u*. Multipath IRS has been studied
in [FGS94] for chordal rings. Whereas it is NP-complete to know
whether a graph supports or not a shortest path 1-LIRS (cf.
Paragraph 2.6), we have the following characterizations
for all-shortest paths 1-LIRS classes.

The characterization remains open for IRS of compactness .
However, restricted to the dynamic cost model, we have the following
characterization of all-shortest paths *k*-IRS:

The characterization results of shortest path minimum dynamic cost
*k*-IRS is given in Paragraph 4.1.

Multipath *k*-IRS corresponds to the model of * multi-dimensional* IRS of dimension 1 (MIRS for short). This
method is a natural generalization of Interval Routing, and it has
been proposed by [FGNT98b]. Roughly speaking, the labeling of the
node is a *d*-tuple of integers considered as a point of an Euclidien
space of dimension *d*. The arc-labeling consists of an union of
Cartesian product of intervals [*a*,*b*] (i.e., consecutive set of
integers). Each product can be seen as a rectangle volume of points
in a *d*-dimensional Euclidien space. The router sends a message
along an incident link that is labeled by a rectangle volume that
contains the destination point. Some results can be found
in [RS97] (see also Theorem 63 in
Paragraph 4.5), and in [KRRS98] for
deadlock-free MIRS (cf. 4.4).

Several labeling schemes based also on multipath Interval Routing are proposed in [GV96]. These schemes, called Topological and Hyper-Rectangle Routing Schemes, are compared with Interval Routing for several classes of graphs.

In [Zem97], a particular case of multipath IRS called 2-adaptive IRS has been proposed. Every destination must appear in exactly two different sets . The two choices achieves two routing paths: a shortest path and a deflecting path. Surprisingly, this potentiality decreases the compactness of the routing schemes in many cases.

As remarked in [GP97], the lower bounds of the compactness of all-shortest paths IRS are the same as the ones expressed in the theorems 16, 17, 31, and 34 because the proofs are based on the uniqueness of the shortest paths. These bounds also hold for shortest and multipath IRS in which each destination appears arbitrary but fixed many times in the arc-labels of every source node. Whereas they also apply for the multi-dimensional model (dimension 1), they do not apply for the 2-adaptive IRS with deflecting path developed by [Zem97] because the deflecting path is not necessary a shortest path.