Subject: [aqm] References on AQM test results and fq_nocodel

From: "Francini, Andrea (Andrea)" <[email-masked]>
Date: Mon, 13 Apr 2015 15:40:41 +0000

I need help finding a couple of references:

1.       Besides the results in Toke's ICCRG presentation at IETF 91 in November 2014 (http://www.ietf.org/proceedings/91/slides/slides-91-iccrg-4.pdf), where can I find  other comprehensive comparisons of AQM implementations for Linux (or any other non-simulated system that handles real packets)?

2.       In Toke's slides, the fq_nocodel scheme appears to be never worse than fq_codel (or any other AQM in those tests), except for the VoIP delay plot of slide 12. Besides the Linux code, is there anywhere a description of the fq_nocodel scheme?

Thanks!

Andrea

---

From: Michael Welzl <[email-masked]>
Date: Mon, 13 Apr 2015 15:48:19 +0000

> On 13 Apr 2015, at 17:40, Francini, Andrea (Andrea) <[email-masked]> wrote:
> 
> 1.       Besides the results in Toke’s ICCRG presentation at IETF 91 in November 2014 (http://www.ietf.org/proceedings/91/slides/slides-91-iccrg-4.pdf), where can I find  other comprehensive comparisons of AQM implementations for Linux (or any other non-simulated system that handles real packets)? 

I think there should be quite a number by now - anyway one relatively recent evaluation study is:
http://heim.ifi.uio.no/~michawe/research/publications/infocom-gi14.pdf

Cheers,
Michael

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Mon, 13 Apr 2015 17:53:56 +0200

Hi Andrea

> 1. Besides the results in Toke’s ICCRG presentation at IETF 91 in
> November 2014
> (http://www.ietf.org/proceedings/91/slides/slides-91-iccrg-4.pdf),
> where can I find other comprehensive comparisons of AQM
> implementations for Linux (or any other non-simulated system that
> handles real packets)?

The data underlying my experiments are available from here:
http://www.cs.kau.se/tohojo/modern-aqms/ -- that page also has links to
the test scripts used to run the experiments. The paper is still under
submission, so can't link that, sadly, but I can share a copy with you
privately if you are interested.

> 2. In Toke’s slides, the fq_nocodel scheme appears to be never worse
> than fq_codel (or any other AQM in those tests), except for the VoIP
> delay plot of slide 12. Besides the Linux code, is there anywhere a
> description of the fq_nocodel scheme?

Well, fq_nocodel is basically the term I use for fq_codel configured so
as to disable the CoDel algorithm (i.e. the target and/or interval is
set to 100 seconds so the algorithm never triggers). As such, it doesn't
have a description outside of my paper, but you can read the fq_codel
draft and ignore everything it says about CoDel, I suppose :)

Also, note that configuring fq_codel in this way in Linux is not optimal
in terms of CPU use: it deliberate triggers the overflow drop mechanism,
which does a linear search through all configured queues, eating up 4k
of cache on every drop. If your test router is sufficiently
CPU-over-provisioned (a modern x86 counts as this for <=1Gbit speeds)
this doesn't affect performance, but I wouldn't recommend it on a tiny
MIPS processor, for instance. (Oh, and this limitation is specific to
the current implementation, and could easily be fixed if anyone wanted
to; the overflow mechanism was meant as a backup, and so wasn't
optimised like, say, the SFQ was).

-Toke

---

From: "Francini, Andrea (Andrea)" <[email-masked]>
Date: Mon, 13 Apr 2015 17:24:27 +0000

Thank you Toke (and Michael) for the pointers.

Just based on the results of the IETF 91 slides, it would seem that disabling CoDel in fq_codel helps in a variety of cases (most evidently in the fairness plots), and only causes some increase in VoIP delay at relatively low link rates (the fq_codel and fq_nocodel curves do overlap in the 100/100 Mbps case of slide 34). 

CoDel's effort to limit the queuing delay appears well motivated when there is only one queue (e.g., to shield VoIP from the delay induced by bulk-transfer or video traffic), but when multiple queues are available the net gain of the effort is unclear. I suspect the same may happen with the flow-queue version of PIE.

Is this just because the set of tests in the slides does not include one that clearly exposes the superiority of fq_codel over fq_nocodel? And what would that test look like?

Andrea

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] 
Sent: Monday, April 13, 2015 11:54 AM
To: Francini, Andrea (Andrea)
Cc: [email-masked]
Subject: Re: [aqm] References on AQM test results and fq_nocodel

