March 10, 2009

Innovations in Measurement Science

1

Measurement Science for Complex Information Systems

Measurement Science for Measurement Science for 

Complex Information System

Complex Information System

D. Cho, C. Dabrowski, J. D. Cho, C. Dabrowski, J. Filliben Filliben, J. Hage

Hage

Houard, F. Hunt, D. , F. Hunt, D. Genin, V. Marbukh Marbukh an

and various students and various students

Innovations in Measurement Science Innovations in Measurement Science 
March 10, 2009

Innovations in Measurement Science

2

Measurement Science for Complex Information Systems

Plan for Presentation

• Introduce NIST project to develop Measuremen

Science for Complex Information Systems

• Show an application of measurement science to 

compare seven alternate congestion-control algfor the Internet
March 10, 2009

Innovations in Measurement Science

3

Measurement Science for Complex Information Systems

What are complex systems?

Large collections of interconnected components 

interactions lead to macroscopic behaviors

http://autoinfo.smartlink.net/quake/quake.htm

http://www.sover.net/~kenandeb/fire/hotshot.html

http://www.avalanche.org/

– Physical systems (e.g., earthquakes, avalanches, forest fir

© http://www.nationalgeographic.com/

©http://emergent.brynmawr.edu 2003

– Biological systems (e.g., slime molds, ant colonies, embryo

http://www.wtopnews.com/

http://www.english.uiuc.edu/maps/depression/photoessay.htm

©http://www.waag.org/realtime/

– Social systems (e.g., transportation networks, cities, econo– Information systems (e.g., Internet, Web services, compute 
March 10, 2009

Innovations in Measurement Science

4

Measurement Science for Complex Information Systems

What is the problem? 

No one understands how to measure, predict or cmacroscopic behavior in complex information sys

“[Despite] society’s profound dependence on networks, fundknowledge about them is primitive. [G]lobal communication networks have quite advanced technological implementationtheir behavior under stress still cannot be predicted reliably.is no science today that offers the fundamental knowledge nto design large complex networks [so] that their behaviors cpredicted prior to building them.”— Network Science, NRC report released in 2006 
March 10, 2009

Innovations in Measurement Science

5

Measurement Science for Complex Information Systems

Technical Approach

• Evaluate models and analysis methods 

– Computationally tractable?– Reveal macroscopic behavior?– Establish causality?

• Evaluate distributed control techniques

– Can economic mechanisms elicit desired behaviors?– Can biological mechanisms organize elements?

Leverage models and mathematics from the phys

sciences to define a systematic method to measurunderstand and control macroscopic behavior in the Internet and distributed software systems built on the Internet

Inte

Distribu

Scheduler

Task

Control

Negotiation

Control

Grid Processor 

DSI

Service 

Negotiator

Agreement

Execution 

Control

CLIE

Application

Task 1

D

C

Task 2

Grid Processor

DSI

Service 

Negotiator

Agreeme

Task 3

DRMS 

Front-End

DRMS 

Front-End

DSF

spawns

monitors

monitors

spaw

Supervisory Process 

ProviderSite

Scheduler

Task

Control

Negotiation

Control

Grid Processor 

DSI

Service 

Negotiator

Agreement

Execution 

Control

CLIE

Application

Task 1

D

C

Task 2

Grid Processor

DSI

Service 

Negotiator

Agreeme

Task 3

DRMS 

Front-End

DRMS 

Front-End

DSF

spawns

monitors

monitors

spaw

Supervisory Process 

ProviderSite

What is the new idea?
March 10, 2009

Innovations in Measurement Science

6

Measurement Science for Complex Information Systems

Why is this hard? Why can we succ

H5. Controlling behavior A5. Evaluate distributed control reH4. Causal analysis A4. Evaluate analysis techniquesH3. Tractable analysis A3. Cluster analysis and statisticaH2. Model validation A2. Sensitivity analysis & key comH1. Model scale A1. Scale-reduction techniques

Hard Issues Plausible Approaches

Project Start Date: October 2006 
March 10, 2009

Innovations in Measurement Science

7

Measurement Science for Complex Information Systems

Multidisciplinary Project 

V. Marbukh

F. Hunt K. Mills

D. Genin C. Dabrowski

Analytical Simulation

Modeling Methods

J. Filliben

Experiment Design Methods

D. Y. Cho

J. Filliben

Data Analysis Methods

C. Houard

J. Hagedorn

Visualization Methods

Disciplinary Expertise Problem Domains

A

B

D

C

F

G

H

I

K

J

A1

A2

A1a

A1b

A1cA1d

A1e

E

A2b

A1f A2g

A2a

B0a

B1

B1b

B2g

B2f

B1a

B2

B2a

B2bB2c

B2d

B2e D1

D1b

D2g

F1d

D1a

D2

D2a

D2b

D2c D2d

D2e

C1

C1a

C1b

C1c C1d

C1e

C2

C1f

C2f

C2e

C2d C2c

C2b

C2a E1

E1b

C2g

E2f

E1a

E2a E2

E2b

E2c

E2d E2e

G1b

G1c G1dG1e

G2e

G2c

G2b

G2a

C1G

G1a

G1f

G2

G2d

G2f

F0a

F1

F1bF1a

F1c

F2

F2a

F2b F2c F2d

F2e

H2

H2aH2b

H2c H2d

H2e

H1

H1b

H2g

H1a

F2f

J1

J1e

J1c J1d

J1b

J1a

J1f

J2

J2a

J2f

J2b

J2c

J2d

J2e

I0a

I1c

I1b

I1a

I1

I1d

I2

I2c

I2a I2b

I2d

K1

K1b

J2g

K1a

I2f

K2

K2b

G2g

H2f

K2a

I2e

D2f

E0a

K0a

J1g

I1e I1f

G1g

I1g

I2g

F2g

C1g E2g

F1g

F1e F1f

A2d

A2c

B1c

B1d

D1c D1d

H1c

E1c E1d

H1d

K1d

K1c

K2d K2c

C0a

Internet

Prob

MesoscoFluid-FloMarkov PerturbaMean-FiOrthogoFactoriaSensitivClusteriPrincipaAnalysisCorrelatMultidimVisualiza

Computational Grids
March 10, 2009

Innovations in Measurement Science

8

Measurement Science for Complex Information Systems

Challenge Problem: Study of Proposed Replace

Congestion-Control Algorithms for the Intern

• Modeling the network

– Parameter state-space reduction techniques– Response state-space reduction techniques– Orthogonal fractional-factorial experiment design– Sensitivity analysis

• Modeling congestion-control algorithms

– Unified model with phase and procedure alignment– Validation against empirical measurements

• Comparing congestion-control algorithms

– Cluster analysis– Detailed analysis of individual responses– Condition-response summary analysis– Causality analysis – through domain expertise
March 10, 2009

Innovations in Measurement Science

9

Measurement Science for Complex Information Systems

The Modeling State-Space Proble

y1, ..., ym = f(k.x1, ..., k.xn)

Response State‐Space Stimulus State‐Space

n Number of inputs (i.e., stimulus factors)k Factor range (i.e., number of values each factor can assumm Number of outputs (i.e., responses)
March 10, 2009

Innovations in Measurement Science

10

Measurement Science for Complex Information Systems

Parameter State-Space Reduction: MesoNet 

(232)1000

220

28

k = 2

r1 = 944

O(109633) [ 1080 = atoms in visible universe

(232)56 O(10539)

(232)20 r2 = 36 O(10192)

O(106)

r3 = 12 

Kevin

Jim

(232)1000

220

28

k = 2

r1 = 944

O(109633) [ 1080 = atoms in visible universe

(232)56 O(10539)

(232)20 r2 = 36 O(10192)

O(106)

r3 = 12 

(232)1000

220

28

k = 2

r1 = 944

O(109633) [ 1080 = atoms in visible universe

(232)56 O(10539)

(232)20 r2 = 36 O(10192)

O(106)

r3 = 12 

Kevin

Jim
March 10, 2009

Innovations in Measurement Science

11

Measurement Science for Complex Information Systems

220-12 OFF Design Improves Computational Feas

Searching Parameter State Space

Assumptions

Processing Time for One Run 8 CPU‐HoursNumber of Available CPUs 48

Assumptions

Processing Time for One Run 8 CPU‐HoursNumber of Available CPUs 48

(220 runs x 8 CPU‐Hours Per Run)/48 CPUs = 174,762.67 Ho

2‐Level Experiment Design Requires 20 Years

OFF Experiment Design Reduces Requirement To Und

(28 runs x 8 CPU‐Hours Per Run)/48 CPUs = 42.67 Hour

*If we had 1,000 CPUs to dedicate to this problem, then we could compute the 220 runs in just under 
March 10, 2009

Innovations in Measurement Science

12

Measurement Science for Complex Information Systems

Response State-Space Reductio

m responses (y1, ... ym)

Principal

Components

Analysis

m – d1 responses

Correlation

Analysis

m – d2 responses

Domain

Expertise

m – d3

responses

SCIENTIFIC

DOMAIN

EXPERTISE

DATA

ANALYSIS

EXPERTISE

m responses (y1, ... ym)

Principal

Components

Analysis

m – d1 responses

Correlation

Analysis

m – d2 responses

Domain

Expertise

m – d3

responses

m responses (y1, ... ym)

Principal

Components

Analysis

m – d1 responses

Correlation

Analysis

m – d2 responses

Domain

Expertise

m – d3

responses

SCIENTIFIC

DOMAIN

EXPERTISE

DATA

ANALYSIS

EXPERTISE
March 10, 2009

Innovations in Measurement Science

13

Measurement Science for Complex Information Systems

22-Dimension Response State Space from M

Macroscopic

Network

Behavior

User

Experience
March 10, 2009

Innovations in Measurement Science

14

Measurement Science for Complex Information Systems

Correlation Analysis Identifies 7 Dimens

Fl

Congestion

Flow Throughput

Advantaged Flows

Delay

Aggregate

Packet

Throughput

Flow Throughput

Very Advantaged Flows

Aggregate Rate of

Flow Completions

Fl

Congestion

Flow Throughput

Advantaged Flows

Delay

Aggregate

Packet

Throughput

Flow Throughput

Very Advantaged Flows

Aggregate Rate of

Flow Completions
March 10, 2009

Innovations in Measurement Science

15

Measurement Science for Complex Information Systems

Principal Components Analysis Suggests 4 D

PC1 – Congestion

PC3 – Throughput for Advantaged Flows

PC2 – Delay

PC4 – Aggregate Through
March 10, 2009

Innovations in Measurement Science

16

Measurement Science for Complex Information Systems

Sensitivity Analysis as a Model Validation 

What parameters (or combinations of parametdetermine a model’s responses?Does the influence of parameters on responsemake sense to a domain expert?

Can any unexpected responses be explained do the explanations make sense?
March 10, 2009

Innovations in Measurement Science

17

Measurement Science for Complex Information Systems

11 of 20 MesoNet Parameters Selected for Sensitivi

* seleother 

Network Parameters

Topology

Propagation Delay

Speed

Buffer Sizing

Network Parameters

Topology

Propagation Delay

Speed

Buffer Sizing

Simulation Control

Measurement‐Interval Size

Number of Measurement Interva

Random‐Number Seed

Simulation Control

Measurement‐Interval Size

Number of Measurement Interva

Random‐Number Seed

User Behavior

Think Time

File‐Size Distribution

Pattern of Long‐Lived Flows

User Behavior

Think Time

File‐Size Distribution

Pattern of Long‐Lived Flows

Protocol Parameters

Initial Congestion Window

Initial Slow‐Start Threshold

Type of Slow Start Regime

Protocol Parameters

Initial Congestion Window

Initial Slow‐Start Threshold

Type of Slow Start Regime

Characteristics of Sources & Receivers

Number of Sources

Distribution of Sources

Number of Receivers

Distribution of Receivers

Distribution of Network‐Interface Speeds

Distribution of Congestion‐Control Mechanisms

Startup Pattern for Sources

Characteristics of Sources & Receivers

Number of Sources

Distribution of Sources

Number of Receivers

Distribution of Receivers

Distribution of Network‐Interface Speeds

Distribution of Congestion‐Control Mechanisms

Startup Pattern for Sources

***

*****

*

**None

Next slide

22

2 pLim

All TCP25% at a time
March 10, 2009

Innovations in Measurement Science

18

Measurement Science for Complex Information Systems

Representative Heterogeneous Four-Tier Topology 

Fast access routers

Directly-connected access routers

Normal access ro
March 10, 2009

Innovations in Measurement Science

19

Measurement Science for Complex Information Systems

211-5 Orthogonal Fraction Factorial (OFF) Experime

Design Template

Full Factorial Design Requires 211 = 

We can only afford 26 = 64 runs; thu

we require a 211-5 OFF Experiment 

No confounding of main effects with interactions Main effects may be confounded wiand higher interactions 
March 10, 2009

Innovations in Measurement Science

20

Measurement Science for Complex Information Systems

Values Selected to Replace +1 and -1 in Design T

Initial Slow-Start Threshold (packets)

Distribution of Receivers

Distribution of Sources

Multiplier on Number Sources Per 

Access Router

Probability of Fast Network Interface*

Probability of a Larger File*

Average Think Time (ms)

Average File Size (packets)

Buffer Sizing Algorithm

Backbone Router Speed (ppms)*

Multiplier for Propagation Delay

Parameter

1.07x10 43 9 x11 Protocol Factors

x10 P2P WEB

x9 P2P WEBx8 3 2x7 0.2 0.4

Source 

& 

Receiver Factors

x6 0.01 0.02x5 5000 2000x4 100 50

UserFactors

x3 RTTxC RTTxC/SQR(n)x2 400 800x1 2 1

NetworkFactors

Factor +1 -1

*By convention +1 is coded with larger value and -1 is coded with smaller value. Here, coding was reversed in th

This makes no difference in the construction of the experiment, but must be managed during data analysis
March 10, 2009

Innovations in Measurement Science

21

Measurement Science for Complex Information Systems

Speed of All Routers Derived from Speed of Backbo

(Topology Tiers 1 to 3)

= x2/R2/R4xDC= x2/R2/R4xFA= x2/R2/R4= x2/R2= x2

Equation

DC (= 10)FA (= 2)R3 (= 10)R2 (= 4)x2

Parameter

Directly Connected Access 100 ppms 200 ppmsFast Access 20 ppms 40 ppms

Typical Access 10 ppms 20 ppmsPOP 100 ppms 200 ppmsBackbone 400 ppms 800 ppmsRouter Type +1 -1
March 10, 2009

Innovations in Measurement Science

22

Measurement Science for Complex Information Systems

Number & Distribution of Sources & Receivers (

3 WEB P2P 27,840 6.46 48.27 45.25

2 WEB P2P 18,560 6.46 48.27 45.25

3 P2P WEB 41,700 4.32 20.14 75.54

2 P2P WEB 27,800 4.32 20.14 75.54

3 WEB WEB 27,840 6.46 48.27 45.25

2 WEB WEB 18,560 6.46 48.27 45.253 P2P P2P 41,700 4.32 20.14 75.542 P2P P2P 27,800 4.32 20.14 75.54

% under

N Routers

% under

F Routers

% under

D Routers

Total

Sources x8 x9 x10

Sources

3 WEB P2P 166,800 4.32 20.14 75.542 WEB P2P 111,200 4.32 20.14 75.54

3 P2P WEB 219,600 2.45 11.47 86.06

2 P2P WEB 146,400 2.45 11.47 86.06

3 WEB WEB 219,600 2.45 11.47 86.062 WEB WEB 146,400 2.45 11.47 86.06

3 P2P P2P 166,800 4.32 20.14 75.54

2 P2P P2P 111,200 4.32 20.14 75.54

% under

N Routers

% under

F Routers

% under

D Routers

Total 

Receivers x8 x9 x10

Receivers
March 10, 2009

Innovations in Measurement Science

23

Measurement Science for Complex Information Systems

Resulting Distribution of Flow Classes

Flow classes defined by relative locations of source 

3 WEB P2P 0.279 3.38 6.83 9.72 45.58 34.182 WEB P2P 0.279 3.38 6.83 9.72 45.58 34.18

3 P2P WEB 0.106 0.99 5.57 2.31 26.00 65.01

2 P2P WEB 0.106 0.99 5.57 2.31 26.00 65.01

3 WEB WEB 0.159 1.92 6.67 5.53 46.74 38.95

2 WEB WEB 0.159 1.92 6.67 5.53 46.74 38.95

3 P2P P2P 0.186 1.74 6.52 4.05 30.43 57.06

2 P2P P2P 0.186 1.74 6.52 4.05 30.43 57.06

% NN

Flows

% FN

Flows

% FF

Flows

% DN

Flows

% DF

Flows

% DD

Flows x8 x9 x10
March 10, 2009

Innovations in Measurement Science

24

Measurement Science for Complex Information Systems

Influence of other Factors on Average Buffer S

2 800 65106 16277 2588

1 800 32553 8139 12942 400 32553 8139 12941 400 16277 4070 647

Access Router

Buffers (avg.)

POP Router

Buffers (avg.)

Backbone 

Router Buffers 

(avg.)

x1 x2

RTTxC

2 800 728 270 1051 800 364 135 532 400 364 135 53

1 400 182 68 27

Access Router

Buffers (avg.)

POP Router

Buffers (avg.)

Backbone 

Router Buffers 

(avg.)

x1 x2

RTTxC/

SQR(n)
March 10, 2009

Innovations in Measurement Science

25

Measurement Science for Complex Information Systems

Sensitivity Analysis Relies on Main Effects P
March 10, 2009

Innovations in Measurement Science

26

Measurement Science for Complex Information Systems

Sensitivity Analysis Driven by Correlation Ana

Active Flows Retransmission 

Rate

Avg. TP NN Flows 

Aggregate TP Flow Completion Rate Avg. TP DD Flows 

Seven Responses Chosen by Correlation Analysis + 
March 10, 2009

Innovations in Measurement Science

27

Measurement Science for Complex Information Systems

Optional mode switch betwalternate procedures:

BIC, CTCP, HSTCP, H-TC

time Current time

synTO Timeout for current SYN

syn Number of SYNs that have been sent SENT

synMAX Maximum number of SYNs to send

synINT Timeout interval for initial SYN

Symbol Definition

time Current time

synTO Timeout for current SYN

syn Number of SYNs that have been sent SENT

synMAX Maximum number of SYNs to send

synINT Timeout interval for initial SYN

Symbol Definition

Threshold to terminate initial slow start (varies

with experiment) sstINT

Threshold to switch from exponential to

logarithmic increase (varies with experiment) sstMAX

sst Current slow‐start threshold

Initial congestion window (we use cwndINT cwnd = 2) INT

cwnd Current congestion windowSymbol Definition

Threshold to terminate initial slow start (varies

with experiment) sstINT

Threshold to switch from exponential to

logarithmic increase (varies with experiment) sstMAX

sst Current slow‐start threshold

Initial congestion window (we use cwndINT cwnd = 2) INT

cwnd Current congestion windowSymbol Definition

Window increase proceduWindow decrease proceduTimeout proceduresOptional periodic procedur

CTCP, FAST, H-TCP

Standard or Limited

MS Windows® TCP

Unified Model for Congestion-Control Algorith
March 10, 2009

Innovations in Measurement Science

28

Measurement Science for Complex Information Systems

Sample: CTCP Congestion-Avoidance Mod

SRTTC Average Smoothed Round‐Trip Time experienced on CTCP flow

minRTTC Minimum round‐trip time experienced on CTCP flow

Low‐window threshold ( LWC LW = 41) for applying CTCP procedures CExponent (kC k = 0.8) for CTCP window‐increase procedures CCTCP zeta parameter (C C = 0.1) defining reduction speed in delay windowExpected throughput (cwnd/minRTTC EC ) on CTCP flow

dwnd CTCP delay windowDC Difference between expected and actual throughput experienced on CTCP flow

CTCP gamma threshold (C  = 30) for detecting early congestion C

CD Boolean denoting whether early congestion has been detected (true) or not (false) C

Window decrease (C  = 0.5) weight for CTCP CActual throughput (cwnd/SRTTC AC ) experienced on CTCP flowWindow increase (C  = 0.125) weight for CTCP C

Symbol Definition

SRTTC Average Smoothed Round‐Trip Time experienced on CTCP flow

minRTTC Minimum round‐trip time experienced on CTCP flow

Low‐window threshold ( LWC LW = 41) for applying CTCP procedures CExponent (kC k = 0.8) for CTCP window‐increase procedures CCTCP zeta parameter (C C = 0.1) defining reduction speed in delay windowExpected throughput (cwnd/minRTTC EC ) on CTCP flow

dwnd CTCP delay windowDC Difference between expected and actual throughput experienced on CTCP flow

CTCP gamma threshold (C  = 30) for detecting early congestion C

CD Boolean denoting whether early congestion has been detected (true) or not (false) C

Window decrease (C  = 0.5) weight for CTCP CActual throughput (cwnd/SRTTC AC ) experienced on CTCP flowWindow increase (C  = 0.125) weight for CTCP C

Symbol Definition

Mode Switch Procedures

Periodic Procedures

IncreaseProceduresDecreaseProceduresTimeoutProcedures
March 10, 2009

Innovations in Measurement Science

29

Measurement Science for Complex Information Systems

Flow 1 Flow 1Flow 2 Flow 2

PATH

PARAMETERS

• Number of flow• Start time of ea• Bottleneck band• Round-trip prop• Number of buffe

1. Yee-Ting, Leith and Shorten, “Experimental Evaluation of TCP 

Protocols for High-Speed Networks”, IEEE/ACM Transactions on 

Networking, (15)5, October 2007, pp. 1109 – 1122.

– Covers BIC, FAST, HSTCP, H-TCP, Scalable TCP

– Uses implementations within Linux kernel

2. Leith, Andrew, Quetchenbach, Shorten and Lavi, “Experimental 

Evaluation of Delay/Loss-based TCP Congestion Control Algorithms”, Proceedings of the 6th International Workshop on 

Protocols for Fast Long-Distance Networks (PFLDnet 2008), March 5-7,2008, Manchester, UK.

– Covers CTCP and TCP Illinois

– Uses CTCP implementation in Windows® VISTA and TCP Illinois 

implementation within Linux kernel

Empirical Studies of Six Alternate Congestion-Contro
March 10, 2009

Innovations in Measurement Science

30

Measurement Science for Complex Information Systems

Simulated Behavior of MesoNet CTCP Mod

0 1000 2000 3000 4000 5000 6000 7000 8000 9000 1 .104

0

100200300400500600700800900

100011001200

Time

Congestion Window

avg. cwnd = 798 avg. cwnd = 836

avg. red cwnd = 419avg. blue cwnd = 417

0 1000 2000 3000 4000 5000 6000 7000 8000 9000 1 .104

0

100200300400500600700800900

100011001200

Time

Congestion Window

avg. cwnd = 798 avg. cwnd = 836

avg. red cwnd = 419avg. blue cwnd = 417

0 1000 2000 3000 4000 5000 6000 7000 8000 9000 1 .104

0

500

10001500200025003000350040004500

Time

Congestion W indow

avg. cwnd = 2745 avg. cwnd = 3406

avg. red cwnd = 1853avg. blue cwnd = 1553

0 1000 2000 3000 4000 5000 6000 7000 8000 9000 1 .104

0

500

10001500200025003000350040004500

Time

Congestion W indow

avg. cwnd = 2745 avg. cwnd = 3406

avg. red cwnd = 1853avg. blue cwnd = 1553

rtt = 162 msrtt = 42 ms

0 1000 2000 3000 4000 5000 6000 

0

100020003000400050006000700080009000

Time

Congestion Window

avg. cwnd = 4325 

avg. avg. 

0 1000 2000 3000 4000 5000 6000 

0

100020003000400050006000700080009000

Time

Congestion Window

avg. cwnd = 4325 

avg. avg. 

rtt = 324 ms

MesoNet CTCP simulatioagrees with empirical resuOther MesoNet congestioalgorithms also agree with results
March 10, 2009

Innovations in Measurement Science

31

Measurement Science for Complex Information Systems

Comparing Alternate Congestion-Control Algorith

Large (up to 278,000 sources), Fast (up 192 Gbps) Homogeneou

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

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

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

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

NN Source & receiver under normal access router

Source or receiver under fast access router and correspondent under normal access router FNSource or receiver under directly connected access routand correspondent under normal access router DN

Typical

FF Source & receiver under fast access router

Source or receiver under directly connected access routand correspondent under fast access router DF Fast

Very Fast DD Source & receiver under directly connected access route

Path Class Flow Type Definition

NN Source & receiver under normal access router

Source or receiver under fast access router and correspondent under normal access router FNSource or receiver under directly connected access routand correspondent under normal access router DN

Typical

FF Source & receiver under fast access router

Source or receiver under directly connected access routand correspondent under fast access router DF Fast

Very Fast DD Source & receiver under directly connected access route

Path Class Flow Type Definition

7 Algorithms

3 Path Classes
March 10, 2009

Innovations in Measurement Science

32

Measurement Science for Complex Information Systems

Simulation Scenario & Long-Lived Flows

F0a

I0a

K0a

Receiver Router

L3 Short-distance flow E0a 0.4 x 2

L2 Medium-distance flow C0a 0.4 x 2L1 Long-distance flow B0a 0.4 x 2

Identifier Definition Source Router Start 

F0a

I0a

K0a

Receiver Router

L3 Short-distance flow E0a 0.4 x 2

L2 Medium-distance flow C0a 0.4 x 2L1 Long-distance flow B0a 0.4 x 2

Identifier Definition Source Router Start 

Long-Lived Flows

Scenario
March 10, 2009

Innovations in Measurement Science

33

Measurement Science for Complex Information Systems

Characterizing the 32 Conditions Simulate

0

0.10.20.30.40.50.6

12 8 20 2 32 26 3 14 4 15 27 9 16 10 28 11 18 24 22 19 17 6 1 29 7 30 5 25 23 13 31 21

Condition

Retransmission Rate

0

0.00020.00040.00060.0008

0.001

0.00120.00140.00160.0018

0.002

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

Condition

Retransmission Rate

Max. = 0.0018

N L M

C

0

0.10.20.30.40.50.6

12 8 20 2 32 26 3 14 4 15 27 9 16 10 28 11 18 24 22 19 17 6 1 29 7 30 5 25 23 13 31 21

Condition

Retransmission Rate

0

0.00020.00040.00060.0008

0.001

0.00120.00140.00160.0018

0.002

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

Condition

Retransmission Rate

Max. = 0.0018

0

0.10.20.30.40.50.6

12 8 20 2 32 26 3 14 4 15 27 9 16 10 28 11 18 24 22 19 17 6 1 29 7 30 5 25 23 13 31 21

Condition

Retransmission Rate

0

0.00020.00040.00060.0008

0.001

0.00120.00140.00160.0018

0.002

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

Condition

Retransmission Rate

Max. = 0.0018

N L M

C

16 Uncongested and 16 Congested Conditions

3000 3500 4000 4500 5000 5500 6000 6500 7000 7500

0

10002000300040005000600070008000

Evolution of Flows Condition 4 - TCP

Time

Active Flows

Sending Flows

Normal Congestion Control

Connecting Flows

Flows in Initial Slow Start 

3000 3500 4000 4500 5000 5500 6000 6500 7000 7500

0

10002000300040005000600070008000

Evolution of Flows Condition 4 - TCP

Time

Active Flows

Sending Flows

Normal Congestion Control

Connecting Flows

Flows in Initial Slow Start 

Evolution of Flow States in Uncongested Condition 4

3000 3500 4000 4500 5000 5500 6000 

0

2 .104

4 .1046 .1048 .1041 .105

1.2 .1051.4 .105

Evolution of Flows Condition 5 - TCP

Time

Active Flows

Sending Flows

Normal Congest

Connecting Flows

Flows in Initial Sl

3000 3500 4000 4500 5000 5500 6000 

0

2 .104

4 .1046 .1048 .1041 .105

1.2 .1051.4 .105

Evolution of Flows Condition 5 - TCP

Time

Active Flows

Sending Flows

Normal Congest

Connecting Flows

Flows in Initial Sl

Evolution of Flow States in Congeste

Cluster Analysis Annotated with Conge
March 10, 2009

Innovations in Measurement Science

34

Measurement Science for Complex Information Systems

Cluster Analyses – Algorithm 3 (FAST) Stands 

Time Period 1 Time Period 2

Time Period 3 Aggregate Responses over 25 minu
March 10, 2009

Innovations in Measurement Science

35

Measurement Science for Complex Information Systems

Approach to Detailed Analysis of Individual Resp

Time Period 1Retransmission Rate
March 10, 2009

Innovations in Measurement Science

36

Measurement Science for Complex Information Systems

Approach to Summarizing Detailed Analyses of Re

Condition-Response Summary Time Period 1Statistically significant and >10% Effect Filter
March 10, 2009

Innovations in Measurement Science

37

Measurement Science for Complex Information Systems

Condition-Response Summaries – Algorithm 3 (FAST

Time Period 1 – 10% Filter Time Period 2 – 30% Filt

Time Period 3 – 30% Filter Aggregate Responses – No Filte
March 10, 2009

Innovations in Measurement Science

38

Measurement Science for Complex Information Systems

Why does Algorithm 3 (FAST) Stand Out?

FAST does not respond well to congestion, where too many flows cofor insufficient buffers – leading to rapid oscillation in flow congestion 

0

50

100150200250300350

4600 4700 4800 4900 5000 5100

Time

CWND

Evolution of congestion window under FAST for long-lived flow L2 during 

500 measurement intervals within Time Period 2 under (the most congested) condition 21
March 10, 2009

Innovations in Measurement Science

39

Measurement Science for Complex Information Systems

Other Congestion-Control Algorithms Adjust Less 

Evolution of congestion window under other congestion-control algorithms for long-lived flow L2 du

500 measurement intervals within Time Period 2 under (the most congested) condition 2

0

50

100150200250300350

4600 4700 4800 4900 5000 5100

Time

CWND

0

50

100150200250300350

4600 4700 4800 4900 5000 5100

Time

CWND

TCP Reno BIC

0

50

100150200250300350

4600 4700 4

CWND

0

50

100150200250300350

4600 4700 4800 4900 5000 5100

Time

CWND

HSTCP

0

50

100150200250300350

4600 4700 4800 4900 5000 5100

Time

CWND

HTCP

0

50

100150200250300350

4600 4700 

CWND
March 10, 2009

Innovations in Measurement Science

40

Measurement Science for Complex Information Systems

Summary of FAST Behavior under Con

• Rapid oscillatory adjustment of congestion wind

leads to:

– Larger congestion-window increase rate– Higher retransmission rate (including for SYNs)– Larger number of flows pending in the connecting sta

• Practical implications include:

– Flows take longer to connect– Flows take longer to complete– Goodput is lower for flows transiting congested areas– Fewer (105 to 107, depending on condition) flows complete in 

minute period
March 10, 2009

Innovations in Measurement Science

41

Measurement Science for Complex Information Systems

Future Work on Congestion-Control Alg

• Does MesoNet reveal the same behavior when 

modeling a smaller, slower network with a much initial slow-start threshold?

• How do the congestion-control algorithms comp

relatively uncongested, heterogeneous network wider range of traffic classes (e.g., web objectsdocuments, service packs and movie download

• Does the sensitivity analysis change when cons

all 20 MesoNet parameters? 
March 10, 2009

Innovations in Measurement Science

42

Measurement Science for Complex Information Systems

Summary of Presentation

• Introduced NIST project to develop Measureme

Science for Complex Information Systems

• Showed an application of measurement science 

compare seven alternate congestion-control algfor the Internet

• Identified a potential for FAST algorithm to beha

undesirably under congested conditions

– Explained the root cause for the potential undesirable – Explained why other congestion-control algorithms ar

likely to exhibit the same potential undesirable behav
March 10, 2009

Innovations in Measurement Science

43

Measurement Science for Complex Information Systems

Additional Information on the Proj
March 10, 2009

Innovations in Measurement Science

44

Measurement Science for Complex Information Systems

Previous NIST Groundwork (2000-20

Complex Dynamics in Communications Networks, Dec

(including Macroscopic Dynamics in Large-Scale Data Networks by Yu

Yuan and Mills, A Cross-Correlation-based Method forSpatial-Temporal Traffic Analysis, July 2005

Yuan and Mills, Monitoring the Macroscopic Effects of DDenial of Service (DDoS) Flooding Attacks, October 20Yuan and Mills, Simulating Timescale Dynamics of NetTraffic Using Homogeneous Modeling, May-June 2006

Preliminary investigation to identify hard technic
March 10, 2009

Innovations in Measurement Science

45

Measurement Science for Complex Information Systems

Sample Artifacts Produced by the Pr

MesoNet – a medium scale network simulator that includes 

congestion control algorithms: BIC, CTCP, FASTH-TCP, Scalable TCP and TCP Reno

EconoGrid – a detailed simulation model of a standards-ba

compute economy

Flexi-Cluster – a flexible simulation model of a compute clu

includes alternate, replaceable functions forpricing, admission control, scheduling and qmanagement

Markov-Model Rewriter – software to systematically pe

model with bounds defined b

DiVisa – software for interactive exploration of multidimensio
March 10, 2009

Innovations in Measurement Science

46

Measurement Science for Complex Information Systems

Sample Challenge Problems Under Investi

• Predict effect on global behavior and user experience fr

adopting proposed replacement congestion-control algo

for the Internet* (Filliben, Cho, Houard & Mills)

• Evaluate accuracy of proposed fluid-flow models for TC

characterize limits of applicability of such models and pimproved analytical models (Genin & Marbukh)

• Devise efficient Markov models to accurately simulate la

scale systems and apply perturbation analysis to predicsystem changes that could lead to undesired behaviors 

(Dabrowski & Hunt)

• Investigate the use of economic methods for resource 

allocation in large distributed systems (e.g., computatiogrids and networks) (Dabrowski, Marbukh & Mills)

*Later I use this challenge problem to illustrate some of our approac
March 10, 2009

Innovations in Measurement Science

47

Measurement Science for Complex Information Systems

Interactive Exploration of Multidimensional Da

Download from – http://math.nist.gov/mcsd/savg/software
March 10, 2009

Innovations in Measurement Science

48

Measurement Science for Complex Information Systems

Sample Papers Produced by the Proje

C. Dabrowski, “Reliability in Grid Computing Systems”, in Concurrency and Computation: Practice and 

Wiley-Blackwell, in press.D. Genin and V. Marbukh, "Do Current Fluid Approximation Models Capture TCP Instability?“, submitteDresden, Germany, June 14 -18.C. Dabrowksi and F. Hunt, “Using Markov Chain Analysis to Study Dynamic Behavior in Large-Scale GProceedings of the 7th Australasian Symposium on Grid Computing and e-Research, Wellington, New Z

C. Dabrowski and F. Hunt, Markov Chain Analysis for Large-Scale Grid Systems, NIST Technical Repo

D. Genin and V. Marbukh, "Metastability in cellular networks with migrating users: emergence and implperformance.“ GLOBECOM 2008, New Orleans, Nov. 31 - Dec. 4.K. Mills and C. Dabrowski, “Can Economics-based Resource Allocation Prove Effective in a Computati

Journal of Grid Computing, Vol. 6, No. 3, September 2008, pp. 291-311. F. Hunt and V. Marbukh, “Dynamic Routing and Congestion Control Through Random Assignment of RProceedings of the 5th International Conference on Cybernetics and Information Technologies, System

Applications: CITSA 2008, Orlando FL, July 2008. V. Marbukh and K. Mills, "Demand Pricing & Resource Allocation in Market-based Compute Grids: A M

and Initial Results", Proceedings of the 7th International Conference on Networking, IEEE, April 2008, p
March 10, 2009

Innovations in Measurement Science

49

Measurement Science for Complex Information Systems

Sample Papers Produced by the Proje

Marbukh and S. Klink, "Decentralized Control of Large-Scale Networks as a Game with Local InteractiTCP/IP Optimization", 2nd International Conference on Performance Evaluation Methodologies and ToOctober 23-25, 2007.V. Marbukh, "Utility Maximization for Resolving Throughput/Reliability Trade-offs in an Unreliable Netwwith Multipath Routing", 2nd International Conference on Performance Evaluation Methodologies and 

Tools, Nantes, France, October 23-25, 2007. K. Mills, "A Brief Survey of Self-Organization in Wireless Sensor Networks", Wireless Communications 

Mobile Computing, Wiley Interscience, Vol. 7, No. 7, September 2007, pp. 823-834. 

V. Marbukh and K. Mills, "On Maximizing Provider Revenue in Market-Based Compute Grids", Proceedings of the 3rd International Conference on Networking and Services, Athens, Greece, June 19

K. Mills and C. Dabrowski, "Investigating Global Behavior in Computing Grids", Self-Organizing System

Lecture Notes in Computer Science, Volume 4124 ISBN 978-3-540-37658-3, pp. 120-136.
March 10, 2009

Innovations in Measurement Science

50

Measurement Science for Complex Information Systems

Input Factors & Network Parameters

6 Robustness Factors

x6 Buffer Sizing Algorithm RTTxCapacity RTTxCap

x5 File Size 100 x4 Propagation Delay 2 x3 Source Distribution Uniform (.33/.33/.33) Ske

x2 Think Time 5000 

x1 Network Speed 8000 

Identifier Definition PLUS (+1) Value Min

x6 Buffer Sizing Algorithm RTTxCapacity RTTxCap

x5 File Size 100 x4 Propagation Delay 2 x3 Source Distribution Uniform (.33/.33/.33) Ske

x2 Think Time 5000 

x1 Network Speed 8000 

Identifier Definition PLUS (+1) Value Min

Router Speeds

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

POP 24 Gbps 12 Gbps

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

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

POP 24 Gbps 12 Gbps

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

Propagation Delays (ms) 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

Buffer Sizes (packets)

Number of 

278,000 

PLUS (+1) 

25,879

162,764

1,302,110

Max

14,55791,555

732,437

Avg

6,470

40,691

325,528

Min

PLUS (+1)

Access 91 207 

POP 221 505 Backbone 1,153 2,606 Router Min Avg 

Minus (-1)

25,879

162,764

1,302,110

Max

14,55791,555

732,437

Avg

6,470

40,691

325,528

Min

PLUS (+1)

Access 91 207 

POP 221 505 Backbone 1,153 2,606 Router Min Avg 

Minus (-1)
March 10, 2009

Innovations in Measurement Science

51

Measurement Science for Complex Information Systems

Processor Time Requirements

6.611.513.46

110.5

Scalable

26.37

(13.18x2)

5.94 5.85 5.17 5.84 5.63 28.42 6.57

Max. CPU time

(one run)

1.16 1.33 1.44 1.40 1.28 1.61

Min. CPU time

(one run)

13.70

(6.85x2)

2.86 3.04 2.92 3.01 2.94 14.77 3.39 Avg. CPU time (per run) 91.5 97.2 93.4 96.4 94.2 472.5 108.6 219.1

CPU time 

(32 runs)

BIC CTCP FAST HTCP TCP Totals HSTCP Totals

Compute Servers ws11-ws14 Compute Servers ws9-ws10

6.611.513.46

110.5

Scalable

26.37

(13.18x2)

5.94 5.85 5.17 5.84 5.63 28.42 6.57

Max. CPU time

(one run)

1.16 1.33 1.44 1.40 1.28 1.61

Min. CPU time

(one run)

13.70

(6.85x2)

2.86 3.04 2.92 3.01 2.94 14.77 3.39 Avg. CPU time (per run) 91.5 97.2 93.4 96.4 94.2 472.5 108.6 219.1

CPU time 

(32 runs)

BIC CTCP FAST HTCP TCP Totals HSTCP Totals

Compute Servers ws11-ws14 Compute Servers ws9-ws10

(Units are CPU days)

Experiment required about 15 days of wall-clock time spread over 4

Total All Runs 16,583,418,069 1,548,371,719,084Max. Per Condition 154,914,953 11,917,420,154Min. Per Condition 40,966,013 3,146,870,571Avg. Per Condition 74,033,116 6,912,373,746Statistic Flows Completed Data Packets SentTotal All Runs 16,583,418,069 1,548,371,719,084Max. Per Condition 154,914,953 11,917,420,154Min. Per Condition 40,966,013 3,146,870,571Avg. Per Condition 74,033,116 6,912,373,746Statistic Flows Completed Data Packets Sent

Simulated Workload