Exact Reliabilities of Most Reliable Double-Loop Networks Frank K. Hwang, 1 Paul E. Wright, 1 X. D. Hu 2 1 AT&T Bell Laboratories, Murray Hill, New Jersey 07974 2 Institute of Applied Mathematics, Chinese Academy of Sciences, Beijing, People’s Republic of China Received 2 June 1994; accepted 2 April 1997 Abstract: A double-loop network with hop constants h1 , h2 , DL (n, h1 , h2 ) may be represented as a directed graph with n nodes 0, 1, . . . , n 0 1 and 2n links of the form i r i / h1mod n and i r i / h2mod n (referred to as h1-links and h2-links). They have been proposed as architectures for local area networks and for data alignment in SIMD processors, among other applications. Three reliability models of doubleloop networks have been studied in the literature. In the link model, nodes always work and each link fails independently with probability p. Hwang and Li showed that for p small DL (n, 1, 1 / n/2) is most reliable for n even, and DL (n, 1, 2) is most reliable for n odd. In the node model, links always work and each node fails independently with probability p. Hu et al. showed that for p small DL (n, 1, 1 / n/2) is the most reliable. However, no nonenumerative algorithms were given to compute the reliabilities of these most reliable networks except DL (n, 1, 1 / n/2) for even n under the node model. Recently, Hwang and Wright proposed a novel approach to compute the reliabilities of double-loop networks under the uniform model that each node fails with probability p, each h1-link with probability p1 , and each h2link with probability p2 , and the failures are independent. In particular, they obtained the reliabilities for DL (n, 1, 2). In this paper, we applied their approach to compute the reliabilities of DL (n, 1, 1 / n/2) under the uniform model, except that for n odd we need the assumption that h1-links always work. Note that even under this additional assumption our reliability model is more general than is the node model, the original model under which DL (n, 1, 1 / n/2) is found to be most reliable for n odd. We also used this approach to obtain the reliabilities of DL (n, 1, n 0 2), known as the daisy chain in the literature. q 1997 John Wiley & Sons, Inc. Networks 30: 81–90, 1997 1. INTRODUCTION A double-loop network DL (n, h1 , h2 ) can be represented as a digraph with n nodes {0, 1, . . . , n 0 1} and 2n links of the form i r i / h1mod n and i r i / h2mod n, referred to as h1-links and h2-links. Double-loop networks have been proposed as architectures for local area networks by Correspondence to: F. K. Hwang Liu [11] and for data alignment in SIMD processors by Fiol et al. [2]. A double-loop network with h1 Å 1 was called a forward-loop backward hop network in [12]. The case h2 Å n 0 1, called a distributed double-loop computer network, was proposed by Liu [11]; the case h2 Å n 0 2, called a daisy chain, was proposed by Grnarov et al. [3]; and the case h2 Å 2, called a braided ring, is used in SILK [9] (see Fig. 1). When nodes do not fail, a frequently used measure of q 1997 John Wiley & Sons, Inc. CCC 0028-3045/97/020081-10 81 8U12 / 8u12$$0773 07-14-97 18:00:34 netwa W: Networks 773 82 HWANG, WRIGHT, AND HU of [8] to compute the reliability of DL (n, 1, 1 / n/2 ) under the uniform model, thus completing the task to obtain the exact reliabilities of all the most reliable networks given for the node model and the link model. We also use the same approach to compute the reliability of the daisy chain whose result was announced in [7] without proof. 2. THE GENERAL APPROACH Material in this section are mostly available in [8]. We include them here without proof for self-completeness. Two double-loop networks DL (n, h1 , h2 ) and DL (n, h *1 , h *2 ) are said to be strongly isomorphic if there is a bijection F from the nodes of DL (n, h1 , h2 ) to the nodes of DL (n, h *1 , h *2 ) such that, after reordering h *1 , h *2 if necessary, F( £ / hi ) Å F( £ ) / h *i , i Å 1, 2, for all nodes £. Let R(n, h1 , h2 ) denote the reliability of DL (n, h1 , h2 ). Then, it is easily seen that R(n, h1 , h2 ) Å R(n, h *1 , h *2 ) if DL (n, h1 , h2 ) is strongly isomorphic to DL (n, h *1 , h *2 ). Hwang and Li [6] proved the following result. Fig. 1. Consecutive-2 link system: DL (n, 1, 2). reliability, e.g., see [1], is the all-terminal reliability which is the probability that the network (as a digraph) is strongly connected, i.e., there exists a directed path from every node to every other node. When nodes can fail, then often we would like to separate the component reliability from the network reliability. Thus, it is reasonable to define the reliability, sometimes referred to as the survival reliability, as the probability that the set of working (surviving) nodes is strongly connected. In this paper, we will deal with this type of reliability. Note that the algorithms given in [1] are not applicable to the survival reliability not only because nodes can fail, but also because the set of working nodes is not a fixed subset, a basic assumption made in [1]. Since the (survival) reliability of the double-loop network is difficult to compute, results have been given which compare the reliabilities of double-loop networks without actually computing them. In particular, Hwang and Li [6] proved that for the link model with sufficiently small link failure probability, DL (n, 1, 1 / n/2) is most reliable for even n, and DL (n, 1, 2), for odd n. Hu et al. [4] proved that for the node model with a sufficiently small node failure probability DL (n, 1, 1 / n/2 ) is most reliable [the reliability of DL (n, 1, 1 / n/2) for even n was explicitly given]. Recently, Hwang and Li [7] and also Hwang and Wright [8] gave efficient methods to compute the reliability of DL (n, 1, 2) under the uniform model (in fact, their analysis holds under the general model in which every node and every link has its own failure probability). In this paper, we adopt the approach 8U12 / 8u12$$0773 07-14-97 18:00:34 netwa Lemma 2.1. DL (n, h1 , h2 ) is strongly isomorphic to DL (n, h *1 , h *2 ) if and only if there exists h relatively prime to n such that, reordering h *1 and h *2 if necessary, h *i å hhi mod n, i Å 1, 2. As a consequence of Lemma 2.1, it is readily seen that DL (n, 1, 1 / n/2 ) is strongly isomorphic to DL (n, 2, 3) for n odd (multiply by 2 and reduce modulo n). Define a network state to be an enumeration of its component states. Let S denote the set of all network states. For a given s √ S, let G (s) denote the digraph obtained from DL (n, h1 , h2 ) by deleting all failed nodes and links incident to them and all failed links. An island is a node in G (s) without either an inlink or an outlink. A circuit C is a closed sequence of distinct, connected nodes £0 r £1 r rrr r £k r £0 . Two circuits C and C * are said to be disconnected if they are node-disjoint and their union C < C * is not strongly connected. Hwang and Wright [8] proved Lemma 2.2. A given s √ S is a working state if and only if G (s) contains neither an island nor two disconnected circuits. Our general approach to computing reliabilities, therefore, is to compute R(n, h1 , h2 ) Å P1 (n, h1 , h2 ) 0 P2 (n, h1 , h2 ), where P1 (n, h1 , h2 ) is the probability that G (s) contains no island and P2 (n, h1 , h2 ) is the probability (summing W: Networks 773 MOST RELIABLE DOUBLE-LOOP NETWORKS over s) that G (s) contains two disconnected circuits but no island. Next, we describe how to efficiently compute P1 (n, h1 , h2 ). Let E1 , . . . , El denote disjoint subgraphs of DL (n, h1 , h2 ) such that < liÅ1 Ei Å DL (n, h1 , h2 ). A state of Ei is an enumeration of all its component states. For any network state s, a taboo state of a subgraph of G (s) is a state whose existence is sufficient to induce network failure. The subgraphs Ei need not themselves be connected. In the examples that we consider, the taboo sets consist of states in which a working node is an island. Let Sj denote the set of nontaboo states of Ej . Let sj √ Sj , j Å 1, . . . , l. Then, there is exactly one network state s compatible with the collection {sj }. Suppose that the parts of the network can be ordered so that if the joint state (sj , sj /1 ), sl/1 Å s1 , contains no taboo states for every j Å 1, . . . , l then every node in G (s) has an inlink and an outlink. For j Å 1, . . . , l, define the ÉSjÉ 1 ÉSj /1É matrix Mj , indexed by elements of Sj 1 Sj /1 so that Mj (sj , sj /1 ) Å H Prob(sj ), if (sj , sj /1 ) contains no taboo states, 0, otherwise. Then, P1 (n, h1 , h2 ) ∑ rrr ∑ M1 (s1 , s2 )M2 (s2 , s3 )rrr Ml (sl , s1 ) Å s1√ S sl√ S Å Trace[M1 M2rrrMl ]. The matrix Mj can be constructed in O(ÉSjÉ 1 ÉSj /1É) time and the trace in time proportional to O(minjÉSjÉ). By choosing the Ei suitably, we can obtain ÉSjÉ Å O(1), l Å O(n), so that P1 (n, h1 , h2 ) is computed in O(n) time. If the Ei ’s are isomorphic, then all of the matrices Mj above are identical and equal to M say. In this case, we obtain P1 (n, h1 , h2 ) Å Trace M l , which can be computed in time O(log n) steps. A modification of the basic procedure allows that one of the subgraphs Ei ’s to be nonisomorphic to the others. With the efficient computation of P1 (n, h1 , h2 ), in hand, the efficient computation of R(n, h1 , h2 ) hinges on that of P2 (n, h1 , h2 ), the probability that the network contains disconnected circuits. In the cases treated below, this has polynomial complexity. 8U12 / 8u12$$0773 07-14-97 18:00:34 netwa 83 3. R(n, 1, 1 / (n / 1)/2) FOR n ODD By Lemma 2.1, DL (n, 1, 1 / (n / 1)/2) is strongly isomorphic to DL (n, 2, 3) for n odd. Hence, it suffices to study DL (n, 2, 3) in this section. To avoid trivialities, we assume that n ¢ 4. We consider a probability model which is more general than is the node model by assuming each node has the failure probability p Å 1 0 q, each h2link has the failure probability p2 Å 1 0 q2 (the failures are independent), while the h1-links always work. When p2 Å 0, the above model is reduced to the node model. We begin by specifying some implicit taboo states. Lemma 3.1. DL (n, 2, 3) fails if any three consecutive nodes fail. Proof. The last working node preceding the three conj secutive failed nodes cannot reach any other node. We begin by considering the case where n is divisible by 3. Let Ei , i Å 0, 1, . . . , n/3 0 1, consist of the nodes 3i 0 1, 3i, 3i / 1 and their six outlinks. Then, Ei has 2 9 Å 512 states. There are 2 6 Å 64 taboo states due to the failure of all three nodes, 3r2 6 0 3r2 3 / 1 Å 169 taboo states due to the failure of the outlinks of a working node and (7/8)r2 5 Å 28 taboo states due to the failure of node 3i / 1 and link 3i 0 1 r 3i / 2, while node 3i 0 1 and link 3i 0 1 r 3i / 1 work (the factor of 78 discounts the overlapping with the taboo states in which a node works but its two outlinks fail). Thus, we have ÉSi É Å 512 0 64 0 169 0 28 Å 251. Arrange the Ei ’s cyclically in the natural order. Note that Ei < Ei/1 contains all the inlinks of Ei/1 . Thus, if Si < Si/1 is not a taboo state for each i, then G (s) is nonempty and every node has an inlink and an outlink. Furthermore, Si < Si/1 is a taboo state if and only if two inlinks of a working node in Si/1 fail. Define M as in Section 2 (here it is 251 1 251). Then, P1 (n, 2, 3) Å Trace M n / 3 . The cases n Å 3k / 1, 3k / 2 differ only in the Ek which is larger than the other Ei . It now remains to compute P2 (n, h1 , h2 ). We begin with the following lemma: Lemma 3.2. There can exist at most two disconnected circuits in G (s). Proof. Since a link covers a distance of at most 3, a circuit has at least n/3 nodes. Therefore, there can be at most two node-disjoint circuits except when n is divisible by 3; three circuits each composed of nodes of a residue class modulo 3 may exist. It is easily verified that the three circuits are strongly connected through the 2links (which always work). j W: Networks 773 84 HWANG, WRIGHT, AND HU Arrange the nodes 0, 1, . . . , n 0 1 in an n-cycle in the natural order. A circuit is called a noncrossing circuit if its links do not cross, i.e., it does not wrap around the n-cycle more than once. Lemma 3.3. A crossing circuit has size at least (2n / 1)/3 . Proof. Since the circuit must go around the n-cycle at least twice, and each link covers a distance of at most 3, it must have at least 2n/3 links. If n is not divisible by 3, then 2n/3 Å (2n / 1)/3 . If n is divisible by 3, then the circuit must necessarily contain an h2-link or else it would be an n/3-circuit, which is noncrossing. Therefore, the number of links in the circuit is at least (2n / 1)/3 . j Corollary 3.1. Suppose that G (s) contains more than one disconnected circuit. Then, both circuits must be noncrossing. Proof. The minimum size of a circuit is n/3 . The result follows from the observation that (2n / 1)/3 / n/3 ú n. j Lemma 3.4. If G (s) contains two disconnected circuits, then they are of equal size. Proof. Suppose that G (s) has two disconnected noncrossing circuits C and C *. Consider C and C * on the ncycle. Then, between every pair of adjacent nodes i and j of C in their natural order, there must exist exactly one node of C *. If there were no such node of C *, then the link of C * closest to the link i r j has a length ¢ ( j / 1) 0 (i 0 1) Å j 0 i / 2 ¢ 4 which can be neither an h1- nor an h2-link. Similarly, were there to exist two intervening nodes of C *, then C * has a link whose length is at most ( j 0 1) 0 (i / 1) Å j 0 i 0 2 ° 1, which again can be neither an h1- nor an h2-link. The lemma follows. j Consider the case when G (s) contains exactly two disconnected circuits C and C * each of which has a 2-links and b 3-links. By Corollary 3.1, 2a / 3b Å n. Since each circuit has a / b nodes, the number of nodes not in C < C * is Lemma 3.5. C, C *, and F(C, C * ) must satisfy the following conditions: (i) Let (w1 , w2 , . . . , w2 (a/b ) ) denote the nodes in C < C * in their natural sequence. Then, C Å {w1 , w3 , . . . , w2 (a/b ) 01 } and C * Å {w2 , w4 , . . . , w2 (a/b ) }. (ii) fi/1 0 fi is an odd number greater than 1. (iii) fi is a failed node for all i Å 1, 2, . . . , b. Proof. (i) Suppose that wi and wi/1 are both in C. Since a link covers a distance of at least 2, there exists at least one fj between wi and wi/1 . But then C * cannot be a circuit since no link of C * can skip three consecutive nodes. (ii) If fi/1 0 fi ° 2, then there exist three consecutive nodes not in C (or C * ) and, hence, C cannot be a circuit. If fi/1 0 fi ¢ 4 is an even number, then by (i), fi / 1 and fi/1 0 1 are in the same circuit, say, C. It follows that fi 0 1 and fi/1 / 1 must be in C * or C * would have skipped three consecutive nodes. But C can reach C * through the link fi/1 0 1 r fi/1 / 1, and C * can reach C through the link fi 0 1 r fi / 1, contradicting the assumption that C and C * are disconnected. (iii) By (ii), fi 0 2, fi 0 1, fi / 1, and fi / 2 are all in C < C *. By (i), fi 0 2 and fi / 1 are in one circuit say C, while fi 0 1 and fi / 2 are in C *. Furthermore, C * can reach C through the link fi 0 1 r fi / 1. If fi works, then C can also reach C * through the two links fi 0 2 r fi and fi r fi / 2, contradicting the assumption that C and C * are disconnected. j By Lemma 3.4, the nodes fi 0 1 for i Å 1, 2, . . . , b, are all in one circuit, say, C, and the nodes fi / 1 for i Å 1, 2, . . . , b are all in C *. It follows immediately: Corollary 3.2. C * has no 2-link to C and no 3-link to F. Let F(b) denote the set of b nodes satisfying condition (ii) of Lemma 3.5. Lemma 3.6. É F(b)É Å [n/(a / b)]( a/b b ), where a Å (n 0 3b)/2. Proof. The number of ways of selecting b balls, no two consecutive, from a / 2b balls arrayed in a cycle is a / 2b a/b n 0 2(a / b) Å b. Let F(C, C * ) Å { f1 , f2 , . . . , fb } denote the cyclic sequence of nodes (in their natural order) not in C < C *. 8U12 / 8u12$$0773 07-14-97 18:00:34 netwa S D a/b b , as given by Kaplansky [10]. Partition all selections into classes such that selections on the same class can be W: Networks 773 MOST RELIABLE DOUBLE-LOOP NETWORKS obtained from each other by rotations. Let Ri denote the ith class. Then, É Ri É Å (a / 2b)/mi , where mi is a factor due to the symmetry of the class. Let ri be an arbitrary member of Ri . Splitting each unselected ball of ri into two, we obtain a selection r *i of b balls from b / 2(a / b) Å n balls satisfying condition (ii) of Lemma 4.5. Let R *i be the set of selections obtained from r *i by rotations. Then, É R *i É Å n/mi . Therefore, É R *i É/É Ri É Å n/(a / 2b). Furthermore, there exists clearly a one-to-one mapping between {Ri } and {R *i }. Consequently, É F(b)É Å 85 working nodes are in C < C *, i.e., Cj (s) contains no island, and Lemma 3.2 guarantees that no more than two disconnected circuits can exist. Therefore, P2 (n, h1 , h2 ) is given by the second term on the rhs of Theorem 3.1. Theorem 3.1 follows immediately. Thus, R(n, 2, 3) may be computed in O(n) time. j Corollary 3.3. Under the node model, i.e., p2 Å 0, R(n, 2, 3) Å Trace M n / 3 0 en / 32q 2 n / 3 p n / 3 , where ex Å 1 if x is an integer, and ex Å 0 otherwise. j ∑ É R *i É i Å n ∑ É Ri É (a / 2b) i Å n a / 2b r a / 2b a / b 4. R(n, 1, 1 / n/2) FOR n EVEN S D a/b b Å n a/b We assume the general model in this section. There is an implicit taboo state for DL (n, 1, 1 / n/2). S D a/b b . j Theorem 3.1. R(n, 2, 3) Å Trace M n / 3 n/3 0 ∑ bÅ0 a / 2b a/b S D a / b 2 ( a/b ) b 2 b a q p q2 p2, b where a Å (n 0 3b)/2. Proof. Let C(b) denote the set of pairs of disconnected circuits each consisting of a 2-links and b 3-links. We show that there exists a one-to-one mapping between C(b) and F(b). Let C and C * be a pair in C(b). By Lemma 3.5(ii), F(C, C * ) is in F(b). On the other hand, by Lemma 3.5(i), a member of F(b) only generates one candidate pair (C, C * ). Furthermore, by Corollary 3.2, (C, C * ) is in C(b) whenever all the 3-links from C * to C are failed. We have established the one-to-one mapping. Hence, ÉC(b)É Å É F(b)É. For C and C * to be circuits, the nodes and 3-links in C < C * must all work; the probability of this event is q 2 ( a/b ) q 22 b . By Lemma 3.5(iii), the nodes not in C < C * must all be failed; the probability is p b . Finally, the a / b nodes of C * has b internal 3-links. By Corollary 3.2, the other a 3-links must go to C and they must all be failed to disconnect C and C *. The probability of this event is p a2 . Note that Lemma 3.5(iii) guarantees that all 8U12 / 8u12$$0773 07-14-97 18:00:34 netwa Lemma 4.1. DL (n, 1, 1 / n/2) fails if for some i Å 0, 1, . . . , n/2 0 1, nodes i and i / n/2 fail simultaneously. Proof. The four outlinks of i and i / n/2 constitute the four inlinks of nodes i / 1 and i / n/2 / 1. If one of these latter two nodes works, then that working node along with its two blocked inlinks constitute a taboo state. Therefore, it suffices to consider the case where nodes i / 1 and i / n/2 / 1 both fail. Continuing the argument, we are reduced to the case where all nodes fail, which is a taboo state by convention. j Let Ei consist of the nodes i and i / n/2 together with their four outlinks. We note in passing that this is an example where the subgraphs Ei are not themselves connected. These subgraphs are all isomorphic so they share a common set of taboo states. Denote the set of nontaboo states by S. There are 64 states to begin with. Of these, 16 are taboo states due to the failure of nodes i and i / n/2, and a further eight are taboo due to the failure of the two outlinks of a working node. The above reckoning counts the taboo state due to the failure of all four outlinks of two working nodes twice. Accordingly, ÉSÉ Å 64 0 16 0 8 0 8 / 1 Å 33. Arrange the Ei , i Å 0, 1, . . . , n/2 0 1, cyclically in the natural order. Given the states si and si/1 of Ei and Ei/1 , it is easily verified that if each pair (si , si/1 ) is not a taboo state then G (s) is nonempty and every node has an inlink and an outlink. Furthermore, (si , si/1 ) is a taboo state if and only if Ei contains two failed links incident on a working node of Ei/1 . Define the 33 1 33 matrix M as in Section 2. Then, P1 (n, 1, 1 / n/2) Å Trace M n / 2 . W: Networks 773 86 HWANG, WRIGHT, AND HU The following fact is useful: Fact. H Corollary 4.1. In the link model, S D f(n) å min a / b : a / b 1 / R(n, 1, 1 / n/2) Å Trace M n / 2 n 2 å 0 mod n, a, b ¢ 0 ( n / 201 ) / 2 J ∑ 0 Å j Å0 n 2 S n/2 2j / 1 D 4 j02 4 j/2 q n0 q2 1 4 j02 1 (2p 21 j / 1 p n2 / 202 j 0 1 0 p 21 j / 2 p n0 ). 2 and is attained only at a Å n/2 0 2 j 0 1, b Å 2 j / 1 for j Å 0, 1, . . . , (n/2 0 1)/2 . Corollary 4.2. In the node model, R(n, 1, 1 / n/2) Å Trace M n / 2 Lemma 4.2. G (s) contains at most two disconnected circuits. If there are two, then they are both n/2-circuits, and, furthermore, both circuits have the same number of h1- and h2-links and each circuit uniquely determines the other. Note that R(n, 1, 1 / n/2) Å (1 0 p 2 ) n / 2 was directly argued in [4]. Proof. Since each circuit has at least n/2 nodes (a consequence of the Fact), there can be at most two disconnected circuits, say C and C *. Suppose that C has n/2 0 kh1- and kh2-links. Consider an h1-link in C, say i 0 1 r i. Then, the h2-link i / n/2 0 1 r i must traverse the cut induced by C and C *, which, in turn, implies that i / n/2 0 1 r i / n/2 is an h1-links in C *. Continuing in this fashion and arguing similarly for the h2-links establishes that both link types are equinumerous in C and C * and that one circuit uniquely determines the other. j Lemma 4.3. There are ( n /k2 ) pairs of disconnected circuits, each having kh2-links, for k Å 1, 3rrr, 2 (n/2 0 1)/2 / 1. Proof. The fact that k must be odd is an immediate consequence of the Fact. Since every pair of disconnected circuits contains all nodes and no circuit can occur in two pairs, it suffices to count the number of n/2-circuits containing a particular node, say 0. But starting from 0 and following any sequence of k h2-links and n/2 0 k h1-links always forms a circuit, so the number of distinct circuits containing 0 is just the number of ways of arranging the k h2-links in the circuit. j In summary, therefore, we obtain Theorem 4.1. R(n, 1, 1 / n/2) Å Trace M n / 2 ( n / 201 ) / 2 0 ∑ j Å0 S D n/2 4 j02 4 j/2 q nq n0 q2 1 2j / 1 4 j02 1 (2p 21 j / 1 p n2 / 202 j 0 1 0 p 41 j / 2 p n0 ). 2 Thus, R(n, 1, 1 / n/2) may be computed in O(n) time. 8U12 / 8u12$$0773 07-14-97 18:00:34 netwa 5. THE DAISY CHAIN Before presenting the solution for R(n, 1, n 0 2), it is first necessary to compute the connectivity reliabilities of some auxiliary networks. A circular (respectively, linear) consecutive-2-out-of-n system is a cyclic (respectively, linear) array of n components which fails if and only if there exist two consecutive failed components, which also can be viewed as a braided ring where links never fail. Let RC (2, n, p) [respectively, RL (2, n, p)] denote the reliabilities of such a system when each component works independently with probability p. Hwang [5] gave explicit solutions for RC (2, n, p) and RL (2, n, p) which are computable in O(log n) time: RL (2, n, p) q (2q/p / 1 / 1 / 4q/p) n/ 2 / ( 01) n/ 1 (2q/p) n/ 2 q Å p n ( n/ 1 ) / 2 , ( n/ 1 ) / 2 2 (2q/p / 1 / 1 / 4q/p) q 1 (4q/p / 1 / 1 / 4q/p) RC (2, n, p) q q (1 / 1 / 4q/p) n / (1 0 1 / 4q/p) n . Å p 2n n Next, consider for m ¢ 3 the linear forward-loopbackward-hop network with m nodes, labeled 1, 2, . . . , m, m 0 1 a-links i r i / 1, i Å 1, 2, . . . , m 0 1 and m 0 2 b-links i r i 0 2, i Å 3, 4, . . . , m, illustrated in Figure 2. For this network, we will assume, however, that nodes and a-links always work but that b-links work with probability pb , as before. Denote this network’s reliability by RN (m). Note that links m r m 0 2 and 3 r 1 must both work. In addition, no two consecutive b-links (two b-links starting from consecutive nodes) can fail. These W: Networks 773 MOST RELIABLE DOUBLE-LOOP NETWORKS 87 Fig. 2. An auxiliary linear network. conditions together are necessary and sufficient for the network to be connected, so we obtain H RN (m) Å p 2b RL (2, m 0 4, pb ), m ¢ 4, m Å 3. pb , (5.1) To avoid trivialities, we assume that n ¢ 5. The first order of business is to analyze the cycle structure of the daisy chain. Lemma 5.1. The only simple circuits in DL(n, 1, n 0 2) are. (a) (b) (c) (d) The complete n-circuit with all a-links; i r i / 1 r i / 2 r i for all 0 ° i ° n 0 1; If n is odd, the complete n-circuit with all b-links; Circuits of size c Å 3l 0 n, containing l, b-links and 2l 0 n, a-links, where n/2 ° l ° 2n/3 . Each such circuit wraps (clockwise) l 0 1 times around the n-cycle and has at least n/2 nodes if n is even and (n / 3)/2 nodes if n is odd. Proof. Suppose that the circuit wraps r times around the n-cycle. Then, if s denotes the number of a-links, l denotes the number of b-links, and c denotes the size of the circuit, we have F 1 n02 1 1 GF G F G s l Å rn c s l Å c0r r / c 0 3r n03 F G 1 01 r t Å l 0 / c 0 3l n FG 1 1 . The only possibilities are (a) c Å 3l / n, in which case c Å n, l Å 0, s Å n, and r Å 1; (b) c Å 3l, in which case r Å l and t Å 0, which implies that s Å 2l; (c) c Å 3l 0 2n, in which case c Å n, s Å 0, l Å n, and r Å n 0 2; and (d) c Å 3l 0 n, in which case r Å l 0 1, s Å 2l 0 n, and n/2 ° l ° 2n/3 . Case (a) is the n-circuit. In case (b), we see that l Å 1, s Å 2 for l ú 1, and the underlying topology forces s ° l. Case (c) can occur only for n odd; again, the entire n-cycle is covered, using only b-links. Case (d) presents the interesting possibilities. Note that in this case l ¢ n/ 2 . If n is odd, then s ¢ 1 as well. j The two unique (up to rotation) examples for n Å 9 of case (d): (a) l Å 5 and (b) l Å 6, are illustrated in Figure 3. Next, we characterize a failed daisy chain. Some definitions will prove to be useful. Definitions. A continent (see Fig. 4) is a subgraph of G(s) of consecutive nodes, u, u / 1, . . . , £ Å u / k 0 1 of G(s), 1 õ k õ ÉG(s)É, such that (i) all internal a-links lie in G(s), (ii) there exist no consecutive failed b-links, (iii) the b-links u / 2 r u and £ r £ 0 2 work, and (iv) none of the links £ r £ / 1, u r u 0 2, or u . Inverting yields FG F G FG FG . The integrality and nonnegativity of s and l now imply that n 0 3 divides c 0 3r, so that c 0 3r Å t(n 0 3), s Å c 0 r / t, and l Å r 0 t, where 0 (c 0 r) ° t ° r is an integer. But now we write F 3 n03 1 01 GF G F G r t Å c l and invert to obtain 8U12 / 8u12$$0773 Fig. 3. Circuits of DL(9, 1, 7), case (d): (a) l Å 5; (b) l Å 6. 07-14-97 18:00:34 netwa W: Networks 773 88 HWANG, WRIGHT, AND HU tion. It follows therefore that J > [i / 1, i / 2, . . . , u 0 1] x M, so [i / 1, i / 2, . . . , u 0 1] contains a working node and so the continent so-discovered is genuine. j Fig. 4. A continent. / 1 r u 0 1 lie in G(s). A continent C is genuine if G(s) " C contains a working node and is virtual otherwise. Finally, we call the circuits evinced in Lemma 3.1(d) oceans. Lemma 5.2. A daisy chain DL(n, 1, n 0 2) fails if and only if one of the following three events occurs: 1. G(s) contains an island. 2. G(s) contains a genuine continent. 3. G(s) contains two disconnected oceans (i.e., their union is not strongly connected). Proof. Sufficiency: In condition 1, a working node (the island) is either unreachable or unable to reach other working nodes, except in the trivial case where it is the only working node, which we define to be a failed state. Similarly, in conditions 2 and 3, there exists a pair of working nodes, one of which cannot communicate with the other. Necessity: Let i and j denote two nodes of G(s) with the property that there is no directed path from i to j. Denote by I the subgraph of G(s) induced by the set of nodes reachable from i in G(s), and by J, the subgraph induced by the set of nodes in G(s) which can reach j. Then, I and J are node-disjoint. If either É IÉ Å 1 or É JÉ Å 1, then an island exists. Assume, therefore, that no islands exist. If I contains a path which wraps around the n-cycle, then it must contain at least one node from every consecutive pair of nodes. Consequently, J cannot contain any two consecutive nodes. But this, in turn, implies that any circuit in J consists exclusively of b-links, which, in turn, is possible only if n is even, and I and J consist, respectively, of the nodes of a given parity (odd or even). Suppose therefore that I does not contain a path which wraps around the n-cycle. Starting from i, and proceeding counterclockwise around the n-cycle, let u denote the last node of I. Then, necessarily, u has no b-link in G(s), which, in turn, implies that the link u r u / 1 exists in G(s). Similarly, proceeding clockwise around the n-cycle, let £ denote the last node of I. Then, the a-link £ r £ / 1 is not in G(s). Since there are no islands, the link u / 1 r u / 2 must lie in G(s), which, in turn, implies that u / 2 r u lies in G(s) as well. If u / 2 r u / 3 does not exist in G(s), then the set {u, u / 1, u / 2} constitutes a continent. Otherwise, by continuing in this fashion, we see that I contains a continent. By Lemma 5.1, no circuit of J may lie in the interval [u, u / 1rrr, i], for, then, I would be disconnected from u, a contradic- 8U12 / 8u12$$0773 07-14-97 18:00:34 netwa Two corollaries of the proof of Lemma 5.2 are the following: Corollary 5.1. A daisy chain fails if it contains a set S of consecutive failed nodes, É SÉ ¢ 2 plus another failed node x, not adjacent to S. Corollary 5.2. If all nodes of a daisy chain work, no islands exist, and, in addition, there exists no pair of consecutive failed b-links, then condition 3 of Lemma 5.2 is necessary and sufficient for the failure of the daisy chain. The computation of R(n, 1, n 0 2) proceeds as follows: Denote the events defined by the conditions of Lemma 5.2 by Ai , i Å 1, 2, 3. Define in addition, the following events: A4 : No consecutive pairs of b-links fail. A5 : All nodes and all a-links work. Note that unlike conditions A1 , A2 , and A3 , conditions A4 and A5 are not conditions on G(s). In G(s), a link is deleted if either of its terminal nodes fails, even it itself is not failed. Note further that A3 , A 1c > A4 > A 5c , A5 , A 2c > A 1c and A4 , A 2c . The relationships between the sets are illustrated by the Venn diagram of Figure 5. From the proof of Lemma 5.2 and Corollaries 5.1 and 5.2, we obtain R(n, 1, n 0 2) Å Pr{A 1c > A 2c > A 3c } Å Pr{A 1c > A 2c > A 3c > A4 } / Pr{A 1c > A 2c > A 3c > A 4c } (5.2) Å Pr{A 1c > A4 } / Pr{A 1c > A 2c > A 4c } 0 Pr{A3 } Å Pr{A 1c > A4 } / Pr{A 4c > A5 } / Pr{A 1c > A 2c > A 4c > A 5c } 0 Pr{A3 }. It is easily verified that the only case in which more than one ocean exists is when n is even; one ocean consists of all odd nodes and the b-links between them, and the other, of all even nodes and the b-links between them. For the two oceans to be disconnected, at least one set of a-links from one ocean to the other must all fail. Hence, Pr{A3 } is simply en (ppb ) n (2q na / 2 0 q na ), where W: Networks 773 MOST RELIABLE DOUBLE-LOOP NETWORKS 89 Fig. 5. Relation between the sets Ai , i Å 1, rrr5. en Å H 1, membership in A 1c > A 2c > A 5c . The case of a single failed node is handled similarly. Accordingly, we obtain if n is even, 0, if n is odd. Pr{A 1c > A 2c > A 4c > A 5c } n0 2 Similarly, Å Pr{A 4c > A5 } Å (ppa ) n[1 0 RC (2, n, pb )]. (5.3) Lemma 5.3. The event A 1c > A 2c > A 5c is equivalent to the existence of a virtual continent of size at most n 0 2 or a single failed node k with failed b-links k / 2 r k and k / 1 r k 0 1. Proof. To see this, observe that on this set at least one consecutive pair of b-links and at least one node or alink fails, the network still works, and the surviving network has no islands or genuine continents. Let k / 2 r k and k / 1 r k 0 1 denote two consecutive failed blinks. There must be at least one failed node. For if there is none, then there is a failed a-link, say i r i / 1. But, then, the (working) node k is unreachable from i. If there is a single failed node, then it must be k, since in all other cases, the working node k would be unreachable. If there are two or more failed nodes, then the set of failed nodes must constitute a consecutive set, for, otherwise, the network would be disconnected. Since the network is connected, the set of working nodes must then form a virtual continent. Conversely, suppose that there is a virtual continent C of size m ° n 0 2, say {k, k / 1, . . . , l Å k / m 0 1. By definition, all nodes and a-links in C work, at least one a-link fails (i.e., l r l / 1), and no node outside C works. These are precisely the conditions required for 8U12 / 8u12$$0773 07-14-97 18:00:34 1 RN (m) ∑ p mq n0m p m0 a (5.4) mÅ3 netwa 1 [1 0 RL (2, n 0 m / 3, pb )] 2 / p n0 1qp n0 qb RL (2, n 0 5, pb ). a Finally, we are left with Pr{A 1c > A4 }. The argument is simplest for n a multiple of 3, i.e., n Å 3l. For i Å 0, . . . , l 0 1, let Ei consist of the nodes 3i, 3i / 1, 3i / 2, the a-links 3i r 3i / 1, 3i / 1 r 3i / 2 and 3i / 2 r 3(i / 1), as well as the b-links 3i / 1 r 3i 0 1, 3i / 2 r 3i and 3(i / 1) r 3i / 1. Then, Ei has 2 9 Å 512 distinct states and ÉSÉ Å 214. The nontaboo link states, given the number of states of the nodes, are enumerated in Table I. TABLE I. Enumeration of nontaboo states of Ei 3i 3i / 1 3i / 2 # States 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 40 20 16 10 40 36 20 22 214 W: Networks 773 90 HWANG, WRIGHT, AND HU Define M as in Section 2. Then, [ 2] Pr {A 1c > A4 ) Å Trace M l . [ 3] The easy extension to the case n å / 0 mod 3 is left to the reader. [ 4] 6. CONCLUSIONS We adopted the transfer matrix method to compute the reliability of the daisy chain and DL (n, 1, 1 / n/2 ) under the uniform model except that for odd n we need to assume that h1-links always work. The time complexity is O(log n), except for the last case, where it is O(n). Previously, applications of the transfer matrix method depended crucially on h1 and h2 being in the set {1, 2, n 0 1, n 0 2}. The current paper gives the first attempt of extending the applicability outside of that set. In particular, the exact reliability of all the most reliable networks previously obtained for the node model and the link model are now known. It should be pointed out that our result for DL (n, 1, 1 / n/2) for even n and the Daisy chain can be easily extended to the general model with the time complexity increasing to O(n). [ 5] [ 6] [ 7] [ 8] [ 9] [10] [11] REFERENCES [12] [1] 8U12 C. J. Colbourne, The Combinatorics of Network Reliability. Oxford University Press, New York (1987). / 8u12$$0773 07-14-97 18:00:34 netwa M. A. Fiol, J. L. A. Yebra, I. Alegre, and M. Valero, A discrete optimization problem in local networks and data alignment. IEEE Trans. Comput. C-36 (1987) 702–713. A. Grnarov, L. Kleinrock, and M. Gerla, A highly reliable distributed loop network architecture. Proceedings of the International Symposium on Fault-Tolerant Computing, Kyoto, Japan (1980) 319–324. X. D. Hu, F. K. Hwang, and W-C. W. Li, Most reliable double loop networks in survival reliability. Networks 23 (1993) 451–458. F. K. Hwang, Simplifical reliabilities for consecutive-kout-of-n systems. SIAM J. Alg. Discr. Methods 7 (1986) 258–264. F. K. Hwang and W.-C. W. Li, Reliabilities of double loop networks. Prob. Info. Eng. Sci. 5 (1991) 255–272. F. K. Hwang and W.-C. W. Li, Connectivity reliabilities and Hamiltonian reliabilities of linear and circular consecutive-2 link systems. Rel. Qual. Saf. Eng. 1 (1994) 247–256. F. K. Hwang and P. E. Wright, Survival reliabilities of some double-loop networks and chordal rings. IEEE Trans. Comput. 44 (1995) 1468–1471. O. C. Ibe, Reliability comparison of token ring network schemes. IEEE Trans. Rel. 41 (1992) 288–293. I. Kaplansky, Solution of the ‘‘problème des ménages.’’ Bull. Am. Math. Soc. 49 (1943) 784–785. M. T. Liu, Distributed Loop Computer Networks, Vol 17, Advances in Computers. Academic Press, New York (1981) 163–221. C. S. Raghavendra, M. Gerla, and A. Avizienis, Reliable loop topologies for large local computer networks. IEEE Trans. Comput. C-34 (1985) 46–55. W: Networks 773

1/--страниц