# A Two-Phase Cloud Resource Provisioning Algorithm for Cost Optimization

Authors: Junjie Chen; Hongjun Li
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Cloud computing is a new computing paradigm to deliver computing resources as services over the Internet. Under such a paradigm, cloud users can rent computing resources from cloud providers to provide their services. The goal of cloud users is to minimize the resource rental cost while meeting the service requirements. In reality, cloud providers often offer multiple pricing models for virtual machine (VM) instances, including on-demand and reserved pricing models. Moreover, the workload of cloud users varies with time and is not known a priori. Therefore, it is challenging for cloud users to determine the optimal cloud resource provisioning. In this paper, we propose a two-phase cloud resource provisioning algorithm. In the first phase, we formulate the resource reservation problem as a two-stage stochastic programming problem, and solve it by the sample average approximation method and the dual decomposition method. In the second phase, we propose a hybrid ARIMA-Kalman model to predict the workload, and determine the number of on-demand instances based on the predicted workload. The effectiveness of the proposed two-phase algorithm is evaluated using a real-world workload trace and Amazon EC2’s pricing models. The simulation results show that the proposed algorithm can significantly reduce the operational cost while guaranteeing the service level agreement (SLA).


---

## Body

## 1. Introduction

Cloud computing [1] is a new computing paradigm to deliver computing resources as services over the Internet. These services are provided at three different levels: Infrastructure as a Service (IaaS) [2], Platform as a Service (PaaS) [3], and Software as a Service (SaaS) [4]. In this paper, we focus on IaaS. IaaS providers such as Amazon EC2 [5] and Microsoft Azure [6] provide their computing resources to cloud users in the form of VMs. Cloud users can rent VMs from cloud providers on a pay-per-use basis.Cloud providers usually have different billing cycles and offer different pricing models. Take Amazon EC2 as an example. Amazon EC2 has two billing cycles: per hour billing and per second billing. In this paper, we adopt per hour billing. Amazon EC2 offers three pricing models: (1)On-demand pricing model. On-demand instances let users pay for compute capacity by the hour with no long-term commitments. (2) Reserved pricing model. Users pay an upfront fee (all upfront, partial upfront, and no upfront) to reserve an instance for a 1-year or 3-year term and is then charged a discounted hourly rate for the instance during the reservation period. (3) Spot pricing model. Spot instances allow users to bid on unused EC2 instances and run those instances for as long as their bid exceeds the spot price. Spot instances are charged the spot price which is set by Amazon EC2 and adjusted gradually based on the supply and demand for spot instances. Such diverse pricing models make it challenging for cloud users to determine the optimal cloud resource provisioning.There have been a lot of studies on cloud resource provisioning, which aim to minimize the resource provisioning cost while satisfying the service requirements. However, most existing studies [7–11] do not consider the pricing models or only consider the on-demand pricing model. Some recent studies [12–16] consider both on-demand and reserved pricing models to reduce the resource provisioning cost. These studies typically use reserved instances to meet the minimum service requirements and use on-demand instances to meet the sudden workload demand.In this paper, we study the cloud resource provisioning problem. To reduce the resource rental cost, we use both on-demand and reserved instances and propose a two-phase cloud resource provisioning algorithm. In the resource reservation phase, we determine the optimal number of reserved instances to minimize the resource rental cost. In the on-demand resource provisioning phase, on-demand instances are purchased based on the predicted workload to guarantee the SLA. The main contributions of this paper are summarized as follows:(i)
We use both on-demand and reserved instances for cloud resource provisioning and propose a two-phase cloud resource provisioning algorithm to reduce the resource rental cost.(ii)
In the first phase, we formulate the resource reservation problem as a two-stage stochastic programming problem, and solve it by the sample average approximation method and the dual decomposition method.(iii)
In the second phase, we propose a hybrid ARIMA-Kalman model for workload prediction and determine the number of on-demand instances based on the predicted workload.(iv)
We conduct extensive experiments to evaluate the effectiveness of the proposed two-phase algorithm using a real-world workload trace and Amazon EC2’s pricing models. The experimental results show that the proposed algorithm can significantly reduce the operational cost while guaranteeing the SLA.The rest of this paper is organized as follows. Related works are reviewed in Section2. The problem formulation is given in Section 3. The two-phase cloud resource provisioning algorithm is presented in Section 4 and Section 5. Experimental results are presented in Section 6. Finally, we conclude this paper in Section 7.


## 2. Related Work

