1. If a header encounters a faulty component, messages must employ nonminimal routing. Misrouting must be controlled so that livelock is avoided and newly introduced dependencies do not produce deadlock among messages in the network. Typically this can be achieved with additional routing resources (e.g., virtual channels, packet buffers) and suitable routing restrictions among them. This is the minimum functionality required for tolerating static faults.

2. In the case of dynamic faults where message transmission is interrupted and message contents possibly corrupted by a component failure, recovery mechanisms must traverse and eliminate or prevent all wait chains. Otherwise it is possible that these messages will remain in the network indefinitely, occupying resources, and possibly lead to deadlock. Furthermore, some protocol is required either to recover the possibly corrupted message or to notify the source node so that a new copy of the message is transmitted.

6.4.1 Routing Algorithms Based on Local Information

Faulty components can be sidestepped by traversing a dimension orthogonal to the dimensions leading to the faulty components. Chen and Shin [53] describe such an algorithm for routing in binary hypercubes. Unlike k-ary n-cubes, messages in binary hypercubes (k = 2) need only traverse one link in each dimension (refer to the description in Chapter 1). If the source and destination node addresses differ in m bits, then the message will traverse m dimensions on a shortest path from the source to the destination. This sequence of dimensions is specified as a coordinate sequence and is represented as a list of dimensions. At an intermediate node, a dimension that is not on the shortest path to the destination is referred to as a spare dimension. When all of the shortest paths toward the destination from an intermediate node are blocked by faults, the message is transmitted across a spare dimension. The dimensions that were blocked by a fault, as well as those used as a spare dimension, are recorded in an n-bit tag maintained in the message header. Note that the size of the tag accommodates at most n − 1 faulty components. The resulting message is comprised of several components: (m, [c₁, c₂, …,c_k], message, d). The value of m represents the distance to the destination. When m = 0, the router can assert that the local PE is the destination. The tag d is initialized to zero at the source. When an intermediate node receives a message, it is forwarded along one of the dimensions in the coordinate sequence. The header is updated to decrement m and eliminate the dimension being traversed from the coordinate sequence. When blocked by faults along all of the shortest paths, the value of m is incremented, the spare dimension is added to the coordinate sequence, the tag d is updated, and the new message is misrouted along the spare dimension. This approach is (n − 1) fault tolerant. The routing algorithm is described in Figure 6.5.

In [53], the algorithm is shown to be able to route messages between any two nodes if the number of faulty components is less than n. In this case there is at least one spare dimension into the node that is nonfaulty, and the algorithm will find that spare dimension. This approach works well in high-dimensional networks. While the algorithm relies on purely local fault information, it can be extended to propagate fault information to nonneighboring nodes and to use this information effectively. Details can be found in [53].

The preceding approach relies on a fixed number of failures to guarantee message delivery, although the probability of delivery with values of f > n is shown to be very high [53]. An alternative to deterministic approaches is the use of randomization to produce probabilistically livelock-free, nonminimal, fault-tolerant routing algorithms. The intuition behind the use of randomization is that repetitive sequences of link traversals typical of livelocked messages are avoided with a high probability. The thesis is that this can be achieved without the higher overhead costs in header size and routing decision logic of deterministic approaches to livelock freedom.

The Chaos router incorporates randomization to produce a nonminimal fault-tolerant routing algorithm using VCT switching. The use of VCT switching in conjunction with nonminimal routing and randomization is proposed as a means to produce very high-speed, reliable communication substrates [187, 188, 189]. In chaotic routing, messages are normally routed along any profitable output channel. When a message resides in an input buffer for too long, blocked by busy output buffers, it is removed from the input buffer and stored in a local buffer pool. Messages in the local buffer pool are given a higher priority when output buffers become free, and messages from this pool are periodically reinjected into the network. In principle, if we have infinite storage at a node, removal of messages after a timeout breaks any cyclic dependencies and therefore prevents deadlock. In reality, the size of the buffer pool at a node is finite and is implemented as a queue. When this queue is full and a message must be stored in the queue, a random message is selected and misrouted. This is sufficient to prevent deadlock. However, livelock is still a source of concern. The key idea here is that a message has a nonzero probability of avoiding misrouting. This is in contrast to deterministic approaches, where given a specific router state, one fixed message is always selected for misrouting. The analysis of chaotic routing shows that the probability of infinite length paths approaches 0. Thus if a link is faulty, all messages using that link will be forwarded along other profitable links or misrouted around the faulty region.

Figure 6.7 provides a simplified illustration of the operation of a channel along a dimension using chaos routing. Each channel supports one input frame and one output frame to an adjacent router. Messages appearing in the input frames can be routed along any free profitable output dimension if the corresponding output frame is free. If the message in the input frame cannot be forwarded, then it is stored in the local queue. If the queue is full, then a random message must be removed from the queue and misrouted. In this case, some output frame must be guaranteed to become free. The deroute buffers associated with the input frames ensure that this is indeed the case. This works as follows. When the message in input frame i in node P cannot be forwarded and the queue is full, that message is moved to the associated deroute buffer. We know that by freeing an input frame along channel i, node P can receive a message from node Q. This permits progress in node Q’s queue, and therefore the input frame i in node Q can be emptied. Consequently, the output frame i in node P can be emptied and can accommodate a message from the queue, and the rerouted message in the deroute buffer i can find its way into the queue. An alternative view toward understanding chaotic routing is to note that all six buffers across a dimension (e.g., as shown in Figure 6.7) cannot be occupied by messages concurrently. If dimensions are served in a round-robin manner, then one output frame will eventually become free, permitting movement of messages from the queue to output frames, and therefore from input frames to output frames or the queue. Finally, we note that whenever an output frame becomes free, messages in the queue have priority over messages in the input frame. This exchange protocol across the channel guarantees deadlock freedom. A detailed description of the Chaos router can be found in Chapter 7.

If an adjacent channel is diagnosed or inferred as being faulty, the corresponding output frame will not empty. This frame is effectively unavailable, and packets attempting to use this channel are naturally rerouted. There is the problem of recovering the packet that is in the output frame at the time the adjacent router has been diagnosed as faulty. Subsequent efforts have focused on augmenting the natural fault tolerance of chaotic routing with more efficient schemes that avoid losing a packet [356].

6.4.2 Routing Algorithms Based on Nonlocal Information

The preceding approaches assumed the availability of only local information with respect to faulty components—neighboring links and nodes. The greater the extent of the fault information that is available at a node, the more efficient routing decisions can be. Assume that each node has a list of faulty links and nodes within a k-neighborhood [198], that is, all faulty components within a distance of k links. The preceding routing algorithm might be modified as follows. Consider an intermediate node X = (x_n–1, x_n–2, …,x₁, x₀) that receives a message with a coordinate sequence (c₁, c₂, …, c_r) that describes the remaining sequence of dimensions to be traversed to the destination. From the coordinate sequence we can construct the addresses of all nodes on a minimum-length path to the destination. For example, from intermediate node 0110, the coordinate sequence (0, 2, 3) describes a path through nodes 0111, 0011, and 1011. By examining all possible r! orderings of the coordinate sequence, we can generate all paths to the destination. If the first k elements of any such path are nonfaulty, the message can be forwarded along this path. The complexity of this operation can be reduced by examining only the r disjoint paths to the destination. These disjoint paths correspond to the following coordinate sequences: (c₁, c₂, …, c_r), (c₂, c₃, …, c_r, c₁), (c₃, c₄, …, c_r, c₁, c₂), and so on.

Rather than explicitly maintaining a list of faulty components in a k-neighborhood, an alternative method for expanding the extent of fault information is by encoding the state of a node. Lee and Hayes [198] introduced the notion of unsafe node. A nonfaulty node is unsafe if it is adjacent to two or more faulty or unsafe nodes. Each node now maintains two lists: one of faulty adjacent nodes and one for unsafe adjacent nodes. With a fixed set of faulty components, the status of a node may be faulty, nonfaulty, or unsafe. The status can be computed for all nodes in parallel in O(log³ N) steps for N nodes. Each node examines the state of its neighbors and changes its state if two or more are unsafe/faulty. A node need only transmit state information to the neighboring nodes if the local state has changed. This labeling algorithm will produce rectangular regions of nodes marked as faulty or unsafe. Figure 6.8 shows an example of the result of the labeling process in a 2-D mesh.

