Early Warning of Network 

Catastrophes

K. Mills, C. Dabrowski, J. Filliben, F. Hunt, and B. Rust

Information Technology Laboratory

August 28, 2014
Proposal in a Nutshell

Goal: Provide early warning of looming network catastrophes,

 so operators can take remedial actions

Approach: Transform theory into practical measurement

 method, creating new capability to monitor and 

 manage networks

Impact:

 Improve resilience of nation’s networks

 Reduce cost of widespread outages and degradations

 Transfer methods to other systems of national 

 importance, e.g., computational clouds, cyber-

 physical systems, smart power grids

August 28, 2014 Early Warning of Network Catastrophes 2
Argument in Brief

Problem/Opportunity

o Cost of outages/degradations in networks large and growing

o Network outages/degradations spread in space and time

o Spreading process modeled as percolation from statistical physics

o Near a critical point process exhibits measureable precursor signals

o To date, precursor signals shown in abstract network models only

We propose to

I. Validate precursor signals in realistic network models

II. Design, develop, and test measurement method and related 

monitoring & analysis software deployable in real networks

III. Evaluate monitoring & analysis software with partners

August 28, 2014 Early Warning of Network Catastrophes 3
Network Outages and Degradations: 

Crippling, Costly, and Continuing

Infonetics study of network downtime costs in six selected companies

Dec 

2006

May 

2007

Jan 

2008

Dec 

2009

Nov 

2010

Apr 

2011

Dec 

2012

Feb 

2013

May 

2014

Pentagon Police Hit

By ‘Catastrophic’ 

Network Outage

Food Stamp System in 

17 States affected 

by Outage

Disaster On the Net:

Internet Outages

Caused by Taiwan

Earthquakes

Netflix Crippled by 

AWS Outages 

on Christmas Eve

Amazon Cloud 

Failure Takes 

Down Web Sites

15% of All Internet

Traffic Secretly

Rerouted Through

China

Amazon EC2 Cloud

Service Hit by 

Botnet Outage

Internet Failure

Hits Several

Continents

Cisco Routers 

Caused Major

Outage in Japan

August 28, 2014 Early Warning of Network Catastrophes 4

Network outages and degradations can last for hours, days, or weeks

Company/

Sector

Across 5000 US companies the cost is about $85B/yr
August 28, 2014 Early Warning of Network Catastrophes 5

Apr 22, 2011

Apr 29, 2011

Costs will Grow as Network Dependence 

Increases due to Cloud Computing 

Sampling of Cloud Outages over 15 Months: Apr 2011-July 2012

Jun 30, 2012

Feb 29, 2012

Jul 2, 2012

Jul 3, 2012

Jul 3, 2012

Jul 10, 2012

Jul 12, 2012

Jul 13, 2012

Jul 26, 2012
August 28, 2014 Early Warning of Network Catastrophes 6

Commercial US Internet Service Provider Network

Global Internet Autonomous System Network

US Internet2 Academic Network

11,174

nodes 

218

nodes 

2D Lattice Network

64

nodes 

Network	mod

are	links;	num

router;	packe

network	and	

Routers	can	f

chosen	with	a

many	packets

qi( ,t)	=	queue	length	of	router i at	time	t

Total	packets	q

Self-Similar	Fluctuation	in	Mean	Queue	Length	

ρ 

uncongested

Fluctuation

circa 2001

Networks: Graphical Topologies Spanning Space and 

Exhibiting Time-Varying Dynamics

172

nodes 
August 28, 2014 Early Warning of Network Catastrophes 7

Like Physical Systems, Networks Exhibit: 

Spatial Structure, Microscopic Behavior, and 

Macroscopic Spatiotemporal Dynamics

Explanatory Example: Data Stream between NIST and Google
Outages and Degradations Spread 

across Networks in Space and Time

Empty 2D Lattice Congestion Persistent Congestion Spreading Congestion Widespread

TIME

IMPLICATION: SHOULD BE POSSIBLE TO DETECT THE SPREADING 

 PROCESS AND PROVIDE EARLY WARNING OF

 INCIPIENT CATASTROPHE

