Predicting Macroscopic Dynamics in Large Distribute

K. Mills

& J. Filliben (NIST),

D

‐Y. Cho (NIH),

& E. Schwar

ASME PVP 2011 July 21, 2011

image generated with http://www.wordle.net/ applied to contents of a paper entitled “Predicting Macroscopic Dynamics in Large Distributed Systems” written by Mills, Filliben

Related Web Page is http://www.nist.gov/itl/antd/Congestion_Control_Study.cfm
• Modern networking technology allows components 

distributed systems to be updated easily.

• Will any given update radically change macroscopic 

dynamics?

• Can we predict how such updates will influence syst

wide behavior?

July 18‐19, 2011

Innovations in Measurement Science 2

We are investigating methods to predict macroscopic d

in large distributed systems.

Here, we demonstrate some of our methods applied to 

how various proposed replacements for the transmissiocontrol protocol (TCP) will affect macroscopic dynamics 

Internet.
Outline

• Introduction to the Problem• Methods to Reduce Stimulus and Respo

State Spaces

• Methods to Analyze Multidimensional

Datasets

• Application to Predict Macroscopic Dyn

of Proposed TCP Replacements

July 18‐19, 2011

Innovations in Measurement Science 
Introduction to the Problem

July 18‐19, 2011

Innovations in Measurement Science 4
0

10002000300040005000

0 2000 4000 6000 8000 10000

cwnd (segments)

Time (0.1 second units)

avg. cwnd = 2745

avg.red cwnd = 1844

avg. blue cwnd = 1196

avg. cwnd = 3042

Internet Congestion Control & TCP

July 18‐19, 2011

Innovations in Measurement Science 5

Router #1680 buffers

Router #2680 buffers

162 msround trip

propagation delay

21 segments/ms 21 segments/ms

Source #1 Source #2 Receiver#1 Receiver#2

80 segments/ms 80 segments/ms 80 segments/ms 80 segments/ms

bottleneck path

252 Mbps Bottleneck Path

Phases in a TCP Flow

TCP Flows Achieve 89 % Utilization So Researchers Pro

TCP Replaceme

Utilizations Much Lower o

Long-Delay Pa

Identifier Acronym Name of Algorith

1 BIC Binary Increase 

Control

2 CTCP Compound TCP3 FAST Fast Active Que

Management Sc

4 HSTCP High Speed TCP5 HTCP Hamilton TCP6 STCP Scalable TCP7 TCP Transmission Co

Protocol
Proposed TCP Replacements Well‐Studied on Bott

July 18‐19, 2011

Innovations in Measurement Science 6

0

10002000300040005000

0 2000 4000 6000 8000 10000

cwnd (segments)

Time (0.1 second units)

avg. cwnd = 3607

avg.red cwnd = 2243

avg. blue cwnd = 1504

avg. cwnd = 3747

0

10002000300040005000

0 2000 4000 6000 8000 10000

cwnd (segments)

Time (0.1 second units)

avg. cwnd = 2745

avg.red cwnd = 1853

avg. blue cwnd = 1553

avg. cwnd = 3406

0

10002000300040005000

0 2000 

cwnd (segments)

Ti

avg. cwnd = 

BIC CTCP 

0

10002000300040005000

0 2000 4000 6000 8000 10000

cwnd (segments)

Time (0.1 second units)

avg. cwnd = 3485

avg.red cwnd = 2170

avg. blue cwnd = 1348

avg. cwnd = 3518

0

10002000300040005000

0 2000 4000 6000 8000 10000

cwnd (segments)

Time (0.1 second units)

avg. cwnd = 3385

avg.red cwnd = 1869

avg. blue cwnd = 1676

avg. cwnd = 3545

0

10002000300040005000

0 2000 

cwnd (segments)

Time 

avg. cwnd = 3

HSTCP HTCP Sca
What would be the macroscopic dynamics if these 

TCP replacements were deployed in the Inte

July 18‐19, 2011

Innovations in Measurement Science 7

Four-Tier Topology (based on the Abilene Network) with 11 Backbone Routers (A-K), 22 Poin