With fault distributions encoded in the state of the nodes, the approach toward routing now can be further modified. The unsafe status of nodes serves as a warning that messages may become trapped or delayed if routed via these nodes. Therefore, the routing algorithm is structured to first route a message to an adjacent nonfaulty node on a shortest path to the destination. If such a node does not exist, the message is routed to an unsafe node on a shortest path to the destination. If no such neighboring node can be found, then the message is misrouted to any adjacent nonfaulty node. By construction, in binary hypercubes every nonfaulty and unsafe node must be connected to at least one nonfaulty node if the number of faulty components is less than . This is not necessarily true for lower-dimensional networks such as meshes, as shown in Figure 6.9. This algorithm is summarized in Figure 6.10. In this paradigm, since functioning nodes can be labeled as unsafe, messages may originate from or be destined to unsafe nodes. Step 2 of the algorithm ensures that such messages can be delivered. The overall structure of the algorithm is such that paths are generally constructed through fault-free nodes and around regions of unsafe and faulty nodes. An example of such routing around the rectangular fault regions that occur in 2-D meshes is shown in Figure 6.9. Note how paths between unsafe nodes are constructed.

The concept of a safe node captures the fault distribution within a neighborhood. A node is safe if all of the neighboring nodes and links are nonfaulty. This concept of safety can be extended to capture multiple distinct levels of safety in binary hypercubes [351]. A node has a safety level of k if any node at a distance of k can be reached by a path of length k. Safety levels can be viewed as a form of nonlocal state information. The location and distribution of faults is encoded in the safety level of a node. The exact locations of the faulty nodes are not specified. However, in practice, knowledge of fault locations is for the purpose of finding (preferably) minimal-length paths. Safety levels can be used to realize this goal by exploiting the following properties. If the safety level of a node is S, then for any message received by this node and destined for a node no more than distance S away, at least one neighbor on a shortest path to the destination will have a safety level of (S − 1). The neighbors on a shortest path to the destination will be referred to as preferred neighbors [351] and the remaining neighbors as spare neighbors. Clearly, if the message cannot be delivered to the destination, the safety levels of all of the preferred neighbors will be < D − 1, where D is the distance to the destination, and that of the spare neighbors will be < D. Once the safety levels have been computed for each node, a message may be routed using the sequence of steps shown in Figure 6.11.

A faulty node has a safety level of 0. A safe node has a safety level of n (the diameter of the network). All nonfaulty nodes are initialized to a safety level of n. The levels of the other nodes are determined by the locations of faulty nodes. Intuitively, for a node to have a safety level of k, no more than (n – k − 1) neighbors can have a safety level of less than (k − 1). This will guarantee that for any incoming message destined to traverse k additional links, at least one neighbor along a preferred dimension will have a safety level of at least k − 1. It has been shown that this property enables the computation of safety levels of all nodes in (n − 1) steps by a local algorithm that in each step updates the safety level of a node as a function of the safety level of its neighbors from the previous step.

6.4.3 Routing Algorithms Based on Graph Search

Often it is not possible to guarantee that the number of faults will be less than or the node degree. In this case, more flexible mechanisms are necessary to ensure that messages can be delivered if a physical path exists between two nodes. Routing algorithms based on graph search techniques provide the maximum flexibility. Message packets can be routed to traverse a set of links corresponding to a systematic search of all possible paths between a pair of nodes. Although the routing overhead is significant, the probability of message delivery in faulty networks is maximized. There have been several schemes for such search-based routing algorithms (e.g., [52, 62]). In the following we describe a fault-tolerant packet routing algorithm based on a depth-first traversal of binary hypercubes [52]. While specific computations may differ, the paradigm is certainly applicable to other point-to-point networks employing SAF or VCT switching mechanisms.

A major issue with exhaustive traversals of graphs or networks is that of visiting a node more than once. In the context of routing message packets in multipath networks, visiting a node more than once results in unnecessary overhead. Most approaches utilize state information maintained in the message header to avoid redundant visits. Consider a message structured as (R, TD, message) [52]. R is an n-bit vector that serves as the routing tag. If bit i in R is set, the message must traverse dimension i. When R = 0, the message has arrived at its destination. TD is the set of dimensions that the message has traversed. It is initialized to 0 at the source. As the message progresses through intermediate nodes, R and TD are updated. Routing at an intermediate node proceeds in three steps. First, the message is transmitted along a link on the shortest path to the destination. If all such paths are blocked by faulty components, the message must be misrouted to a neighboring node. However, we wish to avoid visiting any node more than once. This is realized as follows. In general, given an initial node, and a sequence of dimensions, c₁, c₂, …, c_k, we can determine all of the nodes on the path from the source that are visited by traversing these dimensions. For example, starting from node 0110, a message traversing the dimensions 0, 2, and 3 will visit nodes 0111, 0011, and 1011, respectively. When a message is blocked by faults at an intermediate node, the list of dimensions traversed by the message up to this point can be used to compute the addresses of all of the nodes that have been visited by this message. Any adjacent nodes that belong in this set of nodes are no longer candidates for receiving the misrouted message. If all adjacent nodes have been visited or remain blocked by faults, the message backtracks to the previous node. Figure 6.13 shows an example of a search tree (i.e., sequence of nodes) generated by a message transmitted from node 0010 to node 1101. An algorithmic description of a routing algorithm based on depth-first search is provided in Figure 6.14. Optimizations to improve the efficiency of this implementation can be found in [52]. As in related approaches, each misrouting step lengthens the path between source and destination by two hops.

Related algorithms that are also based on depth-first search, but differing in some of the optimizations, can be found in [26, 28]. In particular, [28] describes an algorithm based on concurrent consideration of diagnosis and routing. The routing algorithm can proceed concurrently with on-line diagnosis of faulty nodes and links. The diagnosis algorithm is based on k-reachability and propagates fault information within a k-neighborhood. The approach is to devise a routing algorithm that can make use of concurrently available, and evolving, diagnostic information. As a result the initial message is injected into the network with a specification of the complete path from source to destination stored in the header. If no faults are encountered, the message is successfully routed to the destination along this path. At some intermediate node it may become evident that a node or link along this path has become faulty. This information may have just become available after the message has left the source. The intermediate node attempts to produce a new feasible path to the destination based on this updated diagnostic information. If such a path is not available and the message cannot be forwarded, the message is returned to the previous node on the path (i.e., a backtracking operation takes place). The routing algorithm is again invoked at this node. If the message is backtracked to the source, then it cannot be delivered. The result is an approach that produces a cooperative relationship between on-line k-reachability diagnosis and fault-tolerant routing.

The hyperswitch [62] is an adaptively routed network that supports circuit and packet switching and a set of backtracking routing algorithms for searching the network for uncongested and fault-free paths. The routing algorithm implemented by the hyperswitch is a best-first search heuristic. The routing probes for circuit-switched messages and the headers for packet-switched messages can be subjected to the same routing algorithm. Rather than an exhaustive depth-first search of the binary hypercube, the header maintains a channel history tag. The tag has n bits and records dimensions across which a header has backtracked. It can also be regarded as a record at a node of the dimensions across which a header has unsuccessfully tried to find a path. When a backtracking header is received and forwarded across another dimension at an intermediate node, the channel history tag is forwarded along with the message. The setting of the dimensions in this tag prevents the message from making traversals along certain dimensions and therefore revisiting portions of the network that may already have been searched. Effectively, portions of the search tree shown in Figure 6.13 are pruned. In Example 6.4, when the header backtracks to node 0011, the channel history tag might be set to 0010 and forwarded along with the message to node 0111. This will prevent the message from traversing dimension 1 at node 0111, and the header will be routed to node 1111 and then onto node 1101. The hyperswitch routing algorithm is programmable and can alternatively implement an exhaustive search or a hybrid search. In a hybrid search, the routing algorithm performs an exhaustive search when the message is within a specified distance from the destination. The hybrid approach is used to prevent excessive (and unnecessary) backtracking in large networks when the message is far from the destination. The trade-off is between the probability of finding a path versus finding a longer path via backtracking.

6.4.4 Deadlock and Livelock Freedom Issues

