Understanding Behavior and Improving 

Reliability in Complex Information Systems

May 9, 2013

Kevin Mills

NIST

 DARPA MRC PI Meeting

Joint work with a long list of collaborators, including statistician Jim Filliben, computer 

scientist Chris Dabrowski, visualization expert Sandy Ressler, data mining expert Dong-Yeon 

Cho, simulation expert Jim Henriksen, electrical engineer Jian Yuan and mathematicians

Fern Hunt & Dan Genin, as well as NSF SURF students Edward Schwartz (incipient PhD from 

CMU), Andrea Haines and Brittany Devine.
Background: Information Systems, increasingly central to the 

nation’s economic well-being and security, are: large, 

distributed, continuously evolving, unpredictable, fragile and 

interdependent – in a word, Complex

May 9, 2013 DARPA MRC PI Meeting 2

Motivation

Problem I: How can we predict the 

effects on macroscopic behavior and 

user experience when new or revised 

components are injected into complex 

information systems?

Problem II: How can we identify lowprobability combinations of conditions 

in complex information systems that 

will drive macroscopic behavior into 

extremely costly failure regimes?

A C

D E G

F

J K

M

P

B L

N

O

A1 A1b

A1c

A1a A2a A2b A2c

C1 C1b

C1c

C1a

C2 C2b C2c C2a H2b

H2c

H2a H1

H1c H1b H1a

E1 E1b E1c E1a

E2b E2a E2c

H1d

H1e

H1f

H2f H2e H2d

G1b

G1c

G1a

G1e G1d G2a G2b G2c

G2e G1f G2d

G2f P1 P2 P1a

P1b

P1c

P1d P2aP2b P2c P2d

P2e

P2f

P2g

K1 K2 K0a

K1a

K1b K1c K1d K2a K2b

K2c

K2d

L2

L1

L1a L1b L1c

L1d

L2a

L2b

L2c L2d

L0a

L0b J1

J2

J1a J1b J1c J1d

J1e

J1f J2a J2b

J2c

J2d J2e J2f N1a N1b

N1c

N1d

N1e N1f N2 N2a

N2b N2c N2d N2e

N2f

M2b

M2c

M2d M2e M2f M2 M2g M1a M2a M M1 1b

M1c

M1dM1e M1f M1g O0a

O1a

O1b

O1c

O1c

O1

O2a

O2

O2b O2c O2d

O2e

O2f O2g

I2 I2a I1 I I0a

I1a

I1b I1c I1d

I2g I2f

I2e

I2d I2b I2c

F2

F2a F1 F1a

F1b F1c F1d

F2g F2f

F2d

F2c F2b F0a F2e

D2 D2a

D1a D1 D1b

D1c D1d

D2g

D2f

D2d D2b D2c D2e

D0a

B0a B B1 1a

B1b

B1c B1d

B2 B2a

B2b

B2c B2d B2e

B2f

B2g H

G1 G2 E2

H2

A2

N1

“The number of websites that would now break if Amazon were 

to go down, and the growing pervasiveness of Amazon behind 

the scenes, is really quite impressive.” Craig Labovitz, DeepField, 

quoted in WIRED ENTERPRISE.

“It is now common knowledge that BGP routing policies can 

interact to produce unexpected routing anomalies such as 

protocol oscillation. We introduce a new class of anomalies, 

where routing is wedged into a local optimum that is very 

difficult to change.” Tim Griffin, Cambridge University
May 9, 2013 DARPA MRC PI Meeting 3

 Hard Problems

Why is it difficult to understand & predict 

behavior in complex information systems? 

y1, ..., ym = f( x1|[1,...,k], ..., xn|[1,...,k] )

Model Response Space Model Parameter Space

For example, the NIST Koala simulator of IaaS Clouds has about n = 130 

parameters with average k = 6 values each, which leads to a model 

parameter space of ~10101 (note that the visible universe has ~1080 atoms) and the 

Koala response space ranges from m = 8 to m = 200, depending on the 

specific responses chosen for analysis (typically m 45). ͌

Reason #1: System state space is immense!!

Why is it difficult to understand & predict 

behavior in complex information systems? 

Reason #2: Emergent behaviors are difficult to predict!!

For example, deploying new client 

software with a reasonable approach

