A Comparative Reliability Study of Computer Network Configurations forLarge-Scale Accelerator Systems
Edward W. Kamen and S. Simon Singhkamen@ee.gatech.edu
singh@ee.gatech.edu
School of Electrical & Computer Engineering
Georgia Institute of Technology
Atlanta, GA 30332, USAAbstract
A comparative study is given on the reliability ofdifferent possible network configurations for computercommunications in large-scale accelerator systems, withthe focus on bus, double ring, and switching hub networks.
The measure of reliability is based on the computation of
the probability that all nodes in the network are operativeand can communicate with each other. Expressions for thisprobability are generated for each of the three network
configurations, and then are evaluated to yield a definitive
comparison in terms of reliability.
1 Introduction
The tremendous complexity of large-scale accelerator
systems has resulted in the need for an information andcontrol network that can meet very demanding
requirements in terms of reliability, speed, capacity, cost,etc. Performance and cost issues are not only important inexperimental physics systems - they are also of central
importance in the use of accelerators for manufacturing
materials such as the accelerator production of tritium (see[1]). In particular, for accelerators to be viable for
manufacturing applications, the information and control
network will have to possess a very high degree ofreliability to insure that downtime is kept to a minimum.
In building a new accelerator facility, or in upgrading an
existing one, a fundamental question is how to design theinformation and control network to meet a very stringent
reliability requirement. This paper is a first attempt toaddress this issue from an analytical standpoint, with thefocus on the computer communication network thatinterconnects input-output controllers to terminals in amaster control room. We do not consider the reliability ofdevice-level networks (fieldbuses) interconnecting valves,actuators, PLCs, sensors, etc. However, the analysis
developed here should be applicable to fieldbuses.
In the existing literature on reliability in computercommunication networks, we have expressions forterminal-pair reliability. These expressions give theprobability that a specific pair of nodes in a network cancommunicate with each other, but do not give a good
"global measure" of reliability across a network. In
applications, an important requirement is that failures in
the network should not disrupt communications between
operative nodes. Hence, a meaningful (global) measure ofreliability is the probability that all operative nodes cancommunicate with each other. This probability, denoted by
P(C), was studied by Ball [2] in the context of generalcomputer communication networks. Ball developed ageneral procedure for determining P(C) based on a
network decomposition scheme. Specific expressions forP(C) were generated by Lin and Silio [3] for single-ringand double-ring networks.
Another important global measure of reliability is theprobability P(A) that all nodes are operative and cancommunicate with each other. In this paper, the primaryobjective is to generate expressions for P(A) for threedifferent possible network configurations for computercommunications in a large-scale accelerator system. These
are bus, double ring, and switching hub networks. All three
types of configurations have been used, or are underconsideration for possible implementation, in accelerator
systems. A switching hub configuration was proposed in[1].
In the next section, we describe the three different
possible network configurations for an accelerator system,and then in Section 3, we generate expressions for P(A) for
an N-node network. In Section 4 we evaluate P(A) for
various values of the probabilities of failure of the nodes,links, and switches comprising the network. This yields adefinitive comparison (in terms of reliability) of thedifferent network configurations. Concluding comments
are given in Section 5.
2 Network configurations
As is well known, a group of computers can be connected
together in the three generic configurations of bus, doublering, and star (switching hub). In the application toaccelerator systems, this threesome translates into thenetworks illustrated in Figures 1, 2, and 3. As noted in theIntroduction, we focus only on connections of the inputoutput controllers (IOCs) to the terminals in the master
control room (MCR). In Figures 1-3, the MCR is shown asa single block connected to the network, although in reality
there will be a number of nodes in the MCR. We also showa gateway to other networks.
For the bus configuration illustrated in Figure 1, thenetwork will go down if any node or link on the network
fails, where a node consists of the bus interface and hostattachment point. For the network illustrated in Figure 2,
some robustness to link failure is built in as a result of thedouble ring structure of the network. In particular,
communications can be diverted from the primary ring to
the secondary ring as a result of a link failure. Robustness
to node failures is also provided by the addition of bypass
switches that switch off nodes that have failed.

IOCIOCIOC

Now let C denote the event that all operative nodes of an
N-node network can communicate with each other, and letP(C) denote the probability of C. To compute P(C), wefirst define the following events:
B0 = event that all nodes have failed

IOCIOCIOC

B1 = event that one node is operative and all other nodes
have failed
Bi = event that i nodes are operative and cancommunicate with each other, where i = 2,3,...,NIOC

MCR

gatewayN

Clearly, C = U Bi , and Bi I B j = ∅ , i ≠ j ,Figure 1 Bus configuration

i =0NIOCIOCand thus P( C ) = ∑ P( Bi ) .

IOCIOCIOC

i =0Using the values for P( B0 ) and P( B1 ) , we haveIOCIOCN

P( C ) = q N + N (1 − q ) q N −1 + ∑ P( Bi )IOCi =2IOCMCR

As noted in the Introduction, there exist papers onnetwork reliability that are based on the computation ofP(C). In this paper, the primary interest is on thecomputation of P(A), where A is the event that all nodes
are operative and can communicate with each other.
Clearly, P(A) = P( B N ), since by the above definition