In the description of the preceding SAF techniques, deadlock freedom was not discussed. With the exception of [198], the original descriptions did not directly address deadlock freedom. For SAF networks in general, there are standard techniques for resolving the issue of deadlock freedom, some of which were described in Chapter 3. The preceding routing algorithms could adopt the following approach. The message buffers within each router are partitioned into B classes. These classes are placed in a strict order (a partial order actually will suffice). For example, if the number of buffer classes is the same as the maximum path length of any message, then as messages are routed between nodes, they are constrained to occupy a buffer in a class equal to the distance traversed to that point. With a known maximum distance and a corresponding number of buffers at each node, buffers are occupied in strictly increasing order and deadlock is prevented. The approach described in [198] produces maximum path lengths of (n + 1), and thus (n + 2) buffer classes would suffice. Typically, maximum path lengths, and therefore buffers at a node, depend upon the maximum number of faults. For routing algorithms based on graph search algorithms, the extent of the search would have to be controlled to bound the maximum path length, as a compromise between the probability of finding a path between any two nodes and the amount of buffer space required for deadlock freedom.

It is evident that fault-tolerant routing requires some form of misrouting to avoid faulty components. However, when messages are permitted to be routed farther away from the destination, the possibility of livelock must be addressed. The preceding techniques utilize deterministic approaches to prevent livelock by incorporating history information into the message header. A record of the history of the message is used in conjunction with knowledge of the structure of the network to bound the lifetime of a message packet in the network. The basic paradigm is one wherein the number of options for a message are guaranteed to be finite, and the routing algorithm ensures progress in exploring all of the options. A finite number of options can be created by using history information to ensure that nodes and links cannot be repeatedly visited by a message.

6.5.1 Rectangular Fault Regions

Consider the simplest fault model: block faults in a 2-D mesh network using the e-cube routing algorithm. Fault-free messages are routed in dimension order. When a block fault is encountered, the desired behavior of the routing algorithms is as shown in Figure 6.15. The e-cube path of the message from node S to node D passes through the block fault region, and one alternative (nonminimal) path for the message is as shown in the figure. However, traversal of this path would require messages to be routed from a column to a row (e.g., at point T in Figure 6.15). E-cube remains deadlock-free by preventing messages from traversing a row after traversing a column. Such traversals introduce new dependencies between channels in the vertical and horizontal direction, introduce cycles in the channel dependency graph, and therefore could lead to deadlocked message configurations. A solution to this problem for 2-D mesh networks proposed by Chien and Kim [58] is planar-adaptive routing, which was described in Section 4.3.1. This approach adds one additional virtual channel in the vertical direction. Now the set of virtual channels can be partitioned into two virtual networks as shown in Figure 6.16: the increasing network and the decreasing network. In the increasing (decreasing) network messages only travel in increasing (decreasing) X coordinates. The message shown in Figure 6.15 will be routed in the increasing virtual network. When the fault region is encountered, the message can be routed in the vertical direction to the top (or bottom) of the fault region. At this point the message may continue its progress in the horizontal direction.

Consider the example shown in Figure 6.15 where the message uses the increasing network. Assume the virtual channel 0 is used in the Y direction in the increasing network.

Since the fault regions are rectangular, messages only travel though intermediate nodes with nondecreasing values of the X coordinate. Further, if fault regions do not include boundary nodes, the ability to “turn the corner” around the fault region is guaranteed, and messages traverse any given column in only one direction; that is, there are no dependencies between the channels d_1,0+ and d_1,0– (see Section 4.3.1 for notation). Thus, there are no cyclic dependencies among the channels in the Y direction. Since channels in the X direction are strictly in increasing coordinates, there can be no cyclic channel dependencies involving both X and Y channels. A similar argument can be made for the decreasing network. Since messages only travel in one network or the other, routing is deadlock-free.

The preceding technique is very powerful and can be extended in several ways. Since the networks are acyclic, messages can be adaptively routed [58] along shortest paths: at an intermediate node, a message may be routed along either dimension. The only case where a message will be misrouted is when the destination node is in the same column or row, and the message is blocked by a fault region. As the preceding discussion demonstrated, routing remains deadlock-free. The technique can also be extended to multidimensional meshes using planar-adaptive routing. Recall from Section 4.3.1 that in planar-adaptive routing messages are adaptively routed in successive planes A_i formed by two dimensions, d_i and di₊₁. When fault regions are constrained to be block faults, any two-dimensional cross section of the fault region will form a rectangular fault region and will appear as shown in Figure 6.15.

Note that when messages reduce the offset in dimension d_i to 0, they are routed in the next adaptive plane. As a consequence, messages cannot be blocked by a fault region in dimension d_i+1 after having reduced the offset in dimension di to zero. Therefore, messages are misrouted in only one dimension at a time. Since traffic in distinct adaptive planes that traverse the same physical link travel along separate virtual channels, and misrouting occurs only within one adaptive plane before messages are routed in the next adaptive plane, deadlock freedom is preserved. An algorithmic description of fault-tolerant planar-adaptive routing is provided in Figure 6.17.

The preceding techniques can be extended to tori as follows. Two virtual channels are required for each physical link to break the physical cycles created by the wraparound connections in the network. A solution for tori can be obtained simply by replacing each virtual channel in the mesh solution by two virtual channels. All of the arguments that characterize and demonstrate deadlock freedom for the mesh solution now apply to toroidal networks with appropriate routing restrictions over the wraparound channels to break the physical cycles. This solution requires six virtual channels for each physical channel.

The preceding techniques do encounter problems when fault regions occur adjacent to each other or include nodes on the boundary, as shown in Figure 6.18. When messages being misrouted around a fault region reach a boundary node such as R, the direction of the message has to be reversed. This introduces dependencies from channels d_{i, j} + to d_{i, j} – and vice versa, creating cyclic dependencies among the virtual channels in dimension j and cycles in the channel dependency graphs of the increasing and decreasing networks. The reason can be understood by observing that, logically, nodes on the boundary of a mesh are adjacent to a fault region of infinite extent. Messages cannot be routed around this fault region. The situation is equivalent to the occurrence of a concave fault region. Adjacent fault regions produce similar concavities as shown at node S. In the presence of concavities, paths in a 2-D mesh that are traversed by messages misrouted due to faults lose two important properties: (1) the X coordinate is no longer monotonically increasing or decreasing, and (2) new dependencies are introduced between channels in the vertical direction, producing cycles in the channel dependency graph. Ensuring that fault regions remain convex will require marking fault-free nodes as faulty. In this example, construction of a rectangular fault region will necessitate marking the first five rows of nodes in Figure 6.18 faulty. Similar examples can be constructed for the multidimensional case. This is clearly an undesirable solution and motivates solutions that make more efficient use of nonfaulty nodes.

One such approach to reduce the number of functional nodes that must be marked as faulty was introduced by Chalasani and Boppana [49] and builds on the concept of fault rings to support more flexible routing around fault regions. Intuitively a fault ring is the sequence of links and nodes that are adjacent to and surround a fault region. Rectangular fault regions will produce rectangular fault rings. Figure 6.19 shows an example of two fault rings and a fault chain. If a fault region includes boundary nodes, the fault ring reduces to a fault chain. The key idea is to have messages that are blocked by a fault region misrouted along the fault rings and fault chains. For oblivious routing in 2-D meshes with nonoverlapping fault rings, and with no fault chains, two virtual channels suffice for deadlock-free routing around fault rings. These two channels form two virtual networks C₀ and C₁, each with acyclic channel dependencies, and messages travel in only one network (see Exercise 6.1).

However, this solution is inadequate in the presence of overlapping fault rings and fault chains. The reason is that the two virtual networks are no longer sufficient to remove cyclic dependencies between channels. Messages traveling in distinct fault rings share virtual channels as shown in Figure 6.19. As a result additional dependencies are introduced between the two virtual networks, leading to cycles. Furthermore, the occurrence of fault chains may cause messages that are initially routed toward the boundary nodes to be reversed. If we employed fault-tolerant planar-adaptive routing, such occurrences would introduce dependencies between the d_1,0+ and d_1,0– virtual channels in dimension 1, creating cyclic dependencies between them.

