# A Dynamical Reliability Prediction Algorithm for Composite Service

Authors: Chunli Xie; Jianguo Ren
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Dynamic selection and dynamic binding and rebinding at runtime are new characters of composite services. The traditional static reliability prediction models are unsuitable to dynamic composite services. A new reliability predicting algorithm for composite services is proposed in this paper. Firstly, a composite service is decomposed into composition unites (executing path, composite module and atomic service) according to their constituents. Consequently, a hierarchical graph of all composite units is constructed. Lastly, a new dynamic reliability prediction algorithm is presented. Comparing with the traditional reliability model, the new dynamic reliability approach is more flexible, which does not recompute reliability for all composite units and only computes the reliability of the effected composite units. In addition, an example to show how to measure the reliability based on our algorithm is designed. The experimental results show our proposed methods can give an accurate estimation of reliability. Furthermore, a more flexible sensitivity analysis is performed to determine which service component has the most significant impact on the improvement of composite service reliability.


---

## Body

## 1. Introduction

With the rapid development and widespread use of web services, more and more businesses are achieved by composite services which can be created by aggregating a number of atomic or composite services (called service components) by following certain composition pattern and rules. Thus, how to ensure the reliability of composite services has become an important problem. In addition, a large amount of function-equivalent services has been in the Internet, which make more services be selected. Users can translate their requirements for services to the constraints of some QoS properties [1]. Then, different users may select different service to realize the same function based on different QoS constraints. There are two methods for web service composition: static composition and dynamic composition. In static web service composition, composition is performed manually; that is, each web service is selected and bound before execution. Static composition is sufficient for constructing applications with well-defined specific requirements that are not likely to change frequently. But, it is not flexible and agile enough when the requirements are changed frequently. Dynamic web service composition can achieve this goal as, in dynamic composition, services components are selected at runtime from a set of service components and when the selected service components failed, the new selected service components will replace them while keeping the running services constantly available to users [2]. Dynamic service composition provides an ability to rapidly adapt to changes that were not envisioned during design time.Dynamic binding and rebinding are the basis for the dynamic composition. There are three kinds of binding: early binding, local binding at runtime, and rebinding at runtime [3–6]. In early binding, the service is selected and bound before execution, which is also called static binding. In local binding, when a composite service is running, one of its service components is bound to a selected service according to some QoS properties before it is invoked. Local binding can help service components to avoid binding to failed services and reduce the failure probability of composite services. During the execution of a composite service, when the QoS of some service components do not satisfy the requirements of the user or the bound services fail, the composite service will pause, and after new services are bound to the service components, the composite service continues to run; the binding in this process is called rebinding at runtime.To address the above problems of dynamic composition, traditional static reliability model to predict the reliability is not applicable to services with dynamic composition. A new dynamic reliability model is presented for the dynamic service composition in this paper. The new model makes the computation simple when the reliability of some service components is changed frequently.The remaining sections of the paper are organized as follows. Section2 describes the related works. Section 3 discusses some concepts about composite units. Section 4 describes the reliability of the composite units. Section 5 presents the dynamic reliability prediction approaches based on the hierarchical graph. Section 6 conducts some experiments to verify our reliability algorithm. Section 7 presents the conclusion and our future works.


## 2. Related Works

The existing reliability predicting models can be divided into two categories: black-box and white-box [7, 8]. The black-box models, such as the Bayesian models, the SRGM (software reliability growth models), and the statistical models, only consider the functionality of software while ignoring its internal structure. The white-box models estimate the reliability of a software system based on its internal structure. The structures are often described by Markov chain [9–19] or Petri net [20, 21]. These white-box models can be further divided into three categories: state-based models, path-based models, and additive models. As these models are often developed for component-based software systems, they are also called component-based reliability models (CBRM). The state-based models which are the common models usually model the system as a discrete-time Markov chain (DTMC), a continuous-time Markov chain (CTMC), or a semi-Markov process Markov chain (SMP). Wang et al. presented a typical state-based model which described four common architecture styles, including batch-sequential, parallel/pipe-filter, call-and-return, and fault-tolerance styles, and proposed a transformation from architecture view to state view to perform reliability analysis [10]. S. Gokhale et al. classified the state-based models from three aspects: the architecture of the application, the failure behavior of components, and the analysis methods. The architectures were CTMC or DTMC and the Markov chain was irreducible or absorbing. The failure behavior was represented by reliability, constant failure rate, or time-dependent failure intensity. The analysis method was composite or hierarchical. In sum, they gave seven kinds of DTMC-based models and CTMC-based models.The emergency of web services makes the software system be dynamic discovery and binding, which make the development and the execution be more complex. Then, web services are more prone to failure than traditional distributed software. It is necessary to develop new methods to predict the reliability of services [17–19]. Tsai et al. extended the components based reliability models to services reliability analysis [20, 21]. The structure of services is also described as Markov chain. Wang et al. proposed a hierarchical reliability model which divided the reliability of services into data reliability, service components reliability, service pool reliability and composite services reliability [22, 23]. Zheng and Lyu proposed a collaborative reliability prediction approach, which employs the past failure data of other similar users to predict the web service reliability for the current user [24, 25]. This method needs large amount of user data; when the number of user is small, it is difficult to classify a user to its similar group. The composition process of web services is actually a workflow process; then a workflow-based model is also a usual method to predict the reliability [26]. Moreover, there are also other approaches to estimate the reliability of composite services from the ports, message delivery, or network transition [27–31]. Web services are different from general software system, as they are dynamic composition. Most of the existing reliability models are based on the service components in the design phase, without considering the dynamic selection and binding. In this paper, we would propose a new dynamic approach to predict the reliability of services.


## 3. Composite Units

Composite services are divided intoatomic service, composite unit, execution path, and compositeservice according to their different constituents. We will discuss the four composite units in detail.


### 3.1. Atomic Service (AS)

An atomic service is the smallest organization unit of web service. In other words, it would be impractical to decompose an atomic service. An atomic service has a fine-grained structure which can be designed, implemented, and tested independently. A composite service is a composite process; in dynamical composition, the service component in composite process is called abstract service. When the service is invoked, the abstract service is bound to the concrete service. There are several concrete services offering the same piece of functionality, which means that several concrete services may match an abstract service in service specification. So, the reliability of atomic service is changed in the execution process.


### 3.2.  Basic Composite Module (BCM)

Service composite module is composed of a set of services according to some operations. The constituted services may be atomic services, composite modules, or composite services. The operations aresequence, choice, loop,andconcurrent. According to the operations, the service composite modules can be divided into four categories, that is,sequence module (SM),choice module (CM),loop module (LP), andconcurrent module (CoM). If all services in a composite module are atomic services, the composite module is called a basic composite module (B
C
M). Let B
C
M
=
{
A
s
s
,
O
P
}, A
s
s is the set of atomic services, and O
P is the operator of atomic services, O
P
∈
{
s
e
q
u
e
n
c
e
,
c
h
o
i
c
e
,
l
o
o
p
,
c
o
n
c
u
r
r
e
n
t
}.


