Efficient Sensitivity Analysis Method for Large Cloud Simulations

Kevin Mills, James Filliben and Chris Dabrowski from NIST

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

We developed an objective method to compare distributed control algorithms in simulations of large systems. Our method has four steps: (1) develop a reduced-parameter model (i.e., Koala), (2) determine the 

most significant model behaviors and the parameters that most influence those behaviors, (3) construct 

a set of parameter combinations under which control algorithms should be compared and (4) use multidimensional data analysis techniques to find patterns revealing significant similarities and differences 

among the algorithms. This work describes steps (1) and (2) as applied to Koala, an IaaS (Infrastructureas-a-Service) cloud simulator.

Theory Koala

Simulator

Experiment

Design

Significant

Behaviors

Significant

Parameters

Main 

Effects

Analysis

http://www.nist.gov/itl/antd/emergent_behavior.cfm
Comparing VM-Placement Algorithms for On-Demand Clouds 

Kevin Mills, James Filliben and Chris Dabrowski from NIST

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

We developed an objective method to compare distributed control algorithms in simulations of large systems. Our method has four steps: (1) develop a reduced-parameter model (i.e., Koala), (2) determine the 

most significant model behaviors and the parameters that most influence those behaviors, (3) construct 

a set of parameter combinations under which control algorithms should be compared and (4) use multidimensional data analysis techniques to find patterns revealing significant similarities and differences 

among the algorithms. This work describes steps (3) and (4) as applied to Koala, an IaaS (Infrastructureas-a-Service) cloud simulator.

Responses Evaluated

Platform Types

VM Placement Algorithms

User Types VM Types

Experiment Design

ANOVA Analyses

Summary of 84 ANOVA Tests Means Per Cluster-Choice Means Per Node-Selection

http://www.nist.gov/itl/antd/emergent_behavior.cfm
VM Leakage and Orphan Control in Open-Source Clouds

Chris Dabrowski & Kevin Mills from NIST 

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

A simple message discard attack initiated by a Trojan in compromised Web-server 

code leads to VM Leakage that exhausts resources in an IaaS cloud based on commonly available open-source code. Adding two orphan control processes, (1) creation orphan control and (2) persistent termination, mitigates the VM Leakage.

VMs as seen by 

cloud users and 

cloud nodes 

without (red) 

and with (blue) 

orphan control 

processes—the 

gaps denote VM 

leakage

Leaked VMs 

without orphan 

control processes—most 

leaked VMs are 

creation 

orphans

Outcomes of 

User Requests 

without orphan 

control processes–Total Grants 

(categorized by 

Full and Partial) 

and Un-served 

Users

Orphan control processes do not eradicate all leaked VMs at highest message loss rate due to existence of temporary termination orphans that occur 

because we limited persistent termination to final termination requests

Outcomes of 

User Requests 

with orphan 

control processes–Total Grants 

(categorized by 

Full and Partial) 

and Un-served 

Users

Without orphan control processes, most leaked VMs are creation orphans because VMs must be created before they can become orphans and user retries 

http://www.nist.gov/itl/antd/emergent_behavior.cfm

0

2000

4000

6000

8000

10000

12000

14000

16000 Number of VMs

Probability of Message Loss

User VMs (with)

Node controller VMs (with)

User VMs (without)

Node controllers VMs (without)

0

2000

4000

6000

8000

10000

12000

14000

16000 Number of VMs

Probability of Message Loss

Node controller VMs

Orphaned VMs

Creation Orphans

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1 Proportion of Requests

Probability of Message Loss

Total Grants

Full Grants

Partial Grants

Requests Abandoned

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1 Proportion of Requests

Probability of Message Loss

Total Grants

Full Grants

Partial Grants

Requests Abandoned
Problem: Identifying failure scenarios in distributed systems such as clouds 

is critical to understanding areas where performance may degrade. However, 

potential failure scenarios may be numerous and difficult to find.

Objective: To perturb Discrete Time Markov Chains (DTMCs) of cloud 

system behavior to identify potential failure scenarios more quickly than 

