Combining Genetic Algorithms & Simulation to

Search for Failure Scenarios in System Models

Kevin Mills

National Institute of Standards & Technology (NIST)

Joint work with NIST colleagues: Chris Dabrowski

Jim Filliben

Sandy Ressler

University of North Texas Seminar

June 28, 2016
Outline

• Motivation & Context

• Method

• Case Study

– Koala IaaS Cloud Simulator

– Searching for Failure Scenarios

– Evaluating Method

• Conclusions & Future Work

June 28, 2016 UNT Seminar 2
3

GROWING GLOBAL DEPENDENCE ON COMPLEX INFO. SYSTEMS

June 28, 2016 UNT Seminar
4

WE CAN BUILD & DEPLOY SUCH SYSTEMS, BUT CAN WE UNDERSTAND,

PREDICT & CONTROL THEM?

June 28, 2016 UNT Seminar
5

PAST NIST RESEARCH FROM 2006-2011

How can we understand the influence of distributed control 

algorithms on global system behavior and user experience?

 Mills, Filliben, Cho, Schwartz and Genin, Study of Proposed 

Internet Congestion Control Mechanisms, NIST SP 500-282 (2010).

 Mills and Filliben, "Comparison of Two Dimension-Reduction 

Methods for Network Simulation Models", Journal of NIST 

Research 116-5, 771-783 (2011).

 Mills, Schwartz and Yuan, "How to Model a TCP/IP Network using 

only 20 Parameters", Proceedings of the Winter Simulation 

Conference (2010). 

 Mills, Filliben, Cho and Schwartz, "Predicting Macroscopic 

Dynamics in Large Distributed Systems", Proceedings of ASME 

(2011).

 Mills, Filliben and Dabrowski, "An Efficient Sensitivity Analysis 

Method for Large Cloud Simulations", Proceedings of the 4th

International Cloud Computing Conference, IEEE (2011).

 Mills, Filliben and Dabrowski, "Comparing VM-Placement 

Algorithms for On-Demand Clouds", Proceedings of IEEE 

CloudCom, 91-98 (2011).

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

What to measure

Under what conditions

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

At an affordable cost

Internet

Cloud

June 28, 2016 UNT Seminar
6

 Research Goals: (1) develop and evaluate design-time methods that 

system engineers can use to detect existence and causes of costly failure 

regimes prior to system deployment and (2) develop and evaluate runtime methods that system managers can use to detect onset of costly 

failure regimes in deployed systems, prior to collapse.

 Recent: investigating design-time methods –

a. Markov Chain Modeling + Cut-Set Analysis + Perturbation 

Analysis (e.g., Dabrowski, Hunt and Morrison, “Improving

the Efficiency of Markov Chain Analysis of Complex

Distributed Systems”, NIST IR 7744, 2010).

b. Anti-Optimization (AO) + Genetic Algorithm (GA) – TODAY’S

SEMINAR

 Ongoing: investigate run-time methods based on approaches that may 

provide early warning signals for critical transitions in large systems (e.g., 

Scheffer et al., “Early-warning signals for critical transitions”, NATURE, 461, 53-59, 2009).

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

How can we increase the reliability of complex information systems?

ONGOING NIST RESEARCH FROM 2012-PRESENT

June 28, 2016 UNT Seminar
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

June 28, 2016 UNT Seminar 7
Case Study Topics

8

1. Koala Simulator

2. Koala Parameters & Representation as Chromosomes

3. Genetic Algorithm

4. Population of Koala Simulators

5. Dynamics of GA Search

6. Analysis Method

7. Results from Four GA Searches

June 28, 2016 UNT Seminar
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

9

Topic 1: Koala Simulator

In our case study we defined anti-fitness as the proportion of arriving users not served

June 28, 2016 UNT Seminar
 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

VM1VM1VM1VM1 VM1VM1VM1VM1VM1 VM1VM1VM1VM1VM1 VM1

Cluster 

Controller #cm

(1)

(4)

(4) (3)

(2)

(4) (4)

(5)

Schematic of Koala IaaS Cloud Simulator

Demand and supply layers modeled after Amazon EC2 

Internal structure modeled after Eucalyptus v1.6

June 28, 2016 UNT Seminar 10
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