In cloud computing, cloud users can reduce the cost and guarantee the QoS requirements through adaptive resource provisioning. Adaptive resource provisioning has been widely studied [7–11]. In [7], the autoscaling techniques were classified into five categories: static threshold-based rules, reinforcement learning, queuing theory, control theory, and time series analysis. Calheiros et al. [8] proposed a workload prediction model using the ARIMA model and evaluated its impact on cloud applications’ QoS. Islam et al. [9] developed prediction-based resource measurement and provisioning strategies using neural network and linear regression to satisfy upcoming resource demands. To train the neural network, Shah et al. [17] presented a quick Gbest-guided artificial bee colony learning algorithm. Chen et al. [10] proposed an iterative QoS prediction model and a PSO-based runtime decision algorithm to derive a self-adaptive approach for resource allocation in cloud-based software services. Liu et al. [11] presented SPRNT, a reinforcement learning-based aggressive virtualized resource management system for IaaS clouds.The above works mainly focus on adaptive resource provisioning. However, cloud providers usually offer multiple pricing models: on-demand, reserved, and spot. Cloud users can significantly reduce the cost based on these pricing models. Chaisiri et al. [12] proposed an optimal cloud resource provisioning algorithm by formulating a stochastic programming model in which the demand and price uncertainty is considered. In [13], a two-phase resource provisioning algorithm was presented. In the first phase, the optimal amount of long-term reserved resources was computed by a mathematical formulae. In the second phase, the authors used the Kalman filter to predict resource demand and adaptively changed the subscribed on-demand resources. Niu et al. [14] proposed a semielastic cluster computing model for organizations to reserve and dynamically resize a virtual cloud-based cluster. In [15], a dynamic instance provisioning strategy based on the large deviation principle was proposed to minimize the number of active instances subject to a QoS requirement in terms of the overload probability. Mireslami et al. [16] proposed a two-phase cloud resource allocation algorithm. In the first phase, reserved resources were allocated to meet the minimum QoS requirements. In the second phase, a stochastic optimization approach was proposed to allocate on-demand resources under demand uncertainty.In this paper, the cloud resource provisioning problem is formulated as a two-stage stochastic programming problem. It can be transformed into a deterministic integer program and solved by exact methods such as branch and bound and cutting plane methods, or heuristic methods such as genetic algorithm, particle swarm optimization, and hybrid algorithms [18–20]. Grey [18] presented a hybrid PSO-GA algorithm for solving the various constrained optimization problems. In this approach, PSO is used to explore the solution while GA is being used for updating the solution.


## 3. Problem Formulation

In this section, we present the model assumptions, including the VM configurations and the pricing models. Based on these assumptions, we present the formulation of the cloud resource provisioning problem. The notations used in this paper are listed in Table1.Table 1
The key notations.
NotationDescriptionVSet of VM types offered by cloud providers,V=V1,V2,…,VMCiProcessing capacity of a VM instance of typeVipioUsage fee of an on-demand instance of typeVi per hourpiRUpfront payment of a reserved instance of typeVipirUsage fee of a reserved instance of typeVi per hourTNumber of hours in a reservation periodtHour index of the reservation period,t=1,2,…,TRReservation decision,R=n1r,n2r,…,nMrnirNumber of reserved instances of typeVintioNumber of on-demand instances of typeVi at time tUR,dtUsage cost of on-demand instances at timetpDdProbability distribution of the workload


### 3.1. Cloud Computing Environment

Cloud providers offer multiple types of VMs to cloud users. LetV=V1,V2,…,VM denote the set of VM types, whereM is the total number of VM types. Each VM type has its own resource configuration and processing capacity. Let Ci denote the processing capacity of a VM instance of type Vi, which is the maximum number of concurrent users or the maximum service request rate that can be handled by a VM instance of type Vi without violating the QoS requirements.We adopt per hour billing and consider two pricing models: on-demand instance and reserved instances (1-year term, partial upfront). Letpio denote the hourly usage fee of an on-demand instance of type Vi. Let piR and pir denote the one-time upfront payment and the hourly usage fee of a reserved instance of type Vi, respectively. Let T be the number of hours in a reservation period. Then, the effective hourly price of a reserved instance of type Vi can be computed as piR/T+pir, which is charged for every hour during the reservation period. It is usually assumed that piR/T+pir<pio.


### 3.2. Cloud Resource Provisioning Problem

We consider the cloud resource provisioning problem over a reservation period. Lett=1,2,…,T be the hour index of the reservation period. Let dt be the workload at time t. Let R=n1r,n2r,…,nMr be the reservation decision and nir be the number of reserved instances of type Vi. Then, the reserved processing capacity is ∑i=1MnirCi, and the total cost of reserved instances for the reservation period is ∑i=1MnirpiR+pirT. For each time t, if the workload does not exceed the reserved processing capacity, there will be no need to purchase on-demand instances; otherwise, on-demand instances will be purchased, and the usage cost of on-demand instances can be written as(1)UR,dt=min∑i=1Mntiopio,s.t.∑i=1MntioCi+∑i=1MnirCi≥dt,ntio∈ℕ0,i∈1,2,…,M,where ntio is the number of on-demand instances of type Vi at time t.The resource reservation problem can be formulated as(2)min∑i=1MnirpiR+pirT+∑t=1TUR,dt,s.t.nir∈ℕ0,i∈1,2,…,M,where the objective is to minimize the total cost for the reservation period, including the upfront fee and the usage cost of reserved instances, and the usage cost of on-demand instances. This problem depends on the workload over the reservation period, which is not known a priori. We can estimate the probability distribution of the workload pDd based on historical data. Then, the resource reservation problem can be rewritten as(3)min∑i=1MnirpiRT+pir+∑dpDdUR,d,s.t.nir∈ℕ0,i∈1,2,…,M.This problem is a two-stage stochastic programming problem, where the objective function is the average cost per hour, and the possible realizations of the workload are called scenarios. The first-stage problem corresponds to the resource reservation problem, where the first-stage decision is the reservation decision. The second-stage problem corresponds to the on-demand resource provisioning problem, where the second-stage decision depends on the realization of the workload.


