Mathematical Problems in Engineering
Data center
Internet
service
provider
End
user
F : A data center in the cloud computing system.
10
15
9
19
5
23
12
20
25
20
15
10
5
0
12345678
F : An example of VM instance demand in dierent hours of
aday.
provider serve to its end users. To reduce the request response
time, the data center oen employs a shared queue structure.
e arrival rate of end user varies over time, which
induces a time-changing VM instance demand. Figure
presents an example which divides a day into phases
( hr/phase) and the -axis shows the VM instance demand
to ensure the QoS requirement in each phase. e marginal
rental cost in Amazon EC is given in Table .FromFigure ,
we can see that there is a big gap between the maximum
and the minimum instance demand. If the ISP only uses RIS
instance, he must acquire instances in order to satisfy the
peak workload appeared in the th phase, which wastes a lot
of resource and rises the daily instance rental cost to 247.96
(the rental cost for using only RIS instance can be computed
as 23×0.448×24=247.96 (the product of the number of
instance, the marginal cost, and total hours)). In contrast,
if the ISP only adopts MIS instance, he will obtain the highest
resource utilization, and there is an opportunity to reduce the
daily rental cost to 230.52(fromFigure ,thetotalnumber
of MIS instances is 10+15+9+19+5+23+12+20=113.
Since a phase contains hours, the rental cost for using only
MIS instance can be computed as 113×3×0.680=230.52).
If the ISP uses a hybrid approach which includes both RIS
and MIS, on the other hand, the daily instance rental cost
can be remarkably reduced. To see that, consider a resource
provisioning policy which rents RIS VM instances and
acquires extra MIS instances if RIS instances are insucient.
e number of MIS instance can be formally written as [
𝑖
−
10]
+
where
𝑖
denotes the number of VM instance demand
in phase . e daily rental cost for this hybrid approach is
187.08, (the rental cost for RIS instance is 10×0.448×24=
107.52. e total number of MIS instances is 5+0+9+
13+2+10=39; therefore the rental cost for MIS instance is
39×0.680×3=79.56. us, the total cost is 107.52+79.56=
187.08.), which saves .% and .% compared with using
purely RIS and MIS instance, respectively.
e above analysis suggests assumptions. First, the QoS
performance in terms of percentile delay can be precisely
predicted; second, the number of RIS and MIS instances can
be determined to minimize the VM instance rental cost. e
following sections explain these two assumptions in detail.
4. A General Optimization Framework for the
CDIP Problem
e notations used in this paper are shown in Notations
section. e CDIP problem can be formulated as
min
𝑘
𝑖
,𝑖∈{0,...,𝑁}
0
××
𝐿
+
𝑆
×
𝑁
𝑖=1
𝑖
()
subject to
Pr
𝑖
≥
≤, ∀∈
{
1,...,
}
,
()
where
0
is the number of RIS instance and
𝑖
,>0,isthe
number of MIS instance in phase .
Note that, in the CDIP problem, the distribution of
𝑖
is determined by the characteristics of exogenous interactive
workload arrivals and the number of active VM instance
𝑖
.
As stated in Section , this problem is hard to solve, since
we can hardly derive an explicit form of constraint (). In
this section, we will show how to approximately characterize
constraint () and obtain the optimal solution.
4.1. A Learning Algorithm to Characterize the Percentile
QoSConstraintinSelf-SimilarTrac.Algorithm learns
the performance of various instance provisioning policies
in the form of percentile delay via the stochastic gradient
method. e algorithm rst creates a data structure called
VP
table (Violation Probability Table), in which each item
VP
table[][] estimates the delay violation probability given
thenumberofinstancebeingin phase .ealgorithm
runs for several iterations to obtain unbiased delay violation
probability samples p[][]foreachphase. ese samples,
which can be generated via real system running or simu-
lation, are further smoothed into VP
table[][]. erefore,
VP
table[][] is an unbiased estimation of delay violation
probability with VM instances in phase .Variables,,and
are iteration counter, decision point counter, and instance
number counter, respectively. Algorithm has the following
property.