[Cake] packet mass, ecn, and a fractional count

[Jonathan Morton]

> On 8 May, 2015, at 05:32, Dave Taht <dave.taht at gmail.com> wrote:
> 
> from observing behaviors with large numbers of flows, fq_codel derived
> algorithms start to struggle to achieve the desired delay, cake
> seemingly less so, and perhaps this is related to collisions also.
> 
> A thought would be to use a fractional (fixed point) increment to
> count rather than "1" when larger numbers of flows are present.

Given that cake handles this extreme case better than average already, I’m not particularly concerned about trying to improve it further.  Adding set-associative hashing (or red-black trees for perfect isolation, if you prefer) to other FQ qdiscs might be a better idea than fudging codel.

There’s a reasonably straightforward answer for why flow collisions might cause worse AQM behaviour.  Assume a situation with a very large number of flows, so adding one more flow doesn’t change the throughput of existing flows much.  Now assume that most queues have just one flow assigned, but there are a few with two each.  (Ignore the possibility of more, for simplicity.)

The flows assigned to the doubled queues will have half the throughput each, compared to those in single queues.  This also means that only half the packets are available for sending congestion signals on, and since codel marks packets on a fixed schedule once it is triggered, each flow will therefore receive only half the congestion signals.  *BUT* each flow still gets the same IW, so a doubled queue is twice as full as singles to begin with.

So with perfect flow isolation (and a separate codel per queue), codel’s signalling rate naturally scales with the number of flows.  With collisions, that doesn’t happen so reliably; it is at best a sublinear scaling.  Without FQ at all, representing the pessimal collisions case, codel has to wait for its signalling rate to grow over time in order to match the number of flows, so it won’t react as quickly to an abruptly imposed load.

 - Jonathan Morton