Study of Proposed Internet Congestion C

Study of Proposed Internet Congestion C

Algorithms

Kevin L. Mills, NIST

(joint work with D. Y. Cho, J. Filliben, D. Genin and E

January 29, 2010

image generated with http://www.wordle.net/
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Outline

3⁄4 Motivation for the study3⁄4 General approach General approach3⁄4 Model and experiment reduction techniques3⁄4 Overview of experiments Overview of experiments3⁄4 Design for exp. #1 and analysis techniques3⁄4 Design for exp. #2 and additional analysis tech3⁄4 Findings

 Utility and safety Characteristics of individual congestion control algo

Characteristics of individual congestion control algo

 Recommendations

3⁄4 Future Work

January 29, 2010Innovations in Measurement Science

2
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Wh h i lt t I t t ti t 

Standard TCP - 1 Gbps Path Between Chicago and Dublin

Why are researc

hers proposing alternate Internet congestion contro

Exam

ple Pro

pos

Window (cwnd) Avg. Throughput 218 Mbps (20% of capacity)

p p

BICCompound TCPCUBIC (not included in FAST

Congestion W HSTCP H-TCP Scalable TCP

Time (s)

Figure 1 from Li et al. 2007. Experimental Evaluation of TCP Protocolsfor Hi

gh-S

peed Networks. Transactions on Networkin

g. 15:5, 1109-1122.

Some common themes among proposals: 

(1) alterations only to congestion avoidance (not initial slow start)(2) relative to TCP: most reduce cwnd less on packet loss and all increase cwn

(3) most have mode switch between TCP and alternate behavior (FAST i t b

January 29, 2010Innovations in Measurement Science

3

(3) most have mode switch between TCP and alternate behavior (FAST is a notab
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

H h l ti d ti t l l How are researc

hers evaluating propose

d congestion control alg

Analytical models of single long-lived flows

Blanc, A., Avrachenkov, K. and Collange, D. 2009. Comparing some high speed TCP versions under bernoulli lossof the International Workshop on Protocols for Future, Large-Scale and Diverse Network Transports (PFLDNet 200Simulation studies in small topologiesJackson, T. and Smith, P. 2008. Building a Network Simulation Model of the TeraGrid Network. In Proceedings of Shimonishisi, H., Sanadidi, M. and Murase, T. 2007.“Assessing Interactions among Legacy and High-Speed TCP PProceedings of the 5th International Workshop on Protocols for Fast Long-Distance Networks.Empirical evaluations in small topologiesLi et al. 2007. Ex

p g erimental Evaluation of TCP Protocols for Hi

gh-S

peed Networks. Transactions on Networkin

g. 15

Lee, G., Lachlan, A., Tang, A. and Low, S. 2007. WAN-in-Lab: Motivation, Deployment and Experiments. In Procee

International Workshop on Protocols for Fast Long-Distance Networks.

January 29, 2010Innovations in Measurement Science

4
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

O t d i h h i l t l i d id Our stu

dy is muc

h more compre

hensive: larger topologies an

d wide-ran

Develop MesoNet: 

Rd d Add Six Congestion Design & Conduct

Today’s Seminar

R

e

duce

d

Parameter DES 

for TCP/IP Networks

Add Six Congestion

Control Algorithms

to MesoNet

Design

& Conduct

Simulation

Experiments

Verify Simulated

Conduct Congestion Control Analyze Data & Algorithms

Against Empirical

Results

Sensitivity Analyses

of MesoNet

Analyze Data

&

Formulate Findings

Topologies with up to 278,000 sources; backbone speeds up to 384 Gbps; loss rates between 10-9 

simulated durations of 25 – 60 mins; traffic including Web browsing and software and movie downlolong-lived flows; temporary spatiotemporal congestion and recovery; algorithms homogeneous and alternates together with standard TCP; buffer sizes include RTT

x

C and RTT

x

C/sqr(

n); propagatio

from 6 to 200 ms; initial slow start threshold from 43 to 231/2 

January 29, 2010Innovations in Measurement Science

5
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Simulating large fast networks across many conditions and conges

y1, ...,

y

m

= f(

x1|[1,

...,k]

, ...,

x

n|[1,

...,k] y ) 1, ...,

y

m

= f(

x1|[1,

...,k]

, ...,

x

n|[1,

...,k] ) ( )

y1, ...,

y

m

= f(

x1|[1,

...,k]

, ...,

x

n|[1,

...,k] y ) 1, ...,

y

m

= f(

x1|[1,

...,k]

, ...,

x

n|[1,

...,k] ) ( )

Simulating large, fast networks across many conditions and conges

algorithms requires search-space reduction

1 m 1|[1,

...,k] n|[1,

...,k]

Response State‐Space Stimulus State‐Space

1 m 1|[1,

...,k] n|[1,

...,k]

Response State‐Space Stimulus State‐Space

k

n Model Reduction Model Reduction (232)1000 O(109633) [ 1080 = at

(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at

(a) 1 m 1|[1,

...,k] n|[1,

...,k]

Response State‐Space Stimulus State‐Space

1 m 1|[1,

...,k] n|[1,

...,k]

Response State‐Space Stimulus State‐Space

k

n Model Reduction Model Reduction (232)1000 O(109633) [ 1080 = at

(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at(232)1000 O(109633) [ 1080 = at

(a)

k(n‐r1)

k(n‐r1‐r2)

model

restriction

factor

clustering

SCIENTIFIC

DOMAIN

EXPERTISE

k(n‐r1)

k(n‐r1‐r2)

model

restriction

factor

clustering

k(n‐r1)

k(n‐r1‐r2)

model

restriction

factor

clustering

SCIENTIFIC

DOMAIN

EXPERTISE

k(n‐r1)

k(n‐r1‐r2)

model

restriction

factor

clustering

SCIENTIFIC

DOMAIN

EXPERTISE

k(n‐r1)

k(n‐r1‐r2)

model

restriction

factor

clustering

k(n‐r1)

k(n‐r1‐r2)

model

restriction

factor

clustering

SCIENTIFIC

DOMAIN

EXPERTISE

k(n‐r1)

k(n‐r1‐r2)

model

restriction

factor

clustering

SCIENTIFIC

DOMAIN

EXPERTISE

k(n‐r1)

k(n‐r1‐r2)

model

restriction

factor

clustering

k(n‐r1)

k(n‐r1‐r2)

model

restriction

factor

clustering

SCIENTIFIC

DOMAIN

EXPERTISE

r1 = 944

(232)56 O(10539

(232)20 r2 = 36 

r1 = 944

(232)56 O(10539

(232)20 r2 = 36 

r1 = 936

(232)64 O(10616

(232)20 r2 = 44 

r1 = 944

(232)56 O(10539

(232)20 r2 = 36 

r1 = 944

(232)56 O(10539

(232)20 r2 = 36 

r1 = 936

(232)64 O(10616

(232)20 r2 = 44 

r1 = 944

(232)56 O(10539

(232)20 r2 = 36 

r1 = 944

(232)56 O(10539

(232)20 r2 = 36 

r1 = 944

(232)56 O(10539

(232)20 r2 = 36 

r1 = 936

(232)64 O(10616

(232)20 r2 = 44 

r1 = 944

(232)56 O(10539

(232)20 r2 = 36 

r1 = 936

(232)64 O(10616

(232)20 r2 = 44 

k(n‐r1)

k(n‐r1‐r2)

model

restriction

factor

clustering

SCIENTIFIC

DOMAIN

EXPERTISE

k(n‐r1)

k(n‐r1‐r2)

model

restriction

factor

clustering

k(n‐r1)

k(n‐r1‐r2)

model

restriction

factor

clustering

SCIENTIFIC

DOMAIN

EXPERTISE

k(n‐r1)

k(n‐r1‐r2)

model

restriction

factor

clustering

SCIENTIFIC

DOMAIN

EXPERTISE

k(n‐r1)

k(n‐r1‐r2)

model

restriction

factor

clustering

k(n‐r1)

k(n‐r1‐r2)

model

restriction

factor

clustering

SCIENTIFIC

DOMAIN

EXPERTISE

k(n‐r1)

k(n‐r1‐r2)

model

restriction

factor

clustering

SCIENTIFIC

DOMAIN

EXPERTISE

k(n‐r1)

k(n‐r1‐r2)

model

restriction

factor

clustering

k(n‐r1)

k(n‐r1‐r2)

model

restriction

factor

clustering

SCIENTIFIC

DOMAIN

EXPERTISE

r1 = 944

(232)56 O(10539

(232)20 r2 = 36 

r1 = 944

(232)56 O(10539

(232)20 r2 = 36 

r1 = 936

(232)64 O(10616

(232)20 r2 = 44 

r1 = 944

(232)56 O(10539

(232)20 r2 = 36 

r1 = 944

(232)56 O(10539

(232)20 r2 = 36 

r1 = 936

(232)64 O(10616

(232)20 r2 = 44 

r1 = 944

(232)56 O(10539

(232)20 r2 = 36 

r1 = 944

(232)56 O(10539

(232)20 r2 = 36 

r1 = 944

(232)56 O(10539

(232)20 r2 = 36 

r1 = 936

(232)64 O(10616

(232)20 r2 = 44 

r1 = 944

(232)56 O(10539

(232)20 r2 = 36 

r1 = 936

(232)64 O(10616

(232)20 r2 = 44 

2(n‐r1‐r2)

2(n‐r1‐r2‐r3)

2‐level

experiment

design

OFF (orthogonal fractional factorial)

experiment design

STATISTICAL

EXPERIMENT

DESIGN

EXPERTISE

2(n‐r1‐r2)

2(n‐r1‐r2‐r3)

2‐level

experiment

design

OFF (orthogonal fractional factorial)

experiment design

2(n‐r1‐r2)

2(n‐r1‐r2‐r3)

2‐level

experiment

design

OFF (orthogonal fractional factorial)

experiment design

STATISTICAL

EXPERIMENT

DESIGN

EXPERTISE

2(n‐r1‐r2)

2(n‐r1‐r2‐r3)

2‐level

experiment

design

OFF (orthogonal fractional factorial)

experiment design

STATISTICAL

EXPERIMENT

DESIGN

EXPERTISE

2(n‐r1‐r2)

2(n‐r1‐r2‐r3)

2‐level

experiment

design

OFF (orthogonal fractional factorial)

experiment design

2(n‐r1‐r2)

2(n‐r1‐r2‐r3)

2‐level

experiment

design

OFF (orthogonal fractional factorial)

experiment design

STATISTICAL

EXPERIMENT

DESIGN

EXPERTISE

2(n‐r1‐r2)

2(n‐r1‐r2‐r3)

2‐level

experiment

design

OFF (orthogonal fractional factorial)

experiment design

STATISTICAL

EXPERIMENT

DESIGN

EXPERTISE

2(n‐r1‐r2)

2(n‐r1‐r2‐r3)

2‐level

experiment

design

OFF (orthogonal fractional factorial)

experiment design

2(n‐r1‐r2)

2(n‐r1‐r2‐r3)

2‐level

experiment

design

OFF (orthogonal fractional factorial)

experiment design

STATISTICAL

EXPERIMENT

DESIGN

EXPERTISE

2

k = 2 

DomainAnalyst

Statistician

2

k = 2 

2

k = 2 

DomainAnalyst

Statistician

Experiment 

Reduction

2

k = 2 

DomainAnalyst

Statistician

2

k = 2 

2

k = 2 

DomainAnalyst

Statistician

2

k = 2 

2

k = 2 

DomainAnalyst

Statistician

2

k = 2 

2

k = 2 

DomainAnalyst

Statistician

2

k = 2 

2

k = 2 

DomainAnalyst

Statistician

Experiment 

Reduction

2(n‐r1‐r2)

2(n‐r1‐r2‐r3)

2‐level

experiment

design

OFF (orthogonal fractional factorial)

experiment design

STATISTICAL

EXPERIMENT

DESIGN

EXPERTISE

2(n‐r1‐r2)

2(n‐r1‐r2‐r3)

2‐level

experiment

design

OFF (orthogonal fractional factorial)

experiment design

2(n‐r1‐r2)

2(n‐r1‐r2‐r3)

2‐level

experiment

design

OFF (orthogonal fractional factorial)

experiment design

STATISTICAL

EXPERIMENT

DESIGN

EXPERTISE

2(n‐r1‐r2)

2(n‐r1‐r2‐r3)

2‐level

experiment

design

OFF (orthogonal fractional factorial)

experiment design

STATISTICAL

EXPERIMENT

DESIGN

EXPERTISE

2(n‐r1‐r2)

2(n‐r1‐r2‐r3)

2‐level

experiment

design

OFF (orthogonal fractional factorial)

experiment design

2(n‐r1‐r2)

2(n‐r1‐r2‐r3)

2‐level

experiment

design

OFF (orthogonal fractional factorial)

experiment design

STATISTICAL

EXPERIMENT

DESIGN

EXPERTISE

2(n‐r1‐r2)

2(n‐r1‐r2‐r3)

2‐level

experiment

design

OFF (orthogonal fractional factorial)

experiment design

STATISTICAL

EXPERIMENT

DESIGN

EXPERTISE

2(n‐r1‐r2)

2(n‐r1‐r2‐r3)

2‐level

experiment

design

OFF (orthogonal fractional factorial)

experiment design

2(n‐r1‐r2)

2(n‐r1‐r2‐r3)

2‐level

experiment

design

OFF (orthogonal fractional factorial)

experiment design

STATISTICAL

EXPERIMENT

DESIGN

EXPERTISE

2

k = 2 

DomainAnalyst

Statistician

2

k = 2 

2

k = 2 

DomainAnalyst

Statistician

Experiment 

Reduction

2

k = 2 

DomainAnalyst

Statistician

2

k = 2 

2

k = 2 

DomainAnalyst

Statistician

2

k = 2 

2

k = 2 

DomainAnalyst

Statistician

2

k = 2 

2

k = 2 

DomainAnalyst

Statistician

2

k = 2 

2

k = 2 

DomainAnalyst

Statistician

Experiment 

Reduction

Experiment Reduction

(b) Theory of Search-space Reduction (c) Search-space Redu

Experiment Reduction

(b) Theory of Search-space Reduction (c) Search-space Redu

January 29, 2010Innovations in Measurement Science

6
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

MesoNet – a 20-parameter TCP/IP Network Model

Model Redu

Parameter Value Speed Relationships 

Cate

gor

y Identifier Name

NetworkConfiguration

X1 TopologyX2 Propagation DelayX3 Network Speed

Parameter Value Speed Relationships s1 X3 Router Class Speed s2 4 Backbone s1 x BBspeedup s3 10 PoP s1/ s2 BBspeedup 2 N-Class s1/ s2/ s3 Bfast 2 F-Class s1/ s2/ s3 x BfasBdirect 10 

D-Class s1/ s2/ s3 x Bdi

X4 Buffer Provisionin

g

Sources & Receivers

X5 Number of Sources & ReceiversX6 Distribution of SourcesX7 Distribution of Receivers

X8 Source & Receiver Interface Speeds

User

X9 Think Time

X10 PatienceX11 Web Object Size for Browsing

Behavior X12 Proportion & Sizes of Lar

ger File

Downloads

X13 Selected Spatiotemporal CongestionX14 Long-lived Flows

X15 Congestion Control Algorithms 

Class #routers srcs/router #srcs %src rcvrs/route Class #routers srcs/router #srcs %src rcvrs/route 

Protocols

X15 Congestion Control AlgorithmsX16 Initial Congestion Window SizeX17 Initial Slow Start Threshold

Simulation &

Measurement

Ctl

X18 Measurement Interval SizeX19 Simulation Duration 

D-class 8 270 2,160 6.2 120 

F-class 40 540 21,600 62.2 120 

N-class 122 90 10,980 31.6 960 1

s r 

D-class 8 270 2,160 6.2 120 

F-class 40 540 21,600 62.2 120 

N-class 122 90 10,980 31.6 960 1

s r 

January 29, 2010Innovations in Measurement Science

7

Control X19 Simulation Duration

X20 Startup Pattern
Study of Proposed Internet Congestion Control Algorithms – Mills et al. Experiment 

Ad t 2 op

2-L l O th l F ti l F t i l D i Level O

rthogonal Fractional Factorial Designs

Sample 29-4 design Sample experiment using 9 

1 Sl td it

2

k

p d 

Factor-> x1 x2 x3 x4 x5 x6 x7 x8 x9

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

1 -1 -1 -1 -1 -1 +1 +1 +1 +1

1. S

electe

d appropriate 

n = 

2

k-p

d

2. Select two values for each pa3. Substitute parameter levels in 4. Fix remaining (11) model para

1 1 1 1 1 1 1 1 1 12 +1 -1 -1 -1 -1 +1 -1 -1 -13 -1 +1 -1 -1 -1 -1 +1 -1 -14 +1 +1 -1 -1 -1 -1 -1 +1 +15 -1 -1 +1 -1 -1 -1 -1 +1 -16 +1 -1 +1 -1 -1 -1 +1 -1 +17 -1 +1 +1 -1 -1 +1 -1 -1 +18 +1 +1 +1 -1 -1 +1 +1 +1 -19 -1 -1 -1 +1 -1 -1 -1 -1 +1

10 +1 -1 -1 +1 -1 -1 +1 +1 -1

11 1 +1 1 +1 1 +1 1 +1 1

Probes combinations with balance a

11 -1 +1 -1 +1 -1 +1 -1 +1 -112 +1 +1 -1 +1 -1 +1 +1 -1 +113 -1 -1 +1 +1 -1 +1 +1 -1 -114 +1 -1 +1 +1 -1 +1 -1 +1 +115 -1 +1 +1 +1 -1 -1 +1 +1 +116 +1 +1 +1 +1 -1 -1 -1 -1 -117 -1 -1 -1 -1 +1 -1 -1 -1 -118 +1 -1 -1 -1 +1 -1 +1 +1 +119 -1 +1 -1 -1 +1 +1 -1 +1 +120 +1 +1 -1 -1 +1 +1 +1 -1 -1 - +

16 16

X

All 32: B

21 -1 -1 +1 -1 +1 +1 +1 -1 +122 +1 -1 +1 -1 +1 +1 -1 +1 -123 -1 +1 +1 -1 +1 -1 +1 +1 -124 +1 +1 +1 -1 +1 -1 -1 -1 +125 -1 -1 -1 +1 +1 +1 +1 1 -126 +1 -1 -1 +1 +1 +1 -1 -1 +127 -1 +1 -1 +1 +1 -1 +1 -1 +128 +1 +1 -1 +1 +1 -1 -1 +1 -129 -1 -1 +1 +1 +1 -1 -1 +1 +130 +1 1 +1 +1 +1 1 +1 1 1

Xi

Or

- + -

+

8

8 8

X

All :

Xj

32

2

8

- + -

+

8

8 8

X

All :

Xj

32

2

8

Resolution IV design – no main effects are confounded with two-term interactions

30 +1 -1 +1 +1 +1 -1 +1 -1 -131 -1 +1 +1 +1 +1 +1 -1 -1 -132 +1 +1 +1 +1 +1 +1 +1 +1 +1

Xi

January 29, 2010Innovations in Measurement Science

8

2-Level Designs Support Convenient Data Analysis Techniqu
Study of Proposed Internet Congestion Control Algorithms – Mills et al. Experiment 

Ad t 2 op

2-L l O th l F ti l F t i l D i Level O

rthogonal Fractional Factorial Designs

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.7

Sample 29-4 design instantiated Sample experiment using 9 

1 Sl td it

2

k

p d 

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.33 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.7

6 1 1600 1 3 0.7 5000 100 0.02/0.002/0.0002 0.3

7 2 800 1 3 0.3 5000 100 0.04/0.004/0.0004 0.3

8 2 1600 1 2 0.7 5000 100 0.04/0.004/0.0004 0.7

9 1 800 0.5 3 0.3 7500 100 0.02/0.002/0.0002 0.3

1. S

electe

d appropriate 

n = 

2

k-p

d

2. Select two values for each pa3. Substitute parameter levels in 4. Fix remaining (11) model para

10 1 1600 0.5 2 0.7 7500 100 0.02/0.002/0.0002 0.711 2 800 0.5 2 0.3 7500 100 0.04/0.004/0.0004 0.7

12 2 1600 0.5 3 0.7 7500 100 0.04/0.004/0.0004 0.313 1 800 1 2 0.7 7500 100 0.04/0.004/0.0004 0.3

14 1 1600 1 3 0.3 7500 100 0.04/0.004/0.0004 0.7

15 2 800 1 3 0.7 7500 100 0.02/0.002/0.0002 0.7

16 2 1600 1 2 0.3 7500 100 0.02/0.002/0.0002 0.3

17 1 800 0.5 2 0.3 5000 150 0.02/0.002/0.0002 0.3

18 1 1600 0 5 3 0 7 5000 150 0 02/0 002/0 0002 0 7

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

Parameter Assigned Value

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

Parameter Assigned Value

Fixed values assigned to remainin

18 1 1600 0.5 3 0.7 5000 150 0.02/0.002/0.0002 0.719 2 800 0.5 3 0.3 5000 150 0.04/0.004/0.0004 0.7

20 2 1600 0.5 2 0.7 5000 150 0.04/0.004/0.0004 0.321 1 800 1 3 0.7 5000 150 0.04/0.004/0.0004 0.3

22 1 1600 1 2 0.3 5000 150 0.04/0.004/0.0004 0.7

23 2 800 1 2 0.7 5000 150 0.02/0.002/0.0002 0.7

24 2 1600 1 3 0.3 5000 150 0.02/0.002/0.0002 0.3

25 1 800 0.5 2 0.7 7500 150 0.04/0.004/0.0004 0.7

26 1 1600 0.5 3 0.3 7500 150 0.04/0.004/0.0004 0.3 X18 M = 200 ms

initial sst = 231 X17 /2 (arbitrary large value)

initial cwnd = 2 (default Microsoft Windows X16 TM value)

X14 no long-lived flows

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

X18 M = 200 ms

initial sst = 231 X17 /2 (arbitrary large value)

initial cwnd = 2 (default Microsoft Windows X16 TM value)

X14 no long-lived flows

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

27 2 800 0.5 3 0.7 7500 150 0.02/0.002/0.0002 0.3

28 2 1600 0.5 2 0.3 7500 150 0.02/0.002/0.0002 0.729 1 800 1 3 0.3 7500 150 0.02/0.002/0.0002 0.7

30 1 1600 1 2 0.7 7500 150 0.02/0.002/0.0002 0.3

31 2 800 1 2 0.3 7500 150 0.04/0.004/0.0004 0.3

32 2 1600 1 3 0.7 7500 150 0.04/0.004/0.0004 0.7

X20 prON = 0.25, prONsecond = 0.08, prONthird = 0.17 

X19 MI = 18,000 (x .2 

M =) 3600 s

8 00 s

X20 prON = 0.25, prONsecond = 0.08, prONthird = 0.17 

X19 MI = 18,000 (x .2 

M =) 3600 s

8 00 s

baseSources = 100

January 29, 2010Innovations in Measurement Science

9

Scale experiment up to a larger faster network simply, e.g., multiply X3 values by 10 and set 
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Summar

y of Our Ex

periments Com

parin

g Con

gestion Control A

Incremental Expe

y p pg g 

Experiment #1a – Large (up to 278,000 sources), Fast (up to 192 Gbps backbone) netw

25 minutes simulated; 3 Time Periods; large (232/2) initial slow start th

How do the algorithms react to and recover from spatiotemporal c

25 minutes simulated;

3 Time Periods; large (232/2) initial slow-start th

all sources use same alternate congestion control algorithm 

Experiment #1b – Same as #1a except smaller (up to 27,800 sources), slower (up to 28

network; low (100) initial sst

E i t #2 S ll ( t 26 085 ) Sl ( t 38 4 Gb b kb ) N t 

How do the algorithms improve flow throughputs and affect TCP 

Experiment #2a 

–

Small (up to 26,085 sources), Slow (up to 38.4 Gbps 

backbone) N

etw

plus downloading software and movies; 60 minutes simulated; large (

some sources use standard TCP and some use alternate congestion 

Experiment #2b – Same as #2a except low (100) initial sst

Experiment #2c – Same as #2a except larger (up to 261,792 sources), faster (up to 384 

network 

January 29, 2010Innovations in Measurement Science 10
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

x1 - All ex

periments used the same three-tier to

pology based on the Ab

A

I

A1

A2

A1a

A1b

A1c

A1d

A2a A2b

C2f

C2e

C2d C2c

C2b

C2a E1

E1b

E1a G2e

G2c

G2b

G2

G2d

G2f

I1c

I1b

I1

I1

I1d

I2

I2c

I2a I2b

I2d

K1

K1a K1b

I2f

K2b

G2g K2a

I2e E0a

I1e I1f I1g

I2g

A2d

A2c

E1c E1d K1d

K1c

K

A

I

A1

A2

A1a

A1b

A1c

A1d

A2a A2b

C2f

C2e

C2d C2c

C2b

C2a E1

E1b

E1a G2e

G2c

G2b

G2

G2d

G2f

I1c

I1b

I1

I1

I1d

I2

I2c

I2a I2b

I2d

K1

K1a K1b

I2f

K2b

G2g K2a

I2e E0a

I1e I1f I1g

I2g

A2d

A2c

E1c E1d K1d

K1c

K

p p gy

B

C

G

I

K

J

A1e

E

A1f A2g

B0a

B1

B1b

B1a

C1

C1a

C2

E1

C2g

E2a E2

E2b

E2c

G1b

G1c G1dG1e

G2a

C1G

G1a

G1f J2

J2f

I0a

I1a

J2g

K

K0a

G1g

B1c C1g E2g

C0a

B

C

G

I

K

J

A1e

E

A1f A2g

B0a

B1

B1b

B1a

C1

C1a

C2

E1

C2g

E2a E2

E2b

E2c

G1b

G1c G1dG1e

G2a

C1G

G1a

G1f J2

J2f

I0a

I1a

J2g

K

K0a

G1g

B1c C1g E2g

C0a

D

F

B2g

H

B2f

B2

B2a

B2bB2c

B2d

B2e D1

D2g

D2

C1b

C1c C1d

C1e

C1f E2f E2d E2e

F0a

H2

H1 H2a H2g

J1

J1e

J1c J1d

J1b

J1a

J1f

J2a J

H2f

J1g

F2

B1d

D

F

B2g

H

B2f

B2

B2a

B2bB2c

B2d

B2e D1

D2g

D2

C1b

C1c C1d

C1e

C1f E2f E2d E2e

F0a

H2

H1 H2a H2g

J1

J1e

J1c J1d

J1b

J1a

J1f

J2a J

H2f

J1g

F2

B1d

Access Router n x Normal SpeedAccess Router m x Normal Speed

B2e

D1b

F1d

D1a

D2

D2a

D2b

D2c D2d

D2e

F0a

F1

F1bF1a

F1c

F2

F2a

F2b F2c F2d

F2e

H2b

H2c H2d

H2e

H1b

H1a

F2f

H2f

D2f

F2g

F1g

F1e F1f

D1c D1d

H1c H1d

Access Router Normal Speed

102 to 103 Sources (not shown) and Receivers (not sho

under each Access Router 

Access Router n x Normal SpeedAccess Router m x Normal Speed

B2e

D1b

F1d

D1a

D2

D2a

D2b

D2c D2d

D2e

F0a

F1

F1bF1a

F1c

F2

F2a

F2b F2c F2d

F2e

H2b

H2c H2d

H2e

H1b

H1a

F2f

H2f

D2f

F2g

F1g

F1e F1f

D1c D1d

H1c H1d

Access Router Normal Speed

102 to 103 Sources (not shown) and Receivers (not sho

under each Access Router 

B kb 11

Router Type Number

DD-flowsFlow Classes

Ver

y Fast (VF)

Path Class 

DD-flowsFlow Classes

Ver

y Fast (VF)

Path Class 

Access Router m x Normal Speed

N l A 105

F-class Access 28D-class Access

6

PoP 22

Backbone 11N l A 105

F-class Access 28D-class Access

6

PoP 22

Backbone 11

F

N-flows

D

N-flows

FF-flowsD

F-flows

Typical (T)Fast (F) 

y ()

F

N-flows

D

N-flows

FF-flowsD

F-flows

Typical (T)Fast (F) 

y ()

All flows transit 

the backbone

January 29, 2010Innovations in Measurement Science 11

N-class 

Access 105 NN-flows 
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Tier 4 is Sources and Receivers

Source Behavior 

For simplicity the state diagram omits a flow connection phase that occurs prior to sending and also the 

January 29, 2010Innovations in Measurement Science 12

For simplicity, the state diagram omits

a flow connection phase that occurs prior to sending, and also the 

failure after which a source reenters the thinking state
Study of Proposed Internet Congestion Control Algorithms – Mills et al. Design for Exp

Algorithms Compared Parameters Varied 

Fast Active-Queue Management Scalable Transmission Control Protocol 3 FAST

2 CTCP Compound Transmission Control Protocol1 BIC Binary Increase Congestion Control

Identifier Label Name of Congestion-Avoidance Algorithm

Fast Active-Queue Management Scalable Transmission Control Protocol 3 FAST

2 CTCP Compound Transmission Control Protocol1 BIC Binary Increase Congestion Control

Identifier Label Name of Congestion-Avoidance Algorithm Parameter Definition PLUS 

x2 Propagation Delay Multiplier x3 Network Speed x4 Buffer Sizing Algorithm 

x6 Source Distribution Uniform

7 TCP Transmission Control Protocol (Reno)6 Scalable Scalable Transmission Control Protocol5 HTCP Hamilton Transmission Control Protocol4 HSTCP High-Speed Transmission Control Protocol7 TCP Transmission Control Protocol (Reno)6 Scalable Scalable Transmission Control Protocol5 HTCP Hamilton Transmission Control Protocol4 HSTCP High-Speed Transmission Control Protocol

Parameters F

x9 Avg. Think Time 

x11 Avg. Size for Web Object 1

x5 Number Sources 2 (baseS

baseSources = 1000

Record Selected Totals 

Scenario

x5 Number Sources

2 (baseS

x7 Receiver Dist. 0.6/0.2/0x8 Prob. Hfast 0.4x10 User Patience infinitex12 L

arge Files

Fp = 

0.1

Start 10 mins. 15 mins. 20 mins. 25 mins.

Warm up Period Time Period 1 Time Period 2 Time Period 3

Add Three Long-Lived 

Flows Between 

D i t d Sit

Return to Normal Web 

Traffic and LongLi d Fl

Add Jumbo File 

Transfers Between 

D i t d Sit

Normal Web Traffic: 

Download Web Pages 

d D

a ge es

p 0 

x13 ST Congestion Jon=0.6

x14 Long Flows 3x15 Algorithm Approprx16 Initial cwnd

2 packe

and Documents Designated Sites Designated Sites Lived Flows

x17 Initial sst

231/2

x18 MI 200 msx19 Duration 25 minsx20 Startup Pattern 25%;8%

pa

January 29, 2010Innovations in Measurement Science 13
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Domain View of Ex

periment #1a

Design for Exp

P

O

P 24 Gbps 12 Gbps

Backbone 192 Gbps 96 Gbps

Router PLUS (+1) Minus (-1)

P

O

P 24 Gbps 12 Gbps

Backbone 192 Gbps 96 Gbps

Router PLUS (+1) Minus (-1)

p

Router Speeds

0.50.6

e0.0016

0.0018

0.002

Max. = 0.0018

0.50.6

e0.0016

0.0018

0.002

Max. = 0.0018

0.50.6

e0.0016

0.0018

0.002

Max. = 0.0018

Congestion Condi

Directly Connected Access 24 Gbps 12 GbpsFast Access 4.8 Gbps 2.4 GbpsNormal Access 2.4 Gbps 1.2 Gbps

O Gbps Gbps

Directly Connected Access 24 Gbps 12 GbpsFast Access 4.8 Gbps 2.4 GbpsNormal Access 2.4 Gbps 1.2 Gbps

O Gbps Gbps

P ti D l

0.20.30.4

Retransmission Rate

0

0.00020.00040.00060.0008

0.001

0.00120.0014

Retransmission Rate

0.20.30.4

Retransmission Rate

0

0.00020.00040.00060.0008

0.001

0.00120.0014

Retransmission Rate

0.20.30.4

Retransmission Rate

0

0.00020.00040.00060.0008

0.001

0.00120.0014

Retransmission Rate

Minus (-1)

6 41 100

PLUS (+1) 12 81 200

Min Avg Max

Minus (-1)

6 41 100

PLUS (+1) 12 81 200

Min Avg Max

Propagation 

D

elays

0

0.1

12 8 20 2 32 26 3 14 4 15 27 9 16 10 28 11 18 24 22 19 1

Condition

12 8 20 2 32 26 3 14 4 15 27 9 16 10 28 11

Condition

N

L

M 0

0.1

12 8 20 2 32 26 3 14 4 15 27 9 16 10 28 11 18 24 22 19 1

Condition

12 8 20 2 32 26 3 14 4 15 27 9 16 10 28 11

Condition

0

0.1

12 8 20 2 32 26 3 14 4 15 27 9 16 10 28 11 18 24 22 19 1

Condition

12 8 20 2 32 26 3 14 4 15 27 9 16 10 28 11

Condition

N

L

M

N = none, L = Low, M = Moderate, C 

278,000 174,600

PLUS (+1) Minus (-1)

Number of Sources

224 Total Runs (32 condition

Statistic Statistic Flows Com

plete

162 764

1,302,110

Max

91 555

732,437

Avg

40 691

325,528

Min

PLUS (+1)

POP 221 505 908

Backbone 1,153 2,606 4,654Router Min Avg Max

Minus (-1)

162 764

1,302,110

Max

91 555

732,437

Avg

40 691

325,528

Min

PLUS (+1)

POP 221 505 908

Backbone 1,153 2,606 4,654Router Min Avg Max

Minus (-1)

Router Buffer Sizes

Total All Runs 16,583,418,06Max. Per Condition 154,914,95Min. Per Condition 40,966,01Avg. Per Condition 74,033,11

p

Total All Runs 16,583,418,06Max. Per Condition 154,914,95Min. Per Condition 40,966,01Avg. Per Condition 74,033,11

p

January 29, 2010Innovations in Measurement Science 14

25,879

162,764

14,55791,555

6,470

40,691

Access 91 207 369

POP 221 505 908

25,879

162,764

14,55791,555

6,470

40,691

Access 91 207 369

POP 221 505 908
Study of Proposed Internet Congestion Control Algorithms – Mills et al. Design for Ex

Selected Res

ponse Measurements for Ex

periment #1

y42 Average number of connecting flows

Response Definition

p p

Macroscopic Behavior Goodput on Flow Clas

Response Definitiony9 Average goodput (pps) for 

y5 Average flows completed per measurement intervaly1 Average number of active (i.e., connected) flows

y43 Average number of active flows in initial slow starty44 Average number of active flows in normal congestion-control modey45 Average number of active flows in alternate congestion-control mode

y3 Average packets output per measurement intervaly5 Average flows completed per measurement intervaly1 Average number of active (i.e., connected) flows

y43 Average number of active flows in initial slow starty44 Average number of active flows in normal congestion-control modey45 Average number of active flows in alternate congestion-control mode

y3 Average packets output per measurement interval

y13 Average goodput (pps) for y21 Average goodput (pps) for 

y17 Average goodput (pps) for y25 Average goodput (pps) for 

y2 Average congestion-window increases per active flowy4 Average congestion window per active flowy8 Average round-trip queuing delayy7 Average smoothed round-trip time (SRTT)y6 Average retransmission ratey2 Average congestion-window increases per active flowy4 Average congestion window per active flowy8 Average round-trip queuing delayy7 Average smoothed round-trip time (SRTT)y6 Average retransmission rate

y33 Average goodput (pps) for the long-d

Response Definition

Goodput on Long-Live

y29

Average goodput(pps) for 

y35 Average goodput (pps) for the short-dy34 Average goodput (pps) for the mediu

Response Definition

Buffer Utilization on Selec

T.

y1 Aggre

gate 

packets in

put

Response Definition

T.

y1 Aggre

gate 

packets in

put

Response Definition

Aggregate Measures

y38 Average buffer saturation foy39 Average buffer saturation fo

y40 Average buffer saturation fo

y37 Average buffer saturation foy36 Average buffer saturation fo

Response Definition

y38 Average buffer saturation foy39 Average buffer saturation fo

y40 Average buffer saturation fo

y37 Average buffer saturation foy36 Average buffer saturation fo

Response Definition

T.y3 Aggregate flows connectedT.y4 Aggregate flows completedT.y5 Average SYNs sent per flowT.y2 Aggregate packets output

y gg g p p

T.y3 Aggregate flows connectedT.y4 Aggregate flows completedT.y5 Average SYNs sent per flowT.y2 Aggregate packets output

y gg g p p

January 29, 2010Innovations in Measurement Science 15

y40 Average buffer saturation fo

y41 Average buffer saturation fo

y40 Average buffer saturation fo

y41 Average buffer saturation fo
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Cluster Analyses Over All Macroscopic Responses

Analysis for E

January 29, 2010Innovations in Measurement Science 16

Algorithm 3 stands out
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Each Res

ponse Subjected to Detailed Anal

ysis

Analysis for E

pj y

Retransmission Rate

January 29, 2010Innovations in Measurement Science 17

Conditions
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

All Detailed Anal

yses Reflected in Condition-Res

ponse Sum

Analysis for E

y p 

Statistically significant outliers

January 29, 2010Innovations in Measurement Science 18
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Filters Applied to Condition-Res

ponse Summaries

Analysis for E

Statistically significant outliers &10%



January 29, 2010Innovations in Measurement Science 19
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Ex

periment #1b (smaller, slower network and low initial sst and add

Design for Exp

0.3

0.35

0 00003

0.000035

0.00004

Max = 3.56 

x 10-5 0.0025

0.003

0.3 Max = 

0.35

0 00003

0.000035

0.00004

Max = 3.56 

x 10-5 0.0025

0.003

Max = 

p (, 

Router Speeds Congestion Condi

POP 3.6 Gbps 1.8 Gbps

Backbone 28.8 Gbps 14.4 GbpsRouter PLUS (+1) Minus (-1)

POP 3.6 Gbps 1.8 Gbps

Backbone 28.8 Gbps 14.4 GbpsRouter PLUS (+1) Minus (-1)

0 1

0.15

0.2

0.25

Retransmission Rate

0

0.000005

0.00001

0.000015

0.00002

0.000025

0.00003

8 12 2 20 26 32 14 3 15 27 9

Condition

Retransmission Rate

0

0.0005

0.001

0.0015

0.002

4 

Retransmission Rate

0 1

0.15

0.2

0.25

Retransmission Rate

0

0.000005

0.00001

0.000015

0.00002

0.000025

0.00003

8 12 2 20 26 32 14 3 15 27 9

Condition

Retransmission Rate

0

0.0005

0.001

0.0015

0.002

4 

Retransmission Rate

P ti D l

Directly Connected Access 3.6 Gbps 1.8 Gbps

Fast Access 720 Mbps 360 Mbps

Normal Access 360 Mbps 180 Mbps

POP 3.6 Gbps 1.8 Gbps

Directly Connected Access 3.6 Gbps 1.8 Gbps

Fast Access 720 Mbps 360 Mbps

Normal Access 360 Mbps 180 Mbps

POP 3.6 Gbps 1.8 Gbps

0

0.05

0.1

8 12 2 20 26 32 14 3 15 27 9 4 10 16 28 11 22 17 29 23 5 

Condition

RCondition

N

L

M

0

0.05

0.1

8 12 2 20 26 32 14 3 15 27 9 4 10 16 28 11 22 17 29 23 5 

Condition

RCondition

N

L

M

Propagation 

D

elays

Minus (-1)

6 41 100

PLUS (+1) 12 81 200

Min Avg Max

Minus (-1)

6 41 100

PLUS (+1) 12 81 200

Min Avg Max

Number of Sources

256 Total Runs (32 conditions x 

27,800 17,460

PLUS (+1) Minus (-1)

Flows

Completed

Statistic 

Router Buffer Sizes

195,317

Max

109,866

Avg

48,830

Min

PLUS (+1)

Backbone 547 1,236 2,208

Router Min Avg Max

Minus (-1)

195,317

Max

109,866

Avg

48,830

Min

PLUS (+1)

Backbone 547 1,236 2,208

Router Min Avg Max

Minus (-1)

Avg. per condition 8,329,266 Min. per condition 4,329,268 Max. per condition 16,729,532 Total all runs 2,132,292,096 

January 29, 2010Innovations in Measurement Science 20

6,104

24,415

2,184

13,734

971

6,104

Access 44 99 105

POP 105 240 431

6,104

24,415

2,184

13,734

971

6,104

Access 44 99 105

POP 105 240 431

Total all runs 2,132,292,096 
Study of Proposed Internet Congestion Control Algorithms – Mills et al. Design for Expe

Algorithms Compared Parameters Varied 

4 FAST-AT FAST with -tuning Enabled

Fast Active-Queue Management Scalable Transmission Control Protocol 3 FAST

2 CTCP Compound Transmission Control Protocol

1 BIC Binary Increase Congestion Control

Identifier Label Name of Congestion-Avoidance Algorithm

4 FAST-AT FAST with -tuning Enabled

Fast Active-Queue Management Scalable Transmission Control Protocol 3 FAST

2 CTCP Compound Transmission Control Protocol

1 BIC Binary Increase Congestion Control

Identifier Label Name of Congestion-Avoidance Algorithm Parameter Definition PLUS (+1

x2 Propagation Delay Multiplier x3 Network Speed 16x4 Buffers (RTT x C x Qfactor) Qfac

x5 Source Multiplier x8 Probability of Fast Source 

7 Scalable Scalable Transmission Control Protocol

6 HTCP Hamilton Transmission Control Protocol

5 HSTCP High-Speed Transmission Control Protocol

4 FAST AT FAST with  tuning Enabled

7 Scalable Scalable Transmission Control Protocol

6 HTCP Hamilton Transmission Control Protocol

5 HSTCP High-Speed Transmission Control Protocol

4 FAST AT FAST with  tuning Enabled

24 Fl

ow 

G

roups

x9

Avg. Think Time 

x11 Avg. Size for Web Object 150 px12 Probability of Large Files Fp=0.04;Sp=0.004;Mp= 

x15 Probability of Alternate Alg. 

baseSources=100 & File Size Multipliers: Fx=10

o G oups

Parameters Fix

6 TYPICAL NORMAL Movie5 TYPICAL FAST Movie4 FAST NORMAL Movie3 FAST FAST Movie

2 VERY FAST NORMAL Movie1 VERY FAST FAST Movie

Identifier Path Class Interface Speed File Type

6 TYPICAL NORMAL Movie5 TYPICAL FAST Movie4 FAST NORMAL Movie3 FAST FAST Movie

2 VERY FAST NORMAL Movie1 VERY FAST FAST Movie

Identifier Path Class Interface Speed File Type

Parameter Definition 

x6 Source Distribution 

x7 Receiver Distribution 

14 VERY FAST NORMAL Document

13 VERY FAST FAST Document12 TYPICAL NORMAL Service Pack11 TYPICAL FAST Service Pack10 FAST NORMAL Service Pack

9 FAST FAST Service Pack

8 VERY FAST NORMAL Service Pack7 VERY FAST FAST Service Pack

14 VERY FAST NORMAL Document

13 VERY FAST FAST Document12 TYPICAL NORMAL Service Pack11 TYPICAL FAST Service Pack10 FAST NORMAL Service Pack

9 FAST FAST Service Pack

8 VERY FAST NORMAL Service Pack7 VERY FAST FAST Service Pack

x7 Receiver Distribution 

x10 User Patience x13 Spatiotemporal Congestion x14 Long-Lived Flows x16 Initial cwnd 

21 FAST FAST Web Object

20 VERY FAST NORMAL Web Object

19 VERY FAST FAST Web Object18 TYPICAL NORMAL Document17 TYPICAL FAST Document16 FAST NORMAL Document15 FAST FAST Document

14 VERY FAST NORMAL Document

21 FAST FAST Web Object

20 VERY FAST NORMAL Web Object

19 VERY FAST FAST Web Object18 TYPICAL NORMAL Document17 TYPICAL FAST Document16 FAST NORMAL Document15 FAST FAST Document

14 VERY FAST NORMAL Document x16 Initial cwnd

x17 Initial sst #2a 

x18 Meas. Int. Size x19 Simulation Duration 

January 29, 2010Innovations in Measurement Science 21

24 TYPICAL NORMAL Web Object23 TYPICAL FAST Web Object22 FAST NORMAL Web Object24 TYPICAL NORMAL Web Object23 TYPICAL FAST Web Object22 FAST NORMAL Web Object x20 Startup Pattern 
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Domain View of Ex

periment #2a/2b

Design for Expe

Router Speeds Congestion Condi

POP 4.8 Gbps 2.4 GbpsBackbone 38.4 Gbps 19.2 GbpsRouter PLUS (+1) Minus (-1)POP 4.8 Gbps 2.4 GbpsBackbone 38.4 Gbps 19.2 GbpsRouter PLUS (+1) Minus (-1)

0.025

0.03

Min = 2 in 10,000 

0.025 C1 C2 C3 C4 

0.03

Min = 2 in 10,000 

C1 C2 C3 C4 

Propagati

on D

elays

Directly Connected Access 4.8 Gbps 2.4 GbpsFast Access 960 Mbps 720 MbpsNormal Access 480 Mbps 240 MbpsDirectly Connected Access 4.8 Gbps 2.4 GbpsFast Access 960 Mbps 720 MbpsNormal Access 480 Mbps 240 Mbps

0.01

0.015

0.02

Retransmission Rate #2a high sst opaga o e ays

Number of Sources

Minus (-1)

6 41 100

PLUS (+1) 12 81 200

Min Avg Max

Minus (-1)

6 41 100

PLUS (+1) 12 81 200

Min Avg Max

0

0.005

16 8 24 32 28 12 4 20 14 6 30 22 15 2 10 31 23 26 11 3 7 13 

Condition

0.030

Min = 4 in 1 0000 000 

Router Buffer Sizes

Number of Sources

26,085 17,355

PLUS (+1) Minus (-1)

0.0150.0200.025

mission Rate

Min

=

4 in 1,0000,000 

C1 C2 C3 

0.0150.0200.025

mission Rate

Min

=

4 in 1,0000,000 

C1 C2 C3 

#2b

0.0000.005

Retrans 0.010m

low sst

5 176

32,553

260,422

Max

2 911 60

18,310.75

146,487.30

Avg

1 2948,138

65,105

Min

x3 = 1.0

Access 647 1 455 82 2 588

POP 4,096 9,155.25 16,276Backbone 32,553 73,243.50 130,211Router Min Avg Max

x3 = 0.5

5 176

32,553

260,422

Max

2 911 60

18,310.75

146,487.30

Avg

1 2948,138

65,105

Min

x3 = 1.0

Access 647 1 455 82 2 588

POP 4,096 9,155.25 16,276Backbone 32,553 73,243.50 130,211Router Min Avg Max

x3 = 0.5 x2 x2

January 29, 2010Innovations in Measurement Science 22

16 8 24 12 32 28 4 14 30 20 6 22 15 2 10 31 23 11 3 26 7 1

Condition

Access 1,294 2,911.60 5,176 647 1,455.82 2,588
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Selected Res

ponse Measurements for Ex

periment #2

Design for Ex

p p

y3 Average number of flows using normal congestion avoidance

y2 Average number of flows in initial slow-starty1 Average number of active flows

Response Definition

y3 Average number of flows using normal congestion avoidance

y2 Average number of flows in initial slow-starty1 Average number of active flows

Response Definition

Macroscopic Behavior

0.050.06

Computed from t

y8 Average size of congestion window per flowy7 Average number of flows completed per measurement interval

Average aggregate packets output by the network every measurement interval y6

y5 Average number of flows attempting to connecty4 Average number of flows using alternate congestion avoidance

y3 Average number of flows using normal congestion avoidance

y8 Average size of congestion window per flowy7 Average number of flows completed per measurement interval

Average aggregate packets output by the network every measurement interval y6

y5 Average number of flows attempting to connecty4 Average number of flows using alternate congestion avoidance

y3 Average number of flows using normal congestion avoidance

0.020.030.04

Retransmission Ratemea

y13 Proportion of completed flows that were Web objectsy12 Aggregate number of flows completedy11 Average smoothed round-trip timey10 Average retransmission rate

Average number of congestion-window increases per flow per measurement interval y9

y13 Proportion of completed flows that were Web objectsy12 Aggregate number of flows completedy11 Average smoothed round-trip timey10 Average retransmission rate

Average number of congestion-window increases per flow per measurement interval y9

0 5000 1 .104 

0

0.01

Time

discard first

30 mins.

re

0 5000 1 .104 

0

0.01

Time

discard first

30 mins.

re

y16 Proportion of completed flows that were movie downloadsy15 Proportion of completed flows that were service-pack downloadsy14 Proportion of completed flows that were document downloadsy16 Proportion of completed flows that were movie downloadsy15 Proportion of completed flows that were service-pack downloadsy14 Proportion of completed flows that were document downloads

48 Goodput Measures (2 Per Flow Group x 24 Flow Groups48 Goodput Measures (2 Per Flow Group

x 24 Flow Groups

Response Definition

y2(u) Avg. Goodput (pps) for flows using alternate algorithm

y16(u) Avg. Goodput (pps) for flows using standard TCP

January 29, 2010Innovations in Measurement Science 23
Study of Proposed Internet Congestion Control Algorithms – Mills et al. Analysis for E

Ex

p yq p 

eriment #2 Uses Anal

ysis Techni

ques from Ex

periment #1 and Addit

VF-F

L 

VF-F

Comparative Goodput bar graphs 

Legen

Flows transferrin

g movies on ver

y fast 

paths with fast interface s

p

Goodput (pps) Goodput (% max)

January 29, 2010Innovations in Measurement Science 24

g yp p 
Study of Proposed Internet Congestion Control Algorithms – Mills et al. Analysis for E

Princi

pal Com

ponents Anal

ysis of Good

puts (hi

gh sst)

x2: Propagation Delayx3: Network Speedx11: File Size

p p y p (g

Group 1: lower network speedGroup 2: higher network speed, longer propagation delay (above line smaller file size, below linGroup 3: higher network speed, shorter propagation delay (above line smaller file size, below l

January 29, 2010Innovations in Measurement Science 25

Suggests that under high initial sst congestion control algorithm not signif
Study of Proposed Internet Congestion Control Algorithms – Mills et al. Analysis for E

Biplots of Avg Goodputs on alternate flows vs TCP flowBiplots of Avg. Goodputs on alternate flows vs. TCP flow

Mi t Movies tranon very fast with fast inteand high ini

January 29, 2010Innovations in Measurement Science 26

Under many conditions Scalable, HSTCP and BIC flows achieve higher goodpu
Study of Proposed Internet Congestion Control Algorithms – Mills et al. Analysis for E

Histograms of Avg Goodput differences between alternate flows anHistograms of Avg. Goodput differences between alternate flows an

Movion vewith speeinitia

January 29, 2010Innovations in Measurement Science 27

Under higher congestion Scalable, HSTCP and BIC flows achieve higher goodp
Study of Proposed Internet Congestion Control Algorithms – Mills et al. Analysis for E

Goodput rank matrix Goodput rank matrix

– CTCP flows under high initial CTCP flows under high initial ss

January 29, 2010Innovations in Measurement Science 28

CTCP provides higher relative Goodput on smaller files
Study of Proposed Internet Congestion Control Algorithms – Mills et al. Analysis for E

Goodput rank matrix Goodput rank matrix

– TCP flows competing with CTCP flows under 

TCP flows competing with CTCP flows under 

January 29, 2010Innovations in Measurement Science 29

TCP flows achieve high relative Goodput when competing with CTCP 
Study of Proposed Internet Congestion Control Algorithms – Mills et al. Analysis for Expe

Average and Standard Deviation in Goodput Ranks Average and Standard Deviation in Goodput Ranks

low initial sst high initial sst

HTCPCTCP

SCALABLE HTCP 

FA

SCALABLE

FAST-AT

FAST

HSTCP

BIC

HSTCP

BIC

SCALABLE

Average Goodput Rank for All Flows Average Goodput Rank for A

CTCP achieves relatively high ranking Goodput for its flows and competin

January 29, 2010Innovations in Measurement Science 30
Study of Proposed Internet Congestion Control Algorithms – Mills et al. Design for Ex

Domain View of Ex

periment #2c 

– Re

p g, eat #2a with lar

ger, faste

Router Speeds Congestion Condi

POP 48 Gbps 24 Gbps

Backbone 384 Gbps 192 GbpsRouter PLUS (+1) Minus (-1)

POP 48 Gbps 24 Gbps

Backbone 384 Gbps 192 GbpsRouter PLUS (+1) Minus (-1)

0.018

0.02

Min = 3.8 in 1,0000,000,000 

C1 C2 C3 

0.018

0.02

Min = 3.8 in 1,0000,000,000 

C1 C2 C3 

Propagati

on D

elays

Directly Connected Access 48 Gbps 24 GbpsFast Access 9.6 Gbps 7.2 GbpsNormal Access 4.8 Gbps 2.4 GbpsDirectly Connected Access 48 Gbps 24 GbpsFast Access 9.6 Gbps 7.2 GbpsNormal Access 4.8 Gbps 2.4 Gbps

0.01

0.0120.0140.016

0.018

smission Rate 0.01 0.012

0.0140.016

0.018

smission Rate Generally lower cong

opaga o e ays

Number of Sources

Minus (-1)

6 41 100

PLUS (+1) 12 81 200

Min Avg Max

Minus (-1)

6 41 100

PLUS (+1) 12 81 200

Min Avg Max

0

0.0020.0040.0060.008

16 28 4 24 8 30 10 2 22 6 32 20 14 12 15 23 31 3 5 11 26 

Retran

0

0.0020.0040.0060.008

16 28 4 24 8 30 10 2 22 6 32 20 14 12 15 23 31 3 5 11 26 

Retran

Router Buffer SizesNumber of Sources

261,792 174,600

PLUS (+1) Minus (-1)

16 28 4 24 8 30 10 2 22 6 32 20 14 12 15 23 31 3 5 11 26 

Condition

16 28 4 24 8 30 10 2 22 6 32 20 14 12 15 23 31 3 5 11 26 

Condition

H

C

FAST

BIC

SCALABLE

H

C

FAST

BIC

SCALABLE

Router Buffer Sizes

51,757

325,528

2,604,219

Max

29,113

183,110

1,464,874

Avg

12,93981,382

651,055

Min

x3 = 1.0

Access 6,469 14,556 25,878POP 40,691 91,555 162,764

Backbone 325,527 732,437 1,302,109Router Min Avg Max

x3 = 0.5

51,757

325,528

2,604,219

Max

29,113

183,110

1,464,874

Avg

12,93981,382

651,055

Min

x3 = 1.0

Access 6,469 14,556 25,878POP 40,691 91,555 162,764

Backbone 325,527 732,437 1,302,109Router Min Avg Max

x3 = 0.5 x2 x2

HSTCP

BIC

January 29, 2010Innovations in Measurement Science 31

Average Goodput Rank for All Fl
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Utility and Safety Utility and Safety

1. Increase rate: How quickly can the maximum transmission rate be 2. Loss/Recovery processing:

a. How much does the protocol reduce transmission rate upon a b. How quickl

y does the protocol increase transmission rate afte

3. Fairness: How well do standard TCP flows do when competing wi4. Utility bounds Utility bounds: Under what circumstances can alternate congestio

: Under what circumstances can alternate congestio

algorithms provide improved user goodputs?

5. Safety: Will widespread deployment of alternate algorithms induce 

macroscopic characteristics in the Internet? 

January 29, 2010Innovations in Measurement Science 32
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Increase Rate Increase Rate

3⁄4 Assuming low congestion, setting of initial sst is a key factor

 High initial sst – all algorithms (standard TCP included) achieved ma

transmission rate with transmission rate with the same (exponential) quickness the same (exponential) quickness

 Low initial sst – alternate algorithms achieved maximum transmissio

more quickly than (linear) increase of standard TCP

3⁄4 Under heavy congestion setting of initial Under heavy congestion, setting of initial sst matters matters little because little because 

slow start terminates upon first packet loss and a flow enters congavoidance, where loss/recovery processing determines goodput

3⁄4 On real TCP flows receivers may convey a window (rwn

d) that ca

goodput because sources pace transmission based on min(cwndTypically, rwnd < cwnd. In our studies, we assume an infinite rwnd 

order to compare effects of congestion control order to compare effects of congestion control algorithms algorithms. Goodp

Goodp

TCP flows in a real network might be constrained by rwnd, so thacongestion control algorithms would provide little advantage over In fact, even TCP congestion control does not have much influenc

d

d

January 29, 2010Innovations in Measurement Science 33

rwn

d < cwn

d.
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Loss/Recovery Processing Loss/Recovery Processing

3⁄4 One group of algorithms (Scalable TCP, BIC1 and HSTCP) reduce 

rate less than standard TCP after a packet loss

 Unfair to TCP flows and to new flows using alternate algorithms Unfair to TCP flows and to new flows using alternate algorithms

3⁄4 Another group of algorithms (CTCP, FAST and FAST-AT) reduce tr

rate by 1⁄2 following a loss (HTCP is a hybrid with reduction betwee

 Th l ith k t bt i hi h These algorithms see

k to obt

ain hi

g

her good t pu bi i t 

by increasing transm

more quickly than standard TCP (the rate of increase varies with the 

 HTCP reverts to TCP congestion avoidance for 1 s after each loss, wh

can lead to lower goodputs than other alternate algorithms

3⁄4 Under extreme spatiotemporal congestion, most alternate algorithm

a low-window threshold and revert to standard TCP congestion avo

procedures (giving no advantage to alternate procedures) procedures (giving no advantage to alternate procedures)

 FAST and FAST-AT do not use TCP congestion avoidance under any

conditions, which can lead to oscillatory behavior and increased loss r

1Note that on re

peated losses occurrin

g close in time, BIC can reduce cwnd substantiall

y 

January 29, 2010Innovations in Measurement Science 34

p g,

y

standard TCP – thus, on paths with very severe congestion TCP can provide higher goo
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Fairness

3⁄4 All alternate algorithms take steps to provide improved goodput ove

comparing fairness must consider relative performance of TCP flowcompeting with flows using each of the alternate algorithms

3⁄4 We found CTCP, HTCP and FAST-AT to be most fair to TCP flows

 Under low initial sst FAST-AT is more unfair because of its quick increa Injecting more FAST-AT packets induced more losses in TCP flows, w

recover only linearly recover only linearly

3⁄4 We found Scalable TCP, BIC and FAST to be most unfair to TCP flo

 Established Scalable and BIC flows (on large files) tended to maintain 

t i i t th TCP fl ft l hil FAST d transmission rates than TCP flows after losses, while FAST recovere

d 

and these alternate algorithms induced more losses in TCP flows

3⁄4 HSTCP appeared moderately fair to TCP flows, especially under co

lower congestion and under low initial sst – HSTCP appeared unfaconditions of heavy congestion

3⁄4 We found that Scalable TCP BIC and HSTCP are also unfair to com

January 29, 2010Innovations in Measurement Science 35

We found that Scalable TCP, BIC and HSTCP are also unfair to comflows that are newly arriving
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Utilit

y Bounds

3⁄4 We found that alternate congestion control algorithms could provide 

utility (goodput) for users – however, this utility would be arise only a specific specific combination combination of circumstances circumstances

 Flow’s rwnd must not be constraining flow transmission rate Flow’s initial sst must be relatively low Flow must be transferring a large file Flow s’ packets must be transiting a relatively uncongested path (i e e

packets must be transiting

a relatively uncongested path (i.e., e

only sporadic losses) or else users must be willing to tolerate marked uin trade for increased gooput

3⁄4 H lik l i thi bi ti f i t i I t t 

How lik

ely is this combination of circumstances on a given Internet 

 Certainly possible to engineer a network, or segments of a network, to 

specific users with improved goodput over TCP

 We suspect a rather low probability for such circumstances to arise ge

i th I t t in the Internet

3⁄4 We conclude that alternate congestion control algorithms can provi

user goodput – however, most users seem unlikely to benefit very o

January 29, 2010Innovations in Measurement Science 36
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Safet

y

3⁄4 We can answer this only in part – additional cautionary findings ma

 We simulated either homogeneous networks where all flows used one

congestion control algorithm or mixes of TCP flows competing with flo

usi lt t ng one alternate al ith t ti lgorithm at a time

 The real Internet could contain a mix of many different types of conge

3⁄4 For most algorithms we studied, under most conditions, we found 

significant change in macroscopic network characteristics

3⁄4 FAST and FAST-AT are exceptions to this general finding

 Under hi

gp p g , h s

patiotem

poral con

gestion, where there were insufficient b

support flows transiting specific routers, FAST and FAST-AT entered abehavior where the flow cwnd increased and decreased rapidly with laamplitude

 Under such conditions the network showed increased loss and retran

a higher number of flows pending in the connecting state and a lower of flows completed over time

3⁄4 We recommend the need for additional study of FAST and FAST-AJanuary 29, 2010Innovations in Measurement Science 373⁄4 We recommend the need for additional study of FAST and FAST A

widespread deployment and use on the Internet
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Characteristics of Individual Alternate AlgorithCharacteristics of Individual Alternate Algorith

1. Implementation complexity: How much code required to impleme2. Activation trigger: What causes a flow to switch from standard TC

avoidance to alternate procedures?

3. Goodput latency: What is the time required for a flow to achieve m

transmission rate?

4. R lt ecovery la

tency: Wh t i th ti i d f fl t 

Wh

at is the time require

d for a flow to recover 

transmission rate after a period of congestion (with sustained loss

January 29, 2010Innovations in Measurement Science 38
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Characteristics of Individual Alternate AlgorithCharacteristics of Individual Alternate Algorith

Algorithm Implementation Com

plexit

y

Activation 

Trigger

Goodput

Latenc

y (av

g)

Recov

p y gg y (

g) Latenc

y 

BIC high 14 packets 18.8 s CTCP moderate 41 packets 7.9 s FAST low none 3.7 s FAST-AT moderate none 3.7 s HSTCP low 31 packets 22.4 s H-TCP moderate 1 s w/o loss 16.6 s Scalable TCP low 16 packets 17.8 s 

January 29, 2010Innovations in Measurement Science 39
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Recommendations

3⁄4 Under some circumstances users may benefit from alternate cong

algorithms – thus it makes sense to deploy such algorithms on the 

3⁄4 Probability appears quite low that a specific user will see benefits o

file transfer

3⁄4 Among the algorithms we studied, CTCP appears to provide the b

Among the algorithms we studied, CTCP appears to provide the bof properties

 Under low congestion, CTCP can increase transmission rate relatively  CTCP reduces rate relatively quickly under sustained congestion and 

maximum transmission rate quickly when congestion eases maximum transmission rate quickly when congestion eases

 CTCP appears relatively friendly to flows using standard TCP CTCP seems unlikely to induce large shifts in the Internet’s macrosco

3⁄4 FAST and FAST FAST and FAST-AT have some appealing properties especially w

AT have some appealing properties, especially w

achieving maximum transmission rate quickly on high-bandwidth, paths and recovering quickly from sporadic losses

3⁄4 However, when transiting highly congested paths with insufficient buff

t fl l FAST d FAST AT t i f ill 

January 29, 2010Innovations in Measurement Science 40

support flow volume, FAST an

d FAST-AT can enter a regime of oscill

a
Study of Proposed Internet Congestion Control Algorithms – Mills et al.

Future Work

3⁄4 Study additional proposed congestion control algorithms

 Of particular interest, CUBIC has replaced BIC as the congestion con

enabled by default in Linux enabled by default in Linux

3⁄4 Consider scenarios where multiple alternate congestion control alg

are mixed together in the same network

3⁄4 Validate findings against live, controlled experiments configured in 

Environment for Network Innovation) or similar test bed environme

3⁄4 Researchers could exploit our findings to propose improvements to 

algorithms we studied – compensating for identified weaknesses, wretaining strengths

3⁄4 Our findings might also help other researchers to improve future d

for additional congestion control algorithms

January 29, 2010Innovations in Measurement Science 41