[Cake] cake shaper vs leaky bucket algorithm

[Greg White]

Thanks Dave and Jonathan.

This would be good text to add to the
http://www.bufferbloat.net/projects/codel/wiki/CakeTechnical page.

To further reduce misunderstanding, I would replace "leaky-bucket" with
"token-bucket" in the description though.

There are apparently two definitions of "leaky-bucket" in the literature,
one that is equivalent to "token-bucket", and one that only refers to the
special case where the bucket depth is equal to one packet/MTU.
https://en.wikipedia.org/wiki/Token_bucket#Comparison_to_leaky_bucket
Descriptions of the second type of leaky bucket ("leaky bucket algorithm
as a queue") commonly indicate that the algorithm eliminates* (absorbs)
burstiness, since packets depart at a fixed rate, whereas what you've
contrasted Cake with below is unambiguously "token bucket" (or "leaky
bucket algorithm as a meter", take your pick) since it allows bursts of
multiple back-to-back packets.

*Actually it only *limits* burstiness to 1 MTU worth of packets in the
common case where packets aren't all MTU-sized.


So, I would say your shaper is a variation on the traditional "leaky
bucket algorithm as a queue" in two ways:  1) you allow the output clock
(schedule pointer) to "reset" in the conditions you described, 2) you
delay small packets to avoid the 1 MTU "burstiness" that the traditional
algorithm would create.

Change 1 seems inarguably a good thing for any link except a time-slotted
link, since it reduces latency.  Change 2 might be more debatable, since
it adds latency where (it could be argued) it isn't needed.  The argument
might be: if it is acceptable (and it has to be) for the shaper to put an
MTU worth of consecutive bytes on the wire, does it matter whether those
bytes are one large packet or several small ones?

In any case, thanks for the more complete description.

-Greg



On 11/18/15, 3:58 AM, "Dave Taht" <dave.taht at gmail.com> wrote:

>thx.
>
>greg, your answer below.
>Dave Täht
>Let's go make home routers and wifi faster! With better software!
>https://www.gofundme.com/savewifi
>
>
>On Wed, Nov 18, 2015 at 11:49 AM, Jonathan Morton <chromatix99 at gmail.com>
>wrote:
>>
>>> 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
>>