[Cake] cake shaper vs leaky bucket algorithm

[Jonathan Morton]

> On 18 Nov, 2015, at 09:46, Dave Taht <dave.taht at gmail.com> wrote:
> 
> Greg white (of cablelabs) asked that how cake's shaper works, be
> compared to a classic leaky bucket algorithm...

I’m pretty sure I’ve already done this a couple of times.  If “leaky bucket” can be said to operate in “credit mode”, Cake’s shaper operates in “deficit mode”.

Leaky-bucket establishes a pool of tokens, replenished at a steady rate, that can be used at any time to transmit data.  If a burst of packets arrives at such a queue when it is fully charged, that burst may be transmitted all at once; to minimise burstiness, the size of the pool must be minimised.  But if timer resolution is poor (the basic PC-AT timer operates at 1kHz under Linux, though modern PCs have a much better one), or there is a significant scheduling delay, an insufficient pool leads to underperformance in throughput.  These artefacts must therefore be estimated in advance, and the pool size chosen to trade off between throughput and maximum burst size.

Burst outputs are problematic in Cake’s primary use case, because there is typically a dumb network device’s queue immediately downstream of Cake, in which bursts of packets inevitably induce latency.

In fact, where the shaper rate is precisely equal to the downstream link rate, leaky-bucket effectively induces persistent latency equal to its pool size when saturated.  At a system level, burstiness must therefore be minimised, but it is desirable to do so without limiting throughput more than necessary.  This is typically achieved in leaky-bucket by choosing an adequately large pool size (to absorb timing artefacts) and then slightly reducing the shaping rate (so that the latency induced is not persistent).

By contrast, Cake’s shaper establishes time intervals in which packet transmission is *prohibited*, equal to the time required to transmit the previous packet.  As long as the shaper is saturated, this is achieved by advancing a schedule pointer (using an integer multiply-accumulate operation, which is straightforward in both hardware and software) by the time-length of the packet just transmitted; the next packet may be transmitted when the actual time reaches that pointer.  The shaper is unsaturated iff the schedule time is reached when there is no data ready to send, and in this case the schedule is reset to begin with the next available packet.

This does allow bursts, but only after a timing artefact actually occurs, and precisely to the extent required to recover the average throughput.  The initial burst that leaky-bucket allows when first becoming saturated is eliminated completely.  I believe this behaviour is optimal.

As a detail, Cake’s shaper also includes facilities for correction of on-wire packet size, which is particularly important when the downstream link is ATM based.  Queue accounting is based on the in-memory packet size, while timing calculations are based on the corrected size.  This further reduces the likelihood of the downstream hardware queue becoming saturated.

 - Jonathan Morton