capacity via renting the VMs from a public IaaS cloud. This
is a typical hybrid cloud model.
The public IaaS cloud will in general provision three
types of VM services for the SaaS provider. The first is the
reserved VM service, which is long-term service with a fixed
VM numbers. We let T denote the minimum allowed rent-
ing period of such services. T is typically several days or
months [4], [28]. The second is the on-demand VM service,
where the number of VMs can be set instantaneously by the
SaaS provider. The last is the on-spot VM services, which the
SaaS provider can bid for. The price of the reserved service
per unit is typically the lowest. The on-demand one is often
the most expensive but it is charged in a pay-as-you-go
fashion. The price of the on-spot one is dynamic according
to the user bid (reflecting the user demand). The above is a
typical IaaS provision scheme for current public IaaS cloud
(e.g., the Amazon EC2).
Since renting the public cloud resources incurs monetary
cost, the SaaS provider should reduce such cost. The key
problem to the SaaS provider is how to decide the number
of VMs it need to rent so that the performance requirement
is satisfied and the cost is minimized. We use the symbols
R, D, and S to denote the numbers of VMs of the above
three services an SaaS provider will rent respectively. Also
let L denote the numbers of the VMs in the local servers the
SaaS provider owns. Let R
max
, D
max
, S
max
and L
max
denote
the upper bound of the numbers of each VM type, and let
W denote the lower bound of the numbers of all of VMs.
In the real-world scenario, the SaaS provide has to
make decisions on the number of the VMs in some
degrees of granularity. Si nce the allowed mi nimum rent-
ing period of reserved VMs is T ,weconsidertheSaaS
provider will d ivide its operation period into a sequence
of time intervals with length T and determine the number
of the reserved VMs at the beginning of each interval. We
name such a decision i nterval with length T acoarse-
grained decisio n interval.
The numbers of the other two types of VMs (the on-
demand ones and the on-spot ones) can be decided in a rela-
tively short-term manner. Without loss of generality, we
consider the operation time can be divided into many non-
overlapping small decision slots with length t. Let t
1
,
t
2
; ...; t
i
; ... (i is a non-negative integer) denote such slots
in sequence. The length of each t
i
is t. For example, in Ama-
zon EC2, t is one hour, which means that the SaaS provider
can make the decisions of the on-demand VMs and the on-
spot ones per hour. We name such a decision slots with
length t a fine-grained decision time slot.
Without loss of generality, suppose T ¼ mt. In other
words, the length of the coarse-grained decision interval is
m times of the fine-grained decision time slot. The SaaS pro-
vide can decide the number of the reserved VMs in the
beginning of time slot t
0
, t
m
, t
2m
; ...; t
jm
; ... where j is a
non-negative integer.
In this way, how to determine the numbers of the above
four types of VMs for the SaaS provider can be divided into
a two-scale decision process. Finally, Table I provides a
summary of the symbols used in this paper.
3.2 User Requests and SaaS Service Model
Consider the users access the SaaS provider with an arrival
rate ðt
i
Þ. Note that ðt
i
Þ can bear an arbitrary distribution
in realistic scenarios.
The user requests to the SaaS provider usually have
deadlines, allowing the request to wait f or a maximum
periods of time d
max
before it is scheduled. Consider the
requests can be stored in a queue denoted by Qðt
i
Þ in
each fine- grained decision time slot. In each find-grained
interval, the user requests in the queue are served with
the rat e mðt
i
Þ. Therefore, the queue has the following
update equation:
Qðt
i þ 1
Þ¼maxfQðt
i
Þmðt
i
Þ; 0gþðt
i
Þ: (1)
To serve the user requests, the SaaS provider allocates
each request a certain number of VMs according to the
request requirement, consisting of those in the local servers
and those in the public IaaS cloud. The service rate in each
time slot t
i
in a coarse-grained decision interval is
TABLE 1
Notation
Symbols Descriptions
T Minimum renting period of reserved VMs
t
i
The ith decision slot for the on-demand VMs and
the on-spot VMs
t The length of each decision slot for the on-demand
VMs and the on-spot VMs. T ¼ mt where m is an
integer.
Rðt
i
Þ The number of reserved VMs at time slot t
i
R
max
The upper bound of the number of the reserved
VMs
Dðt
i
Þ The number of on-demand VMs at time slot t
i
D
max
The upper bound of the number of the on-demand
VMs
Sðt
i
Þ The number of on-spot VMs at time slot t
i
S
max
The upper bound of the number of the on-spot
VMs
Lðt
i
Þ The number of VMs in the local servers at time
slot t
i
L
max
The upper bound of the number of the VMs in the
local servers
Wðt
i
Þ The lower bound of the number of VMs at time
slot t
i
ðt
i
Þ The arrival rate of user requests at time slot t
i
mðt
i
Þ The service rate of user request at time slot t
i
d
max
The maximum allowed queueing time of each
user request
Qðt
i
Þ The backlog of the user request queue
Q
max
The maximum of the queue backlog
Zðt
i
Þ The backlog of the virtual queue
Z
max
The maximum of the virtual queue backlog
f The cost of running the local servers
P
r
ðt
i
Þ The price of reserved VMs at t
i
P
d
ðt
i
Þ The price of on-demand VMs at t
i
P
s
ðt
i
Þ The price of on-spot VMs at t
i
Mðt
i
Þ The communication cost between VMs in the local
servers and those in the cloud
bðt
i
Þ The service response time at time slot t
i
b
max
The service response time upper bound requirment
The parameter bounding growing rate of the
virtual queue
V Parameter for the trade-off between queueing
delay and the cost
400 IEEE TRANSACTIONS ON SERVICES COMPUTING, VOL. 8, NO. 3, MAY/JUNE 2015