Jul 30, 2012 - Time (sec.) Q dela y (ms.) Two views of a Queue. Top graph is sojourn time, bottom is queue size. ... low
Kathie Nichols’
CoDel
present by Van Jacobson to the IETF-84 Transport Area Open Meeting 30 July 2012 Vancouver, Canada
2
3
Sender
Receiver
4
Sender
Receiver
5
Sender
Receiver
• Queue forms at a bottleneck • There’s probably just one bottleneck (each flow sees exactly one)
➡ Choices: can move the queue (by making a new bottleneck) or control it. 5
Queue length
Good Queue / Bad Queue
Time
6
Queue length
Good Queue / Bad Queue
Queue length
Time
Time
6
Good Queue / Bad Queue Queue length
•
Queue length
Time
Good queue goes away in an RTT, bad queue hangs around.
➡ queue length min() over a sliding window measures bad queue ... ➡ ... as long as window is at least an RTT wide.
Time
7
Good Queue / Bad Queue Queue length
•
Queue length
Time
Good queue goes away in an RTT, bad queue hangs around.
➡ tracking min() in a sliding window gives bad queue ... ➡ ... as long as window is at least an RTT wide.
Time
8
Good Queue / Bad Queue Queue length
•
Queue length
Time
Good queue goes away in an RTT, bad queue hangs around.
➡ tracking min() in a sliding window gives bad queue ... ➡ ... as long as window is at least an RTT wide.
Time
8
How big is the queue? • Can measure size in bytes
– interesting if worried about overflow – requires output bandwidth to compute delay
• Can measure packet’s sojourn time
– direct measure of delay – easy (no enque/deque coupling so works with any packet pipeline). 9
Sojourn Time • Works with time-varying output bandwidth (e.g., wireless and shared links)
• Better behaved than queue length – no high frequency phase noise
• Includes everything that affects packet so works for multi-queue links
10
6 5 4 3 1
2
Q delay (ms.)
Two views of a Queue
0
Top graph is sojourn time, bottom is queue size.
24.5
25.0
25.5
26.0
3 2 1 0
(one ftp + web traffic; 10Mbps bottleneck; 80ms RTT; TCP Reno)
Q size (ms.)
4
5
6
Time (sec.)
11
6 5 4 3 1
2
Q delay (ms.)
Two views of a Queue
0
Top graph is sojourn time, bottom is queue size.
24.5
25.0
25.5
26.0
3 2 1 0
(one ftp + web traffic; 10Mbps bottleneck; 80ms RTT; TCP Reno)
Q size (ms.)
4
5
6
Time (sec.)
11
2.0 1.5 1.0 0.0
0.5
Q delay (ms.)
Two views of a Queue
Top graph is sojourn time, bottom is queue size.
25.05
25.10
25.15
25.20
Time (sec.)
1.0 0.5 0.0
(one ftp + web traffic; 10Mbps bottleneck; 80ms RTT; TCP Reno)
Q size (ms.)
1.5
2.0
2.5
25.00
12
Multi-Queue behavior
13
Controlling Queue a) Measure what you’ve got b) Decide what you want c) If (a) isn’t (b), move it toward (b)
14
Controlling Queue a) Measure what you’ve got b) Decide what you want c) If (a) isn’t (b), move it toward (b)
-
Estimator Setpoint Control loop
15
How much ‘bad’ queue do we want? • Can’t let the link go idle (need one or two MTU of backlog)
• More than this will give higher utilization at low degree of multiplexing (1-3 bulk xfers) at the cost of higher delay
• Can the trade-off be quantified? 16
95 90 85 80 75
Bottleneck Link Utilization (% of max)
100
Utilization vs. Target for a single Reno TCP
0
20
40
60
80
100
Target (% of RTT)
17
0.90 0.85 0.80 0.75 0.70
Average Power (Xput/Delay)
0.95
1.00
Power vs. Target for a Reno TCP
0
20
40
60
80
100
Target (as % of RTT)
18
0.90 0.85 0.80 0.75 0.70
Average Power (Xput/Delay)
0.95
1.00
Power vs. Target for a Reno TCP
0
20
40
60
80
100
Target (as % of RTT)
18
0.98 0.97 0.96 0.95 0.94 0.93
Average Power (Xput/Delay)
0.99
1.00
Power vs. Target for a Reno TCP
0
5
10
15
20
25
30
Target (as % of RTT)
19
0.98 0.97 0.96 0.95 0.94 0.93
Average Power (Xput/Delay)
0.99
1.00
Power vs. Target for a Reno TCP
0
5
10
15
20
25
30
Target (as % of RTT)
19
20
• Setpoint target of 5% of nominal RTT (5ms
for 100ms RTT) yields substantial utilization improvement for small added delay.
20
• Setpoint target of 5% of nominal RTT (5ms
for 100ms RTT) yields substantial utilization improvement for small added delay.
• Result holds independent of bandwidth and congestion control algorithm (tested with Reno, Cubic & Westwood).
20
• Setpoint target of 5% of nominal RTT (5ms
for 100ms RTT) yields substantial utilization improvement for small added delay.
• Result holds independent of bandwidth and congestion control algorithm (tested with Reno, Cubic & Westwood).
➡ CoDel has no free parameters: runningmin window width determined by worstcase expected RTT and target is a fixed fraction of same RTT. 20
Algorithm & Control Law (see I-D, CACM paper and Linux kernels >= 3.5)
21
Eric Dumazet has combined CoDel with a simple SFQ (256-1024 buckets with RR service discipline). Cost in state & cycles is small and improvement is big.
• provides isolation - protects low rate CBR and web for a better user experience. Makes IW10 concerns a non-issue.
• gets rid of bottleneck bi-directional traffic problems (‘ack-compression’ burstiness)
• improves flow mixing for better network performance (reduce HoL blocking)
➡ Since we’re adding code, add fqcodel, not codel. 22
Where are we? • thanks to Jim Gettys and the ACM, have dead-tree publication to protect ideas
• un-encumbered code (BSD/GPL dual-license) available for ns2, ns3 & linux
• in both simulation and real deployment,
CoDel does no harm – it either does nothing or reduces delay without affecting xput. 23
What needs to be done • Still looking at parts of the algorithm but changes likely to be 2nd order.
• Would like to see CoDel on both ends of every home/small-office access link but:
- We need to know more about how traffic behaves on particular bottlenecks (wi-fi, 3G cellular, cable modem)
- There are system issues with deployment 24
Deployment Issues Home Gateway
RTR/AP
Cable Modem
Headend
25
Deployment Issues Home Gateway Linux kernel
RTR/AP Protocol stack
Cable Modem
Headend
Device Driver
Device
26
Deployment Issues Home Gateway Linux kernel
Cellphone
RTR/AP Protocol stack Phone CPU
Cable Modem
Headend
Device Driver
Device
3G Modem
RAN
?
SGSN
27
Our thanks to: • Jim Gettys • CoDel early experimenters, particularly Dave Taht
• Eric Dumazet • ACM Queue • Eben Moglen 28