to mitigate domain-name spoofing

attacks in a grid system resulted in

worse performance than ignoring the

attacks, because mitigating the attacks 

shifted the global schedule of job

executions.

Why is it difficult to understand & predict 

behavior in complex information systems? 

Reason #3: Highly improbable events are more

probable than we expect!!

Gaussian and Poissonian assumptions do not hold

in complex systems. Instead, the probability landscape

is better represented by heavy-tailed distributions, 

which means that highly improbably events occur more frequently than we assume. Such improbable 

events often lead to very expensive system-wide 

performance degradation or collapse.
How can we understand the influence of distributed control 

algorithms on global system behavior and user experience?

4

 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

 Past Research 2006-2011

What to measure

Under what conditions

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

At an affordable cost

May 9, 2013 DARPA MRC PI Meeting INTERNET IaaS CLOUDS
May 9, 2013 DARPA MRC PI Meeting 5

 Sample Techniques

Use experiment design theory to reduce

parameter combinations to 256

Use sensitivity analysis

to identity six most

significant parameters

(232)

1000

2

20

2

20-12

Discard parameters not germane to study – reduce by 944 parameters

O(109633)

[ 1080 = atoms in visible universe]

(232)

56 O(10539)

(232)

20 O(10192)

O(106)

256

Model Reduction

Experiment

Design Theory

2

6-1 32

Group related remaining parameters– reduce by 36 parameters

Select only 2 values for each parameter

Use experiment design theory again to reduce

parameter combinations to 32

Level Reduction

Sensitivity

Analysis

Parameter 

Reduction Techniques

We identified an 8-dimensional response space within the 40 responses

Response DimensionSA1-small

(9 dimensions)

SA1-large

(8 dimensions)

SA2-small

(10 dimensions)

SA2-large

(9 dimensions)

Cloud-wide Demand/Supply Ratio

y1, y2, y3, y5, 

y6, y8, y9, y10, 

y13, y23, y24, 

y25, y29, y30, 

y32, y34, y36, 

y38

y1, y2, y3, y5, 

y6, y7, y8, y9, 

y10, y13, y23, 

y34, y25, y29, 

y30, y32, y33, 

y34, y36, y38

y1, y2, y3, y5, 

y6, y8, y9, y10, 

y11, y13, y14,

y15, y23, y24, 

y25, y38

y1, y2, y3, y5, 

y6, y8, y9, y23, y24, 

y25, y38

Cloud-wide Resource Usage

y10, y11, y12, 

y13, y14, y15

y10, y11, y12, 

y13, y14, y15 y10, y11, y12, 

y13, y14, y15

y10, y11, 

y12, y13, y14, 

y15

Variance in Cluster Load

y16, y17, y18, 

y19,y20, y21, y26, y27

y16, y17, y18, 

y19,y20, y21, y26, y27

y16, y18, y19,

y20, y21, y26, y27

y16, y17, y18, y19,y20, y21, y17 (Mem. y26, y27

Util)

Mix of VM Types

y34, y35 (WS) y31 (MS)

y12, y14, y15, 

y30, y31, y33, 

y34, y35, y36

y14, y15, y30, y31, y33, 

y34, y35 y31 (MS) y15, y36 (DS)

Number of VMs y29, y37 y37 y29, y37 y29

User Arrival Rate y4 y4 y4 y4, y37

Reallocation Rate y7, y22 y7, y22 y7 (cluster) y7, y22 y22 (node) Variance in Choice of Cluster y28 y28 y28 y28

Compute correlation coefficient 

(r) for all response pairs

Examine frequency distribution 

for all |r| to determine 

threshold for correlation pairs 

to retain; |r| > 0.65, here

Create clusters of mutually 

correlated pairs; each cluster 

represents one dimension

Select one response from each 

cluster to represent the 

dimension; we selected 

response with largest mean 

correlation that was not in 

another cluster*

*Not possible for cloud-wide resource usage in SA2-small, so we selected response with highest mean correlation.

Response Reduction Techniques

Retransmission Rate

Conditions

Sorted Residual Analyses to Reveal Causality Cluster Analyses Over All Responses

outliers
May 9, 2013 DARPA MRC PI Meeting 6

 Sample Results

INTERNET

INTERNET