The solution proposed by Chalasani and Boppana [49] is to provide additional virtual channels to create disjoint acyclic virtual networks. The effect is to separate the traffic of the two fault rings that traverse the shared links. This can be achieved by providing two additional virtual channels per link, for a total of four virtual channels over each physical channel. Label these virtual channels c₀, c₁, c₂, and c₃. We may construct four virtual networks, each comprised of virtual channels of each type. Messages are assigned types based on the relative positions of the source and destinations and dimension-order routing. In a 2-D mesh, messages are typed as east-west (EW), west-east (WE), north-south (NS), or south-north (SN) based on the relative values of offsets in the first dimension. Routing is in dimension order until a message encounters a fault region. Depending on the type, the message is routed around the fault region as shown in Figure 6.20. The direction around the fault region is selected based on the relative position of the destination node. The WE messages use the c₀ channels, with the remaining messages using the other channels as shown. The EW and WE messages may become NS and SN messages. However, the converse is not true. Thus, dependencies between channel classes are acyclic. Since fault regions are rectangular, dependencies within a fault region are also acyclic—the arguments are similar to those provided for fault-tolerant planar-adaptive routing. A brief description of the routing algorithm is presented in Figure 6.21.

The extension to fully adaptive routing can be performed in a straightforward manner. Assume the existence of any base, fully adaptive routing algorithm and the associated set of virtual channels. The only instance in which the progress of an adaptively routed message is impeded is when the message need only be routed in the last dimension, and progress in this dimension is blocked by a fault region. In this case, with four additional virtual channels, the preceding solution for oblivious routing can be applied. There is no real loss in adaptivity since the message has only one dimension that remains to be traversed. This approach effectively adds four virtual channels to support oblivious routing around fault regions, and transitions to this solution as a last resort. Once a message enters these virtual channels, it remains in these channels until it is delivered to the destination.

If fault rings do not overlap, the above approach is easily extended to fully adaptive routing in tori with the following simple modification. Let us assume there exists a base set of virtual channels that provides fully adaptive deadlock-free routing in 2-D meshes. From the preceding discussion, four additional virtual channels are provided for routing around the fault rings [50], creating the four virtual networks. From Figure 6.20 it is apparent that the channel dependency graph of virtual channels within each of the virtual networks is acyclic. The presence of wraparound channels in the torus destroys this property. The cyclic dependencies introduced in the torus can be eliminated through the use of routing restrictions. Messages traveling in a virtual network are further distinguished by whether or not they will traverse the wraparound channel. These messages are routed in opposite directions around the fault region: messages that will (not) travel along the wraparound channel are routed in the counterclockwise (clockwise) direction around the fault region. Thus, the channel resources used by the message types are disjoint, and cyclic dependencies are prevented from occurring between them. The routing algorithm is essentially the same as the extension to fully adaptive routing in 2-D meshes, modified to pick the correct orientation around the fault ring when a message is blocked by a fault.

However, if fault rings in tori overlap, then messages that use the wraparound links share virtual channels with messages that do not use the wraparound links. This sharing occurs over the physical channels corresponding to the overlapping region of the fault rings. The virtual networks are no longer independent, and cyclic dependencies can be created between the virtual networks and, as a result, among messages. It follows from the preceding discussion that four more virtual channels [37] can be introduced across each physical link, creating four additional networks to further separate the message traffic over shared links. This is a rather expensive solution. The alternative is to have the network functioning as a mesh. In this case the benefits of a toroidal connection are lost.

A different labeling procedure is used in [43] to permit misrouting around rectangular fault regions in mesh networks. Initially fault regions are grown in a manner similar to the preceding schemes, and all nonfaulty nodes that are marked as faulty are labeled as deactivated. Nonfaulty nodes on the boundary of the fault region are now labeled as unsafe. Thus, all unsafe nodes are adjacent to at least one nonfaulty node. An example of faulty, unsafe, and deactivated nodes is shown in Figure 6.23. There are three virtual channels traversing each physical channel. These virtual channels are partitioned into classes. Nodes adjacent to only nonfaulty nodes have the virtual channels labeled as two class 1 channels and one class 2 channel. Nodes adjacent to any other node type have the channels partitioned into class 2, class 3, and class 4 channels. In nonfaulty regions of the network, a message may traverse a class 1 channel along any shortest path to the destination. If no class 1 channel is available, class 2 channels are traversed in two phases. The first phase permits dimension-order traversal of positive direction channels, and in the second phase negative direction class 2 channels can be traversed in any order (i.e., not in dimension order). The only time the fully adaptive variant of this algorithm must consider a fault region is when the last dimension to be traversed is blocked by a fault region necessitating nonminimal routing. Dimension (i + 1) and dimension i channels are used to route the message around the fault region. Messages first attempt routing along a path using class 3 channels and class 2 channels in the positive direction. Subsequently messages utilize class 4 channels and class 2 channels in the negative direction. Note that class 3 and class 4 channels only exist across physical channels in the vicinity of faults. The routing restrictions prevent the occurrence of cyclic dependencies between the channels, avoiding deadlock.

The paradigm adopted throughout the preceding examples has been to characterize messages by the direction of traversal in the network and therefore the direction and virtual channels occupied by these messages when misrouted around a fault ring. The addition of virtual channels for each message type ensures that these messages occupy disjoint virtual networks and therefore channel resources. Since the usage of resources within a network is orchestrated to be acyclic and transitions made by messages between networks remain acyclic, routing can be guaranteed to be deadlock-free. However, the addition of virtual channels affects the speed and complexity of the routers. Arbitration between virtual channels and the multiplexing of virtual channels across the physical channel can have a substantial impact on the flow control latency through the router [57]. This motivated investigations of solutions that did not rely on many (or any) virtual channels.

Origin-based fault-tolerant routing is a paradigm that enables fault-tolerant routing in mesh networks under a similar fault model, but without the addition of virtual channels [145]. The basic fault-free form of origin-based routing follows the paradigm of several adaptive routing algorithms proposed for binary hypercubes and the turn model proposed for more general direct network topologies. Each message progresses through two phases. In the first phase, the message is adaptively routed toward a special node. On reaching this node, the message is adaptively routed to the destination in the second phase. In previous applications of this paradigm to binary hypercubes, this special node could be the zenith node whose address is given by the logical OR of the source and destination addresses. Messages are first routed adaptively to their zenith and then adaptively toward the destination [184]. This phase ordering prevents the formation of cycles in the channel dependency graphs. Variants of this approach have also been proposed, including the relaxation of ordering restrictions on the phases [59]. In origin-based routing in mesh networks this special node is the node that is designated as the origin according to the mesh coordinates. While the approach is directly extensible to multidimensional networks, the following description deals with 2-D meshes.

All of the physical channels are partitioned into two disjoint networks. The IN network consists of all of the unidirectional channels that are directed toward the origin, while the OUT network consists of all of the unidirectional channels directed away from the origin. The orientation of a channel can be determined by the node at the receiving end of the channel. If this node is closer to the origin than the sending end of the channel, the channel is in the IN network. Otherwise it is in the OUT network. The outbox for a node in the mesh is the submesh comprised of all nodes on a shortest path to the origin. An example of an outbox for a destination node D is shown in Figure 6.24. Messages are routed in two phases. In the first phase messages are routed adaptively toward the destination/origin, over any shortest path using channels in the IN network. When the header flit arrives at any node in the outbox for the destination, the message is now routed adaptively toward the destination using only channels in the OUT network. As shown in the example in Figure 6.24, the resulting complete path may not be a minimal path. The choice of minimal paths is easily enforced by restricting messages traversing the IN network to use channels that take the message closer to the destination. The result of enforcing such a restriction on the same (source, destination) pair is also shown in Figure 6.24. The choice of the origin node is important. Since all messages are first routed toward the origin, hot spots can develop around the origin. Congestion around the origin is minimized when it is placed at one of the corners of the mesh. In this case, origin-based routing is equivalent to the negative-first algorithm derived from the turn model. We know from Chapter 4 that such routing algorithms are only partially adaptive. Placing the origin at the center improves adaptivity, but increases hot spot contention in the vicinity.

