From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ob0-x229.google.com (mail-ob0-x229.google.com [IPv6:2607:f8b0:4003:c01::229]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by huchra.bufferbloat.net (Postfix) with ESMTPS id 0DE6C21F3E3 for ; Wed, 18 Nov 2015 02:58:35 -0800 (PST) Received: by obbbj7 with SMTP id bj7so30136680obb.1 for ; Wed, 18 Nov 2015 02:58:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=GNh8d58iKai7/ByaSXK7tFb0xPCUrBb2/QQ5ZGJok2g=; b=CZ+TXvtFn4LZmPf2Al2zb/bYwibAeK3Q9BLOFhrU1cR2cX3SMDmiS/KfZMsEZuJBC6 2Ix5Joc4LTmbM9F8yX282sPtSwMylFWXDPsgRZvDWQvkuzfTjZGkEMO003wGVMyNsSff z5FkrFyr99GHdmpwPq5NBuwS+aBM0Z3mIFf6ppNK+sSkdjna07fH5E6CI/G6FM4+3rGh wDU2biTSy1wc6UrU4vHR7TA+wpa79Xk+S9ePJPZP6v0585Fub/aQwmta1sxODuV24zVO LDA/GGtIs5QplfxGLx+Csre8WjmvoOPwaTH70NaX+183d68eMK/ojd4xNFcHjGfZ5fod GbnQ== MIME-Version: 1.0 X-Received: by 10.60.95.8 with SMTP id dg8mr440200oeb.81.1447844314553; Wed, 18 Nov 2015 02:58:34 -0800 (PST) Received: by 10.202.50.130 with HTTP; Wed, 18 Nov 2015 02:58:34 -0800 (PST) In-Reply-To: <37A0F159-70F5-4FCF-B6FA-FE1D5DB9E6C4@gmail.com> References: <37A0F159-70F5-4FCF-B6FA-FE1D5DB9E6C4@gmail.com> Date: Wed, 18 Nov 2015 11:58:34 +0100 Message-ID: From: Dave Taht To: Jonathan Morton , Greg White Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable 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 10:58:58 -0000 thx. greg, your answer below. Dave T=C3=A4ht 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 w= rote: > >> 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=E2=80=99m pretty sure I=E2=80=99ve already done this a couple of times.= If =E2=80=9Cleaky bucket=E2=80=9D can be said to operate in =E2=80=9Ccred= it mode=E2=80=9D, Cake=E2=80=99s shaper operates in =E2=80=9Cdeficit mode= =E2=80=9D. > > 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 arriv= es 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 signi= ficant scheduling delay, an insufficient pool leads to underperformance in = throughput. These artefacts must therefore be estimated in advance, and th= e pool size chosen to trade off between throughput and maximum burst size. > > Burst outputs are problematic in Cake=E2=80=99s primary use case, because= there is typically a dumb network device=E2=80=99s queue immediately downs= tream 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 mini= mised, but it is desirable to do so without limiting throughput more than n= ecessary. This is typically achieved in leaky-bucket by choosing an adequa= tely large pool size (to absorb timing artefacts) and then slightly reducin= g the shaping rate (so that the latency induced is not persistent). > > By contrast, Cake=E2=80=99s shaper establishes time intervals in which pa= cket transmission is *prohibited*, equal to the time required to transmit t= he previous packet. As long as the shaper is saturated, this is achieved b= y advancing a schedule pointer (using an integer multiply-accumulate operat= ion, which is straightforward in both hardware and software) by the time-le= ngth of the packet just transmitted; the next packet may be transmitted whe= n 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 c= ase 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. T= he initial burst that leaky-bucket allows when first becoming saturated is = eliminated completely. I believe this behaviour is optimal. > > As a detail, Cake=E2=80=99s shaper also includes facilities for correctio= n of on-wire packet size, which is particularly important when the downstre= am link is ATM based. Queue accounting is based on the in-memory packet si= ze, while timing calculations are based on the corrected size. This furthe= r reduces the likelihood of the downstream hardware queue becoming saturate= d. > > - Jonathan Morton >