From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lb0-x234.google.com (mail-lb0-x234.google.com [IPv6:2a00:1450:4010:c04::234]) (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 5F0BB201B8F for ; Thu, 28 May 2015 14:24:20 -0700 (PDT) Received: by lbcue7 with SMTP id ue7so36874562lbc.0 for ; Thu, 28 May 2015 14:24:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:content-type:content-transfer-encoding:subject:message-id:date :to:mime-version; bh=kXIkp2lM/ZN31alsIKLnqwEHT00kKnBSkghtLp4Zj5E=; b=d9kZHaN1QJwvA42fzFXX9RD++3RWgpUrNoC3NYvobi1iVVtItDQBEt4Bf9GYI1o2o7 uzcig1r8YvU7q/bihWtnnaQJFBghsrF52KRygIzdS4YNoEZ+L2azBBUqer9tCHNjDBGl asBrGPO4h0hdpV1VftO5IpY+ximaoPNPzEWsfSU9hF/4MtL1kIn6YejLpJXUa6M8+j0K yBQ/DrAHW4KosAdQlIKp+znwKo1GItkNadv43sKJ0f392Jy/dptwe1BdJvJHGgyowGvl yC9Dp6I1LM2qfgGUl7NcUEMPhJHTlN2EOYhkwOSwC9e3JL9+bxd2kLmQioMai1EdfEr5 XSvA== X-Received: by 10.152.164.193 with SMTP id ys1mr4707465lab.23.1432848250881; Thu, 28 May 2015 14:24:10 -0700 (PDT) Received: from bass.home.chromatix.fi (87-95-58-74.bb.dnainternet.fi. [87.95.58.74]) by mx.google.com with ESMTPSA id o8sm859588lal.2.2015.05.28.14.23.54 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Thu, 28 May 2015 14:24:10 -0700 (PDT) From: Jonathan Morton Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Message-Id: <14FB0F5A-1B98-43D3-9085-8730AE155695@gmail.com> Date: Fri, 29 May 2015 00:23:47 +0300 To: cake@lists.bufferbloat.net Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2098\)) X-Mailer: Apple Mail (2.2098) Subject: [Cake] Today's cake is fishcake a la creme. Enjoy your meal. 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: Thu, 28 May 2015 21:24:59 -0000 Today I pushed several significant updates to cake. They compile, and = don=E2=80=99t appear to cause kernel panics, but there be dragons here. = Tread carefully, and be ready to cast a Jedi Mind Trick[1] if you have = acquired that ability. Iproute2 now actually has the extra shortcut keywords I talked about = previously. They are more-or-less self-explanatory, but are not yet = mentioned in the help text. The GSO peeling code is more refined: - Refactored for efficiency, with several things moved out of the loop. - Unlimited mode unconditionally invokes peeling, just as ATM = compensation does. - Peeling threshold inversely proportional to number of active flows; 1 = flow remains at 1ms. The flow DRR quantum is now dynamically calculated in the same way as = the peeling threshold. It is clamped to limits at 1514 and 300. At 4 = MB/s (the previous threshold, choosing between those two extrema), the = quantum is now 976. The set-associative hash has been tweaked to be more careful about = keeping sparse and semi-sparse flows isolated from each other. A queue = has to be evicted from the flowchain before it=E2=80=99s considered = empty, not simply to have no packets in it. This should tend to improve = flow isolation even further, but it=E2=80=99s possible that a number of = spurious hard collisions might now occur under transient conditions. = Under heavy load, expect to see a larger number of indirect hits and a = smaller number of misses than before. I also tweaked the version of Codel that cake uses: - Recovery now halves the count rather than subtracting two, to ensure = that the signalling frequency doesn=E2=80=99t grow out of hand (since at = high signalling frequencies, it=E2=80=99s likely that count will = increment many times per RTT). The extra Newton step there has been = replaced by a simple fixed-point multiplication by sqrt(2); this should = always get close enough to the true value that a single Newton step (or = a cache lookup) is sufficient to complete the correction. - The trigger threshold has been seriously modified, so that it takes = less time to trigger if the queue grew rapidly than if it is growing = slowly. There is roughly a 6:1 dynamic range in this respect. Given = the standard 100/5 parameters, it can now trigger as quickly as 35ms = after a large burst arrives all at once, or as slowly as 200ms if the = sojourn time persistently remains just barely over 5ms for that long. = The interval parameter still controls the initial marking frequency as = before. The rationale for the latter change is that slow-start needs to be = signalled very quickly in order to be brought under control; in fact, = the ideal moment for slow-start to be signalled at is precisely the = moment the target is breached. Consider that under conventional = slow-start (ie. Reno), cwnd doubles on each RTT, and halves upon = receiving a congestion signal, and it takes precisely one RTT for the = signal to have an effect on the queue input. Therefore, the cwnd will = initially reduce to the level corresponding to the packet on which the = signal was sent. I note that according to Big-O terminology, there are several grades = between Exponential (slow start) and Linear (congestion avoidance) = growth: Polynomial (n^k) and Linearithmic (n log n) are the best known. = Exponential is considered a very extreme growth factor, usually beaten = only by Factorial. This explains why slow-start is so difficult to = control accurately using algorithms tuned for the congestion-avoidance = phase. The existence of the new trigger mechanism also makes it possible to = cause Codel to trigger instantly when the target is breached. I have = not yet added anything which actually does that, but the facility may = prove useful for ingress shaping, making cake behave more like a = less-than-military sort of policer. - Jonathan Morton [1] - Beware of the Infinite Loops.