[Codel] [Make-wifi-fast] fq_codel_drop vs a udp flood

[Jonathan Morton]

> On 1 May, 2016, at 06:41, Dave Taht <dave.taht at gmail.com> wrote:
> 
> fq_codel_drop looks through 1024 queues in the mainline version and
> 4096 in this. [4] That's *expensive*.

Cake originally inherited this behaviour.

Some time ago, I changed it to search only the queues in the active lists.  In a simple case like this, that means it only has to consider 1-2 queues each time, which is a huge improvement and sufficient for any normal traffic situation.

The theoretical worst-case performance (eg. under a DDoS) remains poor.  To fix that, I think we would need to maintain a max-heap of queue lengths (which is a generalisation of the “keep 3 longest queues” idea).  On the upside, this heap would only need to be maintained when drops actually occur, and would remain fast in simple cases where only one or two queues are disproportionately long.

It’s just as easy to head-drop as tail-drop, once you decide to be queue-fair (which *is* desirable to make DoS attacks harder).  It is the queue-fairness which is CPU intensive (and can be optimised, see above).  Head-drop is theoretically superior, since it gets the congestion signal to the receiver faster.  An unresponsive flow won’t care either way, but a responsive one will.

 - Jonathan Morton