Abstract-Using depth-first search, we develop and analyze the performance of a routing scheme for hypercube multicomputers in the presence of an arbitrary number of faulty components. We derive an exact expression for the probability of routing messages via optimal paths (of length equal to the Hamming distance between the corresponding pair of nodes) from the source node to an obstructed node. The obstructed node is defined as the first node encountered by the message that finds no optimal path to the destination node. Also, bounds for this probability are derived in closed form. Note that the probability of routing messages via an optimal path between any two nodes is a special case of our results, and can be obtained by replacing the Obstructed node with the destination node. Numerical examples are also given to illustrate our results, and show that in the presence of component failures the depth-first search routing can route a message via an optimal path to its destination with a very high probability. Index Terms-Coordinate sequences, depth-first search, faulttolerant routing, hypercube multicomputers, inversions. WING to their structural regularity and high potential 0 for the parallel execution of various algorithms, hypercube multicomputers have drawn considerable attention in recent years from both academic and industrial communities [ 11-[ 101. Topological properties of hypercubes were investigated in [ 13. Task and subcube allocation schemes were proposed to exploit the parallelism within a hypercube multicomputer [2]- [4]. Numerous applications on hypercube multicomputers were explored [5]- [7], and several research and commercial hypercube machines were built [8]-[ 101. Efficient message routing is a key to the performance of distributed memory multicomputers, such as hypercubes [ll]. To make hypercube multicomputers useful for reliability-critical applications, significant research efforts have been made on the design of fault-tolerant routing schemes for them [ 121-[20]. A connected hypercube with faulty components is called an injured hypercube. In order to enable nonfaulty nodes in an injured hypercube to communicate with one another, enough network information must be either kept at each node or added Manuscript received May 15, 1989; revised December 11, 1989. This work was supported in part by the Office of Naval Research under Contract N00014-85-K-0122 and NASA under Grant NAG-1-296. M. to the message to be routed. For the first approach, several algorithms have been proposed in [12]-[15], which generally require each hypercube node to keep a certain amount of global information for its routing decisions. This, however, necessitates the propagationhroadcasting of updated network information when the network condition changes. Some broadcasting schemes in injured hypercubes can also be found in [15]- [17]. For the second approach, in which each node is required to know only the condition (faulty or not) of its adjacent components (links or nodes), several routing schemes based on the concept of depth-first search and its variation have been proposed [ 181-[20]. Under a depth-first search routing scheme, each message is accompanied with a stack which keeps track of the history of the path traveled, and tries to avoid visiting a node more than once unless a backtracking is enforced. Although the concept of depth-first search is well understood and appears to be able to exploit the abundant connections in the hypercube and thus achieve a high degree of fault-tolerance, neither formal presentation nor rigorous performance analysis of this scheme has been reported in the literature. Development and analysis of a fault-tolerant routing scheme using depth-first search for hypercube multicomputers is, therefore, the subject of this paper. We shall first develop a routing scheme using depth-first search, in which every node is only required to know the condition of its adjacent components. The path that a message has traversed is kept track of by the message as it is routed toward its destination. Performance of this routing algorithm will be rigorously analyzed. An optimal path between a pair of nodes is a path of length equal to the Hamming distance between the two nodes. Under this routing scheme, the first node in the message's route that is aware of the nonexistence of an optimal path from itself to the destination is called the obstructed node. At the obstructed node, the message has to take a detour. In this paper, we derive exact expressions for the probabilities of optimal path routing from the source node to a given obstructed node in the presence of both link and node failures. Bounds for these probabilities are also derived in closed form, which will be shown to closely approximate the exact expressions. Note that determination of the probability for optimal path routing between any two nodes is a special case of our results since the destination node can be viewed as an obstructed node that is 0 hop away from the destination node. Numerical examples are also given to illustrate our results. It can be seen that in the presence of component failures, the depth-first search routing can route a message via 1045-9219/90/0400-0152$01.00 @ 1990 IEEE an optimal path to its destination with a very high probability. It is worth mentioning that the concept of depth-first search is not only useful for the fault-tolerant routing in hypercubes, but also applicable to fault-tolerant and multipath routing in other multicomputer systems such as square meshes and hexagonal meshes [21], [22]. Note, however, that the depthfirst search routing must be guided to fully exploit the connections in each multicomputer system, and thus, the method of guiding depth-first search closely depends on system topology. This paper is organized as follows. Necessary notation and definitions are introduced in Section 11. A fault-tolerant routing scheme using depth-first search for hypercube multicomputers is presented in Section 111. The performance of this routing scheme is analyzed rigorously in Section IV where illustrative examples are also given. The paper concludes with Section V. An n-dimensional hypercube is defined recursively as Qn = K2 x Qn-1 where K2 is the complete graph with two nodes, Qo is a trivial graph with one node and x is the product operation on two graphs [23]. A Qn contains 2" nodes and n2"-' links since the degree of each node in a Qn is n. Let C be the ternary symbol set (0, 1, * } where * is a don't care symbol. Every subcube in a Qn can then be uniquely addressed by a string of symbols in .E. The rightmost coordinate of the address of a subcube will be referred to as dimension 1, and the second to the rightmost coordinate as dimension 2, and so on. For each hypercube node, the communication link in dimension i is called the ith link of the node. For notational simplicity, each link is represented by a binary string with a "-" symbol in its corresponding dimension. For example, the link between nodes oo00 and 0010 is represented by 00-0. Definition I: The Hamming distance between two hypercube nodes with addresses U = UnUn-1 . . .u1 and w = wnwn-l "'w1 in a Qn is defined as n H(U, w) = x h ( u i , wi)whereh(ui, wi) Also, it is necessary to introduce the exclusive operation between two binary strings, and the concept of relative address between two hypercube nodes. Definition 2: The exclusive operation of two binary strings q = qnqn-l . . . q l and m = m,mn-l...ml, denoted by q e m = r n r n V l ".rl is defined as ri = 0 if qi = mi and ri = 1 i f q i =-for 1 < i i n . We use @ fz1 to denote k sequential exclusive operations. The relative address of a node U with respect to another node w, denoted by u /~, can then be determined by ulw = U w. Let ek = enenPl . . . el where e k = 1 and ej = O V j # k. in which every two consecutive nodes are physically adjacent to each other. Thus, a path in a Qn can be viewed as a sequence of binary numbers of n bits such that every two consecutive binary numbers differ by exactly one bit. The number of links on a path is called the length of the path. An optimal path is a path whose length is equal to the Hamming distance between the source and destination nodes. We shall call the routing via an optimal path the optimal path routing. Also, a link of node U is said to be toward another node w if the link belongs to one of the optimal paths from U to w. Note that due to the special structure of a hypercube, once the source node of a path of length k in a Qn is given, the path can be described by a coordinate sequence ordinate sequence is a sequence of ordered dimensions in each of which the corresponding two adjacent nodes in the path differ [24]. A coordinate sequence is said to be simple if any dimension does not occur more than once in that sequence. It is easy to see that a path is optimal if and only if its coordinate sequence is simple. As shown in Fig. 1  In this section, we present an adaptive routing algorithm based on depth-first search, which requires every node to know only the condition (faulty or not) of its own links. The case that a node is faulty is treated as that all links of the node are faulty. This algorithm can successfully route messages between any pair of connected, nonfaulty nodes. When the insufficient knowledge of faulty components causes a message to be sent to an intermediate node from which no optimal path to the destination node exists, an alternative path will be chosen in such a way that the connectivity of a hypercube is fully exploited. Before presenting the routing algorithm, it is necessary to introduce the following proposition which determines, from the coordinate sequence of a path, the relative addresses of those nodes traversed. Proposition I : Let [c 1 , c2, . . . , ck] be the coordinate sequence of a given path in a Q n starting from node U , and wiu = w,wn-l . . . w 1 denote the relative address of node w with respect to U where k = H ( u , w). Then, the path specified by [cl, c 2 , . . . ,ck] ends at w if and only if @fzl Proof: A message's traversal along the ith dimension is the same as inverting the bit in the ith coordinate of the relative address of its destination. Therefore, traversing along a certain dimension an even number of times has the same effect as not traversing along that dimension at all. This proposition thus follows. Q.E. for j := 1, n do begin far are recorded in a set TD in the same order if visited, and will be delivered together with the message to the next node. Note that using TDR each intermediate node can determine the addresses of those nodes visited before where TDR is the reversing of TD as defined in Section 11. Clearly, sending TD along with the message is much cheaper than sending the addresses of all the nodes visited. When the source node begins routing a message, TD is set to the empty set 4. Therefore, the information to be phased on to the next node can be represented as ( d , message, TD) where d is the relative address of the destination node with respect to an intermediate node, and is updated as the message is routed toward the destination. A message reaches its destination when d becomes 0". When a node receives a message, it will check the value of d to see if the destination is reached. If not, the intermediate node will try to send the message along an optimal path to the destination. However, if all the optimal paths are blocked by faulty components and those nodes visited before, the node will route the message via an alternative path using the concept of depth-first search. When there is no alternative path available, backtracking is enforced. More formally, this routing scheme can be described in an algorithmic form as follows. Algorithm G: Depth-first search routing algorithm. if ( To indicate the destination of a message, the relative address of the destination node is sent along with the message. The depth-first search routing algorithm will attempt to avoid visiting the same node more than once except when backtracking is forced. Thus, those dimensions that a message traversed so Note that an intermediate node can determine whether or not its ith link is connected to a node that was visited before by checking if ei belongs to S(T@). When backtracking is forced, the message must be returned to the node from which this message was originally received. This explains the way we determine the value g in the segment commented by /* Backtracking */ in the above algorithm. When g = \S(TD)), CHEN AND SHIN: ROUTING IN HYPERCUBE MULTICOMPUTERS we know that backtracking is enforced at the source node, and 1111 can thus conclude that the source and destination nodes are disconnected. Note that there is an unavoidable overhead required to achieve fault-tolerant routing. To route a message to its destination in an injured hypercube, those nodes traversed before by the message must be made known to the intermediate nodes so as to avoid message looping. This is the very reason that under G every intermediate node has to append to the message a tag TD, from which the addresses of nodes traversed before can be recovered in light of the topology of a hypercube. Depth-first search is thus ensured at the cost of carrying TD with each message. The values of g and h in G can be easily determined from TD. It can be verified that the complexity of determining g and h is O( ITDO. Note that when the probability of the occurrence of a faulty component is low, the above scheme can be modified to reduce the operational overhead in such a way that the tag TD is appended to the message only after faulty components are encountered by the message. However, when the probability of the occurrence of a faulty component is high, it is worth using the tag TD from the beginning so as to fully exploit different paths and nodes where backtracking may occur under G . These nodes will form a search tree with 2" -k nodes and 2" -k -1 links. Since every link in the search tree is traversed twice, the message will traverse 2(2" -k -1) hops in the search tree and k hops on its optimal path to the destination. Q.E.D. -. avoid sending the message back to a node which received the message before. There are some other techniques conceivable to implement the depth-first search routing for hypercubes. Instead of keeping the entire path traveled in TD, the search can also be implemented by using a stack. In such a case, the operation required for backtracking is simplified, but additional provisions are needed to ensure that a node will not be visited more than once. Consider an injured Q 4 in Fig. 2 . Suppose a message f m is routed from U = 0110 to w = 1001. The original message at U = 01 10 is (1 11 1, f m , 4) . Following the execution of G , node 01 10 sends (1 110, f m , [l]) to node 01 11 which then sends (1 100, f m , [1, 2] ) to node 0101. Since the third dimensional link of 0101 is faulty, node 0101 will send (0100, f m , [1, 2, 4]) to 1101. However, since the third dimensional link of 1101 is faulty, node 1101 will choose an alternative path, and send (0101, f m , [1,2,4,1]) to 1100, which will, in turn, send (0001, f m , [1, 2, 4, 1, 3]) to 1OOO. Then, since links of lo00 in dimensions 1, 2, and 4 are faulty, backtracking is enforced and the message is sent back to 1100. It can be verified that the message is thereafter sent to its destination via 11 10, 11 11, 101 1, and then 1001. The following proposition follows directly from the fact that depth-first search is a general graph search algorithm and can start from any node in a graph [26]. Proposition 2: Algorithm G will route a message to its destination successfully as long as the destination is reachable. Algorithm G is a generalized version of the algorithm presented in [18] where the number of faults is assumed to be less than n. Also, from the fact that those links traversed will not form a cycle, we have the following proposition. The nodes and links traversed under G form a tree. Proposition 3 in turn leads to another proposition. The worst case of G uses H ( u , w ) +2(2" -H ( U , w ) -1) hops to send a message from node U to node w for a pair of connected nodes U and w. Proof: Let H ( u , w ) = k , then there are at most 2" -k To illustrate the performance of depth-first search routing, let us consider an injured hypercube with a given number of faulty components. All possible distributions of faulty components are assumed to be equally likely. The number of faulty nodes required for a simple coordinate sequence C to be the path found by depth-first search is equal to the number of inversions in C [ 191. This fact can be formally stated as follows. Proposition 5: Suppose H ( u , w ) = n in a Q n . Then, under G the minimum number of faulty nodes required for the simple coordinate sequence C = [c1, c2,. . . , c,] to be the path determined by G from U to w is V ( C ) . For example, let 0000 and 11 11 be the source and destination nodes, respectively. Then, the set of nodes whose failures will make G choose the coordinate sequence [3,4,1,2] is (0001, 0010, 0101, OllO}. In light of the fact that the addresses of hypercube nodes form a partial order set, the effects of a faulty node, say x, are the same as those of a faulty link via which an intermediate node is trying to send the message toward x. For the above example, the set of links whose failures will force G to choose the coordinate sequence [3,4,1,2] is {WO-, 00-0, 010-, 01-O}. Proposition 5 can thus be extended and generalized as follows. Lemma 1: Let U and w be two nodes in an injured Qn with f faulty links and g faulty nodes where H ( u , w ) = n . is the path chosen by G from U to w. Then, f + g 2 V ( C ) . Recall that the obstructed node is the first node on a path that is aware that there is no optimal path to the destination node and a detour (i.e., nonoptimal path) has to be taken. To facilitate our presentation, define the weight of a set of dimensions to be their summation, i.e., W(c1, c2, . . . , c,) = ELl c;. Then, we can derive the following theorem which characterizes the performance of G . Proof: There are CT = m(m -1)/2 different ways to choose pairs (Ci, C j ) , i < j , from (~1 , C~, . . . , C , ) . Since C is a simple coordinate sequence, either ci > c, or ci < c j , meaning that each selection (ci , c,) will be counted for either thus proving the lemma. Proof of Theorem I : According to the operations of depth-first search routing, the lowest dimension among those dimensions not traversed before will be chosen first. Since H ( u , w ) = n , the selection of dimension c1 to the first hop implies that c1 -1 faulty components have been encountered. Also, the selection of dimension c2 to the second hop means a) there are another c2 -1 faulty components encountered if c2 < c 1, or b) there are another c2 -2 faulty components encountered if c2 > c1. Following the same reasoning, we know that up to the obstructed node (i.e., the first m hops), (1,3), (2,3)}. Clearly, IS(n, m)l = C: is the number of combinations of m objects out of n different objects. Let Z,(k) denote the number of permutations of n numbers with exactly k inversions. Note that the value of Z,(k) can be obtained from its generation function given in (1) later [25]. Then, from Theorem 1 we have the following important theorem. Theorem 2: Suppose there are f faulty links in a Q n , and a message is routed by G from node U to node w where H ( u , w ) = n. Let hL be the Hamming distance between the obstructed node and the destination node. Then where P ( E ) is the probability of event E , L = n2"-' and m + j = n . Proof: Since faults may occur at any f links in the Q n , there are C t different configurations of faulty links. The problem of obtaining P(hL = j ) is then reduced to that of counting the number of configurations which lead to the case of h~ = j . Note that the message traverses m = n -j hops before it reaches the obstructed node, meaning that there are IS(n, m) 1 possible locations of the obstructed node. Without loss of generality, one can assume that 0" is the source node and 1" is the destination node. Then, there is a one-to-one correspondence between each element in S(n, m) and each possible location of the obstructed node. Consider an obstructed node location x which is determined by an element U E S ( n , m). Let C be the coordinate sequence from node U to x. From Theorem 1, we know that the message has encountered V ( C ) + W ( U ) -m(m + 1)/2 faulty links before reaching x. Thus, the number of different paths from U to x while traversing the dimensions in U and encountering k faulty links can be expressed as Z,(k -W ( U ) +m(m + 1)/2) where Z,(q) is the number of permutations of m numbers with q exactly inversions. For each given coordinate sequence to x, the locations of these k faulty links encountered before reaching x are determined. Moreover, there are additional j faulty links adjacent to x. Also, note that m links in the path from U to x are nonfaulty. Therefore, the number of different configurations for a given coordinate sequence or path to a certain obstructed node location x is C;I:It-m = Ci:;::. Thus, this theorem follows. Q.E.D. It is worth mentioning that determination of the probability of an optimal path routing can be viewed as a special case of Theorem 2 by setting the obstructed node to the destination node, i.e., the determination of P(hL = 0). More formally, we have the following corollary. Corollary 2.1: Under Algorithm G , the probability for a message to be routed in an injured Qn with f faulty links via an optimal path to a destination node which is n hops away can be expressed as ' Proof: Since the destination node is viewed as the obstructed node which is 0 hop away from the destination node, one can substitute j = 0 and m = n into the expression in Theorem 2. Note that the only element in S ( n , n) is (1, 2, ..., n ) and W ( 1, 2, . . . ,n) = n(n + 1)/2, leading to this corollary. As mentioned earlier, the value of Z,(k) can be obtained from its generation function [25], because Z,(k) = l/k!dkG,(0)/dzk. It can be seen that  CHEN AND SHIN: ROUTING IN HYPERCUBE MULTICOMPUTERS ;=I Numerical examples for (2) are given in Table 11 -B. From Table 11 -A and B, it can be observed that (2) very closely approximates the exact expression given in Corollary 2.1. Sim- The values of Zn(k), for 3 5 n 5 6 and 0 5 k 5 n(n -1)/2, are computed in Table I. The exact values for P (~L = j) can thus be determined by Theorem 2, and the probability of an optimal path routing between two nodes can be obtained by Corollary 2.1. From Corollary 2.1 and the data in Table I , we obtain Table 11 -A which shows the probabilities of optimal path routing between two nodes n hops away from each other in a Qn with f faulty links. It can be seen that in the presence of link failures, Algorithm G can route a message to the destination via an optimal path with a very high probability. Notice, however, that when n is large, the determination of Zn(k), although it is feasible, may require excessive computation. To obtain more insights into the performance of G as well as reduce the computation required to obtain P (~L = j ) , an upper bound of P (~L = j ) can be derived in closed form as follows. Lemma 3: Suppose there are f faulty links in an injured Q n , and a message is routed by G from node U to w , where H ( u , w ) = n . Then, P(hL = j ) ICFI;/C$ if 0 5 j 5 min {n, f } where L = n2"-' is the number of links in a Q n . Proof: As mentioned before, the problem of obtaining P(hL = j ) is to count the number of configurations which lead to the case of hL = j . When h~ = j , all the j links toward w of the obstructed node, say x, must be faulty. According to depth-first search, the location of the obstructed node is determined by those faulty links which are not within SQ(x, w ) where SQ(x, w ) is the smallest subcube that contains both x and w Since the j links of node x within SQ(x, w ) are faulty, there are CFI; different distributions of the other f -j faulty links. When these f -j faulty links cause node y, instead of x, to be the obstructed node, we exchange the links (including faulty links) in S Q ( y , w ) with those in SQ(x, w), and obtain a configuration which leads to the case when the obstructed node is y and h~ = j . Notice that some of the CFI; different distributions of faulty links may lead to the case hL > j , meaning that the number of confi urations leading to the case Q.E.D. h~ = j is less than or equal to C f -i . P(hL = j ) = 1, a lower bound for the probability P (~L = 0) can be derived in closed form as below. In light of Lemma 3 and the fact that ilarly to the case of faulty links, the performance of G can be analyzed with respect to faulty nodes as stated in the following theorem. Theorem 3: Suppose there are g faulty nodes in an injured en, and a message is routed by G from node U to node w where H ( u , w ) = n . Let hN be the Hamming distance between the obstructed node and the destination node. Then, for 2 5 j 5 min {g, n}, we have, where m + j = n. Recall that the source and destination nodes are assumed to be nonfaulty. We, therefore, consider only Cr-' different distributions of the g faulty nodes. Also, note that when a message reaches an obstructed node which is j hops away from the destination, the message must have traversed n -j = m nonfaulty nodes (not including the source node), and is blocked by at least j faulty nodes at the obstructed node. The conditions (faulty or not) of these m + j + 2 = n + 2 (including the source and destination nodes) are then determined from a given coordinate sequence to the obstructed node. This theorem thus follows from the same reasoning as the one in the proof of Theorem 2. Q.E.D. Also, the probability of an optimal path routing in the presence of g faulty nodes, i.e., P(hN = 0), can be obtained by Corollary 3.1 below. Corollary 3 .I: Under Algorithm G , the probability for a message to be routed in a Qn with g faulty nodes via an optimal path to a destination node located n hops away is k =O Proofi Note that in this case the destination node is viewed as an obstructed node that is 0 hop away from the destination node. From a given coordinate sequence of an optimal path, the locations of n + 1 nonfaulty nodes (including 158 the source and destination nodes) in the path are known. This corollary thus follows from Theorem 3. Q.E.D. Using Table I and Corollary 3.1, we can obtain Table 111-A which gives the probabilities of optimal path routing between two nodes n hops away from each other in an Q n with g faulty nodes. It can be seen that P(hN = 0) is greater than P (~L = 0) when the number of faulty components g = f is relatively small as compared with the number of nodes in a hypercube. This is due to the fact that a faulty node is viewed as all the links attached to the node are faulty, and thus, the message can find a faulty node sooner than a faulty link. This in turn means that a detour will be taken sooner in the presence of faulty nodes than in the presence of faulty links. This is the reason that P (~N = 0) is greater than P (~L = 0) when g = f is small. However, when the number of faulty components g = f is large, P (~L = 0) is greater than P (~N = 0). This also agrees with our intuition since there are much more links than nodes in a hypercube. Similarly to the case of faulty links, the associated bounds in the case of faulty nodes can be obtained from the following lemma. Lemma 4: Suppose there are g faulty nodes in an injured Q n and messages are to be routed from an arbitrary node U to another node w where H ( u , w ) = n. Then, P (~N = j ) 5 CrJ2-i/Cf-2 if 2 5 j 5 min { n , g}, and P (~N = j ) = 0 if j = 1 where N = 2" is the total number of nodes in a Q,,. From Lemma 4 and the reasoning used in determining the lower bound of P (~L = 0), we can obtain a lower bound for the probability P (~N = 0) in closed form as: Numerical examples for (3) are given in Table 111 -B. It can be seen from Tables 111-A and B that (3) closely approximates the expression given in Corollary 3.1, and also that Algorithm G routes a message to the destination via an optimal path with a rather high probability in the presence of faulty nodes. In this paper, we presented a routing scheme based on depth-first search. The knowledge on the number of inversions of a given permutation is used to analyze the performance of this routing scheme. The number of faulty linkshodes required for a coordinate sequence to become the coordinate sequence of a path toward a given obstructed node is determined. Probabilities for routing messages via optimal path to given obstructed node locations are determined, and their associated bounds are derived in closed form. By setting the obstructed node to the destination node, the probability of the optimal path routing between any two nodes can be obtained as a special case of our results. It is also shown that this routing scheme can route a message to its destination via an optimal path with a very high probability. The authors would like to thank J.-C. J. Chen at IBM for her assistance in obtaining the data for Tables I1 and 111 May 1980, pp. 23-30. T. C. Lee and J. P. Hayes, "Routing and broadcasting in faulty hypercube computers," in Proc. 3rd Conf. Hypercube Concurrent Appl., Jan. 19-20, 1988, pp. 346-354 Jan. 19-20, 1988, pp. 312-317. 1. M. Gordon and Q. F. Stout, "Hypercube message routing in the presence of faults,'' in Proc. 3rd Conf. Hypercube Comput. Appl., Jan. 19-20, , pp. 318-327. 19-20, 1988
Each message waiting for a channel in V IN 1 connected to a faulty/unsafe node can then be routed via the corresponding detour in V IN REF .
Depth-first search approach for fault-tolerant routing in hypercube multicomputers
IEEE Trans. Parallel Distrib. Syst.
IEEE Trans. Parallel Distrib. Syst.
Computer Science