## 3.1. Cloud Computing Environment

Cloud providers offer multiple types of VMs to cloud users. LetV=V1,V2,…,VM denote the set of VM types, whereM is the total number of VM types. Each VM type has its own resource configuration and processing capacity. Let Ci denote the processing capacity of a VM instance of type Vi, which is the maximum number of concurrent users or the maximum service request rate that can be handled by a VM instance of type Vi without violating the QoS requirements.We adopt per hour billing and consider two pricing models: on-demand instance and reserved instances (1-year term, partial upfront). Letpio denote the hourly usage fee of an on-demand instance of type Vi. Let piR and pir denote the one-time upfront payment and the hourly usage fee of a reserved instance of type Vi, respectively. Let T be the number of hours in a reservation period. Then, the effective hourly price of a reserved instance of type Vi can be computed as piR/T+pir, which is charged for every hour during the reservation period. It is usually assumed that piR/T+pir<pio.


## 3.2. Cloud Resource Provisioning Problem

We consider the cloud resource provisioning problem over a reservation period. Lett=1,2,…,T be the hour index of the reservation period. Let dt be the workload at time t. Let R=n1r,n2r,…,nMr be the reservation decision and nir be the number of reserved instances of type Vi. Then, the reserved processing capacity is ∑i=1MnirCi, and the total cost of reserved instances for the reservation period is ∑i=1MnirpiR+pirT. For each time t, if the workload does not exceed the reserved processing capacity, there will be no need to purchase on-demand instances; otherwise, on-demand instances will be purchased, and the usage cost of on-demand instances can be written as(1)UR,dt=min∑i=1Mntiopio,s.t.∑i=1MntioCi+∑i=1MnirCi≥dt,ntio∈ℕ0,i∈1,2,…,M,where ntio is the number of on-demand instances of type Vi at time t.The resource reservation problem can be formulated as(2)min∑i=1MnirpiR+pirT+∑t=1TUR,dt,s.t.nir∈ℕ0,i∈1,2,…,M,where the objective is to minimize the total cost for the reservation period, including the upfront fee and the usage cost of reserved instances, and the usage cost of on-demand instances. This problem depends on the workload over the reservation period, which is not known a priori. We can estimate the probability distribution of the workload pDd based on historical data. Then, the resource reservation problem can be rewritten as(3)min∑i=1MnirpiRT+pir+∑dpDdUR,d,s.t.nir∈ℕ0,i∈1,2,…,M.This problem is a two-stage stochastic programming problem, where the objective function is the average cost per hour, and the possible realizations of the workload are called scenarios. The first-stage problem corresponds to the resource reservation problem, where the first-stage decision is the reservation decision. The second-stage problem corresponds to the on-demand resource provisioning problem, where the second-stage decision depends on the realization of the workload.


## 4. Resource Reservation

In this section, we use the sample average approximation method and the dual decomposition method to solve the resource reservation problem.


### 4.1. Sample Average Approximation (SAA)

If the number of scenarios is very large, it is difficult to solve (3) directly. The sample average approximation method can be used to reduce the number of scenarios [21]. Since the workload is a one-dimensional random variable, a uniform discretization grid is used to generate a set of scenarios d˜1,d˜2,…,d˜N, where N is the sample size. Then, problem (3) can be approximated as(4)min∑i=1MnirpiRT+pir+1N∑j=1NUR,d˜j,s.t.nir∈ℕ0,i∈1,2,…,M.Problem (4) is the SAA of problem (3). Problem (4) is also a two-stage stochastic programming problem, which can be transformed into the following deterministic equivalent formulation:(5)min∑i=1MnirpiRT+pir+1N∑j=1N∑i=1Mnjiopio,s.t.∑i=1MnirCi+∑i=1MnjioCi≥d˜j,j∈1,2,…,N,nir∈ℕ0,i∈1,2,…,N,njio∈ℕ0,j∈1,2,…,N,i∈1,2,…,M.Problem (5) is an integer linear program, which can be solved using a standard branch and bound algorithm.


### 4.2. Dual Decomposition-Based Branch and Bound (DDBnB)