August 28, 2014 Early Warning of Network Catastrophes 8

PACKET INJECTION RATE

2D lattice animation taken from “Percolation Theory Lecture Notes”, Dr. Kim Christensen, Imperial College London, October 9, 2002

Congestion Sporadic 
Spreading Process often Modeled as 

Percolation from Statistical Physics

P∞

p

pc

0

1

1

Below pc

no GCC

Above pc

GCC forms and grows

to include all nodes 

Percolation  spread of some property in a lattice (or graph) leading to the formation 

of a giant connected component (GCC), as measured by P∞, the proportion of nodes 

encompassed by the GCC

p is probability a node has property

pcis known as the critical point

p < pc  no spread

p = pc  percolation phase transition

p > pc  spread occurs, and expands

 with increasing p

Near a critical point, the process exhibits precursor signals,

typically attributable to increasing, systemic correlation

August 28, 2014 Early Warning of Network Catastrophes 9
Academics Model Spreading Network 

Congestion as a Percolation Process

Precursor Signals 

Appear in 

Communication 

Network Models

August 28, 2014 Early Warning of Network Catastrophes 10
Penn State Researchers (Sarkar, Mukherjee, Srivastav, and Ray 2009)

find increasing transit delay as p > pc = 0.3

Increasing slope in time series of selected measured variables could signal crossing a 

critical point, allowing network managers to be alerted prior to network collapse

August 28, 2014 Early Warning of Network Catastrophes 11

Aggregate Avg. Transit Delay (D*) vs. Network Load (λ) Sampled Avg. Transit Delays (D) for Four Network Loads (λ)
Boston University Researchers (Rykalova, Levitan, and Browe 2010) 

find increased correlation in time series of 

packets in transit as p nears pc = 0.2 

# Packets fluctuate between 260 and 380 # Packets fluctuate between 18,000 and 34,000

August 28, 2014 Early Warning of Network Catastrophes 12

Increasing autocorrelation in time series could signal an approaching critical point, 

allowing network managers to be warned prior to network collapse
Why hasn’t theory been transformed 

into practical measurement method?

August 28, 2014 Early Warning of Network Catastrophes 13

Theoretical Models Lack 10 Key Characteristics of Real Networks

Thus the applicability of the theory is unclear to industry

1. Human-engineered, tiered topologies

2. Router buffer sizes finite

3. Router speeds varied to meet demands, limit losses

4. Injection from sources and receivers only at lowest tier

5. Distribution of sources and receivers non-uniform

6. Connection of sources/receivers with few varied speeds

7. Duty cycle of sources exhibits cyclic behavior

8. Human sources exhibit limited patience

9. Sources transfer flows of various sizes

10. Flows use the Transmission Control Protocol (TCP) to 

modulate injection rate based on measured congestion

Network

Factors

Attachment

Factors

User

Factors

Protocol

Factor
Project Aim & Plan

Aim: Transform theory into practical measurement

 method, creating new capability to monitor and 

 manage networks

Phase I – Validate & characterize existing theory

Phase II – Develop & test measurement method

Phase III – Transfer technology & conduct further 

 evaluation

August 28, 2014 Early Warning of Network Catastrophes 14
Phase I – Validate & characterize existing theory

• Task 1: Validate theory in realistic simulations

– How does realism influence percolation?

– Which precursor signals are most effective?

• Task 2: Explore simulated measurement methods

– Where to measure? 

– How do choice of measurement interval and alerting 

threshold influence false positives/negatives?

• Task 3: Verify findings with emulation (>> realism)

