# A QoS-Satisfied Prediction Model for Cloud-Service Composition Based on a Hidden Markov Model

Authors: Qingtao Wu; Mingchuan Zhang; Ruijuan Zheng; Ying Lou; Wangyang Wei
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Various significant issues in cloud computing, such as service provision, service matching, and service assessment, have attracted researchers’ attention recently. Quality of service (QoS) plays an increasingly important role in the provision of cloud-based services, by aiming for the seamless and dynamic integration of cloud-service components. In this paper, we focus on QoS-satisfied predictions about the composition of cloud-service components and present a QoS-satisfied prediction model based on a hidden Markov model. In providing a cloud-based service for a user, if the user’s QoS cannot be satisfied by a single cloud-service component, component composition should be considered, where its QoS-satisfied capability needs to be proactively predicted to be able to guarantee the user’s QoS. We discuss the proposed model in detail and prove some aspects of the model. Simulation results show that our model can achieve high prediction accuracies.


---

## Body

## 1. Introduction

Cloud computing is a term used to refer to the use of widespread, shared computing resources. It is an alternative to having local servers handle computing applications. Cloud computing groups together a large number of computing servers and other resources, often offering their combined capacity on an on-demand, pay-per-cycle basis. The end users of a cloud computing network usually have no idea where the servers are physically located—they just open their applications and start working [1–3].In general, the service resources in cloud computing will include hardware resources (e.g., processors, storage, and networking) and software resources (e.g., web servers, databases, message queuing systems, and monitoring systems). Cloud service types can be abstracted into three layers, namely software as a service (SaaS), platform as a service (PaaS), and infrastructure as a service (IaaS) [4]. Hardware and software resources form the basis for delivering IaaS and PaaS. The SaaS layer at the top focuses on application services by making use of services provided by the lower layers. PaaS/SaaS services are often developed and provided by third-party service providers who are different from the IaaS provider.Therefore, matching the cloud-service components to the users’ quality of service (QoS) is very important because user experience is a principal reason for promoting the development of cloud computing. For each user request, the provider should select an appropriate composition of cloud-service components to serve the user if there is no single cloud-service component that satisfies the user’s QoS perfectly. This will require predictions to be made about the QoS satisfaction for compositions of cloud-service components.Wang et al. [5] propose a composition method for selecting cloud-based web services from candidate services, changing a single service into a more powerful composite service, which uses the Skyline operator and Particle Swarm Optimization. Javadi et al. [6] investigate cloud-computing resource provision to extend the computing capacity of local clusters in the presence of failures. Their three steps in resource provision include resource brokering, dispatch sequences, and scheduling. Benouaret et al. [7] present an approach to composing Data Web services automatically while taking into account user preferences, which is based on fuzzy sets and top-k optimization. Liu et al. [8] introduce a scheme to address the particularities of manufacturing-resource service composition and optimization, where the user’s QoS is considered. Zhang et al. [4] present an investigation of an intelligent decision-support system for selecting cloud-based infrastructure services to choose the best mix of service offerings from an abundance of possibilities. Although those papers discuss the composition of cloud-service components, QoS-satisfied predictions are not considered.Huang et al. [9] introduce a method for addressing the problem of composing a sequence of service components for QoS-guaranteed service provision in a virtualization-based cloud-computing environment. Huang et al. [10] designs a suboptimal resource-allocation system in a cloud-computing environment, and a corresponding prediction mechanism is realized by using support-vector regression to estimate the resource utilization. Di and Wang [11] propose a fully distributed, VM-multiplexing resource-allocation scheme to manage decentralized resources. Jiang et al. [12] propose a new method for cloud-capacity planning, with the goals of utilizing the physical resources fully and providing an integrated system with intelligent cloud-capacity prediction.The Markov model (MM), particularly the hidden Markov model (HMM), has been shown to be a good technique for solving prediction problems. Zhang and Pathirana [13] present an adaptive HMM for identifying underlying path losses. Choi et al. [14] present a sparsely correlated HMM for assessing multiple genomic datasets. Botev et al. [15] present a versatile Monte Carlo method for estimating multidimensional integrals, with application to rare-event probability estimation. Xie et al. [16] present a new structurally discrete approach to predicting network traffic called the nested hidden semi-Markov model, which includes a nested latent semi-Markov chain and one observable discrete stochastic process. However, further research into QoS-satisfied capability should be considered.This paper focuses on QoS-satisfied predictions for compositions of cloud-service components, based on the HMM and our previous work [17–19]. The remainder of this paper is organized as follows. In Section 2, the basic model used in later discussion is presented. In Section 3, we propose a QoS-satisfied prediction model and explain it in detail. In Section 4, the simulation and analysis are discussed. Finally, we conclude the paper in Section 5.