The standard branch and bound algorithm uses the linear programming relaxation for bounding. In this paper, we use the Lagrangian relaxation obtained by scenario decomposition to improve the bounds [22].The idea of scenario decomposition is to introduce a copyRj of the first-stage decision R for each scenario. Then, problem (5) can be reformulated as(6)min∑j=1N1N∑i=1MnjirpiRT+pir+∑i=1Mnjiopio,s.t.∑i=1MnjirCi+∑i=1MnjioCi≥d˜j,j∈1,2,…,N,njir,njio∈ℕ0,j∈1,2,…,N,i∈1,2,…,M,R1=R2=⋯=RN,where the constraints R1=⋯=RN are called the nonanticipativity constraints. The nonanticipativity constraints have several equivalent expressions. Here, we represent the nonanticipativity constraints by ∑j=1NHjRj=0, where Hj is a suitable MN−1×M matrix. By dualizing the nonanticipativity constraints, the Lagrange dual function of problem (6) is defined as(7)Dλ=min∑j=1N1N∑i=1MnjirpiRT+pir+∑i=1Mnjiopio+λT∑j=1NHjRj,s.t.∑i=1MnjirCi+∑i=1MnjioCi≥d˜j,j∈1,2,…,N,njir,njio∈ℕ0,j∈1,2,…,N,i∈1,2,…,M,where λ∈ℝMN−1 is the Lagrange multiplier vector associated with the nonanticipativity constraints. Problem (7) can be decomposed into multiple subproblems according to the scenarios:(8)Djλ=min1N∑i=1MnjirpiRT+pir+∑i=1Mnjiopio+λTHjRj,s.t.∑i=1MnjirCi+∑i=1MnjioCi≥d˜jnjir,njio∈ℕ0,i∈1,2,…,M.Problem (8) is called the scenario subproblem, which is a small integer linear program. The dual problem of problem (6) can be formulated as(9)zLD=maxλ∈ℝMN−1Dλ=∑j=1NDjλ.Dual problem (9) can be solved by the subgradient method. From the definition of the subgradient, the subgradient of Dλ is ∑j=1NHjRjλ, where Rjλ is the first-stage component of the optimal solution of (8) for a given λ. The iterative formula of the subgradient method is as follows:(10)λk+1=λk+γk∑j=1NHjRjλk,where k is the iteration index and γk is a positive step size.Dual problem (9) provides a lower bound for original problem (6). In general, the scenario solutions Rj,j=1,2,…,N will not satisfy the nonanticipativity constraints unless the duality gap is zero. In this paper, we present a branch and bound algorithm that uses the Lagrangian relaxation of the nonanticipativity constraints for bounding. To obtain a feasible first-stage solution, we compute the average R¯=∑i=1NRj/N and round it by some heuristic to obtain an integer solution. The feasible first-stage solution provides an upper bound for problem (6). The branch and bound algorithm is described as follows, where P denotes the set of current problems and zP is a lower bound ofP∈P:Step 1. Initialization: set z¯=+∞ and let P consist of problem (6).Step 2. Termination: if P=∅, then the solution that yielded z¯ is optimal.Step 3. Node selection: select and delete a problem P from P, and solve its Lagrangian dual.Step 4. Bounding: if zLDP≥z¯, go to Step 2 (this step can be carried out as soon as the value of the Lagrangian dual rises above z¯).(i)
The scenario solutionsRj,j=1,2,…,N, are identical: let z¯=zLDP and delete from P all problems P′ with zP′≥z¯. Go to Step 2.(ii)
The scenario solutionsRj,j=1,2,…,N, differ: compute the average R¯=∑i=1NRj/N and round it by some heuristic to obtain R^. If ∑i=1Mn^irpiR/T+pir+∑j=1NUR^,d˜j/N<z¯, then let z¯=∑i=1Mn^irpiR/T+pir+∑j=1NUR^,d˜j/N and delete from P all problems P′ with zP′≥z¯.Step 5. Branching: select a component nir of R and add two new problems to P obtained from P by adding the constraints nir≤⌊n¯ir⌋ and nir≥⌊n¯ir⌋+1, respectively. Go to Step 2.


## 4.1. Sample Average Approximation (SAA)

If the number of scenarios is very large, it is difficult to solve (3) directly. The sample average approximation method can be used to reduce the number of scenarios [21]. Since the workload is a one-dimensional random variable, a uniform discretization grid is used to generate a set of scenarios d˜1,d˜2,…,d˜N, where N is the sample size. Then, problem (3) can be approximated as(4)min∑i=1MnirpiRT+pir+1N∑j=1NUR,d˜j,s.t.nir∈ℕ0,i∈1,2,…,M.Problem (4) is the SAA of problem (3). Problem (4) is also a two-stage stochastic programming problem, which can be transformed into the following deterministic equivalent formulation:(5)min∑i=1MnirpiRT+pir+1N∑j=1N∑i=1Mnjiopio,s.t.∑i=1MnirCi+∑i=1MnjioCi≥d˜j,j∈1,2,…,N,nir∈ℕ0,i∈1,2,…,N,njio∈ℕ0,j∈1,2,…,N,i∈1,2,…,M.Problem (5) is an integer linear program, which can be solved using a standard branch and bound algorithm.


## 4.2. Dual Decomposition-Based Branch and Bound (DDBnB)

