The Need for Realism when Simulating 

Network Congestion*

Kevin Mills and Chris Dabrowski

National Institute of Standards & Technology

Communications & Networking Symposium

April 3-6, 2016

*For more details see: NIST Technical Note 1905

http://dx.doi.org/10.6028/NIST.TN.1905
Total talk is ≈ 16 slides

• Motivation – 2 slides

• Research Questions and Approach – 2 slides

• Models – 5 slides

• Experiment Design – 1 slide

• Results – 5 slides

• Findings – 1 slide

April 3-6, 2016 Communications & Networking Symposium 2
Academics Model Spreading Network 

Congestion as a Percolation Process

All Find that 

Signals Appear 

Near a 

Critical Point

in Abstract 

Network Models

April 3-6, 2016 Communications & Networking Symposium 3
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

4

DOES LACK OF REALISM MATTER WHEN SIMULATATING NETWORK CONGESTION?

April 3-6, 2016 Communications & Networking Symposium
Specific Research Questions

1. Does congestion spread in abstract models 

mirror spread in realistic models?

2. Are some elements of realism essential to 

capture when modeling network congestion?

3. Are some elements unnecessary?

4. What measures of congestion can be 

compared, and how, across diverse network 

models?

April 3-6, 2016 Communications & Networking Symposium 5
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

April 3-6, 2016 Communications & Networking Symposium 6
Models

• Abstract EGM Model→high abstraction

• Realistic MesoNet Model→high realism

• Flexible FxNS Model→combinations of realism

from low to high

April 3-6, 2016 Communications & Networking Symposium 7
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

April 3-6, 2016 Communications & Networking Symposium 8
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

τ = measurement interval size

p = packet inject rate

April 3-6, 2016 Communications & Networking Symposium 9
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 

April 3-6, 2016 Communications & Networking Symposium 10
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 1905 – Appendix A

11

Figure 2.

April 3-6, 2016 Communications & Networking Symposium
FxNS Combinations

7 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

12

7 Realism Elements

April 3-6, 2016 Communications & Networking Symposium
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 δ

13

Only concepts in common among all 34

combinations: graph and packet

April 3-6, 2016 Communications & Networking Symposium
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

April 3-6, 2016 Communications & Networking Symposium 14
Results I – Abstract (C0) vs. Realistic (C127)

15

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

C0

C127

C0

C127

C127

C0 C127

C0

April 3-6, 2016 Communications & Networking Symposium
Results II – Congestion Spread χ All Combinations 

April 3-6, 2016 Communications & Networking Symposium 16
Results III – Connectivity Breakdown α All Combinations 

April 3-6, 2016 Communications & Networking Symposium 17
Results IV – Packet Delivery π All Combinations 

April 3-6, 2016 Communications & Networking Symposium 18
Results V – Scaled Packet Latency δ All Combinations 

April 3-6, 2016 Communications & Networking Symposium 19
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

April 3-6, 2016 Communications & Networking Symposium 20
21

For more of our research see:

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

April 3-6, 2016 Communications & Networking Symposium