Re: [Bloat] The challenge

Re: [Bloat] The challenge

[Hal Murray]

> It is counter-intuitive to keep a queue filled with packets that you might
> drop later - as an engineer you tend to think it is more efficient to drop a
> packet *before* it starts to consume space in your precious queue.  This is
> a good deal of what needs to be solved in wireless drivers ...

On the other hand, if your problem is buffer bloat, maybe the queue space 
isn't so precious.

Yes, I too tend to think that way, but maybe it will sink in if I see a few 
reminders.  Thanks.


-- 
These are my opinions.  I hate spam.

Re: [Bloat] The challenge

[Jim Gettys]

On 05/10/2012 04:30 AM, Hal Murray wrote:
>> It is counter-intuitive to keep a queue filled with packets that you might
>> drop later - as an engineer you tend to think it is more efficient to drop a
>> packet *before* it starts to consume space in your precious queue.  This is
>> a good deal of what needs to be solved in wireless drivers ...

Memory is so cheap that in a wireless router these days the buffers are
in the noise of memory consumption.

> On the other hand, if your problem is buffer bloat, maybe the queue space 
> isn't so precious.
>
> Yes, I too tend to think that way, but maybe it will sink in if I see a few 
> reminders.  Thanks.
The only place where memory cost is still any issue is in very high end
routers.  There, it's been shown you don't need the traditional BDP
buffering anyway, but much, much less.
                        - Jim

[Bloat] The challenge

[Dave Taht]

Both the acm queue article and jim's blog entry this morning were way
above mensa's standards.

Nobody has attempted to explain the elegant simplicity of the
algorithm itself in the inverse sqrt however!  I have a good grip on
it, and am trying, but can barely explain it to myself. Anyone else
care to dig through the codel code and try to put it into english?

Nice bit in ReadWrite News:

http://www.readwriteweb.com/enterprise/2012/05/good-news-for-solving-bufferbloat-codel-provides-no-knobs-solution.php

Bob Cringley lays down the challenge for us here on the bloat list,
and details the opportunity.

http://www.cringely.com/2012/05/beginning-of-the-end-for-bufferbloat/

He closes with:

"My advice to Cisco, Netgear, D-Link and others is that this could be
an important moment in their businesses if they choose to approach it
correctly. It’s a chance to get all of us to buy new routers, perhaps
new everything. Think of the music industry bonanza when we all
shifted our record libraries from vinyl to CDs. It could be the same
for networking equipment. But for that to happen the vendors have to
finally acknowledge bufferbloat and use their marketing dollars to
teach us all why we should upgrade ASAP. Everybody would win.

Take our money, please."

With the cerowrt project, at least, I've hoped to make that shift
possible, and to some extent... happen.

We have *working code*, and *proof of concept*. What's next? Where do
we go from here?

-- 
Dave Täht
SKYPE: davetaht
US Tel: 1-239-829-5608
http://www.bufferbloat.net

Re: [Bloat] The challenge

[Kevin Gross]