The standard branch and bound algorithm uses the linear programming relaxation for bounding. In this paper, we use the Lagrangian relaxation obtained by scenario decomposition to improve the bounds [22].The idea of scenario decomposition is to introduce a copyRj of the first-stage decision R for each scenario. Then, problem (5) can be reformulated as(6)min∑j=1N1N∑i=1MnjirpiRT+pir+∑i=1Mnjiopio,s.t.∑i=1MnjirCi+∑i=1MnjioCi≥d˜j,j∈1,2,…,N,njir,njio∈ℕ0,j∈1,2,…,N,i∈1,2,…,M,R1=R2=⋯=RN,where the constraints R1=⋯=RN are called the nonanticipativity constraints. The nonanticipativity constraints have several equivalent expressions. Here, we represent the nonanticipativity constraints by ∑j=1NHjRj=0, where Hj is a suitable MN−1×M matrix. By dualizing the nonanticipativity constraints, the Lagrange dual function of problem (6) is defined as(7)Dλ=min∑j=1N1N∑i=1MnjirpiRT+pir+∑i=1Mnjiopio+λT∑j=1NHjRj,s.t.∑i=1MnjirCi+∑i=1MnjioCi≥d˜j,j∈1,2,…,N,njir,njio∈ℕ0,j∈1,2,…,N,i∈1,2,…,M,where λ∈ℝMN−1 is the Lagrange multiplier vector associated with the nonanticipativity constraints. Problem (7) can be decomposed into multiple subproblems according to the scenarios:(8)Djλ=min1N∑i=1MnjirpiRT+pir+∑i=1Mnjiopio+λTHjRj,s.t.∑i=1MnjirCi+∑i=1MnjioCi≥d˜jnjir,njio∈ℕ0,i∈1,2,…,M.Problem (8) is called the scenario subproblem, which is a small integer linear program. The dual problem of problem (6) can be formulated as(9)zLD=maxλ∈ℝMN−1Dλ=∑j=1NDjλ.Dual problem (9) can be solved by the subgradient method. From the definition of the subgradient, the subgradient of Dλ is ∑j=1NHjRjλ, where Rjλ is the first-stage component of the optimal solution of (8) for a given λ. The iterative formula of the subgradient method is as follows:(10)λk+1=λk+γk∑j=1NHjRjλk,where k is the iteration index and γk is a positive step size.Dual problem (9) provides a lower bound for original problem (6). In general, the scenario solutions Rj,j=1,2,…,N will not satisfy the nonanticipativity constraints unless the duality gap is zero. In this paper, we present a branch and bound algorithm that uses the Lagrangian relaxation of the nonanticipativity constraints for bounding. To obtain a feasible first-stage solution, we compute the average R¯=∑i=1NRj/N and round it by some heuristic to obtain an integer solution. The feasible first-stage solution provides an upper bound for problem (6). The branch and bound algorithm is described as follows, where P denotes the set of current problems and zP is a lower bound ofP∈P:Step 1. Initialization: set z¯=+∞ and let P consist of problem (6).Step 2. Termination: if P=∅, then the solution that yielded z¯ is optimal.Step 3. Node selection: select and delete a problem P from P, and solve its Lagrangian dual.Step 4. Bounding: if zLDP≥z¯, go to Step 2 (this step can be carried out as soon as the value of the Lagrangian dual rises above z¯).(i)
The scenario solutionsRj,j=1,2,…,N, are identical: let z¯=zLDP and delete from P all problems P′ with zP′≥z¯. Go to Step 2.(ii)
The scenario solutionsRj,j=1,2,…,N, differ: compute the average R¯=∑i=1NRj/N and round it by some heuristic to obtain R^. If ∑i=1Mn^irpiR/T+pir+∑j=1NUR^,d˜j/N<z¯, then let z¯=∑i=1Mn^irpiR/T+pir+∑j=1NUR^,d˜j/N and delete from P all problems P′ with zP′≥z¯.Step 5. Branching: select a component nir of R and add two new problems to P obtained from P by adding the constraints nir≤⌊n¯ir⌋ and nir≥⌊n¯ir⌋+1, respectively. Go to Step 2.


## 5. On-Demand Resource Provisioning