### 3.3. ExecutionPath (Path)

All services invoked sequentially are defined as an execution path when completing a task. LetP
a
t
h
=
{
S
1
,
S
2
,
…
,
S
n
}, S
i
∈
B
C
M, i
=
1,2
,
…
,
n, and the S
i in P
a
t
h is sequential.


### 3.4. Composite Service (CS)

The execution of a composite service is combined by several paths. LetC
S
=
{
〈
P
a
t
h
1
,
P
1
〉
,
〈
P
a
t
h
2
,
P
2
〉
,
…
,
〈
P
a
t
h
n
,
P
n
〉
}, where P
a
t
h
i is the i
th execution path, i
=
1,2
,
3
,
…
,
n, and P
i is the execution probability of P
a
t
h
i. An example of a composite service is shown in Figure 1; the composite service has two execution paths, P
a
t
h
1
,
P
a
t
h
2, C
S
=
{
〈
P
a
t
h
1
,
P
1
〉
,
〈
P
a
t
h
2
,
P
2
〉
}. Services in an execution path of composite services may be atomic services, service module, or composite services; then they have A
S
∈
B
C
M
∈
P
a
t
h
∈
C
S. A composite service includes several paths and the composite modules in a path may be B
C
M or other composite modules which have some B
C
M
s. Any composite service can be finally divided into several execution paths consisting of several B
C
M
s. We will prove the theorem.Figure 1
Execution path graph.Proposition 1.
Any composite service can be finally divided into some execution paths which consist of severalB
C
M
s.Proof.
As a composite service constitutes several execution paths by the probability, suppose that aP
a
t
h
i includes another composite module A which consists of several atomic services and a B
C
M, A
=
{
A
s
a
1
,
A
s
a
2
,
…
,
A
s
a
n
,
B
,
O
P
A
} and B
=
{
A
s
b
1
,
A
s
b
2
,
…
,
A
s
b
n
,
O
P
B
}, where O
P
A
∈
{
s
e
q
u
e
n
c
e
,
l
o
o
p
,
c
h
o
i
c
e
,
c
o
n
c
u
r
r
e
n
t
} and O
P
B
∈
{
s
e
q
u
e
n
c
e
,
l
o
o
p
,
c
h
o
i
c
e
,
c
o
n
c
u
r
r
e
n
t
}. We use O
P
A
=
s
e
q
u
e
n
c
e and O
P
B
=
s
e
q
u
e
n
c
e as an example to illustrate the problem. If we introduce composite module B into A, we will get A
=
{
A
s
a
1
,
A
s
a
2
,
…
,
A
s
a
n
,
A
s
b
1
,
A
s
b
2
,
…
,
A
s
b
n
,
s
e
q
u
e
n
c
e
}. Then, a composite module A can be deeply divided into a
n
+
b
n atomic services and the decomposition does not affect its execution path. If one of the operations is c
h
o
i
c
e, the execution path P
a
t
h
i can be replaced by more execution paths. As O
P
A
,
O
P
B are one of the four operations, the execution path is not affected except when one of the operations is c
h
o
i
c
e. One composite module can be decomposed into one or more B
C
M
s, and the corresponding execution path can be extended into more execution paths. So, a composite service can be finally divided into some execution paths which consist of several B
C
M
s.


### 3.5.  Hierarchical Graph of Composite Units

In this section, we will describe a hierarchical graph to represent the composite unit:composite service, path, basic composite module, andatomic service, while the following section describes how to calculate the graph attributes.Definition 2 (hierarchical graph).
A hierarchical graph is defined by a 2-tuple〈
V
,
E
〉, where 〈
V
,
E
〉 is a DAG (directed acyclic graph). V is a set of nodes in the graph, V
=
{
v
i
}
,
i
=
1
⋯
|
V
|, and E is a set of directed edges in the graph, E
=
{
e
i
}, i
=
1
⋯
|
E
|.Definition 3 (node).
A nodev
∈
V models a composite unit i and is defined by a 2-tuple 〈
N
i
,
R
i
〉, where N
i is the name of composite unit i and R
i is the reliability of composite unit i.Definition 4 (edge).
A directed edgee
∈
E models the constitution of composite units v
i and is defined by the tuple 〈
v
i
,
v
j
,
w
i
,
j
〉, where v
i
,
v
j are nodes, the node v
j is one of the components of node v
i, and w
i
,
j is the weight of edge from node v
i to v
j which describes the constitution of v
i and v
j. If w
i
,
j
<
1, the edge represents the node v
i consisting of v
j according to c
h
o
i
c
e structure, if w
i
,
j
=
1, the edge represents the node v
i consisting of v
j according to s
e
q
u
e
n
c
e or c
o
n
c
u
r
r
e
n
t structure, and if w
i
,
j
>
1, the edge represents the node v
i consisting of v
j according to l
o
o
p structure.As shown in Figure2, the node 〈
C
S
,
R
1
〉 is the composite service, the nodes 〈
P
a
t
h
1
,
R
p
a
t
h
1
〉 and 〈
P
a
t
h
2
,
R
p
a
t
h
2
〉 in level 2 are the execution paths of composite service C
S, the nodes 〈
B
C
M
1
,
R
B
C
M
1
〉, 〈
B
C
M
2
,
R
B
C
M
2
〉, and 〈
B
C
M
3
,
R
B
C
M
3
〉 in level 3 are the B
C
M
s of C
S, the nodes 〈
A
S
1
,
R
A
S
1
〉, 〈
A
S
2
,
R
A
S
2
〉, 〈
A
S
3
,
R
A
S
3
〉, 〈
A
S
4
,
R
A
S
4
〉, and 〈
A
S
5
,
R
A
S
5
〉 in level 4 are atomic services, and the nodes in the last level are the matched concrete services of atomic service A
S
1.Figure 2
Hierarchical graph of composite service.


## 3.1. Atomic Service (AS)

An atomic service is the smallest organization unit of web service. In other words, it would be impractical to decompose an atomic service. An atomic service has a fine-grained structure which can be designed, implemented, and tested independently. A composite service is a composite process; in dynamical composition, the service component in composite process is called abstract service. When the service is invoked, the abstract service is bound to the concrete service. There are several concrete services offering the same piece of functionality, which means that several concrete services may match an abstract service in service specification. So, the reliability of atomic service is changed in the execution process.


## 3.2.  Basic Composite Module (BCM)

Service composite module is composed of a set of services according to some operations. The constituted services may be atomic services, composite modules, or composite services. The operations aresequence, choice, loop,andconcurrent. According to the operations, the service composite modules can be divided into four categories, that is,sequence module (SM),choice module (CM),loop module (LP), andconcurrent module (CoM). If all services in a composite module are atomic services, the composite module is called a basic composite module (B
C
M). Let B
C
M
=
{
A
s
s
,
O
P
}, A
s
s is the set of atomic services, and O
P is the operator of atomic services, O
P
∈
{
s
e
q
u
e
n
c
e
,
c
h
o
i
c
e
,
l
o
o
p
,
c
o
n
c
u
r
r
e
n
t
}.


