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.
![\begin{theorem}
% latex2html id marker 1037
[\cite{FGNT98}]\mbox{}
\beginsmall{i...
...in, and of a $K_2$-star of base $\{x,y\}$).
\par\endsmall{itemize}
\end{theorem}](img360.gif)
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:
![\begin{theorem}[\cite{FGNT98}]
For every integer $k \geqs 1$, for every real $s...
...most $s$\ (the same holds for the linear and/or
strict variants).
\end{theorem}](img361.gif)
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.