Routers (A1-K2) and 139 Access Routers (A1a-K2d) – 6 red and 28 green Access Routers ma

different speeds from the 105 others – not shown is a fourth tier of hundreds of thousands 

computers
Stimulus and Response State Spaces Are Lar

Network Simulation Models

July 18‐19, 2011

Innovations in Measurement Science 8

e.g., p = 1000 and l = 232 e.g., z = 500 
Methods to Reduce the Scale of the Stimu

Response Spaces

July 18‐19, 2011

Innovations in Measurement Science 9
We Employ Stimulus State

‐Space

Reduction Techniques

July 18‐19, 2011

Innovations in Measurement Science 10

Use experiment design theory to reduce

parameter combinations to 256

Use sensitivity analysis

to identity six most

significant parameters

(232)1000

220

220‐12

Discard parameters not germane to study– reduce by 944 parameters

O(109633) [ 1080

= atoms in visible universe]

(232)56 O(10539)

(232)20 O(10192)

O(10

6

)

256

ParameterReduction

OrthogonalFractional‐Factorial

(OFF) Experiment

Design

2

6‐1 32

Group related remaining parameters– reduce by 36 parameters

Select only

2 values for each parameter

Use experiment design theory again to reduce

parameter combinations to 32

LevelReduction

SensitivityAnalysis

OFFExperimentDesign

Category Identifier NNetworkConfiguration

X1 NX2 PX3 BX4 To

UserBehavior

X5 WX6 PX7 ThX8 PaX9 Se

X10 Lo

Sources &Receivers

X11 So

X12 NX13 DX14 D

Protocols

X15 CX16 InX17 In

Simulation Control & Measurement

X18 MX19 SX20 St

NIST Meso
We Employ Response State‐Space Reduction Te