gateway

Figure 2 Double ring configuration

MCR

SWITCHIOCIOCSWITCH

SWITCHIOCIOC

A= B N . Obviously, P(C) is always greater than or equal toP(A). The computation of P(A) for each of the three
configurations shown in Figures 1-3 is given below. In thiscomputation, for the bus and ring networks it is assumed
that failures of nodes, links, and switches are independent
events. For the switching hub network, it is assumed that
failures of links and switches are independent. The analysis
given below does not include the possible failure ofnetwork interface cards (NICs), since in this paper a NIC isviewed as being part of a host, not part of the network.

gatewaySWITCHIOCIOCFigure 3 Switching hub configuration

3.1 Bus configuration

As shown in Figure 3, the star configuration is given interms of a central switching hub as the backbone of thecomputer network. Collections of IOCs are connected tolocal switching hubs, which in turn are connected to thecentral hub. In this framework, all nodes (host attachmentpoints) on a switch are operative if the switch is operative.
The local switching hubs shown in Figure 3 are also
connected together to provide robustness to failures in thelinks from the local hubs to the central hub. This is theconfiguration proposed in [1].

First, consider the N-node bus configuration illustrated inFigure 4. In this case, a node on the network consists of abus interface and a host attachment point. Note that thenetwork has two end-point terminations and a total of N+1links. For any two operative nodes on the network to beable to communicate, it is necessary and sufficient that thetwo end-point terminations, all the links, and all the nodes
be operative. Letting the probability of failure of atermination be denoted by T, the probability of failure of alink be denoted by DL, and the probability of failure of anode be denoted by q, we have that

3 Reliability analysis

P( A) = (1 − q ) (1 − DL)N

Given an N-node computer communication network, let q
denote the probability that, at a random point in time, anode fails. Assuming that failures of nodes are independent
events, the probability that all nodes have failed is q N ,and the probability that all nodes are operating is (1 − q ) .
NThe probability that only one node is in operation and allothers have failed is N (1 − q) q N −1 .

N +1

(1 − T ) 2

Note that in this case, P(A) = P(C).
3.2 Double ring configuration
Consider the section of an N-node double ring
configuration shown in Figure 5. In this case, a node on thering consists of a ring interface and a host attachment
point. As shown in Figure 5, each node on the double ringis connected to two bypass switches which short togetherhost attachment point
terminal

bus interface

and can communicate with each other whenever the switch
is working. The probability of failure of a switch isdenoted by DS.
Now let E denote the event that all switches in theconfiguration shown in Figure 3 are able to communicate
with each other. Then P(A) for this configuration is givenby P(A) = (1 − DS ) P( E ) where P(E) is the probability
Mlink

link

Figure 4 N-node bus network
the links on the bus and switch off the nodes in the case ofa node failure. The probability of failure of a bypass switch
is denoted by DS, and the probability of a link failure isdenoted by DL.
bypass switch
linkhostattachment
pointringinterfaceof the event E.
To compute P(E), we first decompose E as follows. Let
G0 denote the event that all links from the central hub to
the local hubs in the configuration in Figure 3 areoperative, and the links between the local hubs are either
working or not working. Obviously, when G0 occurs all
switches in the network can communicate with each other.
For i = 1,2,...,(M-2), let Gi denote the event that all links
from the central hub to the local hubs, except for i of them,are operative and all switches in the configuration cancommunicate with each other. Note that if all M-1 links
between the central hub and the local hubs fail, not all ofthe switches can communicate.
M −2

Clearly E = U Gi
i =0and since the Gi are mutuallyM −2

disjoint events, P( E ) = ∑ P(Gi ) . It is easily seen thati =0link

Figure 5 Section of double ring
The derivation of P(C) for a double ring with nodal
bypass switches was carried by Lin and Silio [3]. The
derivation of P(C) given in [3] can be modified to yield anexpression for P(A): First, in the case when either the inner
loop or the outer loop of the double ring is operative, theprobability that all nodes are operative and cancommunicate with each other is given byP(G0 ) = (1 − DL)

M −1, P(G1 ) = 2( M − 2)(1 − DL)

and P(Gi ) = α i (1 − DL)

M −1

M −1

DL ,( DL) , for i= 2,3,...,M-2 andifor some positive real numbers α i . Inserting these
expressions for the P( Gi ) into the expression for P(E) and(1 − DL) M −1 gives P(E) equal to(1 − DL) M −1[1 + 2( M − 2) DL + α 2 DL2 +...+α M −2 DLM −2 ]factoringout(1 − q ) N [2(1 − DS ) N (1 − DL) N − (1 − DS ) 2 N (1 − DL) 2 N ]Neglecting the second-order and higher-order powers of
DL in the sum within the bracket, we have thatIn the case when both the inner and outer loops are broken,
the probability that all nodes are operative and cancommunicate is given byand hence using the above expression for P(A), we haveN (1 − q )N[(1 − DS ) (1 − DL)
2N

2 ( N −1)

( DL) ]
2P(A) is then given by the sum of the above two
expressions; that is, P(A) is equal to(1 − q ) N [2(1 − DS ) N (1 − DL) N − (1 − DS ) 2 N (1 − DL) 2 N ]+N (1 − q )N[(1 − DS) (1 − DL)
2N

2 ( N −1)

( DL) ]
2