INTERNET INTERNET CLOUD

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

 Ongoing: 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) – example

to be presented in some depth

 Planned: 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).

 Ongoing Research 2011-

7

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

How can we increase the reliability of complex information systems?

May 9, 2013 DARPA MRC PI Meeting

CLOUD &

INTERNET
8

 Design-Time Example One

May 9, 2013 DARPA MRC PI Meeting

Example Markov Chains + Cut-set Analysis + Perturbation Analysis

EXTRACT FINITE-STATE MACHINE (FSM)

FROM SIMULATION MODEL OR SYSTEM

TREAT FSM AS GRAPH AND

CONDUCT CUT-SET ANALYSIS

Initial Wait Disc Ngt Mon Compl Fail

Initial 0.9697 0 0.303 0 0 0 0

Wait 0 0.7958 0.0634 0.1375 0 0 0.0033

Disc 0 0.1211 0.7387 0.1402 0 0 0

Ngt 0 0.1375 0.0190 0.2933 0.1950 0 0.0001

Mon 0 0 0 0.0003 0.9917 0.0080 0

Compl 0 0 0 0 0 1.0 0

Fail 0 0 0 0 0 0 1.0

INSTRUMENT MODEL AND

BUILD MARKOV CHAIN PERTURB MARKOV CHAIN AT CUTS
9

 Design-Time Example Two

May 9, 2013 DARPA MRC PI Meeting

Example: Anti-Optimization + Genetic Algorithm

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.

Measures of Anti-Fitness (e.g., proportion of

un-served users)

GENETIC ALGORITHM

Principal Components Analysis,

Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Growing Collection of Anti-Fitness 

Reports

{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
10

 Design-Time Example Two

May 9, 2013 DARPA MRC PI Meeting

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.

Measures of Anti-Fitness (e.g., proportion of

un-served users)

GENETIC ALGORITHM

Principal Components Analysis,

Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Growing Collection of Anti-Fitness 

Reports

{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
May 9, 2013 DARPA MRC PI Meeting 11

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)
May 9, 2013 DARPA MRC PI Meeting 12

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

Virtual Machine (VM) Types Simulated in Koala

Four of 22 Physical Platform Types Simulated in Koala

(2) SUPPLY LAYER
May 9, 2013 DARPA MRC PI Meeting 13

(1) DEMAND LAYER

Description of User Types Simulated in Koala

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)
May 9, 2013 DARPA MRC PI Meeting 14

Finite-State Machine of Simulated User Behavior in Koala

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

(1) DEMAND LAYER - USER BEHAVIOR

Also can increase

VM instances
15

CLUSTERS

NODES

NODES

NODES

CLUSTERS CLUSTERS CLUSTERS CLUSTERS CLUSTERS

Utilizations Loads

vCore Memory Disk Space pCore Disk Network

Snapshot of Simulated Cloud State from a 10-D Koala Animation

(Heat Value for 6 Metrics for each of 10 Clusters x 100 Nodes/Cluster after 90 Hours)

SYSTEM BEHAVIOR – ENCOMPASSING LAYERS (1) – (4) 

May 9, 2013 DARPA MRC PI Meeting
16

 Design-Time Example Two

May 9, 2013 DARPA MRC PI Meeting

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.

Measures of Anti-Fitness (e.g., proportion of

un-served users)

GENETIC ALGORITHM

Principal Components Analysis,

Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Growing Collection of Anti-Fitness 

Reports

