[Cake] Re: help request for cake on a large network

[Jonathan Morton <chromatix99@gmail.com>]

> On 30 Sep, 2025, at 3:56 pm, Sebastian Moeller <moeller0@gmx.de> wrote:
> 
>> what would need to be done to increase resources to allow for full isolation of more flows?
> 
> I believe editing net/sched/sch_cake.c and increase the number of CAKE_QUEUES:
> #define CAKE_QUEUES (1024)
> 
> to something larger...
> 
> however I do not know what a realistic maximum is... and IIRC cake will search through this repeatedly

There's nothing that should repeatedly scan the entire list of queues, so there should only be a minor hit to performance from increasing the number of queues.

The set-associative hash searches only the set of 8 queues that the flow hashes to, and only when there's enough pressure to cause a hash collision, so this cost would be expected to go down if the number of queues is increased in anticipation of a heavy workload.

The list of active queues is scanned O(1) elements per delivered packet.  This doesn't mean that each queue is visited only once per delivery cycle, nor that a complete scan of the list can never happen, but amortised over many packets, the scanning cost is independent of the number of active flows.  (At least in theory.  It's grown into rather complex logic that I plan to simplify in the next-gen qdisc.  Running in "besteffort" mode already simplifies the control flow significantly.)

Queues that recently went inactive are kept in a separate list to "decay" their AQM state to quiescent.  This is scanned at a rate of one element per delivered packet.

In the corner case of the configured memory limit being reached, Cake needs to find the longest queue(s) to drop from.  This is done using a heap structure, *specifically* to avoid the possibility of a load-triggered DoS fault.  A linear scan is done only to initialise the heap (when the need for overload dropping is first identified) which is a one-time operation.  So even in this case, the cost per dropped packet is nearly independent - O(log N) - of the number of queues.

So the main limit on the practical number of queues is really the number of hash bits that are allocated to selecting a queue. Without specifically checking, I would be reasonably confident that you could run as many as 64K queues without difficulty.  I would still test this in the lab before deploying to production.

 - Jonathan Morton