Dynamically Configurable Message Flow Control for Fault-Tolerant Routing.
AbstractFault-tolerant routing protocols in modern interconnection networks rely heavily on the network flow control mechanisms used. Optimistic flow control mechanisms, such as wormhole switching (WS), realize very good performance, but are prone to deadlock in the presence of faults. Conservative flow control mechanisms, such as pipelined circuit switching (PCS), ensure the existence of a path to the destination prior to message transmission, achieving reliable transmission at the expense of performance. This paper proposes a general class of flow control mechanisms that can be dynamically configured to trade-off reliability and performance. Routing protocols can then be designed such that, in the vicinity of faults, protocols use a more conservative flow control mechanism, while the majority of messages that traverse fault-free portions of the network utilize a WS like flow control to maximize performance. We refer to such protocols as two-phase protocols. This ability provides new avenues for optimizing message passing performance in the presence of faults. A fully adaptive two-phase protocol is proposed, and compared via simulation to those based on WS and PCS. The architecture of a network router supporting configurable flow control is also described.
Introduction
Modern multiprocessor interconnection networks feature the use of message pipelining coupled
with virtual channels to improve network throughput and insure deadlock freedom
[6,9,21,24]. Messages are broken up into small units called flits or flow control digits [9]. In
wormhole switching (WS), data flits immediately follow the routing header flit(s) into the network
[9]. Routing algorithms using WS can be characterized as optimistic. Network resources (e.g.,
buffers and channels) are committed as soon as they become available. This optimistic nature
leads to high network throughput and low average message latencies. However, in the presence of
I. This research was supported in part by a grant from the National Science Foundation under grant CCR-9214244
and by a grant from Spanish CICYT under grant TIC94-0510-C02-01. A preliminary version of this paper was presented
in part at the 22nd Annual International Symposium on Computer Architecture, Santa Margherita Ligure,
Italy, June 1995.
faults, this behavior can lead to situations where the routing header can become blocked, no
longer make progress, and hence cause the network to become deadlocked. Typically, additional
routing restrictions and/or network resources are required to ensure deadlock freedom in the presence
of faults [4,5,8,11]. For example, fault rings are constructed around convex faulty regions
using additional virtual channels and attendant routing restrictions [4]. Additionally, source hardware
synchronization mechanisms have been proposed to change routing decisions in the presence
of faults [20], and partially adaptive routing around convex fault regions with no additional
channels are feasible [5], while more recently the use of time-outs and deadlock recovery mechanisms
have been proposed [22].
Alternatively, in the pipelined circuit switching (PCS) flow control mechanism, the path setup
and data transmission stages are decoupled [15]. The header flit(s) is first routed to construct a
path. In the presence of faults, the header may perform controlled and limited backtracking. As
opposed to WS, routing algorithms based on PCS are conservative in nature, not committing data
into the network until a complete path has been established. The result is an extremely robust and
reliable communication protocol. However, path setup can exact significant performance penalties
in the form of increased message latencies and decreased network throughput, especially for short
messages.
This paper proposes the use of configurable flow control mechanisms for fully adaptive routing
in pipelined networks. The paper contributes dynamically configurable flow control mechanisms
at the lowest level, and two-phase routing protocols at the routing layer. Routing protocols
can be designed such that in the vicinity of faulty components messages use PCS style flow con-
trol, where controlled misrouting and backtracking can be used to avoid faults and deadlocked
configurations. At the same time messages use WS flow control in fault-free portions of the net-work
with the attendant performance advantages. Such protocols will be referred to as Two-Phase
protocols. A fully adaptive, deadlock-free, two-phase protocol for fault-tolerant routing in
meshes and tori is proposed and analyzed in this paper. Formal properties of Two-Phase routing
are established and the results of experimental evaluation are presented. The evaluation establishes
the performance impact of specific design decisions, addresses the choice of conservative
vs. configurable flow control for fault-tolerant routing, and discusses related deadlock/livelock
freedom issues. Finally, the paper describes the architecture and operations of a single chip router
for implementing Two-Phase routing protocols.
The distinguishing features of this approach are, i) it does not rely on additional virtual channels
over that already needed for fully adaptive routing, ii) the performance is considerably better
than conservative fault-tolerant routing algorithms with equivalent reliability, iii) it is based on a
more flexible fault model, i.e., supports link and/or node faults and does not require convex fault
regions, iv) supports existing techniques for recovery from dynamic or transient failures of links
or switches, and vi) provides routing protocols greater control over hardware message flow con-
trol, opening up new avenues for optimizing message passing performance in the presence of
faults.
The following section introduces a few definitions, and the network, channel, and fault mod-
els. A new class of flow control mechanisms is introduced in Section 3. Section 4 introduces fault
tolerant routing while Section 4.1 provides an analysis of routing properties required for deadlock
freedom. Section 4.2 introduces a fully adaptive two-phase routing protocol for meshes and tori.
Architectural support is discussed in Section 5 and the results of simulation experiments are presented
in Section 6. The paper concludes with plans for implementation of the router and future
research directions.
Preliminaries
2.1 Network Model
Although Two-Phase routing can be used in any topology, the theoretical results are generally
topology specific. The class of networks considered in this paper are the torus connected, bidirec-
tional, k-ary n-cubes and multi-dimensional meshes. A k-ary n-cube is a hypercube with n dimensions
and k processors in each dimension. In torus connected k-ary n-cubes, each processor is
connected to its immediate neighbors modulo k in every dimension. A multidimensional mesh is
similar to a k-ary n-cube, without the wrap around connections. A message is broken up into small
units referred to as flow control digits or flits. A flit is the smallest unit on which flow control is
performed, and represents the smallest unit of communication in a pipelined network. Each processing
element (PE) in the network is connected to a routing node. The PE and its routing node
can operate concurrently. We assume that one of the physical links of the routing node is used for
the PE connection. The network communication links are full-duplex links, and the channel width
and flit size are assumed to be equivalent. A number of virtual channels are implemented in each
direction over each physical channel. Each virtual channel is realized by independently managed
flit buffers, and share the physical channel bandwidth on a flit-by-flit basis. A mechanism as
described in [6] is used to allocate physical channel bandwidth to virtual channels in a demand-driven
manner. Flits are moved from input channel buffers to output channel buffers within a node
by an internal crossbar switch.
Given a header flit that is being routed through the network, at any intermediate node a routing
function specifies the set of candidate output virtual channels that may be used by the message.
The selection function is used to pick a channel from this set [12]. A profitable link is a link over
which a message header moves closer to its destination. A backtracking protocol is one which
may acquire and release virtual channels during path setup. Releasing a virtual channel that is
used corresponds to freeing buffers and crossbar ports used by the message on that channel.
2.2 Virtual Channel Model
The following virtual channel model is used in this paper. A unidirectional virtual channel, v i ,
is composed of a data channel, a corresponding channel, and a complementary channel
is referred to as a virtual channel trio [15]. The routing header will traverse
while the subsequent data flits will traverse . The complementary channel is reserved for
use by special control flits. The corresponding channels and complementary channels essentially
form a control network for coordinating fault recovery and adaptive routing of header flits including
limited and controlled backtracking of header flits. The complementary channel of a trio
traverses the physical channel in the direction opposite to that of its associated data channel. The
channel model is illustrated in Figure 1(a). There are two virtual channels v i (v r ) and v j (v s ) from
(R2) to (R1). Only one message can be in progress over a data channel. Therefore compared
to existing channel models, this model requires exactly 2 extra flit buffers for each data
channel - one each for the corresponding channel and complementary channel respectively.
Since control flit traffic is a small percentage of the overall flit traffic, in practice all control channels
across a physical link are multiplexed through a single virtual control channel [1] as shown in

