NIST Cloud Computing 

Forum and Workshop VIII

Kevin Mills, NIST

July 9, 2015
NIST Cloud Computing Forum and Workshop VIII

J u l y 2 0 1 5

2

• Develop design-time methods that system engineers can use to 

detect existence and causes of costly failure regimes prior to 

deployment

• Develop run-time methods that system managers can use to 

detect onset of costly failure regimes in deployed systems, prior 

to collapse

Project Research Goals

Kevin Mills, NIST
NIST Cloud Computing Forum and Workshop VIII

J u l y 2 0 1 5

Topics

• Some past results on design-time methods

• Example→ Applying one design-time method to 

seek failure scenarios in a cloud system

• Ongoing work on run-time methods

• Where to find more information

Kevin Mills, NIST 3
NIST Cloud Computing Forum and Workshop VIII

J u l y 2 0 1 5

4

Some Past Results

State-space reduction techniques and their application to clouds 

Modeling Complex 

Systems with Few 

Input Parameters

Identifying Key 

Combinations of 

Parameters & 

Values to Compare 

Identifying Essential 

Responses to 

Measure and 

Compare

Identifying Failure 

Scenarios in 

Complex Systems 

by Perturbing 

Markov Chains

Using Spectral 

Methods to 

Streamline Search 

for Failure 

Scenarios

Applying Techniques 

to Assess Effects of 

Asymmetries, 

Dynamics and 

Failures on a Cloud 

Simulator

Combining GAs & 

Simulations to 

Search for Failure 

Scenarios in 

System Models

EXAMPLE

 (next 5 slides)

Directed and self-directed search techniques and their application to clouds 

Kevin Mills, NIST
NIST Cloud Computing Forum and Workshop VIII

J u l y 2 0 1 5

Method: Genetic Algorithm (GA) steers a population of 

 simulators to search for parameter combinations 

 that lead to system failure

Model Parameter 

Specifications Parallel Execution of

Model Simulators

Population of Model

Parameterizations

Selection based on

Anti-Fitness

Recombination

& Mutation

List of parameters 

and for each

parameter a MIN, 

MAX and

precision.

Anti-Fitness Reports

GENETIC ALGORITHM

Principal Components Analysis,

Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Growing Collection of Tuples: {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value} ... {Generation, Individual, Fitness, Parameter 1 value,....Parameter N value}

MODEL SIMULATORS

5

In our following

example, we use the

Koala cloud simulator, 

and we define

anti-fitness as the 

proportion of users not 

served, and we use

differential probability 

analysis on the 

collection of tuples.

Kevin Mills, NIST
NIST Cloud Computing Forum and Workshop VIII

J u l y 2 0 1 5

Model

Element

Parameter Category

Behavior Structure Asymmetry Failure Total

User 28 2 4 0 34

Cloud Controller 21 4 5 0 30

Cluster Controllers 11 5 3 0 19

Nodes 6 0 0 14 20

Intra-Net/Inter-Net 4 11 2 9 26

Totals 70 22 14 23 129

Summary of Koala Parameters to Search Over

Average # values per parameter is about 6, so search space is ≈ 6129

i.e., ≈ 10100 scenarios are possible

 adapted 125-parameter Koala IaaS simulator to be GA controllable 

 added 4 Koala parameters to turn on/off logic to control (a) creation orphans, 

 (b) termination orphans, (c) relocation orphans and (d) administrator actions

Test Case – Can GA find VM Leakage due to message loss and lack of orphan control? 

Failure scenario found manually by accident and described in C. Dabrowski and K. Mills, "VM Leakage and Orphan Control in OpenSource Clouds", Proceedings of IEEE CloudCom 2011, Nov. 29-Dec. 1, Athens, Greece, pp. 554-559.

Kevin Mills, NIST 6
NIST Cloud Computing Forum and Workshop VIII

J u l y 2 0 1 5

7

Generations 500

Population Size 200 Individuals

Elite Per Generation 16 Individuals

Reboot After 200 Generations

Selection Method Stochastic Uniform Sampling

# Crossover Points 3

Mutation Rate 0.001 < Adaptive < 0.01

GENETIC ALGORITHM CONTROL PARAMETERS

Koala GA Search over 500 Generations

(b)

105scenarios, i.e., 200 individuals x 500 generations 

84% of scenarios exhibit anti-fitness ≥ 0.50

Only 8% of scenarios are 

duplicate (equals eliteselection percentage) For Koala simulator, failure scenarios appear within 

first 100-200 generations

Average anti-fitness oscillates around 65% of users not 

served

Kevin Mills, NIST
NIST Cloud Computing Forum and Workshop VIII

J u l y 2 0 1 5

D

PVi 

Outliers contributing to failure scenarios

Outliers contributing to success scenarios

PVs exerting little influence on success or failure

8

Differential Probability Analysis

PV pairs sorted

by decreasing D

Kevin Mills, NIST
NIST Cloud Computing Forum and Workshop VIII

J u l y 2 0 1 5

9

Analysis of Results from Koala GA Search 1 – 500 Generations

Seeking Known Failure Scenario – search duration 30 days

D (y-axis) for 684 PV pairs (x-axis) for first GA search–outlier PV pairs labeled.

Known failure scenario found,

but under previously unknown

circumstances

Kevin Mills, NIST
NIST Cloud Computing Forum and Workshop VIII

J u l y 2 0 1 5

10

Ongoing Work: Do published findings on the spread of 

congestion hold for realistic network models?

Abstract Network Model Add 7 Realism Factors

Config TCP FL SR DE VS NC PD

C0 0 0 0 0 0 0 0 C1 0 0 0 0 0 0 1 C2 0 0 0 0 0 1 0 C3 0 0 0 0 0 1 1 C6 0 0 0 0 1 1 0 C7 0 0 0 0 1 1 1 C10 0 0 0 1 0 1 0 C11 0 0 0 1 0 1 1 C14 0 0 0 1 1 1 0 C15 0 0 0 1 1 1 1 C18 0 0 1 0 0 1 0 C19 0 0 1 0 0 1 1 C22 0 0 1 0 1 1 0 C23 0 0 1 0 1 1 1 C26 0 0 1 1 0 1 0 C27 0 0 1 1 0 1 1 C30 0 0 1 1 1 1 0 C31 0 0 1 1 1 1 1 C50 0 1 1 0 0 1 0 C51 0 1 1 0 0 1 1 C54 0 1 1 0 1 1 0 C55 0 1 1 0 1 1 1 C58 0 1 1 1 0 1 0 C59 0 1 1 1 0 1 1 C62 0 1 1 1 1 1 0 C63 0 1 1 1 1 1 1 C114 1 1 1 0 0 1 0 C115 1 1 1 0 0 1 1 C118 1 1 1 0 1 1 0 C119 1 1 1 0 1 1 1 C122 1 1 1 1 0 1 0 C123 1 1 1 1 0 1 1 C126 1 1 1 1 1 1 0 C127 1 1 1 1 1 1 1

34 Valid Combinations

Most Abstract

Most Realistic

Y: Network Disruption

X: Increasing Load

vs.

 Clustering Analysis 

Kevin Mills, NIST
NIST Cloud Computing Forum and Workshop VIII

J u l y 2 0 1 5

To Learn More

Project Team (the core four)

– Kevin Mills, computer scientist – kmills@nist.gov

– Chris Dabrowski, computer scientist – cdabrowski@nist.gov

– Jim Filliben, statistician – jfilliben@nist.gov

– Sandy Ressler, information visualization specialist – sressler@nist.gov

Project Page

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

Kevin Mills, NIST 11