From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-oi0-x236.google.com (mail-oi0-x236.google.com [IPv6:2607:f8b0:4003:c06::236]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id ACBB13B260 for ; Mon, 23 May 2016 15:11:37 -0400 (EDT) Received: by mail-oi0-x236.google.com with SMTP id j1so55627477oih.3 for ; Mon, 23 May 2016 12:11:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bitamins-net.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc; bh=h+tPWHWyu186oxFLPwlj1MVfrZlso0PIN3Zm4d/znkM=; b=JnjXUvQGOrrPWh2d0d4A/izWy3H+TBfSpmyT+ICHuvT4w3dAqDKHRIavhijuve3yZ3 BqbIcrr/s9Iann3luXdnv9E9vc2tBj7HfV+GPzeCKTP6Ey+JJw04YtpH9qhWxJ3i8g4q F8NG5BMaADfsdGJY5L3XniqS+q2697WOhYvC1aVGVMJ4Ka2u5olwrtuoEzOGNACP2O3o l69ehhaJdYe2LSJcUqk+u61bLtQlRH6r79EAJP4a4EVyvYL66r0zpa47XtZwOCO/GGKQ maF3z8NbRY4S5OoOBapdhg4kK/JuQwXvoiJCfA9kqMXUyBQPy+8l1nFy4K8LYfOfBXtJ IXWg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc; bh=h+tPWHWyu186oxFLPwlj1MVfrZlso0PIN3Zm4d/znkM=; b=gBRcfHaiVBowX6DN2HfsnhXfpIbeg1YCTsVc/EGCVd6G7rdMWf2tVpP/t+3CVNFGiy hvxj8Ae/8DwbErkN0qzlUBlMANlY05LjAlxutDpks4yNiOdTzZa74LtpE0INtCS1Zl+1 zWrJZiAxpoygTA6JavNJLR79ay678QFiFIg6vXcGJr+B/MY5JvxF0xxBNFLQ2QtvCbE6 Zg6NDhmgn88YPmtVSsCxGFQ3GUqz+yWSvWh/mbH704kF0x24kVhZi5rXDISNgSpxmMLc 9TgSsUjtrncEuGeGoHfd9hCblziJ51laEzymRveOnBRs1eTG/J0wiofU3UsetFTQWYFQ RXVw== X-Gm-Message-State: ALyK8tKSFJKAy+ac466OgHIEmfvCGPPW6P2d1C64B/xKFL/T0adB8FyQ1ZeWW9lAj4adEluZ9u+jCbkwEeRfpw== MIME-Version: 1.0 X-Received: by 10.202.239.197 with SMTP id n188mr2539661oih.25.1464030696990; Mon, 23 May 2016 12:11:36 -0700 (PDT) Received: by 10.157.17.78 with HTTP; Mon, 23 May 2016 12:11:36 -0700 (PDT) X-Originating-IP: [206.108.31.34] In-Reply-To: <323AFC22-A092-4F59-8197-AF21EF73FD58@gmail.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> Date: Mon, 23 May 2016 13:11:36 -0600 Message-ID: From: "Luis E. Garcia" To: Jonathan Morton Cc: cake@lists.bufferbloat.net, codel@lists.bufferbloat.net Content-Type: multipart/alternative; boundary=94eb2c092ea2a28eb90533873546 Subject: Re: [Cake] 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: Mon, 23 May 2016 19:11:37 -0000 --94eb2c092ea2a28eb90533873546 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable It sounds like COBALT should be a bit smoother in terms of recovery/switch time from one state to another - if this is the case, I would say that it is a nice improvement - FQ_CODEL is smooth/fast in it's transition (at least in my observations on a ping test while running multiple streams to the bandwidth cap), and if the transition of the states is improved - I'm all for it :) Shorter & simpler code is always welcomed - I look forward to testing it. Now I just need to reconfigure the network with a test router, without breaking the internet at home so my wife doesn't notice. Luis On Mon, May 23, 2016 at 12:30 PM, Jonathan Morton wrote: > > > On 20 May, 2016, at 19:43, Jonathan Morton > wrote: > > > >> On 20 May, 2016, at 19:37, Luis E. Garcia wrote: > >> > >> I think this would be a great idea to implement and test. > >> Can COBALT's behavior be easily implemented to test it using the > OpenWRT or LEVE ? > > > > I assume you mean LEDE. > > > > Yes, the BLUE algorithm is very simple (and is already in Linux, if you > want to see how it behaves independently). It=E2=80=99s merely a case of= modifying > a fork of sch_codel and/or sch_fq_codel and/or sch_cake to run it in > parallel with the Codel algorithm. > > > > I=E2=80=99ll probably get around to it once I=E2=80=99ve got some curre= nt Cake changes > out of the way. > > While I don=E2=80=99t have COBALT working in an actual qdisc yet, I=E2=80= =99ve coded the > core algorithm - including a major refactoring of Codel. This core code, > containing *both* Codel and BLUE, is 90 lines *shorter* than codel5.h > alone. Quite a surprising amount of simplification. > > There=E2=80=99s even a possibility that it=E2=80=99ll be faster, especial= ly on embedded > CPUs, simply because it=E2=80=99s smaller. > > The simplification partly results from a change in API structure. Rather > than calling back into the qdisc to retrieve however many packets it want= s, > COBALT is handed one packet and a timestamp, and returns a flag indicatin= g > whether that packet should be dropped or delivered. It becomes the qdisc= =E2=80=99s > responsibility to dequeue candidate packets and perform the actual > dropping. So there is no longer a gnarly branched loop in the middle of > the AQM algorithm. > > There were objections to Codel=E2=80=99s =E2=80=9Ccallback=E2=80=9D struc= ture for other reasons, > too. The refactoring obviates them all. > > The one remaining loop in the fast path is a new backoff strategy for the > Codel phase where it=E2=80=99s just come out of the dropping state. Orig= inally > Codel reduced count by 1 or 2 immediately, and reset count to zero after = an > arbitrary number of intervals had passed without the target delay being > exceeded. My previous modification changed the immediate reduction to a > halving, in an attempt to avoid unbounded growth of the count value. > > In COBALT, I keep the drop-scheduler running in this phase, but without > actually dropping packets, and *decrementing* count instead of incrementi= ng > 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 will reduce by the correct amount, even if traffic temporarily ceas= es > on the queue. Ideally, this should cause Codel=E2=80=99s count value to = stabilise > where 50% of the time is spent above target sojourn time, and 50% below. > (Actual behaviour won=E2=80=99t quite be ideal, but it should be closer t= han > before.) > > As another simplification, I eliminated the =E2=80=9Cprimed=E2=80=9D stat= e (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 > also eliminates the first_above_time variable. Any packets with sojourn > times below target will bump Codel out of the dropping state anyway. > > Yet another simplification is enabled by COBALT=E2=80=99s hybrid structur= e and the > tacit assumption that it will be used with flow isolation. Because BLUE = is > present to handle overloads, much logic to handle overloads and =E2=80=9C= extra=E2=80=9D > signalling in Codel is not replicated in the refactored version. For > example, there is no =E2=80=9Cdrop then mark=E2=80=9D logic any more; in = all probability > the traffic in one flow is either all ECN capable or all not so. > > BLUE doesn=E2=80=99t 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. > > While going over codel5.h, I noticed that the invsqrt cache stored as u16 > while calculations were being done in u32. This probably caused some maj= or > weirdness with Codel=E2=80=99s behaviour in Cake, so I fixed it in the or= iginal. > > Next step: get an actual qdisc working using this. > > - Jonathan Morton > > --94eb2c092ea2a28eb90533873546 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
It sounds like COBALT should be a bit smoother in terms of= recovery/switch time from one state to another - if this is the case, I wo= uld say that it is a nice improvement - FQ_CODEL is smooth/fast in it's= transition (at least in my observations on a ping test while running multi= ple streams to the bandwidth cap), and if the transition of the states is i= mproved - I'm all for it :)