Figure

1(b). For example, control channel c 1 in Figure 1(b) corresponds to flit buffers v r *, v s *, v j
c
and v i
c .
2.3 Fault Model
On-line fault detection is a difficult problem. In this paper we assume the existence of fault
c
detection mechanisms, and focus on how such information may be used for robust, reliable com-
munication. The detection mechanisms identify two different types of faults. Either the entire processing
element and its associate router can fail or a communication channel may fail. When a
physical link fails, all virtual channels on that particular physical link are marked as faulty. When
a PE and its router fail, all physical links incident on the failed PE are also marked as being faulty.
In addition to marking physical channels incident on the failed PE as being faulty, physical channels
incident on PEs which are adjacent to the failed PEs and/or communication channel may be
marked as unsafe. The unsafe channel [23] designation is useful because routing across them may
lead to an encounter with a failed component. Some of the protocols we will present in
Section 4.2 use unsafe channels. Figure 2 shows failed PEs, failed physical links and unsafe channels
in a two dimensional mesh network. The failed PE can no longer send or receive any messages
and thus is removed from the multi-processor network.
Failures can be either static or dynamic. Static failures are present in the network when the
system is powered on. Dynamic failures occur at random during operation. Both types of failures
are considered to be permanent, i.e., they remain in the system until repaired. For static failures
and dynamic failures that occur on idle links and routers, only header flits encounter failed links
and routing protocols can attempt to find alternative paths.

Figure

1. Inter-router virtual channel model
a) Logical channel model for 2 virtual
channels between routers R1 and
b) Implementation of the logical channel
model
d
c
c
d
d
c
c
d
d
c
c
d
d
r
c
d
r
s
However, dynamic failures can occur on busy links and interrupt a message transmission. Fur-
thermore, failure during the transmission of a flit across a channel can cause the flit to be lost.
Since only header flits contain routing information, data flits whose progress is blocked by a failure
cannot progress. They will remain in the network, holding resources, and can eventually cause
deadlock. We rely on the existence of a recovery mechanism for removing such "dead" flits from
the network. There exist at least two techniques for implementing distributed recovery [16, 22]
under dynamic faults. In both cases, the failure of a link will generate control information that is
propagated upstream and/or downstream along the message path. All resources along the path can
be recovered. Alternatively, a third approach to recovering from messages interrupted by a fault
can be found in [8]. All of these schemes are non-trivial, require hardware support, and have been
developed elsewhere [8, 22, 16]. We will assume the existence of such a technique and evaluate its
performance impact in Section 6.
Scouting Switching - A family of Flow Control Mechanisms
Scouting switching (SS) is a flow control mechanism that can be configured to provide specific
trade-offs between fault tolerance and performance. In SS, the first data flit is constrained to
remain K links behind the routing header. When the flow control is equivalent to wormhole
switching, while large values can ensure path setup prior to data transmission (if a path exists).

Figure

3 illustrates a time-space diagram for messages being pipelined over five links using SS
mechanisms. The parameter, K, is referred to as the scouting
distance or probe lead. Every time a channel is successfully reserved by the routing header, it
returns a positive acknowledgment. As acknowledgments flow in the direction opposite to the

Figure

2. Failed nodes and unsafe channels
Faulty Node
Faulty Channel
Unsafe Channel
routing header, the gap between the header and the first data flit can grow up to 2K - 1 links while
the header is advancing. If the routing header backtracks, it must send a negative acknowledg-
ment. Associated with each virtual channel is a programmable counter. A virtual channel reserved
by a header increments its counter every time it receives a positive acknowledgment and it decrements
its counter every time it receives a negative acknowledgment. When the value of the
counter is equal to K, data flits are allowed to advance. For performance reasons, when
acknowledgments are sent across the channels. In this case, data flits immediately follow the
header flit. For example, in Figure 4, the header is blocked by faulty links at node A. The first data
flit is constrained to remain K links behind the header at node B. From the figure, we can
see that header can backtrack, releasing link A, and establish an alternate path across link C. By
statically fixing the value of K, we fix the trade-off between network performance (overhead of
positive and negative acks) and fault tolerance (the ability of the header to backtrack and be routed
around faults). By dynamically modifying K, we can gain improved run-time trade-offs between
fault tolerance and performance.
If L is the message length in flits, l the number of links in the path, and K the scouting dis-
tance, we can derive expressions for the minimum message latency for each type of routing mech-
Figure