Hi Andrea

-Toke

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Mon, 13 Apr 2015 19:41:14 +0200

"Francini, Andrea (Andrea)" <[email-masked]> writes:

> CoDel's effort to limit the queuing delay appears well motivated when
> there is only one queue (e.g., to shield VoIP from the delay induced
> by bulk-transfer or video traffic), but when multiple queues are
> available the net gain of the effort is unclear. I suspect the same
> may happen with the flow-queue version of PIE.

Yep, this has been my conclusion as well, and the test results on those
slides are what convinced me of it: flow queueing is much more important
than AQM, for most applications. However, note that in the tests I have
run, the latency is measured by a separate flow; the latency of the
packets making up the bulk flows is not measured. For most common
traffic, this is fine, but there can be exceptions where you have a flow
that has enough traffic to induce a queue, but which also requires low
latency throughout. Adaptive video codecs for real-time media is a
notable example. For those, having the AQM is nice.

Also, having the AQM in place guards you against hash collisions. With
the AQM in place, you degrade to its performance, whereas without,
you're basically back to a large, dumb FIFO queue. fq_codel as it exists
now is unfortunately not immune to those; we're working (in the
Bufferbloat community) on an improved queueing discipline that solves
this in most cases. See http://www.bufferbloat.net/projects/codel/wiki/Cake

> Is this just because the set of tests in the slides does not include
> one that clearly exposes the superiority of fq_codel over fq_nocodel?
> And what would that test look like?

Well, see above. Adaptive real-time video in particular is under-tested,
in part due to a lack of good tools to generate traffic. Also, if you
want to see fq_* break, try sticking all your flows in an encrypted VPN :)

-Toke

---

From: Jim Gettys <[email-masked]>
Date: Mon, 13 Apr 2015 14:42:32 -0400