[-- Attachment #1: Type: text/plain, Size: 2560 bytes --]

The decision the algorithm is trying to make is when to drop packets. RED
drops packets when the maximum queue level rises. CoDel drops packets when
the minimum queue level rises. If the queue is never (nearly) empty, the
interface is oversubscribed and packet drops are in order. But because it
looks at minimum, not maximum, CoDel will not drop packets in bursts so
long as those bursts pass within the (5 ms) interval used to measure
minimum queue level.

1/sqrt bit controls how many packets get dropped as a function of time
and I gather it is control loop tuning used to strike a good balance
between responsiveness, stability and do no harm.

Kevin Gross

On Tue, May 8, 2012 at 7:04 PM, Dave Taht <dave.taht@gmail.com> wrote:

> Both the acm queue article and jim's blog entry this morning were way
> above mensa's standards.
>
> Nobody has attempted to explain the elegant simplicity of the
> algorithm itself in the inverse sqrt however!  I have a good grip on
> it, and am trying, but can barely explain it to myself. Anyone else
> care to dig through the codel code and try to put it into english?
>
> Nice bit in ReadWrite News:
>
>
> http://www.readwriteweb.com/enterprise/2012/05/good-news-for-solving-bufferbloat-codel-provides-no-knobs-solution.php
>
> Bob Cringley lays down the challenge for us here on the bloat list,
> and details the opportunity.
>
> http://www.cringely.com/2012/05/beginning-of-the-end-for-bufferbloat/
>
> He closes with:
>
> "My advice to Cisco, Netgear, D-Link and others is that this could be
> an important moment in their businesses if they choose to approach it
> correctly. It’s a chance to get all of us to buy new routers, perhaps
> new everything. Think of the music industry bonanza when we all
> shifted our record libraries from vinyl to CDs. It could be the same
> for networking equipment. But for that to happen the vendors have to
> finally acknowledge bufferbloat and use their marketing dollars to
> teach us all why we should upgrade ASAP. Everybody would win.
>
> Take our money, please."
>
> With the cerowrt project, at least, I've hoped to make that shift
> possible, and to some extent... happen.
>
> We have *working code*, and *proof of concept*. What's next? Where do
> we go from here?
>
> --
> Dave Täht
> SKYPE: davetaht
> US Tel: 1-239-829-5608
> http://www.bufferbloat.net
> _______________________________________________
> Bloat mailing list
> Bloat@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/bloat
>

[-- Attachment #2: Type: text/html, Size: 3520 bytes --]

Re: [Bloat] The challenge

[Simon Barber]

One question now remains - will codel AQM be sufficient on it's own in 
getting delays down to levels that users are happy with for the common 
latency sensitive interactive traffic - VoIP, gaming and Skype for 
example - or are the further reductions that can be had with traffic 
classification and smart queuing algorithms necessary? The nicest part 
about codel on it's own is that it works on opaque packets - it will 
handle VPNs and traffic within them nicely. It gets away from all the 
complexity required to classify traffic in a world where traffic is 
often trying to hide.

Simon

On Tue 08 May 2012 06:04:50 PM PDT, Dave Taht wrote:
> Both the acm queue article and jim's blog entry this morning were way
> above mensa's standards.
>
> Nobody has attempted to explain the elegant simplicity of the
> algorithm itself in the inverse sqrt however!  I have a good grip on
> it, and am trying, but can barely explain it to myself. Anyone else
> care to dig through the codel code and try to put it into english?
>
> Nice bit in ReadWrite News:
>
> http://www.readwriteweb.com/enterprise/2012/05/good-news-for-solving-bufferbloat-codel-provides-no-knobs-solution.php
>
> Bob Cringley lays down the challenge for us here on the bloat list,
> and details the opportunity.
>
> http://www.cringely.com/2012/05/beginning-of-the-end-for-bufferbloat/
>
> He closes with:
>
> "My advice to Cisco, Netgear, D-Link and others is that this could be
> an important moment in their businesses if they choose to approach it
> correctly. It’s a chance to get all of us to buy new routers, perhaps
> new everything. Think of the music industry bonanza when we all
> shifted our record libraries from vinyl to CDs. It could be the same
> for networking equipment. But for that to happen the vendors have to
> finally acknowledge bufferbloat and use their marketing dollars to
> teach us all why we should upgrade ASAP. Everybody would win.
>
> Take our money, please."
>
> With the cerowrt project, at least, I've hoped to make that shift
> possible, and to some extent... happen.
>
> We have *working code*, and *proof of concept*. What's next? Where do
> we go from here?
>

Re: [Bloat] The challenge

[Eric Dumazet]

On Tue, 2012-05-08 at 22:16 -0700, Simon Barber wrote:
> One question now remains - will codel AQM be sufficient on it's own in 
> getting delays down to levels that users are happy with for the common 
> latency sensitive interactive traffic - VoIP, gaming and Skype for 
> example - or are the further reductions that can be had with traffic 
> classification and smart queuing algorithms necessary? The nicest part 
> about codel on it's own is that it works on opaque packets - it will 
> handle VPNs and traffic within them nicely. It gets away from all the 
> complexity required to classify traffic in a world where traffic is 
> often trying to hide.

It all depends on the requirements you have.

To me, CoDel is a RED replacement, because it provides something easier
to deploy (no knobs). So it wont solve by itself cases where you want
something that could not be done by a single RED queue.

I like to see Codel as a basic unit, to replace RED (or pfifo if some
fools still use this for whatever reasons) in a tree involving
classifiers and FQ.

Re: [Bloat] The challenge

[Dave Taht]

[-- Attachment #1: Type: text/plain, Size: 1289 bytes --]

On Tue, May 8, 2012 at 10:40 PM, Eric Dumazet <eric.dumazet@gmail.com>wrote:

> On Tue, 2012-05-08 at 22:16 -0700, Simon Barber wrote:
> > One question now remains - will codel AQM be sufficient on it's own in
> > getting delays down to levels that users are happy with for the common
> > latency sensitive interactive traffic - VoIP, gaming and Skype for
> > example - or are the further reductions that can be had with traffic
> > classification and smart queuing algorithms necessary? The nicest part
> > about codel on it's own is that it works on opaque packets - it will
> > handle VPNs and traffic within them nicely. It gets away from all the
> > complexity required to classify traffic in a world where traffic is
> > often trying to hide.
>
> It all depends on the requirements you have.
>
> To me, CoDel is a RED replacement, because it provides something easier
> to deploy (no knobs). So it wont solve by itself cases where you want
> something that could not be done by a single RED queue.
>
> I like to see Codel as a basic unit, to replace RED (or pfifo if some
> fools still use this for whatever reasons) in a tree involving
> classifiers and FQ.
>
>
+10



-- 
Dave Täht
SKYPE: davetaht
US Tel: 1-239-829-5608
http://www.bufferbloat.net

[-- Attachment #2: Type: text/html, Size: 1740 bytes --]

Re: [Bloat] The challenge

[Kevin Gross]

[-- Attachment #1: Type: text/plain, Size: 3080 bytes --]

From the paper (figure 7), you can see that CoDel still leaves spikes of
buffer occupancy when network conditions change. These will still
be disruptive to real-time traffic. Many networks that need QoS now will
still need QoS. Networks that do not have QoS will be much more usable with
CoDel.

Kevin Gross

On Tue, May 8, 2012 at 11:16 PM, Simon Barber <simon@superduper.net> wrote:

> One question now remains - will codel AQM be sufficient on it's own in
> getting delays down to levels that users are happy with for the common
> latency sensitive interactive traffic - VoIP, gaming and Skype for example
> - or are the further reductions that can be had with traffic classification
> and smart queuing algorithms necessary? The nicest part about codel on it's
> own is that it works on opaque packets - it will handle VPNs and traffic
> within them nicely. It gets away from all the complexity required to
> classify traffic in a world where traffic is often trying to hide.
>
> Simon
>
>
> On Tue 08 May 2012 06:04:50 PM PDT, Dave Taht wrote:
>
>> Both the acm queue article and jim's blog entry this morning were way
>> above mensa's standards.
>>
>> Nobody has attempted to explain the elegant simplicity of the
>> algorithm itself in the inverse sqrt however!  I have a good grip on
>> it, and am trying, but can barely explain it to myself. Anyone else
>> care to dig through the codel code and try to put it into english?
>>
>> Nice bit in ReadWrite News:
>>
>> http://www.readwriteweb.com/**enterprise/2012/05/good-news-**
>> for-solving-bufferbloat-codel-**provides-no-knobs-solution.php<http://www.readwriteweb.com/enterprise/2012/05/good-news-for-solving-bufferbloat-codel-provides-no-knobs-solution.php>
>>
>> Bob Cringley lays down the challenge for us here on the bloat list,
>> and details the opportunity.
>>
>> http://www.cringely.com/2012/**05/beginning-of-the-end-for-**bufferbloat/<http://www.cringely.com/2012/05/beginning-of-the-end-for-bufferbloat/>
>>
>> He closes with:
>>
>> "My advice to Cisco, Netgear, D-Link and others is that this could be
>> an important moment in their businesses if they choose to approach it
>> correctly. It’s a chance to get all of us to buy new routers, perhaps
>> new everything. Think of the music industry bonanza when we all
>> shifted our record libraries from vinyl to CDs. It could be the same
>> for networking equipment. But for that to happen the vendors have to
>> finally acknowledge bufferbloat and use their marketing dollars to
>> teach us all why we should upgrade ASAP. Everybody would win.
>>
>> Take our money, please."
>>
>> With the cerowrt project, at least, I've hoped to make that shift
>> possible, and to some extent... happen.
>>
>> We have *working code*, and *proof of concept*. What's next? Where do
>> we go from here?
>>
>>  ______________________________**_________________
> Bloat mailing list
> Bloat@lists.bufferbloat.net
> https://lists.bufferbloat.net/**listinfo/bloat<https://lists.bufferbloat.net/listinfo/bloat>
>

[-- Attachment #2: Type: text/html, Size: 3884 bytes --]

Re: [Bloat] The challenge

[Jonathan Morton]

On 9 May, 2012, at 4:04 pm, Kevin Gross wrote:

> From the paper (figure 7), you can see that CoDel still leaves spikes of buffer occupancy when network conditions change. These will still be disruptive to real-time traffic. Many networks that need QoS now will still need QoS. Networks that do not have QoS will be much more usable with CoDel.

Combining AQM with FQ certainly seems like a good idea to me.  I haven't had a chance to try the implementation of fq_codel which already exists yet, but it's compiled and just waiting for me to get around to it.  If it works, then it should be an excellent default.

 - Jonathan Morton

Re: [Bloat] The challenge

[Eric Dumazet]

On Wed, 2012-05-16 at 08:55 +0300, Jonathan Morton wrote:
> On 9 May, 2012, at 4:04 pm, Kevin Gross wrote:
> 
> > From the paper (figure 7), you can see that CoDel still leaves spikes of buffer occupancy when network conditions change. These will still be disruptive to real-time traffic. Many networks that need QoS now will still need QoS. Networks that do not have QoS will be much more usable with CoDel.
> 
> Combining AQM with FQ certainly seems like a good idea to me.  I haven't had a chance to try the implementation of fq_codel which already exists yet, but it's compiled and just waiting for me to get around to it.  If it works, then it should be an excellent default.


fq_codel has no priority concepts. It's only Fair. But what is
Fairness ?

In the presence of elephant flows, you get more packets drops from
elephant flows than from thin ones.

If the elephant flow is the 'high priority' traffic, dropping packets
from it is not what you wanted.

pfifo_fast is able to have strict priority. If you want Codel and strict
priority, you can use prio + codel  (or prio + fq_codel)

Re: [Bloat] The challenge

[Dave Taht]

I

On Tue, May 15, 2012 at 10:55 PM, Jonathan Morton <chromatix99@gmail.com> wrote:
>
> On 9 May, 2012, at 4:04 pm, Kevin Gross wrote:
>
>> From the paper (figure 7), you can see that CoDel still leaves spikes of buffer occupancy when network conditions change. These will still be disruptive to real-time traffic. Many networks that need QoS now will still need QoS. Networks that do not have QoS will be much more usable with CoDel.
>
> Combining AQM with FQ certainly seems like a good idea to me.  I haven't had a chance to try the implementation of fq_codel which already exists yet, but it's compiled and just waiting for me to get around to it.  If it works, then it should be an excellent default.

I would certainly like more folk to analyse fq_codel, particularly in
the context of TCP mice and what we call ANTs these days. It seems to
be really excellent, but I too haven't had much time to look at it,
yet. It certainly does an even better job than codel of allowing
sparse streams through in my own testing, and I run it by default on
my laptops, wireless gear, routers and desktop at present. Under heavy
load things like cerowrt and ssh and other stuff like mosh, remain
incredibly responsive.

With ponies that good, there has got to be some manure somewhere.

>  - Jonathan Morton
>
> _______________________________________________
> Bloat mailing list
> Bloat@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/bloat



-- 
Dave Täht
SKYPE: davetaht
US Tel: 1-239-829-5608
http://www.bufferbloat.net

Re: [Bloat] The challenge

[Roger Jørgensen]

On Wed, May 9, 2012 at 7:16 AM, Simon Barber <simon@superduper.net> wrote:
> One question now remains - will codel AQM be sufficient on it's own in
> getting delays down to levels that users are happy with for the common
> latency sensitive interactive traffic - VoIP, gaming and Skype for example -
> or are the further reductions that can be had with traffic classification
> and smart queuing algorithms necessary? The nicest part about codel on it's
> own is that it works on opaque packets - it will handle VPNs and traffic
> within them nicely. It gets away from all the complexity required to
> classify traffic in a world where traffic is often trying to hide.

I'm more worried about how long cascades of codel code in equipment
will work together, add lots of traffic to the mix, just how will it
behave then?



-- 

Roger Jorgensen           | ROJO9-RIPE
rogerj@gmail.com          | - IPv6 is The Key!
http://www.jorgensen.no   | roger@jorgensen.no

Re: [Bloat] The challenge

[Dave Taht]

On Wed, May 9, 2012 at 12:10 PM, Roger Jørgensen <rogerj@gmail.com> wrote:
> On Wed, May 9, 2012 at 7:16 AM, Simon Barber <simon@superduper.net> wrote:
>> One question now remains - will codel AQM be sufficient on it's own in
>> getting delays down to levels that users are happy with for the common
>> latency sensitive interactive traffic - VoIP, gaming and Skype for example -
>> or are the further reductions that can be had with traffic classification
>> and smart queuing algorithms necessary? The nicest part about codel on it's
>> own is that it works on opaque packets - it will handle VPNs and traffic
>> within them nicely. It gets away from all the complexity required to
>> classify traffic in a world where traffic is often trying to hide.
>
> I'm more worried about how long cascades of codel code in equipment
> will work together, add lots of traffic to the mix, just how will it
> behave then?

Dunno. I look forward to finding out.

I put up debian packages of the kernel for ubuntu 12.4 here:

http://huchra.bufferbloat.net/~d/codel/linux/

You'll need to build your own iproute2 from the current (v12) patch set.

Basic tests are throttling down your network card to like 100Mbit and
trying it, unless you have major cpu that can saturate gigE or higher.

I'm mostly using netperf from svn head.

>
>
> --
>
> Roger Jorgensen           | ROJO9-RIPE
> rogerj@gmail.com          | - IPv6 is The Key!
> http://www.jorgensen.no   | roger@jorgensen.no



-- 
Dave Täht
SKYPE: davetaht
US Tel: 1-239-829-5608
http://www.bufferbloat.net

Re: [Bloat] The challenge

[Dave Taht]

On Wed, May 9, 2012 at 12:15 PM, Dave Taht <dave.taht@gmail.com> wrote:
> On Wed, May 9, 2012 at 12:10 PM, Roger Jørgensen <rogerj@gmail.com> wrote:
>> On Wed, May 9, 2012 at 7:16 AM, Simon Barber <simon@superduper.net> wrote:
>>> One question now remains - will codel AQM be sufficient on it's own in
>>> getting delays down to levels that users are happy with for the common
>>> latency sensitive interactive traffic - VoIP, gaming and Skype for example -
>>> or are the further reductions that can be had with traffic classification
>>> and smart queuing algorithms necessary? The nicest part about codel on it's
>>> own is that it works on opaque packets - it will handle VPNs and traffic
>>> within them nicely. It gets away from all the complexity required to
>>> classify traffic in a world where traffic is often trying to hide.
>>
>> I'm more worried about how long cascades of codel code in equipment
>> will work together, add lots of traffic to the mix, just how will it
>> behave then?
>
> Dunno. I look forward to finding out.
>
> I put up debian packages of the kernel for ubuntu 12.4 here:
>
> http://huchra.bufferbloat.net/~d/codel/linux/
>
> You'll need to build your own iproute2 from the current (v12) patch set.
>
> Basic tests are throttling down your network card to like 100Mbit and
> trying it, unless you have major cpu that can saturate gigE or higher.

Um, 'major' cpu is not required. (I spend too much time on relatively
lame embedded hardware.) Almost any box made in the last 5 years can
run at gigE+.

However, there are other reasons (like ease of packet captures, the
core targets of this being uplinks from consumer boxes running at
.1-20Mbit, etc., to run slower)

Seeing the scaling factors actually work is good, too. As a simple and
dramatic example, try running codel at 10Mbit, and compare it against
the default pfifo_fast.

ethtool -K eth0 TSO off
ethtool -K eth0 GSO off
ethtool -K eth0 UFO off
ethtool -s eth0 advertise 0x002 # 10Mbit. 0x008 100Mbit

some_bandwidth_test_or_tests

tc qdisc add dev eth0 root codel # optionally, add ecn

some_bandwidth_test_or_tests

>
> I'm mostly using netperf from svn head.
>
>>
>>
>> --
>>
>> Roger Jorgensen           | ROJO9-RIPE
>> rogerj@gmail.com          | - IPv6 is The Key!
>> http://www.jorgensen.no   | roger@jorgensen.no
>
>
>
> --
> Dave Täht
> SKYPE: davetaht
> US Tel: 1-239-829-5608
> http://www.bufferbloat.net



-- 
Dave Täht
SKYPE: davetaht
US Tel: 1-239-829-5608
http://www.bufferbloat.net

Re: [Bloat] The challenge

[Simon Barber]

significant queues only form where there is a bottleneck, so there 
should not be long cascades of codel actually dropping.

Simon

On 05/09/2012 12:10 PM, Roger Jørgensen wrote:
> On Wed, May 9, 2012 at 7:16 AM, Simon Barber<simon@superduper.net>  wrote:
>> One question now remains - will codel AQM be sufficient on it's own in
>> getting delays down to levels that users are happy with for the common
>> latency sensitive interactive traffic - VoIP, gaming and Skype for example -
>> or are the further reductions that can be had with traffic classification
>> and smart queuing algorithms necessary? The nicest part about codel on it's
>> own is that it works on opaque packets - it will handle VPNs and traffic
>> within them nicely. It gets away from all the complexity required to
>> classify traffic in a world where traffic is often trying to hide.
>
> I'm more worried about how long cascades of codel code in equipment
> will work together, add lots of traffic to the mix, just how will it
> behave then?
>
>
>

Re: [Bloat] The challenge

[Fred Baker]

On May 9, 2012, at 12:16 AM, Simon Barber wrote:

> One question now remains - will codel AQM be sufficient on it's own in getting delays down to levels that users are happy with for the common latency sensitive interactive traffic - VoIP, gaming and Skype for example - or are the further reductions that can be had with traffic classification and smart queuing algorithms necessary?

In my opinion, AQM is enough to get traffic into the "reasonable" range, but if you're looking for a specific SLA that might be applicable to gaming etc, you will need to do some engineering in terms of diffserv etc.

Re: [Bloat] The challenge

[Jim Gettys]

On 05/09/2012 04:06 PM, Fred Baker wrote:
> On May 9, 2012, at 12:16 AM, Simon Barber wrote:
>
>> One question now remains - will codel AQM be sufficient on it's own in getting delays down to levels that users are happy with for the common latency sensitive interactive traffic - VoIP, gaming and Skype for example - or are the further reductions that can be had with traffic classification and smart queuing algorithms necessary?
> In my opinion, AQM is enough to get traffic into the "reasonable" range, but if you're looking for a specific SLA that might be applicable to gaming etc, you will need to do some engineering in terms of diffserv etc.
> _______________________________________________
>
I used to think that, before I understood:
    1) what the web was doing (again), by ignoring the 2 old TCP
connection rule, crossed by web site "sharding".  This is why I wrote
the IW10 considered Evil draft last fall.
    2) what the NIC offload engines were doing to generate line rate
packet trains and injecting them into the net, where they can land
"spat" at the customer end.
    3) Ledbat won't help once an effective AQM is in place; the delay
it's keying off of goes away, and then it competes like Reno with
regular flows.  100 BitTorrent flows competing with your traffic can
ruin your entire day.  We get to revisit this topic.
    4) a busy 802.11 net (or using one where the range to the AP drops
the bandwidth to low rate) means even single big packets has 12
milliseconds of latency @ 1Mbps (even ignoring other 802.11 effects,
just the bit transfer time).

Even on high speed (50Mbps broadband) I see transients of > 100ms just
browsing image heavy web sites.

So while CoDel will help (a lot, particularly policing TCP so that it
will respond quickly rather than suffering the quadratic responsiveness
problem), I now firmly believe we have to probably delve into "fair"
queuing and classification if we want a low latency edge to the Internet.

This doesn't mean I believe we'll have to do all this beyond the
broadband edge box (e.g. CMTS/DSLAM/FIOS) ; but I think these and the
home network have to actually be careful.  thankfully, at the edge, you
have way more cycles/packet you can *afford* to use on such schemes.

Having an AQM that actually works well enough to be "on" by default will
help most of the other instances of bloat I know of elsewhere, but the
edge, it's a different story....
                        - Jim

Re: [Bloat] The challenge

[Jonathan Morton]

On 9 May, 2012, at 4:04 am, Dave Taht wrote:

> Both the acm queue article and jim's blog entry this morning were way
> above mensa's standards.

Does that mean we're allowed to feel extra smart if we understood it anyway?  :-)

> Nobody has attempted to explain the elegant simplicity of the
> algorithm itself in the inverse sqrt however!  I have a good grip on
> it, and am trying, but can barely explain it to myself. Anyone else
> care to dig through the codel code and try to put it into english?

Sounds like fun!

I have a suspicion myself of what the quantitative reasoning behind the inverse sqrt might be, but I also suspect that such details are much less important than some of the *qualitative* properties of the algorithm.  Most likely the people that most need to be convinced will respond better to that than to hard maths anyway.

I think however that everyone has missed the single most important property: the fact that drops occur on *dequeue* rather than enqueue, and the result that this keeps the "resonant frequency" of each flow near the physical RTT by minimising the delay between a packet drop and the TCP's detection of and response to it.

It is counter-intuitive to keep a queue filled with packets that you might drop later - as an engineer you tend to think it is more efficient to drop a packet *before* it starts to consume space in your precious queue.  This is a good deal of what needs to be solved in wireless drivers - there is a wrong assumption in there that dropping at the tail is all that is needed, and that leads to wrong design decisions.

Tail-drop and RED drop on enqueue (at tail), not dequeue (at head), so the missing packet cannot be detected by the TCP until it's "bubble" has passed through the queue.  This sets the resonant frequency lower than the true RTT and delays the TCP's response, so the queue remains overfilled for longer (triggering extra packet drops which require extra recovery) and recovery (through retransmission) also takes longer and is less reliable.

Another point that might be missed by people naively reading the paper - as opposed to regular readers of AQM literature - is that "drop" can actually mean "mark with ECN".  Looking at the code, ECN is indeed used when appropriate.  This is good because it signals the TCP without forcing a retransmission - and without "wasting" the space in the queue occupied by the packet.  This is a good reinforcement of the principle that tail-dropping is no longer the right choice.

Important property #3 is that the queue responds immediately when it's length decreases below the threshold, by stopping the marking/dropping process entirely.  This helps to maintain the high-frequency signal (of "too fast" versus "slow enough") to the TCPs.  The response to exceeding the threshold is slower, but only to the extent of avoiding over-reaction to a natural burst of traffic.

Now about the inverse sqrt: qualitatively, it is just a convenient method of gradually varying the mark/drop rate in terms of a time interval rather than a packet count interval.  The longer the queue remains overfull - controlled by the number of mark/drop events that have occurred - the higher the marking/dropping rate gets.  If the queue then empties (and stays empty-ish for a few RTTs), the rate is reset.  Meanwhile, if the queue regularly oscillates between "full" and "empty" states, the marking/dropping rate is remembered so that aggressive TCPs receive the correct magnitude signal.

Now as for the *quantitative* reason behind it, it is because as the interval between drops gets shorter, the number of increments per RTT goes up because there is one increment per drop.  If the interval is shortened linearly per increment, that means it will in practice shorten exponentially faster, such that the drop rate runs away faster than the TCP can reasonably be expected to respond.  This would result in excessive drop rates and oscillatory behaviour typical of an over-sensitive control system.  By basing the drop rate on the square root of the incremented variable, the runaway behaviour is curtailed since the drop interval now shortens linearly per RTT.

Maybe a diagram or animation would help to clarify that last paragraph.  I'm fairly sure I can draw one.

So overall we have an AQM that provides a low-latency signal of appropriate magnitude to TCPs when the link is genuinely congested, and gets out of the way when it isn't.  Combined with a fair queueing discipline (eg. SFQ or QFQ), I think this will turn out to be an excellent default setting for all sorts of equipment.  What would it take to get this into a DSL modem (at either end of the link)?

 - Jonathan Morton

Re: [Bloat] The challenge

[Dave Taht]

On Wed, May 9, 2012 at 7:34 PM, Jonathan Morton <chromatix99@gmail.com> wrote:
>
> On 9 May, 2012, at 4:04 am, Dave Taht wrote:
>

> So overall we have an AQM that provides a low-latency signal of appropriate magnitude to TCPs when the link is genuinely congested, and gets out of the way when it isn't.  Combined with a fair queueing discipline (eg. SFQ or QFQ), I think this will turn out to be an excellent default setting for all sorts of equipment.  What would it take to get this into a DSL modem (at either end of the link)?

David Woodhouse tossed a copy of the paper on his machine before
getting on a plane. He's been working on a ADSL device for quite some
time. I don't know if he and his box are together, or separated.

>
>  - Jonathan Morton
>



-- 
Dave Täht
SKYPE: davetaht
US Tel: 1-239-829-5608
http://www.bufferbloat.net

Re: [Bloat] The challenge

[David Woodhouse]

[-- Attachment #1: Type: text/plain, Size: 1602 bytes --]

On Wed, 2012-05-09 at 19:37 -0700, Dave Taht wrote:
> On Wed, May 9, 2012 at 7:34 PM, Jonathan Morton <chromatix99@gmail.com> wrote:
> >
> > On 9 May, 2012, at 4:04 am, Dave Taht wrote:
> >
> 
> > So overall we have an AQM that provides a low-latency signal of appropriate magnitude to TCPs when the link is genuinely congested, and gets out of the way when it isn't.  Combined with a fair queueing discipline (eg. SFQ or QFQ), I think this will turn out to be an excellent default setting for all sorts of equipment.  What would it take to get this into a DSL modem (at either end of the link)?
> 
> David Woodhouse tossed a copy of the paper on his machine before
> getting on a plane. He's been working on a ADSL device for quite some
> time. I don't know if he and his box are together, or separated.

Separated by about five thousand miles right now; I'll be home on
Monday; awake by Tuesday. OpenWrt supports a bunch of ADSL modems,
including the shiny dual-port Traverse Geos that I'm using at home. It's
running OpenWrt trunk, and it's simple enough for me to update the
kernel. The two lines are bonded using teql, but if you put your qdisc
on the teql0 interface I don't think that should make any difference at
all. I can give accounts on a machine at my end of the line, and you can
do what you like with it as long as you don't use too much *downstream*
bandwidth between the hours of 8am and 6pm (UK time) on weekdays.

As for the *ISP* end of the link, we could talk to the ISP about that.
Their LNS isn't running Linux though; it's their own code.

-- 
dwmw2

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 6171 bytes --]

Re: [Bloat] The challenge

[Jonathan Morton]

On 10 May, 2012, at 9:35 am, David Woodhouse wrote:

>>> So overall we have an AQM that provides a low-latency signal of appropriate magnitude to TCPs when the link is genuinely congested, and gets out of the way when it isn't.  Combined with a fair queueing discipline (eg. SFQ or QFQ), I think this will turn out to be an excellent default setting for all sorts of equipment.  What would it take to get this into a DSL modem (at either end of the link)?
>> 
>> David Woodhouse tossed a copy of the paper on his machine before
>> getting on a plane. He's been working on a ADSL device for quite some
>> time. I don't know if he and his box are together, or separated.
> 
> Separated by about five thousand miles right now; I'll be home on
> Monday; awake by Tuesday. OpenWrt supports a bunch of ADSL modems,
> including the shiny dual-port Traverse Geos that I'm using at home. It's
> running OpenWrt trunk, and it's simple enough for me to update the
> kernel.

I want to buy a modem that I can put Linux on, and that supports ADSL2+ Annex M.  Where can I get one?

Vaguely acceptable solutions include CardBus or PCI/PCIe slot modems to put in a PowerBook or a PC.  I have enough spare hardware to make that work, and the lines here are underground and so not susceptible to lightning.

> As for the *ISP* end of the link, we could talk to the ISP about that.
> Their LNS isn't running Linux though; it's their own code.

I suppose the downstream side of ADSL is less vexing for now.  Eventually AQM and FQ needs to be in the DSLAM and cell tower by default, though.

I might have mentioned previously what my local cell tower is like - 30+ seconds (at 500Kbps) of tail-drop FIFO.  Yuck.

 - Jonathan Morton

Re: [Bloat] The challenge

[David Woodhouse]

[-- Attachment #1: Type: text/plain, Size: 1421 bytes --]

On Thu, 2012-05-10 at 09:54 +0300, Jonathan Morton wrote:
> I want to buy a modem that I can put Linux on, and that supports ADSL2
> + Annex M.  Where can I get one?

http://wiki.openwrt.org/doc/hardware/soc/soc.lantiq
http://www.traverse.com.au/productview.php?product_id=117
http://www.traverse.com.au/productview.php?product_id=120

> Vaguely acceptable solutions include CardBus or PCI/PCIe slot modems
> to put in a PowerBook or a PC. 

http://www.traverse.com.au/productview.php?range_id=2

>  I have enough spare hardware to make that work, and the lines here
> are underground and so not susceptible to lightning.
> 
> > As for the *ISP* end of the link, we could talk to the ISP about
> that.
> > Their LNS isn't running Linux though; it's their own code.
> 
> I suppose the downstream side of ADSL is less vexing for now.
> Eventually AQM and FQ needs to be in the DSLAM and cell tower by
> default, though.

Probably not the DSLAM, but the ISP's LNS (where my PPP session is
terminated, over L2TP). That's what's currently limiting my downstream
traffic to 1Mb/s per line (or whatever my crappy pieces of wet string
are actually synced at today).

If we overload the DSLAM, it drops one ATM cell out of N, which nixes
fairly much *every* IP packet by dropping a tiny part of each one, and
results in almost zero throughput. We don't let the DSLAM do
buffering :)

-- 
dwmw2

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 6171 bytes --]

