A Necessary and Sufficient Condition for Deadlock-Free Routing in Cut-Through and Store-and-Forward Networks.
AbstractThis paper develops the theoretical background for the design of deadlock-free adaptive routing algorithms for virtual cut-through and store-and-forward switching. This theory is valid for networks using either central buffers or edge buffers. Some basic definitions and three theorems are proposed, developing conditions to verify that an adaptive algorithm is deadlock-free, even when there are cyclic dependencies between routing resources. Moreover, we propose a necessary and sufficient condition for deadlock-free routing. Also, a design methodology is proposed. It supplies fully adaptive, minimal and non-minimal routing algorithms, guaranteeing that they are deadlock-free.The theory proposed in this paper extends the necessary and sufficient condition for wormhole switching previously proposed by us. The resulting routing algorithms are more flexible than the ones for wormhole switching. Also, the design methodology is much easier to apply because it automatically supplies deadlock-free routing algorithms.
Introduction
Deadlocks may appear if the routing algorithms are not carefully designed. A
deadlock occurs when no message or packet can advance toward its destination
because the queues of the message system are full. Obviously, deadlocks arise
because the number of resources is finite.
Many deadlock-free routing algorithms have been developed for store-and-
forward computer networks. Most of them require the use of central queues, restricting
buffer allocation [7, 16, 19, 21, 28, 33]. These algorithms are also applicable
to virtual cut-through networks with central queues. Although algorithms that use
central queues require less storage than those using edge buffers, central queues
can become a bottleneck. So, algorithms that use edge buffers usually achieve a
higher performance. Several researchers have proposed the use of edge buffers for
multicomputer networks [22, 25].
The restriction of buffer allocation, although it avoids deadlock, can increase
traffic jams, especially in heavily loaded networks. In order to avoid congested
regions of the network, an adaptive routing algorithm can be used. Adaptive
strategies have been shown to outperform deterministic strategies in store-and-
forward switching [5], in packet-switched communications [24, 35] and in wormhole
switching [11, 12].
When adaptive routing is used, deadlocks can be avoided in virtual cut-through
and store-and-forward switching by misrouting packets in the presence of conges-
tion. This technique, known as deflection or hot-potato routing [20], requires the
use of non-minimal paths. Examples of deflection routers for virtual cut-through
networks can be found in [29, 17, 26, 27]. This mechanism relies on the existence
of as many input channels as output channels in each node. Incoming packets will
always find a free output channel from the switch, sending packets away from the
destination if necessary. If the only free output channel is the one connecting to local
memory, the packet is buffered in the node. As mentioned above, this mechanism
requires the use of misrouting, thus wasting channel bandwidth when the network is
heavily loaded. Additionally, livelock freedom is only guaranteed in a probabilistic
manner [27]. However, peak values for packet latency are not excessively high.
Other proposals use an injection limitation strategy based on buffer occupancy.
The ring protocol [37] prevents the injection of a new packet into a node of a ring if
it fills the local queue. Thus, at least one packet from the previous node is able to
advance. This mechanism can be easily generalized for topologies with Hamiltonian
paths.
The most common way to prevent deadlock consists of eliminating cyclic dependencies
in the use of resources. Preventing cyclic dependencies between resources
is a sufficient condition for deadlock avoidance. However, it is too restrict-
ive. More efficient routing algorithms can be obtained by allowing cyclic dependencies
between resources. Pifarre et al. [33, 34] proposed a theory for the design of
deadlock-free adaptive routing algorithms in packet switched networks with central
queues. Starting from an acyclic queue dependency graph, they showed how to
develop fully adaptive routing algorithms without producing deadlock.
Simultaneously, a similar theory was proposed by us for wormhole switching [10,
11] and store-and-forward switching with edge buffers [10]. This theory proposes
sufficient conditions to verify that an adaptive algorithm is deadlock-free, even
when there are cyclic dependencies between channels. We also proposed two design
methodologies. The first one supplies fully adaptive routing algorithms and it is
very similar to the one proposed in [33, 34].
Cypher and Gravano [6] proposed a necessary condition for deadlock-free adaptive
routing in packet switched networks with central queues. They showed that an
adaptive deadlock-free packet routing algorithm can always be restricted, obtaining
an oblivious deadlock-free routing algorithm. This is not a sufficient condition, as
will be seen in section 4.5.
More recently, we proposed a necessary and sufficient condition for deadlock-free
routing in networks using wormhole switching [13]. Although this theory supplies
sufficient conditions for deadlock-freedom when it is applied to virtual cut-through
and store-and-forward switching, more flexibility can be obtained by considering
the behavior of those switching techniques. Additionally, the theory proposed in
[13] only considers the current and destination nodes while computing the routing
algorithm. This is acceptable for wormhole switching because most routing
algorithms using edge buffers can be defined in this way. However, routing algorithms
using central queues usually require information about the queue containing
the packet to be routed.
In this paper, we propose a necessary and sufficient condition for deadlock-free
routing in virtual cut-through and store-and-forward switching. This theory is valid
for networks using either central buffers or edge buffers. Also, the buffer containing
the packet is considered by the routing algorithm. As we will see, the deadlock freedom
properties of the whole network can be derived from the properties of a subset
of buffers. Thus, the remaining buffers can be used without any restriction. This
flexibility will allow us the definition of a design methodology that automatically
supplies deadlock-free fully adaptive routing algorithms. Also, this methodology
supports both, minimal and non-minimal routing algorithms. By contrary, the
methodology proposed in [11] for wormhole switching requires a verification step.
Usually, non-minimal routing algorithms do not pass the verification step. As in
[11], this methodology is restricted to routing functions that only consider the current
and destination nodes. As will be seen, it makes no sense for other definitions
of the routing function.
We introduce the new theory and the new kinds of dependency in an informal
way in section 3. Section 4 proposes the new theory formally. Section 5 proposes a
design methodology, giving some application examples in section 6. Finally, some
conclusions are drawn.
3 Informal description
This section is organized as follows: First, we informally define the concept of
dependency between resources. Then, we introduce the difference between deterministic
and adaptive routing regarding deadlocks, defining routing subfunction
informally. Later, we summarize the basic idea for our previous theory of store-
and-forward routing. Then, we present the basic idea for the new theory, using an
example. Moreover, we introduce the different kinds of resource dependency that
will be defined in the next section. Finally, we briefly consider the existence of
deadlocked configurations that cannot be reached.
Channels and buffers are the routing resources of an interconnection network.
Deadlocks arise because packets hold resources while requesting other resources
that will never be granted. While a packet is moving, resources are dynamically
reserved and released. The critical resources are the ones held by blocked packets.
When a packet is holding a resource, and it requests the use of another resource,
there is a dependency between them. At a given node, a packet may request the
use of several resources, then selecting one of them (adaptive routing). Every
requested resource produces a dependency because it will be selected when the
remaining resources are busy.
A network can use either edge buffers associated with channels or central queues.
In the first case, a blocked packet occupies a channel and its associated buffer,
producing dependencies between channels. In the second case, a blocked packet
occupies a buffer in a central queue, producing queue dependencies. In both cases,
a blocked packet is stored in one buffer. Thus, it is possible to use the same
model to analyze both kinds of networks. So, unless explicitly stated, we will
indistinctly refer to the dependencies between edge buffers or central queues as
resource dependencies or simply dependencies. Also, we will indistinctly refer to
edge buffers and central buffers as buffers. A set of one or more buffers with a
FIFO policy will be referred to as a queue.
With deterministic routing, packets have a single routing option at each node.
Thus, it is necessary to remove all the cyclic dependencies between resources to
prevent deadlocks. Otherwise, packets may indefinitely hold some buffers while
waiting for other buffers that are held by other packets. When adaptive routing
is considered, packets usually have several choices at each node. Even if some of
those routing choices are involved in cyclic dependencies, packets can use alternative
resources to break deadlocks. Thus, it is not necessary to eliminate all the
cyclic dependencies, provided that every packet can always find a path toward its
destination whose buffers are not involved in cyclic dependencies.
For virtual cut-through and store-and-forward switching with edge buffers, it
suffices with the existence of a connected channel subset C 1 whose channels are
not involved in cyclic dependencies [10]. If cyclic dependencies are not allowed
between channels belonging to C 1 , then we guarantee that packets will not block
indefinitely holding those channels. If the routing function is able to deliver all the
packets using only channels belonging to C 1 (connected channel subset), deadlock
freedom is guaranteed regardless of how packets are routed across the remaining
channels. Similar considerations are also valid for networks using central queues.
The channels belonging to C 1 will be referred to as escape channels, escape paths or,
in general, escape resources. The routing function restricted to use only the escape
resources will be referred to as routing subfunction. A routing subfunction is only a
mathematical tool to restrict our attention to a subset of resources. Routing is not
restricted at all. When a routing subfunction is considered, only the dependencies
between the resources supplied by it are considered.
There are two important issues about the theory we proposed in [10] for store-
and-forward switching. When a packet uses an escape resource at a given node, it
can freely use any of the available resources supplied by the routing function at the
next node. Also, when a packet is blocked because all the alternative resources are
busy, it is not required to wait until a predetermined resource is available. Instead,
it is repeatedly routed until any of the resources supplied by the routing function
becomes free. Both issues are important, because they considerably increase routing
flexibility, especially when the network is heavily loaded. These considerations also
apply to the theory proposed in this paper.
In [10], a given resource was either supplied by the routing subfunction for
all the destinations or not supplied at all. Labeling each resource as belonging
or not belonging to the set of escape resources is simple, but the result is only a
sufficient condition for deadlock-free adaptive routing. In this paper, we go one step
further by conditionally labeling each resource as escape resource depending on the
destination of the packet. By doing so, we achieve the maximum flexibility in the
definition of the routing subfunction, but resource dependencies must be carefully
analyzed, as illustrated in the following example.
Consider a unidirectional ring with four nodes denoted
two channels connecting each pair of adjacent nodes, except nodes n 3 and n 0 that
are linked by a single channel. Let c Ai
the outgoing channels from node n i . The routing algorithm uses edge buffers and
can be stated as follows: If the current node n i is equal to the destination node
deliver the packet. Otherwise, use either c Ai ; 8j 6= i or c Hi ; 8j ? i. In other
words, c Ai channels can be used to forward packets to all the destinations. However,
c Hi channels can only be used if the destination is higher than the current node.

