Comparing VM-Placement Algorithms

for On-Demand Clouds

Nov. 30, 2011 IEEE Cloud 2011 Kevin Mills, Jim Filliben and Chris Dabrowski

Koala Information Visualizations by Sandy Ressler

see http://math.nist.gov/~SRessler/cloudviz.html for animations and more)

y10 y11 y12 y13 y14 y15
 Define a general and objective method for comparing possible VMplacement algorithms through simulation of large, on-demand 

infrastructure clouds.

 Demonstrate the method to compare 18 selected algorithms.

 Generate some insights regarding two-level (cluster then node) VMplacement algorithms.

 Make observations about specific pairs of algorithms.

 Provide evidence showing that, on average, alternative algorithms yield 

small quantitative differences in many model responses, but also show 

that selection of algorithm for choosing a cluster can lead to very large 

difference in provider revenue, when aggregated over time.

Synopsis

We base our study on the Koala infrastructure cloud simulator.

Nov. 30, 2011 IEEE CloudCom 2011 2
We Developed a 4-Step Method* to Compare Resource 

Allocation Algorithms in Large Distributed Systems

3

Nov. 30, 2011 IEEE CloudCom 2011

Develop 

Reduced 

Parameter 

Model Identify Most 

Influential Model 

Parameters & 

Significant 

Behaviors Select Parameter 

Combinations under 

which to Compare 

Algorithms

Apply Techniques 

for Analyzing 

Multidimensional 

Result Datasets

THIS TALK

*Previously, we applied this method to 

compare congestion-control algorithms 

proposed for the Internet:

 K. Mills, J. Filliben, D. Cho, E. Schwartz and D. Genin,

 Study of Proposed Internet Congestion Control Mechanisms, 

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

First two steps,

as applied to On-Demand 

Clouds, reported at IEEE Cloud 2011:

K. Mills, J. Filliben and C. Dabrowski,

“An Efficient Sensitivity Analysis Method

for Large Cloud Simulations”, Proceedings

of IEEE Cloud 2011, July 5-9, Washington, D.C.,

where we introduced our Koala cloud simulator

and identified six significant parameters that

influence eight behavioral dimensions .
Outline

• Overview of Koala Infrastructure Cloud Simulator – 5 slides

• Experiment Design – 3 slides

• Analysis Method & Results – 3 slides

• Findings – 3 slides 

• Ongoing Work – 1 slide

4
Overview of Koala

Infrastructure Cloud Simulator

5
Schematic of Koala IaaS Cloud Computing Model

 INTERNET

DEMAND LAYER

SUPPLY 

LAYER

VM 

BEHAVIOR

 LAYER

RESOURCE 

ALLOCATION

 LAYER

User 

#1

User 

#2

User 

#n

User 

#3

User 

#4

User 

#5

User 

#6

User 

#n-3

User 

#n-2

User 

#n-1

CLOUD CONTROLLER

Cluster 

Controller #1

Cluster 

Controller #c

NODE CONTROLLER #k

NODE RESOURCES NODE CONTROLLER #k-1

NODE RESOURCES NODE CONTROLLER #k-2

NODE RESOURCES

NODE CONTROLLER #3

NODE RESOURCES NODE CONTROLLER #2

NODE RESOURCES NODE CONTROLLER #1

NODE RESOURCES

NODE CONTROLLER #p

NODE RESOURCES NODE CONTROLLER #p-1

NODE RESOURCES NODE CONTROLLER #p-2

NODE RESOURCES

NODE CONTROLLER #3

NODE RESOURCES NODE CONTROLLER #2

NODE RESOURCES NODE CONTROLLER #1

NODE RESOURCES

NODE CONTROLLER #q

NODE RESOURCES NODE CONTROLLER #q-1

NODE RESOURCES NODE CONTROLLER #q-2

NODE RESOURCES

NODE CONTROLLER #3

NODE RESOURCES NODE CONTROLLER #2

NODE RESOURCES NODE CONTROLLER #1

NODE RESOURCES

INTRANETINTRANETINTRANET

VMs 

Shown for

One Node Only

VMs 

Shown for

One Node Only

VMs 

Shown for

One Node Only

VM1

VM1

VM1

VM1

VM1

VM1

VM1

VM1

VM1

VM1

VM1

VM1

VM1

VM1

VM1

Cluster 

Controller #cm

(1)

(4)

(4) (3)

(2)

(4) (4)

(5)

