Predicting Global Failure Regimes in 

Complex Information Systems

DoE COMBINE Workshop September 19, 2012

Kevin Mills, Jim Filliben & Chris Dabrowski

Koala Information Visualizations by Sandy Ressler

see http://math.nist.gov/~SRessler/cloudviz.html for animations and more)
Overview of Our Past & Ongoing Research – with

application to complex information systems, e.g., Internet, Clouds, Grids

What is the problem?

Why is it hard?

Four Approaches we are investigating:

1. Combine Markov Models, Graph Analysis & Perturbation Analysis

2. Sensitivity Analysis + Correlation Analysis & Clustering

3. Anti-Optimization + Genetic Algorithm

4. Measuring Key System Properties Such as Critical Slowing Down

2

 Today’s Topics in 12 Mins.
Past ITL Research: How can we understand the influence of distributed 

control algorithms on global system behavior and user experience?

3

 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

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

Sept. 11, 2012 DoE COMBINE

Using a single process,

simulated > 105

simultaneous TCP flows in

nationwide topologies
 Ongoing & Planned ITL Research: How can we help to 

increase the reliability of complex information systems?

 Research Goals: (1) develop design-time methods that system engineers 

can use to detect existence and causes of costly failure regimes prior to 

system deployment and (2) develop run-time methods that system 

managers can use to detect onset of costly failure regimes in deployed 

systems, prior to collapse.

 Ongoing: investigating

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

Analysis (MCM+CSA+PA) (e.g., Dabrowski, Hunt and Morrison, 

“Improving the Efficiency of Markov Chain Analysis of Complex

Distributed Systems”, NIST IR 7744, 2010).

b. Sensitivity Analysis + Correlation Analysis & Clustering

c. Anti-Optimization + Genetic Algorithm (AO+GA) 

 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

4

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

Sept. 11, 2012 DoE COMBINE
 What is the Problem? 

 Problem: Given a complex information system (represented using a 

simulation model), how can one identify conditions that could cause 

global system behavior to degenerate, leading to costly system outages?

5

 Why is it Hard? – Reason 1

Koala Cloud

Simulator

Sept. 11, 2012 DoE COMBINE

 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 = 132 

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

parameter space of ~10102 (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). ͌

Size of the search space!!
6

 Why is it Hard? – Reason 2

Determining causality is hard when only global system behavior is observable.

(in a complex system, global behavior cannot always be understood, even if behavior 

 of components is completely understood)

Sept. 11, 2012 DoE COMBINE
Innovations in Measurement Science 

Example: Markov simulation and 

perturbation of a minimal s-t cut set 

of a Markov chain graph:

Using simulated failure scenarios in a 

Markov chain model to predict failures in a Cloud

• Corresponds to software failure 

scenario involving multiple 

faults/attacks.

• Simulation identifies threshold 

beyond which increased failure 

incidence causes drastic 

performance collapse

 Verified in target system being 

modeled (i.e., Koala, a large-scale 

simulation of a Cloud)

0.0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1.0

0.0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1.0 Decrease in Probabilities of Transition Proportion of Requests Granted

Total Grants (Large Scale 

Simulation)

Increase in Probability of Transition from Allocating_Partial

state (11) to Transferring_Failure_Estimate state (10). 

Increase in Probability of Transition from Allocating_ Maximum state (9) to Allocating_Partial state (11). 

Decrease in probability of 

transition from Allocating_Maximum

state (9) to Recording_Allocation (12) state. 

Decrease in Probability of Transition 

from Allocating_Partial state (11) to 

Recording_Allocation state (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 

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)

7

 Cut-Set + Perturbation Analysis 

Sept. 11, 2012 DoE COMBINE
8

 Sensitivity Analysis: Determine which parameters most significantly influence 

model behavior and what response dimensions the model exhibits. Allows 

reduction parameter search space and identifies model responses that must be 

analyzed. 

 Correlation Analysis & Cluster: Determine response dimensions of a model

See: Mills, Filliben and Dabrowski, "An Efficient Sensitivity Analysis Method for Large Cloud Simulations", 

Proceedings of the 4th International Cloud Computing Conference, IEEE (2011).

Use 2-level, orthogonal fractional factorial (OFF) 

experiment design to identify the most significant 

parameters of your model

Use correlation analysis and clustering to identify

unique behavior dimensions of your model

 Sensitivity Analysis + CAC

Sept. 11, 2012 DoE COMBINE
9

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

 Anti-Opt. + Genetic Algorithm

Sept. 11, 2012 DoE COMBINE
10

 Critical Slowing Down

A simple univariate example predicting power 

grid blackout in a human engineered system*

*From P. Hines, E. Cotilla-Sanchez, and S. Blumsack. Topological Models and Critical Slowing Down: Two Approaches to Power System Risk Analysis. 

Proceedings of the 44th Hawaii Conference on System Sciences. IEEE Computer Society, Washington, DC, USA, pp. 1-10.

Time before critical transition (minutes)

-8 -7 -6 -5 -4 -3 -2 -1 0

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

-0.1

Sept. 11, 2012 DoE COMBINE
Questions?

11

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:

{cdabrowski, jfilliben, kmills@nist.gov} 

Contact information about Information Visualization:

sressler@nist.gov

 Thanks for Listening

Sept. 11, 2012 DoE COMBINE