[Cake] Using cake to shape 1000’s of users.

[Toke Høiland-Jørgensen]

Jonathan Morton <chromatix99 at gmail.com> writes:

> Yes, eBPF does seem to be a good fit for that.
>
> So in summary, the logical flow of a packet should be:
>
> 1: Map dst or src IP to subscriber (eBPF).
> 2: Map subscriber to speed/overhead tier (eBPF).
> 3: (optional) Classify Diffserv (???).
> 4: Enqueue per flow, handle global queue overflow (rare!) by dropping
> from head of longest queue (like Cake).

Note that with the existing tc classifier stuff we already added to
Cake, we basically have this already (eBPF can map traffic to tin and
flow however it pleases).

> --- enqueue/dequeue split ---
> 5: Wait for shaper on earliest-scheduled subscriber link with waiting traffic (borrow sch_fq's rbtree?).
> 6: Wait for shaper on aggregate backhaul link (congestion can happen here too).
> 7: Choose one of subscriber's queues, apply AQM and deliver a packet (mostly like Cake does).
>
> If that seems reasonable, we can treat it as a baseline spec for
> others' input.

I think that the minimum modification to the existing CAKE code base
would be to just support an arbitrary (configurable) number of tins that
(eBPF) tc filters can map traffic into. You'd need a better way of
selecting the next tin to service; I think rbtree is a reasonable choice
here. And probably some way of avoiding allocating CAKE_FLOWS queues per
tin if there are a lot of them. The fq structure used for WiFi (which
was inspired by CAKE in the first place) solves this by allocating one
big batch of queues and mapping them to tins as packets are assigned to
them; this is in fq_impl.h.

The above is obviously minded on what would be the minimum required to
support an "ISP shaper" use case in the existing CAKE qdisc. If you're
designing a whole new qdisc, obviously there are other ways of
structuring things; so see the above more as inspiration... :)

-Toke