through detailed large-scale simulation or use of test beds.

Steps:

(1) Using Koala as proxy for real-world cloud, develop detailed state model 

of cloud behavior and convert to time-inhomogeneous DTMC. 

(2) Find minimal s-t cut sets in a directed graph of cloud DTMC to identify 

critical state transitions that break paths to desirable system goal states.

(3) Perturb critical state transitions to describe potential failure scenarios, 

create predictive performance curves, and find performance thresholds.

IDENTIFY FAILURE SCENARIOS IN CLOUD 

SYSTEMS USING MARKOV CHAIN ANALYSIS

Chris Dabrowski and Fern Hunt

Preparing To Submit

Initial Processing

Cluster Estimating

Implementing Allocation (F/P)

Request_Active (F/P)

Allocating Request

Initial State Failed_State Request time expires

0

0.05

0.1

0.15

0.2

0.25

0.3

0.0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1.0 Decrease in Probability of Transition Proportion of Requests Granted (both Full and Partial)

Increase in Probability of Transition from Allocating_Minimum state (8) to Transferring_Failure_Estimate state (10)

(a) Total Grants (Markov Simulation)

(b) Total Grants (Large Scale Simulation)

Decrease in probabilty of transition from Allocating_Minimum state (8) to Allocating_Maximum state (9)

Information Technology 

Laboratory

State Model of Resource Request in Cloud

A detailed representation of the states that a cloud system (Koala) may enter 

under normal and failure conditions, shown for two of the five major phases.

Transferring_Estimate_Request

Allocating_Minimum

Allocating_Maximum Allocating_Partial

Transferring_Failure_Estimate

Recording_Allocation

Transferring_Allocation_Estimate

TIMEOUT SEND SUCCEEDS

Minimum number of VMs allocated for all VM types requested.

Unable to allocate minimum number of VMs for at least one VM type requested.

Maximum number of VMs allocated for al VM types requested. Unable to allocate maximum number of VMs for at least one VM type requested. Allocated less than maximum number of VMs for at least one VM type requested. Allocated at least minimum for all others. Shadow allocation updated and response prepared

Unable to locate records for request or fault

Selecting_Next_Cluster

SEND SUCCEEDS or TIMEOUT

Selection_Failing

Transferring_Implementation_Request(F/P)

Transferring_Failure_Response Cluster selected TIMEOUT

Unable to select cluster

SEND SUCCEEDS

(8)

(7)

(9)

(10)

(11)

(12)

(13)

(16)

(15) (14)

(17), (18)

Processing Complete

TIMEOUT

Hardware or software fault

Hardware or software fault

Hardware or software fault

High-Level Model of 

Phases of Request Lifecycle Detailed State Models of Two Phases

Preparing To Submit

Initial Processing

Cluster Estimating

Implementing Allocation (F/P)

Request_Granted (F/P)

Cluster estimates complete or timeout

Request found to be valid

Allocation successful

Not enough resources available or timeout

Request prepared Request invalid or message failed

Allocating Request

Initial State Failed_State

Request time expires

Cluster selected

User timeout

Not enough resources available

Information Technology 

Laboratory

Creating a Discrete Time Markov Chain

• Observe Koala (as proxy for real-world system) to derive set of 

transition probability matrices (TPMs) that describe probabilities of 

transition between states over different time periods  form a timeinhomogeneous DTMC.

• Generate1000 time period TPMs of 3600 s each.

n

k ik

ij

ij f

f

p

1

Given states si, sj, i, j = 1...n where n = 39, pij, is the 

probability of transitioning from state i to state j, written 

as si  sj. This probability is estimated by calculating the 

frequency of si  sj, or f

ij, divided by the sum of the 

frequencies of sito all other states. 

8 9 10

8 Allocating_Minimum 0 0.248 0.752

9 Allocating_Maximum 0 0 ε

10 Transferring Failure_Estimate 0 0 ε

Information Technology 

Laboratory

Perturbing state transitions in a cut set to 

predict system behavior in failure scenario (1)

• Cut set #1-4 could relate to a scenario in 

