# A Fast Optimization Method for Reliability and Performance of Cloud Services Composition Application

Authors: Zhao Wu; Naixue Xiong; Yannong Huang; Qiong Gu; Chunyang Hu; Zhongbo Wu; Bo Hang
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

At present the cloud computing is one of the newest trends of distributed computation,
which is propelling another important revolution of software industry. The cloud services
composition is one of the key techniques in software development. The optimization for
reliability and performance of cloud services composition application, which is a typical
stochastic optimization problem, is confronted with severe challenges due to its randomness
and long transaction, as well as the characteristics of the cloud computing resources such
as openness and dynamic. The traditional reliability and performance optimization
techniques, for example, Markov model and state space analysis and so forth, have some defects
such as being too time consuming and easy to cause state
space explosion and unsatisfied the assumptions of component execution independence.
To overcome these defects, we propose a fast optimization method for reliability and performance
of cloud services composition application based on universal generating function and genetic
algorithm in this paper. At first, a reliability and performance model for cloud service composition
application based on the multiple state system theory is presented. Then the reliability and
performance definition based on universal generating function is proposed.
Based on this, a fast reliability and performance optimization algorithm is presented. In the end, the illustrative examples are given.


---

## Body

## 1. Introduction

Cloud computing is an emerging trend for the provision of IT infrastructure as services, with the potential of transforming the way of offering business services [1]. Based on cloud computing platform, software development becomes prominent and accessible for all without the expensive investing in hardware resources and the managing and maintaining costs.On cloud computing platform, the cloud services composition (CSC) is a fashionable approach of software development based on cloud services [2–4]. In the framework of CSC, cloud services are considered as self-contained, self-describing, modular applications that can be published, located, and invoked across the web.How to select and integrate cloud services to satisfy user’s functional requirements is an important issue, which has widely attracted attention of researchers [5]. Great progress has been made in this field [6–8]. However, little research focused on reliability model and simulation for CSC. Recently, there has been growing interest in this field. Methods and technologies related to reliability model and simulation for CSC have attracted attention because they can forecast the QoS that users will obtain from CSC [9–11]. In addition, it is helpful to analyze whether there are some reliability bottlenecks within CSC applications. Thus, reliability prediction is the basis of reliability optimization for the CSC applications.The service-oriented architecture (SOA) is the most representative technological architecture to build the cloud services application on cloud computing platform [12–14]. However, because SOA supposed by services composition technique is of dynamic and cooperative essential characteristic, the traditional software reliability prediction methods are not suitable to the cloud services application based on SOA.From the aspect of software architecture, cloud services application is a kind of Internetware based on cloud services, which is built by cloud services composition technique [15, 16]. As a kind of abstract of distributed software system running on the Internet which is opened, dynamic, and difficult to control, there are many differences between the Internetware and traditional software system, such as structure, operation mechanism, correctness guarantees, development method, and life cycle. Due to the static, closed, and controllable running environment, the traditional software model is of finite autonomy, fixed encapsulation, monotonic interaction, tightly coupled structure, and offline evolution. Being different from the traditional software model, the cloud services application, as a kind of Internetware, exists in each node on the cloud service platform with a subjective software service form. In the running environment, which is opened, dynamic, and difficult to control, the cloud services application has some new characters, such as flexible evolution, continuous reaction, and multitarget self-adaption. Due to being difficult to adapt to these new characters, traditional software reliability assurance methods cannot be adopted for the cloud services application which is built based on service composition technique. Quite different to traditional software reliability assurance technique, the reliability assurance method for the cloud services application pays more attention to the mechanism of flexible reliability measure, predication and self-adapting based on summative evaluation of operation information in opened running environment [17, 18]. So, the fast reliability prediction method for the cloud services application has great theory research value.From the aspect of software online evolution, cloud services application confronts fast and continuous change of user’s requirement and running environment. So, cloud services application must have the ability to apperceive the changes in outrunning environment and dynamically evolve according to functionality and performance requirement with this kind of change. In order to provide better QoS to users, cloud services application must have more adaptability to collect various changes realtimely and adjust oneself online according to preestablished strategies in runtime [19]. However, with the closed, controllable, and static user’s requirement in the background, traditional software reliability prediction methods lack the ability to dynamically adapt themselves to the changes of running environment and user’s requirement. Therefore, it cannot be employed in the reliability prediction for cloud services application. So, the fast reliability prediction method for the cloud services application has important realistic technology requirement.At the present time, the researches on reliability prediction for cloud services application are still just starting Due to the opened and dynamic running environment, continuous variable user’s requirement, randomly selected member services and its own characters of loose coupling and long transaction, the severe challenges are confronted the reliability prediction for cloud services application, which is seriously restricting the further development, application, and extension of cloud services application. In the face of urgent demands of high reliable cloud services application from many government, economy, and commerce fields such as e-government, e-commerce, and  e-bank, the fast reliability optimization becomes the key to promote the successful development, application, and extension of the cloud services application.Facing the challenge, this paper researches the reliability model of cloud services application. On this basis, a fast reliability optimization for cloud services application is presented. The paper is organized as follows. Section2 presents the reliability model for cloud service application based on the multiple state system (MSS) theory. The reliability and performance of cloud service and cloud services composition application are defined in Section 3. Section 4 presents a reliability and performance model for cloud services composition application based on universal generating function (referred to as UGF) technique. A fast reliability optimization algorithm by using the UGF technique is presented in Section 5. Section 6 provides some illustrative examples.


## 2. Reliability Model for Cloud Service Composition Application

### 2.1. Multiple State System Theory

The MSS was introduced in the middle of the 1970s in [20–23]. In these works, the basic concepts of MSS reliability were primarily formulated, the system structure function was defined, and its properties were initially studied. The notions of minimal cut set and minimal path set were introduced in the MSS context, as well as the notions of coherence and element relevancy.Some systems can perform their tasks with various distinguished levels of efficiency usually referred to as performance rates. A system that can have a finite number of performance rates is called a multistate system. Any system consisting of different units that have a cumulative effect on the entire system performance has to be considered as a MSS [24]. So the cloud service application can be regard as a multiple state system.MSS reliability analysis relates to systems for which one cannot formulate an “all or nothing” type of failure criterion. Such systems are able to perform their task with partial performance (intensity of the task accomplishment). Failures of some system elements lead only to the degradation of the system performance.


### 2.2. Reliability and Performance Definition for Cloud Services Composition Application

From the aspect of users, the reliability of cloud service application can be defined as the probability that its performance rates satisfy user’s requirements, described as a vector pair(w,q), where w={w1,w2,…,wM} is a vector of user’s requirement rates wj, (j=1,…,M), and q={q1,q2,…,qM} is the vector of steady state probability qj=Pr{W=wj}, (j=1,…,M), according to a certain user’s requirement rate, where W is a random variable that represents the performance rates of cloud service application.Based on the above definition, the reliability function of cloud service application under steady state can be defined as(1)R(t)=Pr{Tf≥t∣F(G(0),W(0))≥0}.And the one under transient state can be defined as(2)R(t)=Pr{F(G(t),W(t))≥0},
where G(t) is the integral performance rate of cloud service application.In the interval[0,T], the reliability function of cloud service application can be defined as
(3)RT=1T∫0T1(F(G(t),W(t))≥0)dt.Based on the above definition, the reliability function of cloud service application under dynamically changing user’s requirements can be defined as(4)R(w,q)=∑m=1MR(wm)qm=∑m=1Mqm∑k=1Kpk1(F(gk,wm)≥0).In order to calculate the probability distribution of reliability, failure timeTf, time between failures Tb, and failure number NT are defined.


### 2.3. Probability Distribution of Performance Rates for Cloud Service

Furthermore, the performance rates for cloud service can be defined. According to its performance rates, the cloud servicej to build a cloud service application can be of kj kinds of various states, described by gj={gj1,gj2,…,gjkj}, where gji is the performance rate of cloud service j under the state i, i∈{1,2,…,kj}. The performance rate Gj(t) corresponding to the cloud service j in any time t≥0 is a random variable that gets the value from gj: Gj(t)∈gj. The probability of performance rates of the cloud service j under various states in any time t can be described as a set,
(5)pj(t)={pj1(t),gj2(t),…,gjkj(t)},
where pji(t)=Pr{Gj(t)=gji}. Because cloud service j is in one and only one of kj kinds of various states in any time t, these states form a mutual exclusion events complete set. Therefore, the formula ∑i=1kjpji(t)=1, (0≤t≤T) is satisfied. In the end, the set of value pairs 〈gji,pji(t)〉 completely determines the probability distribution of performance rates corresponding to a cloud service j in any time t.


### 2.4. Structure Function of Performance Rates for Cloud Service Application