11

Topic 2: Koala Parameters & GA Representation

as Chromosomes (i.e., bit strings) 

June 28, 2016 UNT Seminar
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 

Open-Source Clouds", Proceedings of IEEE CloudCom 2011, Nov. 29-Dec. 1, Athens, Greece, pp. 554-559.

June 28, 2016 UNT Seminar 12
Sample Chromosome Specification

PARAMETER MIN MAX PRECISION #VALUES LOW_BIT HIGH_BIT #BITS

P_CreateOrphanControlOn 0 1 1 2 3 6 3 6 1

P_TerminationOrphanControlOn 0 1 1 2 5 8 5 8 1

P_RelocationOrphanControlOn 0 1 1 2 1 1 1 1 1

P_AdministratorActive 0 1 1 2 330 330 1

P_clusterAllocationAlgorithm 0 5 1 6 3 1 3 3 3

P_describeResourcesInterval 600 3600 600 6 8 1 8 3 3

P_nodeResponseTimeout 3 0 9 0 3 0 3 210 211 2

P_TerminatedInstancesBackOffThreshold 3 6 1 4 5 6 5 7 2

P_TerminationBackOffInterval 180 360 6 0 4 8 8 8 9 2

P_TerminationRetryPeriod 600 1200 300 3 316 317 2

P_StaleShadowAllocationPurgeInterval 600 3600 600 6 242 244 3

P_cloudAllocationCriteria 0 3 1 4 321 322 2

P_clusterShadowPurgeLimit 1 2 1 5 5 290 292 3

P_instancePurgeDelay 180 600 6 0 8 9 8 100 3

P_clusterEvaluationResponseTimeout 6 0 120 3 0 3 1 4 1 5 2

P_MaxPendingRequests 1 1 0 1 1 0 7 2 7 5 4

P_CloudTerminatedInstancesBackOffThreshold 3 6 1 4 169 170 2

P_CloudTerminationBackOffInterval 180 360 6 0 4 4 0 4 1 2

P_CloudTerminationRetryPeriod 3600 10800 1800 5 297 299 3

P_ClusterShutdownGracePeriod 86400 2.59E+05 43200 5 147 149 3

P_RequestEvaluatorTimeoutWaitProportion 0.1 0.4 0.1 4 145 146 2

P_RequestEvaluatorClusterMinimumResponse 0.6 0.9 0.1 3 269 270 2

P_MaxRelocationDuratonProportion 0.65 0.95 0.1 4 9 0 9 1 2

P_MaximumRelocateDescribeRetries 4 1 6 2 7 254 256 3

P_AverageCloudAdministratorAttentionLatency 28800 86400 14400 5 308 310 3

P_AverageCloudAdministratorShutdownDelay 300 900 300 3 4 5 4 6 2

P_avgTimeToClusterCommunicationCut 2.88E+06 2.88E+07 2.88E+06 1 0 217 220 4

Genetic Algorithm Computed

Chromosome Map (Size = 2334)

Koala Parameter 

Space (Size = 10100)

June 28, 2016 UNT Seminar 13
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

14

Topic 3: Genetic Algorithm

June 28, 2016 UNT Seminar
Genetic Algorithm Flow Chart

Generate Needed Random Population of Individuals

Terminate? Evaluate Fitness Stop

Elite Individuals? Population of Individuals

YES

YES COPY TO NEXT GENERATION Select Candidate Individuals NO or YES

Reboot? Elite Individuals?

YES COPY TO NEXT GENERATION

NO or YES YES NO

Candidate Individuals

Choose Pair From Candidate Individuals Crossover? Choose Crossover Points & Swap Chromosomes Population of Recombined Individuals

Mutate Individual? Iterate Over Individuals Flip Chromosomes as Required

Start

YES NO

YES NO

INSERT PAIR INTO RECOMBINED POPULATION

INSERT INSERT IN NEXT POPULATION

INSERT PAIR

NO

SELECT

RECOMBINE

MUTATE

REBOOT?

EVALUATE

SEED

POPULATION

DONE?

1

2

3

4

5

6

7

June 28, 2016 UNT Seminar 15
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

16

Topic 4: Population of Koala Simulators