(here we demonstrate correlation analysis & clu

July 18‐19, 2011

Innovations in Measurement Science 11

Red 80 > |r|x100 < 100 Blue 30 > |r|x100 < 80 Gre

Response Definition

y17 Average Segments/Second on DD flowsy18 Average Segments/Second on DF flowsy19 Average Segments/Second on DN flowsy20 Average Segments/Second on FF flowsy21 Average Segments/Second on FN flowsy22 Average Segments/Second on NN flows

Response Definition

y1 Number of sources transmittingy2 Proportion transmitting [y1 / all sources]y3 Number segments entering networky4 Number of segments leaving networky5 Loss Rate [y4/ (y3 + y4)]y6 Flows completing per intervaly7 Flow-completion rate [y6/(y6+y1)]y8 Connection failures per intervaly9 Connection-failure rate [y8/(y8+y1)]

y10 Retransmission ratey11 Congestion window (cwnd)

y12 cwnd increases per intervaly13 Duplicate ACKs per intervaly14 Timeouts per intervaly15 Round-trip time (rtt)y16 Queuing delay

Response Correlation M
Decide Which Pairs of Correlated Responses to 

July 18‐19, 2011

Innovations in Measurement Science 12

Frequency distribution of |r| for pair-wise correlations – bins highlighted for |r
Cluster Retained Correlated Responses

July 18‐19, 2011

Innovations in Measurement Science 13

Index-Index Plot Sorted by Increasing Count of Correlated Pairs to Indentify Cl

Mutual Correlations that Represent Seven Behavioral Dimensions
Methods to Analyze Multidimensional D

July 18‐19, 2011

Innovations in Measurement Science 14
Even with Response State‐Space Reduction Com

Comparisons Can Yield Large, Multidimensional 

July 18‐19, 2011

Innovations in Measurement Science 15

For example, comparing 7 congestion control algorithms with respecresponses under 32 conditions over three time periods with a mixturcompeting TCP flows yields a multidimensional dataset with > 64,00

We used a range of multidimensional data analysis techniques, including:1. Main-Effects Analysis [a, b, c]2. Cluster Analysis [a, b]3. Primary Principal Components Plots4. Condition-Response Summaries [a, b, c]5. Biplots6. Colored Bar Graphs 7. Rank Analysis
1(a) Sample Main‐Effects Analysis on One Res

July 18‐19, 2011

Innovations in Measurement Science 16

Main effects plot showing absolute and relative influence of each MesoNet parameter (x axis) on 

number of sources transmitting (y1) and identifying six statistically significant parameters – netwtopology (X4), file size (X5), think time (X7) and number (X12) and distribution (X13) of sources
1 (b) Summary of Main‐Effects Analyses Across 18 

July 18‐19, 2011

Innovations in Measurement Science 17

Metric

Class Y#

Network User Behavior Source/Receiver Protocol 

X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X13 X14 X15 X16 X

Flows

Y1 ‐** +** +* ‐** +** +** +**

Y2 ‐** +** +** ‐** +** +**Y3 +** +** +** ‐** +** ‐** ‐** +Y4 ‐** ‐** ‐** +** ‐** +** +** ‐*Y5 +** +** +** ‐** ‐** +** +* 

Congestion

Y6 ‐** ‐** ‐** +** ‐** +** +** +**

Y7 +*Y8 ‐** ‐** ‐** +** +** +** +**

Delay Y9 ‐** +** +** +* +* Y10 ‐** +** +** ‐* +** +**

Aggregate

TP

Y11 +** ‐* +** ‐** ‐** +** +**

Y12 +** +** +** +** ‐** ‐** +**

Long‐Lived

Flow TP

Y13 +** +* +* +** ‐**

Y14 +* +** +** ‐**Y15 +** +** ‐* ‐*

Other Flow

TP

Y16 +** ‐** ‐** +* +** ‐** ‐* +

Y17 +** ‐** +* +** +** ‐** +** ‐** +** Y18 +** ‐** ‐** +** ‐** ‐** +**

Significance of influence of 20 MesoNet parameters (columns) on 18 macroscopic responses (row

period: blue cells indicate significance p < 0.01 and orange cells indicate significance p < 0.05, whighlighted cells indicates the parameter setting that causes an increase in the corresponding re
1 (c) Summary of Parameter Influence on Respons

Time Periods and Two Congestion Control Algo

July 18‐19, 2011

Innovations in Measurement Science 18

 = (|{y | p < 0.01}| + 1⁄2 |{y | p < 0.05}|) / |{y

Parameters with largest influence: network speed (x1), distribution of so

propagation delay (x2), user think time (x7), buffer size (x3) and file size (

number of sources (x12)
2 (a) Cluster Analysis

July 18‐19, 2011

Innovations in Measurement Science 19

Note that congestion-control algorithms may only be compared usame conditions (i.e., parameter combinations) because the condvery different from each other – this leads to the need to plot one dendrogram for each condition (32 here)

Compute normalized Euclidian distance between a pair of congestion-control algorithms in 45 dimensional space (45 responses used in this case)Compute linkage between clusters ofcongestion-control algorithms

Plot as dendrogram and color when the linkagevalue for a pair of clusters falls below 70 % ofthe maximum linkage value 

Algorit

Distance
2 (b) Dendrograms for Each of 32 Conditio

July 18‐19, 2011

Innovations in Measurement Science 20

Identical under no congestion; Similar under low congestion; algorithm 3 distinct unde

IdenticalSimilar

Similar 

Sim

Similar

3 33 33 33 33 

33 3 333 

3 33 3 3
Lower Network

Speed

Higher Network Speed& Longer Propagation Delay

High& S

D

SmallerFile Size

LargerFile Size

LargerFile Size

SmalleFile Siz

3 Primary Principal Components Plots

July 18‐19, 2011

Innovations in Measurement Science 21

PC1 (x axis) vs. PC2 (y axis) from a multivariate dataset containing average throughput achieved on using seven different congestion control algorithms under 32 different parameter combinations. Ciof points and lines within circles distinguish additional subgroups.

Here,congestioncontrolalgorithmdoes notmake adifference
4 (a) Condition‐Response Summaries: Underlying 

July 18‐19, 2011

Innovations in Measurement Science 22

Sample plot analyzing the influence of condition and congestion control algorithm on the segment this experiment retransmission rate was designated as y6) – y axis gives residuals around the meacondition and x axis gives conditions ordered by increasing range of residuals 

Plot shows thatretransmissionrate for congestioncontrol algorithm 3is an outlier underconditions withhigh congestion, andthe higher the level ofcongestion, the morethe algorithm is anoutlier.Grubbs’ test of outliers
4 (b) Condition‐Response Summaries: Rollup Out

Underlying Analyses

July 18‐19, 2011

Innovations in Measurement Science 23

Condition-response summary identifying any statistically significant outliers among congestion coneach of 45 responses measured over 32 different conditions in this particular experiment 
4 (c) Condition‐Response Summaries: Apply 

July 18‐19, 2011

Innovations in Measurement Science 24

Filtered condition-response summary identifying any congestion control algorithms that are statistioutliers and that exhibit at least a 10 % relative effect for each of 45 responses measures over 32 dif
5 Biplots

July 18‐19, 2011

Innovations in Measurement Science 25

Seven biplots, where each biplot compares throughput (in units of 100 segments per second) for la

over very fast paths with fast interface speeds using a proposed TCP replacement (x axis) with throcompeting flows using standard TCP – here a high initial slow-start threshold is used 

Under these Scalable TCHSTCP apphigher throthe expense flows
6 Colored Bar Graphs

July 18‐19, 2011

Innovations in Measurement Science 26

Fraction (y axis) of maximum available throughput achieved when transferring movies over uncongmaximum rate of 1 Gbps – each of the leftmost seven bars – y2(u) – represents flows using one of treplacements for TCP (see legend), while each of the rightmost seven bars – y16(u) – represents floand competing with flows using one of the proposed TCP replacements (see legend) – here a low inthreshold is used. 

Legend

FAST & FAST-AT provide best throughput, while CTCP provides s

Note that TCP flows achieve only 20 throughput, as was measured empiriresearchers
7 Rank Analyses

July 18‐19, 2011

Innovations in Measurement Science 27

Average throughput rank (x axis) vs. standard deviation in throughput rank (y axis) for flows using ereplacement and for competing flows using standard TCP

CTCP leads high ranking throughputs under a wide range of c

0

0.20.40.60.8

1

1.21.4

3 3.5 4 4.5 5

HTCPCTCP

FAST-AT

Average Throughput Rank for All Flows

Standard Deviation in Throughput Rank for All Flows FAST HSTCP BIC SCALABLE 0 0.2 0.4 0.6 0.81 1.2 1.4 1.6

3 3.5 4 

HTCP

Average Throughput Rank 

Standard Deviation in Throughput Rank for All Flows F

HSTCP BIC SCALABLE

low initial slow-star

high initial slow-start threshold 
Application to Predict Macroscopic Dyna

Proposed TCP Replacements

July 18‐19, 2011

Innovations in Measurement Science 28
Experiments Conducted

July 18‐19, 2011

Innovations in Measurement Science 29

How do the proposed TCP replacements react toand recover from spatiotemporal congestion?Experiment #1a

Compared seven proposedTCP replacements (excludedFAST-AT) in a large (up to278,000 sources), fast (up to192 Gbps backbone) network;Web browsing users; 25minutes simulated; three 5-minute time periods; large (> 1billion segments) initial sst; allsources use the samecongestion control algorithm

Experiment #1b

Same as #1a, except; smaller(up to 27,800 sources) andslower (up to 28.8 Gpbsbackbone) network and low

(100 segments) initial sst.

(Added FAST-AT)

How do the proposed TCP replacemthroughputs and affect competing TExperiment #2a

Compared eight replacements in 

26,085 sources), Gpbs backbone) 

browsing users users who downlmovies; 60 minute

(> 1 billion segmsome sources ucongestion controsome sources proposed TCP rep

Experiment #2b Same as #2a ex

segments) initial s

Experiment #2c

Same as #2a exceto 261,792 sources384 Gbps backbon
What distinguishes among proposed TCP replac

Will they be useful? Will they be safe?

July 18‐19, 2011

Innovations in Measurement Science 30

1. Increase rate: How quickly can the maximum transmission rate be a

2. Loss/Recovery processing:

a. How much does the protocol reduce transmission rate upon a l

b. How quickly does the protocol increase transmission rate after 

reduction?

3. TCP Fairness: How well do standard TCP flows do when competing w

proposed TCP replacements?

4. Utility bounds: Under what circumstances can proposed TCP replace

provide improved user throughputs?

5. Safety: Will widespread deployment of proposed TCP replacements 

undesirable macroscopic dynamics into the Internet?
Increase Rate

July 18‐19, 2011

Innovations in Measurement Science 31

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

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

transmission rate with the same (exponential) quickness

 Low initial sst – proposed TCP replacements achieved maximum transmissio

more quickly than (linear) increase of standard TCP

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

slow start terminates upon first packet loss and a flow enters congestion

avoidance, where loss/recovery processing determines throughput

3⁄4 On real TCP flows receivers may convey a window (rwnd) that can restric

throughput because sources pace transmission based on min(cwnd, rwn

Typically, rwnd < cwnd. In our studies, we assume an infinite rwnd in

order to compare effects of congestion control algorithms. Throughput oTCP flows in a real network might be constrained by rwnd, so that propo

replacements would provide little advantage over standard TCP.

In fact, even TCP congestion control does not have much influence when

rwnd < cwnd.
Loss/Recovery Processing

July 18‐19, 2011

Innovations in Measurement Science 32

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

rate less than standard TCP after a packet loss

 Unfair to TCP flows and to new flows using alternate algorithms

3⁄4 Another group of algorithms (CTCP, FAST and FAST‐AT) reduce transmissi

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

 These algorithms seek to obtain higher throughput by increasing transmissio

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

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

can lead to lower throughputs than other alternate algorithms

3⁄4 Under extreme spatiotemporal congestion, most proposed TCP replacem

a low‐window threshold and revert to standard TCP congestion avoidanc

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 rates

1Note that on repeated losses occurring close in time, BIC can reduce cwnd substantially more th

standard TCP – thus, on paths with very severe congestion TCP can provide higher throughput t
TCP Fairness

July 18‐19, 2011

Innovations in Measurement Science 33

3⁄4 All proposed TCP replacements take steps to provide improved throughp

thus comparing fairness must consider relative performance of TCP flows 

competing with flows using each proposed replacement

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 increase in ra

 Injecting more FAST‐AT packets induced more losses in TCP flows, which cou

recover only linearly

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

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

transmission rates than TCP flows after losses, while FAST recovered more qu

and these proposed TCP replacements induced more losses in TCP flows

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

lower congestion and under low initial sst – HSTCP appeared unfair unde

conditions of heavy congestion

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

flows that are newly arriving
Utility Bounds

July 18‐19, 2011

Innovations in Measurement Science 34

3⁄4 We found that proposed TCP replacements could provide increased

utility (throughput) for users – however, this utility would arise only und

a specific combination of 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., experie

only sporadic losses) or else users must be willing to tolerate marked unfair

in trade for increased throughput

3⁄4 How likely is this combination of circumstances on a given Internet flow

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

specific users with improved throughput compared with TCP

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

in the Internet

3⁄4 We conclude that proposed TCP replacements can provide improved

user throughput – however, most users seem unlikely to benefit very oft
Safety

July 18‐19, 2011

Innovations in Measurement Science 35

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

 We simulated either homogeneous networks where all flows used one

congestion control algorithm or mixes of TCP flows competing with flows

using one proposed TCP replacement at a time

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

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

significant change in macroscopic network characteristics

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

 Under high spatiotemporal congestion, where there were insufficient buffer

support flows transiting specific routers, FAST and FAST‐AT entered an oscill

behavior where the flow cwnd increased and decreased rapidly with large

amplitude

 Under such conditions the network showed increased loss and retransmissi

a higher number of flows pending in the connecting state and a lower numb

of flows completed over time

3⁄4 We recommend the need for additional study of FAST and FAST‐AT prior 

widespread deployment and use on the Internet