Shorter & simpler co= de is always welcomed - I look forward to testing it.
Now I just = need to reconfigure the network with a test router, without breaking the in= ternet at home so my wife doesn't notice.

Luis= =C2=A0

On Mon, May 23, 2016 at 12:30 PM, Jonathan Morton <chromatix99@gmail.= com> wrote:

> On 20 May, 2016, at 19:43, Jonathan Morton <chromatix99@gmail.com> wrote:
>
>> On 20 May, 2016, at 19:37, Luis E. Garcia <luis@bitamins.net> wrote:
>>
>> I think this would be a great idea to implement and test.
>> Can COBALT's behavior be easily implemented to test it using t= he OpenWRT or LEVE ?
>
> I assume you mean LEDE.
>
> Yes, the BLUE algorithm is very simple (and is already in Linux, if yo= u want to see how it behaves independently).=C2=A0 It=E2=80=99s merely a ca= se of modifying a fork of sch_codel and/or sch_fq_codel and/or sch_cake to = run it in parallel with the Codel algorithm.
>
> I=E2=80=99ll probably get around to it once I=E2=80=99ve got some curr= ent Cake changes out of the way.

While I don=E2=80=99t have COBALT working in an actual qdisc yet, I=E2=80= =99ve coded the core algorithm - including a major refactoring of Codel.=C2= =A0 This core code, containing *both* Codel and BLUE, is 90 lines *shorter*= than codel5.h alone.=C2=A0 Quite a surprising amount of simplification.
There=E2=80=99s even a possibility that it=E2=80=99ll be faster, especially= on embedded CPUs, simply because it=E2=80=99s smaller.