## 3.3. ExecutionPath (Path)

All services invoked sequentially are defined as an execution path when completing a task. LetP
a
t
h
=
{
S
1
,
S
2
,
…
,
S
n
}, S
i
∈
B
C
M, i
=
1,2
,
…
,
n, and the S
i in P
a
t
h is sequential.


## 3.4. Composite Service (CS)

The execution of a composite service is combined by several paths. LetC
S
=
{
〈
P
a
t
h
1
,
P
1
〉
,
〈
P
a
t
h
2
,
P
2
〉
,
…
,
〈
P
a
t
h
n
,
P
n
〉
}, where P
a
t
h
i is the i
th execution path, i
=
1,2
,
3
,
…
,
n, and P
i is the execution probability of P
a
t
h
i. An example of a composite service is shown in Figure 1; the composite service has two execution paths, P
a
t
h
1
,
P
a
t
h
2, C
S
=
{
〈
P
a
t
h
1
,
P
1
〉
,
〈
P
a
t
h
2
,
P
2
〉
}. Services in an execution path of composite services may be atomic services, service module, or composite services; then they have A
S
∈
B
C
M
∈
P
a
t
h
∈
C
S. A composite service includes several paths and the composite modules in a path may be B
C
M or other composite modules which have some B
C
M
s. Any composite service can be finally divided into several execution paths consisting of several B
C
M
s. We will prove the theorem.Figure 1
Execution path graph.Proposition 1.
Any composite service can be finally divided into some execution paths which consist of severalB
C
M
s.Proof.
As a composite service constitutes several execution paths by the probability, suppose that aP
a
t
h
i includes another composite module A which consists of several atomic services and a B
C
M, A
=
{
A
s
a
1
,
A
s
a
2
,
…
,
A
s
a
n
,
B
,
O
P
A
} and B
=
{
A
s
b
1
,
A
s
b
2
,
…
,
A
s
b
n
,
O
P
B
}, where O
P
A
∈
{
s
e
q
u
e
n
c
e
,
l
o
o
p
,
c
h
o
i
c
e
,
c
o
n
c
u
r
r
e
n
t
} and O
P
B
∈
{
s
e
q
u
e
n
c
e
,
l
o
o
p
,
c
h
o
i
c
e
,
c
o
n
c
u
r
r
e
n
t
}. We use O
P
A
=
s
e
q
u
e
n
c
e and O
P
B
=
s
e
q
u
e
n
c
e as an example to illustrate the problem. If we introduce composite module B into A, we will get A
=
{
A
s
a
1
,
A
s
a
2
,
…
,
A
s
a
n
,
A
s
b
1
,
A
s
b
2
,
…
,
A
s
b
n
,
s
e
q
u
e
n
c
e
}. Then, a composite module A can be deeply divided into a
n
+
b
n atomic services and the decomposition does not affect its execution path. If one of the operations is c
h
o
i
c
e, the execution path P
a
t
h
i can be replaced by more execution paths. As O
P
A
,
O
P
B are one of the four operations, the execution path is not affected except when one of the operations is c
h
o
i
c
e. One composite module can be decomposed into one or more B
C
M
s, and the corresponding execution path can be extended into more execution paths. So, a composite service can be finally divided into some execution paths which consist of several B
C
M
s.


## 3.5.  Hierarchical Graph of Composite Units

In this section, we will describe a hierarchical graph to represent the composite unit:composite service, path, basic composite module, andatomic service, while the following section describes how to calculate the graph attributes.Definition 2 (hierarchical graph).
A hierarchical graph is defined by a 2-tuple〈
V
,
E
〉, where 〈
V
,
E
〉 is a DAG (directed acyclic graph). V is a set of nodes in the graph, V
=
{
v
i
}
,
i
=
1
⋯
|
V
|, and E is a set of directed edges in the graph, E
=
{
e
i
}, i
=
1
⋯
|
E
|.Definition 3 (node).
A nodev
∈
V models a composite unit i and is defined by a 2-tuple 〈
N
i
,
R
i
〉, where N
i is the name of composite unit i and R
i is the reliability of composite unit i.Definition 4 (edge).
A directed edgee
∈
E models the constitution of composite units v
i and is defined by the tuple 〈
v
i
,
v
j
,
w
i
,
j
〉, where v
i
,
v
j are nodes, the node v
j is one of the components of node v
i, and w
i
,
j is the weight of edge from node v
i to v
j which describes the constitution of v
i and v
j. If w
i
,
j
<
1, the edge represents the node v
i consisting of v
j according to c
h
o
i
c
e structure, if w
i
,
j
=
1, the edge represents the node v
i consisting of v
j according to s
e
q
u
e
n
c
e or c
o
n
c
u
r
r
e
n
t structure, and if w
i
,
j
>
1, the edge represents the node v
i consisting of v
j according to l
o
o
p structure.As shown in Figure2, the node 〈
C
S
,
R
1
〉 is the composite service, the nodes 〈
P
a
t
h
1
,
R
p
a
t
h
1
〉 and 〈
P
a
t
h
2
,
R
p
a
t
h
2
〉 in level 2 are the execution paths of composite service C
S, the nodes 〈
B
C
M
1
,
R
B
C
M
1
〉, 〈
B
C
M
2
,
R
B
C
M
2
〉, and 〈
B
C
M
3
,
R
B
C
M
3
〉 in level 3 are the B
C
M
s of C
S, the nodes 〈
A
S
1
,
R
A
S
1
〉, 〈
A
S
2
,
R
A
S
2
〉, 〈
A
S
3
,
R
A
S
3
〉, 〈
A
S
4
,
R
A
S
4
〉, and 〈
A
S
5
,
R
A
S
5
〉 in level 4 are atomic services, and the nodes in the last level are the matched concrete services of atomic service A
S
1.Figure 2
Hierarchical graph of composite service.


## 4. Reliability of Composite Units

### 4.1. Reliability of Atomic Services

An abstract service may have several concrete services to be matched; then, different user may select different concrete service to be bound for the same abstract service as they have different QoS requirement [24]. For example, there are an abstract service A
S and three matched concrete services A
S
1, A
S
2, and A
S
3. The reliability of the three concrete services is {
0.98,0.9,0
.
75
}, and one of the QoS {
h
i
g
h
,
g
e
n
e
r
a
l
,
l
o
w
}. The reliability and price of A
S
1 are the highest, and A
S
3 is the lowest. If a user only cares about the reliability and has no claim for price, he may select A
S
1 to be invoked. Other users may have different choice considering the price. The binding information can be recorded by monitor mechanism, and the binding probability can be computed from this information [27]. Here, we assume that the binding probability is known. As shown in Figure 3, the reliability of atomic service v
i can be computed by the following:
(1)
R
A
S
=
R
i
=
∑
j
=
1
n
‍
R
j
*
w
i
,
j
,Hierarchical graph of composite module.
(a)
Sequence/concurrent
(b)
Choice
(c)
LoopwhereR
i is the reliability of an abstract atomic service node V
i, R
j is the reliability of v
j
,
j
=
1
,
…
,
n, which is a concrete atomic service to be bound to v
i, and w
i
,
j is the binding probability of node v
i to node v
j. After the binding changed, the reliability of atomic service A
S must be recomputed according to the above formula.


