From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail1.sandvine.com (Mail1.sandvine.com [64.7.137.134]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id AB0E63B25E; Tue, 24 May 2016 09:47:47 -0400 (EDT) Received: from BLR-EXCHP-2.sandvine.com (192.168.196.172) by WTL-EXCHP-2.sandvine.com (192.168.194.177) with Microsoft SMTP Server (TLS) id 14.3.195.1; Tue, 24 May 2016 09:47:46 -0400 Received: from WTL-EXCHP-1.sandvine.com ([fe80::ac6b:cc1e:f2ff:93aa]) by blr-exchp-2.sandvine.com ([fe80::6c6d:7108:c63c:9055%14]) with mapi id 14.03.0181.006; Tue, 24 May 2016 09:47:46 -0400 From: Jeff Weeks To: Jonathan Morton , "Luis E. Garcia" CC: "cake@lists.bufferbloat.net" , "codel@lists.bufferbloat.net" Thread-Topic: [Codel] [Cake] Proposing COBALT Thread-Index: AQHRsowJbJMbO4upBUWEkRGSBgLxnp/CAU+AgAAR3YCAABTbAP//4HP2gAUXyICAAPw4hQ== Date: Tue, 24 May 2016 13:47:45 +0000 Message-ID: <274D3A0FA900FD47AA6B56991AAA32FDC5529FC8@wtl-exchp-1.sandvine.com> References: <22371476-B45C-4E81-93C0-D39A67639EA0@gmx.de> <857AEE56-E7DB-4981-B32E-82473F877139@gmail.com> <8AB0D25D-C1CA-45F1-889E-2F73CF8C44F7@gmail.com>, <323AFC22-A092-4F59-8197-AF21EF73FD58@gmail.com> In-Reply-To: <323AFC22-A092-4F59-8197-AF21EF73FD58@gmail.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [192.168.196.10] x-c2processedorg: b2f06e69-072f-40ee-90c5-80a34e700794 Content-Type: text/plain; charset="Windows-1252" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Mailman-Approved-At: Tue, 24 May 2016 09:52:00 -0400 Subject: Re: [Cake] [Codel] Proposing COBALT X-BeenThere: cake@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: Cake - FQ_codel the next generation List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 24 May 2016 13:47:47 -0000 > In COBALT, I keep the drop-scheduler running in this phase, but without a= ctually dropping packets, and *decrementing* count instead of incrementing = it; the backoff phase then =0A= > naturally ends when count returns to zero, instead of after an arbitrary = hard timeout. The loop simply ensures that count will reduce by the correc= t amount, even if traffic =0A= > temporarily ceases on the queue. Ideally, this should cause Codel=92s co= unt value to stabilise where 50% of the time is spent above target sojourn = time, and 50% below. (Actual =0A= > behaviour won=92t quite be ideal, but it should be closer than before.)= =0A= =0A= I tried this as well, at one point, but can't remember, off-hand, why I did= n't stick with it; will have to see if I can find mention of it in my notes= .=0A= What trigger are you using to decrement count? I initially did a crude dec= rement of count every interval, but then you end up with a ramp-down time w= hich is considerably slower then the ramp-up (and the ramp up is slow to be= gin with).=0A= I assume you're actually re-calculating the next drop, using the 1/sqrt(cou= nt) but instead of dropping and increasing count, you're simply decreasing = count, so the time to get from 1->N is the same as the time to get to N->1?= =0A= =0A= > As another simplification, I eliminated the =93primed=94 state (waiting f= or interval to expire) as an explicit entity, by simply scheduling the firs= t drop event to be at now+interval when =0A= > entering the dropping state. This also eliminates the first_above_time v= ariable. Any packets with sojourn times below target will bump Codel out o= f the dropping state anyway.=0A= =0A= How do you handle the case where you're scheduled a drop event 100ms in the= future, and we immediately see low latency; is the event descheduled?=0A= If not, what if we then see high latency again; can the still-scheduled-eve= nt cause us to start dropping packets earlier than 100ms?=0A= =0A= --Jeff=0A= ________________________________________=0A= From: Codel [codel-bounces@lists.bufferbloat.net] on behalf of Jonathan Mor= ton [chromatix99@gmail.com]=0A= Sent: Monday, May 23, 2016 2:30 PM=0A= To: Luis E. Garcia=0A= Cc: cake@lists.bufferbloat.net; codel@lists.bufferbloat.net=0A= Subject: Re: [Codel] [Cake] Proposing COBALT=0A= =0A= > On 20 May, 2016, at 19:43, Jonathan Morton wrote:= =0A= >=0A= >> On 20 May, 2016, at 19:37, Luis E. Garcia wrote:=0A= >>=0A= >> I think this would be a great idea to implement and test.=0A= >> Can COBALT's behavior be easily implemented to test it using the OpenWRT= or LEVE ?=0A= >=0A= > I assume you mean LEDE.=0A= >=0A= > Yes, the BLUE algorithm is very simple (and is already in Linux, if you w= ant to see how it behaves independently). It=92s merely a case of modifyin= g a fork of sch_codel and/or sch_fq_codel and/or sch_cake to run it in para= llel with the Codel algorithm.=0A= >=0A= > I=92ll probably get around to it once I=92ve got some current Cake change= s out of the way.=0A= =0A= While I don=92t have COBALT working in an actual qdisc yet, I=92ve coded th= e core algorithm - including a major refactoring of Codel. This core code,= containing *both* Codel and BLUE, is 90 lines *shorter* than codel5.h alon= e. Quite a surprising amount of simplification.=0A= =0A= There=92s even a possibility that it=92ll be faster, especially on embedded= CPUs, simply because it=92s smaller.=0A= =0A= The simplification partly results from a change in API structure. Rather t= han calling back into the qdisc to retrieve however many packets it wants, = COBALT is handed one packet and a timestamp, and returns a flag indicating = whether that packet should be dropped or delivered. It becomes the qdisc= =92s responsibility to dequeue candidate packets and perform the actual dro= pping. So there is no longer a gnarly branched loop in the middle of the A= QM algorithm.=0A= =0A= There were objections to Codel=92s =93callback=94 structure for other reaso= ns, too. The refactoring obviates them all.=0A= =0A= The one remaining loop in the fast path is a new backoff strategy for the C= odel phase where it=92s just come out of the dropping state. Originally Co= del reduced count by 1 or 2 immediately, and reset count to zero after an a= rbitrary number of intervals had passed without the target delay being exce= eded. My previous modification changed the immediate reduction to a halvin= g, in an attempt to avoid unbounded growth of the count value.=0A= =0A= In COBALT, I keep the drop-scheduler running in this phase, but without act= ually dropping packets, and *decrementing* count instead of incrementing it= ; the backoff phase then naturally ends when count returns to zero, instead= of after an arbitrary hard timeout. The loop simply ensures that count wi= ll reduce by the correct amount, even if traffic temporarily ceases on the = queue. Ideally, this should cause Codel=92s count value to stabilise where= 50% of the time is spent above target sojourn time, and 50% below. (Actua= l behaviour won=92t quite be ideal, but it should be closer than before.)= =0A= =0A= As another simplification, I eliminated the =93primed=94 state (waiting for= interval to expire) as an explicit entity, by simply scheduling the first = drop event to be at now+interval when entering the dropping state. This al= so eliminates the first_above_time variable. Any packets with sojourn time= s below target will bump Codel out of the dropping state anyway.=0A= =0A= Yet another simplification is enabled by COBALT=92s hybrid structure and th= e tacit assumption that it will be used with flow isolation. Because BLUE = is present to handle overloads, much logic to handle overloads and =93extra= =94 signalling in Codel is not replicated in the refactored version. For e= xample, there is no =93drop then mark=94 logic any more; in all probability= the traffic in one flow is either all ECN capable or all not so.=0A= =0A= BLUE doesn=92t add much code; only two lines in the fast path, and a couple= of extra entry points for the qdisc to signal queue-full and queue-empty.= =0A= =0A= While going over codel5.h, I noticed that the invsqrt cache stored as u16 w= hile calculations were being done in u32. This probably caused some major = weirdness with Codel=92s behaviour in Cake, so I fixed it in the original.= =0A= =0A= Next step: get an actual qdisc working using this.=0A= =0A= - Jonathan Morton=0A= =0A= _______________________________________________=0A= Codel mailing list=0A= Codel@lists.bufferbloat.net=0A= https://lists.bufferbloat.net/listinfo/codel=0A=