P( E ) > (1 − DL )P( A) > (1 − DS )M −1M

[1 + 2( M − 2) DL](1 − DL) M −1[1 + 2( M − 2) DL]

Thus we have a lower bound for P(A), and in fact, thisbound is a fairly tight bound since the neglected terms inthe derivation of the lower bound are second and higherorder powers of DL, which will be a small number. In thenext section, we use the lower bound on P(A) to makecomparisons with the P(A) values for the bus and double
ring configurations.

3.3 Switching hub configuration

4 Comparison of configurations

Consider the switching hub configuration shown inFigure 3, and suppose that there are M switches. Here thenodes are the host attachment points on the switches which
are connected by interswitch links, each having aprobability of failure equal to DL. Note that there are atotal of 2M-3 links in the configuration shown in Figure 3.
It is also assumed that all nodes on a switch are operative

In our evaluation of the expressions for P(A) given in theprevious section, we let N equal 206. This corresponds tousing five nodes as connections to consoles of the MCR,
one node for the gateway to another network, and 200
nodes for the input-output controllers. In the case of theswitching hub configuration shown in Figure 3, we use a
total of 21 switches so that M = 21. This corresponds torequiring a minimum of 26 ports on the central switch anda maximum of 13 on the local switches.
For the values of the failure probabilities of the network
components shown in Table 1, the values for P(A) areplotted in Figure 6. It should be noted that the computationof P(A) for the switching hub is actually the lower boundgiven in Section 3. As is clearly evident from the plot, theswitching hub configuration has a much higher degree ofreliability in terms of the P(A) measure than the bus anddouble ring configurations.
Table 1 Scenarios for failure probabilities of network elements
r1r2
r3
r4
r5q, T
10 −3
10−3
10−3
10−3
10−3−
3−4−4−5DL1010101010−6
DS10−3
10−3
10−4
10−4
10−5
10.9
0.8
0.7
0.6

P(A) lower bound values forswitching hub
P(C) values for double ringP(A) values for double ringP(A) values for bus

r1r2
r3
r4
r5
Scenarios for failure probabilities of network elements
Figure 6 Network Reliability Values
It is also interesting to note from Figure 6 that the P(A)values for the bus and double ring are somewhat
comparable. Hence in terms of the P(A) measure, there is
not much of an increase in robustness as result of using asecond ring in the ring network. However, as shown inFigure 6, the P(C) values for the double ring network aremuch better than the corresponding values for the bus. The
reason for this is due to the fact that all nodes must beoperative in the bus, so that P(A) = P(C) in this case. Butfor the double ring, not all nodes have to be operative since
failed nodes can be switched out, and thus P(C) will belarger than P(A) for the double ring. Again looking at
Figure 6, it is quite interesting to observe that the lower
bound for the P(A) values of the switching hub are better
than or comparable to the corresponding P(C) values forthe double ring.
5 Concluding comments

Analytical expressions for the probability P(A) that allnodes are operative and can communicate were generated
for the basic computer network configurations of bus,
double ring, and switching hub. The approach developed
here can be applied to more complicated networks
consisting of mixtures of bus, ring, and switching hub
configurations (see [4]).
Given cost constraints on the selection of network
components and reliability values for the components, aproblem of major interest is determining the configurationthat yields the maximum possible value of P(A). In future
work, we hope to be able to use the analytical formulation
for P(A) to compute the increase in reliability that can beobtained by adding redundant links and switches.
In addition to reliability and cost, there is also theimportant factor of network performance under various
traffic load distributions. With the move to very highbandwidth networks, such as Gigabit Ethernet, it appears
that a very high degree of capacity will be readily
obtainable for both broadcast-based and connection-based
networks. An interesting question is whether or not aquantitative formulation can be developed for network
performance under various traffic loads, and which could
be integrated together with the quantitative measure ofreliability given above in terms of P(A), or some othermeasure of reliability. We leave this an open area ofresearch.
Acknowledgments
This work was supported in part by Westinghouse
Savannah River Company.
References[1] Kamen, E. and Gazarik, M. "APT Process Control andInformation Network Architecture: Phase I --ScopingAnalysis", School of Electrical and Computer
Engineering, Georgia Institute of Technology, Atlanta,
GA, 1996 .
[2] Ball, M. "Computing Network Reliability", Operations
Research, vol. 27, no. 4, July-Aug. 1979, pp. 823-838.
[3] Lin, N. and Silio, C. "A Reliability Comparison ofSingle and Double Rings", Proceedings of IEEE
INFOCOM'90:
ConferenceonComputerCommunications, pp. 504-511, San Francisco, CA,
June 1990.
[4] Kamen, E. and Singh, S. "A Comparative Reliability
Study of Computer Communication Networks," inpreparation.