### 4.2.  Reliability of Basic Composite Module

Sequence module (S
M), choice module (C
o
M), loop module (L
M), and concurrent module (C
o
M) are four kinds of composite modules. Next, we will discuss their reliability in a dynamic environment.


#### 4.2.1. Sequence Module/Concurrent Module

As shown in Figure3(a), node v
i is SM or CM, nodes v
1
,
…
,
v
n are the atomic services which compose the S
M or C
o
M, and the weight of edge from node v
i to v
j, j
=
1
,
…
,
n, is 1. The reliability of S
M or C
o
M is
(2)
R
S
M
=
R
C
o
M
=
R
i
=
∏
j
=
1
n
‍
R
j
.In the equation, if the binding probability of an atomic servicev
k is changed, then the reliability of v
i will be changed, and the reliability of S
M will be changed. Let Δ
R
k be the changed value of v
k; then the new value of node v
i can be represented by
(3)
R
i
′
=
∏
j
=
1
,
j
≠
k
n
‍
R
j
(
R
k
+
Δ
R
k
)
=
R
i
+
Δ
R
k
∏
j
=
1
,
j
≠
k
n
‍
R
j
=
(
1
+
Δ
R
k
R
k
)
R
i
.
From the equation, we can see that when the binding of a service has been changed, it does not need to recalculate the reliability of the entire services. As long as the changed value is calculated, the whole reliability can be known.


#### 4.2.2.  Choice Module

As shown in Figure3(b), the weight of edge from node v
i to node v
j is less than 1; the composite module is C
M. The reliability of C
M can be computed by the following expression:
(4)
R
C
M
=
R
i
=
∑
j
=
1
n
‍
R
j
w
i
,
j
.
If a binding probability of an atomic service (e.g., v
k) is changed, the reliability of the atomic service must be recomputed, R
k
′
=
R
k
+
Δ
R
k, where Δ
R
k is the changed value of node v
k. Thus, the new reliability of C
M can be expressed by the following:
(5)
R
C
M
′
=
R
i
′
=
∑
j
=
1
,
j
≠
k
n
‍
(
R
j
w
i
,
j
)
+
Δ
R
k
w
i
,
k
=
R
i
+
Δ
R
k
w
i
,
k
and Δ
R
k
=
Δ
R
k
w
i
,
k.


#### 4.2.3.  Loop Module

