close

Вход

Забыли?

вход по аккаунту

?

221

код для вставкиСкачать
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
Документ
Категория
Без категории
Просмотров
2
Размер файла
162 Кб
Теги
221
1/--страниц
Пожаловаться на содержимое документа