3. Time-space diagram of WS, Scouting, and PCS
su
data
data
data
su
su
data
Scouting
Pipelined Circuit Switching
Route Setup
Data Transmission
Routing Header
PCS

Acknowledgment

Data Flit
Scouting Acknowledgment
Wormhole Switching
anism.
4 Fault-tolerant Routing
The basic idea proposed in this paper is for messages to be routed in one of two phases. When
messages are traversing fault-free segments of the network, they are routed using protocols based
on WS. When messages traverse a segment of the network with faults, a more conservative flow
control mechanism, and associated fault-tolerant routing protocol is employed. The use of SS flow
control to be made dynamically by simply modifying the value of K.
The design of effective two-phase protocols is dependent upon the relationships between the i)
scouting distance (K), ii) the number of faults (f), iii) the number of links a header flit may be
forced to backtrack in routing around faults (b), and iv) the number of steps a header may be
routed along non-minimal paths (m). The analysis in the following subsection establishes these
relationships for k-ary n-cubes and multi-dimensional meshes. Section 4.2 describes a fully adaptive
two-phase, fault-tolerant, routing protocol.
4.1 Analysis
Messages are assumed to always follow shortest paths in the absence of faults. Further, when

Figure

4. Backtracking out of a faulty region
A
Data flit progress
Failed channel
Routing header progress
scouting l
a header encounters a faulty link, it is allowed to either misroute or backtrack, with the preference
given to misrouting.
Theorem 1 In the absence of any previous misrouting, the maximum number of consecutive links
that a header flit will backtrack over in a torus connected k-ary n-cube in a single source-destination
path is is the number of faulty components.
Proof: If there have been no previous misroutes, the header flit is allowed to misroute in the presence
of faults even when the number of misroutes is limited. Thus, the header will only backtrack
when the only healthy channel is the one previously used to reach the node (Figure 5). In the case
of a k-ary n-cube, every node has 2n channels, incident on a distinct PE. Since the header arrived
from a non-faulty PE, it will be forced to backtrack if 2n - 1 channels are faulty. At the next node,
since the header has backtracked from a non-faulty PE and originally arrived from a non-faulty
PE, it will be forced to backtrack if the remaining 2n - 2 channels are faulty. Each additional back-tracking
step will be forced by 2n - 2 additional failed channels. Thus we have:
Consider the second case shown in Figure 5 where there is a turn at the end of the alley. In order to
cause the routing header to backtrack initially, there needs to be 2n - 1 faulty channels, the second
backtrack requires 2n - 2 faulty channels while the third backtrack is necessitated by 2n - 3 node

Figure

5. Node faults causing backtracking
case 1
case 2
Faulty Node
Faulty Link
faults or 2n - 2 channel faults. All subsequent backtracks require 2n - 2 additional faults. Thus we
Theorem 2 In the absence of any previous misrouting, the maximum number of consecutive links
that a header flit will backtrack over in a n-dimensional mesh in a single source-destination path
is is the number of faulty components.
Proof: If there have been no previous misrouting operations, the message is allowed to misroute
in the presence of faults, even if the maximum number of misrouting operations is limited. There
are several possible cases:
- The routing probe is at a node with 2n channels. This is the same case as with a torus connected
k-ary n-cube. Hence, the number of faults required to force the first backtrack is 2n - 1. To
force additional backtracks, 2n - 2 additional faults are required per additional backtrack.
- The probe is at a node with less than 2n channels. As with the earlier cases, all channels except
the one used to reach the node can be used in case of faults (either for routing or misrouting). The
worst case (Figure 6(a)) occurs when the node has the minimum number of channels. In an n-dimensional
mesh, nodes located at the corners only have n channels. One of the channels was
used by the probe to reach the node. Hence, the failure of n - 1 channels or nodes causes the routing
probe to backtrack. The probe is now on the edge of the mesh, where each node has
channels. One channel was already used to reach the node the first time and another one for the
previous backtracking operation, therefore, only n - 1 channels are available for routing. These
channels must all be faulty to force a backtrack operation. Thus, the maximum number of mandatory
backtrack operations is f div (n - 1), where f is the number of faults.
- Consider the second case shown in Figure 6(b) where a turn at the end of the alley exists. In
order to cause the initial backtrack, there needs to be n faults. n - 2 faults are required to cause a
backtrack at the corner processing element. Each additional backtrack requires n - 1 II faults.
Hence, the maximum number of backtracking operations is (f +1) div (n - 1).
II. n -1 faulty channels or n - 2 faulty nodes for the first additional backtracks.
The above theorems establish a relationship between the number of backtracking operations
and the number of faults for both meshes and tori. Now consider the relationship between the
number of misrouting operations, number of faults, and number of backtracking steps. This is
determined by the configuration of faults and is specified by the following theorem. It will be useful
in determining the scouting distance.
Theorem 3 In a torus connected k-ary n-cube with less than 2n faults, the maximum number of
consecutive backtracking steps, b, before the header can make forward progress is 3 III if

Figure

6. Faults causing backtracking in a mesh
Faulty Link
Faulty Node
(a) (b)

Figure