## 2. Basic Model

The MM is a statistical model with a wide area of application. Many other Markov models are derived fundamentally from MM, including the HMM and the semi-Markov model. The HMM is used extensively for performance modeling and performance-prediction analysis, where the HMM can predict the future state of a target system based on its current state. In reality, because the relationship between the observed time and the observed state is not one to one, a group of probability distributions for two stochastic processes are involved, called the HMM.In an HMM, the states are not observable, but when we visit a state, an observation is recorded that is a probabilistic function of the state. We assume a discrete observation in each state from the set(1){v1,v2,…,vM}:bj(m)≜Pr(Ot=vm∣qt=Sj),
where bj(m) is the observation or emission probability. We also assume a homogeneous model for which the probabilities do not depend on t. The values thus observed constitute an observation sequence O. The state sequence Q is not observed directly (being “hidden”), but it should be possible to infer it from the observation sequence O. An example of an observable model for an HMM is shown in Figure 1, where M=N and bj(m)=1 if j=m and bj(m)=0 otherwise. To summarize and formalize, an HMM has the following elements:(1)
N: the number of states in the model
(2)S={S1,S2,…,SN}(2)
M: the number of distinct observation symbols in the alphabet(3)V={v1,v2,…,vM}.(3)
State transition probabilities:(4)A=[aij],whereaij=Pr(qt+1=Sj∣qt=Si).(4)
Observation probabilities:(5)B=[bj(m)],wherebj(m)=Pr(Ot=vm∣qt=Sj).(5)
Initial state probabilities:(6)Π=[πi],whereπi=Pr(q1=Si).N and M are implicitly defined by the other parameters, leaving λ=(A,B,Π) as the parameter set for an HMM. Given λ, the model can be used to generate an arbitrary number of observation sequences of arbitrary length, but we are usually interested in the other direction, namely, that of estimating the parameters of the model given a training set of sequences.Figure 1
An example of an observable model for an HMM.


## 3. Proposed QoS-Satisfied Prediction Model for Cloud-Service Composition

In this section, we propose a prediction model for cloud-service composition based on an HMM. We first present an overview of cloud-service composition and then give details of the prediction model.


### 3.1. An Overview of Cloud-Service Composition and Matching

The key roles played in a cloud environment are those of the service user and the service provider. The cloud-service user needs anytime, anywhere QoS-satisfied and low-cost services that are flexible and easy to use. The important hurdles to users adopting cloud services involve security, availability, and reliability. We should therefore assess the QoS-satisfied capability for each service provision generated by matching cloud-service components with the users’ QoS. Sometimes, if a single cloud-service component does not satisfy the users’ QoS, multiple cloud-service components should be composed to provide a more complex service. General flowcharts for cloud services and for a cloud-service component-matching model are shown in Figures2 and 3, respectively.Figure 2
General flowchart for cloud-service provision.Figure 3
Cloud-service component-matching model.


### 3.2. QoS-Satisfied Prediction Model