The fault-tolerant implementation of origin-based routing requires the fault regions to be square. Square regions are formed by starting from the rectangular fault regions created by preceding techniques and disabling additional nodes to ensure that the fault regions are square. A final step in setting up the mesh is for each nonfaulty node to compute and store the distance to the nearest fault region in the north, south, east, and west directions. The time required to compute this information and form the square fault regions depends on the network size, thus being bounded by the diameter of the mesh. Finally an origin node is selected such that the row and column containing the origin has no faulty nodes. If this is not possible, these techniques can be applied to the largest fault-free submesh, disabling all remaining nodes. Central to this routing algorithm is the identification of a set of nodes in the diagonal band of the destination. The diagonal band of a node s is the set of all nodes in the outbox of s that lie on a tridiagonal band toward the origin. The X andY offsets from node s to any node in the diagonal band differ by at most 1. An example of a diagonal band is shown in Figure 6.25. The useful property of nodes in the diagonal band is that there exists a fault-free path from any one of these nodes to the destination node using channels in the OUT network [145]. Such nodes are referred to as safe nodes. The property of safety of nodes in the diagonal band is ensured by square fault regions. If fault regions are square, then any message at a safe node that is blocked by a fault region is guaranteed the existence of a path around the fault region, through nodes within the outbox, and reaching a destination node on the other side of the fault region. Square fault regions guarantee the safety of nodes in the diagonal band.

Fault-tolerant routing proceeds as follows. A message is routed adaptively as before in the IN network toward the origin until it arrives at a node in the outbox of the destination or the origin (by definition the origin is in the outbox of the destination). Since the origin is in a fault-free column/row and fault regions are square, a free output channel in the IN network is guaranteed to exist during this phase. Once the message arrives at a node in the outbox of the destination, if the message is at a safe node, then a path is guaranteed to be available to the destination using only channels in OUT. If the message is not at a safe node, routing continues in the IN network. At an intermediate node the distance to the nearest safe node in each direction can be computed. This is compared to the distance of the nearest fault in that direction. If the safe node is closer than fault regions, the message is routed to that node using only channels in IN or OUT. By virtue of their construction, safe nodes guarantee the availability of paths by routing around fault regions. If the message encounters a fault region, it can be routed around the fault region until it can be routed back up to the diagonal band. This case is illustrated in Figure 6.25.

Routing occurs in three phases with three successive goals: (1) route to the outbox, (2) route to a safe node in the outbox, and (3) route to the destination. This technique can be applied to meshes in the absence of virtual channels. Other optimizations such as increasing the size of the safe region in the outbox and trading adaptivity for simplicity and speed are described in [145]. A functional description of the algorithm is shown in Figure 6.26.

Rectangular and square fault regions provide some form of nondecreasing property in coordinates of misrouted messages. This property is exploited to prevent the occurrence of deadlocked message configurations. However, the construction of rectangular fault regions by the marking of fault-free routers and links as faulty can lead to significant underutilization of resources. While permitting arbitrary fault patterns is still an elusive goal, it would be desirable to relax the restrictions on the shape of the fault regions.

To help achieve this goal, the concept of fault rings can be extended in a minimal manner to account for certain classes of nonconvex fault regions [50]. Consider the class of fault regions in n-dimensional mesh networks where any 2-D cross section of the fault region produces a single rectangular fault region. Such a fault model is referred to as a solid fault model [50]. Figure 6.27 provides an example of a nonconvex fault region that follows the solid fault model, and a message being routed along a fault ring around the fault region. As in previous techniques, for nonoverlapping fault rings and nonfaulty boundary nodes, message types are distinguished by the relative position of the destination when the message is generated. For deterministic routing, we initially have EW and WE messages. When the message eventually arrives at the destination column, the message type is changed to NS or SN depending on the relative location of the destination. When a message encounters a fault, the rules for routing the message along the fault ring are shown in Table 6.2. There are four virtual channels over each physical channel: c₀, c₁, c₂, and c₃. As in preceding techniques, each set of channels implements a distinct virtual network.

If a message must travel along a fault ring before encountering a fault region (i.e., as shown in Figure 6.27 at node A), then the message must continue to be routed in the same direction along the fault ring. Otherwise the message follows the direction stated in Table 6.2. Each message type is routed in a distinct virtual network. From the routing rules we can observe that the channel dependency graph within a virtual network is acyclic.

Further, messages can only transition from WE or EW channels to NS or SN channels but not vice versa. Thus, the relation between these virtual networks remains acyclic, and therefore routing remains deadlock-free. Note that these rules apply to rings that do not overlap and that do not include nodes on the boundary of the mesh.

6.5.2 Software-Based Fault-Tolerant Routing

The addition of virtual channels and enforcement of routing restrictions between them impacts the design and implementation of the routers. However, in environments where the fault rates are relatively low, the use of expensive, custom, fault-tolerant routers often cannot be justified. Moreover, contemporary routers are compact, oblivious, and fast. Ideally, we wish to retain these features and minimize both the additional hardware support required in the routers and the impact on the router performance. It would also be advantageous to employ techniques that would not require expensive modifications to the routing control to implement rerouting restrictions. The development of these techniques is governed by the relationship between the MTBF and the MTTR. When MTTR MTBF, the number of faulty components in a repair interval is small. In fact, the probability of the second or the third fault occurring before the first fault is repaired is very low. In such environments, software-based rerouting can be a cost-effective and viable alternative [333].

The software-based approach is based on the observation that the majority of messages do not encounter faults and should be minimally impacted, while the relatively few messages that do encounter faults may experience substantially increased latency, although the network throughput may not be significantly affected. The basic idea is simple. When a message encounters a faulty link, it is removed from the network or absorbed by the local router and delivered to the messaging layer of the local node’s operating system. The message-passing software either (1) modifies the header so that the message may follow an alternative path or (2) computes an intermediate node address. In either case, the message is reinjected into the network. In the case that the message is transmitted to an intermediate node, it will be forwarded upon receipt to the final destination. A message may encounter multiple faults and pass through multiple intermediate nodes. The issues are distinct from adaptive packet routing in networks using packet switching or VCT switching. Since messages are routed using wormhole switching, rerouting algorithms and the selection of intermediate nodes must consider dependencies across multiple routers caused by small buffers (< message size) and pipelined data flow. Since messages are reinjected into the network, dependencies are introduced between delivery channels at a router and the injection channels. These dependencies are introduced via local storage for absorbed packets. Memory allocation must ensure that sufficient buffer space can be allocated within the nodes or interfaces to avoid creating deadlock due to the introduction of these dependencies.

Since messages are removed from the network and reinjected, the problems of routing in the presence of concave fault regions are simplified. Consider the case of messages being routed obliviously using e-cube routing in a 2-D torus. Figure 6.28 illustrates an example of software-based rerouting in the presence of concave fault regions. The resulting routing algorithm has been referred to as e-sft [333]. In step 1 a message from the source is routed through an e-cube path to the destination and encounters the fault region at node A. The message is absorbed at the node, and the header is modified by the messaging layer to reflect the reverse path in the same dimension, using the wraparound channels. The message again encounters the fault region at node B and is routed to an intermediate node in the vertical direction in an attempt to find a path around the fault region. This procedure is repeated at intermediate nodes E and F before the message is successfully routed along the wraparound channels in the vertical dimension to the destination node D. While the path and the sequence of routing decisions to find the path in the preceding example are easy to convey intuitively, the messaging layer must implement routing algorithms that can implement this decision process in a fully distributed manner with only local information about faults. These rerouting decisions must avoid deadlock and livelock. This is realized through the use of routing tables and by incorporating additional information in the routing header to capture the history of encounters with fault regions by this message. The important characteristic of this approach is that messages are still routed in dimension order between any pair of intermediate nodes.

