FQ-CoDel - Join Me in this Bounty

[AhnHEL]

Pledging $20 to getting FQ-CoDel placed on top of the development TO DO List.  Hoping others will join in, considering increased interest in this feature.

https://forum.pfsense.org/index.php?topic=87931.0

https://forum.pfsense.org/index.php?topic=88503.0

https://forum.pfsense.org/index.php?topic=88162.msg501320#msg501320

[Nullity]

Should we wait for "cake" to be finalized?

Here is a quote from the "Known Issues" section of this site: http://www.bufferbloat.net/projects/codel/wiki/Wiki/

At very low bandwidths (e.g. .5Mbps) on ADSL, we're having to play with the target; Kathie did not have to in her simulations. This is due to inevitable buffering in htb or in the device driver. We have a version under development that does bandwidth limiting without buffering an extra packet, called cake. It's looking good so far.

Here is a mailing-list post regarding the current state of "cake": https://lists.bufferbloat.net/pipermail/cerowrt-devel/2015-March/004243.html

I am unsure whether cake applies to Linux or all codel implementations.

[AhnHEL]

@Nullity:

Should we wait for "cake" to be finalized?

Thank you for that Nullity

FQ-CoDel has been out since March of 2014 so I think it should be implemented in pfSense as an update asap since it is the current version of CoDel in use.

Cake, as it states in your link is still in development.  I didnt see a possible release date.  Hopefully by then maybe it can be updated again as a drop in replacement to FQ-CoDel.

I'll maintain my offer of the Bounty.

[Nullity]

@AhnHEL:

@Nullity:

Should we wait for "cake" to be finalized?

Thank you for that Nullity

FQ-CoDel has been out since March of 2014 so I think it should be implemented in pfSense as an update asap since it is the current version of CoDel in use.

Cake, as it states in your link is still in development.  I didnt see a possible release date.  Hopefully by then maybe it can be updated again as a drop in replacement to FQ-CoDel.

I'll maintain my offer of the Bounty.

I am very much in favor of updating our CoDel implementation, but I want to make sure we are spending our time/money wisely.

If you look at the first link in your OP, it shows SFQ performs almost as well as fq_codel. We have our own implementation of an SFQ, FAIRQ. Considering that we may only gain a slight advantage over FAIRQ by implementing fq_codel, I say we wait for cake.

Currently you can even choose FAIRQ then check the "Codel Active Queue" box, giving practically Fair Queue Codel. (I am unsure how well this actually functions.)

[tuffcalc]

@Nullity:

@AhnHEL:

@Nullity:

Should we wait for "cake" to be finalized?

Thank you for that Nullity

FQ-CoDel has been out since March of 2014 so I think it should be implemented in pfSense as an update asap since it is the current version of CoDel in use.

Cake, as it states in your link is still in development.  I didnt see a possible release date.  Hopefully by then maybe it can be updated again as a drop in replacement to FQ-CoDel.

I'll maintain my offer of the Bounty.

I am very much in favor of updating our CoDel implementation, but I want to make sure we are spending our time/money wisely.

If you look at the first link in your OP, it shows SFQ performs almost as well as fq_codel. We have our own implementation of an SFQ, FAIRQ. Considering that we may only gain a slight advantage over FAIRQ by implementing fq_codel, I say we wait for cake.

Currently you can even choose FAIRQ then check the "Codel Active Queue" box, giving practically Fair Queue Codel. (I am unsure how well this actually functions.)