Re: [Bloat] The challenge

[Justin McCann]

On Thu, May 10, 2012 at 3:02 AM, David Woodhouse <dwmw2@infradead.org> wrote:
>
> If we overload the DSLAM, it drops one ATM cell out of N, which nixes
> fairly much *every* IP packet by dropping a tiny part of each one, and
> results in almost zero throughput. We don't let the DSLAM do
> buffering :)

<tangent>
Can't they turn on Early Packet Discard or something similar? This
seems like a no-brainer.

Dynamics of TCP Traffic over ATM Networks (1994), Allyn Romanow , Sally Floyd
     http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.7647

"We investigate the performance of TCP connections over ATM networks
without ATM-level congestion control, and compare it to the
performance of TCP over packet-based networks. For simulations of
congested networks, the effective throughput of TCP over ATM can be
quite low when cells are dropped at the congested ATM switch. The low
throughput is due to wasted bandwidth as the congested link transmits
cells from `corrupted' packets, i.e., packets in which at least one
cell is dropped by the switch. We investigate two packet discard
strategies which alleviate the effects of fragmentation. Partial
Packet Discard, in which remaining cells are discarded after one cell
has been dropped from a packet, somewhat improves throughput. We
introduce Early Packet Discard, a strategy in which the switch drops
whole packets prior to buffer overflow. This mechanism prevents
fragmentation and restores throughput to maximal levels."

</tangent>

Re: [Bloat] The challenge

[David Woodhouse]

[-- Attachment #1: Type: text/plain, Size: 470 bytes --]

On Thu, 2012-05-10 at 10:25 -0400, Justin McCann wrote:
> Can't they turn on Early Packet Discard or something similar? This
> seems like a no-brainer. 

This is British Telecom we're talking about.

No, we cannot expect them to do *anything* even half sane.

The ISP has clue, and the PPP session handled by BT's DSLAM is
terminated in an L2TP session on their LNS. For the foreseeable future,
that is where any queue management has to happen.

-- 
dwmw2

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 6171 bytes --]

Re: [Bloat] The challenge

[Neil Davies]

Bit unfair to BT...

BT have architected their network so that cells loss doesn't happen. 

They pace the cell rate, on a per line basis,  in their BRASs so that 
individual DSLAM buffers are not overrun.

The PPP sessions are terminated in BT's BRAS - the ISPs LNS establishes
an L2TP tunnel to the BRAS. 

As for the sanity, we've measured other ISPs in the UK. They deliver consistently
more jitter and loss than BT's *wholesale* network.

Neil

On 10 May 2012, at 15:42, David Woodhouse wrote:

> On Thu, 2012-05-10 at 10:25 -0400, Justin McCann wrote:
>> Can't they turn on Early Packet Discard or something similar? This
>> seems like a no-brainer. 
> 
> This is British Telecom we're talking about.
> 
> No, we cannot expect them to do *anything* even half sane.
> 
> The ISP has clue, and the PPP session handled by BT's DSLAM is
> terminated in an L2TP session on their LNS. For the foreseeable future,
> that is where any queue management has to happen.
> 
> -- 
> dwmw2
> _______________________________________________
> Bloat mailing list
> Bloat@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/bloat

Re: [Bloat] The challenge

[Jonathan Morton]

On 10 May, 2012, at 10:02 am, David Woodhouse wrote:

> On Thu, 2012-05-10 at 09:54 +0300, Jonathan Morton wrote:
>> I want to buy a modem that I can put Linux on, and that supports ADSL2
>> + Annex M.  Where can I get one?
> 
> http://wiki.openwrt.org/doc/hardware/soc/soc.lantiq
> http://www.traverse.com.au/productview.php?product_id=117
> http://www.traverse.com.au/productview.php?product_id=120
> 
>> Vaguely acceptable solutions include CardBus or PCI/PCIe slot modems
>> to put in a PowerBook or a PC. 
> 
> http://www.traverse.com.au/productview.php?range_id=2

Interesting links, but just as frustrating as usual I'm afraid:

1) A long list of supported devices, without being able to filter for what's on the shelf in my local superhypermegaretailer, is not helpful.  I looked up the devices I already own, which are a reasonable selection from said shelf - no dice.  I broke open one (a Zyxel P660H-D1) that had a similar model number to a supported device - but it's totally different hardware, for which support is only "pending".

2) The Traverse links lead me to two types of devices - one of which is a router-type box which looks promising, but comes without documentation (see the next point below for why I want to read that *first*) and is not listed by *any* of the resellers linked to by the manufacturer - on any of the three continents listed.  So I can't buy it in any obvious way anyway.  (Yes, there is a chap in Belgium who says he will take requests.  I still want to read adequate documentation before imposing on him.)

3) The second type of device is a PCI card which appears to have the combination of an Ethernet NIC and a DSL modem *in series* on board.  This has no advantage, to my mind, over a standard consumer box such as I have several of already - the uplink bottleneck queue is still in a device that I can't control adequately, and which does not directly exert back-pressure on the Linux network stack.

So I repeat my question: where can I reliably go and buy a DSL modem that I can put Linux on?  It probably helps to mention that I'm in Finland, so a European (or at least British) reseller is preferable.


On the plus side, I did manage to get my PowerBook based router/firewall working again, so I've put my CPE back into bridge mode and suddenly the Internet works properly again.  Yay.  But I still have to manually configure HTB to match the link rate of the modem if I wan to control the queue.  That's the problem I really want to solve by putting Linux into the modem itself.

So I did some quick subjective tests using HTB/SFQ and HTB/CoDel - I'd like to try HTB/fq_codel too.  No packet classification going on here, traffic is traffic, let's make our modem devices as dumb as possible, but no dumber.  Bandwidth limits applied both upstream and down - I'm currently running on a simulated decade-old ADSL1 link at 1M/256K, but I can and have easily changed that to 128K/128K to simulate ISDN.

CoDel seems to cope quite well with everything I throw at it, keeping the link responsive.  However, so does SFQ - at least from a user perspective.  Looking at packet traces, it is immediately clear that SFQ still allows individual flows to run very unresponsive, with SACK flags maxed out for many seconds at a time.  CoDel achieves similar responsiveness (SSH remains essentially usable at 128K under multiple load, which is impressive) but does so by dropping several percent of all packets.

The fact that it is dropping packets rather than ECN-marking them suggests that I'm still missing something in my network setup, so I need to figure out what that is.  Even so, the flow recovers (by retransmission) within a dozen packets even over the real Internet, which is considerably faster than SFQ and gives the application smoother data delivery once the window size has grown beyond the buffer size.

With either CoDel or SFQ on the bottleneck queue, even 1M/256K feels fast, subjectively.  Objectively, I can still observe Steam taking 10x as long to download a game update than usual, or some YouTube videos no longer streaming in realtime (because they require 5Mbps for that), but those are expected.  Plain old Web browsing, e-mail, posting on forums (including reasonably sized photos) and software updating works smoothly and unobtrusively, even at a tenth of my usual bandwidth in either direction.

At ISDN speeds, a few problems start to appear with applications that have come to rely on always-on broadband characteristics.  Linux Mint has decided to download megabytes of software catalogue updates every hour by default, which consumes a large fraction of available bandwidth - I soon cut that back to every 12 hours.  No real problems emerged with SFQ or CoDel though.  Running with just HTB/FIFO, SSH was hilariously unusable as soon as any load was put on the link in either direction, but either option solved that almost entirely.

I really want to try combining CoDel and SFQ.

 - Jonathan Morton

Re: [Bloat] The challenge

[David Woodhouse]

[-- Attachment #1: Type: text/plain, Size: 1174 bytes --]

On Mon, 2012-05-14 at 10:27 +0300, Jonathan Morton wrote:
> 
> 2) The Traverse links lead me to two types of devices - one of which
> is a router-type box which looks promising, but comes without
> documentation 

linitx.com can get the Geos although it's not listed on their web site.
And the Solos PCI card *is* listed: http://linitx.com/product/12606

> 3) The second type of device is a PCI card which appears to have the
> combination of an Ethernet NIC and a DSL modem *in series* on board. 

You want the dual-port Solos, not the older Pulsar. It is an ATM device
(well, two ATM devices), properly supported by the upstream kernel via
drivers/atm/solos-pci.c

The Geos is just one (or two) of those on a Geode motherboard.

> So I repeat my question: where can I reliably go and buy a DSL modem
> that I can put Linux on?  It probably helps to mention that I'm in
> Finland, so a European (or at least British) reseller is preferable. 

If the Geos or Solos are too expensive, I'd be looking for other ADSL
devices supported by OpenWrt. Probably Lantiq-based. The Netgear
DGN3500B perhaps (see recent traffic on openwrt-devel).

-- 
dwmw2

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 6171 bytes --]