JMay
2005 Issue: 35
JMay
2005 Issue: 35
Journal of Conceptual Modeling
www.inconcept.com/jcm
A
Reliability Assessment Model for Switched-Chaining
Type Modular Design Based Software Systems
Raghuraj Singh, Assistant Professor
Onkar Singh Assistant Professor
Yogesh Singh, Professor &
Dean
Abstract
This paper considers the problem of assessing the reliability of a switched-chaining software system, which has a generalized modular design based structure. Reliability expression for the software system in terms of the individual module reliabilities and their transition probabilities has been developed. It has been assumed that the system follows Markov chain process for the transfer of control among modules. Reliability expression so developed has also been used to develop reliability expressions for branching and sequential software systems. This demonstrates that branching and sequential software systems are particular cases of the switched-chaining system and no special reliability expressions are needed for them.
Keywords: Software reliability, switched-chaining systems, modular design, Markov chain, reliability expression.
1.
Introduction
The software development industry has begun to place much more emphasis on
software quality. This has led to increasingly large body of work being done in
the area of software quality measures such as reliability. A very large number
of reliability estimation and assessment models have been proposed for different
quality design methodologies. A discussion of such measures can be found in [1]
[5] [9] [10] [12][13] [15]. A study on software systems with Markov transfer of
control among modules has been reported in [2] [3] and effects of combining
diverse software fault detection techniques have been discussed in [16]. A
reliability analysis of large software systems and telecommunication systems has
been done in [4] [11] [14]. Introduction of redundancy has been one of the major
strategies to improve reliability of systems. An evaluation of such strategies
has been done in [6].
In this paper, we have developed software reliability expression, in terms of the individual module reliabilities and their transition probabilities, for a switched-chaining system, which has a generalized modular design based structure. Reliability expression for the switched-chaining system has also been used to develop reliability expressions for branching and sequential software systems [10], which demonstrate that these are particular cases of the switched-chaining systems and no special reliability expressions are needed for them.
1.1 System Description
A system has been assumed to consist of n modules labeled with integer numbers 1, 2, . . ., n and a terminal module T. Although there may be many terminal modules but without loss of generality we have assumed that there is only one terminal module. Such a complete system can be described with a quintuple (S, I, f, s, T), where S = {1, 2, 3, . . ., n, T}, I is set of input points, f the transition function, s the initial (start) module taken as 1 and T the terminal module. Transition function can be better described by the transition probability matrix P i.e. Pi,j , which is the ideal probability that control will be passed from module i to module j.
Since all transition modules are failure prone, let us assume that the module i has an associated reliability ri, which is the probability that the module will complete its fault free operation and successfully transfer control when finished. For an imperfect system like under consideration, the probability Pi,j will be modified to ri.pij. It has been also assumed that the transfer of control among modules takes place according to Markov chain [5], which means that future behavior of the system is conditionally independent of the past behavior and that the system will eventually complete its mission success and enter the terminal state.
The system behavior with respect to the execution process will be described through a Markov chain with the following parameters.
S = Number of states of the chain, where a state means the module under
execution.
λi = Failure rate of the ith module.
Pi,j = P
{System makes transition from state i to state j | start or end of execution of
one or several modules}, i = 1,
2, . . ., S, j = 1, 2, . .
., S and
A system will fail if any of
its modules fails during execution. Thus the system failure rate
in
a state will be sum of the failure rates of the modules under execution in this
state.
j=1,
2, . . ., n
(1)
Where,
,
if module i is under execution in state j; and 
otherwise.
2. Formulation of Reliability Expression
For the purpose of calculating reliability of the system we are only concerned with those Markov chains, which initiate at initial state and terminate at the terminal state. Such Markov chains will pass through only a limited subset of the modules/states of the system [7]. In the simplest form the chain may not pass through any state but in general it may pass through any number of states.
Let
us use 
to
denote a Markov chain that starts at the state i, terminates at the state j and
does not pass through any state numbered greater than k. However there is no
restriction on i and j to be less than or equal to k. Thus,
=
for
q = 1, 2, . . ., p.
For
the chain there
are two cases to consider
·
The chain does not go through a state k at
all; in this case the chain may be denoted by
· The chain goes through the state k at least once. In this case chain may be broken into sub-chains pictorially represented by fig. 1.
Fig. 1: Schematic diagram of a Markov chain
Thus, 
Where +, . , and *
denote OR, followed by, and repetition operations respectively.
But we have to, for calculating reliability, concentrate only on
Or, in general on
Where
i =1, 2, . . . , n (2)
Let
represents
the probability that system starts in the state i, eventually reaches to the
state j but does not pass through any state numbered greater than k.
Thus will
be expressed as:
(3)
Relation (3) is a generalized recurrence relation which denotes the system reliability. In particular, if the initial state is 1 and the total number of transient states are n, then
(4)
This recurrence relation can be solved to give the system reliability, knowing
that 
where
is
the reliability of the state i and
is
the probability that the system makes transition from the state i to state j. If
i is any specified transient state, then relation (4) may be written in the form
(5)
Where,
·
is
the reliability of the system which start in state 1, finally reaches to
terminal state T and does not go through state 1.
·
is
the reliability of the system which start in state 1, finally reaches to state i.
·
is
the reliability of the system which start in state i, finally reaches to
terminal state T and does not go through state i, and
·
is
the reliability of the system which start in state i, finally reaches to state i.
|
|
Schematically, relation (5) can be represented by fig.2, where wavy lines indicate that these are not one step transitions.
Fig. 2: Schematic representation of relation (5)
2.1 Switched-Chaining Systems
In this section, we develop reliability expression for a switched-chaining system. This system not only has sufficient generality but also a rich structure generally followed in modular design. The transition graph of the system is given in fig. 3. State 1 acts as a central control which may transfer control to some specified number of states 2, 3, . . ., k, back to itself or to the terminal state T. Each of the switching states 2, 3, . . ., k may transfer control back to itself or to the state k+1. From the state k+1, the control chains to k+2, k+3, . . ., n except that at each state, control may return to that state, go to the state k+1, or go to the terminal state T. Control may also come back to the state 1 from the state k+1.
Fig. 3: A Switched-Chaining System
|
|
Relation (5) with i = 1 will be used to compute the
system reliability
.
Here it is clear that when i =1,
=
0 and =
1. In order to reach T from state 1 without returning to state 1, the system
must either go directly to T, or to some branch state 2, 3, . . ., k, stay at
that branch state for some q transitions, and then go to a state k+1, visit the
states k+1, k+2, . . ., k+p, T for some p with any number of returns to the
intermediate states k+1, k+2, . . ., k+p. Therefore, it follows that
=
+
+
=
(6)
In Similar way,
Therefore, from (5), the system reliability is
= 
(7)
(8)
Where 
and
are
given in (6) and (7) respectively.
An example for calculating reliability of a switched-chaining system has been discussed in Singh [8].
3. Branching and Sequential Systems
Reliability expressions for the branching and sequential systems have been developed in [10]. For convenience schematic diagrams of the branching and sequential software systems have been reproduced as fig.5 and fig. 6 respectively.
Fig. 5: Branching System Fig. 6: Sequential Systems
If we consider fig. 5 as a special case of switched-chaining system, substitutions T for k+1, and n for k, with no existitence of the state k+2, k+3, etc. and hence taking the corresponding values of transition probabilities as 0 are needed in the reliability equation (6), (7) to derive the reliability equation for the branching systems, which will come out to be as follows:
=
+
=
+
=
/
(9)
In Similar way,
=
+
=
+
= 
/
(10)
Similarly, considering fig. 6 as a special case of switched-chaining system, substitutions 1 for k+1, 2 for k+2, and 3 for k+3 with no existence of the states 1,2, …, k and hence taking corresponding transition probabilities as 0, the reliability equation for sequential system can be derived from the relation (6), (7) as follows:
=
+
=
+
(11)
In Similar way,
=
+
=
+
(12)
Therefore, from (5), the reliability expression for branching and sequential
systems will be where
and
for
branching and sequential systems are given in (9), (10) and (11), (12)
respectively.
4. Conclusions
In this paper, reliability expression for a switched-chaining software system, which is based on modular design philosophy with control transfer among the modules according to Markov process, has been developed. This reliability expression has also been used to develop reliability expressions for the branching and sequential systems discussed in Siegrist [10]. It has been observed that reliability expressions for branching and sequential systems formulated in (9), (10), (11), and (12) are exactly same as the relations (10), (11), (13), and (14) derived in Siegrist [10], which demonstrate that branching and sequential software systems are particular cases of the switched-chaining system and no special reliability expressions are needed for these systems.
References
[1]. Zhang X, Teng X, Pham H. Considering fault removal efficiency in software reliability assessment. IEEE Trans. Systems, MAN, and Cybernetics-Part A: Systems and Humans, Jan 2003; 33(1):114-28.
[2]. Baier C, Haverkort B, Hermanns H, Katoen JP. Model checking algorithms for continuous-time Markov chains. IEEE Trans. Soft Eng, June 2003; 29(6):525-41.
[3]. Rajgopalan J, Mazumdar M. Modular operational test plans for inferences on software reliability based on Markov model. IEEE Trans. Soft Eng, April 2002; 28(4):358-63.
[4]. Kaachie K, Kanoun K, Cukier M, Batos MM. Software reliability analysis of three successive generations of a switching system. Proc. First European Conf Dependable Computing (EDCC-l) 1994; 473-90.
[5]. Cheung RC. A user-oriented software reliability model. IEEE Trans Soft Eng, Mar 1980; SE-6.
[6]. Eckhardt DE, Caglayan AK, Knight JC, Lee LD, McAllister DF, Vouk MA, et al. An experimental evaluation of software redundancy as a strategy for improving reliability. IEEE Trans Soft Eng 1991;17(7):692-702.
[7]. McNaughton R, Yamada H. Regular expressions and state graphs for automata. IEEE Trans Electronic Computers, Jan 1960; 9(1):39-47.
[8]. Singh R, Singh Y. A reliability model for modular design based software system. J Ultra Scientist of Physical Sciences, Aug 2002;14(2):210-17.
[9]. Kuo SY, Huang CY, Lyu MR. Framework for modeling software reliability using various testing efforts and fault detection rates. IEEE Trans Rel, Sept 2001;50(3):310-20.
[10]. Siegrist K. Reliability of systems with Markov transfer of control. IEEE Trans Soft Eng, July 1988;4(7):1049-53.
[11]. Levendel Y. Reliability analysis of large software systems: defects data modeling. IEEE Trans Soft Eng, Feb 1990;6(2):141-52.
[12]. Adams T. Total variance approach to software reliability estimation. IEEE Trans Soft Eng, Sept 1996;22(9):687-88.
[13]. Huang CY, Lyu MR. A unified scheme of some nonhomogenous poisson process models for software reliability estimation. IEEE Trans Soft Eng, Mar 2003;29(3):261-69.
[14]. Kaaniche K, Kanoun K. Reliability of a telecommunications system. Proc Seventh Int’l Symp Soft Rel Eng 1996;207-12.
[15]. Boland PJ, Singh H. A birth-process approach to Moranda’s geometric software reliability model. IEEE Trans Rel, June 2003;52(2):168-74.
[16]. Littlewood B, Popov PT, Stregini L, Shryane N. Modeling the effects of combining diverse software fault detection techniques. IEEE Trans Soft Eng, Dec 2000;26(12):1157-67.
Raghuraj Singh
Assistant Professor
Computer Science & Engg. Department
H.B.T.I., Kanpur-208002
Email:
raghurajsingh@rediffmail.com
University School of Information Technology
G.G.S. Indraprastha University
Kashmiri Gate, Delhi-110006
Email:
ys66@rediffmail.com
Onkar Singh
Assistant Professor
Mechanical Engg. Department
H.B.T.I., Kanpur-208002
Email:
onkpar@rediffmail.com
University School of Information Technology
G.G.S. Indraprastha University
Kashmiri Gate, Delhi-110006
Email:
ys66@rediffmail.com
Yogesh Singh
Professor & Dean,
University School of Information Technology,
G.G.S. Indraprastha University,
Kashmiri Gate, Delhi-110006
Email:
ys66@rediffmail.com
University School of Information Technology
G.G.S. Indraprastha University
Kashmiri Gate, Delhi-110006
Email:
ys66@rediffmail.com