Figure

1 shows the network.
In this routing algorithm, we cannot easily identify a subset of channels that
do not produce cyclic dependencies and allow packets to reach all the destinations.
c Hi channels alone do not allow packets to reach node n 0 . c Ai channels have cyclic
dependencies between them. Thus, we define the escape paths by using part of the
routing capabilities of c Ai channels. More precisely, c Ai channels are used as escape
paths when the packet destination is lower than the node currently holding the
packet. c Hi channels are also used as escape paths. This definition allows packets
to reach any destination because they will either use c Hi or c Ai channels depending
on whether the destination node is higher or lower than the current node.
Restricting c Ai channels to be used as escape paths only when the packet destination
is lower than the current node, breaks the cyclic dependencies between c Ai
channels because c A0 is not an escape channel for any destination. Effectively, there
c
c
c
c
c
c
c
A3

Figure

1: Network for the example
is not any node lower than n 0 .
When we focus on the resources supplied by the routing subfunction some dependencies
are easy to detect. Suppose that a packet destined for node n 2 has
reserved channel c H0 , and then it requests channel c H1 to reach node n 2 . Both
channels, c H0 and c H1 , are supplied by the routing subfunction for packets destined
for node n 2 . Thus, there is a dependency from channel c H0 to channel c H1 . We will
refer to this kind of dependency as direct dependency.
However, some dependencies are difficult to detect. Suppose that a packet
destined for node n 3 has reserved channel c A1 , and then it requests channel c H2 to
reach node n 3 . Obviously, there is a dependency from channel c A1 to channel c H2 .
However, c A1 is not supplied by the routing subfunction for packets destined for node
. So, the question is: When we restrict our attention to the resources supplied
by the routing subfunction, do we consider the dependency from c A1 to c H2 ? The
answer must be positive because c A1 is supplied by the routing subfunction for other
destinations. Thus, it is an escape resource. If we do not consider this dependency,
some packets requesting c A1 to escape from cycles may block forever, as we will
see in section 4.5 using an example. We will refer to this kind of dependency as
direct cross dependency. It is important to note that both kinds of dependency are
particular cases of the same definition. Although this view slightly differs from the
one presented in [13] for wormhole switching, the concept is identical. We believe
that the view presented in this paper is easier to understand.
Let us consider the opposite case. Suppose that a packet destined for node n 3
has reserved channel c H1 , and then it requests channel c A2 to reach node n 3 . In
this case, there is also a dependency from channel c H1 to channel c A2 . However,
c A2 is not requested by the routing subfunction for packets destined for node n 3 . In
other words, c A2 is not required as an escape resource for packets destined for node
Thus, we will not consider this dependency when the behavior of the routing
subfunction is analyzed.
Finally, we consider whether a static analysis of the network is enough. A deadlocked
configuration is an assignment of a set of packets to each queue such that
no packet is able to advance. A configuration describes the state of an interconnection
network at a given time. In some cases, a deadlocked configuration cannot be
reached by routing packets starting from an empty network. This situation usually
arises when two or more packets require the use of the same resource at the same
time to reach the configuration. A configuration that can be reached by routing
packets starting from an empty network is reachable or routable [6]. If all the configurations
are reachable then a static analysis of the network is enough. Otherwise,
the dynamic evolution of the network should be considered. This dynamic analysis
is not required to prove that a routing function is deadlock-free. Reachability only
affects necessary conditions for deadlock-free routing.
If the routing algorithm only considers the current and destination nodes, all
the configurations are reachable, as will be seen later. However, if it also considers
the buffer where the packet is stored then some configurations may be unreachable.
As far as we know, nobody has proposed unreachable configurations for common
topologies. Thus, in practice, we can consider that all the configurations are reach-
able, and a static analysis of the network is enough. Reachability remains as a
theoretical open problem for some definitions of the routing function.
4 Formal theory
This section develops the theoretical background for the design of deadlock-free
adaptive routing algorithms for virtual cut-through and store-and-forward networks
with central buffers or edge buffers. Without loss of generality, we will mainly
focus on virtual cut-through to avoid mixing different terminology and assumptions.
However, the theoretical results are valid for both flow control techniques.
4.1 Router model
Before proposing the theory, we present two simple router models, highlighting the
aspects that may affect deadlock avoidance. More precise assumptions are given in
the next subsection.

