Transcript slides ppt

Queueing theory for TCP
Damon Wischik, UCL
Gaurav Raina, Cambridge
transmission rate [0–100 kB/sec]
DJW 2007
2/24
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;
}
DJW 2007
3/24
Models for TCP
Single TCP sawtooth
One can explicitly
calculate the mean
transmission rate,
stationary distribution
etc.
DJW 2007
4/24
Models for TCP
Single TCP sawtooth
*
*
*
*
*
**
Billiards model
Baccelli+Hong 2002
Each flow increases its
transmission rate
linearly...
until the total transmission
rate hits capacity, when
some flows experience
dropped packets...
and those flows back off.
DJW 2007
5/24
Models for TCP
Single TCP sawtooth
*
Approximate the
aggregate TCP traffic by
**
*means
* * of a* differential
equation...
The differential equation
has increase
Billiards
model& decrease
terms, which
reflect the
Baccelli+Hong
2002
TCP sawtooth.
Fluid model
Kelly+Maulloo+Tan 1998
Misra+Gong+Towsley 2000
Baccelli+McDonald+Reynier 2002
DJW 2007
6/24
Models for TCP
QUESTIONS
TCP sawtooth
When areSingle
these models
good?
What is the formula for packet drop
probability, to plug into the models?
How does it depend on buffer size etc.?
*
*
*
*
*
**
Billiards model
Fluid model
Baccelli+Hong 2002
Kelly+Maulloo+Tan 1998
Misra+Gong+Towsley 2000
Baccelli+McDonald+Reynier 2002
DJW 2007
7/24
Simulation results
small buffer
int. buffer
large buffer
drop
probability
[0–30%]
queue
size
[0–100%]
traffic
intensity
[0–100%]
time [0–5s]
DJW 2007
8/24
Simulation results
When we vary the
buffer size, the
system behaviour
changes
dramatically.
WHY? HOW?
small buffer
drop
probability
[0–30%]
queue
size
[0–100%]
traffic
intensity
[0–100%]
int. buffer
large buffer
ANSWER
It depends on the
timescale and
spacescale of
fluctuations in the
arrival process...
time [0–5s]
DJW 2007
9/24
Formulate a maths question
Round trip time RTT
N TCP flows
Service rate NC
Buffer size B(N)
• What is the limiting queue-length process, as N, in the three
regimes
– large buffers B(N)=BN
– intermediate buffers B(N)=B√N
– small buffers B(N)=B
• Why are these the interesting limiting regimes?
What are the alternatives? [Bain, 2003]
DJW 2007
10/24
•
Intermediate buffers B(N)=B√N
Consider a standalone queue
– fed by N Poisson flows, each of rate x pkts/sec where x varies slowly,
served at constant rate NC, with buffer size B√N
– i.e. an MNx//DNC
//1/B√N queue
– xt=0.95 then 1.05 pkts/sec, C=1 pkt/sec, B=3 pkt
•
Observe
– queue size fluctuates very rapidly; busy periods have duration O(1/N)
so packet drop probability pt is a function of instantaneous arrival rate xt
– queue size flips quickly from near-empty to near-full, in time O(1/√N)
90
– packet drop probability is pt=(xt-C)+/xt
80
70
queue
size
traffic
intensity
60
60
50
50
40
40
30
30
20
20
20
20
10
10
10
10
1
0.5
time
20
40
N=50
60
80
N=100
N=500
N=1000
DJW 2007
11/24
•
Intermediate buffers B(N)=B√N
Consider a standalone queue
– fed by N Poisson flows, each of rate x pkts/sec where x varies slowly,
served at constant rate NC, with buffer size B√N
– i.e. an MNx//DNC
//1/B√N queue
– xt=0.95 then 1.05 pkts/sec, C=1 pkt/sec, B=3 pkt
•
Observe
– queue size fluctuates very rapidly; busy periods have duration O(1/N)
so packet drop probability pt is a function of instantaneous arrival rate xt
– queue size flips quickly from near-empty to near-full, in time O(1/√N)
90
– packet drop probability is pt=(xt-C)+/xt
80
70
queue
size
traffic
intensity
60
60
50
50
40
40
30
30
This formula was
proposed for TCP
by Srikant 2004
20
20
20
20
10
10
10
10
1
0.5
time
20
40
N=50
60
80
N=100
N=500
N=1000
DJW 2007
12/24
Closing the loop
90
80
70
60
60
50
50
40
40
30
30
20
20
20
20
10
10
10
10
1
0.5
20
•
40
60
80
In the open-loop queue
– we assumed Poisson inputs with slowly
varying arrival rate
– queue size flips quickly from nearempty to near-full
– queue size fluctuates very rapidly, with
busy periods of duration O(1/N), so
drop probability pt is a function of
instantaneous arrival rate xt
•
•
In the closed-loop TCP system
– the round trip time means that we can
treat inputs over time [t,t+RTT] as an
exogenous arrival process to the queue
– the average arrival rate should vary
slowly, according to a differential
equation
– the aggregate of many point processes
converges to a Poisson process, and
this carries through to queue size
[Cao+Ramanan 2002]
There is thus a separation of timescales
– queue size fluctuates over short timescales, and we obtain pt from the open-loop
M/D/1/B(N) model
– TCP adapts its rate over long timescales, according to the fluid model differential equation
DJW 2007
13/24
Intermediate buffers B(N)=B√N
drop
probability
[0–30%]
queue
size
[0–619pkt]
traffic
intensity
[0–100%]
time [0–5s]
queue
size
[594–619pkt]
time [50ms]
•
•
•
•
•
2Gb/s link, C=50 pkt/sec/flow
5000 TCP flows
RTT 150–200ms
buffer 619pkt
simulator htsim by Mark
Handley, UCL
DJW 2007
14/24
Intermediate buffers B(N)=B√N
drop
probability
[0–30%]
When the traffic intensity
changes between
<capacity and >capacity,
the buffer can fill or drain
in time O(1/√N)
queue
size
[0–619pkt]
traffic
intensity
[0–100%]
time [0–5s]
queue
size
[594–619pkt]
time [50ms]
Queue size
• 2Gb/s are
link, C=50 pkt/sec/flow
fluctuations
• 5000 TCP flows
O(1), invisible at
• RTT 150–200ms
the O(√N)
• bufferscale
619pkt
•
simulator htsim by Mark
Handley, UCL
DJW 2007
15/24
Instability and synchronization
•
queue
size
[0–619pkt]
•
TCP
window
sizes
[0-25pkt]
•
time [0–5s]
When the queue is not full,
there is no packet loss, so
transmission rates
increase additively
When the queue becomes
full, there are short periods
of concentrated packet
loss
This makes the flows
become synchronized
This is the
billiards model
for TCP
DJW 2007
16/24
Large buffers B(N)=BN
The total arrival rate
is Nxt and the
service rate is NC,
so it takes time O(1)
for the buffer to fill
or drain
and we can
calculate the
packet drop
probability when
the queue is full
drop
probability
[0–30%]
queue
size
[0–BN pkt]
traffic
intensity
[0–100%]
time [0–5s]
queue size
[(B-25)–B pkt]
time [50ms]
Queue size
fluctuations are
O(1), invisible on the
O(N) scale...
DJW 2007
17/24
Small buffers B(N)=B
The queue size changes
too quickly to be
controlled, but the queue
size distribution is
controlled by the average
arrival rate xt
drop
probability
[0–30%]
queue
size
[0–BN pkt]
traffic
intensity
[0–100%]
time [0–5s]
queue size
[(B-25)–B pkt]
time [50ms]
Queue size fluctuations
are of size O(1), over
timescale O(1/N),
enough to fill or drain
the buffer...
DJW 2007
18/24
Conclusion
Single TCP sawtooth
Fine for a
single flow
Arises as a lawof-largenumbers limit,
when there are
many TCP flows
Good for a small number of
flows...
This is also an extreme case
of the fluid model, when
flows are synchronized due
to intermediate-sized buffers
*
*
*
*
*
**
Billiards model
Fluid model
DJW 2007
19/24
Conclusion
Single TCP sawtooth
Proved by
McDonald+Reynier
Fluid model
*
*
*
*
*
**
Billiards model
DJW 2007
20/24
Instability & buffer size
• On the basis of these models,
and of a control-theoretic
analysis of the limit cycles that
ensue, we claimed
½=1
B=100pkt
B=50pkt
– a buffer of 30–50 packets
should be sufficient
– intermediate buffers will make
the system become
synchronized, and utilization
will suffer
– large buffers get high
utilization, but cause
synchronization and delay
B=40pkt
B=30pkt
B=20pkt
B=10pkt
traffic intensity
distribution
[85–110%]
Plot by Darrell Newman, Cambridge
queue size
distribution
[0–100%]
DJW 2007
21/24
Instability & buffer size
½=1
B=100pkt
B=50pkt
B=40pkt
B=30pkt
B=20pkt
B=10pkt
• On the basis of these models,
and of a control-theoretic
analysis of the limit cycles that
ensue, we claimed
But when other people ran – a buffer of 30–50 packets
should be sufficient
simulations they found...
– intermediate buffers will make
• Small buffers lead to terriblythe system become
low utilization
synchronized, and utilization
will suffer
• Intermediate buffers work
– large buffers get high
much better
utilization, but cause
synchronization and delay
traffic intensity
distribution
[85–110%]
Plot by Darrell Newman, Cambridge
queue size
distribution
[0–100%]
DJW 2007
22/24
Burstiness
• The problem is that the Poisson limit breaks down
– A key step in the C+R proof is showing that each flow
contributes at most one packet in a busy period
– But TCP, on a fast access link, will produce bursty traffic:
sources can send an entire window-full of packets back-toback
• For very fast access speeds, i.e. very bursty TCP
traffic, a batch-M/D/1/B model is appropriate
DJW 2007
23/24
Burstiness & access speeds
• Simulations of a system with a single bottleneck link with
capacity NC, where each flow is throttled by a slow access link
4 1 4 2 4=
3 4 5C
4
access speed
41 42 43 44
41 42 43 44
41 4243 44
40C
41 42 43 44
41 42 4344
41 4243 44
41 42 43 44
TCP traffic is Poisson-like
over short timescales, so
the queue's stochastic
fluctuations are small...
TCP traffic is bursty over
short timescales, so the
queue's stochastic
fluctuations are large...
TCP has bang-bang
feedback and it is unable to
maintain a steady state
TCP has continual feedback,
and can nearly maintain a
steady state
DJW 2007
24/24
Burstiness & access speeds
• Simulations of a system with a single bottleneck link with
capacity NC, where each flow is throttled by a slow access link
4 1 4 2 4=
3 4 5C
4
access speed
41 42 43 44
41 42 43 44
You have to be careful
about short-timescale
traffic statistics when you
model TCP
41 4243 44
40C
41 42 43 44
41 42 4344
Queueing theory still has a
role!
41 4243 44
41 42 43 44