In order to keep track of the manner in which a message is rerouted, the header contains a 2-bit flag called the direction flag (DF). The DF is used to record the history of encounters with fault regions. For example, the message from S to D in Figure 6.28 will initially have a DF value of (00). When a fault region is encountered, DF is changed to (01), prior to routing in the reverse direction along the wraparound channel. Since fault-free routing is dimension order, a DF value of (10) would imply the message had attempted to traverse the X dimension in both directions and is now trying to traverse the Y dimension. The exception to this interpretation occurs when the source and destination nodes are in the same column. In this case the message will attempt the Y dimension first, and the interpretation of DF is reversed; that is, (00) and (01) ((10) and (11)) refer to the Y dimension (X dimension). A rerouted message may also encounter faults. The DF value in the header is only modified when the message is absorbed at a node. It enables e-sft routing to keep track of the directions along each dimension that have been attempted and therefore aid in rerouting decisions. There are three additional fields that are required in the header. A faulted status bit (F) indicates that the message has encountered at least one fault and is being rerouted. This bit enables a node to distinguish between messages destined for the local node and messages that must be forwarded. A prevent flag (PF) status bit is used to prevent the occurrence of certain livelock situations by recording a traversal through all DF values. A 2-bit reroute table field (RT) specifies one of three routing tables to be used for rerouting decisions. Finally, since messages may be routed through intermediate nodes, there must be two sets of address fields. The first records the final destination address (X-Final, Y-Final). This is an absolute address. The second is used for routing the messages and is an offset within each dimension (X-Dest, Y-Dest). The message header now appears as shown in Figure 6.29. Note that the routers only process the offset fields and set the F bit. All of the remaining header processing is done in software and only when messages encounter faults. Thus, router operations are minimally impacted.

Let the coordinates of the destination node be (x_d, y_d) and the current node be (x_c, y_c). The offsets to the destination at any intermediate node can be computed as Δx and Δy in each dimension. The network hardware routes messages using traditional dimension-order routing based on the X-Dest and Y-Dest fields in the message header. If the outgoing channel at a router is faulty, the router sets the F bit and routes the message to the local processor interface. This causes the message to be marked as a faulted message and ejected to the local messaging layer. If the F bit is set, the messaging software checks the X-Final and Y-Final fields to determine if the message is to be delivered locally. If the message is not to be delivered locally, a rerouting function is invoked. The X-Dest and Y-Dest fields are updated, and if necessary the DF, PF, and RT flags are modified. The initial rerouting function depends on the relative address of the first node where a fault is encountered and the final destination. Tables 6.3–6.5 describe the rerouting rules. The notation refers to the coordinates of the next node in the path using the short (i.e., s) path along the y dimension. The notation l refers to the choice of the longer path. The rerouting algorithm implemented in the messaging layer is described in Figure 6.30.

6.5.3 Unconstrained Fault Regions

Many of the early approaches to fault-tolerant routing did not adopt the approach of placing constraints on the shape of the fault regions. Rather, these techniques focused on rerouting around single faulty nodes and links. Since complete knowledge of the patterns of occurrences of faults is not assumed, these techniques are not generally applicable to cases where larger fault regions must be supported. In these instances, the routing algorithms discussed here must rely on fault recovery techniques to prevent deadlock. Consequently, guarantees of message delivery are made under conditions very different from those of the preceding techniques. However, these techniques have minimal impact on the design of the routers enabling them to remain compact and fast. Thus, they are attractive in environments with low fault rates.

The turn model described in Chapter 4 can be modified to handle the occurrence of faulty components. The example described here is the nonminimal version of the negative-first routing algorithm for 2-D meshes. Recall that this algorithm operates in two phases: the message is routed in the negative direction in each of the dimensions in the first phase, and then messages are routed in the positive directions in the second phase. The fault-tolerant nonminimal version routes adaptively in the negative direction, even farther west or south than the destination. For example, this is the path taken by message A in Figure 6.31. During this phase the message is routed adaptively and around faulty nodes or links. The exception occurs when a message being routed along the edge of the mesh in the negative direction encounters a faulty node. In the second phase, the message is routed adaptively in the positive directions to the destination, unless it reaches the destination column, in which case there is only one path to the destination. However, by permitting the message to be routed further west and south than the destination, more paths to the destination are created for the second phase, increasing the possibility that messages can be routed around a single faulty component. Modifications to the routing logic of the base negative-first algorithm are simply intended to increase the possibility of finding an alternative path when blocked by a faulty component, particularly along an edge of the mesh. The behavior that is permitted in this case is shown by message B in Figure 6.31. Such a single misroute to avoid a faulty component does avoid deadlock. The number of faults that can be tolerated is one less than the number of dimensions. This has been generalized to avoid up to (n − 1) faults in n-dimensional meshes [131]. The version of this algorithm for 2-D meshes is provided in Figure 6.32.

The advantage of this approach is that no virtual channels are required. From a practical point of view, in environments where MTTR MTBF, it is likely that no more than a single fault will occur within any repair interval. In this case the turn model approach can provide gracefully degraded communication performance in 2-D meshes until the faulty component can be replaced. Meanwhile the hardware architectures of the routers have been minimally impacted and remain compact and fast. For higher-fault-rate environments, more robust techniques that can provide delivery guarantees are desirable.

The dimension reversal (DR) approach defined by Dally and Aoki [73] produces gracefully degradable network performance in the presence of faults by dividing messages into classes. Each message is permitted to be routed in any direction. However, if a message is routed from a channel in dimension d_i to a channel in dimension d_j < d_i, a DR counter maintained in the message header is incremented. This DR counter is used to prevent the occurrence of cycles in the channel dependency graph. A static approach to doing so in multidimensional meshes creates r virtual networks by using r virtual channels across each physical channel. All messages are initialized with their DR values equal to zero. Messages are injected into virtual network 0 and permitted to be routed in any direction toward the destination. Misrouting is also permitted, although it should be controlled to ensure livelock freedom. When a dimension reversal takes place, the message moves into the next virtual network. Messages that experience greater than (r − 1) dimension reversals are routed in dimension order (i.e., deterministic, nonadaptive routing) in the last virtual network. This approach can require a large number of virtual channels.

An alternative dynamic version of this approach has only two virtual networks: the adaptive network and the deterministic network. Messages are now injected into the adaptive network. These messages can be routed in any direction using only adaptive channels and with no constraints on the number of misroutes other than those required to ensure livelock freedom. However, if a message must block waiting for a free channel at any node, the message may only block on channels being used by messages with a higher value of the DR counter. If virtual channels are labeled with the DR value of the message currently using the channel, this is easy to check. If all outgoing channels are being used by messages with lower DR values, the message enters the deterministic network, where it remains while following a fixed dimension-order path to the destination. The ordering of messages in the adaptive network prevents cycles of messages waiting on themselves. Messages only transition into the deterministic network and never the other way around. Therefore, deadlock freedom is guaranteed in the fault-free case. Previous approaches have placed strict ordering requirements on resource usage (i.e., channels) to prevent cyclic dependencies. This approach is a bit different in that the message population is partitioned into groups by virtue of the values of their DR counters. Waiting is based on the DR values of the messages rather than channels or dimensions, and messages are prevented from waiting on themselves.

The simulation results provided in [73] show graceful degradation in average message latency and network throughput with relatively high fault rates. However, in the presence of faults, deadlock may still occur. If a physical channel fails, all messages that are constrained to use the deterministic network and cross that physical channel will be blocked indefinitely. These messages cannot be delivered and can eventually lead to deadlocked configurations of messages, although the routing freedom otherwise provided by the DR scheme makes this highly unlikely. To guarantee deadlock freedom in the presence of faults, some form of fault recovery mechanism will be necessary.

A closer look at existing wormhole-switched routing algorithms can lead to several approaches to making these routing algorithms resilient to faults, although guaranteeing deadlock freedom is more difficult to achieve. Consider a minimal fully adaptive routing algorithm such as DP [91]. A simple extension permits an unprofitable adaptive channel to be used if no deterministic channel has been used by the message up to that point. This will permit the message to route around faulty regions with maximum flexibility before making use of a deterministic channel. However, even if the message has traversed a deterministic channel, misrouting can still be permitted in dimensions lower than that of the last deterministic channel traversed. This will prevent cyclic dependencies from forming among deterministic channels, and thus the extended channel dependency graph remains acyclic. However, from the point of view of guaranteeing deadlock freedom, situations may still arise where a message may have to block on a (deterministic) channel. If this channel is faulty, deadlock may result. In this case we would recommend coupling deadlock recovery schemes outlined in Section 6.7 with these schemes. This approach becomes more viable as the MTTR becomes increasingly smaller relative to the MTBF of the network components.