As shown in Figure3(c), the weight of edge from node v
i to node v
j is larger than 1, the composite module is L
M, and the weight of edge is the number of times. The reliability of L
M can be computed by the following expression:
(6)
R
L
M
=
R
i
=
R
j
w
i
,
j
.
If the binding probability of v
j is changed, Δ
R
j is the changed value of node v
j. The new reliability of L
M can be expressed by the following:
(7)
R
i
′
=
(
R
i
+
Δ
R
j
)
w
i
,
j
=
R
i
(
1
+
Δ
R
j
R
i
)
w
i
,
j
.
From (7), we also can see that when the reliability of an abstract service in L
M is changed there is no need to recalculate all reliabilities of services in L
M to get the reliability of the entire service. It is easy to get the reliability of the entire service as long as the changed value has been got. In a word, the incremental reliability of B
C
M is
(8)
Δ
R
i
=
{
Δ
R
k
R
k
R
i
s
e
q
u
e
n
c
e
/
c
o
n
c
u
r
r
e
n
t
Δ
R
k
w
i
,
k
c
h
o
i
c
e
[
(
1
+
Δ
R
k
R
k
)
w
i
,
k
-
1
]
R
i
l
o
o
p
.


### 4.3. Reliability of Path

As shown in Figure2, an execution path is a sequence structure of all its B
C
M
s in the path. The weight of edge from execution paths to its B
C
M
s is 1. So, the reliability of execution path is the same as S
M:
(9)
R
P
a
t
h
=
R
i
=
∏
j
=
1
n
‍
R
j
,
R
P
a
t
h
′
=
R
i
+
Δ
R
i
,whereΔ
R
P
a
t
h
=
Δ
R
i
=
(
Δ
R
k
/
R
k
)
R
i.


### 4.4. Reliability of Composite Service

The execution of a composite service can be divided into several paths, and each path is executed according to a probability. Assume that nodev
0 is a composite service C
o
S in Figure 2 that has several execution paths, P
a
t
h
1
,
…
,
P
a
t
h
n; their execution probabilities are P
1
,
…
,
P
n and their nodes are v
1
,
v
2
,
…
,
v
n. Then, the reliability of composite service C
S can be calculated by
(10)
R
C
S
=
R
0
=
∑
i
=
1
n
‍
R
i
w
0
,
i
.If the reliability ofP
a
t
h
k has been changed, and Δ
R
k is the changed value of P
a
t
h
k, the new reliability of composite service can be recalculated similar to the C
M:
(11)
R
C
S
′
=
R
0
′
=
R
0
+
Δ
R
0
,whereΔ
R
C
S
=
Δ
R
0
=
Δ
R
k
w
0
,
k and D
e
l
t
a  R
0 is the changed value of composite service.


## 4.1. Reliability of Atomic Services

An abstract service may have several concrete services to be matched; then, different user may select different concrete service to be bound for the same abstract service as they have different QoS requirement [24]. For example, there are an abstract service A
S and three matched concrete services A
S
1, A
S
2, and A
S
3. The reliability of the three concrete services is {
0.98,0.9,0
.
75
}, and one of the QoS {
h
i
g
h
,
g
e
n
e
r
a
l
,
l
o
w
}. The reliability and price of A
S
1 are the highest, and A
S
3 is the lowest. If a user only cares about the reliability and has no claim for price, he may select A
S
1 to be invoked. Other users may have different choice considering the price. The binding information can be recorded by monitor mechanism, and the binding probability can be computed from this information [27]. Here, we assume that the binding probability is known. As shown in Figure 3, the reliability of atomic service v
i can be computed by the following:
(1)
R
A
S
=
R
i
=
∑
j
=
1
n
‍
R
j
*
w
i
,
j
,Hierarchical graph of composite module.
(a)
Sequence/concurrent
(b)
Choice
(c)
LoopwhereR
i is the reliability of an abstract atomic service node V
i, R
j is the reliability of v
j
,
j
=
1
,
…
,
n, which is a concrete atomic service to be bound to v
i, and w
i
,
j is the binding probability of node v
i to node v
j. After the binding changed, the reliability of atomic service A
S must be recomputed according to the above formula.


## 4.2.  Reliability of Basic Composite Module

Sequence module (S
M), choice module (C
o
M), loop module (L
M), and concurrent module (C
o
M) are four kinds of composite modules. Next, we will discuss their reliability in a dynamic environment.


### 4.2.1. Sequence Module/Concurrent Module

As shown in Figure3(a), node v
i is SM or CM, nodes v
1
,
…
,
v
n are the atomic services which compose the S
M or C
o
M, and the weight of edge from node v
i to v
j, j
=
1
,
…
,
n, is 1. The reliability of S
M or C
o
M is
(2)
R
S
M
=
R
C
o
M
=
R
i
=
∏
j
=
1
n
‍
R
j
.In the equation, if the binding probability of an atomic servicev
k is changed, then the reliability of v
i will be changed, and the reliability of S
M will be changed. Let Δ
R
k be the changed value of v
k; then the new value of node v
i can be represented by
(3)
R
i
′
=
∏
j
=
1
,
j
≠
k
n
‍
R
j
(
R
k
+
Δ
R
k
)
=
R
i
+
Δ
R
k
∏
j
=
1
,
j
≠
k
n
‍
R
j
=
(
1
+
Δ
R
k
R
k
)
R
i
.
From the equation, we can see that when the binding of a service has been changed, it does not need to recalculate the reliability of the entire services. As long as the changed value is calculated, the whole reliability can be known.


### 4.2.2.  Choice Module

As shown in Figure3(b), the weight of edge from node v
i to node v
j is less than 1; the composite module is C
M. The reliability of C
M can be computed by the following expression:
(4)
R
C
M
=
R
i
=
∑
j
=
1
n
‍
R
j
w
i
,
j
.
If a binding probability of an atomic service (e.g., v
k) is changed, the reliability of the atomic service must be recomputed, R
k
′
=
R
k
+
Δ
R
k, where Δ
R
k is the changed value of node v
k. Thus, the new reliability of C
M can be expressed by the following:
(5)
R
C
M
′
=
R
i
′
=
∑
j
=
1
,
j
≠
k
n
‍
(
R
j
w
i
,
j
)
+
Δ
R
k
w
i
,
k
=
R
i
+
Δ
R
k
w
i
,
k
and Δ
R
k
=
Δ
R
k
w
i
,
k.


### 4.2.3.  Loop Module

As shown in Figure3(c), the weight of edge from node v
i to node v
j is larger than 1, the composite module is L
M, and the weight of edge is the number of times. The reliability of L
M can be computed by the following expression:
(6)
R
L
M
=
R
i
=
R
j
w
i
,
j
.
If the binding probability of v
j is changed, Δ
R
j is the changed value of node v
j. The new reliability of L
M can be expressed by the following:
(7)
R
i
′
=
(
R
i
+
Δ
R
j
)
w
i
,
j
=
R
i
(
1
+
Δ
R
j
R
i
)
w
i
,
j
.
From (7), we also can see that when the reliability of an abstract service in L
M is changed there is no need to recalculate all reliabilities of services in L
M to get the reliability of the entire service. It is easy to get the reliability of the entire service as long as the changed value has been got. In a word, the incremental reliability of B
C
M is
(8)
Δ
R
i
=
{
Δ
R
k
R
k
R
i
s
e
q
u
e
n
c
e
/
c
o
n
c
u
r
r
e
n
t
Δ
R
k
w
i
,
k
c
h
o
i
c
e
[
(
1
+
Δ
R
k
R
k
)
w
i
,
k
-
1
]
R
i
l
o
o
p
.


## 4.2.1. Sequence Module/Concurrent Module

As shown in Figure3(a), node v
i is SM or CM, nodes v
1
,
…
,
v
n are the atomic services which compose the S
M or C
o
M, and the weight of edge from node v
i to v
j, j
=
1
,
…
,
n, is 1. The reliability of S
M or C
o
M is
(2)
R
S
M
=
R
C
o
M
=
R
i
=
∏
j
=
1
n
‍
R
j
.In the equation, if the binding probability of an atomic servicev
k is changed, then the reliability of v
i will be changed, and the reliability of S
M will be changed. Let Δ
R
k be the changed value of v
k; then the new value of node v
i can be represented by
(3)
R
i
′
=
∏
j
=
1
,
j
≠
k
n
‍
R
j
(
R
k
+
Δ
R
k
)
=
R
i
+
Δ
R
k
∏
j
=
1
,
j
≠
k
n
‍
R
j
=
(
1
+
Δ
R
k
R
k
)
R
i
.
From the equation, we can see that when the binding of a service has been changed, it does not need to recalculate the reliability of the entire services. As long as the changed value is calculated, the whole reliability can be known.


## 4.2.2.  Choice Module

As shown in Figure3(b), the weight of edge from node v
i to node v
j is less than 1; the composite module is C
M. The reliability of C
M can be computed by the following expression:
(4)
R
C
M
=
R
i
=
∑
j
=
1
n
‍
R
j
w
i
,
j
.
If a binding probability of an atomic service (e.g., v
k) is changed, the reliability of the atomic service must be recomputed, R
k
′
=
R
k
+
Δ
R
k, where Δ
R
k is the changed value of node v
k. Thus, the new reliability of C
M can be expressed by the following:
(5)
R
C
M
′
=
R
i
′
=
∑
j
=
1
,
j
≠
k
n
‍
(
R
j
w
i
,
j
)
+
Δ
R
k
w
i
,
k
=
R
i
+
Δ
R
k
w
i
,
k
and Δ
R
k
=
Δ
R
k
w
i
,
k.


## 4.2.3.  Loop Module

As shown in Figure3(c), the weight of edge from node v
i to node v
j is larger than 1, the composite module is L
M, and the weight of edge is the number of times. The reliability of L
M can be computed by the following expression:
(6)
R
L
M
=
R
i
=
R
j
w
i
,
j
.
If the binding probability of v
j is changed, Δ
R
j is the changed value of node v
j. The new reliability of L
M can be expressed by the following:
(7)
R
i
′
=
(
R
i
+
Δ
R
j
)
w
i
,
j
=
R
i
(
1
+
Δ
R
j
R
i
)
w
i
,
j
.
From (7), we also can see that when the reliability of an abstract service in L
M is changed there is no need to recalculate all reliabilities of services in L
M to get the reliability of the entire service. It is easy to get the reliability of the entire service as long as the changed value has been got. In a word, the incremental reliability of B
C
M is
(8)
Δ
R
i
=
{
Δ
R
k
R
k
R
i
s
e
q
u
e
n
c
e
/
c
o
n
c
u
r
r
e
n
t
Δ
R
k
w
i
,
k
c
h
o
i
c
e
[
(
1
+
Δ
R
k
R
k
)
w
i
,
k
-
1
]
R
i
l
o
o
p
.


## 4.3. Reliability of Path

As shown in Figure2, an execution path is a sequence structure of all its B
C
M
s in the path. The weight of edge from execution paths to its B
C
M
s is 1. So, the reliability of execution path is the same as S
M:
(9)
R
P
a
t
h
=
R
i
=
∏
j
=
1
n
‍
R
j
,
R
P
a
t
h
′
=
R
i
+
Δ
R
i
,whereΔ
R
P
a
t
h
=
Δ
R
i
=
(
Δ
R
k
/
R
k
)
R
i.


## 4.4. Reliability of Composite Service

The execution of a composite service can be divided into several paths, and each path is executed according to a probability. Assume that nodev
0 is a composite service C
o
S in Figure 2 that has several execution paths, P
a
t
h
1
,
…
,
P
a
t
h
n; their execution probabilities are P
1
,
…
,
P
n and their nodes are v
1
,
v
2
,
…
,
v
n. Then, the reliability of composite service C
S can be calculated by
(10)
R
C
S
=
R
0
=
∑
i
=
1
n
‍
R
i
w
0
,
i
.If the reliability ofP
a
t
h
k has been changed, and Δ
R
k is the changed value of P
a
t
h
k, the new reliability of composite service can be recalculated similar to the C
M:
(11)
R
C
S
′
=
R
0
′
=
R
0
+
Δ
R
0
,whereΔ
R
C
S
=
Δ
R
0
=
Δ
R
k
w
0
,
k and D
e
l
t
a  R
0 is the changed value of composite service.


## 5. Reliability Prediction of Composite Service

Composite services can be decomposed into three layers, that is,path layer,BCM layer, andatomic service layer. Thus, the reliability of composite services can be calculated by the reliability ofpath, BCM, andatomic service. In this section, we will discuss how to compute the reliability of composite services.


### 5.1.  Reliability Algorithm for Composite Service

The nodes in different layer in Figure2 represent different composite units. We assume that the reliability of atomic services is known, and the reliability of other nodes can be derived from the reliability of their next layer nodes. We can get all the reliabilities of nodes from bottom to up. The algorithm C
a
l
R
e
l
(
G
,
v
) calculates the reliability of all nodes in the hierarchical graph of the composite service C
S (Algorithm 1). The parameter G is the hierarchical graph and v
i is a node, 〈
v
i
,
v
j
〉
∈
E, whose initial value is
(12)
R
i
=
{
0
w
i
,
j
<
1
1
w
i
,
j
≥
1
.Algorithm 1:Double C
a
l
R
e
l (graph G, vertex v
i).
(1)  {
(2)  doubleR
=
R
i;
(3)  for(
v
j
=
v
i
.
f
i
r
s
t
n
e
i
g
h
b
o
r
(
);
(4)v
j != NULL
;
v
j
=
v
i
.
n
e
x
t
n
e
i
g
h
b
o
r
(
)
)
(5)  if(
v
i
s
i
t
e
d
[
v
j
]
=
=
f
a
l
s
e
);
(6)  {
(7)  if(
w
i
,
j
<
1
)
(8)R
=
R
+
C
a
l
R
e
l
(
G
,
v
j
)
*
w
i
,
j;
(9)  else if(
w
i
,
j
=
1
)
(10)R
=
R
*
C
a
l
R
e
l
(
G
,
v
j
)
*
w
i
,
j;
(11) elseR
=
R
*
(
C
a
l
R
e
l
(
G
,
v
j
)
)
w
i
,
j;;
(12) }
(13)return
R;
(14) }When the algorithm is invoked, parameterv
i is the composite service node v
0. The calculation process is the traverse process and all reliabilities of nodes are calculated in traverse of graph. Then the time complexity is the same as the traverse process, which is O
(
n
+
e
), n is the number of nodes, and e is the number of edges.


### 5.2. Dynamic Reliability Algorithm for Composite Services

If the reliability of an atomic service is changed, the composite service will be affected. In this section, we will discuss how to perform our dynamic reliability model to evaluate the reliability of composite services. Not all composite units are affected by the atomic service; we only recalculate the reliability of the influenced nodes. For example, in Figure4, the nodes with bold line are the affected nodes. The first step is to find all affected nodes, for example, C
S, P
a
t
h
1, P
a
t
h
2, P
a
t
h
3, P
a
t
h
4, B
C
M
1, and A
S
1 in Figure 4. Then, all the affected nodes are extracted to a subgraph G
′ in Figure 5. We present an algorithm C
a
l
D
e
l
t
a
R
e
l to calculate the reliability of the affected nodes (Algorithm 2). The parameter G
′ is the subgraph and v
i is a node in subgraph G
′. Variable R
i is the reliability of node v
i. The returned result (Δ
R
C
S) is the incremental reliability of a composite service and R
C
S
′
=
Δ
R
C
S
+
R
C
S.Algorithm 2:Double C
a
l
D
e
l
t
a
R
e
l (graph G
′, vertex v
i).
(1)  {
(2)  doubleΔ
R
=
0;
(3)  for(
v
j
=
v
i
.
f
i
r
s
t
n
e
i
g
h
b
o
r
(
);
(4)v
j != N
U
L
L
;
v
j
=
v
i
.
n
e
x
t
n
e
i
g
h
b
o
r
(
)
)
(5)  if(
!
v
i
s
i
t
e
d
[
v
j
]
);
(6){
Δ
R
j
=
C
a
l
D
e
l
t
a
R
e
l
(
G
′
,
v
j
)
(7)  if(
w
i
,
j
<
1
)
(8)Δ
R
=
Δ
v
j
w
i
,
j;
(9)  else if(
w
i
,
j
=
1
)
(10)Δ
R
=
Δ
v
j
/
R
j
R
i;
(11) else
(12)Δ
R
=
[
(
1
+
Δ
v
j
/
R
j
)
w
i
,
j
-
1
]
R
i;
(13) }
(14)return
Δ
R;
(15) }Figure 4
Hierarchical graph of composite service.Figure 5
Subgraph of composite service.


## 5.1.  Reliability Algorithm for Composite Service

The nodes in different layer in Figure2 represent different composite units. We assume that the reliability of atomic services is known, and the reliability of other nodes can be derived from the reliability of their next layer nodes. We can get all the reliabilities of nodes from bottom to up. The algorithm C
a
l
R
e
l
(
G
,
v
) calculates the reliability of all nodes in the hierarchical graph of the composite service C
S (Algorithm 1). The parameter G is the hierarchical graph and v
i is a node, 〈
v
i
,
v
j
〉
∈
E, whose initial value is
(12)
R
i
=
{
0
w
i
,
j
<
1
1
w
i
,
j
≥
1
.Algorithm 1:Double C
a
l
R
e
l (graph G, vertex v
i).
(1)  {
(2)  doubleR
=
R
i;
(3)  for(
v
j
=
v
i
.
f
i
r
s
t
n
e
i
g
h
b
o
r
(
);
(4)v
j != NULL
;
v
j
=
v
i
.
n
e
x
t
n
e
i
g
h
b
o
r
(
)
)
(5)  if(
v
i
s
i
t
e
d
[
v
j
]
=
=
f
a
l
s
e
);
(6)  {
(7)  if(
w
i
,
j
<
1
)
(8)R
=
R
+
C
a
l
R
e
l
(
G
,
v
j
)
*
w
i
,
j;
(9)  else if(
w
i
,
j
=
1
)
(10)R
=
R
*
C
a
l
R
e
l
(
G
,
v
j
)
*
w
i
,
j;
(11) elseR
=
R
*
(
C
a
l
R
e
l
(
G
,
v
j
)
)
w
i
,
j;;
(12) }
(13)return
R;
(14) }When the algorithm is invoked, parameterv
i is the composite service node v
0. The calculation process is the traverse process and all reliabilities of nodes are calculated in traverse of graph. Then the time complexity is the same as the traverse process, which is O
(
n
+
e
), n is the number of nodes, and e is the number of edges.


## 5.2. Dynamic Reliability Algorithm for Composite Services

If the reliability of an atomic service is changed, the composite service will be affected. In this section, we will discuss how to perform our dynamic reliability model to evaluate the reliability of composite services. Not all composite units are affected by the atomic service; we only recalculate the reliability of the influenced nodes. For example, in Figure4, the nodes with bold line are the affected nodes. The first step is to find all affected nodes, for example, C
S, P
a
t
h
1, P
a
t
h
2, P
a
t
h
3, P
a
t
h
4, B
C
M
1, and A
S
1 in Figure 4. Then, all the affected nodes are extracted to a subgraph G
′ in Figure 5. We present an algorithm C
a
l
D
e
l
t
a
R
e
l to calculate the reliability of the affected nodes (Algorithm 2). The parameter G
′ is the subgraph and v
i is a node in subgraph G
′. Variable R
i is the reliability of node v
i. The returned result (Δ
R
C
S) is the incremental reliability of a composite service and R
C
S
′
=
Δ
R
C
S
+
R
C
S.Algorithm 2:Double C
a
l
D
e
l
t
a
R
e
l (graph G
′, vertex v
i).
(1)  {
(2)  doubleΔ
R
=
0;
(3)  for(
v
j
=
v
i
.
f
i
r
s
t
n
e
i
g
h
b
o
r
(
);
(4)v
j != N
U
L
L
;
v
j
=
v
i
.
n
e
x
t
n
e
i
g
h
b
o
r
(
)
)
(5)  if(
!
v
i
s
i
t
e
d
[
v
j
]
);
(6){
Δ
R
j
=
C
a
l
D
e
l
t
a
R
e
l
(
G
′
,
v
j
)
(7)  if(
w
i
,
j
<
1
)
(8)Δ
R
=
Δ
v
j
w
i
,
j;
(9)  else if(
w
i
,
j
=
1
)
(10)Δ
R
=
Δ
v
j
/
R
j
R
i;
(11) else
(12)Δ
R
=
[
(
1
+
Δ
v
j
/
R
j
)
w
i
,
j
-
1
]
R
i;
(13) }
(14)return
Δ
R;
(15) }Figure 4
Hierarchical graph of composite service.Figure 5
Subgraph of composite service.


## 6. Case Study

### 6.1. Experimental Setup

We demonstrate the reliability prediction model with a typical example of a service for travel. In this example, the composite consists of 11 atomic services, and we assume that their reliability is known. As shown in Figure6 the composite service can be divided into 4 execution paths and 7 basic composite modules. Its hierarchical graph is Figure 7.Figure 6
Travel service.Figure 7
Hierarchical graph of travel service.


### 6.2. Comparison of Prediction Accuracy

The prediction reliability of the composite units in travel service according to formula (2) to (10) is shown in Table 1.Table 1
Reliability of composite units.
Composite unit
R
A
S
1
0.9
A
S
2
0.9
A
S
3
0.9
A
S
4
0.85
A
S
5
0.85
A
S
6
0.9
A
S
7
0.9
A
S
8
0.85
A
S
9
0.9
A
S
10
0.85
A
S
11
0.95
B
C
M
1
0.5267
B
C
M
2
0.9
B
C
M
3
0.9
B
C
M
4
0.85
B
C
M
5
0.9
B
C
M
6
0.85
B
C
M
7
0.95
p
a
t
h
1
0.4029
p
a
t
h
2
0.4266
p
a
t
h
3
0.4029
p
a
t
h
4
0.4503
C
S
0.422To study our method performance, we compare our prediction approach with the user-object reliability model (UORM). As shown in Figure8, success and failure states are added to the state diagram of UORM, the transition matrix is P, and the reliability is
(13)
R
UORM
=
R
END
(
I
-
Q
)
1
,
n
-
1
=
0.422
.
From Table 1, we can see that the result of our approach is the same as that of UORM.Figure 8
State diagram of composite service.


### 6.3.  Dynamic Reliability Prediction

If the reliability of atomic serviceA
S
3 is changed, the affected composite units are B
C
M
1, P
a
t
h
1, P
a
t
h
2, P
a
t
h
3, and P
a
t
h
4. According to (11), we have
(14)
Δ
R
C
S
=
∑
i
=
1
4
‍
(
Δ
R
P
a
t
h
i
w
0
,
i
)
,
Δ
R
P
a
t
h
i
=
Δ
R
B
C
M
1
R
B
C
M
1
R
P
a
t
h
i
,
Δ
R
B
C
M
1
=
Δ
R
A
S
3
R
A
S
3
R
B
C
M
1
.
If Δ
R
A
S
3
=
0.02, the new reliability of composite service v
0 is R
C
S
′
=
R
C
S
+
Δ
R
C
S
=
0.41298. The computing process is very simple, but, according to UORM, the transition matrix P
′ must be rebuilt. The new reliability R
UORM
′
=
R
END
(
I
-
Q
)
′
1
,
n
-
1
=
0.41298. From the results of two methods, we can see that our dynamic approach is simpler than UORM, especially when the atomic services are not fixed; then our approach is more applicable to dynamic web services.


### 6.4. Sensitivity Analysis

Sensitivity analysis helps to understand the impact of the reliability of service components with respect to the system or composite service reliability [28]. The sensitivity of composite service reliability based on our approach with respect to a given atomic service A
S
i can be defined as
(15)
C
i
=
Δ
R
C
S
Δ
R
A
S
i
,
P
=
[
Q
D
0
I
]
=


[
0
0.158
0.369
0
0
0
0
0
0
0.474
0
0
0
0.54
0.36
0
0
0
0
0.1
0
0
0
0
0
0.45
0.45
0
0
0.1
0
0
0
0
0
0
0
0.85
0
0.15
0
0
0
0
0
0
0
0.9
0
0.1
0
0
0
0
0
0
0
0.85
0
0.15
0
0
0
0
0
0
0
0.95
0
0.05
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
]
,
P
′
=
[
Q
′
D
′
0
I
]
=


[
0
0.154
0.360
0
0
0
0
0
0
0.474
0
0
0
0.54
0.36
0
0
0
0
0.1
0
0
0
0
0
0.45
0.45
0
0
0.1
0
0
0
0
0
0
0
0.85
0
0.15
0
0
0
0
0
0
0
0.9
0
0.1
0
0
0
0
0
0
0
0.85
0
0.15
0
0
0
0
0
0
0
0.95
0
0.05
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
]
.
The higher sensitivity indicates the greater impact on the reliability of composite service. The results of sensitivity analysis are shown in Table 2. From Table 2, we can see that sensitivity of atomic services A
S
1, A
S
2, A
S
3, A
S
4, and A
S
5 is the same. The atomic service A
S
9 has the lowest sensitivity among all abstract services, because the atomic service A
S
9 in the execution path P
a
t
h
2 and the execution probability of P
a
t
h
2 is the smallest. We will try to improve the reliability of some critical atomic services to improve the reliability of the composite service.Table 2
Sensitivity results.
A
S
C
i
A
S
1
0.7351
A
S
2
0.7351
A
S
3
0.7351
A
S
4
0.7351
A
S
5
0.7351
A
S
6
0.2205
A
S
7
0.5146
A
S
8
0.1323
A
S
9
0.0882
A
S
10
0.2537
A
S
11
0.2537


## 6.1. Experimental Setup

We demonstrate the reliability prediction model with a typical example of a service for travel. In this example, the composite consists of 11 atomic services, and we assume that their reliability is known. As shown in Figure6 the composite service can be divided into 4 execution paths and 7 basic composite modules. Its hierarchical graph is Figure 7.Figure 6
Travel service.Figure 7
Hierarchical graph of travel service.


## 6.2. Comparison of Prediction Accuracy

The prediction reliability of the composite units in travel service according to formula (2) to (10) is shown in Table 1.Table 1
Reliability of composite units.
Composite unit
R
A
S
1
0.9
A
S
2
0.9
A
S
3
0.9
A
S
4
0.85
A
S
5
0.85
A
S
6
0.9
A
S
7
0.9
A
S
8
0.85
A
S
9
0.9
A
S
10
0.85
A
S
11
0.95
B
C
M
1
0.5267
B
C
M
2
0.9
B
C
M
3
0.9
B
C
M
4
0.85
B
C
M
5
0.9
B
C
M
6
0.85
B
C
M
7
0.95
p
a
t
h
1
0.4029
p
a
t
h
2
0.4266
p
a
t
h
3
0.4029
p
a
t
h
4
0.4503
C
S
0.422To study our method performance, we compare our prediction approach with the user-object reliability model (UORM). As shown in Figure8, success and failure states are added to the state diagram of UORM, the transition matrix is P, and the reliability is
(13)
R
UORM
=
R
END
(
I
-
Q
)
1
,
n
-
1
=
0.422
.
From Table 1, we can see that the result of our approach is the same as that of UORM.Figure 8
State diagram of composite service.


## 6.3.  Dynamic Reliability Prediction

If the reliability of atomic serviceA
S
3 is changed, the affected composite units are B
C
M
1, P
a
t
h
1, P
a
t
h
2, P
a
t
h
3, and P
a
t
h
4. According to (11), we have
(14)
Δ
R
C
S
=
∑
i
=
1
4
‍
(
Δ
R
P
a
t
h
i
w
0
,
i
)
,
Δ
R
P
a
t
h
i
=
Δ
R
B
C
M
1
R
B
C
M
1
R
P
a
t
h
i
,
Δ
R
B
C
M
1
=
Δ
R
A
S
3
R
A
S
3
R
B
C
M
1
.
If Δ
R
A
S
3
=
0.02, the new reliability of composite service v
0 is R
C
S
′
=
R
C
S
+
Δ
R
C
S
=
0.41298. The computing process is very simple, but, according to UORM, the transition matrix P
′ must be rebuilt. The new reliability R
UORM
′
=
R
END
(
I
-
Q
)
′
1
,
n
-
1
=
0.41298. From the results of two methods, we can see that our dynamic approach is simpler than UORM, especially when the atomic services are not fixed; then our approach is more applicable to dynamic web services.


## 6.4. Sensitivity Analysis

Sensitivity analysis helps to understand the impact of the reliability of service components with respect to the system or composite service reliability [28]. The sensitivity of composite service reliability based on our approach with respect to a given atomic service A
S
i can be defined as
(15)
C
i
=
Δ
R
C
S
Δ
R
A
S
i
,
P
=
[
Q
D
0
I
]
=


[
0
0.158
0.369
0
0
0
0
0
0
0.474
0
0
0
0.54
0.36
0
0
0
0
0.1
0
0
0
0
0
0.45
0.45
0
0
0.1
0
0
0
0
0
0
0
0.85
0
0.15
0
0
0
0
0
0
0
0.9
0
0.1
0
0
0
0
0
0
0
0.85
0
0.15
0
0
0
0
0
0
0
0.95
0
0.05
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
]
,
P
′
=
[
Q
′
D
′
0
I
]
=


[
0
0.154
0.360
0
0
0
0
0
0
0.474
0
0
0
0.54
0.36
0
0
0
0
0.1
0
0
0
0
0
0.45
0.45
0
0
0.1
0
0
0
0
0
0
0
0.85
0
0.15
0
0
0
0
0
0
0
0.9
0
0.1
0
0
0
0
0
0
0
0.85
0
0.15
0
0
0
0
0
0
0
0.95
0
0.05
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
]
.
The higher sensitivity indicates the greater impact on the reliability of composite service. The results of sensitivity analysis are shown in Table 2. From Table 2, we can see that sensitivity of atomic services A
S
1, A
S
2, A
S
3, A
S
4, and A
S
5 is the same. The atomic service A
S
9 has the lowest sensitivity among all abstract services, because the atomic service A
S
9 in the execution path P
a
t
h
2 and the execution probability of P
a
t
h
2 is the smallest. We will try to improve the reliability of some critical atomic services to improve the reliability of the composite service.Table 2
Sensitivity results.
A
S
C
i
A
S
1
0.7351
A
S
2
0.7351
A
S
3
0.7351
A
S
4
0.7351
A
S
5
0.7351
A
S
6
0.2205
A
S
7
0.5146
A
S
8
0.1323
A
S
9
0.0882
A
S
10
0.2537
A
S
11
0.2537


## 7. Conclusion and Future Works

In this paper, a new approach has been proposed to evaluate the reliability of composite services based on the hierarchical graph of composite units. The composite services can be decomposed into four different kinds of composite units, and they areA
S, B
C
M, P
a
t
h, and  C
S nodes in the hierarchical graph from bottom to top layer. We proposed a recursive algorithm to compute the reliability for the four kinds of nodes from down to up, which simplifies the whole computational process. We also proposed an algorithm to compute the reliability of some affected nodes when some atomic service nodes are changed. The approach firstly searches the affected path in the hierarchical graph from the changed atomic service node to the root node and all nodes in the path are affected by the atomic service. The reliability of nodes in the affected path is recalculated, and the reliability of composite service is recalculated based on the reliability of paths, instead of recalculating the reliability of all nodes. A case study illustrates how to apply the proposed methods to estimate the composite service reliability. The results of case study show the effectiveness and usefulness of our approach. The proposed approach has some limitations. Currently, a composite service may have more than one decomposition. Which decomposition is the best way and how to select the best decomposition are our new future works.



---

*Source: 917903-2014-07-06.xml*