On-demand resource provisioning problem (1) is an integer linear program, which can be solved using any standard integer linear programming solver. However, the workload is not known a priori. In this paper, we propose a hybrid ARIMA-Kalman model for workload prediction.It has been shown in the literature that the workload exhibits strong autocorrelation. Then, the workload can be modeled by an ARIMA model [8, 23]:(11)d¯t=ϕ1d¯t−1+ϕ2d¯t−2+⋯+ϕpd¯t−p+εt+θ1εt−1+⋯+θqεt−q,where d¯t=∇ddt, εt∼WN0,σ2, Φ=ϕ1,…,ϕp are the AR coefficients, and Θ=θ1,…,θq are the MA coefficients. Let r=maxp,q+1, and model (11) can be rewritten as(12)d¯t=ϕ1d¯t−1+ϕ2d¯t−2+⋯+ϕrd¯t−r+εt+θ1εt−1+⋯+θr−1εt−r+1,where ϕi=0 for i>p and θj=0 for j>q. Then, the state-space representation of model (12) can be obtained as [24](13)d¯t=Gxt+Wt,(14)xt=Fxt−1+Vt,where (13) and (14) are the measurement and state equations, d¯t is the measurement variable, xt∈ℝr is the state vector, Wt=0 is the measurement noise with variance R=0, and Vt=εt,0,…,0T is the state noise with covariance matrix Q=diagσ2,0,…,0. The measurement matrix G and the state transition matrix F are given as(15)G=1,θ1,…,θr−1,F=ϕ1ϕ2⋯ϕr−1ϕr10⋯0001⋯00⋮⋮⋱⋮⋮00⋯10.From state-space models (13) and (14), the Kalman prediction equations is obtained as follows [25]:(16)xt/t−1=Fxt−1/t−1,Pt/t−1=FPt−1/t−1FT+Q,d¯t/t−1=Gxt/t−1,Zt/t−1=GPt/t−1GT,(17)xt/t=xt/t−1+Ktd¯t−Gxt/t−1,Pt/t=I−KtGPt/t−1,Kt=Pt/t−1GTGPt/t−1GT−1,where (16) and (17) are the time and measurement update equations, xt/s and d¯t/s are the estimates of xt and d¯t given the observations up to time s, Pt/s is the error covariance matrix of xt/s, Zt/s is the error variance of d¯t/s, and Kt is the Kalman gain.Letψ=x0/0,P0/0,Φ,Θ,σ2 denote the set of parameters in the Kalman prediction equations, which can be estimated by the maximum likelihood method. In this paper, we use the EM algorithm [26] to obtain the maximum likelihood estimates of the parameters. If we could observe the states Xn=x0,x1,…,xn in addition to the observations Dn=d¯1,d¯2,…,d¯n, then we would consider Xn,Dn as the complete data. Under the Gaussian assumption, the log-likelihood of the complete data can be written as(18)lnLDn,Xn;ψ=−12lnP0/0−12x0−x0/0TP0/0−1x0−x0/0n2lnQ−12∑t=1nxt−Fxt−1TQ−1xt−Fxt−1−n2lnR−12∑t=1nd¯t−Gxt2R−1.From (18), if we did have the complete data, it will be straight forward to obtain the maximum likelihood estimate of ψ using multivariate normal theory. However, we cannot observe the states. The EM algorithm is an iterative method for finding the maximum likelihood estimate of ψ based on the incomplete data by successively maximizing the conditional expectation of the complete data log-likelihood. Each iteration of the EM algorithm consists of two steps, the expectation step (E-step) and the maximization step (M-step). In the E-step, the conditional expectation of the complete data log-likelihood is computed given the parameter estimates from the previous iteration:(19)Qψψj−1=ElnLDn,Xn;ψDn,ψj−1.From (18), we can obtain(20)Qψψj−1=−12lnP0/0−12trP0/0−1P0/n+x0/n−x0/0x0/n−x0/0Tn2lnQ−12trQ−1S11−S10FT−FS10T+FS00FT−n2lnR−12R−1∑t=1nd¯t−Gxt/n2+GPt/nGT,where(21)S11=∑t=1nxt/nxt/nT+Pt/n,S10=∑t=1nxt/nxt−1/nT+Pt,t−1/n,S00=∑t=1nxt−1/nxt−1/nT+Pt−1/n.Pt,t−1/n is the error covariance of xt−1/n and xt/n. In the M-step, (20) is maximized with respect to the parameters and then the updated parameter estimates are obtained as(22)ϕij=S10S00−11i,i=1,…,p,σ2f=n−1S11−S10S00−1S10T11,θij=∑t=1nd¯txt/nTS11−1i+1,i=1,…,qx0/0j=x0/n,P0/0j=P0/n.The flowchart of the EM algorithm is shown in Figure1.Figure 1
The EM algorithm.The one-step-ahead prediction of the workload based on Kalman prediction is given by(23)dt=−∑j=1ddj−1jdt−j+Gxt/t−1.For each timet, even with a workload prediction method, the underprovisioning problem can occur due to underestimation, which causes the SLA violation. To reduce the SLA violation rate, (23) can be modified as(24)dt=−∑j=1ddj−1jdt−j+Gxt/t−1+α⋅GPt/t−1GT,α>0.


## 6. Evaluation

In this section, we conduct extensive experiments to evaluate the effectiveness of the proposed two-phase algorithm based on a real-world workload trace and Amazon EC2’s pricing models.


### 6.1. Experiment Setup

The workload trace used in the experiments is obtained from a 4-week access log file of the NASA web server [27], as shown in Figure 2. The probability distribution of the workload can be estimated based on the workload trace. We consider four types of VM instances offered by Amazon EC2: small (m1.small), medium (m1.medium), large (m1.large), and extralarge (m1.xlarge) [5]. Table 2 shows the configuration and the pricing models of each VM type. The parameters of the algorithms are set as follows. The sample size of the SAA problem is set to 10. In the subgradient method, we use a diminishing step size γk=1+m/k+m where m=100, and repeat the iterations until the stopping criterion Dk−Dk−1Dk≤ε is satisfied where ε=0.00001. In the EM algorithm, the initial values of the parameters are set according to [25].Figure 2
The workload trace.Table 2
The configuration and the pricing models of each VM type.
VM typeResource configurationProcessing capacity (requests/s)Reserved instance (1 year, partial upfront)On-demand instance usage fee (per hour)Upfront paymentUsage fee (per hour)Small1 vCPU, 1.7GiB RAM, 160 GB disk20$123$0.010$0.044Medium1 vCPU, 3.75GiB RAM, 410 GB disk50$247$0.020$0.087Large2 vCPU, 7.5GiB RAM, 840 GB disk110$493$0.042$0.175Extralarge4 vCPU, 15GiB RAM, 1680 GB disk225$987$0.083$0.35


