[Cake] cake shaper vs leaky bucket algorithm

Greg White g.white at CableLabs.com
Wed Nov 18 13:16:02 EST 2015

Ok, sorry to have mentioned MTU!  :)

Actually, the textbook definitions of "leaky bucket as a queue" tend to
start with policing/shaping on pps (or equivalently assuming that all
packets are the same size), and then extend the definition to handle
variable sized packets by using the MTU as the quantum of burstiness.

So, in the comparison, add a third difference:  3) you eliminate any
dependence on (or concept of) the network MTU


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

>On Wed, Nov 18, 2015 at 6:30 PM, Jonathan Morton <chromatix99 at gmail.com>
>>> On 18 Nov, 2015, at 19:12, Greg White <g.white at CableLabs.com> wrote:
>>> 2) you delay small packets to avoid the 1 MTU "burstiness" that the
>>>traditional algorithm would create.
>I think dragging in MTU here is a problem. What we are seeing on most
>new hardware is also "superpackets" from GRO/TSO/GSO offloads, where
>inside the box up to 64k from a single stream is delivered as a single
>unit. Where I see this now all the time is a 10 or 20 IW10 packet
>"burst" coming into the router/modem from the gigE interface, needing
>to get broken down into real packets and mixed into other flows at the
>10 or 20Mbit uplink.
>>> 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?
>> When a large packet is committed for transmission, the latency it
>>causes (due to serialisation) is unavoidable.
>I still wish we had 584 byte MTUs standard...
>> When a series of small packets are available, the situation is more
>>complex.  Committing them all at once is certainly not a win; they must
>>still incur serialisation delay.
>> Conversely, committing them at the properly scheduled times allows
>>flow-isolation to work better (especially in the not-uncommon case where
>>new packets arrive for another flow while the original series is still
>>being dealt with), and also ensures that the correct sequence of sojourn
>>times is visible to the AQM layer.
>> But Cake¹s shaper doesn¹t treat sub-MTU packets specially in any case;
>>in fact, it is unaware of the MTU, and is entirely capable of handling
>>multi-MTU-sized aggregates.  It waits until the next transmission is
>>scheduled, transmits the next available packet, then advances the
>>pointer by the wire-time occupied by that packet.
>The other advantage (already in the doc, but perhaps needs to be
>brought out more) - is that in the sqm-scripts, with htb+fq_codel,
>we had to increase the htb pool (quantum) size as the bandwidth got
>higher, which was error prone and entirely dependent on the
>capabilities and load of the cpu involved. (I don't know if my scaling
>actually ever got fixed right, either)
>cake, compensates, almost magically, for the interrupt response rate
>and cpu capabilities relative to the load. It's also tons faster than
>htb+fq_codel were, scaling to 100mbit on the same hardware that
>struggled at 60mbit (faster... on the last benchmark series I ran - in
>june - we have added a few features since)....
>Now, it kind of remains to be seen as to how to burn this into
>hardware, there's some work on that, stalled out on funding....
>am really happy with cake so far. :)
>> So treating packets of different sizes differently, as you describe,
>>would actually complicate the algorithm as well as worsening its
>>system-level performance.
>>  - Jonathan Morton

More information about the Cake mailing list