However, routing algorithms can be made more resilient to faults by combining routing techniques that support fully adaptive nonminimal routing. For example, it is possible to combine the theory of deadlock avoidance proposed in Section 3.1.3 with the turn model described in Section 4.3.2. This approach was followed in the fault-tolerant routing algorithm proposed in [93, 95] for n-dimensional meshes using wormhole switching. Each physical channel is split into four virtual channels. Virtual channels are grouped into four sets or virtual networks. The first virtual network consists of one virtual channel in each direction. It is used to send packets toward the east (X-positive). It will be referred to as the eastward virtual network. The second virtual network also consists of one virtual channel in each direction. It is used to send packets toward the west (X-negative), and it will be referred to as the westward virtual network. When the X coordinates of the source and destination nodes are equal, packets can be introduced in either virtual network. The routing algorithms for eastward and westward virtual networks are based on nonminimal west-last and east-last, respectively. Once a packet has used a west (east) channel in the eastward (westward) virtual network, it cannot turn again. However, 180-degree turns are allowed in Y channels except in the east (west) edge of the mesh. This routing algorithm is fully adaptive nonminimal. It is deadlock-free, as shown in Exercise 3.3 for 2-D meshes. While routing in the eastward (westward) virtual network, it tolerates faults except when routing on the east (west) edge. In order to tolerate faults in the edges, two extra virtual networks are used. The extra eastward (westward) virtual network is used when a fault is met while routing on the west (east) edge of the mesh. The resulting routing algorithm is very resilient to faults under both the node failure and the link failure models [93, 95]. Figure 6.33 shows the paths followed when some channels fail. Figure 6.34 shows the paths followed when some nodes fail. This approach also supports rectangular fault regions.

6.7.1 Base Mechanisms

The ability to tolerate dynamic failures in message pipelines places additional requirements on the basic functionality of the network routers and interfaces. Consider the occurrence of a link failure as shown in Figure 6.39. The figure shows a message in transit between nodes S_A and D_A. The last flit of the message has left S_A and is currently in node L_A. The link marked in the network now fails. The portions of the message above the failed link continue to make progress toward the destination. The portions of the message below the failed link, starting with the flits in the output buffers of router RA, block in place. These data flits have no routing information associated with them. Therefore, they cannot be rerouted and block indefinitely holding resources, possibly leading to deadlock as shown in Figure 6.1.

This situation places new requirements on the functionality of switching techniques and associated routing algorithms. There are at least two basic approaches to deal with such orphaned data flits. In one approach, header information is maintained through the routers that contain flits of the message. When messages are interrupted, a new message can be constructed with the stored header information, and the (relatively) smaller message can be forwarded along an alternative path to the destination. This will be referred to as flit-level recovery. Messages are injected only once into the network and recover from link-level dynamic and transient failures. Alternatively, the blocked data flits can be recovered and discarded from the network, the router buffers freed, and the message retransmitted from the source. In this case, the source and destination must synchronize message delivery or drop messages. This requires that the message be buffered at the source until it can be asserted that it has been delivered either explicitly through acknowledgments or implicitly through other mechanisms. This will be referred to as message-level recovery to denote the level at which recovery takes place. Implementations of each basic approach are described in the following.

6.7.2 Flit-Level Recovery

Reliable message delivery can be handled by end-to-end protocols that utilize acknowledgments and message retransmission to synchronize delivery of messages. Messages remain buffered at the source until it can be asserted that the message has been delivered. If we consider packet switching, more efficient alternatives exist for ensuring reliable end-to-end message delivery. Error detection and retransmission/rerouting can be implemented at the link level. A message must be successfully transmitted across a link before it is forwarded. With some a priori knowledge of the component failure rates, fault-tolerant routing algorithms can be developed where packets are injected into the network exactly once and guaranteed to be delivered to the destination by rerouting around faulty components. The difficulty in applying the same approach to wormhole-switched messages has been that the message packets cannot be completely buffered at each router and are spread across multiple routers when the header flit blocks. Thus, link-level monitoring and retransmission are difficult to realize on a message packet basis. The Reliable Router developed at the Massachussets Institute of Technology [74, 75] has implemented a novel approach utilizing a flit-level copying and forwarding algorithm to solve this problem and realize exactly-once injection and subsequent delivery of all packets in wormhole-switched networks.

Networks of reliable routers utilize three virtual networks. Five virtual channels are provided across each physical channel. Two of these virtual channels are used to implement an adaptive network where messages may utilize any outgoing channel from a router. Two more virtual channels are utilized to implement a dimension-ordered network where messages traverse links in dimension order. The two sets of dimension-order channels are used by packets at two priority levels. The two priorities are used with distinct resources to prevent software deadlocks. The remaining virtual channel is used as part of a network that implements the turn model for fault-tolerant routing. The adaptive and dimension-ordered networks together implement DP (see Section 4.4.4) for fully adaptive routing. When a message cannot acquire an adaptive channel, it attempts the dimension-order channel. If this channel is also busy, the message blocks for one cycle, and then first attempts to route along the adaptive channel. When a message can no longer progress due to a fault on the outgoing dimension-ordered link, the message employs nonminimal turn model-style routing in the fault-handling network to route around the fault (except for 180-degree turns). At the adjacent router, the message may transition back to the adaptive and dimension-ordered networks, or may remain in the fault-handling network until it is delivered to the destination. This choice depends on the dimension across which the failed channel was encountered. If the packet traversed a nonminimal link in the y direction, this dimension traversal can be subsequently corrected without violating the x-y ordering in the dimension-order virtual network. However, nonminimal traversals in the x dimension result in the packet remaining in the fault-handling network until it has reached its destination. This restriction is necessary to ensure deadlock freedom. Based on this overall routing strategy, dynamic faults are handled as described below.

Link-level monitoring and retransmission are used to guarantee the successful progress of data flits across links and between routers. This implies that a copy of each data flit is maintained by the sending router until it can be asserted that the flit was received error-free. The flit-level flow control ensures that there always exist exactly two copies of every flit in the network at all times. Thus, when a data flit successfully advances, flow control information must travel in the reverse direction to free the oldest copy of the flit. If a link fails, the message can now be partitioned into two messages. Data flits on the header side of the fault continue toward the destination. Data flits on the other side of the failure must construct a new header and reroute this new message along an alternative path. This requires that copies of the header flit exist in each router containing a data flit of the message. Finally a special token defines the end of the message. The flit-level flow control and copying is illustrated in Figure 6.40.

Each message is comprised of four components: a header, tail, data, and the token signifying the end of the message. Figure 6.40(a) shows the state of a message just prior to failure of the link. Now assume that a link failure has been detected. Figure 6.40(b) shows the state of the routers two cycles later. One side of the failed link has the header and a single data flit. A token is generated (not shown), appended to the data flit, and this new message can now continue toward the destination. The data flits on the other side of the fault are orphaned. A new header is constructed, prepended to the first data flit, and routed as a new message. The token of the original message serves as the token for this message. Header reconstruction is supported by maintaining a copy of the header in all of the routers with a data flit from the message (not shown in the figure). When the message token passes through the router, the copies of the header flit can be cleared. To facilitate reconstruction of the message at the destination, the headers are distinguished (original and restart) as are the token types (unique and replica). Finally, although not shown, a copy of every flit is maintained on both sides of a link. Flit-level flow control must enable the correct release of flit copies. Whenever router R₂ successfully transmits a flit to router R₃, a copied signal is transmitted to R₁ so that R₁ may invalidate its copy of the flit. In this way exactly two copies of each data flit are maintained in the network at all times. A more detailed description of the architecture of the router implementation can be found in Chapter 7.

6.7.3 Message-Level Recovery

An alternative to flit-level recovery is to find and discard the interrupted message components and retransmit the message from the source. Recovery is at the level of complete messages rather than at the flit level. The PCS-based solutions exploit the fact that a separate control network comprised of the control channels exists. Consider a message pipeline where a fault is detected on a reserved virtual link or physical channel as shown in Figure 6.39. The link is marked faulty. The link controller at the source end of the faulty virtual link introduces a release flit (referred to as kill flit in [123]) into the complementary virtual control channel of the virtual link upstream from the fault. This release flit is routed back to the source router. The link controller at the destination end of the faulty virtual link introduces a release flit into the corresponding virtual control channel of the virtual link downstream from the failed virtual link. This release flit is propagated along toward the destination. When a release flit arrives at a node, the input and output virtual links associated with the message are released, and the flit is propagated toward the source (or destination). If multiple faults occur in one message pipeline, this mechanism is applied recursively to fault-free segments.