7. Fault configuration showing required to search all inputs in one plane
A
Legend
Source/Desination Node
Failed Node
Failed Channel
i) the maximum number of misroutes allowed is 6,
ii) misrouting is preferred over backtracking,
iii) when necessary, the output channel selected by the routing function for misrouting the mes-
sage, is in the same dimension as the input channel of the message.
Proof: Consider Figure 7, where all of the adjacent nodes to the destination in one plane are
faulty. The routing header would have to take a maximum of six misroutes to check all of the possible
input links to the destination lying within a plane. This will eliminate two dimensions to
search out of the n possible dimensions. If all permitted misroutes have been used or the routing
header arrives at a previously visited node, the routing header must backtrack. Backtracking over
a misroute removes it from the path and decrements the misroute count. The routing header backtracks
two hops to point A in Figure 7. From this point, the routing header can take one misroute
into any of the n - 2 remaining dimensions, j for example (where j is not one of the two dimensions
forming the plane in Figure 7). The routing header is now two hops away from the node
adjacent to the destination lying along dimension j. The routing header can check to see if that
node is faulty with one profitable hop. If that node is faulty, then the routing header is forced to
backtrack two hops back to point A. Alternatively, in two hops the header can check if the link
adjacent to the destination is faulty. In this case the maximum backtrack distance is three hops
back to point A. From point A, with one misroute and two profitable routes, the routing header
can check the status of every node one hop away from the destination and/or every link adjacent to
the destination. Since the number of faults allowed in the system is limited to 2n - 1, the existence
of one healthy node and one healthy channel adjacent to the destination is guaranteed. Hence, the
maximum number of backtracks that the routing header has to perform is three.
Theorem 4 In a n-dimensional mesh with less than n faults, the maximum number of consecutive
backtracking steps, b, before the header can make forward progress is 3 if
i) the maximum number of misroutes allowed is 6,
ii) misrouting is preferred over backtracking,
iii) when necessary, the output channel selected by the routing function for misrouting the message
is in the same dimension as the input channel of the message.
Proof: Consider the case when the destination node cannot be surrounded by faults in any plane.
III. If only node failures are considered, the number of backtracks required per backtracking operation is 2.
Figure

8 shows the corner of a mesh where 3. At the corner node of the mesh, two of the three
input/output channels of the corner node are faulty. The routing probe entering the corner node is
forced to backtrack one step. However, since there cannot be any additional faulty links or nodes
in the network (due to the limit in the number of faults), the routing probe can reach the destination
without any further backtracking operations. If the routing probe is not at a corner node, but
at a node on the edge of the mesh, then since each node on the edge of a mesh has
and since a maximum of n - 1 faults are allowed, no backtracking will be required because misrouting
is preferred over backtracking.
Consider the case when the destination node can be surrounded by faults in some plane. This
means that a situation similar to that shown in Figure 7 occurs, even in the nodes at the edge of the
mesh. If the number of misroutes is limited to 6, then the results of Theorem 3 can be applied and
the maximum number of consecutive backtracking steps is 3.
Only 2n and n faults are required to disconnect the network in a k-ary n-cube and n-dimensional
mesh respectively. However, in practice, the network can often remain connected with a
considerably larger number of failed nodes and channels. If the total number of faults was allowed
to be greater than 2n or n, then it is possible that some messages may be undeliverable. If allowed
to remain in the network, these messages impact performance and may lead to deadlock. Techniques
such as those described in 6.2Section 2.3 can be used to detect and remove such messages

Figure

