![](https://csdnimg.cn/release/download_crawler_static/16787562/bg4.jpg)
Z. Cai et al. / Future Generation Computer Systems 79 (2018) 38–53 41
is an extension of TAR with a much more flexible regime transition
strategy. In MRS-AR, the regime transition is defined by a Markov
process rather than transition variables. MRS-AR has been used
to model many different time series with changing regimes such
as exchange rates [21,40] and financial time series [20]. For each
prediction step, the absolute probability distribution (APD) over
regimes, obtained from the last conditional probability distribu-
tion multiplying multi-step transition probabilities, can be used to
forecast prices [21]. However, APDs of non-seasonal Markov chains
usually converges to equilibrium distributions quickly. Therefore,
APDs are only suitable for predicting short-term regimes rather
than long-term ones. For example, Chen et al. [19] used the regime
with the largest absolute probability to produce a one-step fore-
cast. Expectation based prediction is another way to produce fore-
cast values. Yuan et al. [21] used the expected mean to forecast,
without specifying regimes, which is determined by the probability
distribution of regimes and the mean of each regime. However,
specifying appropriate regimes is benefit in improving the ac-
curacy of predictions. Therefore, in this paper, two methods are
proposed to predict regimes which use ARMA to model historical
durations of regimes combined with the probability transition
matrix among regimes.
To summarize, statistical probability models have been widely
used to recognize changes in spot prices without considering
trends in sequential prices. Existing time series based models such
as autoregression, ARIMA, SES, DES and TES with a single model
cannot describe nonlinear Spot prices with multiple regimes well.
Therefore, in this paper, two Markov regime-switching autoregres-
sive model based prediction methods are proposed which build
separate models for different regimes. For comparison, a dynamic-
ARIMA is proposed too which differentiates prices to deal with
large fluctuations.
3. Problem description
As stated, there are mainly two kinds of pricing models in
Cloud computing platforms [2]: (1) Fixed pricing models: prices of
resources are fixed, e.g., Amazon’s EC2 On-demand VM instances
and Reserved VM instances; (2) Variable pricing models: prices
of resources change stochastically according to real-time market
demands, e.g., Amazon’s EC2 prices of spot VM instances (spot
prices). Amazon’s EC2 spot VM instances are sold to users via
auctions. When a user rents a spot instance, the user places a bid
price. Only when the bid price is higher than the spot price, does
the user have the possibility of getting the VM instance. After the
user gets the VM, the user needs to pay according to the spot
price. If the spot price is higher than the bid price, the Cloud
computing provider will withdraw the VM (out-of-bid event) and
the last interval will not be charged. When out-of-bid events occur,
recovery from previous checkpoints will consume additional time
and cost. Spot instances are usually cheaper than On-demand VM
instances with the same configurations. However, spot instances
are unreliable because of out-of-bid events resulting from the
stochastic prices. Choosing appropriate VM types, selecting the
correct rental periods and elaborating bids based on forecasted
spot prices (predicted trends) is helpful in minimizing resource
rental costs.
In this paper, we aim to develop several prediction algorithms
to forecast spot prices accurately. For a spot price time series,
using all the past data to forecast future prices is time consuming.
Therefore, only data of a fixed length of time (a window) is usually
used, e.g., the prices of past 480 h. As time progresses, the time
window moves forward. For each time window, the time series of
spot prices is represented by {Y
t
}
T
t=1
, where t indicates the index
of time units (e.g., the index of hours, minutes or seconds) and
T is the length of the time series in the current time window.
The objective of the proposed forecasting methods is to minimize
forecasting errors. To evaluate the performance of predictions the
popular Mean Absolute Percentage Error (MAPE) [41] is used as
defined in the following.
MAPE
n
=
100
n
n
∑
l=1
|
ˆ
Y
T
(l) − A
T
(l)
A
T
(l)
| (1)
where A
T
(l) is the actual value,
ˆ
Y
T
(l) is the forecasted value of
prediction step l and n is the length of the forecast period. Note
that MAPE has been criticized in the past, most notably in [42].
However, it is still the easiest to understand and most widely used
error measure in the literature.
4. Preliminaries
4.1. Autoregressive integrated moving average model
Autoregressive-Moving Average (ARMA) is a popular model for
describing a (weakly) stationary stochastic process. ARMA consists
of two parts, an autoregressive (AR) part and a moving average
(MA) part. The AR part involves regressing past values and the
MA part is a linear combination of past error terms. The model of
ARMA(p, q) is as follows.
Y
t
=
p
∑
i=1
φ
i
Y
t−i
+
q
∑
j=1
θ
j
ε
t−j
+ ε
t
(2)
where ε
t
∼ i.i.d.N(0, σ
2
) is the error item of time t, p is the order
of the autoregression part, φ
i
is the autoregression parameter of
Y
t−i
, q is the order of the moving average part and θ
j
is the moving
average parameter of ε
t−j
. ARMA is usually suitable for stable time
series and large fluctuations in spot prices will decrease the pre-
diction accuracy of ARMA. ARIMA is an extension of ARMA which
applies an initial differencing step to reduce the non-stationarity
which improves the prediction accuracy of spot prices with large
fluctuations. The model of ARIMA(p, 1, q) is as follows.
Y
t
− Y
t−1
= θ
0
+
p
∑
i=1
φ
i
(Y
t−i
− Y
t−i−1
) +
q
∑
j=1
θ
j
ε
t−j
+ ε
t
(3)
where ε
t
∼ i.i.d.N(0, σ
2
).
4.2. Markov regime-switching AR model
The linear based ARIMA uses a single model to describe time
series. However, spot prices in some VM types have switching
regimes, i.e., different periods have different regimes (different sta-
tistical characteristics). Therefore, different time series models are
needed to describe different regimes. For example, two different
autoregressive (AR) models are required to model two different
regimes. For the first regime, the AR model might be
Y
t
= c
1
+
p
∑
i=1
φ
i,1
Y
t−i
+ ε
t,1
(4)
where ε
t,1
∼ i.i.d.N(0, σ
2
1
), c
1
is the intercept value and φ
i,1
is the
autoregressive parameter of Y
t−i
. For the second regime, the AR
model might be
Y
t
= c
2
+
p
∑
i=1
φ
i,2
Y
t−i
+ ε
t,2
(5)
where ε
t,2
∼ i.i.d.N(0, σ
2
2
), c
2
is the intercept value and φ
i,2
is the
autoregressive parameter of Y
t−i
. Different regimes have different
intercept values and autoregressive parameters. Each regime can
be defined as a state of a Markov process. The spot price switches