Comparing VM-Placement Algorithms for On-Demand Clouds 

K. Mills, J. Filliben and C. Dabrowski 

Information Technology Laboratory 

NIST 

Gaithersburg, MD USA 

{kmills, jfilliben, cdabrowski}@nist.gov 

Abstract—Much recent research has been devoted to 

investigating algorithms for allocating virtual machines (VMs) 

to physical machines (PMs) in infrastructure clouds. Many 

such algorithms address distinct problems, such as initial 

placement, consolidation, or tradeoffs between honoring 

service-level agreements and constraining provider operating 

costs. Even where similar problems are addressed, each 

individual research team evaluates proposed algorithms under 

distinct conditions, using various techniques, often targeted to 

a small collection of VMs and PMs. In this paper, we describe 

an objective method that can be used to compare VMplacement algorithms in large clouds, covering tens of 

thousands of PMs and hundreds of thousands of VMs. We 

demonstrate our method by comparing 18 algorithms for 

initial VM placement in on-demand infrastructure clouds. We 

compare algorithms inspired by open-source code for 

infrastructure clouds, and by the online bin-packing literature. 

Keywords- cloud computing; resource allocation; simulation 

I. INTRODUCTION

Paxson and Floyd [1] describe many difficult problems 

impeding simulation of large data communication networks, 

which typically require hundreds of parameters that can each 

take on millions of values and that can also record hundreds 

of response variables, which might represent aspects of 

fewer significant underlying behaviors. The same can be said 

for most simulations of large distributed systems, such as ondemand infrastructure clouds. 

We have developed an objective method to compare 

resource-allocation algorithms in simulations of large 

distributed systems. Our method involves several steps: (1) 

developing a reduced-parameter model for a large distributed 

system of interest, (2) conducting a sensitivity analysis to 

determine the most significant model behaviors and the 

parameters that most influence those behaviors, (3) applying 

two-level orthogonal fractional factorial experiment design 

[2] to construct a set of parameter combinations under which 

resource-allocation algorithms should be compared and (4) 

using multidimensional data analysis techniques to find 

patterns revealing significant similarities and differences 

among the algorithms being compared. In previous work [3-

4], we applied our method to compare proposed congestioncontrol algorithms for the Internet. Also in previous work 

[5], we demonstrated the first two steps in our method, when 

applied to on-demand infrastructure clouds. We constructed 

a reduced-parameter model (explained below in Sec. III) and 

we conducted a sensitivity analysis that revealed eight 

behavioral dimensions and six influential parameters. 

In this paper, we demonstrate steps three and four in our 

method, using the results from our sensitivity analysis to 

construct 32 parameter combinations under which we 

compare the macroscopic behavior of 18 possible algorithms 

for initially placing virtual machines (VMs) on physical 

machines (PMs). Our comparative conditions encompasses 

cases with up to O(104

) PMs and O(105) VMs. While there 

are many possible algorithms to investigate (as explained 

below in Sec. II), we elected to focus on algorithms inspired 

by a combination of the Eucalyptus open-source code [6] and 

the online bin-packing literature [7-8]. Eucalyptus inspired 

us to evaluate two-level algorithms that first choose a cluster 

for VMs in a related request and then choose nodes within 

the selected cluster. The literature for online bin-packing 

inspired us to adopt algorithms based on well-known 

heuristics that can provide good (not optimal) results without 

infeasible computation. 

Our paper makes three main contributions. First, we 

demonstrate an objective method for comparing possible 

VM-placement algorithms through simulation of large, ondemand infrastructure clouds. While we restrict our 

comparison to 18 selected algorithms, the approach we use 

should be applicable to compare any set of competing 

algorithms. Second, we generate some insights regarding 

two-level VM-placement algorithms, showing that choice of 

cluster has larger influence, than choice of nodes, on 

macroscopic behavior in an infrastructure cloud. We also 

provide observations about specific pairs of algorithms, 

where each pair combines a criterion for choosing a cluster 

with a heuristic for choosing PMs within a cluster. We also 

discuss some tradeoffs among algorithms. Third, we provide 

evidence showing that, on average, different algorithms for 

initial VM placement in on-demand infrastructure clouds 

yield only small quantitative differences in many of the 42 

responses we measured (as explained below in Sec. IV). On 

the other hand, we show that selection of the algorithm for 

choosing a cluster can lead to very large difference in 

provider revenue, when aggregated over time. 

The remainder of this paper is organized as follows. In 

Sec. II we describe the general area of VM-placement 

research in infrastructure clouds, setting our study within this 

larger context. In Sec. III we describe our model and identify 

both fixed and varied parameters used in our study. We give 

values for fixed parameters, but postpone defining values for 

variable parameters until Sec. IV, where we describe our 

experiment design. In Sec. V we present our results and 

related analysis methods. In Sec. VI we discuss our findings. 

We close in Sec. VII with conclusions and future work. 

2011 Third IEEE International Conference on Coud Computing Technology and Science

978-0-7695-4622-3 2011

U.S. Government Work Not Protected by U.S. Copyright

DOI 10.1109/CloudCom.2011.22

91
II. RELATED WORK

The literature identifies that VM-placement decisions can 

be made under any of at least three different regimes [9]: (1) 

reservations [10-11], (2) on-demand access [11] and (3) spot 

markets [10-12]. In one reservation regime [11], a user pays 

a fee per instance per VM type for a period (e.g., one year) 

during which the specified VMs may be acquired at a 

discount from published usage charges. In on-demand access 

regimes, a user simply requests a specified number of one or 

more VM types needed immediately, and pays for VM usage 

according to a fixed schedule of fees. In spot markets, a 

provider’s prices fluctuate over time and a user specifies the 

usage rates they are willing to pay for requested VMs. When 

the provider price falls to or below the user’s willingness to 

pay, then the user’s requested VMs are launched. Should the 

provider price subsequently rise above the user’s willingness 

to pay, then the user’s VMs are terminated, and can only be 