8. Backtracking in corner node of mesh
Failed Link
Failed Node
from the network.
4.2 Two-Phase Routing Protocol
Routing protocols operate in two phases: an optimistic phase for routing in fault-free segments
and a conservative phase for routing in faulty segments. The former uses an existing fully adap-
tive, minimal, routing algorithm [12]. In this section we propose two candidates for the conservative
phase. The candidates differ primarily in the impact on performance as a function of the
number of faults.
The proposed Two-Phase (TP) protocol is shown in Figure 9 and operates as follows: In the
absence of faults, TP uses a deadlock-free routing function based on Duato's Protocol (DP) [12].
In DP, the virtual channels on each physical link are partitioned into restricted and unrestricted
partitions. Fully adaptive minimal routing is permitted on the unrestricted partition (adaptive
while only deterministic routing is allowed on the restricted partition (deterministic
channels). The selection function uses a priority scheme in selecting candidate output channels at
a router node. First, the selection function examines the safe adaptive channels. If one of these
channels is not available, either due to it being faulty or busy, the selection function examines the
/* Structure of Two-Phase Routing */
IF detour complete THEN /* completed detour (destination reached or detour completed)*/
reset header to DP mode;
END IF
IF DP THEN /* route using DP routing restrictions with unsafe channels */
select safe profitable adaptive channel; RETURN;
select safe deterministic channel; RETURN;
IF NOT (safe deterministic channel faulty) THEN
RETURN; /* blocks progress */
END IF
select unsafe profitable adaptive channel; /* Acks sent or not sent depending on */
switch to SS mode & set ack counter; /* which one of the two different */
conservative phases of TP routing used */
select unsafe deterministic channel;
switch to SS mode & set ack counter;
set header to detour mode;
END IF
IF detour THEN /* route with no restrictions in detour mode */
select profitable channel; RETURN;
IF #_misroutes < m THEN
END IF
END IF

Figure

9. Structure of Two-Phase routing
safe deterministic channel (if any). If the safe deterministic channel is busy, the routing header
must block and wait for that channel to become free. If a safe adaptive channel becomes free
before the deterministic channel is freed, then the header is free to take the adaptive channel. If the
deterministic channel is faulty, the selection function will try to select any profitable adaptive
channel, regardless of it being safe or unsafe. The selection function will not select an unsafe
channel over an available safe channel. An unsafe channel is selected only if it is the only alternative
other than misrouting or backtracking. When an unsafe profitable channel is selected as an
output channel, the message enters the vicinity of a faulty network region. This is indicated by
setting a status bit in the routing header. Subsequently, the counter values of every output channel
traversed by the header is set to K. Values of K > 0 will permit the routing header to backtrack to
avoid faults if the need arises. Message flow control is now more conservative, supporting more
flexible protocols in routing around faulty regions. If no unsafe profitable channel is available, the
header changes to detour mode.
In detour mode, no positive acknowledgments are generated and with no positive acknowledg-
ments, data flits do not advance. During the construction of the detour, the routing header performs
a depth-first, backtracking search of the network using a maximum of m misroutes. Only
adaptive channels are used to construct a detour. The detour is complete when all the misroutes
made during the construction of the detour have been corrected or when the destination node is
reached. When the detour is complete, SS acknowledgments flow again, and data flits resume
progress. Note that all channels (or none) in a detour are accepted before the data flits resume
progress. This is required to ensure deadlock-freedom. The detour mode is identified by setting a
status bit in the header.
While it is desirable to remain with WS for the fault-free routing (optimistic phase), alternatives
are possible for the conservative phase. In the conservative phase of TP (Figure 9), the
header enters SS mode when an unsafe channel is selected. Alternatively, in the conservative
phase we may chose to continue optimistic WS flow control across unsafe channels. In
this case, it not necessary to mark channels as unsafe. When WS forward progress is stopped due
to faults, then detours can be constructed using increased misrouting as necessary. When a detour
is completed, one acknowledgment is sent to resume the flow of the data flits. Note, in this case
we always have no positive or negative acknowledgments are transmitted.
When larger values of K are used (as in Figure 9), the increased ability to backtrack and route
around fault regions reduces the probability of constructing detours. Thus we see that the choice
of K is a trade-off between acknowledgment traffic, and the increased misrouting/backtracking
that occurs in detour construction. We expect that the choice of an appropriate value of K is
dependent upon the network load and failure patterns. The trade-offs are evaluated in Section 6.
Note that the proofs of deadlock freedom do not rely on unsafe channels. Therefore the designer
has some freedom in configuring the appropriate mechanisms as a function of the failure patterns.

Figure

shows a routing example using the Two-Phase routing protocol (as shown in

Figure

with seven node failures and initially set to 0, the
routing header routes to node B where it is forced to cross an unsafe channel. The value of K is
increased to 3 and the header routes profitably to node A, with the data flits advancing until node
B. At node A, the routing header cannot make progress towards the destination entering detour
mode, so it is misrouted upwards. After two additional misroutes can no longer be misrouted due
to the limit on m. The routing header then is forced to backtrack to node A. Since there are no
other output channels to select, the routing header is forced to backtrack to node C. From there, it
is misrouted twice downwards and then finds profitable links to the destination. In this case, the
detour is completed when the destination is reached. Also, notice that data flits do not advance
while the header is in detour mode. Thus, the first data flit is still at node B.
For comparison purposes, consider the use of an alternative conservative phase as described

Figure

10. Routing example
Failed channel
Failed node
above where unsafe channels are not used and K is always 0. Referring to Figure 10, the routing
header is routed profitably to node A. In this case, Thus, the first data flit also reaches node
A. Since it cannot be routed profitably from node A, a detour is constructed. The header is misrouted
upwards three links, cannot find a path around the fault region, and therefore is forced to
backtrack back to node A. The routing header is then forced to misroute to node C. From node C,
it misroutes downwards, and traverses a path to the destination. Notice that in this case a path that
is two hops longer since the data flits now pass through node A. However, while the header is
routed from node B to node A, no acknowledgment flits are generated. These two examples indicate
that the specific choice of flow control/routing protocol for the conservative phase is a trade-off
that is dictated by the fault patterns and network load.
The theorems in Section 4.1 cover networks with a fixed number of faults. For an arbitrary
number of faults, f, small values of m, and destination node failures, it is possible that the header
may backtrack to the location of the first data flit. In fact, this may occur if the links are simply
busy rather than being faulty. One solution is to re-try from this point. However, it is possible that
this also will not succeed. At this point, we rely on the recovery mechanism referenced in
Section 2.3 to tear down the path and, if designed to do so, re-try from the source. With successive
failures to establish a path from the source, some higher level protocol is relied upon to take
appropriate action. This behavior particularly addresses messages destined for failed nodes. After
a certain number of attempts, the higher level protocol may mark the node as unreachable from
the source. While livelock is addressed in this fashion, the following theorem establishes the
deadlock freedom of TP.
Theorem 5 Two-Phase routing is deadlock-free.
Proof: Let C be set of all virtual channels, C 1 be set of deterministic channels and C 2 be set of
adaptive channels. The following situations can occur during the message routing:
- If the routing header does not encounter any faulty nodes or channels, TP routing uses DP routing
restrictions which have been shown to be deadlock-free in the fault-free network [12].
- If the routing header encounters an unsafe channel and selects a safe channel over the unsafe
channel, then no deadlock can occur since the safe adaptive channel still is contained in the set of
virtual channels C 2 and routing in this set cannot induce deadlock.
- If the routing header is forced to take an unsafe adaptive channel, then no deadlock can occur
since the unsafe channels are still in channel set C 2 and routing in C 2 cannot induce deadlock.
- If the routing header encounters a faulty node or channel and cannot route profitably and cannot
take a deterministic channel from C 1 , because it is faulty, then the routing header constructs a
detour. No deadlock can occur while building the detour because the probe can always backtrack
up to the node where the first data flit resides. No deadlock can occur in the attempt to construct a
detour because if after several re-tries, the detour cannot be constructed, the recovery mechanism
will tear down the path, thus releasing the channels being occupied by the message.
- As the detour uses only adaptive channels, channels from C 2 , no deadlock can arise in routing
the message after the detour has been constructed because, taking into account the condition to
complete a detour, the ordering between channels in the deterministic channels, C 1 , is still preserved

- Finally, the detour only uses adaptive channels from C 2 . Thus, building a detour does not prevent
other messages from using deterministic channels to avoid deadlock.
5 Architectural Support

Figure

11 illustrates the block diagram of a router that implements Two-Phase routing. This is
a modified version of a PCS router described in [1]. Each input and output physical channel has
associated with it a link control unit (LCU). The input LCU's feed a first-in-first-out (FIFO) data
input buffer (DIBU) for each virtual channel. All input control channels are multiplexed over a
single virtual channel and therefore feed a single FIFO control input buffer (CIBU). The data
FIFO's feed the inputs of the crossbar. The control FIFO's arbitrate for access to the routing control
unit (RCU). The RCU implements the two-phase routing protocol to select an output link, and
maps the appropriate input link of the crossbar to the selected output link. The modified control
flit is now sent out the RCU output arbitration unit to the appropriate control output virtual chan-
nel. The LCUs and DIBUs support SS flow control as described later in this section.
A single chip version of this router with only PCS flow control has been implemented in a
metal layer CMOS process and fabricated by MOSIS [1]. The overall design contains
over 14,000 transistors and is 0.311 cm square. The chip has 88 pins. The core logic of the
router chip consumes 55% of the chip area and the crossbar occupies 14% of the area dedicated to
the core circuitry. An additional 10% of the logic payload is devoted to the RCU.
The routing header (Figure 12) for the Two-Phase protocol consists of six fields. The first field
is the header bit field which identifies the flit as a routing header. The second field is the backtrack
field. This bit signifies whether the routing header is going towards the source (i.e., backtracking)
or towards the destination. The next field is the misroute field. It records the number of misrouting
operations performed by the routing header. Since the Two-Phase protocol must be allowed a
maximum of 6 misroutes to ensure the delivery of the message (in a network with up to 2n - 1
node faults), this field is three bits in size. The fourth field is the detour bit. This bit is used by the
control logic to determine if the message is in detour mode. If the bit is clear and the SS bit is set,

Figure

11. Overview of router chip
LCU
CPU
CPU
Data Buffer (Input/Output)
Control Buffer (Input/Output)
Data Input Bus
Data Output Bus
Control Input Bus
Control Output Bus
LEGEND
CIBU/COBU
DIBU/DOBU
LCU LCU
LCU LCU
LCU LCU
LCU
CROSSBAR
RCU
RCU
RCU
INPUT
Enable Buffers

Figure

12. Format of header flit(s)
Bit
Header Back-track
Misroute Detour Xn-offset
X2-offset
X1-offset
SS
the router generates an acknowledgment flit every time the routing header advances. Acknowledgments
are propagated over the complementary control channel. Following the detour field is the
SS bit. When the SS bit is set, SS flow control is used across every channel traversed by the
header thus setting the counter to K. The next field is actually a set of offsets, one offset for each
of the n dimensions in the k-ary n-cube. Their size depends on the size of the interconnection net-work
(i.e., the value of k).
Depending upon how the conservative phase is implemented, each physical channel will
require an unsafe channel status bit maintained in the RCU. When a routing header enters the
RCU, the input virtual channel address is used to access the unsafe channel store and the history
store. The history store maintains a record of output channels that have been searched by a back-tracking
header. Figure 13 shows the organization of the RCU. The major distinguishing features
of this router architecture are due to the support for the backtracking search done by a header. A
detailed discussion of architectural requirements for such routing can be found in [15, 1].
Associated with each virtual channel is a counter for recording acknowledgments and a register
with the value of K, the scouting distance. For a two bit counter is required for each virtual
channel. All counters are maintained in the counter management unit (CMU) in the RCU.
When a positive (negative) acknowledgment flit arrives for a virtual circuit, the CMU increments
(decrements) the counter that corresponds to the data virtual channel. If the counter value is K,
data flits are allowed to flow. Otherwise they are blocked at the DIBU as show in Figure 14. This

Figure

13. Routing control unit
Channel Mappings
Decision Unit Inc/Dec Banks
History Store Decode
Unsafe Store
Header (modified)
Output Virt. Chan
DIBU
Enable
Input Virt. Chan. Header
Unit
Counter Management
is achieved by providing DIBU output enables from the RCU. Finally, the RCU does not propagate
the acknowledgment beyond the first data flit of a message.
6 Performance Evaluation
The performance of the fault-tolerant protocols was evaluated with simulation studies of message
passing in a 16-ary 2-cube with messages. The routing header was 1 flit long. The simulator
performs a time-step simulation of network operation at the flit level. The message
destination traffic was uniformly distributed. Simulation runs were made repeatedly until the 95%
confidence intervals for the sample means were acceptable (less than 5% of the mean values). The
simulation model was validated [14] using deterministic communication patterns. We use a congestion
control mechanism (similar to [3]) by placing a limit on the size of the buffer (eight buffers
per injection channel) on the injection channels. If the input buffers are filled, messages cannot
be injected into the network until a message in the buffer has been routed. A flit crosses a link in
one cycle.
The performance of TP was compared to the performance of Duato's Protocol (DP) [12]. DP
is a wormhole based routing protocol which partitions the virtual channels into two sets, adaptive
and escape. The adaptive channels permit fully adaptive minimal routing while the escape channels
are used to implement a deadlock-free sub-network. To measure the fault tolerance of TP, it
was compared with Misrouting, Backtracking with m misroutes (MB-m) [15]. MB-m is a PCS
based routing protocol which allows fully adaptive routing and up to m misroutes per virtual circuit

Figure

14. Data flit flow control
COBU
CIBU To RCU Arb
From RCU
DOBU
DOBU
DOBU
To Crossbar
Enable Lines From RCU
DIBU
DIBU
DIBU
From Crossbar
Router A Router B
The metrics used to measure the performance of TP are average message latency and network
throughput. Average message latency is the average of the time that messages spend in the net-work
after their respective routing headers have been injected into the network until the time when
the tail flit is consumed by the destination node. Network throughput is defined as the total number
of flits delivered divided by the number of nodes in the network and the total simulation time
in clock cycles.
When no faults are present in the network, TP routing uses the DP routing restrictions and
This results in performance that is identical to that of DP. The fault performance of TP is
evaluated with a configuration of TP which uses
the faulty regions, i.e., does not use unsafe channels, and then uses misrouting backtracking
search to construct detours when the header cannot advance.
6.1 Static Faults

Figure

15 is a plot of the latency-throughput curves of TP and MB-m with 1, 10, and 20 failed
nodes randomly placed throughout the network. While the theorems developed in this paper
depend on the number of faults being less than the degree of processing elements (i.e.,
connected k-ary n-cube), the plots show the performance of TP for larger
values of faults because the faults are randomly distributed throughout the network. When randomly
placed, 2n - 1 faults do not perturb the system significantly. The performance of both routing
protocols drop as the number of failed nodes increase, since the number of undeliverable

Figure

15. Latency-throughput of TP and MB-m with node faults
Throughput
Latency
(Clock
Cycles)
Latency Vs. Throughput
TP and MB-m in Faulty Network
MB-m (1F)
MB-m (10F)
MB-m (20F)
messages increases as the number of faults increase. However, the latency of TP routed messages
for a given network load remains 30 to 40% lower than that of MB-m routed messages.
MB-m degrades gracefully with steady but small drops in the network saturation traffic load
(the saturation traffic is the network load above which the average message latency increases dramatically
with little or no increase in network throughput) as the number of faults increases.

Figure

16(a) shows that the latency of messages successfully routed via MB-m remains relatively
flat regardless of the number of faults in the system. The number in parenthesis indicates the number
of messages offered/node/5000 clock cycles. However, with the network offered load at 0.2
flits/node/cycle (30 msgs/node/5000 cycles), the latency increased considerably as the number of
faults increased. This is because with a low number of faults in the system, an offered load of
flits/node/cycle is at the saturation point of the network. With the congestion control mechanism
provided in the simulator, any additional offered load is not accepted. However, at the saturation
point, any increases in the number of faults will cause the aggregate bandwidth of the
network to increase beyond saturation and therefore cause the message latency to increase and the
network throughput to drop. When the offered load was at 0.32 flits/node/cycle, the network was
already beyond saturation so the increase in the number of faults had a lesser effect.
At low to moderate loads and with a lower number of faults, the latency and throughput characteristics
of TP are significantly superior to that of MB-m. The majority of the benefit is derived
from messages in fault-free segments of the network transmitting with
trol). TP however, performed poorly as the number of faults increased. While saturation traffic

Figure

16. Latency and throughput of TP and MB-m as function of node faults
Node Failures200.0600.0Latency
(Clock
Cycles)
Latency Vs. Node Faults
TP and MB-m
TP (1)
MB-m (1)
MB-m (30)
Node Failures0.100.30Throughput
Throughput Vs. Node Faults
TP and MB-m
TP (1)
MB-m (1)
MB-m (30)
with one failed node was 0.32 flits/node/cycle, it dropped to slightly over
with 20 failed nodes (only ~17% of original network throughput). In the simulated system (a 16-
ary 2-cube), 2n - 1 faults is 3. Hence 20 failed nodes is much greater than the limit set by the theorems
proposed in this paper. Figure 16 also shows the latency and throughput of TP as a function
of node failures under varying offered loads. At higher loads and increased number of faults, the
effect of the positive acknowledgments due to the detour construction becomes magnified and
performance begins to drop. This is due to the increased number of searches that the routing
header has to perform before a path is successfully established and the corresponding increase in
the distance from the source node to the destination. The trade-off in this version of TP is the
increased number of detours constructed vs. the performance of messages in fault-free sections of
the network. With larger numbers of faults, the former eventually dominates. In this region purely
conservative protocols appear to remain superior.
In summary, at lower fault rates and below network saturation loads, TP performs better than
the conservative counterpart. We also note that TP protocol used in the experiments was designed
for 3 faults (a 2 dimensional network). A relatively more conservative version could have been
configured.

Figure

17 compares the performance of TP with only one fault in the
network and low network traffic, both versions realize similar performance. However, with high
network traffic and larger number of faults, the aggressive TP performs considerably better. This
is due to the fact that with K > 0, substantial acknowledgment flit traffic can be introduced into the
Throughput (Flits/Cycle/Node)100.0200.0Latency
(Clock
Cycles)
Latency Vs. Throughput
Conservative vs. Aggressive SR
Aggressive (1F)
Aggressive (10F)
Aggressive (20F)
Conservative (1F)
Conservative (10F)
Conservative (20F)

Figure

17. Comparison of aggressive conservative SS routing behavior
network, dominating the effect of an increased number of detours.
6.2 Dynamic Faults
When dynamic faults occur, messages may become interrupted. In [16], a special type of control
flit called, kill flit, was introduced to permit distributed recovery. When a message pipeline is
interrupted, PEs that span the failed channel or PE release kill flits on all virtual circuits that were
affected. These kill flits follow the virtual circuits back to the source and the destination of the
messages. These control flits release any reserved buffers and notify the source that the message
was not delivered, and notify the destination to ignore the message currently being received. If we
are also interested in guaranteeing message delivery in the presence of dynamic faults, the complete
path must be held until the last flit is delivered to the destination. A message acknowledgment
sent from the destination traverses the complementary control channel, removes the path,
and flushes the copy of the message at the source. Kill flits require one additional buffer in each
control channel. This recovery approach is described in [16]. Here we are only interested in the
impact on the performance of TP. Figure 18 illustrates the overhead of this recovery and reliable
message delivery mechanism.
The additional message acknowledgment introduces additional control flit traffic into the sys-
tem. Message acknowledgments tend to have a throttling effect on injection of new messages. As
a result, TP routing using the mechanism saturates at lower network loads and delivered messages
have higher latencies. We compare the cases of i) probabilistically inserting f faults dynamically,
with ii) f/2 static faults - this is the average number of dynamic faults that would occur. From the
simulation results shown in Figure 18, we see that at low loads the performance impact of support
for dynamic fault recovery is not very significant. However, as injection rates increase, the additional
traffic generated by the recovery mechanism and the use of message acknowledgments
begins to produce a substantial impact on performance. The point of interest here is that dynamic
fault recovery has a useful range of feasible operating loads for TP protocols. In fact, this range
extends almost to saturation traffic.
6.3 Trace Driven Simulation
The true measure of the performance of an interconnection network is how well it performs
under real communication patterns generated by actual applications. The network is considered to
have failed if the program is prevented from completing due to undeliverable messages. Communication
traces derived from several different application programs: EP (Gaussian Deviates), MM
(Matrix Multiply), and MMP (another Matrix Multiply). These program traces were generated
using the SPASM execution driven simulator [25].
Communication trace driven simulations were performed allowing only randomly placed
physical link failures. Node failures would require the remapping of the processes, with the resulting
remapping affecting performance. No recovery mechanisms were used for recovery of undeliverable
messages. The traces were generated from applications executing on a 16-ary 2-cube.
The simulated network was a 16-ary 2-cube with 8 and 16 virtual channels per physical link. The
aggressive version of TP was used, i.e., no unsafe channels were used. Figure 19 shows three plots
of the probability of completion rates for the three different program traces with differing values
of misrouting (m). A trace is said to have completed when all trace messages have been delivered,
hence the probability of completion is defined as the ratio of the number of traces that were able to
execute to completion over the total number of traces run. If even one message cannot be deliv-
ered, program execution cannot complete. The results show the effect of not having recovery
mechanisms. These simulations were implemented with no re-tries attempted when a message
backtracks to the source or the node containing the first data flit. This is responsible for probabilities
of completion below 1.0 for even a small number of faults. The performance effect of the
recovery mechanism was illustrated in Figure 18. We expect that 2 or 3 re-tries will be sufficient
in practice to maintain completion probabilities of 1.0 for a larger number of faults.
In some instances, an increased number of misroutes resulted in poorer completion rates. We

