Networking CAKE Is Ready For Tasting With Linux 4.19

For those maintaining their own home-built Linux router, Linux 4.19 is going to be pretty exciting: CAKE Qdisc has been merged into net-next, making it a feature for this next kernel cycle.

CAKE Qdisc is a networking feature that's long been in development (19+ rounds of review before being accepted into net-next) and has already been available as an OpenWRT feature. CAKE Qdisc (exposed as the sch_cake module) aims to "squeeze the most bandwidth and latency out of even the slowest ISP links and routers." Among its features:

CAKE is filled with:

* A hybrid Codel/Blue AQM algorithm, "Cobalt", tied to an FQ_Codel derived Flow Queuing system, which autoconfigures based on the bandwidth.
* A novel "triple-isolate" mode (the default) which balances per-host and per-flow FQ even through NAT.
* An deficit based shaper, that can also be used in an unlimited mode.
* 8 way set associative hashing to reduce flow collisions to a minimum.
* A reasonable interpretation of various diffserv latency/loss tradeoffs.
* Support for zeroing diffserv markings for entering and exiting traffic.
* Support for interacting well with Docsis 3.0 shaper framing.
* Extensive support for DSL framing types.
* Support for ack filtering.
* Extensive statistics for measuring, loss, ecn markings, latency variation.

Networking maintainer David Miller isn't happy with some aspects of CAKE, but he has decided to merge it anyways and is now in net-next ahead of the Linux 4.19 merge window opening in August.

The CAKE Principles:
(or, how to have your cake and eat it too)

This is a combination of several shaping, AQM and FQ techniques into one easy-to-use package:

- An overall bandwidth shaper, to move the bottleneck away from dumb CPE equipment and bloated MACs. This operates in deficit mode (as in sch_fq), eliminating the need for any sort of burst parameter (eg. token bucket depth). Burst support is limited to that necessary to overcome scheduling latency.

- A Diffserv-aware priority queue, giving more priority to certain classes, up to a specified fraction of bandwidth. Above that bandwidth threshold, the priority is reduced to avoid starving other tins.

- Each priority tin has a separate Flow Queue system, to isolate traffic flows from each other. This prevents a burst on one flow from increasing the delay to another. Flows are distributed to queues using a set-associative hash function.

- Each queue is actively managed by Cobalt, which is a combination of the Codel and Blue AQM algorithms. This serves flows fairly, and signals congestion early via ECN (if available) and/or packet drops, to keep latency low. The codel parameters are auto-tuned based on the bandwidth setting, as is necessary at low bandwidths.

The configuration parameters are kept deliberately simple for ease of use. Everything has sane defaults. Complete generality of configuration is *not* a goal.

The priority queue operates according to a weighted DRR scheme, combined with a bandwidth tracker which reuses the shaper logic to detect which side of the bandwidth sharing threshold the tin is operating. This determines whether a priority-based weight (high) or a bandwidth-based weight (low) is used for that tin in the current pass.

This qdisc was inspired by Eric Dumazet's fq_codel code, which he kindly granted us permission to leverage.

The CAKE queue management algorithm is short for the "Common Applications Kept Enhanced" and with Linux 4.19 can be enabled via the NET_SCH_CAKE Kconfig switch.