Difference between fq_codel and FAIRQ + CoDel?



  • I've been a huge pfSense fan for years and I noticed that they implemented CoDel which should help a lot for buffer bloat/latency problems but there appears to be a newer implementation called fq_codel and another version in-development called Cake.

    Can I use FAIRQ + CoDel to achieve the same performance as fq_codel?



  • fq_codel creates a pseudo-queue for each flow (fair queueing), then applies codel to each pseudo-queue.

    fairq creates a pseudo-queue for each flow as well, but codel is applied to the whole queue, not the per flow pseudo-queues.

    This is an oversimplified explanation, of course. :)



  • Oh, HFSC (Hierarchical Fair Service Curve) is a fair queueing algorithm as well.



  • I originally just put codelq on all my interfaces and it removed the buffer bloat.

    I switched to FAIRQ + CoDel and it works just as well for buffer bloat and improved the performance of VOIP, Gaming netflix etc.



  • @pahowart:

    I originally just put codelq on all my interfaces and it removed the buffer bloat.

    I switched to FAIRQ + CoDel and it works just as well for buffer bloat and improved the performance of VOIP, Gaming netflix etc.

    With FAIRQ, did you put all traffic into 1 queue or did you use multiple queues?



  • It really depends on the implementations. FairQ in PFSense is a scheduler and you're talking about using CoDel as a child discipline. In order for FairQ to place packets into hash-buckets, it needs to buffer at least some of the packets. Whatever packets FairQ is buffering, CoDel cannot affect, but CoDel can the packets before FairQ buffers them.

    FairQ+Codel looks like this on your outgoing
    CoDel->FairQ

    To make an analogy with fq_Codel, it would look more like this
    FairQ->CoDel

    It really depends on how much buffering FairQ does. Test and see. HFSC+CoDel works well for me.

    Cake is a whole other beast. First off, it improved on fq_CoDel and uses "ways", which virtually eliminates hash collisions and allowing perfect flow isolation. Second, it is a scheduler/shaper(cannot be used as a child discipline without sacrilege) and accounts for link overhead when deciding which packet to send next, like PPPOE and DSL. Third, it supports 4 priority levels and will dynamically demote greedy flows from a higher priority to a lower priority until the flow backs off.

    They're also looking into yet another AQM called Bobbie. It acts more like a policier, thus the name, but is less aggressive than Cake. Cake is meant to shape/AQM egress. The problem is a bit different when shaping ingress because 1) you only have indirect control of the sender by signalling to back-off by marking or dropping packets 2) the data was already sent and is expensive to resend since it already traversed the Internet to get to you

    Bobbie builds on several basic concepts of Cake, but prefers to give love taps, allowing for high utilization while still keeping download bloat quite low. Cake will maintain strictly low latency, but when shaping your downloads, it drops too many packets and reduces average utilization.



  • With FAIRQ, did you put all traffic into 1 queue or did you use multiple queues?

    I used the multiple queue's as set up by the multi wan wizard and then edited each child to use codel. Buffer bloat tests are mostly A or A+ but will degrade under load at times.

    Over all still better gaming performance than codel on it's own.



  • @Harvy66:

    It really depends on the implementations. FairQ in PFSense is a scheduler and you're talking about using CoDel as a child discipline. In order for FairQ to place packets into hash-buckets, it needs to buffer at least some of the packets. Whatever packets FairQ is buffering, CoDel cannot affect, but CoDel can the packets before FairQ buffers them.

    FairQ+Codel looks like this on your outgoing
    CoDel->FairQ

    To make an analogy with fq_Codel, it would look more like this
    FairQ->CoDel

    It really depends on how much buffering FairQ does. Test and see. HFSC+CoDel works well for me.

    Can you post a link supporting that CoDel does not affect packets buffered by FAIRQ, or concisely explain what you mean? The fact that Codel can be enabled with FAIRQ seems to negate your statement.

    Your statement about the ordering is strange since both Codel and FAIRQ are implemented in ALTQ, and ALTQ is the thing that does all the buffering for queues. FAIRQ and Codel manipulate those queued packets.



  • @sofakng:

    I've been a huge pfSense fan for years and I noticed that they implemented CoDel which should help a lot for buffer bloat/latency problems but there appears to be a newer implementation called fq_codel and another version in-development called Cake.

    Can I use FAIRQ + CoDel to achieve the same performance as fq_codel?

    I just remembered that fq_codel is coming to FreeBSD. Harvy66 posted the info a few months ago.
    https://lists.freebsd.org/pipermail/freebsd-net/2015-September/043442.html

    That post mentions "dummynet" which is what pfSense refers to as limiters.

    I dunno if dummynet's fq_codel can work together with our ALTQ schedulers though…



  • @Nullity:

    @sofakng:

    I've been a huge pfSense fan for years and I noticed that they implemented CoDel which should help a lot for buffer bloat/latency problems but there appears to be a newer implementation called fq_codel and another version in-development called Cake.

    Can I use FAIRQ + CoDel to achieve the same performance as fq_codel?

    I just remembered that fq_codel is coming to FreeBSD. Harvy66 posted the info a few months ago.
    https://lists.freebsd.org/pipermail/freebsd-net/2015-September/043442.html

    That post mentions "dummynet" which is what pfSense refers to as limiters.

    I dunno if dummynet's fq_codel can work together with our ALTQ schedulers though…

    Dave Täht via lists.bufferbloat.net
    Jan 21

    On 1/20/16 8:31 AM, John Klimek wrote:

    I'm currently using pfSense on an x86 system and it's working great, but I'd like to use fq_codel and the upcoming Cake algorithm/system.

    There is work going on to finally port this stuff to BSD.



  • @Nullity:

    @Harvy66:

    It really depends on the implementations. FairQ in PFSense is a scheduler and you're talking about using CoDel as a child discipline. In order for FairQ to place packets into hash-buckets, it needs to buffer at least some of the packets. Whatever packets FairQ is buffering, CoDel cannot affect, but CoDel can the packets before FairQ buffers them.

    FairQ+Codel looks like this on your outgoing
    CoDel->FairQ

    To make an analogy with fq_Codel, it would look more like this
    FairQ->CoDel

    It really depends on how much buffering FairQ does. Test and see. HFSC+CoDel works well for me.

    Can you post a link supporting that CoDel does not affect packets buffered by FAIRQ, or concisely explain what you mean? The fact that Codel can be enabled with FAIRQ seems to negate your statement.

    Your statement about the ordering is strange since both Codel and FAIRQ are implemented in ALTQ, and ALTQ is the thing that does all the buffering for queues. FAIRQ and Codel manipulate those queued packets.

    It's a logical requirement that a scheduler or AQM have its own buffers regardless of if ALTQ also has buffers.

    https://en.wikipedia.org/wiki/ALTQ

    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.

    The schedulers responsibility is to manage the overall bandwidth allocations among the queues via scheduling and delaying.
    The child disciplines's responsibility is to provide the scheduler which packet is next for a given queue.

    Of course you can pervert some of these responsibilities a bit, like CAKE, but it can create incompatibilities among certain combinations of schedulers and child disciplines. Breaking the implicit software contract is taboo.

    By the nature of how FAIRQ works, it need to read in multiple packets and hash them into buckets, then load balance the buckets. CoDel can decide to drop packets instead of handing them off to FAIRQ, but that's about it's limit of control.

    What I'm unsure about is how many packets FAIRQ needs to read in to its buckets before it decides which packet to schedule next. It's entirely possibly that the next N packets all get hashed into the same bucket. Does it give up trying to populate all buckets once one bucket gets too backed up or the total number of buffered packets reaches some limit?

    Not that I really care because I don't use it, but how it does it's own buffer can greatly affect how much peak bufferbloat can occur. CoDel can drop delayed packets that are in its queue, but it can't drop the packets once it hands them off to FAIRQ. Well, it could, but it would require ALTQ to have a horribly complex and/or leaky abstract layer to allow arbitrary algorithms to work concurrently instead of in tandem.



  • @Harvy66:

    By the nature of how FAIRQ works, it need to read in multiple packets and hash them into buckets, then load balance the buckets. CoDel can decide to drop packets instead of handing them off to FAIRQ, but that's about it's limit of control.

    What I'm unsure about is how many packets FAIRQ needs to read in to its buckets before it decides which packet to schedule next. It's entirely possibly that the next N packets all get hashed into the same bucket. Does it give up trying to populate all buckets once one bucket gets too backed up or the total number of buffered packets reaches some limit?

    Not that I really care because I don't use it, but how it does it's own buffer can greatly affect how much peak bufferbloat can occur. CoDel can drop delayed packets that are in its queue, but it can't drop the packets once it hands them off to FAIRQ. Well, it could, but it would require ALTQ to have a horribly complex and/or leaky abstract layer to allow arbitrary algorithms to work concurrently instead of in tandem.

    Show something that supports this "hand-off" theory. I only see lots of conjecture. I have never seen any documentation detailing what you explain. It is an interesting theory but without proof, that is all this "hand-off" theory is. I would be much more hesitant to share my possibly-misinformative theories…

    For details about FAIRQ and the number of packets it needs in buckets, refer to http://gitweb.dragonflybsd.org/dragonfly.git/blob/HEAD:/sys/net/altq/altq_fairq.c#l68



  • Oh, the CoDel in 2.3 comes from FreeBSD apparently. For a while FreeBSD didn't want the extra (mbuf?) overhead that ermal's implementation added to stock, so only pfSense had codel.

    I dunno what has changed in the new(?) codel implementation.

    Anyone testing 2.3?



  • @Nullity:

    fq_codel creates a pseudo-queue for each flow (fair queueing), then applies codel to each pseudo-queue.

    fairq creates a pseudo-queue for each flow as well, but codel is applied to the whole queue, not the per flow pseudo-queues.

    Can anyone help me/us understand whether codel is applied to the entire FAIRQ queue or the individual buckets? Here's the source
    https://github.com/pfsense/FreeBSD-src/blob/devel/sys/contrib/altq/altq/altq_fairq.c
    https://github.com/freebsd/freebsd/blob/master/sys/net/altq/altq_fairq.c

    Line 611 seems to be the important spot.

    The big difference between codel & fq_codel was applying codel to individual flows in fq_codel. If our codel implementation already applied to the individual flows rather than the entire queue (all buckets aggregated), that would be a very interesting revelation…  :o

    @Harvy66, you can see in the fairq, hfsc, cbq, etc source-code that every AQM (codel, red, rio) is integrated directly into the altq code. No hand-offs.



  • @Nullity:

    @Nullity:

    fq_codel creates a pseudo-queue for each flow (fair queueing), then applies codel to each pseudo-queue.

    fairq creates a pseudo-queue for each flow as well, but codel is applied to the whole queue, not the per flow pseudo-queues.

    Can anyone help me/us understand whether codel is applied to the entire FAIRQ queue or the individual buckets? Here's the source
    https://github.com/pfsense/FreeBSD-src/blob/devel/sys/contrib/altq/altq/altq_fairq.c
    https://github.com/freebsd/freebsd/blob/master/sys/net/altq/altq_fairq.c

    Line 611 seems to be the important spot.

    The big difference between codel & fq_codel was applying codel to individual flows in fq_codel. If our codel implementation already applied to the individual flows rather than the entire queue (all buckets aggregated), that would be a very interesting revelation…  :o

    @Harvy66, you can see in the fairq, hfsc, cbq, etc source-code that every AQM (codel, red, rio) is integrated directly into the altq code. No hand-offs.

    Uhgg, those people. My expectation of quality and theory from them has been lowered. No wonder we're a backwater when it comes to getting AQMs. We need a plug-in system like the FreeBSD TCP stack.



  • @Harvy66:

    Uhgg, those people. My expectation of quality and theory from them has been lowered. No wonder we're a backwater when it comes to getting AQMs. We need a plug-in system like the FreeBSD TCP stack.

    You lost me. I thought the FreeBSD TCP/IP stack was the most respected in open-source.

    I linked both FreeBSD & pfSense source-code. The pfSense code seems practically identical to the FreeBSD code.



  • I'm still a little confused…

    It sounds like pfSense 2.3 might support fq_codel type of queueing/shaping?  …but 2.2.6 applies codel and fairq in the wrong order?



  • @sofakng:

    I'm still a little confused…

    It sounds like pfSense 2.3 might support fq_codel type of queueing/shaping?  …but 2.2.6 applies codel and fairq in the wrong order?

    The unfounded, "wrong order" theory was a red herring. Forget about it. :)

    We currently have "fair queueing" algorithms (HFSC & FAIRQ), which can use the CoDel de-bufferbloating algorithm. It is not exactly fq_codel, but it is similar. How exactly it differs, I dunno. Documentation on fq_codel's internals is available but the internals of FAIRQ+CoDel are found only in source-code, which I do not yet understand.

    We will (after 2.3) get proper fq_codel, but we have to wait for it to be completed and added to the upstream FreeBSD code before we can add it to pfSense. Though, for most ALTQ users, I think this will not be very useful, since fq_codel will be implemented in the limiters (dummynet) section of traffic-shaping will not be a traffic-shaper queueing (ALTQ) algorithm.

    I do not know how useful fq_codel (in dummynet/limiters) will be to us ALTQ users. We will just have to wait and see, I suppose…