The Influence of Realism on 

Congestion in Network Simulations*

K. Mills 

(joint work with C. Dabrowski)

NIST

December 1, 2015

*For more details see: NIST Technical Note 1901

 http://www.nist.gov/itl/antd/upload/TechNote1901-draft1.pdf
Total talk is 20 slides

• Motivation – 6 slides

• Research Questions and Approach – 2 slides

• Models – 5 slides

• Experiment Design – 1 slide

• Results – 5 slides

• Findings – 1 slide

December 1, 2015 NIST TN 1901 2
Congestion Spreads 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 CONGESTION COLLAPSE

December 1, 2015 NIST TN 1901 3

PACKET-INJECTION RATE

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

Congestion Sporadic 
Spreading Processes often Modeled as 

Percolation

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 signals,

typically attributable to increasing, systemic correlation

December 1, 2015 NIST TN 1901 4
Academics Model Spreading Network 

Congestion as a Percolation Process

Finding that 

Signals Appear 

Near a 

Critical Point

in Abstract 

Network Models

December 1, 2015 NIST TN 1901 5
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

Aggregate Avg. Transit Delay (D*) vs. Network Load (λ) Sampled Avg. Transit Delays (D) for Four Network Loads (λ)

December 1, 2015 NIST TN 1901 6
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

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

allowing network managers to be warned prior to network collapse

December 1, 2015 NIST TN 1901 7
Abstract Models Lack Key Traits of Real Networks

1. Human-engineered, tiered topologies, with propagation

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

Routers &

Links

Computers

Users

Protocols

December 1, 2015 NIST TN 1901 8

DOES LACK OF REALISM MATTER WHEN SIMULATATING NETWORK CONGESTION?
Specific Research Questions

• Does congestion spread in abstract models 

mirror spread in realistic models?

• Are some elements of realism essential to 

capture when modeling network congestion?

• Are some elements unnecessary?

• What measures of congestion can be 

compared, and how, across diverse network 

models?

December 1, 2015 NIST TN 1901 9
Research Approach

Abstract

Model from 

Literature

Realistic

Model from 

Literature

Flexible 

Network 

Simulator 

(FxNS)

Basic Model

Behaviors

Factor Into

Realism Elements 

that can be 

enabled or disabled

Simulate Combinations

of Realism Elements and

Compare Patterns of

Congestion

December 1, 2015 NIST TN 1901 10
Models

• Abstract EGM Model→high abstraction

• Realistic MesoNet Model→high realism

• Flexible FxNS Model→combinations of realism

 from low to high

December 1, 2015 NIST TN 1901 11
The Abstract (EGM) Model

P. Echenique, J. Gomez-Gardenes, and Y. Moreno, “Dynamics of Jamming 

Transitions in Complex Networks”, Europhysics Letters, 71, 325 (2005)

Simulations based on 11,174-node scale-free graph, Pk ~ k

-γ& γ=2.2, taken from a 

2001 snapshot of the Internet Autonomous System (AS) topology collected by the 

Oregon Router Server (image courtesy Sandy Ressler)

γ = -2.2

December 1, 2015 NIST TN 1901 12
Details of the EGM Model

h is a traffic awareness parameter,

whose value 0 ... 1.

where i is the index of a node’s neighbor,

diis minimum #hops to destination via 

neighbor i, and ciis the queue length of i.

Node Buffer Size: ∞ for EGM, all packets buffered, no packets dropped

Injection Rate: p packets injected at random nodes (uniform) at each time step

Destination Node: chose randomly (uniform) for each packet

Forwarding Rate: 1 packet per node at each time step

Routing Algorithm: If node is destination, remove packet; Otherwise select 

 next-hop as neighboring node i with minimum di

System Response: proportion ρ of injected packets queued in the network

Computing di Measuring ρ

h = 1 is shortest path (in hops)

A = aggregate number of packets

t = time

t = measurement interval size

p = packet inject rate

NIST TN 1901 13
Comparative Simulation Results

0

0.2

0.4

0.6

0.8

1

0 5 10 15 20 25 30

p

ρ 

h=1

h=0.85

p

ρ

EGM Simulations

FxNS Simulations with

All Realism Elements Disabled 

December 1, 2015 NIST TN 1901 14
The Realistic (MesoNet) Model

K. Mills, E. Schwartz, and J. Yuan, "How to Model a TCP/IP Network using only 20 

Parameters", WSC 2010, Dec. 5-8, Baltimore, MD.

Category ID Name

Specific 

FxNS

Network

x1 topology

18%

NC