Figure

2 shows the router model for networks with edge buffers. Each router
consists of a switch, an address decoder that implements the routing algorithm,
and several channels. The local processor sends and receives packets through the
channels connecting it to the switch.
The switch allows multiple packets to traverse a node simultaneously without
interference. Blocking switches are also supported, provided that the scheduling
policy does not produce packet starvation.
The address decoder configures the switch, determining the output channel for
each packet as a function of the destination node, the current node and/or the
current queue, and the output channel status. The address decoder can only process
mux
mux
Switch
Address
decoder
mux
mux
mux
mux
From/to local processor
Physical
input
Physical
output
Virtual channel
Input buffers Output buffers

Figure

2: Router model
one packet header at a time. If there is contention for the address decoder, access is
round robin. When a packet gets the address decoder, but cannot be routed because
all the alternative output channels are busy, it must wait in the corresponding
input queue until its next turn. By doing so, the packet will get the first channel
that becomes free, thus increasing routing flexibility. Configurations with as many
address decoders as input channels are also supported, provided that they are linked
by an arbiter with round robin policy.
Physical channels are bidirectional full-duplex. Physical channels may be split
into virtual channels. Virtual channels are assigned the physical channel cyclically,
only if they are ready to transfer a flit (demand-slotted round robin). Each virtual
channel has two buffers at the input side. A large buffer with capacity for one
or more packets is required to store packets and remove them from the network
whenever no output channel is available. A channel will only accept a new packet
if there is enough buffer space to store the whole packet. Also, a small buffer with
capacity for a few flits is used to speed up packet pipelining when the packet is
not blocked. This small buffer does not affect deadlock avoidance, because blocked
packets are always moved to the large buffer. So, in what follows, we will not
consider the small buffers. Similarly, small output buffers may be used to increase
throughput when virtual channels are used but those buffers will not be considered
for deadlock avoidance.
If the network uses central queues instead of edge buffers, the router model is
similar to the one described above. In this case, a few central queues deep enough
to store one or more packets are used. As above, a channel will only accept a new
packet if there is enough buffer space to store the whole packet. Buffer space must
be reserved before starting packet transmission, thus preventing other channels
from reserving the same buffer space. An arbiter is needed to handle simultaneous
requests. As above, a small buffer associated with each channel may be used to
speed up packet pipelining when the packet is not blocked. Small buffers do not
affect deadlock avoidance and they will not be considered.
4.2 Assumptions
The basic assumptions are very similar to the ones proposed in [11], modified
for virtual cut-through. Messages may be split into packets. As packets carry
information about their destination, the theory is valid for both, messages and
packets. Without loss of generality, we will only refer to packets. The assumptions
are the following:
1. A node can generate messages of arbitrary length destined for any other node
at any rate. Messages may be split into packets.
2. A packet arriving at its destination node is eventually consumed.
3. Virtual cut-through or store-and-forward switching is used.
4. Each channel has a single queue associated with it, allowing the storage of a
finite number of packets. Alternatively, each node has a few central queues
with capacity for a finite number of packets. A channel will only accept a
new packet if there is enough buffer space in the corresponding queue to
store the whole packet. Buffer space must be reserved before starting packet
transmission.
5. The address decoder may arbitrate between packets requesting it, but may
not choose among waiting packets.
6. The route taken by a packet depends on its destination, the current node
and the status of the requested channels or queues (free or busy). The queue
containing the packet can also be considered. However, some theoretical
results are only valid for routing algorithms that do not consider the current
queue. At a given node, an adaptive routing function supplies a set of channels
or queues. A selection from this set is made based on the status of those
resources. This selection is performed in such a way that a free resource (if
any) is supplied.
7. When several packets are waiting because all the resources supplied by the
routing function are busy, they are routed following a round-robin strategy,
thus preventing starvation.
8. The routing function may allow packets to follow non-minimal paths.
9. All the configurations can be reached by routing packets starting from an
empty network.
4.3 Definitions
Before proposing the theorems, some definitions are needed. Most differences
between these definitions and the ones proposed in [11] for wormhole switching
arise because the routing function used in this paper also considers the queue containing
the packet. A similar extension can be done for the theories proposed in
[11, 13, 14]. Additionally, definitions and theorems consider both, central and edge
queues.
network I is a strongly connected directed mul-
tigraph, G(N;C). The vertices of the multigraph N represent the set of processing
nodes. The arcs of the multigraph C represent the set of communication
channels. More than a single channel is allowed to connect a given pair of nodes.
The source and destination nodes of channel c i are denoted s i and d i , respectively.
Each node has one injection queue and one delivery queue. The sets of injection
and delivery queues are denoted Q I and QD , respectively. Let QN be the set of
standard queues, which includes all the queues in the network except injection and
delivery queues. Also, Q
Each queue q can be a central queue at
node n i if central buffers are used or it can be associated with a channel c i if edge
buffers are used. In this case, we will consider that q i is at node d i . For the sake of
simplicity, an enumeration of arbitrary queues is denoted instead of
. An enumeration does not imply any queue ordering.
F be the set of valid queue status, fullg.
Definition 3 An adaptive routing function R :
P(QND ) is the power set of QND , supplies a set of alternative edge or central
queues to send a packet from the current queue q c to the destination node n d ,
g. In general, p will be less than the number of queues that
can be reached from the current queue to restrict routing and obtain deadlock-free
algorithms. As a particular case, defines a deterministic
routing function. If the current queue q c is at destination node n d then the routing
function can only supply a delivery queue at current node. Defining the domain of
the routing function as Q IN \Theta N is more general than considering only the current
and destination nodes. Thus, all the theoretical results for routing functions defined
on Q IN \Theta N are also valid for routing functions defined on N \Theta N . Some specific
results for these functions will be presented in section 4.5.
Definition 4 A selection function selects a non-full queue
(if any) from the set supplied by the routing function. From the definition, S takes
into account the status of all the queues belonging to the set supplied by the routing
function. The selection can be random or based on static or dynamic priorities.
It must be noticed that starvation is prevented using a round-robin strategy when
several packets are waiting for the router, according to assumption 7. The selection
function will only affect performance.
configuration is an assignment of a set of packets to each queue.
The number of packets in the queue q i is denoted size(q i ). The destination node for
a packet p j will be denoted dest(p j ). If the first packet in the queue q i is destined
for node n d , then head(q configuration is legal iff
such that q m 2
For each queue, the capacity is not exceeded and all the packets stored in
the queue (if any) have been routed from some injection queue using the routing
function.
Definition 6 A deadlocked configuration for a given interconnection network I
and routing function R is a nonempty legal configuration verifying the following
In a deadlocked configuration no packet has already arrived at its destination
node. Packets cannot advance because all the alternative queues supplied by the
routing function are full. No condition is imposed on empty queues.
Definition 7 A routing function R for an interconnection network I is deadlock-free
iff there is not any deadlocked configuration for that routing function on that
network.
routing function R for a given interconnection network I is connected
iff for any legal configuration
such that q m 2
In other words, it is always possible to establish a path for every packet from its
current queue to its destination node (delivery queue). Notice that the configuration
must be legal. Otherwise, the routing function may not supply any queue.
As will be seen, it is possible to prove deadlock freedom by focusing on the
behavior of a restricted routing function. This concept is formalized by the following
definition:
Definition 9 A routing subfunction R 1 for a given routing function R is a routing
function defined on the same domain as R that supplies a subset of the queues
supplied by R
The set of all the queues supplied by R 1 is
As a particular case, given a queue subset QND1 ' QND one can always construct
a routing subfunction R 1 by applying the following relationship:
Expression (1) is more general than expression (2) because it allows us to remove
a queue from R 1 only for some destinations.
Given an interconnection network I, a routing function R and a
pair of queues q there is a direct dependency from q i to q j iff there exists
a legal configuration with packets stored in q i and
That is, q j can be requested by packets stored in q i for some legal configuration.
If routing subfunctions are not considered, this is the only kind of dependency
between resources.
When a routing subfunction is considered, we only consider the queues supplied
by it and the dependencies between them, as indicated in the next definition.
Definition 11 Given an interconnection network I, a routing function R, a routing
subfunction R 1 and a pair of queues q there is a dependency from q i
to q j iff there exists a legal configuration with packets stored in q i and
This definition is identical to definition 10 except that it is restricted to queues
supplied by R 1 . It considers all the possible dependencies between resources supplied
by a routing subfunction. However, the definition of routing subfunction
produces two particular cases with subtle differences between them. As the configuration
with packets stored in q i is legal then
configuration then the dependency is referred
to as direct dependency. If for all the legal configurations q
then the dependency is referred to as direct cross dependency. Notice that
supplied by R 1 for some other destinations.
Direct and direct cross dependencies are particular cases of the same definition.
The difference between them can be informally viewed as follows: If the packet
stored in q i has been routed there by using queues supplied by R 1 (the configuration
is legal for R 1 ), the dependency is referred to as direct dependency. If the
packet stored in q i cannot be routed there by using queues supplied by R 1 (the
configuration is legal for R but not for R 1 ), the dependency is referred to as direct
cross dependency. This view complements the one presented in section 3. When a
routing subfunction is defined by using expression (2) there is not any direct cross
dependency because this kind of dependency requires that a queue is supplied by
the routing subfunction only for some destinations.
Direct dependencies are the only ones that would exist if R 1 were a routing
function instead of being a routing subfunction of R. Thus, these dependencies are
identical to the ones proposed in definition 10 for routing functions. So, we use the
same name.
The additional kinds of dependency defined in [13, 14] only exist in wormhole
networks. Resource dependencies can be analyzed by using a graph to represent
them. We define two graphs.
Definition 12 A resource dependency graph D for a given interconnection network
I and routing function R, is a directed graph, G(Q;E). The vertices of D are
the queues of I. The arcs of D are the pairs of queues (q such that there is a
direct dependency from q i to q j .
An extended resource dependency graph DE for a given interconnection
network I and routing subfunction R 1 of a routing function R, is a directed
The vertices of DE are the queues supplied by the
routing subfunction R 1 for some destinations. The arcs of DE are the pairs of
queues such that there is either a direct or direct cross dependency from q i
to q j . It must be noticed that the extended resource dependency graph has been
redefined with respect to both, [11] and [13, 14].
4.4 Necessary and sufficient condition
Two theorems are proposed. The first one simply states that techniques based
on directed acyclic graphs can also be applied to adaptive routing functions. The
second theorem allows us the design of adaptive routing functions with cyclic dependencies
in their resource dependency graph. It supplies a necessary and sufficient
condition for deadlock avoidance. For each theorem, a sketch of the proof as
well as the full proof are given.
Theorem 1 A connected and adaptive routing function R for an interconnection
network I is deadlock-free if there are no cycles in its resource dependency graph
D.
Proof As the resource dependency graph for R is acyclic, it is possible
to establish an order between the queues of Q. As R is connected, the minimal
queues in that order are also delivery queues. Suppose that there is a deadlocked
configuration for R. Let q i 2 Q be a full queue such that there is not any full queue
less than q i . If q i is a delivery queue, then the packet at the queue head has reached
its destination and there is no deadlock. Otherwise, using the queues less than q i ,
the packet at the queue head of q i can advance and there is not any deadlock.2
Proof: Suppose that there are no cycles in D. Then, one can assign an order to
the queues of Q so that if (q . Consider the queue(s) q i such
that
Such a queue q i is minimal in the order. Let us prove that it is a delivery queue.
If it were not a delivery queue, as the routing function is connected, for any legal
configuration such that
As the configuration is legal then (q contrary to the assumption that
q i is minimal. Thus, q i is a delivery queue.
Suppose that there is a deadlocked configuration for R. Let q i 2 Q be a full
queue such that there is not any full queue less than q i . If q i is minimal, it is also a
delivery queue and the packet at the head of q i is not blocked. If q i is not minimal
then
Thus, the packet at the head of queue q i is not blocked, and there is no
deadlock.2
Theorem 2 A connected and adaptive routing function R for an interconnection
network I is deadlock-free iff there exists a routing subfunction R 1 that is connected
and has no cycles in its extended resource dependency graph DE .
Proof The case R supply a
subset of the queues supplied by R. As the extended resource dependency graph
for R 1 is acyclic, it is possible to establish an order between the queues of QND1
(queues supplied by R 1 for some destination). As R 1 is connected, the minimal
queues in that order are also delivery queues. Suppose that there is a deadlocked
configuration for R. There are two possible cases:
a) No queue belonging to QND1 is full. As R 1 is connected, packets stored
at queue heads can be routed using queues belonging to QND1 and there is no
deadlock.
Queue requested by
Alternative queue (not requested by R1)

Figure

3: Filling the cycle
b) Some queues belonging to QND1 are full. Let q i 2 QND1 be a full queue such
that there is not any full queue less than q i . Again, there are two possible cases:
b1) If q i is minimal (delivery queue) then the packet at the queue head is not
blocked and there is no deadlock.
b2) If q i is not minimal, no queue of QND1 less than q i will have a full queue.
Thus, the packet at the queue head of q i can be routed because R 1 is connected
and there is no deadlock.
Suppose that R is deadlock-free. Thus, there is not any deadlocked config-
uration. We have to construct a connected routing subfunction R 1 without cycles
in its extended resource dependency graph DE .
The basic idea for the proof is the following: First, we define a connected
routing subfunction R 1 that uses as few queues belonging to cycles of D as possible.
Using queues belonging to cycles of D does not imply that the resulting routing
subfunction will have cyclic dependencies between queues, provided that it only
uses a subset of the queues belonging to each cycle of D. Then, we proceed by
contradiction. We assume that there is a cycle in the extended resource dependency
graph for R 1 , showing that it is possible to redefine R 1 in such a way that the cycle
is broken.
Let us describe this idea in more detail. The definition of R 1 is iterative. We
start by including in R 1 all the queues that do not belong to any cycle of D. If R 1
is not connected yet, we iteratively add queues to R 1 until it is connected. In each
iteration, we consider a single queue q j belonging to a cycle of D. q j is added to
R 1 to route packets from a queue q i to a node x if the previous definition for R 1
did not offer any path from q i to x and q j is supplied by R to route packets from
q i to x following a shortest (possibly minimal) path.
us assume that there is a cycle in the extended queue dependency graph
for R 1 . We fill the queues of the cycle trying to build a deadlocked configuration,
in such a way that the next queue requested by each packet is supplied by R 1 (see
Fig. 3). The resulting configuration is legal because the definition of dependency
requires legal configurations. As R is deadlock-free, it will offer an alternative queue
q k for the packet stored in some queue q i . Thus, we redefine R 1 by eliminating q j and
by adding q k for the packet destination. By repeating this process for all the legal
packet destinations it is possible to break the dependency from q i to q j , contrary
to the assumption that there is a cycle in the extended resource dependency graph
Proof: ( Suppose that there exists a routing subfunction R 1 of the routing
function R and that R 1 is connected and there are no cycles in DE . If R 1 (q;
D. Thus, there is not any cycle in D and R
is deadlock-free by theorem 1. Otherwise, R 1 (q;
x). As there are no cycles in DE , one can assign
an order to the queues of QND1 so that if (q . Consider the
Such a queue q i is minimal in the order. Let us prove that it is a delivery queue.
If it were not a delivery queue, as the routing subfunction R 1 is connected, for any
legal configuration such that
As the configuration is legal then (q contrary to the assumption that
q i is minimal. Thus, q i is a delivery queue.
Suppose that there is a deadlocked configuration for R. There are two possible
cases:
a) No queue belonging to QND1 is full. Let q i 2 Q IN be a nonempty queue. As
R 1 is connected then
Also does not have a deadlock.
b) Some queues belonging to QND1 are full. Let q i 2 QND1 be a full queue such
that there is not any full queue less than q i . Again, there are two possible cases:
As shown above, it is also a delivery queue and thus, the
packet at the head of the queue is not blocked.
not minimal. Thus
Taking into account that R 1 is connected
As every deadlocked configuration is legal, then
and R does not have any deadlock.
Suppose that R is deadlock-free. Thus, there is not any deadlocked configur-
ation. Now, we have to construct a routing subfunction, showing that it is connected
and it has no cycles in its extended resource dependency graph DE . There are two
possible cases:
a) If the resource dependency graph D for R is acyclic, then we define
Obviously, R 1 is connected and it has no cycles in DE .
b) If D is not acyclic, let Q a ae Q be the subset of queues that do not belong to
any cycle in D. We define
Now, there are two possible cases:
b.1) If R 1 is connected, it is obvious that it has no cycles in DE .
b.2) If R 1 is not connected, we start from the current definition for R 1 , adding
queues to it from QND \Gamma Q a until R 1 is connected. This is an iterative process. Let
SP (q; x) be the set of queues supplied by R(q; x) belonging to a shortest path from
q to x. A shortest path will only be minimal if R supplies at least one minimal
path from q to x. In each iteration, a single queue q j 2 QND \Gamma Q a is considered,
redefining R 1 as follows:
R (p+1)
R (p)
where R (p)
1 is the routing subfunction R 1 in the iteration p. In other words, q j is
added to R 1 to route packets from q i to x if the previous definition for R 1 did not
offer any path from q i to x and q j is supplied by R to route packets from q i to x
following a shortest path. Otherwise, R 1 remains unaltered. The iterative process
will finish because R is connected. Thus, after the iterative process, R 1 is also
connected. Let QND1 be the set of queues supplied by R 1 for some destination.
Now, we have to prove that there are no cycles in the extended resource dependency
graph DE for R 1 , possibly redefining it again. Restricting routing cannot
produce new cyclic dependencies. Thus, only a cycle in the resource dependency
graph D for R may induce a cycle in DE .
We proceed by contradiction. We assume that R 1 has a cycle in its extended
resource dependency graph, showing that it is possible to redefine it so that the
new routing subfunction is connected and it has no cycles in its extended resource
dependency graph. Suppose that there is a cycle in DE . Let Q
be the subset of queues that form the cycle in DE . Without loss of generality, q i+1
will always denote a queue requested by packets stored in q i . Let us consider the
dependency from q 1 to q 2 . We fill the queue q 1 with packets destined for a legal
destination requiring the use of q 2 . We proceed in the same way with the remaining
dependencies.
Let Q d be the set formed by all the queues q i 2 QND1 such that
There is a sequence of dependencies (a path in DE ) from every queue in Q d to
some queue in Q c . We also fill every queue q i 2 Q d with packets destined for a legal
destination requiring the use of the next queue in the sequence of dependencies.
We have filled the queues in Q c [ Q d in such a way that
As R is deadlock-free, all the packets in the above described configuration must
be able to advance. If R only supplies paths for packets stored in queues belonging
to Q d , the packets in the cycle (stored in queues belonging to Q c ) will never advance.
Thus, R must supply paths for packets stored in queues belonging to Q c
QND such that
Obviously,
these queues are full. Taking into account
the definition for R 1
Otherwise, R 1 would offer two different paths to reach head(q i ). Additionally,
there is no dependency from q j to any other queue belonging to Q c [Q d . Otherwise,
it would be full. We can redefine R 1 by including q j and eliminating
q i+1 to route packets from q i toward head(q i ). Obviously, R 1 is still connected.
According to the new definition for R 1
thus breaking the dependency from q i to q i+1 when the packet destination is
Similarly, we can fill the cycle with other configurations identical to the
one described above, except that the packet stored in q i is now destined for other
nodes. Once we have tried all the legal destinations that require crossing q i+1 , we
have broken the dependency from q i to q i+1 , contrary to the assumption that there
was a cyclic dependency in DE . Thus, the extended resource dependency graph
DE for R 1 is acyclic and the theorem holds.2
Corollary 1 A connected and adaptive routing function R for an interconnection
network I is deadlock-free if there exists a subset of queues QND1 ' QND such
that the routing subfunction R 1 (q;
connected and has no cycles in its resource dependency graph D 1 .
Proof: Taking into account the definition of R 1 , there is not any direct cross
dependency between the queues belonging to QND1 . Thus, the resource dependency
graph for R 1 is identical to the extended resource dependency graph. By theorem 2,
R is deadlock-free.2
There are some interesting considerations:
1. Theorem 2 is identical to the necessary and sufficient condition proposed
in [13, 14] for wormhole switching, except that the routing function is not
required to supply at least one minimal path and be coherent. A routing
function R is coherent if for every path P that can be established by R,
all subpaths of P are also paths of R. Coherence is required in wormhole
switching because a blocked packet may occupy several channels. Thus, a
packet may visit a node twice and request a channel it is still occupying.
Also, it must be noticed that the extended resource dependency graph defined
in this paper only contains direct and direct cross dependencies.
2. If some legal configurations are unreachable then assumption 9 does not hold,
and definition 7 becomes only a sufficient condition. As a consequence, theorem
also becomes a sufficient condition. However, if the routing function
only considers the current and destination nodes to compute the path then
every legal configuration is also reachable. Effectively, as the routing function
has no memory of the path followed by each packet, we can consider that a
packet stored in a channel queue was generated by the source node of that
channel. Thus, there is not any other packet requiring the use of that channel
at the same time to reach the configuration. Similar considerations are
applicable to routing functions using central queues.
3. Corollary 1 gives a very flexible way to define deadlock-free adaptive routing
functions. If a routing function satisfies the conditions proposed by it, it
does not matter how packets are routed through queues not belonging to
QND1 . Those packets are allowed to use all the minimal and non-minimal
paths. However, when non-minimal paths are used, livelock-freedom should
be guaranteed. This result is much more flexible than the one previously
obtained for wormhole switching [13, 14]. The reason being that packets
occupy a single buffer when they are blocked. As a consequence, dependencies
only exist between queues in the same node or in adjacent nodes.
4. The routing subfunction R 1 can be adaptive.
4.5 Routing functions defined on N \Theta N
In this section we consider routing functions defined as follows:
Definition 14 An adaptive routing function R : N \Theta N ! P(QND ), supplies a
set of alternative edge or central queues to send a packet from the current node n c
to the destination node n d , R(n c ; n d g.
Routing functions defined on N \Theta N have no memory of the path followed
by the packet. The remaining definitions proposed in section 4.3 can be modified
accordingly. In particular, legal configurations and routing subfunctions are defined
as follows:
Definition 15 A configuration is legal iff
such that q
Definition routing subfunction R 1 for a given routing function R is a routing
function defined on the same domain as R that supplies a subset of the queues
supplied by R
The following theorem is specific for routing functions defined on N \Theta N . This
theorem will allow us the definition of a very flexible design methodology for adaptive
routing algorithms.
Theorem 3 A connected and adaptive routing function R for an interconnection
network I is deadlock-free if there exists a subset of queues QND1 ' QND such that
the routing subfunction R 1 connected and
deadlock-free.
Proof: Suppose that there exists a queue subset QND1 ' QND that defines a
routing subfunction R 1 that is connected and deadlock-free. If QND the
proof is trivial. Otherwise QND1 ae QND .
Suppose that there is a deadlocked configuration for R. There are two possible
cases:
a) No queue belonging to QND1 is full. Let q i 2 Q IN be a nonempty queue. As
R 1 is connected then
Also does not have a deadlock.
b) Some queues belonging to QND1 are full. As there is a deadlocked configuration
for R
A queue belonging to QND1 is supplied by R 1 for the same destinations as it is
supplied by R. Thus, if we restrict our attention to queues belonging to QND1 , the
configuration is also legal for R 1 . Let Taking into account that
Thus, considering the queues belonging to QN1 , there is a deadlocked configuration
contrary to the initial assumption. Thus, R must be deadlock-free.2
If the routing function were defined on Q IN \Theta N then it would not be possible to
guarantee that a legal configuration for R is also legal for R 1 . The definition of legal
configuration given by definition 5 requires the existence of a sequence of queues
supplied by the routing function. If some of those queues are
supplied by R but not for R 1 , then the configuration is legal for R but not for R 1 .
Also, if we used the definition of routing subfunction given by expression (3)
for theorem 3, the resulting theorem would not be valid. Again, the reason is that
a legal configuration for R is not necessarily a legal configuration for every routing
subfunction defined as R 1 . The following example
explains this issue more clearly.
Consider a 2D-mesh with edge buffers and a single physical channel connecting
each pair of nodes. The routing function R is defined on N \Theta N . It forwards packets
following any minimal path. This routing function is not deadlock-free. Figure 4
shows a deadlocked configuration. Dotted incomplete boxes represent nodes of a
3 \Theta 3 mesh. Dashed boxes represent switches. Solid boxes represent packet buffers
(queues). The number inside each buffer indicates the packet destination. Solid
arrows indicate the channel requested by the packet at the queue head. As packets
are allowed to follow all the minimal paths, there are cyclic dependencies between
channels. Additionally, there is no alternative path for the packets in the figure
because packets are only allowed to follow minimal paths.

Figure

4: Deadlocked configuration for R
Consider a routing function R 1 that uses dimension-order routing (XY-routing).
Obviously, R 1 (x; y) ' R(x; y) 8x; y 2 N . Thus, R 1 is a routing subfunction of
R. It is well known that R 1 is connected and deadlock-free. However, R is not
deadlock-free. Theorem 3 cannot be applied because there is no queue subset
QND such that R 1 . According to this
definition of routing subfunction, channels must be used in the same way by R and
they belong to QND1 . However, Y channels can be used by R to forward
packets whose destination node is not in the same column as the current node, and
R 1 can only use Y channels to forward packets whose destination node is in the
same column as the current node.
This example also shows that the existence of an oblivious deadlock-free routing
subfunction according to expression (3) does not imply that the routing function
is deadlock-free. Thus, the necessary condition for deadlock-free adaptive routing
proposed in [6] is not a sufficient one.
The above described example does not invalidate theorem 2. Figure 5 shows
the extended resource dependency graph for R 1 on a 3 \Theta 3 mesh. Black circles
represent channels. Channel from node i to node j is denoted cij. Solid arrows
represent direct dependencies. Dashed arrows represent direct cross dependencies.
The graph contains cycles. It can be seen that there are direct cross dependencies
from Y channels to X channels that close the cycles.
In this section we propose a methodology for the design of deadlock-free fully
adaptive routing algorithms. It is restricted to routing functions defined on N \Theta
N . As we will see, this methodology makes no sense for routing functions that
consider the current queue. It starts from a previously proposed deterministic or
c67 c76 c87
c36
c54
c43

Figure

5: Extended resource dependency graph for R 1
partially adaptive routing algorithm. This methodology indicates a way to add
channels or central queues to an existing network, also deriving the new routing
function from the old one. It is similar to the first methodology proposed in [11]
for wormhole switching, the main difference being that the methodology we propose
here automatically supplies deadlock-free routing algorithms.
Methodology 1 This methodology supplies fully adaptive minimal and non-minimal
routing algorithms, starting from a previously proposed routing algorithm.
The steps are the following:
1. Given an interconnection network I 1 , define a connected deadlock-free routing
function R 1 for it. Let Q 1 be the set of queues at this point.
2. Split each physical channel into a set of (additional) virtual channels or add
a set of central queues. Let Q be the set of all the queues in the network. Let
Q xy be the set of queues belonging to a path (minimal or not) from node x
to node y that can be requested at node x. Define the new routing function
R as follows:
That is, the new routing function can use any of the new queues or, altern-
atively, the queues supplied by R 1 . The selection function can be defined in
any way. However, it is recommended to give a higher priority to the new
queues belonging to minimal paths.
establishes the starting point. We can use either a deterministic or a
partially adaptive routing function as the basic one. Step 2 indicates how to add
edge or central queues to the network and how to define a new fully adaptive routing
function from the basic one. Only one additional central queue per node or virtual
channel per physical channel are required for fully adaptive routing. As defined,
this methodology supplies non-minimal routing functions. It is possible to define
minimal routing functions by restricting Q xy to contain only the queues belonging
to minimal paths from x to y.
routing algorithms.
Proof: According to the definition for R
Thus, there exists a subset of queues Q 1 ae Q that defines a routing subfunction
R 1 that is connected and deadlock-free. Taking into account theorem 3, we can
conclude that R is deadlock-free. 2
The proposed methodology is very simple to apply. Some examples can be found
in [11] for a binary n-cube with wormhole switching. For the sake of completeness,
we will briefly present an example in section 6. The resulting routing algorithms
are the same for virtual cut-through and wormhole switching. The only difference
being that, for virtual cut-through switching, the routing function can be defined
in such a way that it also uses non-minimal paths. As shown above, the resulting
routing algorithms are always deadlock-free. It is not necessary to check that the
extended resource dependency graph is acyclic. Thus, this design methodology is
more flexible and much easier to apply than the one we proposed for wormhole
switching [11].
As defined, methodology 1 makes no sense for routing functions defined on
. This methodology extends the range of the routing function but not its
domain. If the domain is not extended, packets stored in the new queues cannot
be routed. However, if the domain of R is extended, the initial routing function
R 1 is modified. As an example, let us consider the positive hop algorithm [19].
This fully adaptive minimal routing algorithm uses central queues grouped into
classes. Every time a packet stored in a queue of class i crosses a channel, it
moves to a queue of class i + 1. This routing function requires the class of the
queue containing the packet to compute the next class to be used. However, it
has no memory of the previous path followed by the packet. Let Q 1 be the set
of queues at this point. Suppose that the positive hop algorithm is extended for
non-minimal routing by adding a new queue to each node so that the new queues
are used for fully adaptive non-minimal routing. Once the new queues have been
added, the positive hop algorithm does not work unless additional information is
carried in the packet header. Effectively, when a packet moves from a queue of
class i belonging to Q 1 to a new queue, and then it returns to another queue of
the routing function does not remember the previous class for this packet. In
summary, extending the domain of the routing function supplied by methodology 1
modifies the initial routing function. As a consequence, the methodology makes no
sense for routing functions defined on Q IN \Theta N .
6 Design examples
In this section, we present some examples of deadlock-free routing algorithms for
virtual cut-through and store-and-forward switching using edge buffers. Those
algorithms will be proved to be deadlock-free by using the theory proposed in
previous sections. First, we present a simple example using the design methodology
proposed in section 5. Then, we present a routing algorithm that is not deadlock-free
if wormhole switching is used.
Let us apply the design methodology proposed in section 5 to n-dimensional
meshes. For step 1 we use dimension-order routing. It is well known that this
routing function is connected and deadlock-free. For step 2, consider that each
physical channel c i has been split into two virtual channels, namely, a i and b i . Let
C 1 be the set of b channels. The algorithm obtained applying step 2 can be stated
as follows: Route using any of the a channels. If all of them are busy, route using
dimension-order routing on b channels. This routing function allows packets to
follow any minimal or non-minimal path. Of course, it is also possible to restrict
the use of a channels to minimal paths.
Let us consider a 2D-mesh without virtual channels using the north-last routing
function [18]. For the sake of simplicity, consider that only minimal paths are
allowed. Channels corresponding to north, east, south and west directions will be
denoted as N , E, S and W . The north-last routing function allows packets to
follow any minimal path with one exception: Packets are not allowed to turn after
using N channels. Thus, it is not fully adaptive. As shown in section 4.5, fully
adaptive routing without virtual channels may produce deadlocks. We are going to
add the minimum number of virtual channels to obtain a fully adaptive deadlock-free
routing function. Also, we will show that it is not deadlock-free if wormhole
switching is used.
Consider that N channels are split into two virtual channels, namely, N 1 and
After using N 1 channels, no turns are allowed. However, 90-degree turns are
allowed after using N 2 channels. The new routing function R is fully adaptive and
deadlock-free. Effectively, consider that C 1 is the subset containing N 1 , E, S and
channels. C 1 defines a routing subfunction R 1 identical to the north-last routing
2Requested channel
Reserved

Figure

Deadlocked configuration for R on a 3 \Theta 3 mesh using wormhole switching
function. It is easy to see that R 1 can be defined on N \Theta N . As shown in [18], R 1
is connected and deadlock-free. Thus, according to theorem 3, R is deadlock-free
for virtual cut-through and store-and-forward switching.
However, R is not deadlock-free in a wormhole network. Figure 6 shows a deadlocked
configuration on a 3 \Theta 3 mesh. Solid lines represent the
reserved by each packet. Dashed arrows represent the next channel requested by
each packet. Dashed arrows also point at the destination node for the packet. We
have chosen a configuration such that a single routing option is available for each
packet. As can be seen, no packet is able to advance. One of the packets has
reserved one E channel and two N 2 channels, then requesting another E channel.
Thus, such a deadlocked configuration is only valid for wormhole switching.
Conclusions
A theory of deadlock-free adaptive routing has been proposed for virtual cut-through
and store-and-forward networks with edge buffers and/or central buffers.
This theory extends our previous results for wormhole networks. Theorem 2 proposes
a necessary and sufficient condition for deadlock-free adaptive routing. This
condition establishes that a routing function is deadlock-free if and only if there
exists a restricted routing function that is able to deliver all the packets and it has
no cyclic dependencies between the queues supplied by it. This condition is very
similar to the one we proposed for wormhole switching. However, the restrictions
required for wormhole switching have been removed.
Theorem 2 and corollary 1 give a very flexible condition for the design of adaptive
routing algorithms, by allowing the existence of cyclic dependencies between
resources. For routing functions that only consider the current and destination
nodes, theorem 3 adds more flexibility, allowing the addition of edge or central
buffers to a deadlock-free routing function. The new buffers can be used in any
way, even following non-minimal paths. To simplify the application of theorem 3,
a design methodology has been proposed. It supplies fully adaptive routing algorithms
which are guaranteed to be deadlock-free. Finally, we have presented
some design examples, showing the application of the theory.

Acknowledgment

I would like to thank the anonymous referees for their helpful comments and suggestions



--R

"Limits on interconnection network performance,"
"A performance evaluation of adaptive routing in bidimensional cut-through networks,"
"Multicomputers: message-passing concurrent computers,"
"Mesh and torus chaotic routing,"
"The need for adaptive routing in the chaotic and unbalanced traffic environment,"
"Requirements for deadlock-free, adaptive packet routing,"
"Adaptive, deadlock-free packet routing in torus networks with minimal storage,"
"The torus routing chip,"
"Deadlock-free message routing in multiprocessor interconnection networks,"
"On the design of deadlock-free adaptive routing algorithms for multicomputers: design methodologies,"
"A new theory of deadlock-free adaptive routing in wormhole net- works,"
"Performance evaluation of adaptive routing algorithms for k-ary n-cubes,"
"A necessary and sufficient condition for deadlock-free adaptive routing in wormhole networks,"
"A necessary and sufficient condition for deadlock-free adaptive routing in wormhole networks,"
"Adaptive routing protocols for hypercube interconnection networks,"
"A DAG-based algorithm for prevention of store-and-forward deadlock in packet networks,"
"Etude des m'ecanismes de communication pour une machine massivement parall'ele: MEGA,"
"The turn model for adaptive routing,"
"Prevention of store-and-forward deadlock in computer networks,"
"Deflection routing in hypercube networks,"
"Prevention of deadlocks in packet-switched data transport systems,"
"Deadlock-free message routing in multicomputer networks,"
"Virtual cut-through: a new computer communication switching technique,"
"Adaptive packet routing in a hypercube,"
"The Chaos router: A practical application of randomization in network routing,"
"Chaos router: architecture and perform- ance,"
"The Chaos router,"
"Deadlock avoidance in store-and-forward networks - I: Store-and-forward deadlock,"
"A framework for adaptive routing in multicomputer networks,"
"Performance of minimal adaptive routers,"
"A survey of wormhole routing techniques in direct networks,"
"S-Connect: From networks of workstations to supercomputer performance,"
"Fully-adaptive minimal deadlock-free packet routing in hypercubes, meshes and other networks,"
"Fully adaptive minimal deadlock-free packet routing in hypercubes, meshes and other networks: Algorithms and simulations,"
"Message routing schemes in a hypercube machine,"
"Support for multiple classes of traffic in multicomputer routers,"
"Routing messages through networks: an exercise in deadlock avoidance,"
"Computer networks,"
--TR

--CTR
V. Puente , J. A. Gregorio , R. Beivide , F. Vallejo , A. Ibaez, A new routing mechanism for networks with irregular topology, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.31-31, November 10-16, 2001, Denver, Colorado
Jos F. Martnez , Josep Torrellas , Jos Duato, Improving the performance of bristled CC-NUMA systems using virtual channels and adaptivity, Proceedings of the 13th international conference on Supercomputing, p.202-209, June 20-25, 1999, Rhodes, Greece
Olav Lysne , Timothy Mark Pinkston , Jose Duato, Part II: A Methodology for Developing Deadlock-Free Dynamic Network Reconfiguration Processes, IEEE Transactions on Parallel and Distributed Systems, v.16 n.5, p.428-443, May 2005
Milenko Drinic , Darko Kirovski , Seapahn Meguerdichian , Miodrag Potkonjak, Latency-guided on-chip bus network design, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
V. Puente , J. A. Gregorio , F. Vallejo , R. Beivide , C. Izu, High-performance adaptive routing for networks with arbitrary topology, Journal of Systems Architecture: the EUROMICRO Journal, v.52 n.6, p.345-358, June 2006
Ming-Jer Tasi , Sheng-De Wang, A Fully Adaptive Routing Algorithm for Dynamically Injured Hypercubes, Meshes, and Tori, IEEE Transactions on Parallel and Distributed Systems, v.9 n.2, p.163-174, February 1998
On the Design of a High-Performance Adaptive Router for CC-NUMA Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.14 n.5, p.487-501, May
M. E. Gmez , P. Lpez , J. Duato, FIR: an efficient routing strategy for tori and meshes, Journal of Parallel and Distributed Computing, v.66 n.7, p.907-921, July 2006
Jose Duato , Olav Lysne , Ruoming Pang , Timothy M. Pinkston, Part I: A Theory for Deadlock-Free Dynamic Network Reconfiguration, IEEE Transactions on Parallel and Distributed Systems, v.16 n.5, p.412-427, May 2005
Cruz Izu, Throughput fairness in k-ary n-cube networks, Proceedings of the 29th Australasian Computer Science Conference, p.137-145, January 16-19, 2006, Hobart, Australia
Yoshio Turner , Yuval Tamir, Deadlock-free connection-based adaptive routing with dynamic virtual circuits, Journal of Parallel and Distributed Computing, v.67 n.1, p.13-32, January, 2007
Jos Duato, A Theory of Fault-Tolerant Routing in Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.8 n.8, p.790-802, August 1997
J. Duato , T. M. Pinkston, A General Theory for Deadlock-Free Adaptive Routing Using a Mixed Set of Resources, IEEE Transactions on Parallel and Distributed Systems, v.12 n.12, p.1219-1235, December 2001
Tobias Bjerregaard , Shankar Mahadevan, A survey of research and practices of Network-on-chip, ACM Computing Surveys (CSUR), v.38 n.1, p.1-es, 2006
design methodologies;virtual cut-through;interconnection networks;deadlock avoidance;adaptive routing;store-and-forward