restarted when the price falls to the level the user is willing 

to pay. In the grand scheme of resource-allocation decision 

making, one can envision PMs migrating back and forth 

among three pools, each assigned to one of the three regimes, 

as demand for VMs varies. Consideration of how best to 

allocate PMs to each pool would seem a ripe area for 

research [9]. We restrict our study to consider only ondemand access. 

In on-demand clouds, there are potentially two types of 

VM-placement decisions to be made: (1) initial placement 

[13-23] and (2) migration (and/or resizing) of VMs over time 

[24-30], as PM availability changes, as consolidation is 

needed to conserve power and in response to the degree to 

which service-level agreements (SLAs) are being achieved. 

Most previous research on initial VM placement considered 

only PMs within a single cloud, but in one case [22] 

placement decisions considered which of several clouds to 

choose. In the existing literature, initial placement and VM 

migration are usually considered as separate topics, though 

in some cases similar algorithms may be adopted. Future 

research might consider interaction between initial placement 

and migration decisions, especially under situations where 

tradeoffs are needed among power conservation, SLAs, 

revenue maximization and reliability. We restrict our study 

to consider only initial VM placement. 

One could consider initial VM placement in on-demand 

clouds at two levels: (1) cluster and (2) node (i.e., PM). 

When VMs communicate, placing them on the same cluster 

makes good sense because communication among the VMs 

will be local to a cluster switch. Most existing research [13-

23] considers PMs as an unstructured pool, where restricting 

VMs to a shared cluster would be accomplished by 

designating a Boolean attribute, one of potentially many 

attributes over which some optimization algorithm or binpacking heuristic would be executed. In our study, guided by 

the open-source code in Eucalyptus (v1.6) [6], we adopt 

explicit use of two distinct decisions levels: (1) choosing a 

cluster for all VMs in a given request and then (2) choosing 

specific PMs within the selected cluster. Taking this course 

is the same as assuming that all VMs within a single request 

will communicate. VMs that need not communicate would 

then be included in separate requests. 

In most VM placement algorithms, PMs are partitioned 

into two sets: (1) those that meet some criteria and (2) those 

that do not. Subsequently, the set of PMs that meet the 

criteria are ordered, and VM placement attempts are made 

starting with the first PM on the list, and continuing until all 

VMs have been placed or until the set of qualified PMs is 

exhausted. Various criteria have been used to order qualified 

PMs. For example, many researchers [13, 16, 18, 23, 27] 

adopt ordering heuristics based on the literature associated 

with online bin packing [7-8]. Other schemes extend those 

heuristics by adding specific attributes (e.g., CPU usage, 

network and disk controller usage, and memory usage), 

summarized into a weighted value used to order PMs or to 

assign categories (e.g., star ratings [15]) that can be used to 

order PMs. In some schemes, attributes used to order PMs 

are determined by individual VM users [23, 30, 31], while in 

other schemes attributes are determined by the provider [13, 

14, 19, 27], or user and provider attributes are combined [21, 

22, 23, 26]. To limit our study, we elected to use heuristics 

based on those found in online bin-packing literature. The 

method we use to compare placement heuristics should be 

applicable to any specific set of VM-placement algorithms 

that one wishes to compare. 

III. MODEL

We based our study on Koala, a discrete-event simulator 

inspired by the Amazon Elastic Compute Cloud (EC2)1

 [32] 

and by the Eucalyptus open-source software [6]. Using 

published information describing the EC2 application 

programming interface (API) [33] and available virtual 

machine (VM) types [34], Koala models essential features of 

the interface between users and EC2. Intended to study 

algorithms for initial VM placement, Koala models only four 

EC2 commands: RunInstances, DescribeInstances, Reboot 

Instances and TerminateInstances. The internal structure of 

Koala is based on the Eucalyptus (v1.6) open-source cloud 

software. Specifically, Koala models three Eucalyptus 

components: cloud controller, cluster controller and node 

controller. As in Eucalyptus, Koala’s simulated cloud, 

cluster and node controllers communicate using Web 

Services [35], which Koala also simulates. 

Koala modifies the design of Eucalyptus in three ways. 

First, Koala extends the Eucalyptus RunInstances command 

to allow multiple VM types within a single request, which 

appears possible in EC2. Second, Koala avoids centralization 

of node information at the cloud controller, permitting 

simulation of clouds up to O(105

) nodes. Third, Koala allows 

competing RunInstances to proceed partially in parallel 

(serializing only the commitment phase), which prevents 

long queuing delays during periods of intense user requests. 

In lieu of simulating details of a hypervisor and guest VMs, 

Koala includes an optional sub-model based on analytical 

equations representing VM behavior with or without tasks. 

 1

 Any mention of commercial products is for information only; it does not 

imply recommendation or endorsement by NIST. 

92
la

I

d

w

d

x

A

u

c

r

o

ty

ty

s

r

m

in

th

c

in

r

a

th

p

m

a

a

f

in

r

o

r

in