Based on the above definition of the performance rates of cloud service application and cloud service, the structure function of cloud service application can be defined.  Let(6)Ln={g11,…,g1k1}×{g21,…,g2k2}×⋯×{gn1,…,gnkn}
be the possible combinations of performance rates of all cloud services and M={g1,…,gk} the possible values range of performance rates of cloud service application. Then the transform function ϕ(G1(t),…,Gn(t)):Ln→M, called the structure function of cloud service application, can map the performance rates space of cloud services into one of cloud service applications. Hence, a general reliability model of cloud service application can be defined as
(7)gj,pj(t),1≤j≤n,ϕ(G1(t),…,Gn(t)).The structure function of cloud service application establishes a feasible way to calculate the reliability of cloud service application using one of cloud services.


## 2.1. Multiple State System Theory

The MSS was introduced in the middle of the 1970s in [20–23]. In these works, the basic concepts of MSS reliability were primarily formulated, the system structure function was defined, and its properties were initially studied. The notions of minimal cut set and minimal path set were introduced in the MSS context, as well as the notions of coherence and element relevancy.Some systems can perform their tasks with various distinguished levels of efficiency usually referred to as performance rates. A system that can have a finite number of performance rates is called a multistate system. Any system consisting of different units that have a cumulative effect on the entire system performance has to be considered as a MSS [24]. So the cloud service application can be regard as a multiple state system.MSS reliability analysis relates to systems for which one cannot formulate an “all or nothing” type of failure criterion. Such systems are able to perform their task with partial performance (intensity of the task accomplishment). Failures of some system elements lead only to the degradation of the system performance.


## 2.2. Reliability and Performance Definition for Cloud Services Composition Application

From the aspect of users, the reliability of cloud service application can be defined as the probability that its performance rates satisfy user’s requirements, described as a vector pair(w,q), where w={w1,w2,…,wM} is a vector of user’s requirement rates wj, (j=1,…,M), and q={q1,q2,…,qM} is the vector of steady state probability qj=Pr{W=wj}, (j=1,…,M), according to a certain user’s requirement rate, where W is a random variable that represents the performance rates of cloud service application.Based on the above definition, the reliability function of cloud service application under steady state can be defined as(1)R(t)=Pr{Tf≥t∣F(G(0),W(0))≥0}.And the one under transient state can be defined as(2)R(t)=Pr{F(G(t),W(t))≥0},
where G(t) is the integral performance rate of cloud service application.In the interval[0,T], the reliability function of cloud service application can be defined as
(3)RT=1T∫0T1(F(G(t),W(t))≥0)dt.Based on the above definition, the reliability function of cloud service application under dynamically changing user’s requirements can be defined as(4)R(w,q)=∑m=1MR(wm)qm=∑m=1Mqm∑k=1Kpk1(F(gk,wm)≥0).In order to calculate the probability distribution of reliability, failure timeTf, time between failures Tb, and failure number NT are defined.


## 2.3. Probability Distribution of Performance Rates for Cloud Service

Furthermore, the performance rates for cloud service can be defined. According to its performance rates, the cloud servicej to build a cloud service application can be of kj kinds of various states, described by gj={gj1,gj2,…,gjkj}, where gji is the performance rate of cloud service j under the state i, i∈{1,2,…,kj}. The performance rate Gj(t) corresponding to the cloud service j in any time t≥0 is a random variable that gets the value from gj: Gj(t)∈gj. The probability of performance rates of the cloud service j under various states in any time t can be described as a set,
(5)pj(t)={pj1(t),gj2(t),…,gjkj(t)},
where pji(t)=Pr{Gj(t)=gji}. Because cloud service j is in one and only one of kj kinds of various states in any time t, these states form a mutual exclusion events complete set. Therefore, the formula ∑i=1kjpji(t)=1, (0≤t≤T) is satisfied. In the end, the set of value pairs 〈gji,pji(t)〉 completely determines the probability distribution of performance rates corresponding to a cloud service j in any time t.


## 2.4. Structure Function of Performance Rates for Cloud Service Application

Based on the above definition of the performance rates of cloud service application and cloud service, the structure function of cloud service application can be defined.  Let(6)Ln={g11,…,g1k1}×{g21,…,g2k2}×⋯×{gn1,…,gnkn}
be the possible combinations of performance rates of all cloud services and M={g1,…,gk} the possible values range of performance rates of cloud service application. Then the transform function ϕ(G1(t),…,Gn(t)):Ln→M, called the structure function of cloud service application, can map the performance rates space of cloud services into one of cloud service applications. Hence, a general reliability model of cloud service application can be defined as
(7)gj,pj(t),1≤j≤n,ϕ(G1(t),…,Gn(t)).The structure function of cloud service application establishes a feasible way to calculate the reliability of cloud service application using one of cloud services.


## 3. Reliability and Performance Definition for Cloud Service Composition Application Based on UGF

### 3.1. UGF Technique

The methods of MSS reliability assessment are based on four different approaches:(1) an extension of the Boolean models to the multivalued case; (2) the stochastic process (mainly Markov and semi-Markov) approach; (3) the Monte-Carlo simulation technique; and (4) the UGF approach.The approach based on the extension of Boolean models is historically the first method that was developed and applied for the MSS reliability evaluation. It is based on the natural expansion of the Boolean methods to the multistate systems.The stochastic process methods that are widely used for the MSS reliability analysis are more universal. The method can be applied only to relatively small MSS because the number of system states increases dramatically with the increase in the number of system elements.Even though almost every real world MSS can be represented by the Monte-Carlo simulation for the reliability assessment, the main disadvantages of this approach are the time and expenses involved in the development and execution of the model.The computational burden is the crucial factor when one solves optimization problems where the reliability measures have to be evaluated for a great number of possible solutions along the search process. This makes using the three abovementioned methods in reliability optimization problematic. On the contrary, the UGF technique is fast enough. This technique allows one to find the entire MSS performance distribution based on the performance distribution of its elements by suing a fast algebraic procedure. An analyst can use the same recursive procedures for MSS with a different physical nature of performance and different types of element interaction.For the above reasons, we choose UGF technique to study a fast reliability optimization method for cloud services composition network. The UGF generalizes the technique that is based on using a well-known ordinary generating function. The basic ideas of the method were introduced by Ushakov [25]. The approach proved to be very convenient for numerical realization. It requires relatively small computational resources for evaluating MSS reliability indices and, therefore, can be used in complexes reliability optimization algorithms. Because the relationship between system state probability and system output performance rates can be expressed definitely by UGF, and the u-function of system can be obtained by calculating the u-function of components simply, UGF is approved as an efficient reliability assessment approach that is suitable to various MMS. Therefore, UGF can be successfully applied for the reliability assessment and optimization of MMS.In most studies on the prediction and optimization of system reliability based on the UGF, the system structure and composite form of research object are relatively simple, such as electric power system and mechanical system. The presented design methods and calculation methods of theu-function composite operators are only applicable to some simple structure forms, such as series, parallel, series parallel hybrid, and bridge structure, which limits the application range of the UGF method. Different from the above research objects, the cloud services composition is of complex, flexible and dynamic structure form. The adaptability to complex, flexible and dynamic system, such as the cloud services composition application, becomes advantage and characteristic of our presented method.


### 3.2. Reliability Definition of Cloud Service Composition Application Based on UGF

Based on the reliability model for cloud service application described in Section2, the reliability of cloud service composition can be defined by UGF. The general form of the definition is as follows.The reliability of a cloud service composition (or a cloud service) is a random variableX. Therefore, the corresponding u-function can be defined as
(8)u(z)=∑k=1Kpk·zXk,
where the discrete variable X has K possible values and pk is the reliability when X is in the state Xk. Based on this definition, the reliability of a cloud service composition (or a cloud service) can be expressed as
(9)U(t,z)=∑k=1Kpk(t)·zGk.BecauseU(z) is correlative with the state probability pk and the reliability rate Gk, which correspond to the cloud service composition (or a cloud service), describes the reliability of cloud service composition (or a cloud service). On this basis, we can define related performance operators furthermore, such as usability operator δA, output performance operator δG and unfinished performance operator δU, to describe related reliability indexes.Based on the above performance operators, the related reliability indexes for cloud service composition (or a cloud service) can be defined as follows.(i)
The usability is defined as(10)EA=EA(W,q)=∑m=1Mqm·δR(U(z),F,Wm).(ii)
The output performance expectation is defined as(11)EG=δG(U(z))=δG(∑k=1Kpk·zGk)=dUdz(1)=∑k=1Kpk·Gk.(iii)
The unfinished performance requirement is defined as:(12)EU(W,q)=∑m=1Mqm·δU(U(z),F,Wm),
where
(13)δU(U(z),F,Wm)=δU(∑k=1Kpk·zGk,F,Wm)=∑k=1Kpk·max{-F(Gk,Wm),0}.


### 3.3. Composite Operators of Reliability and Performance Indexes Based on UGF