Figure

18. Comparison of TP with and without tail-acknowledgment flits
Throughput (Flits/Cycle/Node)100.0200.0Latency
(Clock
Cycles)
Latency Vs. Throughput
Comparison of Dynamic Fault-Tolerant Mechanism
w/o TAck (1F)
w/o TAck (10F)
w/o TAck (20F)
with TAck (1F)
with TAck (10F)
with TAck (20F)
believe that this is primarily due to the lack of recovery mechanisms and re-tries. Increased misrouting
causes more network resources to be reserved by a message. This may in turn increase the
probability that other messages will be forced to backtrack due to busy resources. Without re-
tries, completion rates suffer. We again see the importance of implementating relatively simple
heuristics such as a small number of re-tries.
Finally, the larger number of virtual channels offered better performance since it provided an
increase of network resources and hence reduced the probability of backtracking due to busy
links.
6.4 Summary of Performance
Specifically, the performance evaluation provided the following insights.
Link Failures0.801.00
Probability
of
Completion
Probability of Completion
M=3, V=8
M=4, V=8
M=5, V=8
Link Failures0.40.8Probability
of
Completion
Probability of Completion
M=3, V=8
M=4, V=8
M=5, V=8
Link Failures0.700.901.10
Probability
of
Completion
Probability of Completion
M=3, V=8
M=4, V=8
M=5, V=8