Nov. 30, 2011 IEEE CloudCom 2011 6
Virtual Machine (VM) Types* Simulated in Koala

7

VM Type

Virtual 

Cores

Virtual Block 

Devices # Virtual 

Network 

Interfaces

Memory 

(GB)

Instruct.

Arch. #

Speed 

(GHz) #

Size (GB) 

of Each

M1 small 1 1.7 1 160 1 2 32-bit

M1 large 2 2 2 420 2 8 64-bit

M1 xlarge 4 2 4 420 2 16 64-bit

C1 medium 2 2.4 1 340 1 2 32-bit

C1 xlarge 8 2.4 4 420 2 8 64-bit

M2 xlarge 8 3 1 840 2 32 64-bit

M4 xlarge 8 3 2 850 2 64 64-bit

*Inspired by Amazon Elastic Compute Cloud VM Types 

VM Types are offered by the Cloud provider and requested by Cloud users

Nov. 30, 2011 IEEE CloudCom 2011
Description of User Types Simulated in Koala

8

We created different classes of demand, such as processing users (PU), distributed 

simulation users (MS), peer-to-peer users (PS), Web service users (WS) and 

data search users (DS)

Nov. 30, 2011 IEEE CloudCom 2011
Finite-State Machine of Simulated User Behavior in Koala

9

REFLECTING

REQUESTING

RETRYING

RESTING TERMINATING

USER START TIME ARRIVES SELECT USER TYPE, SELECT GEOLOCATION, SELECT # OF REST PERIODS, SELECT THINK PERIOD

FULLY OR PARTIALLY LAUNCHED SEND TERMINATE INSTANCES REQUEST [RETRIES != 0] NERA

THINK PERIOD ENDS SELECT # OF RETRIES, SELECT MIN & MAX VMs, SEND RUN INSTANCE REQUEST

DECREMENT # OF RETRIES, SELECT THINK PERIOD

THINK PERIOD EXPIRES SEND RUN INSTANCE REQUEST

[RETRIES == 0 && REST PERIODS != 0] NERA

HOLDING PERIOD ENDS SELECT HOLDING PERIOD

TERMINATE INSTANCES RESPONSE SELECT USER TYPE, SELECT GEOLOCATION, SELECT # OF REST PERIODS, SELECT THINK PERIOD

SELECT USER TYPE, GEOLOCATION SELECT # OF REST PERIODS, SELECT THINK PERIOD [RETRIES == 0 && REST PERIODS == 0] NERA SELECT REST PERIOD HOLDING

DECREMENT # OF REST PERIODS SELECT # OF RETRIES, SELECT THINK PERIOD REST PERIOD EXPIRES

While Holding Randomly describe, reboot and terminate VM instances

RETRY, REST & FAILURE PATHS

SUCCESS PATH

Nov. 30, 2011 IEEE CloudCom 2011
Description of Selected Platform Types Simulated in Koala

10

We created 22 platform classes, inspired by 

a visit to an Amazon EC2 data center – only four platform types were 

used in these experiments

Nov. 30, 2011 IEEE CloudCom 2011
Experiment Design

Nov. 30, 2011 IEEE CloudCom 2011 11
VM-Placement Algorithms Simulated in Koala

12

We compared 18 VM-Placement Algorithms that require two levels: (1) choosing a 

cluster and (2) placing VMs on nodes within that cluster.

Nov. 30, 2011 IEEE CloudCom 2011

3 x 6 = 18
Sensitivity Analysis of Koala Revealed 6 Influential Parameters

13

Sensitivity Analysis also Guided our Choice of Two Values for Each Parameter

Nov. 30, 2011 IEEE CloudCom 2011

We compared the

18 Algorithms under

2

6-1 = 32 conditions,

chosen using 

Orthogonal Fractional

Factorial (OFF) 

experiment design 

theory
Response Variables used for Experiment

14

We selected 42 variables that we wanted to explore, though Sensitivity Analysis 

indicated Koala exhibited only 8 Behavioral Dimensions:

Nov. 30, 2011 IEEE CloudCom 2011

y3 – cloud-wide demand/supply

y15 – cloud-wide resource usage

y21 – variance in cluster load

y7 – reallocation rate

y29 – number of VMs

y4 – user arrival rate

y31 – mix of VM types

y28 – variance in cluster choice
Analysis Method & Results

Nov. 30, 2011 IEEE CloudCom 2011 15
Used ANOVA (Analysis of Variance) to Compare Each Algorithm Level

16