x2 propagation delay

14%

DE

x3 network speed VS

x4 buffer provisioning PD

Sources & 

Sinks

x5 number sources/sinks

x6 source distribution SR

x7 sink distribution

x8 source/sink speed VS

Users

x9 think time p

x10 patience n/a

x11 web object file sizes FL

x12 larger file sizes

x13 localized congestion n/a

x14 long-lived flows

Congestion 

Control

x15 control algorithm

x16 initial cwnd TCP

x17 Initial sst

Simulation 

Control

x18 measurement interval fixed

x19 simulation duration fixed

x20 startup pattern p

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

Comparisons of MesoNet Simulations vs. FxNS Simulations (all realism elements enabled) 

for eight MesoNet responses are available in NIST TN 1901 – Appendix A

December 1, 2015 NIST TN 1901 15

Figure 2.
FxNS Combinations

Dependencies among Realism Elements

Seq Cmb TCP FL SR DE VS NC PD

1 c0 0 0 0 0 0 0 0

2 c1 0 0 0 0 0 0 1

3 c2 0 0 0 0 0 1 0

. . .

32 c123 1 1 1 1 0 1 1

33 c126 1 1 1 1 1 1 0

34 c127 1 1 1 1 1 1 1

34 Valid FxNS Combinations

December 1, 2015 NIST TN 1901 16
Experiment Design

Enabled Disabled

PD buffers = 250×router speed buffers = ∞

NC

3-tier 218-node topology 

as in Fig. 2 with routers 

labeled as core, PoP, Dclass, F-class or N-class

flat 218-node 

topology as in 

Fig. 2 but with 

routers unlabeled

VS

core 80 p/ts; PoP 10 p/ts; 

D-class 10 p/ts; F-class 2 

p/ts; N-class 1 p/ts; fast 

source/sink 2 p/ts; normal 

source/sink 0.2 p/ts 

all routers and 

sources/sinks 9 

p/ts

DE core links have 

propagation delays 

no propagation 

delays

SR

51,588 sources & 206,352 

sinks deployed uniformly 

below access routers

no sources or 

sinks deployed

FL

transfers are packet 

streams: sized randomly 

from Pareto distribution 

(mean 350, shape 1.5) -

streams set up with TCP 

connection procedures

transfers are 

individual packets

TCP

packet transmission 

regulated by TCP 

congestion-control 

including slow-start (initial 

cwnd = 2 sst = 230/2) and 

congestion avoidance

packet 

transmissions not 

regulated by 

congestioncontrol

 FIXED PARAMETERS

• 218-Router Topology (Fig. 2)

• Routing (SPF propagation delay)

• Duration (200,000 ts per p)

 VARIABLE PARAMETERS

• Packet-Injection Rate p (up to 2500)

• FxNS Combination

 RESPONSES

• Congestion Spread χ=|Gχ|/|GN| 

• Connectivity Breakdown α=|Gα|/|GN|

• Proportion of Packets Delivered π

• Scaled (0..1) Latency of Delivered Packets δ

December 1, 2015 NIST TN 1901 17

Only concepts in common among all 34

combinations: graph and packet
Results1,2

[1] 136 xy-plots (34 FxNS combinations × 4 responses) are available at:

 http://tinyurl.com/poylful

[2] Related FxNS simulation data can be explored interactively using a 

 multidimensional visualization created by Phillip Gough of CSIRO:

 http://tinyurl.com/payglq6
Results I – Abstract (C0) vs. Realistic (C127)

December 1, 2015 NIST TN 1901 19

Plots for all responses and all 34 combinations available: http://tinyurl.com/poylful

C0

C127

C0

C127

C127

C0 C127

C0
Results II – Congestion Spread χ All Combinations 

December 1, 2015 NIST TN 1901 20
Results III – Connectivity Breakdown α All Combinations 

December 1, 2015 NIST TN 1901 21
Results IV – Packet Delivery π All Combinations 

December 1, 2015 NIST TN 1901 22
Results V – Scaled Packet Latency δ All Combinations 

December 1, 2015 NIST TN 1901 23
Findings

• Congestion spreads differently in abstract and realistic 

models

• Hierarchical Router Speeds and TCP very important to 

model

• Packet dropping important to model for accurate 

packet latencies

• Propagation delay not important to model in a 

continental US network, but would be important to 

model in topologies where propagation delays exceed 

queuing delays

• Congestion spread, connectivity breakdown and the 

effectiveness and efficiency of packet delivery can be 

measured using only two concepts: graphs and packets

December 1, 2015 NIST TN 1901 24