Figure

19. Probability of completions for various program traces and numbers of
allowed misroutes
. The cost of positive acknowledgments dominates the cost of detour construction, suggesting
the use of low values of K, preferably
. Configurable flow control enables substantial performance improvement over PCS for low to
modest number of faults since the majority of traffic is in the fault-free portions, realizing
close to WS performance.
. For low to modest number of faults, the performance cost of recovery mechanisms is relatively
low.
. At very high fault rates, we still must use more conservative protocols to ensure reliable message
delivery and application program completion.
Conclusions
Routing in the presence of faults demands a greater level of flexibility than required in fault-free
networks. However, designing routers based on the relatively rare occurrence of faults,
requires that all message traffic be penalized: even the messages that route through the fault-free
portions of the network. Overhead may arise due to the setting up of a fault-free path prior to data
transmission (PCS), marking processors, and channels faulty to construct convex fault regions
[4,5], or increasing the number of virtual channels for routing messages around the faulty components
[4].
From low to moderate number of faults, configurable flow control mechanisms can lead to
deadlock-free fault-tolerant routing protocols whose performance is superior to more conservative
routing protocols with comparable reliability. In a network with a large number of faults, TP's
partially optimistic behavior results in a severe performance degradation. With conservative routing
protocols, no network resources are reserved until a path has been setup between the source
and the destination. TP does not require any complex renumbering scheme to provide fault-tolerance
[19,20], does not require the construction of convex regions [4,5], does not require additional
virtual channels [4], and the dynamic fault-tolerant version of TP does not rely on time-outs [11]
or padding of messages [22]. It does, however, result in a more complex channel model which can
affect link speeds.
The router designed to support TP requires only slightly more hardware than a router supporting
PCS [1], making the implementation very feasible. Current efforts are redesigning the PCS
router for support of TP protocols. It is however apparent that one of the most important performance
issues is a more efficient mechanism for implementing the positive/negative acknowledg-
ments. We are currently evaluating an implementation that adds a few control signals to the
physical channel, modifying the physical flow control accordingly (the logical behavior remains
unchanged). By implementing acknowledgment flits in hardware, we hope to extend the superior
low load performance of TP to significantly higher number of faults.