We propose a QoS-satisfied prediction model based on an HMM to predict whether a composition of cloud-service components can satisfy the user’s QoS. Using the basic HMM model, we assume that the QoS capability of cloud-service components is a state set{v1,v2,…,vM}:bj(m)≜Pr(Ot=vm∣qt=Sj), where bj(m) is the observation probability of obtaining vm(m=1,2,…,M) when the composition state is Sj and O is a sequence of obtained vm values. To reduce the complexity of calculation for Pr(O∣λ), we define a forward variable
(7)αt(i)≜Pr(O1,O2,…,Ot,qt=Si∣λ),1≤i≤N.The three stages of its recursion are shown in Figure4(a) and described as follows.Forward-backward procedure: (a) computation ofαt(j); (b) computation of βt(j).
(a)
Forward
(b)
Backward(1) Initialization:(8)α1(i)≜Pr(O1,q1=Si∣λ)=Pr(O1∣q1=Si,λ)Pr(q1=Si∣λ)=πibi(O1).(2) Recursion:(9)αt+1(j)≜Pr(O1,…Ot+1,qt+1=Sj∣λ)=[∑i=1Nαt(i)aij]bj(Ot+1).Proof
(10)
α
t
+
1
(
j
)
≜
Pr
(
O
1
,
…
,
O
t
+
1
,
q
t
+
1
=
S
j
∣
λ
)
=
Pr
(
O
1
,
…
,
O
t
+
1
∣
q
t
+
1
=
S
j
,
λ
)
Pr
(
q
t
+
1
=
S
j
∣
λ
)
=
Pr
(
O
1
,
…
,
O
t
∣
q
t
+
1
=
S
j
,
λ
)
·
Pr
(
O
t
+
1
∣
q
t
+
1
=
S
j
,
λ
)
Pr
(
q
t
+
1
=
S
j
∣
λ
)
=
Pr
(
O
1
,
…
,
O
t
,
q
t
+
1
=
S
j
∣
λ
)
·
Pr
(
O
t
+
1
∣
q
t
+
1
=
S
j
,
λ
)
=
Pr
(
O
t
+
1
∣
q
t
+
1
=
S
j
,
λ
)
·
∑
i
=
1
N
Pr
(
O
1
,
…
,
O
t
,
q
t
=
S
i
,
q
t
+
1
=
S
j
∣
λ
)
=
Pr
(
O
t
+
1
∣
q
t
+
1
=
S
j
,
λ
)
·
∑
i
=
1
N
Pr
(
O
1
,
…
,
O
t
,
q
t
+
1
=
S
j
∣
q
t
=
S
i
,
λ
)
·
Pr
(
q
t
=
S
i
∣
λ
)
=
Pr
(
O
t
+
1
∣
q
t
+
1
=
S
j
,
λ
)
·
∑
i
=
1
N
Pr
(
O
1
,
…
,
O
t
,
q
t
=
S
i
∣
λ
)
·
Pr
(
q
t
+
1
=
S
j
∣
q
t
=
S
i
,
λ
)
=
[
∑
i
=
1
N
α
t
(
i
)
a
i
j
]
b
j
(
O
t
+
1
)
.(3) End:(11)Pr(O∣λ)=∑i=1NPr(O,qT=Si∣λ)=∑i=1NαT(i).
Similarly, we define a backward variable
(12)βt(i)≜Pr(Ot+1,…,OT∣qt=Si,λ).
The three stages of its recursion are shown in Figure 4(b) and described as follows.(1) Initialization:(13)βT(i)=1.(2) Recursion:(14)βt(i)≜Pr(Ot+1,…,OT∣qt=Si,λ)=∑j=1Naijbj(Ot+1)βt+1(j).Proof
(15)
β
t
(
i
)
≜
Pr
(
O
t
+
1
,
…
,
O
T
∣
q
t
=
S
i
,
λ
)
=
∑
j
=
1
N
Pr
(
O
t
+
1
,
…
,
O
T
,
q
t
+
1
=
S
j
∣
q
t
=
S
i
,
λ
)
=
∑
j
=
1
N
Pr
(
O
t
+
1
,
…
,
O
T
∣
q
t
+
1
=
S
j
,
q
t
=
S
i
,
λ
)
·
Pr
(
q
t
+
1
=
S
j
∣
q
t
=
S
i
,
λ
)
=
∑
j
=
1
N
Pr
(
O
t
+
1
∣
q
t
+
1
=
S
j
,
q
t
=
S
i
,
λ
)
·
Pr
(
O
t
+
2
,
…
,
O
T
∣
q
t
+
1
=
S
j
,
q
t
=
S
i
,
λ
)
·
Pr
(
q
t
+
1
=
S
j
∣
q
t
=
S
i
,
λ
)
=
∑
j
=
1
N
Pr
(
O
t
+
1
∣
q
t
+
1
=
S
j
,
λ
)
·
Pr
(
O
t
+
2
,
…
,
O
T
∣
q
t
+
1
=
S
j
,
λ
)
·
Pr
(
q
t
+
1
=
S
j
∣
q
t
=
S
i
,
λ
)
=
∑
j
=
1
N
a
i
j
b
j
(
O
t
+
1
)
β
t
+
1
(
j
)
.(3) End:(16)Pr(O∣λ)=∑i=1Nβ1(i).
From these forward and backward variables, we have
(17)Pr(O∣λ)=∑i=1N∑j=1Nαt(i)aijbj(Ot+1)βt+1(j),1≤t≤T-1.We therefore obtainλ*=argmaxλPr(O∣λ), which is a functional extremum problem. Because the length of the training sequence is limited, there is no optimal method for estimating λ. Therefore, recursion is used to achieve a maximum local value for Pr(O∣λ), thereby obtaining the model parameter set λ=(A,B,Π).We defineξt(i,j) as the probability of being in Si at time t and in Sj at time t+1, given the whole observation sequence O and the model parameter set λ. Then
(18)ξt(i,j)≜Pr(qt=Si,qt+1=Sj∣O,λ)=αt(i)bj(Ot+1)βt+1(j)aij∑k=1N∑l=1Nαt(k)aklbl(Ot+1)βt+1(l).Proof
(19)
ξ
t
(
i
,
j
)
≜
Pr
(
q
t
=
S
i
,
q
t
+
1
=
S
j
∣
O
,
λ
)
=
Pr
(
O
∣
q
t
=
S
i
,
q
t
+
1
=
S
j
,
λ
)
·
Pr
(
q
t
=
S
i
,
q
t
+
1
=
S
j
∣
λ
)
Pr
(
O
∣
λ
)
=
Pr
(
O
∣
q
t
=
S
i
,
q
t
+
1
=
S
j
,
λ
)
·
Pr
(
q
t
+
1
=
S
j
∣
q
t
=
S
i
,
λ
)
·
Pr
(
q
t
∣
λ
)
Pr
(
O
∣
λ
)
=
Pr
(
O
1
,
…
,
O
t
∣
q
t
=
S
i
,
λ
)
·
Pr
(
O
t
+
1
∣
q
t
+
1
=
S
j
,
λ
)
·
Pr
(
O
t
+
2
,
…
,
O
T
∣
q
t
+
1
=
S
j
,
λ
)
·
a
i
j
Pr
(
q
t
=
S
i
∣
λ
)
Pr
(
O
∣
λ
)
=
Pr
(
O
1
,
…
,
O
t
,
q
t
=
S
i
∣
λ
)
Pr
(
O
t
+
1
∣
q
t
+
1
=
S
j
,
λ
)
·
Pr
(
O
t
+
2
,
…
,
O
T
∣
q
t
+
1
=
S
j
,
λ
)
a
i
j
Pr
(
O
∣
λ
)
=
α
t
(
i
)
b
j
(
O
t
+
1
)
β
t
+
1
(
j
)
a
i
j
Pr
(
O
∣
λ
)
=
α
t
(
i
)
b
j
(
O
t
+
1
)
β
t
+
1
(
j
)
a
i
j
∑
k
=
1
N
∑
l
=
1
N
Pr
(
q
t
=
S
k
,
q
t
+
1
=
S
l
,
O
∣
λ
)
=
α
t
(
i
)
b
j
(
O
t
+
1
)
β
t
+
1
(
j
)
a
i
j
∑
k
=
1
N
∑
l
=
1
N
α
t
(
k
)
a
k
l
b
l
(
O
t
+
1
)
β
t
+
1
(
l
)
.
Thus, the probability of being insi at time t is therefore given by
(20)γt(i)=Pr(O,qt=Si∣λ)=∑j=1Nξt(i,j),
where ∑t=1T-1ξt(i,j) denotes the mathematical expectation of transition from state Si. Therefore, the probability of transition from Si to Sj is given by
(21)a^ij=∑t=1T-1ξt(i,j)∑t=1T-1γt(i).
In state Sj, the probability of observing vm is given by
(22)b^j(m)=∑t=1Tγt(j)1(Ot=vm)∑t=1Tγt(j).
We therefore obtain a new modelλ^=(A^,B^,Π^), where A^=[a^ij], B^=[bj(m)], Π^=[π^i], and π^i=γ1(i). We can prove Pr(O∣λ^)≥Pr(O∣λ). The training process is repeated, and the model parameters are adjusted gradually until Pr(O∣λ^) converges. Finally, we obtain the prediction model λ^, which is used to assess the QoS-satisfied capability for compositions of cloud-service components.


