Transcript ppt

Parallel TCP Sockets:
Simple Model, Throughput
and Validation
Eitan Altman Dhiman Barman Bruno Tuffin
Milan Vojnović
INRIA
UC Riverside
IRISA/INRIA Microsoft Research
United Kingdom
France
United States
France
IEEE Infocom 2006 Talk, Barcelona, Spain, April 25, 2006
1
Motivation
• Parallel TCP sockets used for bulk-data transfers
– Throughput improvements
– Ex GridFTP
• Throughput characterization of AIMD (“AdditiveIncrease & Multiplicative Decrease”) connections
• Known: throughput-loss formulae of a single AIMD
– Given a loss process (stochastic; stationary; ergodic)
– SQRT, Altman, Avrachenkov, Barakat (2000)
• Our goal: Aggregate throughput of N AIMD
connections competing for a bottleneck
2
Related Work
• Partial results for the same problem by Altman, El
Azouzi, Ross, Tuffin (2004)
– For two connections only (N = 2)
– Unnecessary assumptions on loss process
• Experimental results by Hacker, Athey, Noble (2002)
– Throughput increase exhibits diminishing-returns
with the number of connections
3
This Talk
• One main result: throughput formula for parallel,
symmetric AIMD connections
– For any given number of connections
– For many loss polices (= assignment of congestion
signal to competing connections)
• Throughput second-moment for specific loss
polices
– Shows throughput higher-order statistic depends on
the loss policy
• Simulation & Internet experiment results
4
Origins of TCP throughput
deficiency
• TCP window
synchronization
c
Bottleneck capacity
Connection 1 send rate
0
Connection 2 send rate
c
• TCP window control
– Congestion avoidance
0
c
• Receiver window
limitation
0
5
Model
• Single link of capacity c
• Congestion event whenever the aggregate arrival
rate hits c
– Model introduced by Baccelli & Hong (2002)
1
2
i
.
.
.
.
.
.
AIMD connection
Xi = send rate
N
Bottleneck capacity c
6
Model (2)
• Assumption ONE: at a congestion event, exactly
one connection undergoes multiplicative-decrease
– TCP windows non synchronized
• Example: 3 AIMD connections
X(3)
X(2)
Slope h X(1)
bX(1)
Congestion event
X(1) + X(2) + X(3) = c
Time
7
Main Result: Throughput Formula
• Consider N symmetric AIMD connections
• b = multiplicative-decrease factor
• Assume ONE = exactly one connection
undergoes multiplicative-decrease per
congestion event
The aggregate throughput is:
8
Implications of the Result
• Applies to a broad class of loss processes
– A broad class of loss polices to select connection to
undergo a multiplicative-decrease at congestion events
– Can depend in many ways on the observed past of
send rates, provided only the system is stable
• Throughput-invariance
– Loss policy is irrelevant
• Special cases (for b = ½; TCP like):
– N = 1 : Utilization = 0.75 c
– N = 2 : Utilization = 6/7 c  0.86 c
9
• Throughput deficiency
due to TCP window
adaptation compensated
with a few parallel
connections
• Utilization
Utilization (N)
Implications of the Result (2)
– > 90% for N=3
– almost 95% for N=6
N
10
Proof Sketch
= 1 if connection i selected at
the n-th congestion event, else 0
11
Proof Sketch (2)
• Palm inversion
const
• The latter follows by taking expectation on
both sides of the recurrence for Xi2(Tn)
12
Example 1: Aggregate
Throughput is Invariant
• Connections:
– RED (2) and BLUE (2)
• A BLUE connection chosen
with probability s
Throughput (s)
Aggregate throughput
Throughput of
Throughput of
BLUE connections RED connections
s
13
Example 2: Loss Polices
• Beatdown
– Pick a selected connection as
long as possible
• Rate-independent
– Pick at random a connection
with fixed probability
• Rate-proportional
– Pick at random a connection
proportional to its send rate
• Largest-rate
– Pick a connection with largest
send rate
= round-robin (in steady-state,
with symmetric connections)
14
Throughput: Higher-order Statistics
Depends on Loss Policy
• Result for N = 2 & b = ½
• Loss policy: second moment
• Same type of result as in Altman, El Azouzi, Ross,
Tuffin (2004)
– But a correct version
– Full proof; not symbolic math software solving
15
Validation
• ns-2 simulations
– Single bottleneck c = 10 Mb/s
– Queue discipline either Threshold Dropper or
DropTail or RED
– N TCP connections
• Internet experiments
– PlanetLab on various end-to-end paths
16
Validation: ns-2 simulations
– Drop only from a
selected connection
for a fixed time
interval Th
– Enforces assumption
ONE
– b = buffer size (pkts)
Utilization (N)
• Queue discipline:
threshold dropper
17
• Buffer size b = varying
parameter
• Suggests buffer-size
sensitivity
• Inspection suggests
window synchronization
Utilization (N)
Simulations with DropTail
N
N=5
18
• Buffer size b = varying
parameter
• Good conformance for
some b and N
Utilization (N)
Simulations with RED
N = 10
N
19
Cornell-Greece
RTT = 338 ms
N
Utilization (N)
UMASS-Berkeley
RTT = 97 ms
Utilization (N)
Utilization (N)
Utilization (N)
Internet Experiments
INRIA-Stanford
RTT = 195 ms
Fortiche-Titeuf
RTT = 1.6 ms
N
20
Utilization (N)
Internet Experiments (2)
N
N
N
21
Conclusion
• Obtained aggregate throughput formula of symmetric AIMD
connections
– Under given bottleneck model
– And: one congestion signal per link congestion event
• Throughput-invariance to loss policy which connection is
signalled
• A few connections suffice to compensate for throughput
deficiency due to window adaptation
• Higher-order throughput statistics is not invariant
• Simulation and Internet experiments suggest TCP window
22
synchronization may be common