Ok… so I changed my WAN traffic shaper to FAIRQ, limited to 95% of my upstream bandwidth, and created one default queue with codel active queue & default queue checked (nothing else checked and nothing else entered, i.e. no bandwidth limit) . It seems to be keeping my pings very low even on a fully saturated uplink (even lower than just using codel - about 18ms using my ISP's speedtest server).

My goals are: (i) ease of setup (I don't want to set up a bunch of queues); and (ii) keep pings as low as possible when the uplink is fully saturated.  This new FAIRQ/Codel setup seems to do the trick, even when I drop the uplink bandwidth limit to less than 500kbps (I have one site that is on a slow DSL connection - hence wanting fq_codel that can also deal with slow links).

Would appreciate it if some of you guys could also test and verify.

Cheers

[Nullity]

Thanks for testing, tuffcalc! :)

I will get some results to you by this weekend.

Being that FAIRQ makes more of an impact as the number of simultaneous streams increases, properly testing it will not be easy. Well, I guess you could share a torrent… then consistency becomes a problem. Anyway, I will test a single stream for now.

[Harvy66]

It looks to me that sch_cake is actually a traffic shaper, like HFSC, while fq_codel is strictly an AQM. fq_codel could still be useful because I don't think you'll be able to use sch_cake with HFSC, but you should be able to use fq_codel with HFSC.

I wonder if sch_cake will support configurable sub-queues or it it's entirely supposed to be used as a "no knobs" schedulers that has codel logic built in.

With the limited information in the mailing list, it sounds like sch_cake may not let the end user actually configure queue bandwidth. While the scheduler still needs to know the link bandwidth, it's main goal is to maintain low latency and to fairly distribute bandwidth while maintain low latency. It does understand Diffserv, but still "no knobs". It described high priority traffic as always low bandwidth, which may not be good for all situations, like where "high priority" bandwidth requires a large portion of the link's bandwidth, like a game or VoIP server. Or a 150man LoL LAN party.

[Nullity]

@Harvy66:

It looks to me that sch_cake is actually a traffic shaper, like HFSC, while fq_codel is strictly an AQM. fq_codel could still be useful because I don't think you'll be able to use sch_cake with HFSC, but you should be able to use fq_codel with HFSC.

I wonder if sch_cake will support configurable sub-queues or it it's entirely supposed to be used as a "no knobs" schedulers that has codel logic built in.

With the limited information in the mailing list, it sounds like sch_cake may not let the end user actually configure queue bandwidth. While the scheduler still needs to know the link bandwidth, it's main goal is to maintain low latency and to fairly distribute bandwidth while maintain low latency. It does understand Diffserv, but still "no knobs". It described high priority traffic as always low bandwidth, which may not be good for all situations, like where "high priority" bandwidth requires a large portion of the link's bandwidth, like a game or VoIP server. Or a 150man LoL LAN party.

That is a bunch of assumptions…

[Harvy66]

Assumptions, yes, but good questions to investigate. Or at least I think so.

[Nullity]

@tuffcalc:

@Nullity:

@AhnHEL:

@Nullity:

Should we wait for "cake" to be finalized?

Thank you for that Nullity

FQ-CoDel has been out since March of 2014 so I think it should be implemented in pfSense as an update asap since it is the current version of CoDel in use.

Cake, as it states in your link is still in development.  I didnt see a possible release date.  Hopefully by then maybe it can be updated again as a drop in replacement to FQ-CoDel.

I'll maintain my offer of the Bounty.

I am very much in favor of updating our CoDel implementation, but I want to make sure we are spending our time/money wisely.

If you look at the first link in your OP, it shows SFQ performs almost as well as fq_codel. We have our own implementation of an SFQ, FAIRQ. Considering that we may only gain a slight advantage over FAIRQ by implementing fq_codel, I say we wait for cake.

Currently you can even choose FAIRQ then check the "Codel Active Queue" box, giving practically Fair Queue Codel. (I am unsure how well this actually functions.)

Ok… so I changed my WAN traffic shaper to FAIRQ, limited to 95% of my upstream bandwidth, and created one default queue with codel active queue & default queue checked (nothing else checked and nothing else entered, i.e. no bandwidth limit) . It seems to be keeping my pings very low even on a fully saturated uplink (even lower than just using codel - about 18ms using my ISP's speedtest server).

My goals are: (i) ease of setup (I don't want to set up a bunch of queues); and (ii) keep pings as low as possible when the uplink is fully saturated.  This new FAIRQ/Codel setup seems to do the trick, even when I drop the uplink bandwidth limit to less than 500kbps (I have one site that is on a slow DSL connection - hence wanting fq_codel that can also deal with slow links).

Would appreciate it if some of you guys could also test and verify.

Cheers

I tested but I got poor results and do not know why. I will retest later, perhaps after defaulting the config.

Change of subject… Cake is ambitious. Egress and ingress shaping, perhaps ADSL ATM tuning... all sorts of goals, and all while being simple for the user to setup. Dave is awesome.

[mcwtim]

I'll pledge $100 to getting fq_codel added given how broken the current codel implementation is.

[Harvy66]

@Nullity:

@Harvy66:

It looks to me that sch_cake is actually a traffic shaper, like HFSC, while fq_codel is strictly an AQM. fq_codel could still be useful because I don't think you'll be able to use sch_cake with HFSC, but you should be able to use fq_codel with HFSC.

I wonder if sch_cake will support configurable sub-queues or it it's entirely supposed to be used as a "no knobs" schedulers that has codel logic built in.

With the limited information in the mailing list, it sounds like sch_cake may not let the end user actually configure queue bandwidth. While the scheduler still needs to know the link bandwidth, it's main goal is to maintain low latency and to fairly distribute bandwidth while maintain low latency. It does understand Diffserv, but still "no knobs". It described high priority traffic as always low bandwidth, which may not be good for all situations, like where "high priority" bandwidth requires a large portion of the link's bandwidth, like a game or VoIP server. Or a 150man LoL LAN party.

That is a bunch of assumptions…

I forgot about this. I've been reading the bufferbloat.net archives and they do mention many times that cake has traffic shaping built in and is meant to be the traffic shaper. This means it cannot be used in conjunction with HFSC. Their goals seem to be to tightly couple the shaper with the AQM which gives them a lot more information and better scheduling. The down side is cake seems to have a lot more corner cases than fq_codel, it also means you can't tag and shape different traffic types like you can with HFSC.

I would still prefer to use HFSC+fq_codel instead of just cake. I want to actually shape my traffic, not just make sure it's "fair".

Some of the discussions about making making changes to cake are around getting bufferbloat to some really really low single digit milliseconds or possible fractional. to me that seems like pure overkill to give up the configurability of HFSC. Cake does have some stuff that makes it work better with the scheduling difference between DSL, Cable, and ATM. I guess fq_codel doesn't do as well when packets are grouped/batched and bursted and the timings are in tens of milliseconds. I guess that explains why my first hop for cable was almost always 10ms+ no matter what.

[Nullity]

It seems like cake depends on many Linux-only features.
I doubt cake will ever be ported to *BSD.

FQ_CODEL, or a proper combining of FAIRQ+CODELQ (CoDel seperatey applied on a per hash basis), are our best hope.

Anyone know what $$$ goal we should be aiming for?

[dtaht]

A string of messages on this thread need corrections:

@AhnHEL : 1) fq_codel entered the linux kernel may 11, 2012, not march 2014.

2. Codel is the drop (aqm) algorithm. FlowQueue is the fair queuing algorithm. The two, while tightly intertwined in the fq_codel code should be thought of as two separate things, that evolve somewhat independently. It is possible to have a sfq+codel,drr+codel,wfq+codel… (in fact, these all exist) or a sfq+red,fq+pie (both of these exist also) variant of these combinations. As near as I can tell the pfsense FAIRQ is sfq-like, and the combination of FAIRQ + codel is pretty close to what we did with fq_codel.

https://tools.ietf.org/html/draft-ietf-aqm-codel-01

https://tools.ietf.org/html/draft-hoeiland-joergensen-aqm-fq-codel-01

One of my struggles is also to get people to not conflate the added shapers' behavior on top of these. It is the soft rate limiting in hfsc/htb etc that eats all the cpu, not these algorithms. In the cases where you can run at line rate (or hardware flow control is in use) the new aqms (pie and codel) do GREAT with no software rate limiting needed.

3. Yep, there is no release date for cake. And funding runs out next month.

4. @Nullity: "If you look at the first link in your OP, it shows SFQ performs almost as well as fq_codel. We have our own implementation of an SFQ, FAIRQ. Considering that we may only gain a slight advantage over FAIRQ by implementing fq_codel, I say we wait for cake."

there are two considerations - interflow latency ( which FQ helps ) and within a flow latency (which aqm helps). Measuring the former is fairly easy with the tools like fq_codel, the dslreports test, etc. Measuring the latter involves taking apart packet captures.

I would certainly like to be able to measure how well FAIRQ + codel functions. Flaws I can see in the combination are a much larger outside packet limit, a smaller number of potential hash slots, and per-packet fairness has some flaws over byte fairness. Still it does look like a viable combination for y'all.

We are always encouraging folk to install the tools we use to measure bufferbloat (https://flent.org) on their systems, and measure. We have a few billion machines to fix and it helps to not have to poke into them all - and to find champions to drive their favorite OSes to do more of the right thing(s).

@ Harvy66 - no, cake contains a traffic shaper (like htb, not hfsc), and it can be on or off. it also contains the latest fq and codel ideas. If you could express what you want (or have) for a configuration we'd gladly discuss it on the cake list. We have "modes" where we can allocate bandwidth amongst up to 8 classes of queues, and it is very easy to add a new "mode" - if only we knew what modes were desirable.

It is my hope to find (far) less than 20 modes that cover 99% of all use cases.

"The down side is cake seems to have a lot more corner cases than fq_codel, it also means you can't tag and shape different traffic types like you can with HFSC." -

the hope it is has less corner cases than fq_codel did (notably it works down to 64kb bandwidth with no tuning), far less than sqm-scripts did (for atm etc),

... and a head to head comparison with what people actually do with HFSC seems to be increasingly needed.

[dtaht]

In terms of the bounty problem:

fq_codel was written in a single saturday afternoon by "net ninja" eric dumazet, who had a flash of insight (after about 9 months of work on predecessors) about how to use DRR instead of SFQ to solve all the remaining problems we had in one go. It, like codel before it, took about a week to have the biggest bugs wrung out and for it to go kernel mainline, and there has been a steady evolution of incremental improvements since, based on ever bigger data sets against more and more hardware and flow types.

There are several things that I would like to change about fq_codel (notably using byte, rather than packet limits) that are constrained by the existing API, and this is partially why we have been (after 2 years of doing one-off alternatives) trying to wedge all the best ideas into one more testable-at-scale set of algorithms, currently called cake.

Not knowing enough about bsd myself to port the mere ~300 lines of fq_codel code, bootstrapping myself up to get it to work would take several weeks, and to clean up and polish the work several more. But it is worse than that, I am informed, for example, that the ALTQ infrastructure is going away in a future release of freebsd. Finding that BSD expert to partner up with would shave quite a bit of bootstrap time - honestly it's a days work to port (and a week to polish) this tiny amount of code if that someone could be found.

Otherwise, the available bounty of about 150 dollars? is about 59,850 dollars short of the actual engineering time it would take to do.

My emphasis has therefore been to find an existing BSD expert to partner up with ( and/or a grad student with infinite spare time), a company that cares enough about bsd to sponsor the work, and to fully document the algorithms in ietf drafts.

But it is worse than that in that there are several known unknowns in BSD that would take more time to code up - notably an efficient timestamping facility is needed by codel (which seems to be the case on pfsense but nobody has benchmarked higher rates), and some gnarly IP header hashing functions may or may not exist.  And I have no clue whatsoever what the replacement for ALTQ will look like.

So as much as I like the idea of improving pfsense and am willing to help, finding and funding that BSD expert would be the first barrier.

[Harvy66]

I know ALTQ is the scheduler part, do changes to it break anything with the queues? If it doesn't, then work done for fq_codel now won't be lost with ALTQ changes.

With ALTQ, packets can be assigned to queues for the purpose of bandwidth control. The scheduler defines the algorithm used to decide which packets get delayed, dropped or sent out immediately

[cplmayo]

I would love to see fq_codel or better yet an implementation of cake_codel into PfSense. I toyed with IPFire with the hope of getting these features but found overall that IPFire was very weak when compared to PfSense and choose to stick with it regardless of QoS Limitations that I saw. currently running Fairq with Codel sub queues and I am getting about the best reduction in buffer bloat that I have seen.

Depending on need I would be more than willing to throw at least $100 into the bounty to get a native implementation of either fq_codel or cake_codel into this distro.

[Nullity]

fq_codel is already coming to FreeBSD (and most likely pfSense), but it will not be an ALTQ queueing discipline, it will instead be implemented within "dummynet", which is what pfSense calls "limiters".

Whether this will be useful to us, I do not know, but it sure seems like good news to me.

http://comments.gmane.org/gmane.os.freebsd.devel.net/47124

[cplmayo]

@Nullity:

fq_codel is already coming to FreeBSD (and most likely pfSense), but it will not be an ALTQ queueing discipline, it will instead be implemented within "dummynet", which is what pfSense calls "limiters".

Whether this will be useful to us, I do not know, but it sure seems like good news to me.

http://comments.gmane.org/gmane.os.freebsd.devel.net/47124

Implementing fq_Codel in the limiters should work well and be easy to setup. Also I think it will allow the limiters to function better. I still think that cake_Codel is the future and hope it will be implemented in BSD.

I have tried HFSC, PRIQ, and CBQ all of these did a good job of keeping my internet running smoothly but bufferbloat was always a problem. I have since found that FairQ with Codel as the scheduler I do not have to limit my Bulk traffic and my network performance is largely unaffected.

[Nullity]

@cplmayo:

@Nullity:

fq_codel is already coming to FreeBSD (and most likely pfSense), but it will not be an ALTQ queueing discipline, it will instead be implemented within "dummynet", which is what pfSense calls "limiters".

Whether this will be useful to us, I do not know, but it sure seems like good news to me.

http://comments.gmane.org/gmane.os.freebsd.devel.net/47124

Implementing fq_Codel in the limiters should work well and be easy to setup. Also I think it will allow the limiters to function better. I still think that cake_Codel is the future and hope it will be implemented in BSD.

I have tried HFSC, PRIQ, and CBQ all of these did a good job of keeping my internet running smoothly but bufferbloat was always a problem. I have since found that FairQ with Codel as the scheduler I do not have to limit my Bulk traffic and my network performance is largely unaffected.

Cake will never come to BSD. Cake is deeply entrenched in Linux-only features. Many of the features do not exist at all in BSD, so the whole porting effort would be very complicated and/or expensive.