### 6.2. Performance of Resource Reservation Algorithm

We first analyze the impact of resource reservation on the operational cost. Figure3 shows the operational cost under different resource reservations. We can observe that the operational cost can be significantly reduced by resource reservation, and there is a tradeoff between the on-demand cost and the reservation cost. The optimal resource reservation is n1r=0,n2r=1,n3r=0,n4r=1 with the reserved processing capacity of 275 requests/s, and the optimal operational cost is $3407.9. By combining on-demand and reserved instances, the operational cost can be reduced by 25.58% compared with the pure on-demand strategy.Figure 3
Impact of resource reservation on the operational cost.We compare the accuracy of the uniform discretization grid with that of the Monte Carlo and quasi-Monte Carlo methods [21]. As can be seen from Figure 4(a), the uniform discretization grid is the best among the three methods under the same sample size. We also study the impact of the sample size on the accuracy of the uniform discretization grid. As can be seen from Figure 4(b), the accuracy of the uniform discretization grid becomes higher as the sample size increases, and reaches 98.01% when N=10.Figure 4
Performance of the SAA method. (a) Comparison of uniform discretization with Monte Carlo and quasi-Monte Carlo. (b) Impact of the sample size on the accuracy of uniform discretization.
(a)(b)Figure5 shows the convergence of the dual decomposition-based branch and bound algorithm. It can be seen that the optimal solution can be obtained by the DDBnB algorithm after 9 iterations. Table 3 compares the performance of our resource reservation algorithm based on stochastic programming (RRSP) with two existing algorithms: the RIPAM algorithm considering only medium instance type [15] and the DCRA algorithm [16]. The RRSP algorithm can reduce the operational cost by 24.92%. Our algorithm can achieve 4.14% more cost saving than RIPAM, and 20.84% more cost saving than DCRA.Figure 5
Convergence of the DDBnB algorithm.Table 3
Comparison of RRSP with two existing algorithms.
Operational cost ($/year)Cost saving (%)RRSP3438.524.92RIPAM [15]3628.120.78DCRA [16]4392.64.08


### 6.3. Workload Prediction Based on Hybrid ARIMA-Kalman Model

In this subsection, we evaluate the performance of the hybrid ARIMA-Kalman model. The data of the first three weeks are used as the training data and the data of the last week as the test data. Figure6 shows the prediction results. We can observe that the predicted workload is very close to the actual workload. The prediction accuracy of the hybrid ARIMA-Kalman model is compared with the ARIMA model [8] and the neural network method [9] based on three metrics, mean absolute percentage error (MAPE), root mean square error (RMSE), and mean absolute error (MAE). The ARIMA model has an autoregressive order of 2 and a moving average order of 1. The neural network method uses the backpropagation neural network, the learning rate is set to 0.7, there is only one hidden layer, and the numbers of neurons in the input, hidden, and output layers are 6, 4, and 1, respectively. As can be seen from Table 4, the hybrid ARIMA-Kalman model is better than the other two methods.Figure 6
Prediction results.Table 4
Comparison of prediction accuracy of the three prediction methods.
MAPERMSEMAEARIMA-Kalman0.141752.109842.9142ARIMA0.141852.110242.9359Neural network0.142652.822842.6461Although the predicted workload is very close to the actual workload, the underprovisioning problem can occur due to underestimation of the workload. To reduce the SLA violation rate, modified workload prediction formula (24) is used. Figure 7 shows the impact of the parameter α on the SLA violation rate and the on-demand cost. It can be seen that, as the value of α increases, the SLA violation rate decreases while the on-demand cost increases.Figure 7
Impact ofα on the SLA violation rate and the on-demand cost.


## 6.1. Experiment Setup

The workload trace used in the experiments is obtained from a 4-week access log file of the NASA web server [27], as shown in Figure 2. The probability distribution of the workload can be estimated based on the workload trace. We consider four types of VM instances offered by Amazon EC2: small (m1.small), medium (m1.medium), large (m1.large), and extralarge (m1.xlarge) [5]. Table 2 shows the configuration and the pricing models of each VM type. The parameters of the algorithms are set as follows. The sample size of the SAA problem is set to 10. In the subgradient method, we use a diminishing step size γk=1+m/k+m where m=100, and repeat the iterations until the stopping criterion Dk−Dk−1Dk≤ε is satisfied where ε=0.00001. In the EM algorithm, the initial values of the parameters are set according to [25].Figure 2
The workload trace.Table 2
The configuration and the pricing models of each VM type.
VM typeResource configurationProcessing capacity (requests/s)Reserved instance (1 year, partial upfront)On-demand instance usage fee (per hour)Upfront paymentUsage fee (per hour)Small1 vCPU, 1.7GiB RAM, 160 GB disk20$123$0.010$0.044Medium1 vCPU, 3.75GiB RAM, 410 GB disk50$247$0.020$0.087Large2 vCPU, 7.5GiB RAM, 840 GB disk110$493$0.042$0.175Extralarge4 vCPU, 15GiB RAM, 1680 GB disk225$987$0.083$0.35