Nov. 30, 2011 IEEE CloudCom 2011
Summary of 84 ANOVA Tests: 42 Responses x 2 Algorithm Levels

Nov. 30, 2011 IEEE CloudCom 2011 17
Means for Each Response Under Each Value of Each Algorithm Level

Nov. 30, 2011 IEEE CloudCom 2011 18
Findings

Nov. 30, 2011 IEEE CloudCom 2011 19
Choice of Cluster has Larger Influence on System 

Behavior than Choice of Node

• Cluster choice caused significant differences in 79% of responses, covering 

100% of the eight behavioral dimensions Koala exhibits

• Node selection influenced only 29% of responses, covering only one of the 

eight behavioral dimensions Koala exhibits

• Percent-Allocation (PAL) cluster choice generates an average of $384/hour 

more revenue for the cloud provider, which, when aggregated over a year, 

reaches about $3.4M more than Least-Full First (LFF)

• On the other hand, PAL has an overall harmful effect on the general 

population of users, who receive more negative responses and must retry 

more, incurring on average 20 minutes more waiting time to obtain VMs

• PAL serves fewer users but gives each served user a larger proportion of 

their requested VMs, and also increases variance in resource loads and 

utilizations

20 Nov. 30, 2011 IEEE CloudCom 2011
Choice of Node Influences a Few Responses

• Least-Full First (LF) and Tag-and-Pack (TP) lead to lower cloud-wide virtual 

core utilization because these heuristics more often choose empty nodes

• On the other hand, LF tends to squeeze out some larger VM types – by 

tagging nodes TP avoids this behavior

• LF and Random (RA) lead to lower grant latencies, because these 

heuristics allow successful users to acquire VMs with one fewer retries, on 

average

21 Nov. 30, 2011 IEEE CloudCom 2011
Some Notable Algorithm Pairs

• PAL-LF: highest NERA and give-up rates, lowest user success rate, highest

 fraction of VMs obtained, highest disk-space utilization and disk

 and network controller loads

• PAL-MF: highest variance among clusters for virtual core, memory and 

 disk-space utilizations

• LFF-LF: lowest grant latency and lowest virtual core and memory utilizations

• LLF-TP: least revenue per hour and lowest disk-space utilization

22 Nov. 30, 2011 IEEE CloudCom 2011
Ongoing Work

Nov. 30, 2011 IEEE CloudCom 2011 23
Ongoing Work

24

Currently using our 4-step process to determine effect on VMPlacement Algorithms of asymmetric and dynamic conditions, e.g.,

Parameter Summary

x1 Cluster Distribution around the Internet (same site or unique sites)

x2 Platform Types per Cluster (fixed or random probabilities)

x3 Node Failure (supply nodes fail more or less frequently)

x4 Absolute Cluster Size Variation (fewer larger clusters or more smaller clusters)

x5 Relative Cluster Size Variation (uniform clusters or some large and some small)

x6 Cloud Reconfiguration (cloud adds or subtracts clusters or not)

x7 Cluster Reconfiguration (clusters add or subtract nodes or not)

x8 Variability in Inter-site Communication Delays (very long delays vs. typical delays)

x9 Variability in Intra-site Communication Delays (very long delays vs. typical delays)

x10 Failure of Node Components (VCPUs, Memory and Disks fail and recover more or less frequently)

x11 Starting Load (100% or 50%)

x12 Time Varying User Type Probability Map (switching user type maps vs. fixed user type map)

x13 User VM Demand Changes (users grow or shrink number of VMs during holding time or do not)

x14 Probability Bogus User Request (high or low probability of user generating invalid request)

x15 probability Node NERA (high or low probability that a node reneges on accepting a VM)

x16 probability Inter-Site Message Loss (high or low probability of message loss on the Internet)

x17 probability Intra-Site Message Loss (high or low probability of message loss on Intranets)

x18 Cluster Communication Cut Function (high or low probability of cuts in communication with clusters)

Nov. 30, 2011 IEEE CloudCom 2011
Questions?

Nov. 30, 2011 IEEE 25 CloudCom 2011

For more information see: http://www.nist.gov/itl/antd/emergent_behavior.cfm

and/or http://www.nist.gov/itl/cloud/index.cfm

Contact information about studying Complex Information Systems:

{kmills, jfilliben, cdrabowski@nist.gov} 

Contact information about Cloud Information Visualization:

sressler@nist.gov

Contact information about NIST Cloud Computing Program:

dawn.leaf@nist.gov