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 $[a_1,b_1] \cup \ldots \cup [a_k,b_k]$, and for each interval [a_i,b_i], $2 \leqs i \leqs k$, 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 $s \geqs 2$.

In the following an s-buffered deadlock-free k-IRS is denoted by $\edge{k,s}$-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.