Comparing VM-Placement Algorithms

for On-Demand Clouds

Feb. 14, 2012 NIST Presentation to LSN

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

1
NIST 2011 Papers Related to Clouds as Complex Systems

2

1. C. Dabrowski and K. Mills, "VM Leakage and Orphan Control in Open-Source Clouds", Proceedings 

of IEEE CloudCom 2011, Nov. 29-Dec. 1, Athens, Greece, pp. 554-559.

2. K. Mills, J. Filliben and C. Dabrowski, "Comparing VM-Placement Algorithms for On-Demand 

Clouds", Proceedings of IEEE CloudCom 2011, Nov. 29-Dec. 1, Athens, Greece, pp. 91-98.

3. C. Dabrowski and K. Mills, "Extended Version of VM Leakage and Orphan Control in Open-Source 

Clouds", NIST Publication 909325; an abbreviated version of this paper was published in the 

Proceedings of IEEE CloudCom 2011, Nov. 29-Dec. 1, Athens, Greece.

4. C. Dabrowski and F. Hunt, "Identifying Failure Scenarios in Complex Systems by Perturbing Markov 

Chain Models", Proceedings of ASME 2011 Conference on Pressure Vessels & Piping, Baltimore, 

MD, July 17-22, 2011. 

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.

Feb. 14, 2012 NIST Presentation to LSN
 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.

 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.

 Introduce Ongoing Work

Synopsis

We base our study on the Koala infrastructure cloud simulator.

Feb. 14, 2012 NIST Presentation to LSN 3
We Developed a 4-Step Method* to Compare Resource 

Allocation Algorithms in Large Distributed Systems

4

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 .

Feb. 14, 2012 NIST Presentation to LSN
Outline

• Overview of Koala Infrastructure Cloud Simulator – 5 slides

• Experiment Design – 3 slides

• Analysis Method & Results – 3 slides

• Findings – 2 slides 

• Ongoing Work – 1 slide

Feb. 14, 2012 NIST Presentation to LSN 5
Overview of Koala

Infrastructure Cloud Simulator
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)

Feb. 14, 2012 NIST Presentation to LSN 7
Virtual Machine (VM) Types* Simulated in Koala

8

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

Feb. 14, 2012 NIST Presentation to LSN
Description of User Types Simulated in Koala

9

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)

Feb. 14, 2012 NIST Presentation to LSN
Finite-State Machine of Simulated User Behavior in Koala

10

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

Feb. 14, 2012 NIST Presentation to LSN
Description of Selected Platform Types Simulated in Koala

11

We created 22 platform classes, inspired by 

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

used in these experiments

Feb. 14, 2012 NIST Presentation to LSN
Experiment Design
VM-Placement Algorithms Simulated in Koala

13

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

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

3 x 6 = 18

Feb. 14, 2012 NIST Presentation to LSN
Sensitivity Analysis of Koala Revealed 6 Influential Parameters

14

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

We compared the

18 Algorithms under

2

6-1 = 32 conditions,

chosen using 

Orthogonal Fractional

Factorial (OFF) 

experiment design 

theory

Feb. 14, 2012 NIST Presentation to LSN
Response Variables used for Experiment

15

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

indicated Koala exhibited only 8 Behavioral Dimensions:

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

Feb. 14, 2012 NIST Presentation to LSN
Analysis Method & Results
Used ANOVA (Analysis of Variance) to Compare Each Algorithm Level

17

Feb. 14, 2012 NIST Presentation to LSN
Summary of 84 ANOVA Tests: 42 Responses x 2 Algorithm Levels

Feb. 14, 2012 NIST Presentation to LSN 18
Means for Each Response Under Each Value of Each Algorithm Level

Feb. 14, 2012 NIST Presentation to LSN 19
Findings
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

Feb. 14, 2012 NIST Presentation to LSN 21
Choice of Node Influences Only 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

Feb. 14, 2012 NIST Presentation to LSN 22
Ongoing Work
Ongoing Work – Related to Cloud Reliability

1. Characterizing the Effects of Stressful 

Conditions (e.g., asymmetries, dynamics

and failures) on IaaS Clouds

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)

Feb. 14, 2012 NIST Presentation to LSN 24

2. Applying Anti-Optimization and Directed 

Search (e.g., Genetic Algorithms) to 

Predict Catastrophic Failure Scenarios in 

IaaS Clouds

Color denotes fitness
Questions?

25

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 

Feb. 14, 2012 NIST Presentation to LSN