which software or hardware failures make 

resource databases inaccessible, preventing 

clusters from computing minimum allocation 

estimates. Instead, clusters return failure 

estimates to the cloud controller. 0

0.05

0.1

0.15

0.2

0.25

0.3

0.0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1.0 Decrease in Probability of Transition Proportion of Requests Granted (both Full and Partial) Increase in Probability of Transition from Allocating_Minimum 

state (8) to Transferring_Failure_Estimate state (10)

(a) Total Grants (Markov Simulation)

(b) Total Grants (Large Scale Simulation)

Decrease in probabilty of transition 

from Allocating_Minimum state (8)

to Allocating_Maximum state (9)

Portions of TPM perturbed

Decline in total requests granted (Full and Partial) due

to cluster estimation failure:

(a) As estimated by perturbing the DTMC; and 

(b) As computed in Koala large-scale simulation.

Blue curves show the resulting decrease in requests 

granted as estimated using the DTMC and as actually 

occurred in the Koala `large-scale simulation. These 

curves are plotted against the left vertical axis. The 

right vertical axis provides units for the decrease in 

probability of the state transition.

Cut set 

#1-4

Allocating_Minimum

Allocating_Maximum

Transferring_Failure_Estimate (8)

(9)

(10)

• Raise probabiltiy of Allocating_Minimum 

Transferring_Failure_Estimate:TPM element {8, 10}

• Lower probablity of Allocating_Minimum 

Allocating_Maximum: TPM elements {8, 9}. 

8 9 10

8 Allocating_Minimum 0 0.248 0.752

9 Allocating_Maximum 0 0 ε

10 Transferring Failure_Estimate 0 0 ε

Information Technology 

Laboratory

Perturbing state transitions in a cut set to 

predict system behavior in failure scenario (2)

• Cut set #2-3 could relate to a failure scenario in 

which viruses or other faults cause widespread 

software process failures in clusters, which 

prevent completion of cluster allocation 

estimation computations. Instead, clusters 

return failure estimates to the controller. 

Portions of TPM perturbed

Decline in total requests granted (Full and Partial) due

to cluster estimation failure:

(a) As estimated by perturbing the DTMC; and 

(b) As computed by Koala large-scale simulation.

9 10 11 12

9 Allocating_Maximum 0 ε 0.464 0.536

10 Transferring Failure_Estimate 0 ε 0.000 0.000

11 Allocating Partial 0 ε 0.000 1-3ε

12 Recording_Allocation 0 ε 0.000 0.000

Blue curves show the resulting decrease i n requests

granted as estimated using the DTMC and as actually

occurred i n the Koala large-scale simulation. These

curves are plotted against the left vertical axis. The

right vertical axis provides units for the decrease in

probability of the state transition.

Cut set

#2-3

•Raise Allocating_ Maximum  Allocating_Partial: TPM element {9, 11} 

•LowerAllocating_Maximum  Recording_ Allocation (TPM element {9, 12})

•Raise Allocating_PartialTransferring_Failure_Estimate: TPM element {11, 10} 

•Lower Allocating_Partial  Recording_Allocation: TPM element {11, 12}

Allocating_Minimum

Allocating_Maximum Allocating_Partial

Transferring_Failure_Estimate

Recording_Allocation

(8)

(9)

(10)

(11)

(12)

0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1 Decrease in Probabilities of Transition Proportion of Requests Granted (both Full and Partial)

Increase in Probability of Transition from Selecting 

Next Cluster state (14) to Selection_Failing state (15)

(a) Total Grants (Markov Simulation)

(b) Total Grants (Large Scale Simulation)

Decrease in probability of transition from

Selecting_Next_Clusterstate (14) to Transferring_

Implementation_Request (F) state (17)

Decrease in probability of transition from Selecting_ 

Next_Cluster state (14) to Transferring_

Implementation_Request (P) state (18)

Information Technology Ongoing Work Laboratory

Apply methodology to larger problems and determine scalability

• Current model consists of 39 states and 139 transitions

• Includes user, cloud controller, and cluster behavior, but not 

node behavior or actual use of VMs

For more information, see: 

• Identifying Failure Scenarios in Complex Systems by Perturbing Markov Chain 

Models, by Christopher Dabrowski and Fern Hunt, Proceedings of the 2011 

Pressure Vessels and Piping Division Conference. July 17–21, Baltimore, MD.

• Using Markov Chains and Graph Theory Concepts to Analyze Behavior in 

Complex Distributed Systems, by Christopher Dabrowski and Fern Hunt, 

Proceedings of the 23rd European Modeling and Simulation Symposium, 

September 12-14, 2011. Rome Italy.

Apply methodology to different types of failure scenarios

Information Technology 

Laboratory

Using the DTMC to simulate large-scale 

system (Koala) behavior

• Markov chains can emulate Koala to capture high-level system 

behavior, but in two orders of magnitude less computational time.

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1 Cumulative Proportion of Total Grants

Time Step

Total Grants (Markov simulation)

Total Grants (Large-scale simulation)

0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5 Cumulative Proportion of Full and Partial Grants

Time Step

Full Grant (Markov simulation)

Full Grant (Large-scale simulation)

Partial Grant (Markov simulation)

Partial Grant (Large-scale simulation) (Qtp)

T * vm= vm+1, where tp = integral value (m/S) + 1 

To evolve system state in discrete time steps, 

multiply state vector vm (at time step m) by the 

TPM, Qtp, for the applicable time period tp to 

produce a new system state vector vm+1, 

where T indicates a matrix transpose.

× =

vm vm+1

Total Grants

Full and Partial Grants

Repeated for 576 time steps in 16 hour 

simulated period, one time period per hour.

Information Technology 

Laboratory

Preparing To Submit

Initial Processing

Cluster Estimating

Implementing Allocation (F/P)

Request_Granted (F/P)

Allocating Request

Initial State

Using minimal s-t cut set analysis 

to find potential failure scenarios

• In a directed graph of the Koala 

DTMC, minimal s-t cut sets 

consist of critical state 

transitions, which if removed, 

disconnect all paths to absorbing 

Requests_Granted (F/P) state. 

• Applying algorithm to find 

minimal s-t cut sets* to the Koala

DTMC resulted in 159 cut sets. 

Examples of one and twotransition cut sets are shown.

High-Level Model 

of Request Lifecycle Detailed Model of 

Cluster Estimating Phase

Both cut sets disconnect all paths 

from Initial State to Request _Granted 

(F/P) absorbing states.

One-transition cut sets Two-transition cut sets

Allocating_Minimum

Allocating_Maximum Allocating_Partial

Transferring_Failure_Estimate

Recording_Allocation

Transferring_Allocation_Estimate

(8)

(9)

(10)

(11)

(12)

(13)

Cut set #1-4

Cut set #2-3

*Provan S., and Ball M., 1984, “Computing Network Reliability in Time 

Polynomial in the Number of Cuts,” Operations Research, 32(3), pp. 516–526.

Initial 

State

Absorbing

States
No effective methods exist to predict failure regimes in large distributed systems—the search space is 

large and causality is difficult to establish. Today, system operators wait for failures and diagnose, react 

and mitigate. We propose to leverage models and methods from the physical sciences to predict unforeseen dynamics and failure scenarios that could lead to spatiotemporal collapse in designs and deployments of large distributed systems. We intend to investigate and demonstrate our methods in the context of IaaS (Infrastructure-as-a-Service) clouds. Our work aims to improve cloud computing reliability, 

benefiting designers of distributed systems running on clouds, and those deploying clouds.

Predicting Catastrophic Failure Scenarios in Cloud Systems 

(Proposed Research)

C. Dabrowski, J. Filliben, D. Genin, F. Hunt, K. Mills and S. Ressler from NIST

Possible

Approaches

First 

Hard

Problem

Possible

Research

Team

Proposed

Schedule

Proposed

Tasks

http://www.nist.gov/itl/antd/emergent_behavior.cfm

Second 

Hard

Problem