June 28, 2016 UNT Seminar
17

Head Node 1

Head Node 2

Shared File

Store

Compute Node 1 Compute Node 2 Compute Node 12

Compute Node 13 Compute Node 14 Compute Node 24

Enterprise Network

Cluster Network

License Server 8 Koala Processes

8 Koala Processes

12 Koala Processes

12 Koala Processes 12 Koala Processes

200 Koala Working Directories GA Checkpoint Database

Node Manager Job Manager

GA Controller GA Management Processes

CLUSTER GA Results Tuples

Population of Koala Simulators Deployed on a High 

Performance Computing Cluster

June 28, 2016 UNT Seminar
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

18

Topic 5: Dynamics of GA Search

June 28, 2016 UNT Seminar
19

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

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0 100 200 300 400 500

Generation

(a) Average Anti-Fitness

0

0.05

0.1

0.15

0.2

0.25

0.3

0 100 200 300 400 500

Generation

(b) Standard Deviation in Anti-Fitness

0.7

0.72

0.74

0.76

0.78

0.8

0.82

0.84

0 100 200 300 400 500

Generation

(c) Maximum Anti-Fitness Discovered

One GA Search over 500 Generations

June 28, 2016 UNT Seminar
20 0

0.05

0.1

0.15

0.2

5

101520253035404550556065707580859095

100

Anti-Fitness

Frequency Distribution of Anti-Fitness

Assessment of Search Conducted by GA

(based on 105 scenarios, i.e., 200 individuals x 500 generations) 

• 84% of scenarios exhibit anti-fitness ≥ 0.50

• Only 8% of scenarios are duplicate (equals elite-selection percentage)

• For Koala simulator, failure scenarios appear within first 100-200 generations

June 28, 2016 UNT Seminar
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

21

Topic 6: Analysis Method

June 28, 2016 UNT Seminar
-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0 100 200 300 400 500 600 700

i = 684 Parameter-Value Pairs

P(PVi|f>0.70) - P(PVi|f<0.15) 

D

PVi 

Outliers contributing to failure scenarios

Outliers contributing to success scenarios

PVs exerting little influence on success or failure

22

Differential Probability Analysis

June 28, 2016 UNT Seminar
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

23

Topic 7: Results from Four GA Searches
24

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0 100 200 300 400 500 600 700

CreateOrphanControlOn = FALSE

AvgUserRequestTimeout = 30

AvgThinkTime = 900

CreateOrphanControlOn = TRUE

NodesPerCluster = 200

UserRestPeriodMultiplier = 32

NodesPerCluster = 400

Analysis of Results from 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.

June 28, 2016 UNT Seminar

No Orphan Control &

User Timeout Too Short

Users Too Persistent

Clusters Too Small - Overload
25

Analysis of Results from GA Search 2 – 205 Generations

Seeking Previously Unknown Failure Scenarios – search duration 14 days

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

June 28, 2016 UNT Seminar

-0.3

-0.2

-0.1

0

0.1

0.2

0.3

0.4

0.5

0 100 200 300 400 500 600 700

AvgUserRequestTimeout = 30

AvgThinkTime = 900

UserRestPeriodMultiplier = 32

NumberofSitesReservedForCloud = 2

NodesPerCluster = 200

MilesPerRouterHop = 500

MaxPerHopDelay = 0.9

StdUserRequestTimeout = 30

NodesPerCluster = 400

AvgUserRequestTimeout = 120

NumberofSitesReservedForCloud = 1

AvgThinkTime = 1500

MilesPerRouterHop = 1500

Users Too Persistent

Clusters Too Small –

Overload

Users Less 

Persistent

Longer

User Timeouts 

smaller 

communication 

delays in cloud

User Timeouts Too Short, exacerbated by small std dev and 

by greater communication 

delays within cloud
-0.3

-0.2

-0.1

0

0.1

0.2

0.3

0.4

0.5

0.6

0 100 200 300 400 500 600 700

NodesPerCluster = 600 UserTypeArraySelector = 4

AvgThinkTime = 1200 AvgUserRequestTimeout = 90

SiteDistanceMultiplier = 7

MinSiteCoordinate = 0 UserRestPeriodMultiplier = 32