Based on the above reliability definition expressed by UGF for cloud services, theu-function composite operators Ω can be designed for various performance indexes of the diverse composition patterns. The reliability of cloud service composition can be worked out based on the Ω calculation of cloud services’ reliability.Two rules must be satisfied in the design ofu-function composite operators Ω as follows:
(14)(1)Ω(U1(z),…,Uk(z),Uk+1(z),…,Un(z))=Ω(U1(z),…,Uk+1(z),Uk(z),…,Un(z));(2)Ω(U1(z),…,Uk(z),Uk+1(z),…,Un(z))=Ω(Ω(U1(z),…,Uk(z)),Ω(Uk+1(z),…,Un(z))).The generic form of composite operatorsΩ can be expressed as
(15)Ω(∑∀kpk·zGk,∑∀lpl·zGl)=∑∀k∑∀lpk·pl·zf(Gk,Gl),
where f(Gk,Gl) can be defined according to the performance indexes and composition structures of the cloud service application.


## 3.1. UGF Technique

The methods of MSS reliability assessment are based on four different approaches:(1) an extension of the Boolean models to the multivalued case; (2) the stochastic process (mainly Markov and semi-Markov) approach; (3) the Monte-Carlo simulation technique; and (4) the UGF approach.The approach based on the extension of Boolean models is historically the first method that was developed and applied for the MSS reliability evaluation. It is based on the natural expansion of the Boolean methods to the multistate systems.The stochastic process methods that are widely used for the MSS reliability analysis are more universal. The method can be applied only to relatively small MSS because the number of system states increases dramatically with the increase in the number of system elements.Even though almost every real world MSS can be represented by the Monte-Carlo simulation for the reliability assessment, the main disadvantages of this approach are the time and expenses involved in the development and execution of the model.The computational burden is the crucial factor when one solves optimization problems where the reliability measures have to be evaluated for a great number of possible solutions along the search process. This makes using the three abovementioned methods in reliability optimization problematic. On the contrary, the UGF technique is fast enough. This technique allows one to find the entire MSS performance distribution based on the performance distribution of its elements by suing a fast algebraic procedure. An analyst can use the same recursive procedures for MSS with a different physical nature of performance and different types of element interaction.For the above reasons, we choose UGF technique to study a fast reliability optimization method for cloud services composition network. The UGF generalizes the technique that is based on using a well-known ordinary generating function. The basic ideas of the method were introduced by Ushakov [25]. The approach proved to be very convenient for numerical realization. It requires relatively small computational resources for evaluating MSS reliability indices and, therefore, can be used in complexes reliability optimization algorithms. Because the relationship between system state probability and system output performance rates can be expressed definitely by UGF, and the u-function of system can be obtained by calculating the u-function of components simply, UGF is approved as an efficient reliability assessment approach that is suitable to various MMS. Therefore, UGF can be successfully applied for the reliability assessment and optimization of MMS.In most studies on the prediction and optimization of system reliability based on the UGF, the system structure and composite form of research object are relatively simple, such as electric power system and mechanical system. The presented design methods and calculation methods of theu-function composite operators are only applicable to some simple structure forms, such as series, parallel, series parallel hybrid, and bridge structure, which limits the application range of the UGF method. Different from the above research objects, the cloud services composition is of complex, flexible and dynamic structure form. The adaptability to complex, flexible and dynamic system, such as the cloud services composition application, becomes advantage and characteristic of our presented method.


## 3.2. Reliability Definition of Cloud Service Composition Application Based on UGF

Based on the reliability model for cloud service application described in Section2, the reliability of cloud service composition can be defined by UGF. The general form of the definition is as follows.The reliability of a cloud service composition (or a cloud service) is a random variableX. Therefore, the corresponding u-function can be defined as
(8)u(z)=∑k=1Kpk·zXk,
where the discrete variable X has K possible values and pk is the reliability when X is in the state Xk. Based on this definition, the reliability of a cloud service composition (or a cloud service) can be expressed as
(9)U(t,z)=∑k=1Kpk(t)·zGk.BecauseU(z) is correlative with the state probability pk and the reliability rate Gk, which correspond to the cloud service composition (or a cloud service), describes the reliability of cloud service composition (or a cloud service). On this basis, we can define related performance operators furthermore, such as usability operator δA, output performance operator δG and unfinished performance operator δU, to describe related reliability indexes.Based on the above performance operators, the related reliability indexes for cloud service composition (or a cloud service) can be defined as follows.(i)
The usability is defined as(10)EA=EA(W,q)=∑m=1Mqm·δR(U(z),F,Wm).(ii)
The output performance expectation is defined as(11)EG=δG(U(z))=δG(∑k=1Kpk·zGk)=dUdz(1)=∑k=1Kpk·Gk.(iii)
The unfinished performance requirement is defined as:(12)EU(W,q)=∑m=1Mqm·δU(U(z),F,Wm),
where
(13)δU(U(z),F,Wm)=δU(∑k=1Kpk·zGk,F,Wm)=∑k=1Kpk·max{-F(Gk,Wm),0}.


## 3.3. Composite Operators of Reliability and Performance Indexes Based on UGF

Based on the above reliability definition expressed by UGF for cloud services, theu-function composite operators Ω can be designed for various performance indexes of the diverse composition patterns. The reliability of cloud service composition can be worked out based on the Ω calculation of cloud services’ reliability.Two rules must be satisfied in the design ofu-function composite operators Ω as follows:
(14)(1)Ω(U1(z),…,Uk(z),Uk+1(z),…,Un(z))=Ω(U1(z),…,Uk+1(z),Uk(z),…,Un(z));(2)Ω(U1(z),…,Uk(z),Uk+1(z),…,Un(z))=Ω(Ω(U1(z),…,Uk(z)),Ω(Uk+1(z),…,Un(z))).The generic form of composite operatorsΩ can be expressed as
(15)Ω(∑∀kpk·zGk,∑∀lpl·zGl)=∑∀k∑∀lpk·pl·zf(Gk,Gl),
where f(Gk,Gl) can be defined according to the performance indexes and composition structures of the cloud service application.


## 4. Reliability and Performance Model of Cloud Services Composition Application Based on UGF

### 4.1. Fault Tolerant Model of Cloud Services Composition Application

To strengthen the capability of fault tolerant of cloud service composition applications to improve its reliability and performance, the component duplication technique has been introduced into the design of cloud service composition applications. By deploying a number of functionally equivalent software versions for each cloud service, the cloud service composition applications can avoid the global failure due to the fault of one cloud service as far as possible. We assume thatnc functionally equivalent software versions are available for each cloud service c. Each software version i has an estimated reliability rci and response time τci (it includes the execution time of software version and the network transmission time used transfer computing results to other software version, end users, etc.). Failures of software versions in each cloud service are statistically independent, as well as the total failures of the different cloud services.In many cases, the information about the software version’s reliability and the response time is available from separate testing and/or reliability prediction models. This information can be incorporated into a fault-tolerant program model in order to obtain an evaluation of its reliability and performance.According to the generally accepted model, the cloud service composition application consists ofC cloud services. Each cloud service performs a subtask and the sequential execution of the cloud services performs a major task.To assure that all of the computing tasks can correctly be executed by cloud service, the cloud services broker (referred to as CSB) and the check mechanism are established in the cloud service composition application. The check mechanism presumes that software versions send their computing results to the CSB. Then the CSB compares received computing results with each other. The CSB sends the computing results to the next cloud service in the service flow, if at leastk out of n computing results agree. Otherwise, the CSB discards these received computing results and recalls the cloud services. If the consistent results cannot be obtained after trying a certain number of times, the CSB will stop the execution of the cloud services composition application.The software versions in each cloud servicec run on parallel hardware units. The total number of units is hc. The units are independent and identical. The availability of each unit is ac. The number Hc of units available at the moment determines the amount of available computational resources and, therefore, the number of software versions that can be executed simultaneously Lc(Hc). No hardware unit can change its state during the execution.The software versions of each cloud servicec start their execution in accordance with a predetermined ordered list. Lc first software versions from the list start their execution simultaneously (at time zero). If the number of terminated software versions is less than kc, after termination of each software version a new software version from the list starts its execution immediately. If the number of terminated software versions is not less than kc, after termination of each software version the CSB compares the outputs. If kc outputs are identical, the CSB terminates its execution (terminating all the software versions that are still executed), otherwise a new software version from the list is executed immediately.If after termination ofnc software versions the number of identical outputs is less than kc then the entire cloud services application fail.The execution time of the CSB includes the execution time and data transmission time spent by all cloud services invoked by the CSB and itself. In the case that CSB gets not less thankc consistent results successfully, the time of the entire CSB execution Tc is equal to the termination time of the software version that has produced the kcth correct output (in most cases, the time needed by the CSB to make the decision can be neglected). It can be seen that the CSB execution time is a random variable depending on the reliability and the response time of the software versions and on the availability of the hardware units.The sum of the random execution times of each CSB gives the random task execution time for the entire systemT. In order to estimate both the system's reliability and its performance, different measures can be used, depending on the application.In cloud service applications where the response time of each task is of critical importance, the system’s acceptability function is defined asF(T,w)=1(T<w), where w is a maximal allowed system response time. The system’s reliability R(w)=E(F(T,w)) in this case is the probability that the correct output is produced in time less than w. The conditional expected system response time ε~(w)=E(T×1(T<w))/R(w) is considered to be a measure of the system's performance. This index, defined according to (16), determines the system’s expected response time given that the system and network do not fail:
(16)ε~(w)=E(G~)Pr{F(G,W)=1}=E(GF(G,W))E(F(G,W)).In cloud service applications where the system’s average productivity (the number of executed tasks) over a fixed mission time is of interest, the system’s acceptability function is defined asF(T)=1(T<∞), the system’s reliability is defined as the probability that it produces correct outputs regardless of the total response time (this index can be referred to as R(∞)), and the conditional expected system response time ε~(∞) is considered to be a measure of the system's performance.


