From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-oi0-x234.google.com (mail-oi0-x234.google.com [IPv6:2607:f8b0:4003:c06::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 EBA5221F426 for ; Sat, 9 May 2015 09:37:18 -0700 (PDT) Received: by oiko83 with SMTP id o83so79028155oik.1 for ; Sat, 09 May 2015 09:37:12 -0700 (PDT) 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=gk/+CT30UH0UXoYL13KAxnu7wvUuN4l8hZS5NszEInE=; b=gScgUnC751JD/B4YZNVQWJypIn1gX3MRSrZbSFmoyYnCN5ixMaZ8UU7bGDjZKgBHoP G2QuO6jfMTzIReywtdclx+oz2nzOlM+Gv+GFf5Qhifupv2ifIMXCurrw+WVy7n/07+kQ kB5MKsDA3kuRgBIdPbV7B8PP2Ti07ThZwBwGKSomUgTdO03+EutC6SoJzw6o9/YF6SAs GijHLJaV7IxHHv8za/sB79OGuE56yrVakaEFQuw9yrgSVE8LeAag4stzyu9syQYFHFGQ oTTntzUSWfGR79U+p1/sBwc79HHJqtcN2Y1k++ChPDKpblmdkO91az2hFy/W0/GdbR1x k4PQ== MIME-Version: 1.0 X-Received: by 10.202.227.130 with SMTP id a124mr2330502oih.59.1431189432095; Sat, 09 May 2015 09:37:12 -0700 (PDT) Received: by 10.202.71.139 with HTTP; Sat, 9 May 2015 09:37:12 -0700 (PDT) In-Reply-To: References: Date: Sat, 9 May 2015 09:37:12 -0700 Message-ID: From: Dave Taht To: Jonathan Morton Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Cc: cake@lists.bufferbloat.net Subject: Re: [Cake] packet mass, ecn, and a fractional count 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: Sat, 09 May 2015 16:37:54 -0000 On Thu, May 7, 2015 at 10:12 PM, Jonathan Morton wr= ote: > >> On 8 May, 2015, at 05:32, Dave Taht wrote: >> >> from observing behaviors with large numbers of flows, fq_codel derived >> algorithms start to struggle to achieve the desired delay, cake >> seemingly less so, and perhaps this is related to collisions also. >> >> A thought would be to use a fractional (fixed point) increment to >> count rather than "1" when larger numbers of flows are present. > > Given that cake handles this extreme case better than average already, I= =E2=80=99m not particularly concerned about trying to improve it further. = Adding set-associative hashing (or red-black trees for perfect isolation, i= f you prefer) to other FQ qdiscs might be a better idea than fudging codel. :) A larger point behind me sending, what? 20 or so speculative ideas to the cake mailing list is the hope to inspire better research than, for example, the recent "hard limit codel" paper. I would hope half someone gets around to exploring one day. The largest point though is that achieving 5-20ms of queue delay is quite a dang lot when the path is, say, gige few hundred us. The "right" amount of buffering is *1* packet, all the time (the goal is nearly 0 latency with 100% utilization). We are quite far from achieving that on anything with multiple barriers in the way in hardware and software, but it is helpful to keep that in mind.... and try to find people that might want to sink the time into exploring those problems also... > There=E2=80=99s a reasonably straightforward answer for why flow collisio= ns might cause worse AQM behaviour. Assume a situation with a very large n= umber of flows, so adding one more flow doesn=E2=80=99t change the throughp= ut of existing flows much. Now assume that most queues have just one flow = assigned, but there are a few with two each. (Ignore the possibility of mo= re, for simplicity.) > > The flows assigned to the doubled queues will have half the throughput ea= ch, compared to those in single queues. This also means that only half the= packets are available for sending congestion signals on, and since codel m= arks packets on a fixed schedule once it is triggered, each flow will there= fore receive only half the congestion signals. *BUT* each flow still gets = the same IW, so a doubled queue is twice as full as singles to begin with. > > So with perfect flow isolation (and a separate codel per queue), codel=E2= =80=99s signalling rate naturally scales with the number of flows. With co= llisions, that doesn=E2=80=99t happen so reliably; it is at best a sublinea= r scaling. Without FQ at all, representing the pessimal collisions case, c= odel has to wait for its signalling rate to grow over time in order to matc= h the number of flows, so it won=E2=80=99t react as quickly to an abruptly = imposed load. Agree, and i think this could be reworked into a better explanation as to why fq_codel and derivatives work so much better than single queue aqms. And in part (tracy widom) due to this better flow isolation we can scale up the drop/mark rate mildly faster and achieve lower latency faster when more flows are in play. > > - Jonathan Morton > --=20 Dave T=C3=A4ht Open Networking needs **Open Source Hardware** https://plus.google.com/u/0/+EricRaymond/posts/JqxCe2pFr67