– Deploy model scenarios in Emulab (http://emulab.antd.nist.gov)

– Do simulated findings hold under emulation?

August 28, 2014 Early Warning of Network Catastrophes 15
Phase II – Develop & test measurement method

• Task 4: Design measurement method

– What proportion of nodes must be monitored?

– What monitoring points most effective?

– What measurement intervals and thresholds best?

• Task 5: Develop measurement & analysis software

– Leverage existing perfSONAR platform

– Construct analysis & alerting software

• Task 6: Test software using emulation

– Deploy in Emulab

– Test early warning for selected scenarios

August 28, 2014 Early Warning of Network Catastrophes 16
Phase III – Technology transfer & further evaluation

• Task 7: Release measurement & analysis software

– Package for public distribution

– Distribute via perfSONAR and/or similar channels

• Task 8: Evaluate software in real deployments

– Identify and provide any needed improvements

– Leverage perfSONAR consortium

– Expand into commercial partnerships

August 28, 2014 Early Warning of Network Catastrophes 17
What Impact?

• If completely successful: transfer theory to practice

– Improve resilience of nation’s networks

– Reduce cost of widespread outages and degradations

– Transfer methods to other systems of national 

 importance, e.g., computational clouds, cyber-physical 

 systems, smart power grids

• If minimally successful: explain limits of theory

– Increase confidence in the nation’s networks

– Stimulate new directions for ongoing academic research

August 28, 2014 Early Warning of Network Catastrophes 18
Who Would Benefit?

August 28, 2014 Early Warning of Network Catastrophes 19

David Lambert, Internet2: “...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 ... systems of the future.” 

Network

Operators

Equipment

Vendors

Network Users
Why NIST?

• National need (Presidential Policy Directive 21 – Feb. 12, 2013)

– Network outages costly, crippling, and continuing

– Growing national dependence on networks

• Incentives not available in academe or industry

– Focus on measurement problems of national importance

– Commitment to sufficient time horizon

– Flexibility to produce diverse outputs as required

• Well positioned, qualified team 

– Deep knowledge modeling realistic networks

– Decade of experience studying Internet congestion

• State-of-the-art laboratory facilities

– Top-notch network simulation test bed

– In-house Emulab mirrors top academic equivalents

• Ongoing industry contacts

– Network operators

– Equipment vendors

– perfSONAR network measurement community

August 28, 2014 Early Warning of Network Catastrophes 20
Research Team Qualifications

 Kevin Mills (PhD senior computer scientist)—experience developing realistic 

Internet models to study congestion behavior, and successfully leading this

team in previous, related research (http://www.nist.gov/itl/antd/emergent_behavior.cfm)

 Chris Dabrowski (MS computer scientist)—experience developing methods 

to predict causes and patterns of performance degradation in networks

 Jim Filliben (PhD mathematical statistician)—leading expert in advanced 

statistical modeling and analysis techniques, including five years focused on 

network congestion 

 Fern Hunt (PhD mathematician)—experience in mathematical modeling of 

dynamical systems, complex systems, and models of network failures

 Bert Rust (PhD mathematician)—world-class expert in developing 

mathematical models to characterize time series data, ranging from climate 

change measurements to traffic measurements from the Internet 

August 28, 2014 Early Warning of Network Catastrophes 21
Proposed Schedule

August 28, 2014 Early Warning of Network Catastrophes 22

Year 2015 2016 2017 2018 2019

Phase ID Task Qtr 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3

Validation

1 Modeling

2 Characterization

3 Emulation

Measurement

Methods

4 Design

5 Development

6 Testing

Technology

Transfer

7 Software Release

8 Evaluation

Go – No Go

Go – No Go
Total Resource Requirements

August 28, 2014 Early Warning of Network Catastrophes 23

*80% of labor spending for one new FTE, three new Post-Docs, and one new Guest Researcher

Budget Resources ($K)

STRS Invested Equipment (IE)

Div/Grp FY15 FY16 FY17 FY18 FY19 FY15 FY16 FY17 FY18 FY19

772/04 $810 $810 $810 $810 $405 $425 $375

776/04 $230 $230 $230 $230 $115

771/01 $172 $172 $172 $172 $136

Totals $1,212* $1,212 $1,212 $1,212 $656 $425 $375

	
Staffing & IE Budgeting Details

August 28, 2014 Early Warning of Network Catastrophes 24

Invested Equipment (IE) Planned Purchases

Equipment Description & Estimated Cost

FY2015 – $375K – 50 additional Emulab nodes + software licenses

– $50K – 6 additional network switches + cables

FY2016 – $375K – 50 additional Emulab nodes + software licenses

	
Questions?

Discussion?

August 28, 2014 Early Warning of Network Catastrophes 25