From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from ondar.cablelabs.com (ondar.cablelabs.com [192.160.73.61]) by huchra.bufferbloat.net (Postfix) with ESMTP id A1C8B21F3AF for ; Wed, 18 Nov 2015 09:12:07 -0800 (PST) Received: from kyzyl.cablelabs.com (kyzyl [10.253.0.7]) by ondar.cablelabs.com (8.14.7/8.14.7) with ESMTP id tAIHC6Fm032248; Wed, 18 Nov 2015 10:12:06 -0700 Received: from exchange.cablelabs.com (10.5.0.19) by kyzyl.cablelabs.com (F-Secure/fsigk_smtp/407/kyzyl.cablelabs.com); Wed, 18 Nov 2015 10:12:06 -0700 (MST) X-Virus-Status: clean(F-Secure/fsigk_smtp/407/kyzyl.cablelabs.com) Received: from EXCHANGE.cablelabs.com ([::1]) by EXCHANGE.cablelabs.com ([::1]) with mapi id 14.03.0224.002; Wed, 18 Nov 2015 10:12:04 -0700 From: Greg White To: Dave Taht , Jonathan Morton Thread-Topic: [Cake] cake shaper vs leaky bucket algorithm Thread-Index: AQHRIfARME372g0Mi0eJhN0LveILIJ6iBJ0A Date: Wed, 18 Nov 2015 17:12:03 +0000 Message-ID: References: <37A0F159-70F5-4FCF-B6FA-FE1D5DB9E6C4@gmail.com> In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: user-agent: Microsoft-MacOutlook/14.5.6.150930 x-originating-ip: [10.4.11.49] Content-Type: text/plain; charset="iso-8859-1" Content-ID: <40BC9AE8B08BF346814B236AB35E7958@cablelabs.com> Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Cc: "cake@lists.bufferbloat.net" Subject: Re: [Cake] cake shaper vs leaky bucket algorithm X-BeenThere: cake@lists.bufferbloat.net X-Mailman-Version: 2.1.13 Precedence: list List-Id: Cake - FQ_codel the next generation List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 18 Nov 2015 17:12:30 -0000 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" wrote: >thx. > >greg, your answer below. >Dave T=E4ht >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 >wrote: >> >>> On 18 Nov, 2015, at 09:46, Dave Taht wrote: >>> >>> Greg white (of cablelabs) asked that how cake's shaper works, be >>> compared to a classic leaky bucket algorithm... >> >> I=B9m pretty sure I=B9ve already done this a couple of times. If =B3lea= ky >>bucket=B2 can be said to operate in =B3credit mode=B2, Cake=B9s shaper op= erates >>in =B3deficit mode=B2. >> >> 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=B9s primary use case, because ther= e >>is typically a dumb network device=B9s 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=B9s 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=B9s 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 >>