Information Technology Reference
In-Depth Information
3.4 Virtual Machine Allocation Problem Formulation
Given a set of virtual machines
V
=
{vm
i
|i
=1
,
2
, ..., n}
to be scheduled on
M
{M
j
|j
,
, ..., m}
a set of physical servers
=
=1
2
. Each VM is represented
x
i,
1
,x
i,
2
, ..., x
i,d
).
Similarly, each physical machine is denoted as a d-dimensional vector of capacity
resources, i.e.
vm
i
as a d-dimensional vector of demand resources, i.e.
=(
y
j,
1
,y
j,
2
, ..., y
j,d
). We consider types of resources such as
processing element (PE), computing power (Million instruction per seconds -
MIPS), physical memory (RAM), network bandwidth (BW), and storage. In
addition, the virtual machine has life-cycle with starting time and finishing time,
i.e., each
M
j
=(
vm
i
is started at a fixed starting time (
ts
i
) and is neither preemptive
nor migrated during its period time (
ts
i
+
dur
i
).
A feasible schedule
S
indicates a successful mapping of all VMs to physi-
cal servers , i.e.
∀i ∈{
1
,
2
..., n}, ∃j ∈{
1
,
2
, ..., m}
:
allocated
(
vm
i
,M
j
) where
allocated
(
vm
i
,M
j
) holds when
vm
i
is allocated on the physical server
M
j
.
We assume that every host
M
j
can run any virtual machine and the power
consumption model
P
j
(
t
) of the host
M
j
has a linear relationship with CPU
utilization as described in Eq. (
1
).
The virtual machine scheduling problem is NP-hard, even if all physical
servers are identical and all virtual machines are identical too, the scheduling is
still NP-hard with
1[
19
].
The goal is to find out a feasible schedule
d ≥
S
that minimizes the total energy
consumption of the cloud system, denoted as
j
=1
E
j
in the equation (
5
)as
following with
]. (In this paper we
have not yet concerned on the energy consumption for other systems, such as
electrical converters, cooling systems, and network systems).
i ∈{
1
,
2
, ..., n}
,
j ∈{
1
,
2
, ..., m}
,
t ∈
[0;
T
Minimize
m
=1
E
j
(5)
j
where
E
j
with
j
=1
,
2
, ..., m
is total energy consumption of a physical machine
M
j
as shown in Eq.
3
.
The scheduling problem has the following (hard) constraints:
- Constraint 1: Each VM is run by a physical server (host) at any time.
- Constraint 2: VMs do not request any resource larger than total capacity
resource of their hosts.
- Constraint 3: Let
M
j
.
The sum of total demand resources of these allocated VMs is less than or
equal to total capacity of the resources of the
r
j
(
t
) be the set of VMs that are allocated onto a host
M
j
.
vm
i
∈r
j
(
t
)
x
i,c
≤ y
j,c
∀c
=1
, ..., d
:
(6)
where:
-
x
i,c
is resource of type
c
(e.g. CPU core, computing power, memory)
vm
i
(i=1,2,...,n).
requested by the
Search WWH ::
Custom Search