StdUserRequestTimeout = 30

MinReservationRetries = 2

AvgInterUserStartDelay = 30

MinIntrasiteDelay = 2x10-8

MinClusters = 9

MaxSiteCoordinate = 16000

MaxPerHopDelay = 0.9

MaxIntrasiteDelay = 1.5x10-5

CloudSizeChangeFraction = 0.3

ClusterResponseTimeout = 120

MaxIntersiteLossRate = 10-7

PlatformTypeArraySelector = 4 ProbabilityImageNotFound = 10-6

ChoosePlatformTypesRandomly = FALSE

RandomizeMinMaxVMsRequested = TRUE

MinRestPeriods = 2

NodeResponseTimeout = 30

26

Analysis of Results from GA Search 3 – 209 Generations

Nudging up Some Parameter Ranges and Seeking Additional Failure Scenarios -

search duration 16 days

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

June 28, 2016 UNT Seminar

Identify parameter settings that lead to

failures and parameter settings that

lead to success -> i.e., optimization
27

Next slide, shows the differential probability analysis for the combined tuple collection

As an example, we augmented GA search 3 with a 4th GA search looking for 

success scenarios, and combined the tuple collections from searches 3 and 4 

to yield |L| = 42253 scenarios and |H| = 14601

June 28, 2016 UNT Seminar
28

Analysis of Results from GA Search 4 – 209+205 Generations

Including additional PV pairs in L discovered by GA searching for success scenarios

- search duration 14 days

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

0 100 200 300 400 500 600 700

AvgUserRequestTimeout = 90 AvgThinkTime = 1200

SiteDistanceMultiplier = 7 UserRestPeriodMultiplier = 32

NodesPerCluster = 600 UserTypeArraySelector = 4

MinSiteCoordinate = 0 StdUserRequestTimeout = 30

MaxSiteCoordinate = 16000 AvgInterUserStartDelay = 30

MinIntrasiteDelay = 2x10-8 MinReservationRetries = 2

MinClusters = 9 RandomizeMinMaxVMsRequested = FALSE

AvgAdminDelay = 900 CloudSizeChangeFraction = 0.3

ClusterResponseTimeout = 120

RandomizeMinMaxVMsRequested = TRUE

NodeResponseTimeout = 30

MinRestPeriods = 2

ChoosePlatformTypesRandomly = FALSE

MaxSiteCoordinate = 12000

AvgAdminDelay = 300

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

June 28, 2016 UNT Seminar

Increasing the samples of success scenarios

does not change the main findings of the

GA with respect to optimization of parameters
SUMMARY:

• Defined a design-time method, combing GA search with simulation, 

to seek failure scenarios in system models

• Applied the method in a case study, seeking (and finding) a known 

failure scenario in an existing cloud simulator

• Iterated search to reveal previously unknown failure scenarios

FINDINGS:

• GA searches explored predominantly non-duplicative scenarios with 

high anti-fitness

• Uncovered evidence that GA search can reveal insights about 

optimal parameters settings, while simultaneously searching for 

failure scenarios

• GA search should be pursued only for systems with sufficient 

schedule time, and where failure scenarios have high cost

29

Conclusions

June 28, 2016 UNT Seminar
• Additional analysis methods need to be explored:

– Use statistical and information-theoretic techniques to extract features 

from collected tuples

– Apply clustering algorithms to suggest specific classes of failure scenarios

• Continue to explore our case study:

– Uncover parameter subspaces where no failure scenarios can be found

– Search under alternate definitions of anti-fitness 

• Apply method to models of other complex systems:

– Communication networks

– Electrical grids

– Epidemic networks

– Network attack models

• Investigate run-time methods to provide early warning of incipient 

failures

30

Future Work

June 28, 2016 UNT Seminar
RELATED INFORMATION

31

Project Web Page: http://www.nist.gov/itl/antd/emergent_behavior.cfm

Project Team:

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

Paper: K. Mills, C. Dabrowski, J. Filliben and S. Ressler, 

"Combining Genetic Algorithms and Simulation to 

Search for Failure Scenarios in System Models", 

Proceedings of the 5th International Conference on 

Advances in Simulation, Venice, Italy, October 2013.

June 28, 2016 UNT Seminar