Re: [Bloat] Rebecca Drucker's talk sounds like it exposes an addressable bloat issue in Ciscos

[Jonathan Morton <chromatix99@gmail.com>]

> On 10 Jan, 2021, at 7:39 am, Erik Auerswald <auerswal@unix-ag.uni-kl.de> wrote:
> 
> In my experience, asking about token-bucket algorithm details is often
> a sign for the asker to not see the forest for the trees.

IMHO, token-bucket is an obsolete algorithm that should not be used.  Like RED, it requires tuning parameters whose correct values are not obvious to the typical end-user, nor even to automatic algorithms.  Codel replaces RED, and virtual-clock algorithms can similarly replace token-bucket.

Token-bucket is essentially a credit-mode algorithm.  The notional "bucket" is replenished at regular (frequent) intervals by an amount proportional to the configured rate of delivery.  Traffic may be delivered as long as there is sufficient credit in the bucket to cover it.  This inherently leads to the delivery of traffic bursts at line rate, rather than delivery rate, and the size of those bursts may be as large as the bucket.  Conversely, if the bucket is too small, then scheduling and other quantum effects may conspire to reduce achievable throughput.  Since the bucket size must be chosen, manually, in advance, it is almost always wrong (and usually much too large).

Many token-bucket implementations further complicate this by having two nested token-buckets.  A larger bucket is replenished at exactly the configured rate from an infinite source, while a smaller bucket is replenished at some higher rate from the larger bucket.  This reduces the incidence of line-rate bursts and accommodates Reno-like sawtooth behaviour, but as noted, has the potential to seriously confuse BBR if the buckets are too large.  BBRv2 may handle it better if you add ECN and AQM, as the latter will help to correct bad estimations of throughput capacity resulting from the buckets initially being drained.

The virtual-clock algorithm I implemented in Cake is essentially a deficit-mode algorithm.  During any continuous period of traffic delivery, defined as finding a packet in the queue when one is scheduled to deliver, the time of delivering the next packet is updated after every packet is delivered, by calculating the serialisation time of that packet and adding it to the previous delivery schedule.  As long as that time is in the past, the next packet may be delivered immediately.  When it goes into the future, the time to wait before delivering the next packet is precisely known.  Hence bursts occur only due to quantum effects and are automatically of the minimum size necessary to maintain throughput, without any configuration (explicit or otherwise).

Since the scenario here involves an OpenWRT device, you should be able to install Cake on it, if it isn't there already.  Please give it a try and let us know if it improves matters.

 - Jonathan Morton