[Cake] tail drop on complete overload

[Jonathan Morton]

> On 13 Apr, 2015, at 01:16, Dave Taht <dave.taht at gmail.com> wrote:
> 
> The full flow space search on complete overload is terribly expensive,
> moreover it is not deterministic, and touches a lot of cache.

I would be interested to see if anyone can actually trigger this in practice.  It’s a slow-path function, which I assume would be rarely called - only when the queue is physically full.  By then, the overload mechanisms would already be in operation, dropping packets instead of marking them.  So it’s probably quite a lot easier to trigger it using a local sender than an external one - and if you *can* trigger it externally, then you’ve probably got enough CPU headroom to deal with it the right way.

Also, I don’t think it’s quite as expensive as you think.  Note that instead of iterating over the lists of flows, it iterates over the array of flow *backlog* counters in each class.  In the default configuration, that’s four 4KB arrays, accessed in ascending linear order (which on most practical memory architectures is the optimal pattern).  This is simply to pinpoint the longest queue, which I believe is desirable behaviour.

I don’t see how it can be non-deterministic.

The actual drop is as efficient as it can be.  Tail-drop would be *more* efficient, sure, since it just involves an early error return in enqueue(), but has its own behavioural risks.

It may be feasible - and in hardware would probably be easy - to keep track of the identity of the longest queue opportunistically.  This would reduce the cost of identifying that queue when it is necessary to do so, at the cost of a little extra overhead on processing every packet.  Is that worth it?

 - Jonathan Morton