Transcript slides ppt

Buffer requirements for TCP:
queueing theory & synchronization analysis
Gaurav Raina
Damon Wischik
Cambridge
UCL
traffic rate [0-100 kB/sec]
TCP
time [0-8 sec]
if (seqno > _last_acked) {
if (!_in_fast_recovery) {
_last_acked = seqno;
_dupacks = 0;
inflate_window();
send_packets(now);
_last_sent_time = now;
return;
}
if (seqno < _recover) {
uint32_t new_data = seqno - _last_acked;
_last_acked = seqno;
if (new_data < _cwnd) _cwnd -= new_data; else _cwnd=0;
_cwnd += _mss;
retransmit_packet(now);
send_packets(now);
return;
}
uint32_t flightsize = _highest_sent - seqno;
_cwnd = min(_ssthresh, flightsize + _mss);
_last_acked = seqno;
_dupacks = 0;
_in_fast_recovery = false;
send_packets(now);
return;
}
if (_in_fast_recovery) {
_cwnd += _mss;
send_packets(now);
return;
}
_dupacks++;
if (_dupacks!=3) {
send_packets(now);
return;
}
_ssthresh = max(_cwnd/2, (uint32_t)(2 * _mss));
retransmit_packet(now);
_cwnd = _ssthresh + 3 * _mss;
_in_fast_recovery = true;
_recover = _highest_sent;
}
Motivation: buffer size
• Internet routers have buffers,
to accomodate bursts in traffic.
• How big do the buffers need to be?
– 3 GByte? Rule of thumb is C*RTT—what Cisco does today
– 300 MByte? C*RTT/√N [Appenzeller, Keslassy, McKeown, 2004 ]
– 30 kByte? constant buffer size, independent of line rate
• Large buffers are unsustainable:
– Data volumes double every 10 months
– CPU speeds double every 18 months
– Memory access speeds double every 10 years
Buffers & synchronization
Desynchronized
TCP flows:
Synchronized
TCP flows:
aggregate
traffic rate
individual
flow rates
– aggregate traffic
is smooth
– small buffers
are OK
– aggregate traffic
is bursty
– large buffers
are needed
+
+
=
+
+
=
time
Network traffic model
• When there are many TCP flows, the average traffic rate xt
varies smoothly, according to a differential equation
[Misra, Gong, Towsley, 2000]
aggregate
traffic rate
– involving average round trip time RTT
– and packet loss probability pt
desynchronized
time
synchronized
Network traffic model
• When there are many TCP flows, the average traffic rate xt
varies smoothly, according to a differential equation
[Misra, Gong, Towsley, 2000]
– involving average round trip time RTT
– and packet loss probability pt
• The packet loss probability pt satisfies a differential
equation, which depends on buffer size:
[Raina, W., 2005]
– either for small buffers (max queueing delay « RTT)
val1
0 5 10 15 20 0 5 10 15 20 0 5 10 15 20
2000
200
20
– or for large buffers (max queueing delay  RTT)
40
41
42
43
44
45
ti me
0
50
100
queue
val1
size
150
queueapprox
40
42
44
46
time
48
time
50
Analysis
• Write down differential equations
– for average TCP traffic rate xt
– for queue dynamics and loss prob pt
taking account of buffer size
• Calculate
– average link utilization
– average queue occupancy/delay
– extent of synchronization
and consequent loss of utilization, and jitter
Results
Small buffers
Large buffers
[20-50 pkts]
[>50ms queue delay]
lowbandwidth
flows
• slightly
synchronized;
• high utilization;
• low delay/jitter.
• desynchronized;
• high utilization;
• high delay,
low jitter.
[window <5pkts]
highbandwidth
flows
[window >10pkts]
• desynchronized;
• severely
synchronized;
• moderate utilization;
• high utilization;
• low delay/jitter.
• high delay/jitter.
There is a virtuous circle:
desynchronization permits small buffers; small buffers induce desynchronization.
Illustration: 20 flows
Standard TCP, single bottleneck link, no AQM
service C=1.2 kpkt/sec, RTT=200 ms, #flows N=20
B=20 pkts
(small buffer)
B=54 pkts
(intermediate buffer)
B=240 pkts
(large buffer)
Illustration: 200 flows
Standard TCP, single bottleneck link, no AQM
service C=12 kpkt/sec, RTT=200 ms, #flows N=200
B=20 pkts
(small buffer)
B=170 pkts
(intermediate buffer)
B=2,400 pkts
(large buffer)
Illustration: 2000 flows
Standard TCP, single bottleneck link, no AQM
service C=120 kpkt/sec, RTT=200 ms, #flows N=2000
B=20 pkts
(small buffer)
B=537 pkts
(intermediate buffer)
B=24,000 pkts
(large buffer)
Limitations/concerns
• Surely bottlenecks are at the access network,
not the core network?
– Unwise to rely on this!
– The small-buffer theory works fine for as few as 20 flows
• Perhaps TCP is constrained by receiver window,
not by congestion window?
– Unwise to rely on this!
Probably there are congestion-constrained flows
which cause congestion
– Would small buffers hurt flows
that are constrained by receiver window?
Not if they respond appropriately.
Further work
• These results have been partially validated
(Internet2 & Level3)
• Full validation needs
– goodly amount of traffic
– full measurement kit
– ability to control buffer size
• Alternatives to TCP
– should pace packet injections
– can achieve desynchronization at all window sizes
2000
20
20
200
10
20
5
5
20
20
200
15
time
0
0
time
[0-5
sec]
42
43
44
45
20
41
15
40
queueing
2000 delay
0.19 ms
15
20
15
200 delay
queueing
1.9 ms
10
val1
15
10
5
0
queue size
[0-15 pkt]
20
queueing
20 delay
19 ms
10
0
0
5
5
10
val1
15
15
Small buffers
10
5
5
10
val1
As line rate increases
– queue size fluctuates more and more rapidly
[Cao+Ramanan 2002]
time
15
20
0
0
• so pt depends only on the instantaneous utilization at time t
20
41
42
44
45
• can model packet40 arrivals
by43 a Poisson
process of rate xt
0
5
10
– queue size distribution depends only on link utilization,
not on line rate
40
41
42
43
time
44
45
Large buffers (queueing delay 200 ms)
queue
val1size
0
50
100
150
pkt]
[0-160
queueapprox
40
42
44
46
time
50
time 48[0-10 sec]
• When Nxt<C the queue size is small (C=line rate)
• No packet drops, so TCP increases xt
Large buffers (queueing delay 200 ms)
queue
val1size
0
50
100
150
pkt]
[0-160
queueapprox
40
42
44
46
time
50
time 48[0-10 sec]
• When Nxt<C the queue size is small (C=line rate)
• No packet drops, so TCP increases xt
• When Nxt>C the queue fills up
and packets begin to get dropped
Large buffers (queueing delay 200 ms)
queue
val1size
0
50
100
150
pkt]
[0-160
queueapprox
40
42
44
46
time
50
time 48[0-10 sec]
• When Nxt<C the queue size is small (C=line rate)
• No packet drops, so TCP increases xt
• When Nxt>C the queue fills up
and packets begin to get dropped
• TCP may ‘overshoot’, leading to synchronization
Large buffers (queueing delay 200 ms)
queue
val1size
0
50
100
150
pkt]
[0-160
queueapprox
40
42
44
46
time
50
time 48[0-10 sec]
• Drop probability depends on
both average traffic rate xt and queue size qt
System summary
• xt = average traffic rate at time t
pt = packet loss probability at time t
C = line rate B = buffer size RTT = round trip time
• TCP traffic model
• Small buffer queueing model
(though this is sensitive to traffic statistics)
• Large buffer queueing model
N=# flows
Stability/instability analysis
traffic
rate
Nxt/C
1.4
1.2
0.8
0.6
20
40
60
80
100
20
40
60
80
100
1.4
1.2
0.8
0.6
• For some values of RTT*C/N,
the dynamical system is stable
• For others it is unstable and there are oscillations
(i.e. the flows are partially synchronized)
• When it is unstable,
we can calculate the amplitude of the oscillations
time
Instability plot
traffic intensity Nx/C
0.5
-1
log10 of
pkt loss
probability p
1
extent of
oscillations
in Nx/C
-2
-3
-4
queue equation
1.5
2
TCP throughput equation
Instability plot
traffic intensity Nx/C
0.5
1
1.5
2
-1
RTT*C/N=4 pkts
log10 of
pkt loss
probability p
-2
-3
RTT*C/N=20 pkts
-4
RTT*C/N=100 pkts
Alternative buffer-sizing rules
Intermediate buffers buffer = bandwidth*delay / sqrt(#flows)
or
Large buffers, no AQM buffer = bandwidth*delay
b25
b100
b400
-1
-2
Large buffers with RED
-3
buffer=bandwidth*delay*{¼,1,4}
-4
0.5
b10
1
1.5
b20
b50
-1
-2
Small buffers, no AQM
-3
buffer={10,20,50} pkts
-4
0.5
b50
1
1.5
b1000
-1
-2
Small buffers, no AQM, ScalableTCP
p -3
-4
buffer={50,1000} pkts
-5
-6
0.5
1
1.5