(

n

f

Koala is org

ayer, (2) sup

Internet/Intrane

describe each l

which is not u

denote experim

x6 (see Table V

Fi

A. Demand La

The demand

users who, af

cyclically over 

requests a mini

one or more o

ypes and quan

ype (see Tabl

some probabil

randomly choo

maximum (uni

nstances to req

hen issues a 

cloud controlle

nstances betw

requested VM 

available) fault.

he maximum 

partial grant d

maximum requ

a holding time, 

a parameter (x

first issue Desc

nstances are 

reboot, termina

of the holding 

request to stop 

nstances, the u

(mean 30 minut

Since we b

not germane di

for each stocha

ganized as five

pply layer, (3

et layer and 

ayer in turn, om

used in the ex

ment input para

V) and outputs a

gure 1. Schematic

ayer

d layer consist

fter random 

a simulation 

imum and max

f the VM type

ntities a user s

e II), which i

lity (x2). Aft

ses a minimum

iform max-mi

quest for each 

corresponding

er, which may 

ween the minim

type or with a

. A full grant d

requested ins

denotes that al

uested. If given

Pareto distribu

3). During the

cribeInstances

running, and 

ate and describ

period, the us

any running i

user will wait an

tes) and then st

believed differe

irectly to our s

astic distributio

e layers (see Fig

3) VM place

(5) VM beha

mitting the VM

xperiments disc

ameters using d

as y1 to y42 (se

 of Koala organiza

ts of a variable

startup delay

run. During e

ximum numbe

es shown in T

selects depend

s selected on 

ter selecting 

m (uniform 1 to

n to a max-m

associated VM

g RunInstances

respond with 

mum and max

a NERA (not e

denotes that a u

stances of eac

llocated VMs 

n VM instances

uted with varia

e holding perio

requests to de

will subsequ

e running insta

ser issues a Te

instances. Afte

n exponentially

tart a new cycle

ences in user 

study, we assig

on controlling r

g. 1): (1) dema

ment layer, (

avior layer. W

M behavior lay

cussed here. W

designators x1

ee Table VI). 

ation

e number (x1)

y, each perfo

each cycle a u

er of instances 

Table I. The V

upon the use

each cycle w

a type, a u

o a max-min) a

max) number 

M type. The us

s request to t

an allocation 

ximum for ea

enough resourc

user was allocat

ch VM type. 

were below t

s, the user sele

ables specified 

od, the user w

termine when 

uently random

ances. At the e

rminateInstanc

er terminating 

y distributed tim

e.

persistence we

gned fixed mea

related behavio

and

(4) 

We

yer,

We

to 

of

rm

ser

of

VM

er’s 

with 

ser

and 

of

ser

the

of 

ach 

ces 

ted

A

the 

cts 

by 

will

all 

mly 

end 

ces

all

me

ere 

ans

ors.

If a u

instanc

time (m

will ret

hours) b

a user r

rest per

starts a 

TABLE

(PU), dis

users, We

TABLE I

B. Supp

The

clusters

When v

supply 

platform

set of 

creation

one of 

their e

simulat

resourc

specifie

user receives 

es, then the u

mean 15 minut

try a failed re

before resting 

request cannot 

riods (mean 4),

new cycle. 

TABLE I. Descr

II. Description of

stributed modeling

eb service (WS) u

III. Description of

pply Layer

e supply layer 

s that each man

visiting an Am

of nodes wa

m configuratio

possible platf

n, each node m

the configurat

established co

tion run. For a 

ces on the node

ed by the VM’s

a NERA inst

user waits an 

tes) before retr

equest over a 

for a random p

be honored wi

, then the user 

ription of VM type

f selected simulate

g and simulation 

users, and data sear

f selected platform 

consists of a 

nages a variab

mazon EC2 dat

as composed o

ons. This motiv

form configur

manifests, wit

tions shown in

onfigurations 

VM to be allo

e must be suffic

s type.

tead of being

exponentially 

rying the reque

random perio

period (mean 1

ithin a random 

abandons the r

es simulated in Ko

ed user types: pro

(MS) users, peer

rch (DS) users 

types simulated in

variable numb

ble number (x5

ta center, we n

of a limited n

vated us to def

rations for no

th some proba

n Table III. No

for the dura

cated to a node

cient for the re

g allocated 

distributed 

est. A user 

d (mean 4 

6 hours). If 

number of 

request and 

oala 

ocessing users 

r-to-peer (PS) 

n Koala 

ber (x4) of 

5) of nodes. 

noticed the 

number of 

fine a fixed 

odes. Upon 

ability (x6),

odes retain 

ation of a 

e, available 

quirements 

93
C

p

c

n

w

c

u

c

a

T

H

c

V

s

(

le

c

V

w

(

s

c

c

th

in

u

c

n

N

m

b

o

th

w

th

o

f

q

r

n

c

g

a

f

C. VM Placem

Koala pat

procedures, wh

cluster should 

nodes within th

we compare th

controller to ch

used by cluster 

criteria and heu

algorithms we c

TABLE IV. Alter

Heuristics for Choo

In Eucalyp

controllers to f

VMs requested

some criterion 

(LFF) criterion

east to most 

criterion orders

VMs that can b

were ordered b

(RAN) criterion

After orderi

selects the firs

created. If VM

controller retur

he cloud contr

n the set. This

until all cluste

create the VMs

In Eucalypt

nodes using on

Next-Fit (NF). 

more heuristics

bin-packing lite

ordered by iden

hat can accom

which node las

he next node i

of qualified nod

from least to m

qualified nodes

randomly the se

nodes by VM 

can be placed

generates a s

appropriate VM

free (i.e., unma

ment Layer 

tterns VM 

hich involve 

requested VM

he cluster shoul

hree alternativ

hoose a cluste

controllers to 

uristics creates 

compare. 

rnative Criteria fo

osing Nodes 

ptus, the clo

find out which 

d and then ord

(Table IV – l

n orders the set

full, while t

s the set by dec

be allocated.

by increasing c

n orders random

ing the qualifie

st cluster in th

Ms are created

rns the positive

roller reallocat

s process conti

ers have been 

, then the user 

tus, the cluste

ne of two heur

Koala simulat

s (Table IV – 

erature. FF sea

ntifier from fir

mmodate a giv

st received a V

identifier. Leas

des (i.e., nodes

ost full. Most-F

s from most to 

et of qualified 

type, so that o

d on marked 

set of qualifi

M type, and then

arked) qualified

placement af

two decisions

Ms be placed a

ld VMs be plac

ve criteria use

r and six alter

choose nodes. 

the (3 x 6 =) 1

for Choosing Clu

oud controlle

clusters can a

ers the qualifie

left side). The 

t of qualified c

the Percent A

creasing propor

(Under both th

cluster identifie

mly the set of q

ed clusters, the

he set and as

d successfully,

e result to the

tes the VMs to

inues until VM

exhausted. If

receives a NER

er controller a

ristics: (1) Firs

tes FF and NF

right side) in

rches the clust

rst to last, until

ven VM type.

VM and begins

st-Full First (L

 on which the V

Full First (MF)

least full. Ran

nodes. Tag & 

only VMs of a

nodes. To pl

ied nodes m

n adds to the en

d nodes. The V

fter Eucalypt

s: (1) on whi

and (2) on whi

ced. In this stud

ed by the clo

rnative heurist

Combining the

8 VM-placeme

uster and Alternat

er polls clus

accommodate t

ed clusters usi

Least-Full Fi

clusters from t

Allocated (PA

rtion of request

hese criteria, t

er.) The Rando

qualified cluste

e cloud control

ks that VMs 

, then the clo

 user; otherwi

o the next clus

Ms are created 

f no clusters c

RA fault. 

allocates VMs 

st-Fit (FF) or (

F, as well as fo

nspired by onli

ter’s set of nod

l a node is fou

. NF remembe

s its search fro

LF) orders the 

VM type will f

) orders the set

dom (RA) orde

Pack (TP) mar

a designated ty

lace a VM, T

marked with t

nd of that set a

VM is then plac

tus 

ich 

ich

dy,

oud

ics 

ese 

ent 

tive 

ster

the

ing

irst

the 

AL) 

ted

ies 

om

ers. 

ller

be

oud

ise, 

ster

or

can

to 

(2)

our

ine

des,

und 

ers

om

set

fit)

t of 

ers 

rks

ype

TP

the 

any 

ced

on the f

TP mar

the last

remove

For

accomm

VM to 

the VM

the min

then the

D. Inte

Koa

users to

on a g

consiste

cloud a

number

same si

each us

sites (9

arrange

categor

(Intrane

simulat

compri

packets

delay (

For in

distanc

within 

Individ

for intr

loss ra

range (

only fo

which t

We 

each of

where e

shown 

in an e

signific

we sele

32 par

orthogo

selects

balance

the 18 V

We 

to 42 re

six cate

wide re

utilizati

messag

only ei

represe

first node in th

rks the node w

t VM on a nod

ed. 

r any of the 

modate a VM, 

the next node 

M is created or 

nimum request

e cloud control

ernet/Intranet L

ala assigns the 

o sites (1000 he

grid (8000x80

ent with the g

and cluster con

r (1 here) of si

ite as the relate

ser cycle, a us

999 here) not 

ement divides 

ries: (1) inte

et). Koala 

ted Web Ser

se a uniformly

s. Individual p

(1 Gigabits pe

nter-site messa

e and simulate

sites varies ra

dual packets are

ra-site packets)

ate for inter-si

(10-3 to 10-8 he

or a maximum

the related WS

IV.

e compared 18 

f them to the sa

each paramete

in Table V. T

earlier sensitiv

cant drivers of K

ected two valu

rameter combin

onal fractional

1⁄2 of the 26

ed coverage. W

VM-placement

e compared the 

esponse variab

egories represe

esource utiliza

ion and load, (

ge load and (6)

ight significant

ented using a su

he set. If the se

with the appropr

de is terminate

heuristics, if 

then the node 

in the set. Thi

until all nodes

ted number of

ller receives a N

Layer

cloud controll

ere) randomly 

000 miles her

globe. Before a

ntrollers are ra

ites. Node con

ed cluster contr

ser is assigned

occupied by 

 message co

er-site (Intern

components 

rvices (WS) 

y distributed n

packets are su

er second here)

ages, propaga

ed router hops,

andomly (mean

e also subjected

). To simulate

ite packets va

ere). Lost pack

m number (3 

S message is de

EXPERIMENT

VM-placemen

ame 32 combin

er could be set 

The selected pa

vity analysis (S

Koala behavio

ues for each pa

nations by ad

l factorial exp

possible comb

We then ran 32

t algorithms. 

VM-placemen

les, as shown i

enting: (1) use

ation and load

(4) number and

) revenue. The 

t behavioral di

ubset of eight o

elected node is 

riate VM type.

ed, the node’s

a selected no

controller real

is process cont

s have been ex

f VMs cannot b

NERA fault.

er, cluster cont

located at x,y c

re) spanning

a simulation co

andomly place

ntrollers are pla

roller. At the be

d randomly to 

cloud compon

ommunications 

net) and (2) 

communicate

messages, w

number (1 to 1

ubjected to tr

) and propaga

ation delay de

, while propaga

n 250 nanoseco

d to a loss rate 

e Internet cong

aries uniformly

kets are retrans

here) of attem

clared undelive

T DESIGN

nt algorithms b

nations of six p

to one of two

arameters were

SA) [5] as the

r. Also guided 

arameter. We c

dopting a two

periment desig

binations, whil

2 simulations f

nt algorithms w

in Table VI, gr

er experience, 

d, (3) variance

d types of VM

SA found that

imensions, wh

of the 42 respon

unmarked, 

 Whenever 

marking is 

ode cannot 

llocates the 

tinues until 

xhausted. If 

be created,

trollers and 

coordinates 

a distance 

ommences, 

d on some 

aced on the 

eginning of 

one of the 

nents. This 

into two 

intra-site 

e through 

which each 

10 here) of 

ransmission 

ation delay. 

epends on 

ation delay 

onds here). 

(10-12 here 

gestion, the 

y within a 

mitted, but 

mpts, after 

erable. 

y exposing 

parameters, 

o values, as 

e identified 

e six most 

by the SA, 

constructed

-level, 26-1

gn [2] that 

le ensuring 

for each of 

with respect 

rouped into

(2) cloude in cluster 

Ms, (5) WSt Koala has 

hich can be 

nses, so we 

94
a

id

(

r

m

a

c

c

E

s

r

(

also compared 

dentify a respo

(1) cloud-wide

resource usage 

mix of VM typ

arrival rate (y4)

cluster choice (y

TABLE V. Tw

Table VI. K

The simula

containing 576

Each row was t

selection heuris

responses. We

(ANOVA) to te

Layer Param

Demand 

Layer

x

x

x

Supply

Layer

x

x

x

the 18 algorith

onse variable 

e demand/supp

(y15), (3) var

pes (y31), (5) n

), (7) reallocati

y28). 

wo Selected Values

Koala Response Va

V.

ation runs gen

6 rows and 42

tagged with the

stic and parame

e applied on

est for differenc

meter Parameter Nam

x1 Number of use

x2 Probability of 

user’s type

x3

Average (& 

shape) of user

holding time

x4 Number of 

clusters

x5

Number of 

nodes per 

cluster

x6

Probability of 

node’s platform

configuration

type

hms along those

 to represent e

ply ratio (y3),

riance in cluste

number of VM

ion rate (y7) an

s for each Selected 

ariables Selected fo

RESULTS

nerated a mul

2 columns (on

e cluster-choic

eter combinatio

ne-way analys

ces among gro

me Plus (1) Level

ers 2500

a

PU1 = 0.20

PU2 = 0.20

PU3 = 0.10

PU4 = 0.10

MS1 = 0.10

MS3 = 0.01

PS1 = 0.10

PS2 = 0.01

WS1 = 0.15

WS2 = 0.07

WS3 = 0.03

DS1 = 0.10

DS2 = 0.01

r’s 8 hours (a = 1.2)

20

1000

a

m

n C22 = 1.0

e dimensions (w

each dimensio

, (2) cloud-wi

er load (y21), (

Ms (y29), (6) us

nd (8) variance

Koala Parameter

or Comparison 

ltivariate data

ne per respons

e criterion, nod

on that led to t

sis of varian

ups of respons

Minus (-1) Level

250

PU1 = 1/6

PU2 = 1/6

MS1 = 1/6

PS1 = 1/6

WS1 = 1/6

DS1 = 1/6

4 hours (a = 1.2)

10

100

C8 = 0.25

C14 = 0.25

C18 = 0.25

C22 = 0.25

we

n):

ide

(4) 

ser

e in 

set

se). 

dethe 

nce 

es. 

For ea

statistic

grouped

groups:

where i

heuristi

appropr

corresp

for that

were di

Figure 2

Fraction 

In t

ANOV

The das

points, 

(labeled

Each bl

mean v

selectio

choice

local m

choice

value a

Below

red any

In t

value th

only (1

conclud

signific

obtaine

ANOV

data po

this ca

signific

Tab

each of

summa

ach response, 

c to measure th

d by cluster-ch

:

 

i is the clusteric, k is the par

riate F degree

ponding cumul

t F-test statistic

ifferent. 

. Plot of ANOVA

of VMs Obtained

the left hand p

VA for the ave

shed horizonta

which is 0.5

d on the x axis

lock contains s

value of the 3

on heuristic w

criterion. Belo

mean value of t

criterion, (2) t

and the grand m

the x axis we 

y value > 95%.

the example s

that would – i

100 – 99.99 =

de that cluste

cant difference

ed. In the righ

VA analysis to t

oints when the

ase, the node

cant differences

ble VII gives t

f the 42 respo

ary (col. 4) re

for example, 

he ratio of vari

hoice criterion t

 

-choice criterio

rameter combin

es of freedom.

lative distribut

c to reflect the l

A Results for Re

(red denotes signif

art of Fig. 2, w

erage fraction 

al line denotes t

576. The figur

s), one for each

six labeled poin

32 data points 

was paired with

ow each block a

the 192 data p

the difference 

mean, and (3) t

report the F c

shown, we obs

f the three gro

=) .01% of the

er-choice crite

es in the av

ht hand part o

test for differen

e node-selectio

e-selection heu

s.

two summaries

onses, one resp

eports differen

we computed

iability within 

to variability b

on, j is the nod

nation, and dfn

 We then com

tion function (

likelihood that 

esponse Variable y

ficant difference am

we show the re

of VMs obtai

the grand mean

re includes th

h cluster-choic

nts, each repre

when the lab

h the designat

are three numb

points for a giv

between that l

the percentage 

cdf value, high

served an F-te

oups were equ

e time. This l

erion yields s

verage fraction

f Fig. 2, we r

nces among six

on heuristic is 

uristic did no

s of ANOVA

ponse per row

nces caused b

d an F-test 

data points 

between the 

(1) 

de-selection 

n represents 

mputed the 

(cdf) value 

the groups 

y41- Average 

mong groups) 

esults of an 

ined (y41).

n of all data 

hree blocks 

ce criterion. 

esenting the 

beled nodeted clusterbers: (1) the 

ven clusterlocal mean 

difference. 

hlighting in 

est statistic 

ual – occur 

leads us to 

statistically 

n of VMs 

reverse the 

x groups of 

varied. In 

ot lead to 

results for 

w. The first 

by cluster95
c

d

d

r

m

b

in

d

r

s

p

T

4

C

H

c

e

h

d

s

r

n

(

o

a

choice criterion

differences cau

differences are 

Table VIII 

rows) given ea

mean averages 

by six node-sel

n red for resp

difference cau

reports the me

selection heuris

parameter comb

TABLE VII. Summ

42 Responses; Colu

Criterion and Colum

Heuristic – cells hig

The ANOV

clearly that clu

effect on overa

heuristic. Clu

differences in 7

significant diffe

represent the e

node-selection

(12/42) of the r

only 12.5% (1/8

Examining 

allocated (PAL

n and the sec

used by nodehighlighted in 

reports the me

ach cluster-cho

192 observatio

lection heuristi

ponses where 

used by cluste

ean value for

stic. Each mea

binations by th

mary of 84 ANOV

umn 4 Reports Dif

mn 5 Reports Diff

ghlighted in red ide

VI. D

VA tests on the 

ster-choice crit

all cloud beha

uster-choice 

79% (33/42) of

erences in 100

eight behavior

heuristic sign

responses, and 

8) of Koala’s b

results in Tab

L) cluster-cho

cond summary 

-selection heur

red. 

ean value for e

oice criterion (

ons (32 parame

ics). The mean

ANOVA fou

er-choice crite

r responses gi

n averages 96 

hree cluster-cho

VA Tests: Each Ro

fferences Attributa

ferences Attributab

entify significant d

DISCUSSION

experiment res

terion exhibits 

avior than doe

criterion cau

f the responses

% (8/8) of resp

ral dimensions

nificantly influe

led to significa

behavioral dime

le VIII shows 

oice criterion 

(col. 5) repo

ristic. Significa

ach response (

(cols. 3-5). Ea

eter combinatio

ns are highlight

und a significa

erion. Table 

iven each nod

observations (

oice criteria). 

ow Represents One

able to Cluster-Cho

ble to Node-Select

differences 

sults demonstra

a much strong

es node-selecti

used significa

s, and also led 

ponses chosen

s of Koala. T

enced only 29

ant differences

ensions. 

that the perce

leads to high

orts

ant

(42 

ach

ons

ted

ant

IX 

de-

(32 

e of 

oice 

tion 

ate 

ger

ion

ant 

to 

to 

The

9%

s in 

nther 

average

cloud.

clusters

request

number

generat

only $

when a

generat

TABLE

Choice C

On

effect o

NERA

before

20 min

also lea

PAL, th

a larger

more r

increas

utilizati

Wit

among 

realloca

grants 

e loads (y13-y

This occurs b

s that can ac

ted instances

r of running i

te more revenu

384/hour mor

aggregated over

tes about $3.4M

VIII. Mean for 

Criteria – cells high

the other hand

on the general 

responses (y2)

their VMs can

nutes more wai

ads to an incre

hen, serves few

r proportion of

resources to f

e in varianc

ion (y16-y18) a

thin the cloud,

parallel alloc

ations of cluste

(y8). While

y15) and utiliz

because admit

ccommodate 

(y41), which 

instances (y29

ue per hour (y3

re revenue tha

r a year this di

M more than LL

Each Response u

hlighted in red per

d, these factors

population of 

) and so have to

n be placed, wh

iting time (y6).

ease in the rate

wer users (y4) b

f their requeste

fewer users a

ce in resourc

among clusters

, PAL also lea

cation requests

ers (y7) and a 

e this may 

zations (y10-y

tted users are 

the highest f

also leads to

), allowing th

39). While PAL

an least-full fi

ifference mean

LF. 

under Each of T

r ANOVA from Ta

s have an overa

users, who rec

o retry more re

hich leads to g

. The increase 

e of WS messa

but gives each s

ed VMs (y41).

also leads to 

ce load (y19

s in the cloud. 

ads to increase

s, which result

a lower proport

seem count

y12) in the 

placed on 

fraction of 

o a higher 

he cloud to 

L generates 

first (LLF), 

ns that PAL 

hree Clusterable VII 

all negative 

ceive more 

equests (y1)

greater than 

in requests 

ages (y37). 

served user 

Dedicating 

significant 

9-y21) and 

ed conflicts 

ts in more 

tion of full 

terintuitive, 

96
a

V

r

T

H

a

m

(y

f

a

lo

c

to

a

lo

h

V

s

w

lo

B

s

s

a

th

V

accommodating

VMs means t

requested, as co

TABLE IX. Mean

Heuristics – cells h

When comp

and dedicates f

more full grant

(y16-y21) amon

fewer full gran

available space

ower node rea

chance that ove

o the same clus

Examining 

attributable to 

ower cloud-wi

heuristics more

VMs. By choo

squeeze out som

with Web serv

ower user suc

By tagging no

squeezing out 

space utilization

and RA lead to

hat these heur

VMs to do so w

g a larger prop

that fewer us

ompared with t

n for Each Respon

highlighted in red p

pared with PA

fewer resources

ts (y3), and als

ng clusters. RA

nts (y3) becau

e is not alway

llocation rate (

erlapping alloc

ster.

results in Ta

node-selection

ide virtual core

e often choose 

osing empty n

me larger VM 

vice users. This

cess rate (y40)

des for particu

larger VM typ

n (y12) and dis

o lower grant la

ristics allow u

with an averag

portion of each

sers can obtai

the LFF cluster

nse under Each of

per ANOVA from 

AL, LLF serves

s to each user,

so distributes l

AN, on the oth

use the cluster

ys chosen. RA

(y22) because t

cation requests 

able IX reveal

n heuristic. LF

e utilization (y1

empty nodes o

nodes more oft

types (y34 and

s factor also le

) and higher g

ular types of V

pes. TP also y

sk count load (y

atencies (y6), r

users who succ

e of about one

h user’s request

in all the VM

r-choice criterio

f Six Node-Select

Table VII 

s more users (y

, which results 

oad more even

her hand, leads 

r with the mo

AN also leads 

there is a smal

will be assign

ls a few effe

F and TP lead 

10) because the

on which to pla

ften, LF tends 

d y35) associat

eads LF to yie

give-up rate (y

VMs, TP avoi

yields lower di

(y14). Finally, L

reflecting the fa

cessfully acqu

e fewer retry th

ted

Ms

on. 

tion 

y4)

in 

nly 

to 

ost

to 

ller

ned

cts 

to 

ese 

ace

to

ted

eld

y5).

ids

isk

LF

fact

uire

han

the oth

with th

combin

closer t

Rev

all 42

notewo

node-se

combin

rate (y2

(y41), w

At the

utilizati

control

highest

memory

The

and vi

Combin

(y12) an

The

(y14). R

(y30), w

of M1x

We 

resourc

distribu

compar

Internet

in our 

analysi

we co

initially

clouds. 

algorith

compar

We 

placem

larger 

behavio

tradeof

evidenc

initial 

yield s

respons

the crit

differen

We 

intend t

situatio

Second

VM-pla

of muc

applyin

algorith

reduce

her heuristics.

he LLF and 

ned with PAL

to the grand av

viewing individ

2 responses a

orthy combina

election heur

nation led to th

2), give-up rat

while also yiel

e same time, 

ion (y12) an

ler (y15) load

t variance am

ry (y17) and dis

e LLF-LF comb

irtual core (y

ning LLF and T

nd the least rev

e RAN-TP com

RAN-MF yield

while RAN-LF

xlarge VMs (y3

VII. CONC

e have develop

ce-allocation a

uted systems. P

re proposed c

t. In this paper

method, usin

s to construct 

ompared macr

y placing VMs

 While we res

hms, the appro

re any set of co

e generated 

ment algorithms

influence, than

or in an infra

ffs among c

ce showing tha

VM placemen

small quantita

ses. On the oth

terion for choo

nce in provider

e envision futur

to compare the

ons where var

d, we will exten

acement algori

ch recent rese

ng our meth

hms for movin

cost, enhance u

This occurs p

RAN cluster

L, LF and RA

verage. 

dual ANOVA 

allowed us t

ations of clus

ristic. For e

he highest user 

ate (y5) and fr

ding the lowes

PAL-LF led 

nd disk (y14)

ds. Combining

mong clusters 

sk space (y18)

bination led to 

y10) and mem

TP yielded low

venue per hour

mbination gave

ded the lowest 

F combined to 

32).

CLUSIONS AND

ped an object

algorithms in

Previously, we

congestion-con

r, we demonstr

ng results fro

t parameter co

roscopic beha

s on nodes in 

stricted our co

oach we use 

ompeting algor

insights rega

s, showing th

n selection of

astructure clou

luster-choice

at, on average

nt in on-dema

ative differenc

her hand, we 

osing a cluste

r revenue, when

re work along t

ese 18 VM-pla

rious failures 

nd our compar

ithms, which h

earch. Finally,

hod to comp

ng VMs among

user performan

rimarily when

r-choice criter

A lead to gran

plots (such as 

to identify p

ster-choice crit

example, the 

request rate (y

raction of VM

st user success 

to highest d

) and networ

g PAL with M

for virtual c

utilizations. 

 lowest grant la

mory (y11) u

west disk space

r (y39). 

e lowest disk 

faction of M1

give the highe

D FUTURE WOR

tive method to

n simulations 

e applied our 

ntrol algorithm

rated steps thre

m an earlier 

ombinations un

avior of algor

on-demand inf

omparison to 1

should be app

rithms. 

arding two-le

at choice of c

f nodes, on m

ud. We identi

criteria. We 

, different algo

and infrastruct

ces in many 

showed that s

er can lead to 

n aggregated o

three direction

acement algorit

inhibit cloud 

ison to include

have become t

, we will also

pare various 

g cloud assets, 

nce, or both. 

n combined 

ria. When 

nt latencies 

Fig. 2) for 

particularly 

terion and 

PAL-LF 

y1), NERA 

Ms obtained 

rate (y40).

disk space 

rk-interface

MF yielded 

core (y16),

atency (y6)

utilizations. 

e utilization 

count load 

small VMs 

est fraction 

RK

o compare 

of large 

method to 

ms for the 

ee and four 

sensitivity 

nder which 

rithms for 

frastructure 

18 selected 

plicable to

evel VMcluster has 

macroscopic 

ified some 

provided 

orithms for 

ture clouds 

measured 

selection of 

very large 

ver time. 

s. First, we 

thms under 

operation. 

e additional 

the subject 

o consider 

proposed 

whether to 

97
FIGURE & TABLE ENLARGEMENTS

Enlargements of all figures and tables in this paper may be 

downloaded from 

http://www.nist.gov/itl/antd/upload/LargerTablesPaper36.pdf

REFERENCES

[1] V. Paxson and S. Floyd. “Why we don’t know how to 

simulate the Internet,” Proceedings of the 1997 Winter 

Simulation Conference, ed. S. Andradottir, K. J. Healy, D. H. 

Withers, and B. L. Nelson, pp. 1037-1044. 

[2] G. E. Box, J. S. Hunter, and W. G. Hunter, Statistics for 

Experimenters, 2nd ed., Wiley, 2005, 639 pages. 

[3] K. Mills, J. Filliben, D. Cho and E. Schwartz, “K. Mills, J. 

Filliben, D-Y. Cho and E. Schwartz, "Predicting Macroscopic 

Dynamics in Large Distributed Systems", Proceedings of 

ASME PVP 2011, Baltimore, MD, July 17-22, 2011. 

[4] K. Mills, J. Filliben, D. Cho, E. Schwartz and D. Genin, Study 

of Proposed Internet Congestion Control Algorithms, NIST 

Special Publication 500-282, May 2010, 534 pages. 

[5] K. Mills, J. Filliben and C. Dabrowski, "An Efficient 

Sensitivity Analysis Method for Large Cloud Simulations", 

Proceedings of the 4th International Cloud Computing 

Conference, IEEE, Washington, D.C., July 5-9, 2011. 

[6] D. Nurmi, et al., “The Eucalyptus Open-Source CloudComputing System”, Proceedings of the 9th IEEE/ACM 

International Symposium on Cluster Computing and the Grid, 

May 18-21, 2009, pp. 124-131. 

[7] S. S. Seiden, R. V. Stee, and L. Epstein, “New Bounds for 

Variable-Sized Online Bin Packing”, SIAM Journal on 

Computing, Vol. 32, No. 2, 2003, pp. 455-469. 

[8] E. Coffman, M. Garey, and D. Johnson. Approximation 

Algorithms for Bin Packing: A Survey. PWS Publishers, 

Boston, 1997. 

[9] S. Shang, Y. Wu, J. Jiang and W. Zheng, “An Intelligent 

Capacity Planning Model for Cloud Market”, Journal of 

Internet Services and Information Security, 1:1, 37-45. 

[10] I. Fujiwara, K. Aida, and I. Ono, “Applying Double-sided 

Combinational Auctions to Resource Allocation in Cloud 

Computing”, Proceedings of the 10th Annual International 

Symposium on Applications and the Internet, IEEE, July 19-

23, 2010, pp. 7-14. 

[11] Amazon Elastic Compute Cloud (Amazon EC2) 

http://aws.amazon.com/ec2/, 2010. 

[12] A. Andrzejak, D. Kondo, and S. Yi, “Decision Model for 

Cloud Computing under SLA Constraints,” INRIA Technical 

Report-004/4849, Version 1, April 21, 2010. 

[13] M. Cardosa, A. Singh, H. Pucha and A. Chandra, “Exploiting 

Spatio-Temporal Tradeoffs for Energy Efficient MapReduce 

in the Cloud”, Dept. of Comp. Sci. and Eng., University of 

Minnesota, TR-10-008. April 7, 2010, 18 pp. 

[14] X. Meng, V. Pappas and L. Zhang, “Improving the Scalability 

of Data Center Networks with Traffic-aware Virtual Machine 

Placement”, Proceedings of IEEE 2010 INFOCOM, Mar. 14-

19, 2010. 

[15] B. Chandrasekaran, R. Purush, B. Douglas and D. Schmidt, 

“Virtualization Management Using Microsoft System Center 

and Dell OpenManage”, Dell Power Solutions, Aug. 2007, 

40-44.

[16] J. Xu and J. Fortes, “Multi-objective Virtual Machine 

Placement in Virtualized Data Center Environments”, 

Proceedings of the 2010 IEEE/ACM Conference on Green 

Computing and Communications, 179-188. 

[17] M. Mishra and A. Sahoo, “On Theory of VM Placement: 

Anomalies in Existing Methodologies and Their Mitigation 

Using a Novel Vector Based Approach”, Proceedings of the 

4th International Cloud Computing Conference, IEEE, 

Washington, D.C., July 5-9, 2011. 

[18] U. Bellur, C. Rao and M. Kumar, “Optimal Placement 

Algorithms for Virtual Machines”, Proceedings of CoRR. 

2010.

[19] J. Fontan, “Session 6: Advance Usage of OpenNebula”, 

OpenNebual Technology Days, July 20-21, 2010. 

[20] M. Sindelar, R. Sitaraman and P. Shenoy, “Sharing-Aware 

Algorithms for Virtual Machine Colocation”, Proceedings of 

the 23rd Annual ACM Symposium on Parallelism in 

Algorithms and Architectures, June 4-6, 2011. 

[21] H. Van and F. Tran, “Autonomic resource management for 

service host platforms” Proceedings of Workshop on 

Software Engineering Challenges in Cloud Computing, 

Vancouver, Canada, April 2010. 

[22] C. Mark, D. Niyato and T. Chen-Khong, “Evolutionary 

Optimal Virtual Machine Placement and Demand Forecaster 

for Cloud Computing”, Proceedings of the 2011 IEE 

International Conference on Advanced Information 

Networking and Applications, 348-355. 

[23] F. Machida, M. Kawato and Y. Maeno, “Redundant Virtual 

Machine Placement for Fault-tolerant Consolidated Server 

Clusters”, Proceedings of the 12th IEEE/IFIP Network 

Operations and Management Symposium, Osaka, Japan, 

2010, 32-39. 

[24] N. Bobroff, A. Kochut and K. Beaty, “Dynamic Placement of 

Virtual Machines for Managing SLA Violations”, 

Proceedings of the 10th IFIP/IEEE Symposium on Integrated 

Network Management, 2007,119-128. 

[25] M. Chen, H. Zhang, Y.Y. Su, X. Wang, G. Jiang and K. 

Yoshihra, “Effective VM Sizing in Virtualized Data Centers”, 

Proceedings of the 12th IFIP/IEEE Symposium on Integrated 

Network Management, 2011, Dublin, Ireland. 

[26] S. Das, M. Kagan and D. Crupnicoff, “Faster and Efficient 

VM Migrations for Improving SLA and ROI in Cloud 

Infrastructures”, DC CAVES 2010. 

[27] A. Verma, P. Ahuja and A. Neogi, “pMapper: Power and 

Migration Cost Aware Application Placement in Virtualized 

Systems” Proceedings of the 9th ACM/IFIP/USENIX 

International Conference on Middleware, 243-264. 

[28] C. Isci, J. Hanson, I. Whalley, M. Steinder and J. Kephart, 

“Runtime Demand Estimation for Effective Dynamic 

Resource Management”, Proceedings of the 12th IEEE/IFIP 

Network Operations and Management Symposium, Osaka, 

Japan, 2010, 381-388. 

[29] S. Lee, R. Panigrahy, V. Prabhakaran, V. Ramasubrahmanian, 

K. Talwar, L. Uyeda and U. Wieder, “Validating Heuristics 

for Virtual Machine Consolidation”, Microsoft Research, 

MSR-TR-2011-9, January 2011, 14 pp. 

[30] B. Malet and P. Pietzuch, “Resource Allocation across 

Multiple Cloud Data Centres”, Proceedings of the 8th 

International Workshop on Middleware for Grids, Clouds and 

e-Science, ACM, 2010. 

[31] C. Hyser, B. McKee, R. Gardner and B. Watson, “Autonomic 

Virtual Machine Placement in the Data Center”, HP 

Laboratories, HPL-2007-189, 11 pp. 

[32] Amazon Elastic Compute Cloud (Amazon EC2) 

http://aws.amazon.com/ec2/, 2010. 

[33] Amazon Elastic Compute Cloud API Reference API Version 

2009-08-15.

[34] Amazon EC2 Instance Types 

http://aws.amazon.com/ec2/instance-types/, 2010. 

[35] F. Curbera, et al. “Unraveling the Web services web: an 

introduction to SOAP, WSDL, and UDDI”, Internet 

Computing, IEEE, March/April, 2002, pp. 86-93. 

98