{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
May 9, 2013 DARPA MRC PI Meeting 17

Summary of Koala Parameters to Search Over

Model

Element

Parameter Category

Behavior Structure Failure Asymmetry Total

User 28 2 0 4 34

Cloud Controller 21 4 0 5 30

Cluster Controllers 11 5 0 3 19

Nodes 6 0 14 0 20

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

Totals 70 22 23 14 129

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.
May 9, 2013 DARPA MRC PI Meeting 18

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

Measures of Anti-Fitness (e.g., proportion of

un-served users)

GENETIC ALGORITHM

Principal Components Analysis,

Clustering, ...

MULTIDIMENSIONAL ANALYSIS TECHNIQUES

Growing Collection of Anti-Fitness 

Reports

{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

19

 Design-Time Example Two

May 9, 2013 DARPA MRC PI Meeting
May 9, 2013 DARPA MRC PI Meeting 20

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
May 9, 2013 DARPA MRC PI Meeting 21

Dynamics of GA’s Search

GENETIC ALGORITHM CONTROL PARAMETERS

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

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

Average Anti-Fitness

Restarted 

Generation 311

0

0.05

0.1

0.15

0.2

0.25

0.3

0 100 200 300 400 500

Generation

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

Maximum Anti-Fitness Discovered
May 9, 2013 DARPA MRC PI Meeting 22

Assessment of Search Conducted by GA

(based on 105scenarios, 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)

Conclusion: GA is searching scenarios with high anti-fitness and 

 the scenarios searched are overwhelmingly unique

0

0.05

0.1

0.15

0.2

5

101520253035404550556065707580859095

100

Anti-Fitness

Frequency Distribution of Anti-Fitness
-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) 

May 9, 2013 DARPA MRC PI Meeting 23

Failure Scenarios Discovered by GA

≥ 0.15 ≤ -0.15

Parameter Value Difference

P_CreateOrphanControlOn 0 0.58

P_averageUserRequestTimeout 30 0.42

P_averageThinkTime 900 0.33

P_nodesPerCluster 200 0.31

P_userRestPeriodMultiplier 32 0.25

P_nodesPerCluster 400 0.2

P_MinMaxInstanceLoad 0 0.16

P_maximumRestPeriods 6 0.15

P_minimumReservationRetries 2 0.15

P_averageThinkTime 1500 -0.15

P_MinMaxInstanceLoad 1 -0.16

P_clusterAllocationAlgorithm 2 -0.18

P_averageUserRequestTimeout 120 -0.19

P_CreateOrphanControlOn 1 -0.58

Statistically

Significant

Not Statistically

Significant

GA also found that an overload problem 

arises when clusters are too small

GA discovered that lack of orphan control

leads to system failure, conditioned on

user request timeouts being too short,

which causes virtual message losses
May 9, 2013 DARPA MRC PI Meeting 24

Costs of Search

• Pre-search work required significant programming effort to

– Increase cloud simulator robustness

– Create robust distributed management system for GA and simulations 

running a cluster

• Computing resources used

– Generation one: 200 cores on a local cluster

– Subsequent generations: 184 cores on a local cluster (16 cores acting as 

warm standbys to take over for failed simulations)

• Search latency about 30 days (as designed) for 500 Generations

• Failure scenarios are evident within 100 Generations, which 

requires about 6 days
25

 Run-Time Research Goals

May 9, 2013 DARPA MRC PI Meeting

Academia Industry

Pro Models + Theory Monitoring for Real Networks

Con Abstract Models Reactive, No Models/No Theory

Impact, If Successful:

David Lambert, Internet 2: “...will create a strong foundation of system measurement 

that has not existed before that is likely to help avoid 

potentially debilitating real-life network failures and 

their scientific and economic consequences.”

Iraj Saniee, Bell Labs: “...the proposed research would help fill a vacuum in 

commercial network control and management systems...”

Craig Lee, Aerospace: “This line of work must be pursued, and its results used to 

shape satellite ground systems of the future.” 

Problem: Catastrophic events manifest over extended space & time, e.g., 

congestion, attacks, cascading failures, disconnections 

State-o f-the-Art: (1) Identify precursor S/T patterns in our realistic net models

(2) Assess detection techniques for applicability to real nets

(3) Apply thermodynamic models & theory to explain catastrophic events

New Ideas: 
26

 Take Home Messages

May 9, 2013 DARPA MRC PI Meeting

If you want to evaluate your MRC algorithms in large simulated 

deployment scenarios, NIST has expertise in relevant techniques –

and would be willing to help apply them.

If you want to investigate the robustness of your innovative MRC 

algorithms, NIST would be interested in collaborating to apply and 

evaluate techniques to identify design-time failure scenarios.

If you are interested in exploring run-time methods to predict 

incipient systemic failures, NIST has interest in collaborating on that 

topic.
May 9, 2013 DARPA MRC PI Meeting 27

 Contact Information

Kevin Mills, NIST 

Principal Investigator

Measurement Science for Complex Information Systems

Email: kmills@nist.gov

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

Additional Questions?