#### 4.1.1. Number of Software Versions That Can Be Simultaneously Executed

The number of available hardware units in cloud servicec can vary from 0 to hc. Given that all of the units are identical and have availability ac, one can easily obtain probabilities Qc(x)=Pr{Hc=x} for 0≤x≤hc:
(17)Qc(x)=Pr{Hc=x}=(hcx)acx(1-ac)hc-x.The number of available hardware unitsx determines the number of software versions that can be executed simultaneously: lc(x). Therefore,
(18)Pr{Lc=lc(x)}=Qc(x).The pairsQc(x), lc(x) for 0≤x≤hc determine the probability mass function (referred to as p.m.f. as follows) of the discrete random value Lc.


#### 4.1.2. Termination Times of Software Version

In each cloud servicec, a sequence where each software version starts its execution is defined by the numbers of software versions. This means that each software version i starts its execution not earlier than software versions 1,…,i-1 and not later than software versions i+1,…,nc. If the number of software versions that can run simultaneously is lc, then we can assume that the software versions run on lc independent processors. Let αm be the time when processor m terminates the execution of a software version and is ready to run the next software version from the list of not executed software versions. Having the response time of each software version τci(1≤i≤nc), one can obtain the termination time tci(lc) for each software version i using the following simple algorithm.(1)
Assignα1=⋯=αlc=0 (all of the units are ready to run the software versions at time 0).(2)
Fori=1,…,nc repeat the following:
(a)
find anym(1≤m≤lc):αm=min{α1,…,αlc} (m is the number of the earliest processor that is ready to run a new software version from the list),(b)
obtaintci(lc)=αm+τci and assign αm=tci(lc).Timestci(lc), (1≤i≤nc), correspond to intervals between the beginning of cloud service execution and the moment when the software versions produce their outputs. Observe that the software versions that start execution earlier can terminate later: j<y does not guarantee that tcj(lc)≤tcy(lc). In order to obtain the sequence, in which the software versions produce their outputs, the termination times should be sorted in increasing order tcm1(lc)≤tcm2(lc)≤⋯≤tcmnc(lc) which gives the order of software versions m1,m2,…,mnc corresponding to times of their termination.The ordered listm1,m2,…,mnc determines the sequence of software version outputs. Now one can consider the cloud service c as a system in which the nc software versions are executed consecutively according to the order m1,m2,…,mnc and produce their outputs at times tcm1(lc),tcm2(lc),…,tcmnc(lc).


### 4.2. Definition of Reliability and Performance of the Cloud Service and the Cloud Services Composition Application