--R


DISHA: An efficient fully adaptive deadlock recovery scheme.
A comparison of adaptive wormhole routing algorithms.




The reliable router: A reliable and high-performance communication substrate for parallel computers

High performance bidirectional signalling in VLSI systems.
A theory of fault-tolerant routing in wormhole networks
A new theory of deadlock-free adaptive routing in wormhole networks
Scouting: Fully adaptive
Computer Systems Performance Evaluation.


The effects of faults in multiprocessor net- works: A trace-driven study
Adaptive routing protocols for hypercube interconnection networks.
The turn model for adaptive routing.

Cray T3D: A new dimensions for cray research.
Compressionless routing: A framework for fault-tolerant routing
A fault-tolerant communication scheme for hypercube computers

Machine abstractions and locality issues in studying parallel systems.
--TR

--CTR
Dong Xiang, Fault-tolerant routing in hypercubes using partial path set-up, Future Generation Computer Systems, v.22 n.7, p.812-819, August 2006
Dong Xiang , Ai Chen , Jiaguang Sun, Fault-tolerant routing and multicasting in hypercubes using a partial path set-up, Parallel Computing, v.31 n.3+4, p.389-411, March/April 2005
multiphase routing;multicomputer;fault-tolerant routing;pipelined interconnection network;message flow control;virtual channels;wormhole switching;routing protocol