When a release flit arrives at an intermediate router node, the set of actions taken by that node will depend on the state of the interrupted message pipeline in that node. We have the following rules that are to be implemented by each router node. In all of the following steps it is implicit that virtual links and associated buffers are released. If two control flits for the same message arrive at a router node (from opposite directions along the path), the two control flits collide at that router node. A flit in progress toward the destination (source) is referred to as a forward (reverse) flit. The following rules govern the collision of control flits and are based on the assumption [123] that paths are removed by message acknowledgments from the destination rather than by the last flit of the message. Thus, a path is not removed until the last flit has been delivered to the destination. This behavior guarantees message delivery in the presence of dynamic or transient faults.

Release flits are injected into the network only on the occurrence of faults. Since faults are a dynamic phenomenon, they may occur at any time during path setup, message transmission, or message acknowledgment. The interaction of control flits produces the actions defined above to ensure proper recovery. In the fault-free case each virtual circuit contains at most one control flit at a time. Therefore, it is necessary to add additional buffer space for one reverse and one forward release flit per virtual control channel. Since nonheader control flits are allowed to pass blocked headers, release flits will not wait and therefore cannot create chains of blocked flits as shown in Figure 6.1. Header flits using backtracking PCS algorithms do not block on faults. Thus, no flit in the network blocks indefinitely on a fault. As a result, release flits cannot induce deadlock in the presence of faults, and the existing routing algorithm is deadlock-free.

As long as a path exists between the source and the destination, if a fault interrupts the message, both the source and the destination will be notified. However, it is possible that an inconsistent state can develop between a source and a destination where the destination has received the message intact, but the source believes the message was lost and must retransmit. This situation develops when a dynamic fault occurs in the virtual circuit after the last flit is delivered, but before the final message acknowledgment reaches the source. This situation can be remedied at the operating system level by assigning identification tags to messages. If the source is prevented from sending the next message until the previous message has been successfully received, the destination can detect and discard duplicate messages relatively easily.

The above approach requires the use of virtual channels to support recovery traffic. The use of virtual channels can complicate routing decisions and channel control, leading to an increase in the flow control latency through the router and across the channel. Fault-tolerant implementations of compressionless routing have been proposed [179], motivated by a desire to simplify router design to enable adaptive routing and fault recovery with speeds comparable to oblivious routers. Compressionless routing exploits the small amount of buffering within the network routers to be able to indirectly determine when the header of a message has reached the destination. For example, assume that each router can only buffer two flits at the input and output of a router. If a message is to traverse three routers to the destination, once the 12th flit has been injected into the network the source node can assert that the header has been received into the destination node queue. Figure 6.41 illustrates this case, with the exception that the message is actually comprised of 10 flits. When the last data flit is injected into the network, the header will not have reached the destination node. Therefore, the message is padded with pad flits. The number of pad flits that must be added is a function of the distance to the destination and the message size.

A separate pad signal enables the routers to distinguish between data flits and pad flits and is also used to remove the path when message transmission is complete. Thus, every message is padded with one pad flit as the tail flit. The pad signal appears as shown in Figure 6.42.

Fault-tolerant routing can now be realized as follows. The sender maintains a counter for the number of injected flits and a timer for recording the time a message remains blocked. The flit counter enables the sender to determine whether the header has reached the destination. For the static fault model, once the header flit has been delivered it can be asserted that the message will be delivered. If the header encounters a fault, it can be rerouted. Misrouting can be accommodated by limiting the number of nonminimal steps that are permitted and correspondingly increasing the number of required pad flits. No routing restrictions are enforced to prevent deadlock, and therefore routing is maximally adaptive. Rather, deadlock detection is employed. A timer is used to determine if a message has been blocked too long and is therefore possibly deadlocked. When the timer expires at the source, an FKILL control signal is transmitted from the source to release the path and buffers. The message is then retransmitted. Compressionless routing is based on the experimental observation that algorithms with a high degree of adaptivity rarely result in deadlocked message configurations. The occurrence of static faults is indistinguishable from deadlock due to cyclic dependencies.

In the case of dynamic faults, messages may be interrupted by faults, and therefore the algorithm requires some modification. Now messages are padded such that the path is held until the last data flit has reached the destination. If a fault interrupts a message in progress, the detecting router transmits FKILL and BKILL signals toward the destination and source routers, respectively, to release the path. When the destination receives an FKILL signal, it can be asserted that the received message is incomplete and can be discarded. The reception of a BKILL signal by the source causes retransmission by the source. Faults occurring on links that are transmitting pad flits do not require transmission of recovery signals.

Compressionless routing does not require virtual channels and is applicable to a wide variety of topologies. The KILL signals can be used for buffer allocation and for determining the immediate status of adaptively routed messages (i.e., whether they have been delivered or not). This latter property can be used to guarantee in-order delivery of multiple messages. The overall result is a simpler and therefore faster router design. However, pad flits use real bandwidth. If messages tend to be short and networks low dimensional and large, the increase in router speed is traded off against a drop in network utilization. An alternative view is that compressionless routing encourages the use of higher-dimensional networks with low average interprocessor distance.

6.7.4 Miscellaneous Issues

All of the approaches described in this section utilize bandwidth in different ways to enable recovery from dynamic faults and for synchronization between the source and destination to detect or avoid duplicate messages. These techniques do so while providing for fully distributed recovery of orphan flits. In PCS-based dynamic fault tolerance, network bandwidth is consumed by release flits and message acknowledgments for synchronization as well as recovery. In compressionless-routing-based recovery, network bandwidth is consumed by pad flits and a few extra control signals (which represent bandwidth that could otherwise have been used for data transmission). Exactly-once delivery appears to require the least amount of additional bandwidth for fault recovery at the expense of increased storage within the router. The increase in the number of messages produces an increase in the number of message headers. The headers utilize more bandwidth and storage within the routers for copies. However, with increasingly larger routers becoming feasible this does not appear to be a limiting factor. The increased message population changes the blocking probabilities experienced by all messages and can have some impact on average message latency and throughput. At low loads this impact would not appear to be significant.

Timeout mechanisms have been proposed for use at the link level as well as the message level. Link-level timeouts are often used to determine if flit transmission across a channel has been successful, and the timeout interval is generally easier to establish. Node-level timeouts have been used to determine if messages have been received. There are several issues with using timeouts at the node level. It is difficult to determine the appropriate value of the timeout interval since it is sensitive to traffic conditions and fault patterns. In the presence of dynamic communication traffic that varies across applications, conservative estimates of timeout intervals lead to long recovery times while small timeout intervals lead to false recovery; that is, network congestion is erroneously interpreted as a deadlock situation. Further, buffering requirements at the source node increase with the timeout interval since messages must be maintained for a longer period of time. Most importantly, the use of timeouts does not address the problem of recovering orphaned data flits in the network.

The availability of such distributed recovery mechanisms enables several existing adaptive routing algorithms based on wormhole switching to become fault recoverable. Consider fully adaptive routing algorithms under the wormhole switching model. Under the static fault model, if a wormhole-switched header blocks on a faulty virtual link, deadlock may occur. Thus, adaptive wormhole-switched routing algorithms that rely on deterministic subnetworks become deadlock-prone. If the header is forced to block waiting on a faulty link in a deterministic subnetwork, the recovery mechanism can be invoked to remove this message if recovery mechanisms are supported. Since the fault occurs at the location of the header flit, only the source node is informed that the route failed. The message may now be retransmitted or a higher-level fault handler may be invoked. Since the base routing algorithm is adaptive, a retransmitted message may possibly find a different path to the destination. However, since generally no memory of the past route is maintained, routing algorithms based on wormhole switching are likely to repeat their last route. Randomizing the choice of adaptive output channels will make these routing algorithms more robust. A final message acknowledgment is necessary to remove the message path and ensure delivery of the last flit.

 Hard faults (e.g., radiation-induced, natural failures, etc.)

 Transient faults (e.g., radiation-induced, switching transients, etc.)

 Design faults (e.g., hardware and software)