Letrcmi be the reliability of the software version that produces ith output in cloud service c (rcmi is equal to the probability that this output is correct). Consider the probability that k out of n first software versions of cloud service c succeed. This probability can be obtained as
(19)Rk=[∏i=1n(1-rcmi)]×[∑i1=1n-k+1rcmi11-rcmi1∑i2=i1+1n-k+2rcmi21-rcmi2⋯∑ik=ik-1+1nrcmik1-rcmik].The cloud servicec produces the correct output directly after the end of the execution of j software versions (j≥kc) if the mjth software version succeeds and exactly kc-1 out of the first executed j-1 software versions succeed.The probability of such eventpcj(lc) is
(20)pcj(lc)=rcmj[∏i=1j-1(1-rcmi)]×[∑i1=1n-kc+1rcmi11-rcmi1∑i2=i1+1n-kc+2rcmi21-rcmi2⋯∑ikc-1=ikc-2+1j-1rcmikc-11-rcmikc-1].Observe thatpcj(lc) is the conditional probability that the cloud service response time is tcmj(lc) given that lc software versions can be executed simultaneously:
(21)pcj(lc)=Pr{Tc=tcmj(lc)∣Lc=lc}.Having the p.m.f. ofLc we can now obtain for 1≤x≤hc(22)Pr{Tc=tcmj(lc(x))}=Pr{Tc=tckj(lc(x))∣Lc=lc(x)}Pr{Lc=lc(x)}=pcj(lc(x))Qc(x).The pairstcmj(lc(x)), pcj(lc(x))Qc(x), obtained for 1≤x≤hc and kc≤j≤nc, determine the p.m.f. of software version response time Tc.Since the events of successful cloud service execution termination for differentj and x are mutually exclusive, we can express the probability of cloud service c success as
(23)Rc(∞)=Pr{Tc<∞}=∑x=1hc[Qc(x)∑j=kcncpcj(lc(x))].Since failure of any cloud service constitutes the failure of the entire application, the application’s reliability can be expressed as(24)R(∞)=∏c=1CRc(∞).For cloud services, there are four kinds of execution patterns in cloud services composition application: sequence, parallel, split, and loop. From the p.m.f. of response timesTc for each cloud service c one can obtain the p.m.f. of the response time of the entire application in accordance with the composition structures and execution logics of the cloud services composition application:
(25)T={∑c=1CTcforsequencestructure,max(T1,…,Tc)forparallelstructure,∑c=1CpcTcforsplitstructure,∑l=1L∑c=1CTcforloopstructure,
where the pc is the probabilities that the cth split is chosen to be executed. The L is the number of times of loop that C cloud services are executed repeatedly. pc and L can be obtained from separate testing and/or prediction models.


## 4.1. Fault Tolerant Model of Cloud Services Composition Application

To strengthen the capability of fault tolerant of cloud service composition applications to improve its reliability and performance, the component duplication technique has been introduced into the design of cloud service composition applications. By deploying a number of functionally equivalent software versions for each cloud service, the cloud service composition applications can avoid the global failure due to the fault of one cloud service as far as possible. We assume thatnc functionally equivalent software versions are available for each cloud service c. Each software version i has an estimated reliability rci and response time τci (it includes the execution time of software version and the network transmission time used transfer computing results to other software version, end users, etc.). Failures of software versions in each cloud service are statistically independent, as well as the total failures of the different cloud services.In many cases, the information about the software version’s reliability and the response time is available from separate testing and/or reliability prediction models. This information can be incorporated into a fault-tolerant program model in order to obtain an evaluation of its reliability and performance.According to the generally accepted model, the cloud service composition application consists ofC cloud services. Each cloud service performs a subtask and the sequential execution of the cloud services performs a major task.To assure that all of the computing tasks can correctly be executed by cloud service, the cloud services broker (referred to as CSB) and the check mechanism are established in the cloud service composition application. The check mechanism presumes that software versions send their computing results to the CSB. Then the CSB compares received computing results with each other. The CSB sends the computing results to the next cloud service in the service flow, if at leastk out of n computing results agree. Otherwise, the CSB discards these received computing results and recalls the cloud services. If the consistent results cannot be obtained after trying a certain number of times, the CSB will stop the execution of the cloud services composition application.The software versions in each cloud servicec run on parallel hardware units. The total number of units is hc. The units are independent and identical. The availability of each unit is ac. The number Hc of units available at the moment determines the amount of available computational resources and, therefore, the number of software versions that can be executed simultaneously Lc(Hc). No hardware unit can change its state during the execution.The software versions of each cloud servicec start their execution in accordance with a predetermined ordered list. Lc first software versions from the list start their execution simultaneously (at time zero). If the number of terminated software versions is less than kc, after termination of each software version a new software version from the list starts its execution immediately. If the number of terminated software versions is not less than kc, after termination of each software version the CSB compares the outputs. If kc outputs are identical, the CSB terminates its execution (terminating all the software versions that are still executed), otherwise a new software version from the list is executed immediately.If after termination ofnc software versions the number of identical outputs is less than kc then the entire cloud services application fail.The execution time of the CSB includes the execution time and data transmission time spent by all cloud services invoked by the CSB and itself. In the case that CSB gets not less thankc consistent results successfully, the time of the entire CSB execution Tc is equal to the termination time of the software version that has produced the kcth correct output (in most cases, the time needed by the CSB to make the decision can be neglected). It can be seen that the CSB execution time is a random variable depending on the reliability and the response time of the software versions and on the availability of the hardware units.The sum of the random execution times of each CSB gives the random task execution time for the entire systemT. In order to estimate both the system's reliability and its performance, different measures can be used, depending on the application.In cloud service applications where the response time of each task is of critical importance, the system’s acceptability function is defined asF(T,w)=1(T<w), where w is a maximal allowed system response time. The system’s reliability R(w)=E(F(T,w)) in this case is the probability that the correct output is produced in time less than w. The conditional expected system response time ε~(w)=E(T×1(T<w))/R(w) is considered to be a measure of the system's performance. This index, defined according to (16), determines the system’s expected response time given that the system and network do not fail:
(16)ε~(w)=E(G~)Pr{F(G,W)=1}=E(GF(G,W))E(F(G,W)).In cloud service applications where the system’s average productivity (the number of executed tasks) over a fixed mission time is of interest, the system’s acceptability function is defined asF(T)=1(T<∞), the system’s reliability is defined as the probability that it produces correct outputs regardless of the total response time (this index can be referred to as R(∞)), and the conditional expected system response time ε~(∞) is considered to be a measure of the system's performance.


### 4.1.1. Number of Software Versions That Can Be Simultaneously Executed

The number of available hardware units in cloud servicec can vary from 0 to hc. Given that all of the units are identical and have availability ac, one can easily obtain probabilities Qc(x)=Pr{Hc=x} for 0≤x≤hc:
(17)Qc(x)=Pr{Hc=x}=(hcx)acx(1-ac)hc-x.The number of available hardware unitsx determines the number of software versions that can be executed simultaneously: lc(x). Therefore,
(18)Pr{Lc=lc(x)}=Qc(x).The pairsQc(x), lc(x) for 0≤x≤hc determine the probability mass function (referred to as p.m.f. as follows) of the discrete random value Lc.


### 4.1.2. Termination Times of Software Version

In each cloud servicec, a sequence where each software version starts its execution is defined by the numbers of software versions. This means that each software version i starts its execution not earlier than software versions 1,…,i-1 and not later than software versions i+1,…,nc. If the number of software versions that can run simultaneously is lc, then we can assume that the software versions run on lc independent processors. Let αm be the time when processor m terminates the execution of a software version and is ready to run the next software version from the list of not executed software versions. Having the response time of each software version τci(1≤i≤nc), one can obtain the termination time tci(lc) for each software version i using the following simple algorithm.(1)
Assignα1=⋯=αlc=0 (all of the units are ready to run the software versions at time 0).(2)
Fori=1,…,nc repeat the following:
(a)
find anym(1≤m≤lc):αm=min{α1,…,αlc} (m is the number of the earliest processor that is ready to run a new software version from the list),(b)
obtaintci(lc)=αm+τci and assign αm=tci(lc).Timestci(lc), (1≤i≤nc), correspond to intervals between the beginning of cloud service execution and the moment when the software versions produce their outputs. Observe that the software versions that start execution earlier can terminate later: j<y does not guarantee that tcj(lc)≤tcy(lc). In order to obtain the sequence, in which the software versions produce their outputs, the termination times should be sorted in increasing order tcm1(lc)≤tcm2(lc)≤⋯≤tcmnc(lc) which gives the order of software versions m1,m2,…,mnc corresponding to times of their termination.The ordered listm1,m2,…,mnc determines the sequence of software version outputs. Now one can consider the cloud service c as a system in which the nc software versions are executed consecutively according to the order m1,m2,…,mnc and produce their outputs at times tcm1(lc),tcm2(lc),…,tcmnc(lc).


## 4.1.1. Number of Software Versions That Can Be Simultaneously Executed

The number of available hardware units in cloud servicec can vary from 0 to hc. Given that all of the units are identical and have availability ac, one can easily obtain probabilities Qc(x)=Pr{Hc=x} for 0≤x≤hc:
(17)Qc(x)=Pr{Hc=x}=(hcx)acx(1-ac)hc-x.The number of available hardware unitsx determines the number of software versions that can be executed simultaneously: lc(x). Therefore,
(18)Pr{Lc=lc(x)}=Qc(x).The pairsQc(x), lc(x) for 0≤x≤hc determine the probability mass function (referred to as p.m.f. as follows) of the discrete random value Lc.


## 4.1.2. Termination Times of Software Version

In each cloud servicec, a sequence where each software version starts its execution is defined by the numbers of software versions. This means that each software version i starts its execution not earlier than software versions 1,…,i-1 and not later than software versions i+1,…,nc. If the number of software versions that can run simultaneously is lc, then we can assume that the software versions run on lc independent processors. Let αm be the time when processor m terminates the execution of a software version and is ready to run the next software version from the list of not executed software versions. Having the response time of each software version τci(1≤i≤nc), one can obtain the termination time tci(lc) for each software version i using the following simple algorithm.(1)
Assignα1=⋯=αlc=0 (all of the units are ready to run the software versions at time 0).(2)
Fori=1,…,nc repeat the following:
(a)
find anym(1≤m≤lc):αm=min{α1,…,αlc} (m is the number of the earliest processor that is ready to run a new software version from the list),(b)
obtaintci(lc)=αm+τci and assign αm=tci(lc).Timestci(lc), (1≤i≤nc), correspond to intervals between the beginning of cloud service execution and the moment when the software versions produce their outputs. Observe that the software versions that start execution earlier can terminate later: j<y does not guarantee that tcj(lc)≤tcy(lc). In order to obtain the sequence, in which the software versions produce their outputs, the termination times should be sorted in increasing order tcm1(lc)≤tcm2(lc)≤⋯≤tcmnc(lc) which gives the order of software versions m1,m2,…,mnc corresponding to times of their termination.The ordered listm1,m2,…,mnc determines the sequence of software version outputs. Now one can consider the cloud service c as a system in which the nc software versions are executed consecutively according to the order m1,m2,…,mnc and produce their outputs at times tcm1(lc),tcm2(lc),…,tcmnc(lc).


## 4.2. Definition of Reliability and Performance of the Cloud Service and the Cloud Services Composition Application

Letrcmi be the reliability of the software version that produces ith output in cloud service c (rcmi is equal to the probability that this output is correct). Consider the probability that k out of n first software versions of cloud service c succeed. This probability can be obtained as
(19)Rk=[∏i=1n(1-rcmi)]×[∑i1=1n-k+1rcmi11-rcmi1∑i2=i1+1n-k+2rcmi21-rcmi2⋯∑ik=ik-1+1nrcmik1-rcmik].The cloud servicec produces the correct output directly after the end of the execution of j software versions (j≥kc) if the mjth software version succeeds and exactly kc-1 out of the first executed j-1 software versions succeed.The probability of such eventpcj(lc) is
(20)pcj(lc)=rcmj[∏i=1j-1(1-rcmi)]×[∑i1=1n-kc+1rcmi11-rcmi1∑i2=i1+1n-kc+2rcmi21-rcmi2⋯∑ikc-1=ikc-2+1j-1rcmikc-11-rcmikc-1].Observe thatpcj(lc) is the conditional probability that the cloud service response time is tcmj(lc) given that lc software versions can be executed simultaneously:
(21)pcj(lc)=Pr{Tc=tcmj(lc)∣Lc=lc}.Having the p.m.f. ofLc we can now obtain for 1≤x≤hc(22)Pr{Tc=tcmj(lc(x))}=Pr{Tc=tckj(lc(x))∣Lc=lc(x)}Pr{Lc=lc(x)}=pcj(lc(x))Qc(x).The pairstcmj(lc(x)), pcj(lc(x))Qc(x), obtained for 1≤x≤hc and kc≤j≤nc, determine the p.m.f. of software version response time Tc.Since the events of successful cloud service execution termination for differentj and x are mutually exclusive, we can express the probability of cloud service c success as
(23)Rc(∞)=Pr{Tc<∞}=∑x=1hc[Qc(x)∑j=kcncpcj(lc(x))].Since failure of any cloud service constitutes the failure of the entire application, the application’s reliability can be expressed as(24)R(∞)=∏c=1CRc(∞).For cloud services, there are four kinds of execution patterns in cloud services composition application: sequence, parallel, split, and loop. From the p.m.f. of response timesTc for each cloud service c one can obtain the p.m.f. of the response time of the entire application in accordance with the composition structures and execution logics of the cloud services composition application:
(25)T={∑c=1CTcforsequencestructure,max(T1,…,Tc)forparallelstructure,∑c=1CpcTcforsplitstructure,∑l=1L∑c=1CTcforloopstructure,
where the pc is the probabilities that the cth split is chosen to be executed. The L is the number of times of loop that C cloud services are executed repeatedly. pc and L can be obtained from separate testing and/or prediction models.


## 5. Fast Optimization Algorithm of Reliability and Performance for Cloud Services Composition Application Based on UGF and GA

### 5.1. Using UGF to Evaluate the Response Time Distribution of Cloud Services

In order to obtain the response time distribution for a cloud servicec for a given lc in the form pcj(lc), tcmj(lc)(kc≤j≤nc) one can determine the realizations tcmj(lc) of the response time Tc(lc) using the algorithm presented in Section 4.1.2 and the corresponding probabilities pcj(lc) using (20). However, the probabilities pcj(lc) can be obtained in a much simpler way using a procedure based on the UGF technique.Let the random binary variablescmi be an indicator of the success of software version mi in cloud service c such that scmi=1 if the software version produces the correct output and scmi=0 if it produces the wrong output. The p.m.f. of scmi can be represented by the u-function
(26)ucmi(z)=rcmiz1+(1-rcmi)z0.
It can be easily seen that using the operator ⊗+ we can obtain the u-function
(27)Ucj(z,lc)=⨂+(ucmi(z),…,ucmj(z))
that represents the p.m.f. of the number of correct outputs in cloud service c after the execution of a group of first j software versions (the order of elements m1,m2,…,mnc and, therefore, Ucj(z,lc) depend on lc). Indeed, the resulting polynomial relates the probabilities of combinations of correct and wrong outputs (the product of corresponding probabilities) with the number of correct outputs in these combinations (the sum of success indicators). Observe that after collecting the like terms (corresponding to obtaining the overall probability of a different combination with the same number of correct outputs) Ucj(z,lc) takes the form
(28)Ucj(z,lc)=∑k=0jπjkzk,
where πjk is the probability that the group of first j software versions produces k correct outputs.Note thatUcj(z,lc) can be obtained by using the recurrent expression:
(29)Ucj(z,lc)=Ucj-1(z,lc)⨂+[rcmjz1+(1-rcmj)z0].According to its definition,pcj(lc) is the probability that the group of first j software versions produces kc correct outputs and the group of first j-1 software versions produces kc-1 correct outputs given that lc software versions can be executed simultaneously. The coefficient πjkc in polynomial Ucj(z,lc) is equal to the conditional probability that the group of first j software versions produces kc correct outputs given that lc software versions can be executed simultaneously.In order to let the coefficientπjkc in polynomial Ucj(z,lc) be equal to pcj(lc), the term with the exponent equal to kc should be removed from Ucj-1(z,lc) before applying (29) (excluding the combination in which j-1 first software versions produce kc correct outputs while the mjth software version fails).If after the execution ofj first software versions the number of correct outputs produced is k and k+nc-j<kc, then the required number of correct outputs kc cannot be obtained even if all the nc-j subsequent software versions produce correct outputs. Therefore, the terms πjkzk with k<kc-nc+j can be removed from Ucj(z,lc).The above considerations lie at the base of the following algorithm for determining all of the probabilitiespcj(lc) (kc≤j≤nc).(1)
For the givenlc, determine the order of software version termination m1,m2,…,mnc using the algorithm from Section 4.1.2.(2)
Determine theu-function of each software version of cloud service c according to (26).(3)
DefineUc0(z,lc)=1. For j=1,2,…,nc,
(a)
obtainUcj(z,lc) using (28) and, after collecting like terms, represent it in the form (29),(b)
remove fromUcj(z,lc) all the terms πjkzk for which k<kc-nc+j,(c)
Ifj≥kc, assign  pcj(lc)=πjkc and remove term πjkczkc from Ucj(z,lc).


### 5.2. Evaluating Response Time Distribution of the Cloud Services Composition Application

Having the pairspcj(lc(x)), tcmj(lc(x)) for each possible realization lc(x) of Lc (1≤x≤hc) and probabilities Pr{Lc=lc(x)}=Qc(x), one can obtain the p.m.f. of random response times Tc for each cloud service by applying (22). If the conditional p.m.f. pcj(lc(x)), tcmj(lc(x)) are represented by the u-function
(30)u~c(z,lc(x))=∑j=kcncpcj(lc(x))ztcmj(lc(x))
then the u-function representing the p.m.f. of the random value Tc takes the form
(31)U~c(z)=∑x=1hcQc(x)u~c(z,lc(x)).In accordance with the four kinds of execution patterns of cloud services in cloud services composition application, we present four kinds of composition operators foru-function operation corresponding to formula (25): (1)
The composition operator⊗sequ for sequence execution pattern:
(32)U~(z)=U~1(z)⨂sequU~2(z)=∑l1=1L1Pr(T1l1=T~1l1)zT~1l1⨂sequ∑l2=1L2Pr(T2l2=T~2l2)zT~2l2=∑l1=1L1∑l2=1L2Pr(T1l1=T~1l1)Pr(T2l2=T~2l2)zT~1l1+T~2l2.(2)
The composition operator⊗para for parallel execution pattern:
(33)U~(z)=U~1(z)⨂paraU~2(z)=∑l1=1L1Pr(T1l1=T~1l1)zT~1l1⨂para∑l2=1L2Pr(T2l2=T~2l2)zT~2l2=∑l1=1L1∑l2=1L2Pr(T1l1=T~1l1)Pr(T2l2=T~2l2)zmax(T~1l1,T~2l2).(3)
The composition operator⊗split for split execution pattern:
(34)U~(z)=U~1(z)⨂splitU~2(z)=∑l1=1L1Pr(T1l1=T~1l1)zT~1l1⨂split∑l2=1L2Pr(T2l2=T~2l2)zT~2l2=p1∑l1=1L1Pr(T1l1=T~1l1)zT~1l1+p2∑l2=1L2Pr(T2l2=T~2l2)zT~2l2,
where the p1 and p2 are the probabilities that the splits, corresponding to U~1(z) and U~2(z), are chosen to execute.(4)
The composition operator⊗loop for loop execution pattern.The composition operator⊗loop can be expressed by multiple composition operators ⊗sequ, because the loop execution pattern can be transformed to an accumulation of multiple sequence execution patterns. The number of composition operators ⊗sequ transformed is equal to the number of times of repeated execution in loop pattern.Hence, one can obtain theu-function U~(z) representing the p.m.f. of the random entire application response time T as
(35)U~(z)=⨂f(U~1(z),…,U~C(z))=⨂f(∑x=1hcQc(x)u~c(z,lc(x))),
where the composition operator ⊗f is an abstract composition operator that it can be one of the composition operators ⊗sequ, ⊗para, ⊗split, and ⊗loop.In accordance with the composition patterns in cloud services composition application, the concreteu-function U~(z) representing the p.m.f. of T can be obtained by replacing ⊗f by one of the composition operators ⊗sequ, ⊗para, ⊗split, and ⊗loop.


### 5.3. Evaluating Response Time Distribution of Different Cloud Services Executed on the Same Hardware

Now consider the case where all of the software cloud services are consecutively executed on the same hardware consisting ofh parallel identical modules with the availability a. The number of available parallel hardware modules H is random with p.m.f. Q(x)=Pr{H=x}, 1≤x≤h, defined in the same way as in (17).WhenH=x, the number of software versions that can be executed simultaneously in each cloud service c is lc(x). The u-functions representing the p.m.f. of the corresponding cloud service response time Tc are u~c(z,lc(x)) defined by (30). The u-function U^(z,x) representing the conditional p.m.f. of the entire application response time T (given that the number of available hardware modules is x) can be obtained for any x(1≤x≤h) as
(36)U^(z,x)=⨂+(u~1(z,l1(x)),…,u~C(z,lC(x)))=∏c=1Cu~c(z,lc(x)).Having the p.m.f. of the random valueH we obtain the u-function U~(z) representing the p.m.f. of T as
(37)U~(z)=∑x=1HQ(x)U^(z,x).


### 5.4. Optimizing the Structure of Cloud Service Composition Application with Fault-Tolerant Mechanism Based on UGF and GA

When a fault-tolerant cloud service application is designed, one has to choose software versions for each cloud service and find the sequence of their execution in order to achieve the entire application’s greatest reliability subject to cost constraints. The software versions are chosen from a list of the available products. Each software version is characterized by its reliability, response time, and cost. The total cost of the entire application is defined according to the cost of its software versions. The cost for each software version can be the purchase cost if the software versions are commercial and the off-the-shelf cost, or it can be an estimate based upon the software version’s size, complexity, and performance.Assume thatBc functionally equivalent software versions are available for each cloud service c and that the number kc of the software versions that should agree in each cloud service is predetermined. The choice of the software versions and the sequence of their execution in each cloud service determine the entire application’s reliability and performance.The permutationxc* of Bc different integer numbers ranging from 1 to Bc determines the order of the software version that can be used in cloud service c. Let ycb=1 if the software version b is chosen to be included in cloud service c and ycb=0 otherwise. The binary vector yc={yc1,…,ycBc} determines the subset of software versions chosen for cloud service c. Having the vectors xc* and yc one can determine the execution order xc of the software versions chosen by removing from xc* any number b for which ycb=0. The total number of software versions in cloud service c (equal to the length of vector yc after removing the unchosen software versions) is determined as
(38)nc=∑b=1Bcycb.The application structure optimization problem can now be formulated by finding vectorsxc for 1≤c≤C that maximize R(w) subject to cost constraint
(39)Ω=∑c=1C∑b∈xcωcb≤Ω*,
where ωcb is the cost of software version b used in cloud service c, Ω is the entire application cost and Ω* is the maximal allowable application cost. Note that the length of vectors xc can vary depending on the number of software versions chosen.In order to encode the variable-length vectorsxc in the GA using the constant length integer strings one can use (Bc+1)-length strings containing permutations of numbers 1,…,Bc,Bc+1. The numbers that appear before Bc+1 determine the vector xc. For example, for Bc=5 the permutations (2,3,6,5,1,4) and (3,1,5,4,2,6) correspond to xc=(2,3) and xc=(3,1,5,4,2) respectively. Any possible vector xc can be represented by the corresponding integer substring containing the permutation of Bc+1 numbers. By combining C substrings corresponding to different cloud services one obtains the integer string a, that encodes the entire application structure.The encoding method is used in which the single permutation defines the sequences of the software versions chosen in each of theC cloud services. The solution encoding string is a permutation of n=∑c=1C(Bc+1) integer numbers ranging from 1 to n. Each number j belonging to the interval ∑c=1m-1(Bc+1)+1≤j≤∑c=1m(Bc+1) corresponds to software version j-∑c=1m-1(Bc+1) of cloud service. The relative order in which the numbers corresponding to the software versions of the same cloud service appear in the string determines the structure of this cloud service.


## 5.1. Using UGF to Evaluate the Response Time Distribution of Cloud Services

In order to obtain the response time distribution for a cloud servicec for a given lc in the form pcj(lc), tcmj(lc)(kc≤j≤nc) one can determine the realizations tcmj(lc) of the response time Tc(lc) using the algorithm presented in Section 4.1.2 and the corresponding probabilities pcj(lc) using (20). However, the probabilities pcj(lc) can be obtained in a much simpler way using a procedure based on the UGF technique.Let the random binary variablescmi be an indicator of the success of software version mi in cloud service c such that scmi=1 if the software version produces the correct output and scmi=0 if it produces the wrong output. The p.m.f. of scmi can be represented by the u-function
(26)ucmi(z)=rcmiz1+(1-rcmi)z0.
It can be easily seen that using the operator ⊗+ we can obtain the u-function
(27)Ucj(z,lc)=⨂+(ucmi(z),…,ucmj(z))
that represents the p.m.f. of the number of correct outputs in cloud service c after the execution of a group of first j software versions (the order of elements m1,m2,…,mnc and, therefore, Ucj(z,lc) depend on lc). Indeed, the resulting polynomial relates the probabilities of combinations of correct and wrong outputs (the product of corresponding probabilities) with the number of correct outputs in these combinations (the sum of success indicators). Observe that after collecting the like terms (corresponding to obtaining the overall probability of a different combination with the same number of correct outputs) Ucj(z,lc) takes the form
(28)Ucj(z,lc)=∑k=0jπjkzk,
where πjk is the probability that the group of first j software versions produces k correct outputs.Note thatUcj(z,lc) can be obtained by using the recurrent expression:
(29)Ucj(z,lc)=Ucj-1(z,lc)⨂+[rcmjz1+(1-rcmj)z0].According to its definition,pcj(lc) is the probability that the group of first j software versions produces kc correct outputs and the group of first j-1 software versions produces kc-1 correct outputs given that lc software versions can be executed simultaneously. The coefficient πjkc in polynomial Ucj(z,lc) is equal to the conditional probability that the group of first j software versions produces kc correct outputs given that lc software versions can be executed simultaneously.In order to let the coefficientπjkc in polynomial Ucj(z,lc) be equal to pcj(lc), the term with the exponent equal to kc should be removed from Ucj-1(z,lc) before applying (29) (excluding the combination in which j-1 first software versions produce kc correct outputs while the mjth software version fails).If after the execution ofj first software versions the number of correct outputs produced is k and k+nc-j<kc, then the required number of correct outputs kc cannot be obtained even if all the nc-j subsequent software versions produce correct outputs. Therefore, the terms πjkzk with k<kc-nc+j can be removed from Ucj(z,lc).The above considerations lie at the base of the following algorithm for determining all of the probabilitiespcj(lc) (kc≤j≤nc).(1)
For the givenlc, determine the order of software version termination m1,m2,…,mnc using the algorithm from Section 4.1.2.(2)
Determine theu-function of each software version of cloud service c according to (26).(3)
DefineUc0(z,lc)=1. For j=1,2,…,nc,
(a)
obtainUcj(z,lc) using (28) and, after collecting like terms, represent it in the form (29),(b)
remove fromUcj(z,lc) all the terms πjkzk for which k<kc-nc+j,(c)
Ifj≥kc, assign  pcj(lc)=πjkc and remove term πjkczkc from Ucj(z,lc).


## 5.2. Evaluating Response Time Distribution of the Cloud Services Composition Application

Having the pairspcj(lc(x)), tcmj(lc(x)) for each possible realization lc(x) of Lc (1≤x≤hc) and probabilities Pr{Lc=lc(x)}=Qc(x), one can obtain the p.m.f. of random response times Tc for each cloud service by applying (22). If the conditional p.m.f. pcj(lc(x)), tcmj(lc(x)) are represented by the u-function
(30)u~c(z,lc(x))=∑j=kcncpcj(lc(x))ztcmj(lc(x))
then the u-function representing the p.m.f. of the random value Tc takes the form
(31)U~c(z)=∑x=1hcQc(x)u~c(z,lc(x)).In accordance with the four kinds of execution patterns of cloud services in cloud services composition application, we present four kinds of composition operators foru-function operation corresponding to formula (25): (1)
The composition operator⊗sequ for sequence execution pattern:
(32)U~(z)=U~1(z)⨂sequU~2(z)=∑l1=1L1Pr(T1l1=T~1l1)zT~1l1⨂sequ∑l2=1L2Pr(T2l2=T~2l2)zT~2l2=∑l1=1L1∑l2=1L2Pr(T1l1=T~1l1)Pr(T2l2=T~2l2)zT~1l1+T~2l2.(2)
The composition operator⊗para for parallel execution pattern:
(33)U~(z)=U~1(z)⨂paraU~2(z)=∑l1=1L1Pr(T1l1=T~1l1)zT~1l1⨂para∑l2=1L2Pr(T2l2=T~2l2)zT~2l2=∑l1=1L1∑l2=1L2Pr(T1l1=T~1l1)Pr(T2l2=T~2l2)zmax(T~1l1,T~2l2).(3)
The composition operator⊗split for split execution pattern:
(34)U~(z)=U~1(z)⨂splitU~2(z)=∑l1=1L1Pr(T1l1=T~1l1)zT~1l1⨂split∑l2=1L2Pr(T2l2=T~2l2)zT~2l2=p1∑l1=1L1Pr(T1l1=T~1l1)zT~1l1+p2∑l2=1L2Pr(T2l2=T~2l2)zT~2l2,
where the p1 and p2 are the probabilities that the splits, corresponding to U~1(z) and U~2(z), are chosen to execute.(4)
The composition operator⊗loop for loop execution pattern.The composition operator⊗loop can be expressed by multiple composition operators ⊗sequ, because the loop execution pattern can be transformed to an accumulation of multiple sequence execution patterns. The number of composition operators ⊗sequ transformed is equal to the number of times of repeated execution in loop pattern.Hence, one can obtain theu-function U~(z) representing the p.m.f. of the random entire application response time T as
(35)U~(z)=⨂f(U~1(z),…,U~C(z))=⨂f(∑x=1hcQc(x)u~c(z,lc(x))),
where the composition operator ⊗f is an abstract composition operator that it can be one of the composition operators ⊗sequ, ⊗para, ⊗split, and ⊗loop.In accordance with the composition patterns in cloud services composition application, the concreteu-function U~(z) representing the p.m.f. of T can be obtained by replacing ⊗f by one of the composition operators ⊗sequ, ⊗para, ⊗split, and ⊗loop.


## 5.3. Evaluating Response Time Distribution of Different Cloud Services Executed on the Same Hardware

Now consider the case where all of the software cloud services are consecutively executed on the same hardware consisting ofh parallel identical modules with the availability a. The number of available parallel hardware modules H is random with p.m.f. Q(x)=Pr{H=x}, 1≤x≤h, defined in the same way as in (17).WhenH=x, the number of software versions that can be executed simultaneously in each cloud service c is lc(x). The u-functions representing the p.m.f. of the corresponding cloud service response time Tc are u~c(z,lc(x)) defined by (30). The u-function U^(z,x) representing the conditional p.m.f. of the entire application response time T (given that the number of available hardware modules is x) can be obtained for any x(1≤x≤h) as
(36)U^(z,x)=⨂+(u~1(z,l1(x)),…,u~C(z,lC(x)))=∏c=1Cu~c(z,lc(x)).Having the p.m.f. of the random valueH we obtain the u-function U~(z) representing the p.m.f. of T as
(37)U~(z)=∑x=1HQ(x)U^(z,x).


## 5.4. Optimizing the Structure of Cloud Service Composition Application with Fault-Tolerant Mechanism Based on UGF and GA

When a fault-tolerant cloud service application is designed, one has to choose software versions for each cloud service and find the sequence of their execution in order to achieve the entire application’s greatest reliability subject to cost constraints. The software versions are chosen from a list of the available products. Each software version is characterized by its reliability, response time, and cost. The total cost of the entire application is defined according to the cost of its software versions. The cost for each software version can be the purchase cost if the software versions are commercial and the off-the-shelf cost, or it can be an estimate based upon the software version’s size, complexity, and performance.Assume thatBc functionally equivalent software versions are available for each cloud service c and that the number kc of the software versions that should agree in each cloud service is predetermined. The choice of the software versions and the sequence of their execution in each cloud service determine the entire application’s reliability and performance.The permutationxc* of Bc different integer numbers ranging from 1 to Bc determines the order of the software version that can be used in cloud service c. Let ycb=1 if the software version b is chosen to be included in cloud service c and ycb=0 otherwise. The binary vector yc={yc1,…,ycBc} determines the subset of software versions chosen for cloud service c. Having the vectors xc* and yc one can determine the execution order xc of the software versions chosen by removing from xc* any number b for which ycb=0. The total number of software versions in cloud service c (equal to the length of vector yc after removing the unchosen software versions) is determined as
(38)nc=∑b=1Bcycb.The application structure optimization problem can now be formulated by finding vectorsxc for 1≤c≤C that maximize R(w) subject to cost constraint
(39)Ω=∑c=1C∑b∈xcωcb≤Ω*,
where ωcb is the cost of software version b used in cloud service c, Ω is the entire application cost and Ω* is the maximal allowable application cost. Note that the length of vectors xc can vary depending on the number of software versions chosen.In order to encode the variable-length vectorsxc in the GA using the constant length integer strings one can use (Bc+1)-length strings containing permutations of numbers 1,…,Bc,Bc+1. The numbers that appear before Bc+1 determine the vector xc. For example, for Bc=5 the permutations (2,3,6,5,1,4) and (3,1,5,4,2,6) correspond to xc=(2,3) and xc=(3,1,5,4,2) respectively. Any possible vector xc can be represented by the corresponding integer substring containing the permutation of Bc+1 numbers. By combining C substrings corresponding to different cloud services one obtains the integer string a, that encodes the entire application structure.The encoding method is used in which the single permutation defines the sequences of the software versions chosen in each of theC cloud services. The solution encoding string is a permutation of n=∑c=1C(Bc+1) integer numbers ranging from 1 to n. Each number j belonging to the interval ∑c=1m-1(Bc+1)+1≤j≤∑c=1m(Bc+1) corresponds to software version j-∑c=1m-1(Bc+1) of cloud service. The relative order in which the numbers corresponding to the software versions of the same cloud service appear in the string determines the structure of this cloud service.


## 6. Illustrative Examples

Consider a fault-tolerant cloud services composition application consisting of five cloud services in serial running on fully available hardware. The parameters of the software versions that can be used in these cloud services are presented in Table1. This table contains the values of kc and Lc for each cloud service and the cost, reliability, and response time for each software version.Table 1
Parameters of fault-tolerant cloud services and software versions.
No. of cloud services
L
c
k
c
Software  versions
1
2
3
4
5
6
7
8
1
1
1
c
5
15
7
8
12
6
—
—
τ
17
10
20
32
30
75
—
—
r
0.71
0.85
0.85
0.89
0.95
0.98
—
—
2
2
2
c
5
15
7
8
12
—
—
—
τ
28
55
35
55
58
—
—
—
r
0.71
0.85
0.85
0.89
0.95
—
—
—
3
4
3
c
4
3
4
6
5
4
9
6
τ
17
20
38
38
48
50
41
63
r
0.80
0.80
0.86
0.90
0.90
0.94
0.98
0.98
4
1
2
c
12
16
17
17
—
—
—
—
τ
17
10
20
32
—
—
—
—
r
0.75
0.85
0.93
0.97
—
—
—
—
5
3
1
c
5
9
11
7
12
—
—
—
τ
30
54
40
65
70
—
—
—
r
0.70
0.80
0.80
0.80
0.89
—
—
—Two sets of solutions were obtained for the maximal allowable application response timesw=250 and w=300. For each value of w, four different solutions were obtained for different cost constraints. These solutions are presented in Tables 2 and 3. The tables contain the application corresponding cost and reliability for each optimal solution, the expected conditional response time, minimal and maximal possible application response times, and the corresponding optimal execution sequences of the software versions chosen.Table 2
Parameters of solutions obtained forw=250.
Ω
*
Sequence of software versions
T
min
T
max
Ω
R(250)
ε
~(∞)
160
231 ∣ 541 ∣ 37162 ∣ 324 ∣ 214
166
307
159
0.913
188.34
140
34 ∣ 241 ∣ 64231 ∣ 234 ∣ 123
173
301
140
0.868
194.43
120
5 ∣ 431 ∣ 31562 ∣ 43 ∣ 21
205
249
119
0.752
217.07
100
3 ∣ 241 ∣ 4562 ∣ 43 ∣ 41
205
270
100
0.598
220.52Table 3
Parameters of solutions obtained forw=300.
Ω
*
Sequence of software versions
T
min
T
max
Ω
R(300)
ε
~
(
∞
)
160
341 ∣ 4521 ∣ 85632 ∣ 324 ∣ 41
188
369
160
0.951
210.82
140
53 ∣ 541 ∣ 28361 ∣ 431 ∣ 51
173
301
140
0.868
194.43
120
6 ∣ 241 ∣ 61372 ∣ 241 ∣ 31
240
307
120
0.813
252.87
100
4 ∣ 142 ∣ 2386 ∣ 43 ∣ 41
219
295
100
0.672
238.05Comparing the entire application cost and the reliability of the optimal solutions corresponding tow=250 and w=300 in Tables 2 and 3, it can be seen that the entire application cost and the reliability of the optimal solution corresponding to w=300 are always equal or greater than ones corresponding to w=250 in the case of the same value of Ω*.Comparing the entire application cost and the reliability of the optimal solutions corresponding to the different 4 maximal allowable application costs in Tables2 and 3, it can be seen that the entire application cost and the reliability of the optimal solution corresponding to larger Ω* are always equal or greater than ones corresponding to smaller Ω* in the case of the same value of w.From Tables2 and 3, it can also be seen that the software versions executed in practice gradually become more and more along with the growth of the value of Ω*.These phenomenon above indicates that the selection of suitableΩ* and w is helpful to improve the reliability of the cloud services composition application and cut down the cost.To help the designers of the cloud services composition application to select the suitableΩ* and w, the values of the functions R(w) of all of solutions obtained are drawn in Figure 1. At first, the designers can intuitively find out which curves cross over the value of reliability demand. On this basis, the designers can easily find which points (solution) can meet the maximal allowable response time. The approach abovementioned can be easily realized by software. Thus, it can be applied in online prediction and optimization situation.Figure 1
R
(
w
) functions for the solutions obtained.


## 7. Conclusions

The traditional reliability and performance prediction and optimization techniques, for example, Markov model and state space analysis, have some defects such as being too time consuming and easy to cause state space explosion and unsatisfied the assumptions of component execution independence by Markov model. Aiming at the defects of Markov model, an optimization model of reliability and performance based on MSS for cloud services application is proposed in this paper, which eliminates the limitation for component execution independence, and more fits the actual execution of cloud services composition application. On this basis, aiming at the defects of state space analysis technique, a fast optimization algorithm with very small time consumption based on UGF and GA for the reliability and performance of cloud services composition application is presented in this paper, which eliminates the risk of state space explosion. The model and algorithm presented in this paper can be applied in online prediction and optimization for reliability and performance of cloud services composition application.



---

*Source: 407267-2013-10-29.xml*