[Cake] cake shaper vs leaky bucket algorithm

[Cake] cake shaper vs leaky bucket algorithm

[Dave Taht]

Greg white (of cablelabs) asked that how cake's shaper works, be
compared to a classic leaky bucket algorithm...

https://en.wikipedia.org/wiki/Leaky_bucket

Dave Täht
Let's go make home routers and wifi faster! With better software!
https://www.gofundme.com/savewifi

Re: [Cake] cake shaper vs leaky bucket algorithm

[Jonathan Morton]

> On 18 Nov, 2015, at 09:46, Dave Taht <dave.taht@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

Re: [Cake] cake shaper vs leaky bucket algorithm

[Dave Taht]

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@gmail.com> wrote:
>
>> On 18 Nov, 2015, at 09:46, Dave Taht <dave.taht@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
>

Re: [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@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@gmail.com>
>wrote:
>>
>>> On 18 Nov, 2015, at 09:46, Dave Taht <dave.taht@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
>>

Re: [Cake] cake shaper vs leaky bucket algorithm

[Jonathan Morton]

> On 18 Nov, 2015, at 19:12, Greg White <g.white@CableLabs.com> wrote:
> 
> 2) you delay small packets to avoid the 1 MTU "burstiness" that the traditional algorithm would create.
> 
> 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.

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.

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

Re: [Cake] cake shaper vs leaky bucket algorithm

[Dave Taht]

On Wed, Nov 18, 2015 at 6:30 PM, Jonathan Morton <chromatix99@gmail.com> wrote:
>
>> On 18 Nov, 2015, at 19:12, Greg White <g.white@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
>

Re: [Cake] cake shaper vs leaky bucket algorithm

[Greg White]

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

-Greg


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

>On Wed, Nov 18, 2015 at 6:30 PM, Jonathan Morton <chromatix99@gmail.com>
>wrote:
>>
>>> On 18 Nov, 2015, at 19:12, Greg White <g.white@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
>>

Re: [Cake] cake shaper vs leaky bucket algorithm

[Greg White]

agreed.   (and I hope you understand I was speaking of the black-box
behavior rather than describing an implementation of it, your
implementation approach is clearly the appropriate one)



On 11/18/15, 10:30 AM, "Jonathan Morton" <chromatix99@gmail.com> wrote:

>
>> On 18 Nov, 2015, at 19:12, Greg White <g.white@CableLabs.com> wrote:
>> 
>> 2) you delay small packets to avoid the 1 MTU "burstiness" that the
>>traditional algorithm would create.
>> 
>> 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.
>
>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.
>
>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
>