Page 84 - Proceedings of the 2018 ITU Kaleidoscope

‎ 2018 ITU Kaleidoscope Academic Conference‎

Figure 1 – Two-phase optimization scheme for VMP problems considered in this work, presenting a basic example with a
placement recalculation time of β = 2 (from t = 2 to t = 4) and a placement reconfiguration time of γ = 1 (from t = 4 to
t = 5).

of obtained solutions in VMP problems when compared VMs plus new requests) and their specifications;
to offline decisions [13]. Offline algorithms present a • information about the utilization of resources of each
substantial advantage over online alternatives. Unfortunately, active VM at each discrete time t;
offline formulations are not appropriate for highly dynamic
environments of real-world IaaS providers, where cloud • the current placement at each discrete time t (i.e. x(t)).
services are requested dynamically according to current The result of the iVMP phase at each discrete time t is an
demand. In this context, a previously proposed two-phase incremental placement ∆x(t) for the next time instant in such
optimization scheme is considered, combining advantages a way that x(t + 1) = x(t) + ∆x(t). The placement at t + 1 is
of online and offline VMP formulations and decomposing m(t)×n , as defined in
VMP problems into two different sub-problems: (1) represented as a matrix x(t + 1) ∈ {0, 1}
Equation ((1)):
(online) incremental VMP (iVMP) and (2) (offline) VMP
reconfiguration (VMPr).   x 1,1 (t + 1) . . . x 1,n (t + 1)  
The iVMP sub-problem is considered for dynamic arriving x(t + 1) =    x m(t),1 (t + 1) . . . x m(t),n (t + 1)    (1)
. . .
. . .
requests, where VMs could be created, modified and removed  . . . 
at runtime. Consequently, this sub-problem should be Formally, the placement for the next discrete time instant
formulated as an online problem and solved with short time x(t + 1) is a function of the current placement x(t) and the
constraints, where existing heuristics could be reasonably active VMs at discrete time t, i.e.:
appropriate. In online algorithms for iVMP, decisions are
performed at each discrete time t. The considered iVMP x(t + 1) = f [x(t),V(t)] (2)
problem is based on [13] and could be formally enunciated Additionally, the VMPr sub-problem is considered for
as: improving the quality of solutions obtained in the iVMP
Given a complex IaaS environment composed by a set of phase, reconfiguring the placement through VM migrations.
PMs (H), a set of active VMs already requested before time This sub-problem could be formulated offline, where
t (V(t)), and the current placement of VMs into PMs (i.e. alternative solution techniques could result in more suitable
x(t)), an incremental placement of V(t) into H for the time ones (e.g. meta-heuristics). An offline algorithm solves a
t + 1 (x(t + 1)) without migrations is sought, satisfying the VMP problem considering a static environment, where VM
problem constraints and optimizing the considered objective requests do not change over time considering the migration
functions. of VMs between PMs. The formulation of the considered
The considered formulation of the iVMP problem receives VMPr problem is based on [12] and could be enunciated as:
the following information as input data: Given a current placement of VMs into PMs (x(t)), a
placement reconfiguration through migration of VMs between
• a set of n available PMs and their specifications; PMs for the discrete time t (i.e. x (t)) is sought, satisfying the
0
• a dynamic set of m(t) requested VMs (already allocated constraints and optimizing the considered objective functions.

– 68 –