## 3.1. An Overview of Cloud-Service Composition and Matching

The key roles played in a cloud environment are those of the service user and the service provider. The cloud-service user needs anytime, anywhere QoS-satisfied and low-cost services that are flexible and easy to use. The important hurdles to users adopting cloud services involve security, availability, and reliability. We should therefore assess the QoS-satisfied capability for each service provision generated by matching cloud-service components with the users’ QoS. Sometimes, if a single cloud-service component does not satisfy the users’ QoS, multiple cloud-service components should be composed to provide a more complex service. General flowcharts for cloud services and for a cloud-service component-matching model are shown in Figures2 and 3, respectively.Figure 2
General flowchart for cloud-service provision.Figure 3
Cloud-service component-matching model.


## 3.2. QoS-Satisfied Prediction Model

We propose a QoS-satisfied prediction model based on an HMM to predict whether a composition of cloud-service components can satisfy the user’s QoS. Using the basic HMM model, we assume that the QoS capability of cloud-service components is a state set{v1,v2,…,vM}:bj(m)≜Pr(Ot=vm∣qt=Sj), where bj(m) is the observation probability of obtaining vm(m=1,2,…,M) when the composition state is Sj and O is a sequence of obtained vm values. To reduce the complexity of calculation for Pr(O∣λ), we define a forward variable
(7)αt(i)≜Pr(O1,O2,…,Ot,qt=Si∣λ),1≤i≤N.The three stages of its recursion are shown in Figure4(a) and described as follows.Forward-backward procedure: (a) computation ofαt(j); (b) computation of βt(j).
(a)
Forward
(b)
Backward(1) Initialization:(8)α1(i)≜Pr(O1,q1=Si∣λ)=Pr(O1∣q1=Si,λ)Pr(q1=Si∣λ)=πibi(O1).(2) Recursion:(9)αt+1(j)≜Pr(O1,…Ot+1,qt+1=Sj∣λ)=[∑i=1Nαt(i)aij]bj(Ot+1).Proof
(10)
α
t
+
1
(
j
)
≜
Pr
(
O
1
,
…
,
O
t
+
1
,
q
t
+
1
=
S
j
∣
λ
)
=
Pr
(
O
1
,
…
,
O
t
+
1
∣
q
t
+
1
=
S
j
,
λ
)
Pr
(
q
t
+
1
=
S
j
∣
λ
)
=
Pr
(
O
1
,
…
,
O
t
∣
q
t
+
1
=
S
j
,
λ
)
·
Pr
(
O
t
+
1
∣
q
t
+
1
=
S
j
,
λ
)
Pr
(
q
t
+
1
=
S
j
∣
λ
)
=
Pr
(
O
1
,
…
,
O
t
,
q
t
+
1
=
S
j
∣
λ
)
·
Pr
(
O
t
+
1
∣
q
t
+
1
=
S
j
,
λ
)
=
Pr
(
O
t
+
1
∣
q
t
+
1
=
S
j
,
λ
)
·
∑
i
=
1
N
Pr
(
O
1
,
…
,
O
t
,
q
t
=
S
i
,
q
t
+
1
=
S
j
∣
λ
)
=
Pr
(
O
t
+
1
∣
q
t
+
1
=
S
j
,
λ
)
·
∑
i
=
1
N
Pr
(
O
1
,
…
,
O
t
,
q
t
+
1
=
S
j
∣
q
t
=
S
i
,
λ
)
·
Pr
(
q
t
=
S
i
∣
λ
)
=
Pr
(
O
t
+
1
∣
q
t
+
1
=
S
j
,
λ
)
·
∑
i
=
1
N
Pr
(
O
1
,
…
,
O
t
,
q
t
=
S
i
∣
λ
)
·
Pr
(
q
t
+
1
=
S
j
∣
q
t
=
S
i
,
λ
)
=
[
∑
i
=
1
N
α
t
(
i
)
a
i
j
]
b
j
(
O
t
+
1
)
.(3) End:(11)Pr(O∣λ)=∑i=1NPr(O,qT=Si∣λ)=∑i=1NαT(i).
Similarly, we define a backward variable
(12)βt(i)≜Pr(Ot+1,…,OT∣qt=Si,λ).
The three stages of its recursion are shown in Figure 4(b) and described as follows.(1) Initialization:(13)βT(i)=1.(2) Recursion:(14)βt(i)≜Pr(Ot+1,…,OT∣qt=Si,λ)=∑j=1Naijbj(Ot+1)βt+1(j).Proof
(15)
β
t
(
i
)
≜
Pr
(
O
t
+
1
,
…
,
O
T
∣
q
t
=
S
i
,
λ
)
=
∑
j
=
1
N
Pr
(
O
t
+
1
,
…
,
O
T
,
q
t
+
1
=
S
j
∣
q
t
=
S
i
,
λ
)
=
∑
j
=
1
N
Pr
(
O
t
+
1
,
…
,
O
T
∣
q
t
+
1
=
S
j
,
q
t
=
S
i
,
λ
)
·
Pr
(
q
t
+
1
=
S
j
∣
q
t
=
S
i
,
λ
)
=
∑
j
=
1
N
Pr
(
O
t
+
1
∣
q
t
+
1
=
S
j
,
q
t
=
S
i
,
λ
)
·
Pr
(
O
t
+
2
,
…
,
O
T
∣
q
t
+
1
=
S
j
,
q
t
=
S
i
,
λ
)
·
Pr
(
q
t
+
1
=
S
j
∣
q
t
=
S
i
,
λ
)
=
∑
j
=
1
N
Pr
(
O
t
+
1
∣
q
t
+
1
=
S
j
,
λ
)
·
Pr
(
O
t
+
2
,
…
,
O
T
∣
q
t
+
1
=
S
j
,
λ
)
·
Pr
(
q
t
+
1
=
S
j
∣
q
t
=
S
i
,
λ
)
=
∑
j
=
1
N
a
i
j
b
j
(
O
t
+
1
)
β
t
+
1
(
j
)
.(3) End:(16)Pr(O∣λ)=∑i=1Nβ1(i).
From these forward and backward variables, we have
(17)Pr(O∣λ)=∑i=1N∑j=1Nαt(i)aijbj(Ot+1)βt+1(j),1≤t≤T-1.We therefore obtainλ*=argmaxλPr(O∣λ), which is a functional extremum problem. Because the length of the training sequence is limited, there is no optimal method for estimating λ. Therefore, recursion is used to achieve a maximum local value for Pr(O∣λ), thereby obtaining the model parameter set λ=(A,B,Π).We defineξt(i,j) as the probability of being in Si at time t and in Sj at time t+1, given the whole observation sequence O and the model parameter set λ. Then
(18)ξt(i,j)≜Pr(qt=Si,qt+1=Sj∣O,λ)=αt(i)bj(Ot+1)βt+1(j)aij∑k=1N∑l=1Nαt(k)aklbl(Ot+1)βt+1(l).Proof
(19)
ξ
t
(
i
,
j
)
≜
Pr
(
q
t
=
S
i
,
q
t
+
1
=
S
j
∣
O
,
λ
)
=
Pr
(
O
∣
q
t
=
S
i
,
q
t
+
1
=
S
j
,
λ
)
·
Pr
(
q
t
=
S
i
,
q
t
+
1
=
S
j
∣
λ
)
Pr
(
O
∣
λ
)
=
Pr
(
O
∣
q
t
=
S
i
,
q
t
+
1
=
S
j
,
λ
)
·
Pr
(
q
t
+
1
=
S
j
∣
q
t
=
S
i
,
λ
)
·
Pr
(
q
t
∣
λ
)
Pr
(
O
∣
λ
)
=
Pr
(
O
1
,
…
,
O
t
∣
q
t
=
S
i
,
λ
)
·
Pr
(
O
t
+
1
∣
q
t
+
1
=
S
j
,
λ
)
·
Pr
(
O
t
+
2
,
…
,
O
T
∣
q
t
+
1
=
S
j
,
λ
)
·
a
i
j
Pr
(
q
t
=
S
i
∣
λ
)
Pr
(
O
∣
λ
)
=
Pr
(
O
1
,
…
,
O
t
,
q
t
=
S
i
∣
λ
)
Pr
(
O
t
+
1
∣
q
t
+
1
=
S
j
,
λ
)
·
Pr
(
O
t
+
2
,
…
,
O
T
∣
q
t
+
1
=
S
j
,
λ
)
a
i
j
Pr
(
O
∣
λ
)
=
α
t
(
i
)
b
j
(
O
t
+
1
)
β
t
+
1
(
j
)
a
i
j
Pr
(
O
∣
λ
)
=
α
t
(
i
)
b
j
(
O
t
+
1
)
β
t
+
1
(
j
)
a
i
j
∑
k
=
1
N
∑
l
=
1
N
Pr
(
q
t
=
S
k
,
q
t
+
1
=
S
l
,
O
∣
λ
)
=
α
t
(
i
)
b
j
(
O
t
+
1
)
β
t
+
1
(
j
)
a
i
j
∑
k
=
1
N
∑
l
=
1
N
α
t
(
k
)
a
k
l
b
l
(
O
t
+
1
)
β
t
+
1
(
l
)
.
Thus, the probability of being insi at time t is therefore given by
(20)γt(i)=Pr(O,qt=Si∣λ)=∑j=1Nξt(i,j),
where ∑t=1T-1ξt(i,j) denotes the mathematical expectation of transition from state Si. Therefore, the probability of transition from Si to Sj is given by
(21)a^ij=∑t=1T-1ξt(i,j)∑t=1T-1γt(i).
In state Sj, the probability of observing vm is given by
(22)b^j(m)=∑t=1Tγt(j)1(Ot=vm)∑t=1Tγt(j).
We therefore obtain a new modelλ^=(A^,B^,Π^), where A^=[a^ij], B^=[bj(m)], Π^=[π^i], and π^i=γ1(i). We can prove Pr(O∣λ^)≥Pr(O∣λ). The training process is repeated, and the model parameters are adjusted gradually until Pr(O∣λ^) converges. Finally, we obtain the prediction model λ^, which is used to assess the QoS-satisfied capability for compositions of cloud-service components.


