Deadlock-Free Interval Routing Schemes

The study of the trade-off between the length of the routing paths and compactness, and more generally the memory requirement, is complex and is the heart of much active research [PU88,FJ90,FG97]. There are still many interesting problems related to Interval Routing which have not been solved.

Another interesting aspect related to the routing problem is the
quality of the traffic of the messages and the congestion (or load of
the links). Moreover problems related to deadlock often arise. A *deadlock* refers to a situation in which a set of messages is
blocked forever because each packet in the set holds some resources
(links or processors) that are also needed by another packet.
Deadlock-free routing is relevant in the framework of *wormhole* protocols [DS87]. The first studies dealing with
deadlock-free Interval Routing have been done in [VDLP94],
[SML94], and in [ZBG94]. An IRS on *G* is * deadlock-free* if its induced routing function on *G* is
deadlock-free (see [DS87]).

We can distinguish two approaches: itemize

study of *k*-IRS that induces deadlock-free routing function;
study of *k*-IRS with some control mechanisms, in each router,
for buffer management: A set of buffers is assigned to each router
(eventually to each link) to prevent deadlock situations, e.g., a
buffer on each *virtual channel* can be used
(see [DS87]).

itemize
[VDLP94] showed results on deadlock-free IRS for 2D-grids with
faulty regions. For the second approach, [ZBG94] unify the
notion of virtual channel and interval assigned to links. For each
edge *e* labeled by the intervals
,
and for each interval [*a*_{i},*b*_{i}],
,
it
is associated a virtual channel (using the definitions given
by [DS87]). In [ZBG94] it is showed that shortest path
deadlock-free SLIRS are closed under Cartesian product.

However this approach imposes the use of *k*-1 virtual channels if *k*
intervals per edge are used, whereas the number of buffers could be
lower than this bound if a better control of the buffers is done.

In [Fla97a] IRS deadlock-free for some classic topologies
such that trees, rings, grids, complete graphs and chordal rings are
constructed with specific controllers. Some trade-offs are derived
between the compactness of the IRS and the number of buffers in order
to guarantee deadlock-free IRS for Cartesian product based graphs:
hypercube, grids, and tori. The number of buffers used by the router
is taken into account. The notion of buffered deadlock-free *k*-IRS is
introduced. It is based on the notion of *acyclic orientation
covering*. An acyclic orientation of a graph is just an orientation
of its edges which introduces no cycles. Given an IRS *R* on a graph
*G*, the number of buffers, *s*, used in the router can be upper
bounded by the size of the smallest set of acyclic orientations of *G*
that covers all the routing paths induced by *R*
(see [Tel94, Chapter 5]). In other words, there exists a set of
*s* acyclic orientations of *G* such that all the arcs of every
routing path of *R* is contained in at least one acyclic orientation
of *G*. Note that .

In the following an *s*-buffered deadlock-free *k*-IRS is denoted by
-IRS. Here we give only a part of the results
of [Fla97a]:

In [KRRS98], interesting results about deadlock-free multi-dimensional IRS are mentioned (cf. Paragraph 4.3). In particular some trade-offs between the number of buffers, the compactness, and the dimension are given for Butterfly, Cube Connected Cycles, Hypercube and Torus. (Recall that IRS corresponds to MIRS of dimension 1.) Finally, we would like to mention that [Sch97] proposed deadlock-free IRS with experimental results for augmented grids and augmented tori.