## 6.2. Performance of Resource Reservation Algorithm

We first analyze the impact of resource reservation on the operational cost. Figure3 shows the operational cost under different resource reservations. We can observe that the operational cost can be significantly reduced by resource reservation, and there is a tradeoff between the on-demand cost and the reservation cost. The optimal resource reservation is n1r=0,n2r=1,n3r=0,n4r=1 with the reserved processing capacity of 275 requests/s, and the optimal operational cost is $3407.9. By combining on-demand and reserved instances, the operational cost can be reduced by 25.58% compared with the pure on-demand strategy.Figure 3
Impact of resource reservation on the operational cost.We compare the accuracy of the uniform discretization grid with that of the Monte Carlo and quasi-Monte Carlo methods [21]. As can be seen from Figure 4(a), the uniform discretization grid is the best among the three methods under the same sample size. We also study the impact of the sample size on the accuracy of the uniform discretization grid. As can be seen from Figure 4(b), the accuracy of the uniform discretization grid becomes higher as the sample size increases, and reaches 98.01% when N=10.Figure 4
Performance of the SAA method. (a) Comparison of uniform discretization with Monte Carlo and quasi-Monte Carlo. (b) Impact of the sample size on the accuracy of uniform discretization.
(a)(b)Figure5 shows the convergence of the dual decomposition-based branch and bound algorithm. It can be seen that the optimal solution can be obtained by the DDBnB algorithm after 9 iterations. Table 3 compares the performance of our resource reservation algorithm based on stochastic programming (RRSP) with two existing algorithms: the RIPAM algorithm considering only medium instance type [15] and the DCRA algorithm [16]. The RRSP algorithm can reduce the operational cost by 24.92%. Our algorithm can achieve 4.14% more cost saving than RIPAM, and 20.84% more cost saving than DCRA.Figure 5
Convergence of the DDBnB algorithm.Table 3
Comparison of RRSP with two existing algorithms.
Operational cost ($/year)Cost saving (%)RRSP3438.524.92RIPAM [15]3628.120.78DCRA [16]4392.64.08


## 6.3. Workload Prediction Based on Hybrid ARIMA-Kalman Model

In this subsection, we evaluate the performance of the hybrid ARIMA-Kalman model. The data of the first three weeks are used as the training data and the data of the last week as the test data. Figure6 shows the prediction results. We can observe that the predicted workload is very close to the actual workload. The prediction accuracy of the hybrid ARIMA-Kalman model is compared with the ARIMA model [8] and the neural network method [9] based on three metrics, mean absolute percentage error (MAPE), root mean square error (RMSE), and mean absolute error (MAE). The ARIMA model has an autoregressive order of 2 and a moving average order of 1. The neural network method uses the backpropagation neural network, the learning rate is set to 0.7, there is only one hidden layer, and the numbers of neurons in the input, hidden, and output layers are 6, 4, and 1, respectively. As can be seen from Table 4, the hybrid ARIMA-Kalman model is better than the other two methods.Figure 6
Prediction results.Table 4
Comparison of prediction accuracy of the three prediction methods.
MAPERMSEMAEARIMA-Kalman0.141752.109842.9142ARIMA0.141852.110242.9359Neural network0.142652.822842.6461Although the predicted workload is very close to the actual workload, the underprovisioning problem can occur due to underestimation of the workload. To reduce the SLA violation rate, modified workload prediction formula (24) is used. Figure 7 shows the impact of the parameter α on the SLA violation rate and the on-demand cost. It can be seen that, as the value of α increases, the SLA violation rate decreases while the on-demand cost increases.Figure 7
Impact ofα on the SLA violation rate and the on-demand cost.


## 7. Conclusion

In this paper, we propose a two-phase cloud resource provisioning algorithm for cloud users to reduce the resource rental cost using both on-demand and reserved instances. In the first phase, we formulate the resource reservation problem as a two-stage stochastic programming problem. We use the sample average approximation method to reduce the number of scenarios, and solve the SAA problem by a dual decomposition algorithm with branch and bound to obtain the optimal resource reservation. In the second phase, we propose a hybrid ARIMA-Kalman model for workload prediction and determine the number of on-demand instances based on the predicted workload. The effectiveness of the proposed two-phase algorithm is evaluated based on a real-world workload trace and Amazon EC2’s pricing models. The simulation results show that the proposed algorithm can achieve about 5%–20% more cost saving than existing algorithms while guaranteeing the SLA. In the future, we plan to investigate more pricing models offered by cloud providers such as spot pricing model, and use these pricing models to further reduce the resource rental cost of cloud users.



---

*Source: 1310237-2020-10-08.xml*