Inter
national
J
our
nal
of
Electrical
and
Computer
Engineering
(IJECE)
V
ol.
9,
No.
1,
February
2019,
pp.
512
524
ISSN:
2088-8708,
DOI:
10.11591/ijece.v9i1.pp512-524
512
Bin
packing
algorithms
f
or
virtual
machine
placement
in
cloud
computing:
a
r
e
view
K
umaraswamy
S
1
and
Mydhili
K
Nair
2
1
Department
of
Computer
Science
and
Engineering,
Global
Academy
of
T
echnology
,
Beng
aluru
560098,
India
2
Department
of
Information
Science
and
Engineering,
Ramaiah
Institute
of
T
echnology
,
Beng
aluru
560054,
India
Article
Inf
o
Article
history:
Recei
v
ed
Dec
31,
2017
Re
vised
Jul
25,
2018
Accepted
Jul
29,
2018
K
eyw
ords:
Cloud
computing
V
irtual
machine
placement
Bin
packing
ABSTRA
CT
Cloud
computing
has
become
more
comm
ercial
and
f
amiliar
.
The
Cloud
data
centers
ha
v
e
huge
challenges
to
maintain
QoS
and
k
eep
the
Cloud
perf
ormance
high.
The
placing
of
virtua
l
machines
among
ph
ysical
machines
in
Cloud
is
significant
in
opti-
mizing
Cloud
performance.
Bin
packing
based
algorithms
a
re
most
used
concept
to
achie
v
e
virtual
machine
placement
(VMP).
This
paper
presents
a
rigorous
surv
e
y
and
comparisons
of
the
bin
packing
based
VMP
methods
for
the
Cloud
computing
en
viron-
ment.
V
arious
methods
are
discussed
and
the
VM
placement
f
actors
in
each
methods
are
analyzed
to
understand
the
adv
antages
and
dra
wbacks
of
each
method.
The
scope
of
future
research
and
studies
are
also
highlighted.
Copyright
c
2019
Institute
of
Advanced
Engineering
and
Science
.
All
rights
r
eserved.
Corresponding
A
uthor:
K
umarasw
amy
S,
Dept.
of
Computer
Science
and
Engineering,
Global
Academy
of
T
echnology
,
Rajarajeshw
ari
Nag
ar
,
Beng
aluru
-
560098
India.
+919886363412
Email:
sksw
amy99@gmail.com
1.
INTR
ODUCTION
1.1.
Back
Gr
ound
In
recent
years
Cloud
computing
architectures
ha
v
e
recei
v
ed
an
increasing
attention
due
to
their
great
promises
in
enabling
distrib
uted
computing
paradigm
[1].
It
pro
vides
pool
of
computing
resources
enabling
the
Cloud
user’
s
application
to
use
it
[2].
These
resources
can
be
rented
to
users
or
customers
by
Cloud
Service
Pro
viders
(CSPs)
on
pay-as-you-go
model,
lik
e
public
utility
such
as
g
as,
w
ater
and
electricity
[3,
4].
V
irtualization
is
an
enabled
technology
for
cloud
computing.
It
pro
vides
the
fle
xibility
to
cloud.
It
minimizes
the
ener
gy
cost,
maximizes
the
CPU
utilization,
and
maximizes
the
usage
of
memory/disk.
Multiple
VMs
on
a
PM
may
de
grades
the
performance
of
PM
or
o
v
erutilize
the
PM.
T
o
o
v
ercome
these
issues,
virtualization
layer
pro
vides
the
mobility
to
pl
ace
or
mo
v
e
VM
to
other
PMs
within
cloud.
The
plan
for
placing
VMs
among
PMs
plays
an
important
role
in
optimi
zing
cloud
perform
ance
is
c
alled
V
irtual
Machine
Placement
(VMP)
which
finds
the
optimal
VM
placement/mapping
with
PMs
with
v
arious
objecti
v
es
and
constraints.
In
principle,
the
VMP
problem
is
related
to
the
classical
Bin
P
acking
(BP)
problem,
where
the
aim
is
to
pack
or
place
or
map
set
of
items
/
objects
of
dif
ferent
size
into
a
minimum
number
of
unit-capacity
bins.
It
is
pro
v
ed
in
literature
that
both
BP
and
VMP
are
NP-hard
problems
[5].
If
there
are
’m’
PMs
and
’n’
VMs,
then,
m
n
placement
solutions.
If
m
and
n
are
v
ery
big
numbers,
solutions
are
huge.
One
can
easily
say
that
VMP
is
as
hard
as
BP
.
The
dif
ferences
between
Classical
BP
and
BP-based
VMP
are
detailed
in
T
able
1
J
ournal
Homepage:
http://iaescor
e
.com/journals/inde
x.php/IJECE
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
513
Since
VMP
problem
is
an
NP
hard
problem,
e
xact
algorithms
tak
es
more
time
to
get
solutions,
hence
this
problem
can
be
ef
fecti
v
ely
approximated
using
approximation
algorithms
such
as
greedy
algorithms,
ge-
netic
algorithms
to
accomplish
results.
These
pro
vide
a
solution,
which
though
v
ery
good
in
most
cases,
may
not
be
an
optimal
solution
b
ut
near
-optimal.
P
acking
algorithms
lik
e
First
Fit,
Best
Fit,
W
orst
Fit
,
First
Fit
Decreasing
(FFD),
Best
Fit
Dec
reasing
(BFD),
W
orst
Fit
Decreasing
(WFD),
greedy
algorithms
etc.,
are
used
to
place
VMs
optimally
.
Also,
authors
in
Ref.
[6,
7,
8,
9]
present
fe
w
heuristics
lik
e
First-Fit
(FF),
Best-Fit
(BF),
and
W
orst-Fit
(WF)
for
load
balancing,
some
of
which
could
be
tuned
to
serv
e
the
purpose
of
VMP
.
In
the
FF
,
the
VM
is
placed
in
the
PM
which
is
selected
as
first
machine
with
a
v
ailable
capacity
.
In
BF
,
the
name
itself
says
fit
to
be
best
when
left
o
v
er
space
is
least
after
placing
the
VM
in
the
PM.
In
the
WF
,
left
o
v
er
space
is
more
compared
to
pre
vious
methods
when
the
VM
is
pack
ed
in
the
PM.
In
First
Fit
Decreasing
(FFD),
Best
Fit
Decreasing
(BFD),
and
W
orst
Fit
Decreasing
(WFD)
heuristics
VMs
are
sorted
in
decreasing
order
before
packing.
Once
sorted,
the
VMs
are
placed
according
to
original
heuristics.
T
able
1.
Dif
ferences
between
Classical
BP
and
BP-based
VMP
schemes
Classical
BP
BP-based
VMP
Item
size
is
fix
ed
once
placed
Item
size
will
v
ary
e
v
en
after
place-
ment
due
to
SLAs
mono-objecti
v
e
optimization
e.g.,
to
minimize
number
of
bins
multi-objecti
v
e
optimization
e.g.,
minimize
number
of
bins
and
max-
imize
VMs
performance
single-dimensional
resource
pack-
ing
e.g.,
CPU
or
memory
multi-dimensional
resource
pack-
ing
e.g.,
CPU
and
memory
The
VMP
problem
can
also
be
considered
as
a
multi-dimensional
or
multi-capacity
problem
wi
thin
a
PM
[10].
In
Multi-Capacity
Bin
P
acking
(MCBP)
problem,
once
item
is
allocated
to
bin,
its
resources
lik
e
CPU,
memory
,
bandwidth
etc.,
cannot
be
allocated
or
a
v
ailable
to
other
items
in
a
bin.
In
multi-dimensional
problem,
capac
ity
is
shared
and
is
not
dedicated
to
single
item.
This
leads
to
conflict
among
items
to
get
dedicated
resources.
Figure
1
sho
ws
the
comparison
between
multi-dimensional
and
multi-capacity
bin
packing.
Figure
1.
multi-dimensional
vs.
multi-capacity
bin
packing
[10]
1.2.
Pr
oblem
Description
There
has
been
considerable
contrib
utions
in
the
literature
re
g
arding
BP
problem
and
its
applicat
ion
for
the
VMP
issue.
Man
y
approximation
techniques
to
solv
e
BP
problem
for
VMP
i
ssue
ha
v
e
been
presented;
ho
we
v
er
,
comparati
v
e
study
on
all
these
techniques
is
still
lacking
in
the
literature.
Comparing
all
the
major
techniques
for
VMP
issue
through
BP
problem
modeling,
w
ould
aid
in
understanding
the
relati
v
e
merits
and
design
limi
tations
of
all
these
techniques,
and
w
ould
also
aid
in
framing
future
problems
in
this
area.
The
main
focus
of
this
paper
is
to
pro
vide
comprehensi
v
e
surv
e
y
and
simulation
study
on
v
arious
approximation
technique–re
g
arding
BP
solution
techniques–used
for
VMP
issue;
also,
to
pro
vide
the
merits
and
limitations
for
these
techniques,
and
to
identify
the
future
research
problems.
Bin
pac
king
algorithms
for
virtual
mac
hine
...
(K
umar
aswamy
S)
Evaluation Warning : The document was created with Spire.PDF for Python.
514
ISSN:
2088-8708
1.3.
Contrib
utions
In
this
surv
e
y
paper
,
the
important
considerations
and
challenges
such
as:
resource
utilization,
rel
iabil-
ity
e.t.c,
to
ef
ficiently
design
BP
based
solution
for
VMP
issue
are
outlined.
The
three
important
approximation
solutions
for
BP
problem:
First
Fit
,
Best
Fit
and
Best
Fit
Decreasing
approaches,
are
described;
also,
the
recently
e
xtended
techniques
for
these
approximation
solutions
presented
in
the
literature
are
also
described.
Heuristics
for
VMP
issue,
usually
do
not
g
ua
rantee
performa
n
c
e
bounds;
ne
v
ertheless,
the
y
pro
vide
empirically
demonstrated
performance
merits,
and
dif
ferent
heuristic
techniques
used
for
VMP
issue
are
also
outlined.
Rel-
ati
v
e
simulation
oriented
performance
comparison
for
dif
ferent
approximation
solutions
for
BP
problem
based
VMP
issue
is
pres
ented,
and
corresponding
merits
and
limitations
are
outlined.
Finally
,
the
future
directions
for
the
VMP
issue
are
highlighted.
This
paper
is
or
g
anized
as
follo
ws;
we
start
with
a
discussion
on
the
considerations
and
challenges
for
VMP
(Section
2),
follo
wed
by
BP-based
problem
definition
in
Section
3.
Section
4
presents
BP
based
VMP
.
Challenges
of
BP
algorithms
are
presented
in
section
5.
Section
6
presents
performance
e
v
aluation
of
VMP
schemes.
This
is
follo
wed
by
future
studies
(Section
7),
and
conclusion
(Section
8).
2.
CONSIDERA
TIONS
AND
CHALLENGES
OF
VMP
Se
v
eral
placement
problem
e
xist
with
re
g
ard
to
determining
as
to
where
data
needs
to
be
stored
and
where
the
job
in
VMs
can
be
e
x
ecuted.
Here
we
discuss
the
considerations
and
challenges
of
VMP
.
2.1.
Considerations
of
VMP
There
are
se
v
eral
f
actors
in
v
olv
ed
in
deciding
as
to
when
and
where
to
place
or
reallocate
VMs
for
performing
computations
in
Cloud
computing
en
vironment.
The
main
f
actors
are
as
follo
ws.
(a)
Performance:
T
o
see
that
the
utilization
of
ph
ysical
infrast
ructures
are
impro
v
ed,
dat
a
centers
(DC)
need
t
o
emplo
y
virtualization
that
could
f
acilitate
lar
ge
number
of
applications
to
run
simultane-
ously
[11].
(b)
Cost:
Recent
trend
in
Cloud
mark
et
sho
ws
that
dynamic
pricing
schemes
utilization
is
being
in-
creased
[12]
to
reduce
the
in
v
estment
in
the
DC.
There
fore,
internal
cost
for
VMP
also
needs
to
be
considered.
(c)
Locality:
If
accessibility
and
usability
for
users
need
to
be
considered,
VMs
should
be
closely
located
to
users.
(d)
Reliability
and
continuous
a
v
ailability:
Reliability
and
a
v
ailability
of
the
dif
ferent
DC,
and
its
e
xpected
usage
frequenc
y
must
be
tak
en
into
account.
2.2.
Challenges
of
VMP
V
ariation
of
scenarios
in
which
the
applications
are
to
be
deplo
yed
need
rele
v
ant
parameters
consid-
erations
that
results
in
the
follo
wing
challenges
while
placing
VMs.
(a)
Firstly
,
non-e
xistence
of
generic
model
for
representing
v
arious
scenarios
for
resource
scheduling.
(b)
Secondly
,
parameterization
of
model
for
bigger
problem
size.
(c)
Thirdly
,
the
VMP
problem
is
typically
mapped
to
multiple-knapsack
problem,
belonging
to
a
cate-
gory
of
NP
hard
problems
[13].
Thus,
tradeof
fs
between
e
x
ecution
time
and
quality
of
solution
is
an
important
issue
to
be
tackled,
gi
v
en
the
size
of
real
life
DC.
3.
BIN
P
A
CKING
PR
OBLEM
Let,
S
=
S
1
;
S
2
;
:::S
m
be
the
set
of
bins
and
all
of
them
ha
v
e
the
same
size
V
.
Let,
a
1
;
a
2
;
::::a
n
be
the
set
of
n
items
that
need
to
be
pack
ed
in
the
bins.
The
task
is
to
disco
v
er
inte
ger
number
of
bins
B
and
a
B
partition
of
the
set
(1
;
2
;
::n
)
gi
v
en
by
,
S
1
[
S
2
[
;
:::
[
S
B
,
so
that,
P
i
2
S
k
a
i
V
8
k
=
1
;
2
;
::B
.
The
optimal
IJECE
V
ol.
9,
No.
1,
February
2019
:
512
–
524
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
515
solution
is
to
find
minimal
B
.
The
inte
ger
Liner
Programming
formulation
of
Bin
P
acking
problem
is
sho
wn
in
Equation
1.
min
B
=
n
X
i
=1
y
i
(1)
subject
to
B
1
,
P
n
j
=1
a
j
x
ij
V
y
i
,
8
i
2
(1
;
2
;
::n
)
,
P
n
i
=1
x
ij
=
1
,
8
j
2
(1
;
2
;
::n
)
,
y
i
2
(0
;
1)
,
8
i
2
(1
;
2
:::n
)
,
x
ij
2
(0
;
1)
,
8
i
2
(1
;
2
;
:::n
)
,
8
j
2
(1
;
2
;
:::n
)
Here,
y
i
=
0
if
bin
i
is
not
used,
otherwise,
y
i
=
1
and
x
ij
=
0
if
item
j
is
put
into
bin
i
,
otherwise,
x
ij
=
1
.
4.
BP-B
ASED
VMP
W
e
vie
w
the
problem
of
placement
of
VMs
in
data
centers(DC)s
as
similar
to
a
BP
problem.
W
e
visulaize
the
classic
BP
Problem
[5]
in
the
conte
xt
of
VMP
in
the
follo
wing
w
ay:
VMs
(objects)
of
dif
ferent
sizes
are
placed
in
hosts
(bins
)
to
ensure
minimum
hosts
being
emplo
yed
for
placing
all
VMs.
In
other
w
ords,
the
problem
statement
can
be
stated
as
follo
ws:
W
ith
’x’
PMs
being
made
a
v
ailable
with
resource
capacities
in
terms
of
memory
,
CPU
and
netw
ork
bandwidth
resources,
we
require
’y’
VMs
to
be
placed
such
that
the
total
resource
requirement
of
the
VMs
placed
on
a
PM
should
not
e
xceed
its
capacity
.
Se
v
eral
BP-based
VMP
algorithms
are
used
in
finding
optimal
VMP
are
discussed
ne
xt.
4.1.
First
Fit
(FF)
appr
oach
The
First
Fit
Bin
P
acking
algorithm
is
described
in
Algorithm
1.
The
items
are
scanned
in
an
y
order
and
e
v
ery
item
is
attempted
to
be
placed
in
the
a
v
ailable
bins
sequentially
.
If
it
does
not
get
fit
into
e
xisting
bins
then,
ne
w
bin
is
created
to
place
the
item.
This
algorithm
achie
v
es
an
approximation
ratio
of
2
.
Algorithm
1
First
Fit
Algorithm
f
or
i
=
1
to
n
do
f
or
j
=
1
to
m
do
if
Item
i
with
size
a
i
fits
in
Bin
S
j
then
Place
the
item
a
i
in
Bin
S
j
.
j
+
+
end
if
if
Item
i
does
not
fit
in
Bin
S
j
then
j
+
+
end
if
end
f
or
if
Item
i
does
not
fit
in
an
y
Bin
then
Open
a
ne
w
bin
and
place
the
item
in
it.
m
=
m
+
1
end
if
end
f
or
Authors
in
[14]
introduce
a
dynamic
serv
er
and
consolidation
management
algorithm
that
meas
ures
historical
data,
forecas
ts
future
demand
and
re-maps
VMs
to
PMs.
T
o
forecast
future
demand,
time
series
method
is
used.
The
BP
heuristic
method
based
on
FF
approximation
is
used
to
perform
mapping
between
VMs
and
PMs.
Authors
in
[15]
in
v
estig
ated
VMP
problem
in
a
Cloud
as
a
generalized
assignment
problem
(GAP)
and
formulated
a
multi-le
v
el
generalized
assignment
problem
(MGAP).
It
uses
FF
heuristic
to
solv
e
MGAP
and
maximizes
the
profit
under
the
SLA.
Bin
pac
king
algorithms
for
virtual
mac
hine
...
(K
umar
aswamy
S)
Evaluation Warning : The document was created with Spire.PDF for Python.
516
ISSN:
2088-8708
In
the
FF
approach,
the
VMs
are
placed
in
the
host
where
the
y
first
fit,
according
to
a
predefined
order
between
acti
v
e
hosts.
The
FF
algorithm
[16,
5]
accomplishes
this
by
acti
v
ating
a
single
host
at
a
time,
as
it
is
filled
up
with
VMs.
This
results
in
DC
sa
ving
ener
gy
,
since
only
hosts
that
contain
some
VMs
need
to
be
switched
on.
Ho
we
v
er
,
since
host
resource
usage
le
v
els
tend
to
be
close
to
the
maximum,
VM
migration
is
more
lik
ely
to
happen
in
the
presence
of
elasticity
,
that
de
grades
the
performance,
besides
consuming
some
e
xtra
ener
gy
.
4.2.
Best
Fit
(BF)
appr
oach
The
Best
Fit
technique
is
described
in
Algorithm
2.
The
algorithm
w
orks
similar
to
First
Fit,
b
ut,
the
items
are
placed
in
that
bin
which
has
the
lo
west
residual
capacity
.
The
Best
Fit
algorithm
achie
v
es
an
approximation
ratio
of
2
.
Algorithm
2
Best
Fit
Algorithm
Let
r
1
=
V
0
;
r
2
=
V
0
;
::r
m
=
V
0
be
the
initial
residual
capacity
of
each
bin.
f
or
i
=
1
to
n
do
f
or
j
=
1
to
m
do
if
Item
i
with
size
a
i
fits
in
Bin
S
j
then
Calculate
scor
e
ij
=
r
j
a
i
j
+
+
end
if
end
f
or
Fit
item
i
into
that
bin
which
has
the
lo
west
scor
e
ij
.
r
j
=
r
j
a
i
if
Item
i
does
not
fit
in
an
y
Bin
then
Open
a
ne
w
bin
and
place
the
item
in
it.
m
=
m
+
1
end
if
end
f
or
Authors
in
Ref.
[17]
consider
greedy
algorithm
with
tw
o-stage
to
solv
e
VMP
for
maximizing
ener
gy-
ef
ficienc
y
and
netw
ork
performance.
In
first
stage,
i
f
no
congestion,
ener
gy
optimization
took
priority
.
Authors
combined
minimum
cut
hierarchical
clustering
with
Best
Fit(BF)
algorithm,
enabled
VMs
with
lar
ge
traf
fic
to
be
placed
on
the
same
PM
or
the
same
access
switch.
In
second
stage,
if
there
is
congestion,
the
y
applied
local
search
algorithm
to
minimize
Maximum
Link
Utilization(MLU)
and
link
congestion
with
equal
distrib
ution
of
netw
ork
traf
fic.
Authors
in
[18]
consider
F
at-tree
DC
topology
to
propose
a
solution
for
VMP
problem
and
migration.
The
solut
ion
reduces
the
po
wer
cos
t
and
job
delay
by
consolidating
VMs
to
a
fe
w
PM
s
and
mi
grating
VMs
to
close
locations.
In
VMP
stage,
it
considers
tw
o
mechanisms,
namely
random
placement
mechanism,
and
po
wer
-ef
ficient
placement.
In
random
placement,
PM
is
selected
randomly
to
place
a
VM.
In
po
wer
-ef
ficient
mechanism,
three
algorithms,
i.e.,
FF
,
BF
and
WF
are
discussed;
an
OpenFlo
w
controller
uses
these
algorithms
to
find
proper
PM
to
deplo
y
a
VM
based
on
the
weighted
dif
ference.
The
authors
in
[19]
discuss
a
static
disk
threshold-based
migration
algorithm
aiming
at
optimizing
the
performance
of
the
VMs.
T
o
pre
v
ent
the
de
gradation
and
congestion
problems
in
the
netw
ork,
authors
in
[20]
in
v
estig
ate
a
VM
placement
method,
called
ener
gy
ef
ficienc
y
and
quality
of
service
a
w
are
VM
placement
(EQVMP).
T
o
predict
the
future
beha
vior
of
a
VM
on
destination
host,
authors
in
Ref.
[21,
17]
present
a
VM
placement
scheme
named
Backw
ard
Speculati
v
e
Placement
(BSP),
that
monitors
the
historical
demand
traces
of
the
deplo
yed
VMs.
4.3.
First
Fit
Decr
easing
(FFD)
and
Best
Fit
Decr
easing(BFD)
appr
oach
The
Fit
Fit
Decreasing
and
Best
Fit
decreasing
techniques
w
ork
similar
to
First
Fit
and
Best
Fit
tech-
niques
respecti
v
ely
.
But,
the
items
are
arranged
in
decreasing
order
of
their
sizes
to
impro
v
e
the
approximation
IJECE
V
ol.
9,
No.
1,
February
2019
:
512
–
524
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
517
ratio.
The
approximation
ratio
of
both
these
techniques
is
<
2
.
Algorithms
3
and
4
describe
these
tw
o
tech-
niques.
Algorithm
3
First
Fit
Decreasing
Algorithm
Item
Set
(1
;
2
;
::n
)
is
arranged
in
decreasing
order
of
their
sizes.
a
1
a
2
:::
a
n
f
or
i
=
1
to
n
do
f
or
j
=
1
to
m
do
if
Item
i
with
size
a
i
fits
in
Bin
S
j
then
Place
the
item
a
i
in
Bin
S
j
.
j
+
+
end
if
if
Item
i
does
not
fit
in
Bin
S
j
then
j
+
+
end
if
end
f
or
if
Item
i
does
not
fit
in
an
y
Bin
then
Open
a
ne
w
bin
and
place
the
item
in
it.
m
=
m
+
1
end
if
end
f
or
Algorithm
4
Best
Fit
Decreasing
Algorithm
Item
Set
(1
;
2
;
::n
)
is
arranged
in
decreasing
order
of
their
sizes.
a
1
a
2
:::
a
n
Let
r
1
=
V
0
;
r
2
=
V
0
;
::r
m
=
V
0
be
the
initial
residual
capacity
of
each
bin.
f
or
i
=
1
to
n
do
f
or
j
=
1
to
m
do
if
Item
i
with
size
a
i
fits
in
Bin
S
j
then
Calculate
scor
e
ij
=
r
j
a
i
j
+
+
end
if
end
f
or
Fit
item
i
into
that
bin
j
which
has
the
lo
west
scor
e
ij
.
r
j
=
r
j
a
i
if
Item
i
does
not
fit
in
an
y
Bin
then
Open
a
ne
w
bin
and
place
the
item
in
it.
m
=
m
+
1
end
if
end
f
or
In
the
simplified
model,
since
only
single
dimension
is
considered
(e.g.,
CPU
usage),
VMs
could
be
ordered
according
to
its
resource
requirement.
In
a
complicated
model,
se
v
eral
dimensions
are
considered
to
establish
a
ranking
amongst
the
set
of
VMs.
The
ranking
is
established
in
the
follo
wing
manner
.
(a)
The
v
olume
of
a
VM
is
calculated
by
mult
iplying
its
demands
in
all
dimens
ions
(by
emplo
ying
the
v
olume
method).
(b)
The
rank
of
each
VM
is
determined
with
respect
to
a
reference
host
which
is,
normally
,
the
least
occupied
acti
v
e
host
or
the
last
one
to
be
acti
v
ated.
In
this
approach,
during
rank
calculation,
the
VM
placement
problem
can
be
modeled
as
an
instance
of
the
0-1,
or
Binary
,
Knapsack
Problem
[17].
Bin
pac
king
algorithms
for
virtual
mac
hine
...
(K
umar
aswamy
S)
Evaluation Warning : The document was created with Spire.PDF for Python.
518
ISSN:
2088-8708
F
or
complicated
model,
directly
we
can
not
apply
the
FFD,
generalization
of
FFD
algorithm
is
essential.
Con-
v
ersion
of
multi
dim
ension
in
to
single
dimension
is
done.
Such
FFD
algorithms
are
called
FFD-based
algo-
rithms.
Research
in
Refs.
[22]
considers
V
irtual
Machine
Monitor
(VMMs)
CPU
c
ycles
and
migration
o
v
er
-
head
in
designing
VMP
problem,
to
maximize
the
performance
of
applications
and
reduce
the
number
of
PMs.
The
e
v
aluation
of
the
problem
is
done
in
three
dif
ferent
FFD
based
heuristics
viz.
Dot
Product,
Euclidean
Distance
and
Resource
Imbalance
V
ector
method.
It
reduces
the
number
of
migrations
by
more
than
84%.
Authors
[23]
considered
deterministic
resources
viz.,
CPU,
memory
,
po
wer
consumption
and
netw
ork
bandwidth
as
a
stochastic
resource
for
formulating
Multi-Dimensional
Stochastic
V
irtual
Machine
Placement
Problem
(MSVP).
Since
it
is
a
NP-hard
problem,
authors
proposed
polynomial
time
algorithm
called
Max-
Min
Multi-Dimensional
Stochastic
Bin
P
acking
(M3SBP)
to
maximize
the
minimum
utilizati
on
ratio
of
all
the
resources
of
a
PMs
in
lar
ge
scale
data
centers.
This
algorithm
is
inspired
by
First
Fit
Decreasing
(FFD)
and
Dominant
Resource
First
(DRF)
This
paper
[24]
used
data
model
for
each
VM,
the
data
model
accurately
gi
v
es
the
resource
usage
of
the
VM.
Based
on
this
forecast,
VM
placement
algorithm
with
po
wer
-a
w
are
BFD
heuristic
algorithm
is
designed.
The
simulation
results
of
this
algorithm
sho
w
the
ef
fecti
v
e
reduction
in
po
wer
consumption,
number
of
VM
migrations,
and
pre
v
ent
SLA
violations.
Authors
[25]
proposed
the
ener
gy-ef
ficient
and
QoS
a
w
are
VM
placement
(EQVMP)
mechanism.
This
mechanism
is
a
combination
of
three
modules
viz.,
hop
reduction,
ener
gy
sa
ving
and
load
balancing.
The
ener
gy
sa
ving
module
uses
VM
placement
technique
inspired
by
Best-Fit
Decreasing
(BFD)
and
max-min
multi-dimensional
stochastic
bin
packing
(M3SBP),
so
that
it
minimizes
the
number
of
serv
er
in
the
datacenter
without
SLA
violation
In
[26],
the
First
Fit
Decreasing
algorithm
is
used
to
solv
e
the
VMP
problem.
In
this,
for
each
bin
priority
is
pro
vided.
The
highest
priority
bins
consume
too
man
y
resources
or
too
fe
w
resources.
So,
the
virtual
machines
in
these
bins
will
be
subjected
to
placement.
4.4.
Other
Heuristics
Fe
w
of
the
authors
consider
dif
fer
ent
packing
t
yp
e
for
VM
consolidation
in
their
w
orks.
F
or
e.g.,
in
Ref.
[5],
authors
consider
consolidation
problem
as
a
r
andom
variable
pac
king
problem
with
bandwidth
constraints,
and
solv
e
it
by
approximation
algorithm.
Ref.
[10]
considers
VM
consolidation
problem
as
multi-
capacity
stochastic
bin
packing
problem.
It
proposes
heuristic
method
in
order
to
increase
the
ef
ficienc
y
of
placement
algorithm.
[9]
propose
similar
w
ay
of
VM
placement
using
bin
packing,
to
increase
resource
utiliza-
tion
and
profit
of
C
SP
.
Fe
w
authors
also
consider
the
Ne
xt
Fit
(NF)
approach,
in
which
the
VM
is
placed
into
the
current
PM
(if
VM
resource
demands
are
satisfied
in
current
PM),
otherwise
ne
w
PM
is
started.
It
pro
vides
performance
ratio
of
2.
In
the
paper
[5],
authors
suggest
ener
gy
sa
ving
by
minimizing
the
number
of
idle
resources
in
a
cloud
computing
en
vironment.
It
has
been
achie
v
ed
by
f
ar
-reaching
e
xperiments,
so
as
to
quantify
the
performance
of
the
suggested
algorithm.
The
same
has
also
bee
n
compared
with
the
FCFSMaxUtil
and
Ener
gy
a
w
are
T
ask
Consolidation
(ETC)
algorithm.
The
outcomes
ha
v
e
sho
wn
that
the
suggested
algorithm
surpass
the
FCFSMaxUtil
and
ETC
algorithm
in
terms
of
the
CPU
utilization
and
ener
gy
consumption.
According
to
Mark
o
v
Decision
Proces
s
(MDP)
and
based
on
reinforcement
learning
for
auto-scaling
resources,
authors[27]
propose
an
automatic
resource
pro
visioning
system.
Proposed
system
simulation
re-
sults
sho
ws
bett
er
performance
when
compared
to
similar
approaches
with
respect
to
rate
of
Service
Le
v
el
Agreement
(SLA)
violation
and
stability
.
The
authors
[28]
proposed
optimal
technique
based
on
four
-adapti
v
e
threshold
model
to
reduce
ener
gy
consumption.
Hosts
are
clustered
into
fi
v
e
clusters
using
K-Means
Clustering
algorithm
viz.,
1.
Hosts
with
lo
w
load
2.
Hosts
with
light
load
3.
Hosts
with
middle
load
4.
Hosts
with
hea
vy
load
and
5
hosts
with
hea
vy
load.
VMs
are
migrated
between
these
clusters
on
the
basis
threshold
v
alues
using
mathematical
modeling
approach
to
reduce
ener
gy
consumption.
T
able
2
summarizes
the
already
discussed
heuristics
in
pre
vious
section
by
comparing
their
basi
c
at-
trib
utes
lik
e:
the
problem
type,
the
type
of
heuristics
used,
the
objecti
v
e
type
(ener
gy
or
bandwidth
or
QoS
a
w
are),
type
of
placement,
and
finally
objecti
v
e
function
composite
or
single.
IJECE
V
ol.
9,
No.
1,
February
2019
:
512
–
524
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
519
T
able
2.
Bin
P
acking
Algorithms
Surv
e
yed
P
aper
Pr
oblem
type
Heuristics
Ener
gy
awar
e
Band
width
awar
e
QoS
awar
e
Static/
Dy-
namic
place-
ment
Objecti
v
e
function
[25]
Ener
gy-ef
ficient
and
QoS
a
w
are
VMP
problem
BFD
Y
es
Y
es
Y
es
Dynamic
Dynamic
[24]
Cloud
serv
er
consolidation
problem
BFD
Y
es
No
Y
es
Dynamic
Composite
[18]
Po
wer
-ef
ficient
VM
placement
and
migration
problem
FF
,BF
,WF
Y
es
Y
es
No
Dynamic
Composite
[17]
multi-
dimensional
resource
con-
straints
packing
problem
BF
based
Y
es
Y
es
No
Dynamic
Composite
[15]
multile
v
el
gener
-
alized
assignment
problem
(MGAP)
FF
No
Y
es
Static
and
Dy-
namic
single
no
[14]
Dynamic
re-
source
allocation
problem
FF
N
A
No
Y
es
Dynamic
Single
[22]
N
A
FFD-based
N
A
No
Y
es
Dynamic
Single
[23]
multi
dimen-
sional
stochastic
VM
Placement
MSVP
FFD-based
N
A
Y
es
Y
es
Dynamic
Single
[10]
multi-capacity
stochastic
bin
packing
opti-
mization
problem
Hierarchical
based
Y
es
Y
es
No
Dynamic
Composite
[5]
VM
consolida-
tion
problem
Random
V
ariable
P
ack-
ing(R
VP)
No
Y
es
No
Dynamic
Composite
[9]
Deterministic
bin
packing
W
orst
Fit
Y
es
No
Y
es
Static
N
A
[26]
VM
consolida-
tion
problem
for
po
wer
sa
ving
e
xtended
FFD
Y
es
No
No
rank-
based
N
A
Bin
pac
king
algorithms
for
virtual
mac
hine
...
(K
umar
aswamy
S)
Evaluation Warning : The document was created with Spire.PDF for Python.
520
ISSN:
2088-8708
5.
CHALLENGES
OF
BP
ALGORITHMS
Some
of
the
important
challenge
of
BP
algorithms
are
discussed
as
follo
ws.
(a)
Interference
between
items:
Due
to
the
multi-dimensional
packing
of
resources
used
by
se
v
eral
VMs
at
same
t
ime,
there
is
content
ion
for
resources
among
VMs.
There
may
be
af
finity
between
tw
o
VMs
due
to
which
the
y
may
be
required
to
be
placed
together
.
There
can
be
v
arious
possible
reasons
for
such
af
finity
.
F
or
e
xample,
the
netw
ork
traf
fic
between
tw
o
communicating
VMs
may
suggest
that
the
y
be
placed
together
so
as
to
reduce
the
netw
ork
o
v
erheads.
There
may
be
b
usiness
constraints
lik
e
the
requirement
of
web-serv
er
and
database
layers
to
be
together
.
The
contention
may
af
fect
the
performance
of
co-located
VMs.
There
are
se
v
eral
approaches
that
ha
v
e
been
proposed
to
miti
g
ate
the
ef
fect
of
contention
such
as
resource
isolat
ion
among
VMs
and
optimal
mapping
of
VMs
and
PMs.
There
could
also
be
interference
between
tw
o
VMs
which
requires
that
the
y
should
not
be
placed
together
.
This
may
be
due
to
technical
constraints.
F
or
e
xample,
say
there
is
a
resource
(some
remote
data
center)
mirrored
at
tw
o
places,
that
the
tw
o
VMs
need
to
access.
The
VMs
are
pro-
grammed
to
access
the
nearest
resource.
No
w
,
there
may
be
a
technical
requirement
to
k
eep
the
tw
o
VMs
separately
,
so
that
the
y
do
not
access
the
same
cop
y
.
There
may
be
a
disk
contention:
tw
o
VMs
trying
to
access
the
same
data
on
disk.
Interference
can
also
be
due
to
b
usiness
constraints
lik
e
not
k
eeping
VMs
of
competi
tors
together
.
Or
,
s
o
that
one
of
the
VM
remains
a
v
ailable
e
v
en
if
the
ph
ysical
host
hosting
the
other
VM
f
ails.
(b)
Item
size
and
bin
size:
VM
capacity
cannot
be
al
w
ays
static
o
v
er
its
lifetime
due
to
SLAs.
Dy-
namic
size
of
VM
can
be
considered
in
BP
based
algorithm.
This
is
also
true
for
bin/PM
size.
F
or
v
ariable-sized
BP
,
there
are
man
y
open
questions.
In
terms
of
asymptotic
w
orst-case
ratio,
follo
wing
question
arises:
i.
which
combination
of
sizes
produces
the
smallest
w
orst-case
ratio?
ii.
what
can
be
said
about
the
problem
with
at
least
three
bin
sizes?
iii.
in
terms
of
absolute
w
orst-case
ratio,
what
is
a
lo
wer
bound
for
of
f-line
algorithms?
i
v
.
ho
w
to
design
an
optimal
on-line
algorithm?
(c)
P
artial
packing:
Existing
research
w
orks
do
not
discuss
filling
PMs/bins
in
optimal
w
ay
,
lea
ving
lar
ge
resource
fra
g
m
ents
or
residue.
Hence,
resources
are
underutilized.
Better
BP
algorithms
need
to
be
designed
so
to
a
v
oid
resource
fragments.
(d)
No
migration:
most
of
BP
based
w
orks
doesn’
t
supports
migration
in
VMs.
T
asks
cannot
be
relo-
cated
once
the
y
ha
v
e
been
allocated
to
an
y
processor
(i.e.
no
migration).
6.
PERFORMANCE
EV
ALU
A
TION
In
this
section,
the
simulation
analysis
results
for
analyzing
the
relati
v
e
performance
of
dif
ferent
VMP
algorithms
are
presented.
The
simulation
w
as
carried
out
through
open
source
simulation
tool
kit:
CloudSim.
T
w
o
performance
metrics
are
utilized
in
simulation
study:
No
of
Se
v
ers
and
CPU
utilization.
The
first
metric
indicates
the
number
of
serv
ers
on
which
all
the
VMs
are
running.
It
is
clear
that,
less
number
of
serv
ers
indicate
that,
ef
ficient
resource
utilization
has
been
achie
v
ed.
The
second
metric
indicates
the
total
CPU
utilization
in
the
cloud
serv
er
.
Higher
v
alues
of
CPU
utilization
indicates
that,
proper
resource
utilization
is
being
achie
v
ed.
The
simulation
analysis
results
w
.r
.t.
no
of
serv
ers
is
illustrated
in
Figure
2.
It
is
clear
that,
FF
,
FFD
and
Max-Min
algorithms
achie
v
e
the
maximum
perform
ance,
mainly
due
to
the
theoretical
performance
bounds
establ
ished
for
thes
e
algorithms.
Sim
ilarly
,
NF
and
S-NF
achie
v
e
poor
performance
mainly
due
to
lack
of
ef
fecti
v
e
theoretical
performance
bounds.
Figure
3
illustrates
the
simulation
analysis
results
w
.r
.t.
CPU
utilization.
All
the
VMP
techniques
sho
w
similar
performance,
mainly
due
to
their
primary
design
focus
of
on
achie
ving
ef
ficient
CPU
utilization.
From
this
simulation
study
,
it
can
be
inferred
that,
FF
,
FFD
and
Max-Min
are
the
most
f
a
v
orable
techniques
for
achie
ving
ef
ficient
load
balancing
in
cloud.
IJECE
V
ol.
9,
No.
1,
February
2019
:
512
–
524
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
521
0.5%_mean
1%_mean
300
350
400
450
500
NF
FF
FFD
MaxMin
S−NF
S−FF
S−FFD
Number of servers
Algorithms
Figure
2.
Number
of
serv
ers
vs
placement
algorithms
Server_1
Server_2
Server_3
Server_4
Server_5
Server_6
0
20
40
60
80
100
EBFA
BFA
FFA
NFA
% of CPU Utilization
Algorithms
Figure
3.
%
of
CPU
utilization
vs
placement
algorithms
7.
DISCUSSIONS
FOR
FUTURE
DIRECTIONS
This
section
pro
vides
VMP
schemes
that
can
be
considered
for
the
Cloud
en
vironment
in
the
future,
with
respect
to
the
follo
wing
issues.
(a)
Consideration
of
appropriate
schemes.
(b)
VM
placement
f
actors
consideration.
(c)
Resource
consideration.
(d)
Po
wer
,
cost
and
netw
ork
related
f
actors.
7.1.
Resour
ce-awar
e
VMP
schemes
Managing
virtual
resource
is
an
important
issues
in
Cloud
computing.
Normally
,
for
job
e
x
ecution,
VM
may
require
v
arious
resources.
Resource-a
w
are
VMP
schemes
are
responsible
for
considering
the
resource
requirements
(hardw
are
etc.)
of
the
VMs
in
the
placement
decisions.
The
optimized
placement
of
VMs
on
the
PMs
can
be
achie
v
ed
through
ef
ficient
resource-a
w
are
placement
scheme.
Resource
contention
amongst
multiple
co-hosted
neighboring
VMs
ensures
maximum
resource
utilization
in
this
scheme.
Bin
pac
king
algorithms
for
virtual
mac
hine
...
(K
umar
aswamy
S)
Evaluation Warning : The document was created with Spire.PDF for Python.