## 4. Stimulation Experiment and Analysis

To check the feasibility of the proposed QoS-satisfied prediction model, we constructed a simulation experiment based on a cloud-computing experimental platform at our university. The simulation system included more than 100 cloud-service components, such as adaptable components and servers, and the open-source Eucalyptus system was adopted.Using our simulation system, we designed three cloud storage services whose QoS were different to check the prediction model. First, we trained the prediction model by adjusting the model parameters gradually, using a machine learning algorithm based on a support vector machine (SVM). In the SVM, the penalty factorc, the kernel function parameter g, and the boundary range p were set to 1024, 1024, and 0.0097, respectively. After obtaining the model parameter set λ, we achieved the prediction model λ^. We then made predictions for the three cloud storage services by using the prediction model and acquiring their simulated results. The simulation experiment was run 10 times to produce average results. The QoS-satisfied capabilities for the prediction values and observation values of the three cloud storage services (A, B, and C) are shown in Figures 5 and 6, respectively. The comparison between actual and observed values for service B is shown in Table 1, where the selected observation times from 74 onwards show the acquisition of a stable observed effect.Table 1
Comparison of prediction results.
Time
Actual value
Observation value
Error (%)
74
19.4
19.3995
0.003
76
18.7
18.7011
0.006
78
20
19.9994
0.003
80
19
19.001
0.005
82
20
19.9993
0.004
84
19.2
19.2008
0.004
86
19.9
19.8991
0.005
88
18.5
18.5011
0.006
90
19.5
19.4991
0.005
92
19.4
19.3986
0.007
94
20
19.999
0.005
96
19.5
19.4993
0.004
98
20
19.9991
0.005
100
19.3
19.2987
0.007Figure 5
Prediction values.Figure 6
Observation values.Note that the error is small (no more than 0.01%). This is because there is a stable network environment, without any other factors’ effects in our simulated system. In reality, a larger error would be expected. However, it should be able to satisfy the user’s QoS requirements in most cases.


## 5. Conclusions

Cloud computing refers to the use of shared computing resources and is an alternative to having local servers handle user applications. A match between cloud-service components and users’ QoS is therefore very important if user experience is the basis for promoting the development of cloud computing. If no single cloud service satisfies the user’s QoS perfectly, a composition of multiple cloud-service components should be considered, which should also include predicting the QoS satisfaction of the composite service. This paper presents a QoS-satisfied prediction model based on an HMM to assess the QoS-satisfied capability for compositions of components. We discuss the proposed model in detail and prove aspects of the model. Simulation results show that our model can achieve high prediction accuracies. In future work, we will introduce heterogeneous cloud services into the system and develop the prediction model to make it a better fit with real applications.



---

*Source: 387083-2013-07-31.xml*