The simplification partly results from a change in API structure.=C2=A0 Rat= her than calling back into the qdisc to retrieve however many packets it wa= nts, COBALT is handed one packet and a timestamp, and returns a flag indica= ting whether that packet should be dropped or delivered.=C2=A0 It becomes t= he qdisc=E2=80=99s responsibility to dequeue candidate packets and perform = the actual dropping.=C2=A0 So there is no longer a gnarly branched loop in = the middle of the AQM algorithm.

There were objections to Codel=E2=80=99s =E2=80=9Ccallback=E2=80=9D structu= re for other reasons, too.=C2=A0 The refactoring obviates them all.

The one remaining loop in the fast path is a new backoff strategy for the C= odel phase where it=E2=80=99s just come out of the dropping state.=C2=A0 Or= iginally Codel reduced count by 1 or 2 immediately, and reset count to zero= after an arbitrary number of intervals had passed without the target delay= being exceeded.=C2=A0 My previous modification changed the immediate reduc= tion to a halving, in an attempt to avoid unbounded growth of the count val= ue.

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.=C2=A0 The loop simply ensures that cou= nt will reduce by the correct amount, even if traffic temporarily ceases on= the queue.=C2=A0 Ideally, this should cause Codel=E2=80=99s count value to= stabilise where 50% of the time is spent above target sojourn time, and 50= % below.=C2=A0 (Actual behaviour won=E2=80=99t quite be ideal, but it shoul= d be closer than before.)

As another simplification, I eliminated the =E2=80=9Cprimed=E2=80=9D state = (waiting for interval to expire) as an explicit entity, by simply schedulin= g the first drop event to be at now+interval when entering the dropping sta= te.=C2=A0 This also eliminates the first_above_time variable.=C2=A0 Any pac= kets with sojourn times below target will bump Codel out of the dropping st= ate anyway.

Yet another simplification is enabled by COBALT=E2=80=99s hybrid structure = and the tacit assumption that it will be used with flow isolation.=C2=A0 Be= cause BLUE is present to handle overloads, much logic to handle overloads a= nd =E2=80=9Cextra=E2=80=9D signalling in Codel is not replicated in the ref= actored version.=C2=A0 For example, there is no =E2=80=9Cdrop then mark=E2= =80=9D logic any more; in all probability the traffic in one flow is either= all ECN capable or all not so.

BLUE doesn=E2=80=99t 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-e= mpty.

While going over codel5.h, I noticed that the invsqrt cache stored as u16 w= hile calculations were being done in u32.=C2=A0 This probably caused some m= ajor weirdness with Codel=E2=80=99s behaviour in Cake, so I fixed it in the= original.

Next step: get an actual qdisc working using this.

=C2=A0- Jonathan Morton


--94eb2c092ea2a28eb90533873546--