Note that having no AQM at all, and only flow queuing (e.g. fq_nocodel),
leaves some applications in dire straights, being both interactive, and
using a single TCP stream (for example, you really don't want to run my
favorite window system, X, over a bloated link without some form of
mark/drop algorithm to keep TCP behaving sanely).  And with RTT's of those
applications growing without bounds, they become really insane charging
elephants.  Ironically, I used to be able to run X over intercontinental
links (e.g. 150ms RTT's); trying that on today's bloated edge puts you in a
world of hurt.

So both a mark/drop algorithm and flow queuing are needed to really solve
the problem, though as Toke says, fq makes the biggest difference if you
only pick one. But this is really more of an artifact of the web's abuse of
TCP; tons of short, transient connections...
                                            - Jim

On Mon, Apr 13, 2015 at 1:41 PM, Toke Høiland-Jørgensen <[email-masked]>
wrote:

> this in most cases. See
> http://www.bufferbloat.net/projects/codel/wiki/Cake
>
> _______________________________________________
> aqm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/aqm
>

---

From: Simon Barber <[email-masked]>
Date: Tue, 14 Apr 2015 08:36:45 -0700

One problem with fair queueing is that it can be gamed. By opening multiple 
flows you achieve unfair priority. Part of Codel or PIE's beauty is that 
they are blind to the traffic, only reacting to the externally visible 
characteristics. This stems from the question 'what is a flow?'. There is 
no easy answer to this question, so Codel and PIE intentionally avoid the 
question.

Of course in many practical situations some simple assumptions about what a 
flow is do work, and in those situations fair queueing performs very well. 
It's important to keep in mind the limitations though. Fair queueing is not 
a panacea.

Simon

Sent with AquaMail for Android
http://www.aqua-mail.com

---

From: "De Schepper, Koen (Koen)" <[email-masked]>
Date: Tue, 14 Apr 2015 15:39:56 +0000

> However, note that in the tests I have
> packets making up the bulk flows is not measured.

I’m also interested to see how interactive adaptive applications are performing on the different FQ schemes. For most of the time, such an application will behave as a greedy flow (always data available), while the generation of application data is made fast adaptive to the available throughput experienced by the sender application. Obviously the interactivity is enhanced when the network has a very low latency, which is not provided by the FQ_noCodel scheme. Reporting the self inflicted delay on greedy flows might be a good measurement to additionally report in the test suites, so its impact on greedy interactive applications can be estimated.

> the problem, though as Toke says, fq makes the biggest difference if you only pick one.

I expect also that the advantage of FQ in general will becomes less relevant if the queue of all flows in the network are very small and even most of the time empty. This is what you see already when a low latency configured AQM is combined with FQ. The lower the latency in the queues the less the impact of FQ. FQ might still have an advantage in case of dynamics where a queue build up cannot be avoided.

Koen.

From: aqm [mailto:[email-masked]] On Behalf Of Jim Gettys
Sent: maandag 13 april 2015 20:43
To: Toke Høiland-Jørgensen
Cc: Michael Welzl; [email-masked]; Francini, Andrea (Andrea)
Subject: Re: [aqm] References on AQM test results and fq_nocodel

Note that having no AQM at all, and only flow queuing (e.g. fq_nocodel), leaves some applications in dire straights, being both interactive, and using a single TCP stream (for example, you really don't want to run my favorite window system, X, over a bloated link without some form of mark/drop algorithm to keep TCP behaving sanely).  And with RTT's of those applications growing without bounds, they become really insane charging elephants.  Ironically, I used to be able to run X over intercontinental links (e.g. 150ms RTT's); trying that on today's bloated edge puts you in a world of hurt.

So both a mark/drop algorithm and flow queuing are needed to really solve the problem, though as Toke says, fq makes the biggest difference if you only pick one. But this is really more of an artifact of the web's abuse of TCP; tons of short, transient connections...
                                            - Jim

On Mon, Apr 13, 2015 at 1:41 PM, Toke Høiland-Jørgensen <[email-masked]<mailto:[email-masked]>> wrote:

-Toke

_______________________________________________
aqm mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/aqm

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Tue, 14 Apr 2015 17:57:12 +0200

"De Schepper, Koen (Koen)" <[email-masked]> writes:

> Reporting the self inflicted delay on greedy flows might be a good
> measurement to additionally report in the test suites, so its impact
> on greedy interactive applications can be estimated.

Some sort of greedy real-time media or equivalent is definitely missing
from my suite of tests. However, that is partly due to the lack of a
good tool to do it with; preferably one that actually matches real
deployed applications (webrtc for instance), and that doesn't require
either synchronised clocks, packet dumps, or inspecting the router
queues while running.

On the page I linked to there are packet dumps available from my tests,
btw, in case anyone does want to go extract some of these figures from
them...

> I expect also that the advantage of FQ in general will becomes less
> relevant if the queue of all flows in the network are very small and
> even most of the time empty. This is what you see already when a low
> latency configured AQM is combined with FQ. The lower the latency in
> the queues the less the impact of FQ. FQ might still have an advantage
> in case of dynamics where a queue build up cannot be avoided.

Well, I haven't yet seen an AQM that can keep the queue "very small and
even most of the time empty" in the presence of (e.g.) the RRUL test.
Especially not during the period where the flows start up (or, roughly
equivalent, if the bandwidth changes very rapidly). FQ helps a lot here,
especially for the transients.

-Toke

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Tue, 14 Apr 2015 18:01:43 +0200

Simon Barber <[email-masked]> writes:

> One problem with fair queueing is that it can be gamed. By opening
> multiple flows you achieve unfair priority. Part of Codel or PIE's
> beauty is that they are blind to the traffic, only reacting to the
> externally visible characteristics. This stems from the question 'what
> is a flow?'. There is no easy answer to this question, so Codel and
> PIE intentionally avoid the question.

Sure, if we knew what the One True Queue Management Scheme that always
did the right thing was, we probably wouldn't be having this
conversation. :)

> Of course in many practical situations some simple assumptions about
> what a flow is do work, and in those situations fair queueing performs
> very well. It's important to keep in mind the limitations though. Fair
> queueing is not a panacea.

Well, my focus has primarily been "why does my internet suck so much and
what can I do to fix it". And for that (e.g. home type networks)
fq_codel is very close to a panacea.

I am well aware that there probably exists situations in which the
fq_codel assumptions do not hold up (and we do point out a couple in the
draft). However, I don't think I've ever seen someone actually
*demonstrate* (you know, with data) a scenario where fq_codel performs
worse than either Codel or PIE. If someone can point me to such a
demonstration I'll be happy to be proved wrong... :)

-Toke

---

From: Simon Barber <[email-masked]>
Date: Tue, 14 Apr 2015 09:20:06 -0700

Indeed fq_codel will work very well for many home users - especially where 
the home user can be expected to be aware of apps that might be gaming the 
system. If multiple homes are sharing a link it might not always work so well.

To construct an example where fair queueing works poorly, place a flow that 
is trying to game the system (e.g. a download performed by a download 
accelerator, launching multiple TCP streams for the single download) next 
to a bunch of flows that are opaque (e.g. Several VoIP calls through a VPN).

Simon

---

From: David Lang <[email-masked]>
Date: Tue, 14 Apr 2015 12:57:25 -0700 (PDT)

> this in most cases. See http://www.bufferbloat.net/projects/codel/wiki/Cake

do your finding still stand if you have enough different flows through the 
system that you end up with lots of flows (some of which may be bulk data) in 
each queue?

> want to see fq_* break, try sticking all your flows in an encrypted VPN :)

In this case, doesn't the router just see everything as a single flow? In which 
case there is nothing that it can do to affect priorities within that flow.

David Lang

---

From: David Lang <[email-masked]>
Date: Tue, 14 Apr 2015 13:20:26 -0700 (PDT)

> did the right thing was, we probably wouldn't be having this

if the fq portion is being gamed, how severe can the imbalance be? Is it a 
matter that if there are N flows without gaming the system, and each is getting 
1/N bandwith, then if a cheater uses M flows the cheater gets M/(N+M) of the 
bandwidth?

more importantly, is there any way short of a massive number of flows 
(essentially a DDOS), that this gaming of the system can hurt the latency of the 
other flows? or is it just the relative bandwidth of the different apps that 
suffers, and if an app is low bandwidth, but latency sensitive (i.e. VoIP), it 
won't be affected until it's "share" of bandwidth drops below the minimum it 
needs?

> demonstration I'll be happy to be proved wrong... :)

Looping back to the start of the topic, the slides apparently are being read 
that fq without codel is just as good, or better than fq_codel, so codel can be 
dropped, and only fq is needed.

Is this what you are concluding from this? Or is that a misreading of something 
(the data, your work, or me misreading this thread)?

David Lang

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Fri, 17 Apr 2015 15:53:15 +0200

David Lang <[email-masked]> writes:

> if the fq portion is being gamed, how severe can the imbalance be? Is
> it a matter that if there are N flows without gaming the system, and
> each is getting 1/N bandwith, then if a cheater uses M flows the
> cheater gets M/(N+M) of the bandwidth?

Yes, not counting hash collisions, that would be the case.

> (essentially a DDOS), that this gaming of the system can hurt the
> latency of the other flows? or is it just the relative bandwidth of
> the different apps that suffers, and if an app is low bandwidth, but
> latency sensitive (i.e. VoIP), it won't be affected until it's "share"
> of bandwidth drops below the minimum it needs?

Well, since fq_codel is hash based, if you manage to hit the same bucket
as the VoIP flow, that VoIP flow is not going to get the nice implicit
priority it would otherwise from the flow queueing. So yeah, if you,
say, send out 1000 packets at once on different UDP ports, then the VoIP
flow is going to notice. But in this case you're basically DOS'ing the
router; and FIFO queueing and pure AQMs fare pretty badly as well...

> Looping back to the start of the topic, the slides apparently are
> being read that fq without codel is just as good, or better than
> fq_codel, so codel can be dropped, and only fq is needed.
>
> Is this what you are concluding from this? Or is that a misreading of
> something (the data, your work, or me misreading this thread)?

Well, *for the tested scenarios and metrics* that is true. However,
there can be other scenarios where you will benefit from having AQM on
each of the queues. Several such hypothetical scenarios have been
mentioned in this thread. The open question, as far as I'm concerned, is
*how much* a difference it makes. I.e. exactly how much the performance
degrades if it is absent, and in which scenarios. As I said before, I
don't think anyone has ever actually tried it and produced data...

-Toke