How to model a TCP/IP network 

usi l 20 t ing only 20 parame

ters

K. Mills 

(NIST), E. Schwartz 

(CMU

) & J. Yuan 

(Tsi

visual hash of MesoNet source code from http://www.wordle.net/

( ), ( ) (

Winter Simulation Conference – Dec 8, 201
Outline

• Goal – Problem – Solution• Scale Reduction: Theory and Practice• Overview of the 20 MesoNet Parameter

• Parameter Explanations in 5 Categories

– Network (4 parameters) (4 parameters)– Sources & Receivers (4 parameters)– User Behavior (6 parameters)– Protocols (p ) 3arameters)– Simulation & Measurement Control (3 paramete

• Describe Sample Use of Model• Discuss Simulation Resource Requirem

Discuss Simulation Resource Requirem

• Conclusions
Goal – Problem – Solution

• Goal

– compare proposed Internet congestion 

algorithms under a wide range of controlled, 

repeatable conditions

• Problem

– real network not controllable and 

repeatabl b d ble; test b

e

d

s currently too ll sma ; mos

network simulation models have large search sand require infeasible memory and processing resources f l f k 

for large, fast networ

ks; more trac

fluid-flow simulators are currently inaccurate

• Solution

– design a reduced scale network sim

model (MesoNet) that is easy to configure and 

tractable to compute
Simulating large, fast networks across many conditions and cong

algorithms requires scale reduction in both model parameters 

Scale Reduction: Theory & Practice

y

1, ...,

yz

= f(

x1|[1,...,

l] ...,

xp|[1,...,

l]

)

ResponseState‐Space Stimulus State‐Space

(232)1000 O(109633) [ 1080 = atomsin visible universe]

Multidimensional Response Parameter 

Reduction (2 )

Discardparameters not germane to study – reduce by 944 parameters

O(10 ) [ ]

(232)56 O(10539)

20

Group related remainingparameters– reduce by 36 param

22 Responses

CorrelationAnalysis &Clusterin

g

PrincipalComponentsAnalysis

Use experimentdesign the

bi i 

220

(232)20 O(10192)

O(10

6)

Model Reduction

Select only 2 valuesfor each parameter

Level Reduction

g

7 Responses 4 Responses

Domain

Analysis

parameter combinationsto 

Use sensitto identity 

significant

220‐12 Experiment 2

Design Theory

Sensitivity

7 Responses Analysis

Talk given Dec. 6 @ 2:00 PM

Talk 

given Dec. 6 @ 1:30 PM

Use experimentdesign theo

parameter combinationsto 3

g
Model Reduction for MesoNet Simula

• Need to identify and retain only parameters germane 

topic being studied (we identified 56 such parameter

• Need to examine retained parameters to identify gro

related parameters defining aspects of same macroparameter (after grouping we identified 20 paramete

relevant to a study of Internet congestion control) 

For a full explanation of our reasoning and our entstudyp p re ort see NIST Special Publication 500-28Study of Proposed Internet Congestion Control MAvailable online at http://www.nist.gov/itl/antd/Congestion_Cont
MesoNet – a TCP/IP network mode

using only 20 parameterusing only 20 parameter

Category Identifier Name Network

X1 Topology 

Network X2 Propagation DelayConfiguration 

X2 Propagation DelayX3 Network Speed X4 Buffer Provisioning 

Sources & 

X5 Number of Sources & Receivers X6 Distribution of Sources 

Receivers X7 Distribution of Receivers 

X8 Source & Receiver Interface Speeds X9 Think Time 

X10 Patience X11 Web Object Size for Browsing User 

Behavior 

X11 Web Object Size for BrowsingX12 Proportion & Size of Larger Fi

Downloads 

X13 Selected Spatiotemporal Congestion X14 Long-lived Flows 

Protocols 

X15 Congestion Control Algorithms X16 Initial Congestion Window Size X17 Initial Slow Start Threshold 

Simulation & M t

X18 Measurement Interval Size 

Measurement X19 Si l i D iControl 

X19 Simulation Duration X20 Startup Pattern 
Parameter X1 is the Topology = 

Routers + Links + Routes + Pro

pg 

a

gation D

A K

A1

A1b

A1c

A1a

A2a A2b A2c

C1

C1b

C1c

C1a H1c H1b

H1a H1d

H1e

H1f

K1

K2

K0a

K1a

K1b

K1c K1d

K2a K2b

K2c

K2d

J1b J1c

I2

I2a

I1

I I0a

I1a

I1b I1c I1d

I2g

I2f

I2e

I2d I2b I2c

B2d

A2

C

J

K

L

C1

C2

C2b

C2c

C2a

H2bH2c

H2aH H1 1f

H2f

H2e

H2d

L2

L1

L1a L1b

L1c

L1d

L2L2

L0a

L0b

J1

J2

J1a J1b J1c J1d

J1e

J1f

J2a

J2b

J2c

J2d

J2e J2f

B2

B2a

B2bB2c B2d B2e

B2f

B2g

H

H2

D

M

B

L

N

L2 L2

L2

L2d N1a

N1b

N1c

N1d

N1

N1f N2

M2b

M2c

M2d M2e M2f

M2

M2g

M1a M2a

M1b M1

M1c

M1dM1e M1f M1g

F2a

F1

F1a

F1b F1c F1d

F2b

D2

D2a

D2g

D2f

D2d D2b D2c

B0a D2e

B1a B1

B1b

B1c B1d

N1

E

G

F

O

E1

E1b

E1a

G1a

N1f

N2a

N2b

N2c N2d N2e

N2f

M1f g

O0a

O1a

O1b

O1c

O1c

O1

O2a

O2

O2b O2c O2d

O2e

O2f

O2g

F2

F2g F2f

F2d

F2c

F0a

F2e

D1a D1

D1b

D1c D1d

D0a

E2

P E1b E1c

E2b E2a E2c

G1bG1c

G1e

G1d

G2a G2b G2c

G2e

G1f G2d

G2f

P1 P2

P1a

P1b

P1c

P1d

P2a

P2b P2c P2d

P2e

P2f

P2g G1 G2

3 Router Tiers: Backbone 3 Router Tiers: Backbone

– Point of Presence (PoP) Point of Presence (PoP)

– Acc

3 Access Router Classes: Typical

– Fast

– Directly Connec

1 ingress/egress path from access routers to backbone rou
Topology Link Characteristics and S

Pro

p

a

gation Dela

y with Paramete

A

C

D

E

G

F

J

K

M

B

L

N

O

A1

A1b

A1c

A1a

A2a A2b A2c

C1

C1b

C1c

C1a

C2

C2b

C2c

C2a

H2bH2c

H2a

H1

H1c H1b

H1a

E1 E1a

H1d

H1eH1f

H2f

H2e

H2d

G1a

K1

K2

K0a

K1a

K1b

K1c K1d

K2a K2b

K2c

K2d

L2

L1

L1a L1b

L1c

L1d

L2aL2b

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

M1b M1

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

B1a B1

B1b

B1c B1d

B2

B2a

B2bB2c B2d B2e

B2f

B2g

H

E2

H2

A2

N1

E1b

E1c P pg y

E2b E2a E2c

G1bG1c

G1e

G1d

G2a G2b G2c

G2e

G1f G2d

G2f

P1 P2

P1a

P1b

P1c

P1d

P2a

P2b P2c P2d

P2e

P2f

P2g G1 G2

Link# End

points Cost Metric Pro

p. Dela

y (ms) X2 = 0.5 X2 = 2

• Packets incur propaga

delay when transiting 

p p y( )

1 A-B 50 21 10.5 42 2 B-C 10 25 12.5 50 3 B-D 50 8 4 16 4 B-L 223 75 37.5 150 5 C-H 100 12 6 24 6 D-E 10 10 5 20 7

D

F 108 33 16 5 66

• Cost metric used to c

routes from source b

router to destination 

7

D-F 108 33 16.5 66

8 E-G 100 33 16.5 66 9 

F-G 10 7 3.5 14

10 F-H 50 12 6 24 11 F-I 55 22 11 4412 G-O 104 23 11.5 46 13

G-P 110 19 9 5 38 router to destination 

router

13

G

P 110 19

9.5 38

14 I-H 10 14 7 28 15 I-J 50 8 4 16 16 I-K 147 22 11 4417 J-L 60 20 10 40 18 K-L 50 7 3.5 1419 L-M 50 12 6 24 20 L-N 39 6 3 1221 L-O 10 14 7 28 22 M-O 10 6 3 12 23 N-O 10 8 4 16 24 O-P 10 14 7 28 
Defined Speed Relationships among Router 

used to used to Scale Router Speeds with Parame

Scale Router Speeds with Parame

(MesoNet simplification – only routers have speeds

Parameter Value Speed Relationships Speed Scas1 X3 Router Class Speed X3 = 800 s

2

4 Backbone Backbone

s

1

x BBspeedup BBspeedup 1600 

s3 10 PoP 

s1/ s2 400 

BBspeedup 2 N-Class 

s1/ s2/ s3 40 

Bfast 2 

F-Class 

s1/ s2/ s3 

x Bfast 80 

Bdirect Bdirect 10

D-Class

s1/

s2/

s

3

x Bdirect Bdirect 400 

P t X4 arame

ter X4 sel t th lec

t

s th

e B ff P i i i B

uffer 

Provisioni

Algorithm, which generally interacts with n

speed and propagation delay
Three Parameters Determine Number (X5

Distribution of Sources ( Distribution of Sources

(X6) and Receiver

) and Receiver

Combination of parameters X5, X6, and X7 determine distrfl i th t l d i th i l ti flows i

n th

e topology during th

e

simulation

Sample Computation of Number and Distribution of Sources and Receiver

(given Topology on Slide 7 and base # Sources = 100, X5 = 3, probNs = 0.1, probNsf = 0.6, probN

Class #routers srcs/router #srcs %srcs rcvrs/router #rcvrs %rcvrs Flo

N-class 122 90 10,980 31.6 960 117,120 95.3 NN

FN

F-class 40 540 21,600 62.2 120 4,800 3.9 FF

D

N

D-class 8 270 2,160 6.2 120 960 0.8 

D

F

DD

Parameter X8 defines the probability that sources and recconnect to the topology at 1 Gbps or 100 Mbps
User Behavior Represented via Source

Too Slow (reactive sources only)

Select Think Time

(Exponential Distribution)

Select Think Time

(Exponential Distribution)

Too Lon

g

(reactive sources only)

Select Think Time

(E ti l

Think Time Expired

Select Receiver &

File Size (Pareto Distribution)

Select R

File Size (Pa

(Exponenti

al

Distribution)

Finished

Select Think Time

File Size (Pa

Parameter x9 specifies averageThink Time

Parameter x10 specifies User Pat

(probability source is reactive)

Select Think Time

(Exponential Distribution)

^Note: this simplified diagram omits a flow connection phase that occurs be

and also the potential for the connection phase to fail – after which source 
User Traffic Characterization

Parameter X11 charact

e

riz

e

s Web Objects (on, )

Size of Web Objects

on average size (packets)

 shape of Pareto distribution

Probability of Web Object 

(1 

–

Fp

–

Sp

–

Mp)

charact r z s j ( , )

 shape of Pareto distribution

Larger File Size Multipliers Larger File Probabilities

( p

p

p)

Parameter x12 characterizes Larger Files [(Fx, Fp), (Sx, Sp), (Mx, 

Fx documentsSx software downloadsMx movies

Fp documentsSp software downloadsMp movies

Jumbo File Characteristics

Jx size multi

plier for jumbo files

Parameter X13 characterizes Jumbo Files (Jx, Jon, Joff)

p j

Jon fraction of simulated time after which jumbo file transfers beginJoff fraction of simulated time after which jumbo file transfers end

Parameter X14 characterizes number, location and 

start and stop times for Long-Lived Flows 
Assignment of Three Protocol Paramet

P t 15 arame

ter x15 specifies (prTCP, prHSTCP, prCTCP, 

prSCALABLE, 

prFAST, 

p

Congestion Control Algorithm Identifier Probability of Source ImplemenTransmission Control Protocol (TCP) 1 prTCP High Speed TCP (HSTCP) High Speed TCP (HSTCP)

2 prHSTCP prHSTCP

Compound TCP (CTCP) 3 prTCP Scalable TCP (STCP) 4 prSTCP FAST AQM Scalable TCP (FAST) 5 prFAST Hamilton TCP (HTCP) 6 prHTCP Bi I C ti (BIC Binary 

Increase 

Congestion (BIC) 7

p

rBIC

160180

Parameter x16 specifies 

80

100120140160

cwnd

initial sst linear increase

Parameter x16 specifies 

congestion window (cwn

0

204060

c80

initial cwnd

exponential increase Parameter x17 specifies 

slow start threshold (sst

0

0 10 20 30 40

time
Simulation Measurement & Control

Parameter x18 specifies 

5000 interval size6000

s

200030004000

ending Flows Parameter x19 specifies 

measurement intervals t

0

1000

2000

Se

Parameter x20 specifies 

for sources

0 50 100 150 200 250

Time

Count of Flows in the Sending State Measured every 

M = 200 ms 

for MI = 250 intervals – Simulation Duration (.2 s x 250 =) 50 s

– 0 25 % . of t ti t 0 f sources starting

a t=0, 0 08 % f t ti 0.08 % of sources starting

after an average delay 33 % of think time, 0.17 % of sources starting after an average delay 66 % of think time and remainingsources starting after average delay of think time
Combining MesoNet Parameters with

2-Level Orthogonal Fractional Factorial (OFF) Experi

Global Local

X5

+ X2

X3

+

_

_+

X5

+

X1

X2

X3

+_

_

_

+

X5

+ X2

X3

+_

_

_+

X5

+ X2

X3

+_

_

_+

X7

Exampl

OF

Global Local

X4

X1 +

_

_ + X4

X1 +

_ +

X5

+

+

X5

+

+

X4

X1 +

_ + X4

X1 +

_ +

X5

+

+

X5

+

+

OFF Design 1-FAT Design

X5

X7 

Factor-at

Design for 

X4

+

X1

X2

X3

+

_

_

_

_

+ X4

+

X1

X2

X3

+

_

_

_

_

+ X4

+

X1

X2

X3

+ _

_

_

_

_

+ X4

+

X1

X2

X3

+ _

_

_

_

_

+

X4

X6

Comparing 7 Congestion Control Algorithms with 2-Level design for, 

Parameters requires (29 x 7 =) 3584 runs

At 28 processor hours per run and with 48 available processors, 

runs would require about 2090 hours (87 days)

Adopting a 29-4 OFF experimental design would reduce the resourc

to only to only (3 x7) 2 x7) = 224 runs, wh runs, wh ch could be completed n about ich could be completed in about 130 

Cost: misses 29 - 25 parameter combinations 
Two Sample Experiments using 29-4 Ortho

Fractional Factorial Design

Definition of the 32 Parameter Configurations used to Simulate a Modest Moderate Speed Network in Experiment #1. F E i #2 d l f X3 d # S l i li d b 10 

One Experiment Design – Two Experiments 

Factor-> X2 X3 X4 X5 X7 X9 X11 X12 X15

Condition -- -- -- -- -- -- -- -- --

1 1 800 0.5 3 0.7 5000 100 0.04/0.004/0.0004 0.72 1 1600 0.5 2 0.3 5000 100 0.04/0.004/0.0004 0.3

Values of 11 Fixed Param

For

Experiment #2 re

d values for X3 and # Sources were multipli

ed b

y 10 

a Larger, Faster Network.

3 2 800 0.5 2 0.7 5000 100 0.02/0.002/0.0002 0.34 2 1600 0.5 3 0.3 5000 100 0.02/0.002/0.0002 0.75 1 800 1 2 0.3 5000 100 0.02/0.002/0.0002 0.76 1 1600 1 3 0.7 5000 100 0.02/0.002/0.0002 0.37 2 800 1 3 0.3 5000 100 0.04/0.004/0.0004 0.38 2 1600 1 2 0.7 5000 100 0.04/0.004/0.0004 0.79 1 800 0.5 3 0.3 7500 100 0.02/0.002/0.0002 0.3

10 1 1600 0.5 2 0.7 7500 100 0.02/0.002/0.0002 0.7

11 2 800 0 5 2 0 3 7500 100 0 04/0 004/0 0004 0 7

Parameter Assigned Value 

X1 Abilene Topology (Backbone: 11 routers and 14 links; 22 X6 probNs = 0.1, probNsf = 0.6 X7 probNr = 0.6, probNrf = 0.2 

X10 0 (all users have infinite patience) X13 Jon = 1; Joff = 1; Jx = 1 (no explicit spatiotemporal cong

11 2 800 0.5 2 0.3 7500 100 0.04/0.004/0.0004 0.712 2 1600 0.5 3 0.7 7500 100 0.04/0.004/0.0004 0.3

13 1 800 1 2 0.7 7500 100 0.04/0.004/0.0004 0.314 1 1600 1 3 0.3 7500 100 0.04/0.004/0.0004 0.715 2 800 1 3 0.7 7500 100 0.02/0.002/0.0002 0.716 2 1600 1 2 0.3 7500 100 0.02/0.002/0.0002 0.317 1 800 0.5 2 0.3 5000 150 0.02/0.002/0.0002 0.318 1 1600 0.5 3 0.7 5000 150 0.02/0.002/0.0002 0.7

19 2 800 0.5 3 0.3 5000 150 0.04/0.004/0.0004 0.7

X13 Jon 1; Joff 1; Jx 1 (no explicit spatiotemporal congX14 no long-lived flows X16 initial cwnd = 2 (default Microsoft WindowsTM value) X17 initial sst = 231/2 (arbitrary large value) X18 

M = 200 ms 

X19 MI = 18,000 (x .2 

M =) 3600 s 

19 2 800 0.5 3 0.3 5000 150 0.04/0.004/0.0004 0.7 X20 prON = 0.25, prONsecond = 0.08, prONthird = 0.1720 2 1600 0.5 2 0.7 5000 150 0.04/0.004/0.0004 0.3

21 1 800 1 3 0.7 5000 150 0.04/0.004/0.0004 0.322 1 1600 1 2 0.3 5000 150 0.04/0.004/0.0004 0.723 2 800 1 2 0.7 5000 150 0.02/0.002/0.0002 0.724 2 1600 1 3 0.3 5000 150 0.02/0.002/0.0002 0.325 1 800 0.5 2 0.7 7500 150 0.04/0.004/0.0004 0.726 1 1600 0.5 3 0.3 7500 150 0.04/0.004/0.0004 0.327 2 800 0.5 3 0.7 7500 150 0.02/0.002/0.0002 0.3

X20 prON 0.25, prONsecond 0.08, prONthird 0.17

Each of the 32 parameter comwere run against 7 congestion 

28 2 1600 0.5 2 0.3 7500 150 0.02/0.002/0.0002 0.7

29 1 800 1 3 0.3 7500 150 0.02/0.002/0.0002 0.730 1 1600 1 2 0.7 7500 150 0.02/0.002/0.0002 0.331 2 800 1 2 0.3 7500 150 0.04/0.004/0.0004 0.332 2 1600 1 3 0.7 7500 150 0.04/0.004/0.0004 0.7

– requiring 7 x 32 = 224 simul
Is MesoNet Computationally Tracta

32 bit SLX 64 bit SLX

 Experiment #1 Experiment #2 CPU hours (224 runs) 5,857.18 94,355.28 Avg. CPU hours/Run 26.15 421.23

32-bit SLX 64-bit SLX

Avg. CPU hours/Run 26.15 421.23Min. CPU hours/Run 12.58 203.04 Max. CPU hours/Run 43.97 739.04 Avg. Memory Usage (Mbytes) 196.56 2,392.41 

Required 35 Required 11 processor weeks processor yea

Parallel simulation of configurations reduced t

E i t #1 Sl S ll N t k E i t #2 L 

1 week using

48 processors

31 days usi

48 processo

Parallel simulation of configurations reduced t

Experiment #1 – Slow, Small Network Experiment #2 – Large

Statistic Flows Completed Data Packets Sent Flows Completed DaAvg./Run 11,466,429 3,414,017,482 116,317,093 Min./Run 7,258,056 2,138,998,764 72,944,797 Max./Run 17,390,781 17,390,781 5,048,119,166 5,048,119,166 175,947,632 175,947,632 Total All Runs 2,568,480,122 764,739,915,978 26,055,028,851 7,4
Comparing MesoNet with RossNet* Parallel Network 

(Throughput/Latency Tradeoff)

MesoNet limited to 1 processor per simulation, using sequential SL

Simulation Experiment Event Rat

RossNet can use 2-4 processors per simulation

Simulation Experiment Event RatMesoNet Experiment #1 – 32-bit SLX – 1 processor per simulation 7MesoNet Experiment #2 – 64-bit SLX – 1 processor per simulation 4RossNet Simulation of small topologies – 2 to 4 processors per simulation 2RossNet Simulation of AT&T topology – 2 to 4 processors per simulation 

RossNet speedups from parallel simulation averaged just under 1.when using 4 processorsGiven 48 processors, MesoNet can run 48 simulations in parallel, w

RossNet simulations using 4 processors can run only 12 simulation

RossNet requires a speedup of 4 to equal the throughput of MesoIf sufficient processors exist to run all RossNet simulations in paRossNet might provide superior latency to MesoNet

*Yaun, G., D. Bauer, H. Bhutada, C. Carothers, M. Yukel and S. Kalyanaraman. 2003. Large-Scale Ne

Techniques: Examples of TCP and OSFP Models. In SIGCOM Computer Communications Review, 33
Conclusions

• Defined a concise TCP/IP model using only 20 

parameters

• Showed how the model can be combined with 

orthogonal fraction factorial techniques to deefficient experiments

• Demonstrated how to carefullyp p ex lore a para

space using parallel instances of a sequential s

• Found our model and approach competitive wit

parallel TCP/IP simulator, which required addprocessors to achieve the same throughput
Related Work

• More Parallel Simulators – (throughput/latency tradeoffRiley, G., M. Ammar, F. Fujimoto, A. Park, K. Perumalla and D. Xu. 2004. A Federated Approach tN t k Si l ti I Network Simulation. In ACM T ti M d li d C t Si l ti ACM Transactions on Modeling and Computer Simulation, 14 2 116 14:2, 116-148.

Zeng. X., R. Bagrodia and M. Gerla. 1998. GloMoSim: a Library for Parallel Simulation of Large-sNetworks. In Proceedings of the 12th Workshop on Parallel and Distributed Simulations, 154-16

• Fluid-Flow Simulators – (inaccurate)Towsley, D., V. Misra and W. Gong. 2000. Fluid-based analysis of a network of AQM routers sup

flows with an app g lication to RED. In Proceedings of SIGCOMM, 30:4, 151,160.

Yi, Y. and S. Shakkottai. 2007. FluNet: A hybrid internet simulator for fast queue regimes, In CNetworks: The International Journal of Computer and Telecommunications Networking, 51:18, 4• Hy r ont nuous brid Continuous-Tim /D scr t e/Discrete-E nt S mu ators vent Simulators– (pLee, J., S. Bohacek, J. Hespanha and K. Obraczka. 2007. Modeling Communication Networks witSystems. In IEEE/ACM Transactions on Networking, 15:3, 630-643.