From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf0-x22f.google.com (mail-lf0-x22f.google.com [IPv6:2a00:1450:4010:c07::22f]) (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 EBF8421F3DB for ; Wed, 18 Nov 2015 02:49:06 -0800 (PST) Received: by lfdo63 with SMTP id o63so23603215lfd.2 for ; Wed, 18 Nov 2015 02:49:03 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=content-type:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=AbJS9FE/LVISrxZunOOiyf8cEIL7jBmwFvMuLFvbyww=; b=wt2RVK367/9N9k/GaookBdv5n2pT6YggoPHXpKvesRG/ZDgXgwtRrFIYZ167HnxdD2 wJa3kD4epkh6VSrSB3x4v/luF0Qw0lrrt9vfaI2jfDYyEsLKtOchCRSD6dv43R/UNx9N vJsd9vOrLWYE2ovcoDBHI9UczjJlWsNYEDyqTgnnifDVcTp84vtPWW6HPGA+Yi61Yqz/ XlyYS0wlH0DLGkv/IHWWVpaqhf5n40zEQQa0foE0UYogQDSUbLQKrK6PcNaASCZYNXav TcdkcnSlyrEuFT9UiZ/QGyl369KXAkB0p7sgCEntiVX1EGWx63DpXKcS1g7hxXz4CF6B 0saw== X-Received: by 10.25.39.19 with SMTP id n19mr298060lfn.156.1447843743430; Wed, 18 Nov 2015 02:49:03 -0800 (PST) Received: from bass.home.chromatix.fi (83-245-246-100-nat-p.elisa-mobile.fi. [83.245.246.100]) by smtp.gmail.com with ESMTPSA id 194sm343532lfd.4.2015.11.18.02.49.02 (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Wed, 18 Nov 2015 02:49:02 -0800 (PST) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 9.1 \(3096.5\)) From: Jonathan Morton In-Reply-To: Date: Wed, 18 Nov 2015 12:49:00 +0200 Content-Transfer-Encoding: quoted-printable Message-Id: <37A0F159-70F5-4FCF-B6FA-FE1D5DB9E6C4@gmail.com> References: To: Dave Taht X-Mailer: Apple Mail (2.3096.5) 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:49:29 -0000 > On 18 Nov, 2015, at 09:46, Dave Taht wrote: >=20 > 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=9Ccredit 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 = 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=E2=80=99s primary use case, = because there is typically a dumb network device=E2=80=99s 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=E2=80=99s 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=E2=80=99s 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