From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lb0-x233.google.com (mail-lb0-x233.google.com [IPv6:2a00:1450:4010:c04::233]) (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 B0C4C3B260; Mon, 23 May 2016 14:30:20 -0400 (EDT) Received: by mail-lb0-x233.google.com with SMTP id k7so37385472lbm.0; Mon, 23 May 2016 11:30:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=iihQU//5Ha7lPOmyfHt/hggGXXtyM00J0+wvmcil7qQ=; b=SReMnd6w64yLy2FfB/whOS2a3uUjFlRRisFruDUXV/RIyZ/vuWOPHzKzit5MZSuQFX tsKN6wI9oDTkbZ7getBR6/W6NfIMCw8MpFf8OF/TOpG5qbbqk4fWZBaKJP4iPKXrZstR w9w+aQbmHbVlpxHgddL8celTn5mOhh3fWd3Rt3OqGsyK1hA0mtOencUoXBjKRP8Z+g2g yrZpQeYUouscgPtTMLGCHWqbU0ORwhdNYdtHaa6Dw29C0boJf8n5MP1950nCWqjQZuaT fHe42ObzUfMcKbFl6FvjZ1CvPXvvQeGQ9AN6kzw4eZ4rWirym1z6jEu/gJxKltLQl1vI BPWQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=iihQU//5Ha7lPOmyfHt/hggGXXtyM00J0+wvmcil7qQ=; b=JKSIwgVSoBqVIzhuzPRGqE61Blq9oLkSRAJ2lVNmv0nJqJFmq8ZWFY6R1Z0RHpECq5 swqgp9WVF1oir2D/ZfccJrB+1TNkH/7j9UMNp4cXCinrBupiEW+e/wCVfn9JCV3GDwHH Rb4kJlF7JY0viEvMNeRBjdO+mf3JZX2uM2vpMIISs/1N8FIlxLQ0dQxtn7X3/OMUQxVf x2HiNkWITg63LX/lAZI/tQ/CjZjQmvgWJP+nAnOvyBKChx75XFUGeES+JfI/LrrqRse2 mnpVDgNG3EmZq27VHUpQwj0ndMH6+DNMzhQjcHE9FxDu55w39CJoqJlre6C2zO4t6Zuz QCqQ== X-Gm-Message-State: AOPr4FWh5sJy9eP0avMXstYVV1eW4mwq6vK8oGD/TInu76lIxko54KyP8BNVZbD++zbxTA== X-Received: by 10.112.171.74 with SMTP id as10mr5515414lbc.139.1464028219054; Mon, 23 May 2016 11:30:19 -0700 (PDT) Received: from bass.home.chromatix.fi (188-67-138-144.bb.dnainternet.fi. [188.67.138.144]) by smtp.gmail.com with ESMTPSA id uc8sm5808137lbb.30.2016.05.23.11.30.17 (version=TLSv1/SSLv3 cipher=OTHER); Mon, 23 May 2016 11:30:18 -0700 (PDT) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 9.3 \(3124\)) From: Jonathan Morton In-Reply-To: <8AB0D25D-C1CA-45F1-889E-2F73CF8C44F7@gmail.com> Date: Mon, 23 May 2016 21:30:15 +0300 Cc: cake@lists.bufferbloat.net, codel@lists.bufferbloat.net Content-Transfer-Encoding: quoted-printable Message-Id: <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> To: "Luis E. Garcia" X-Mailer: Apple Mail (2.3124) Subject: Re: [Codel] [Cake] Proposing COBALT X-BeenThere: codel@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: CoDel AQM discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 23 May 2016 18:30:21 -0000 > On 20 May, 2016, at 19:43, Jonathan Morton = wrote: >=20 >> On 20 May, 2016, at 19:37, Luis E. Garcia wrote: >>=20 >> 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 ? >=20 > I assume you mean LEDE. >=20 > 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. >=20 > I=E2=80=99ll probably get around to it once I=E2=80=99ve got some = current Cake changes out of the way. While I don=E2=80=99t have COBALT working in an actual qdisc yet, I=E2=80=99= ve 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, = especially 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 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=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 = structure 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. = Originally 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 = 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 will reduce by the correct amount, even if = traffic temporarily ceases 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 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 = 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 = structure 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=9Cextra=E2=80=9D signalling in Codel is not = replicated in the refactored version. For example, there is no =E2=80=9Cd= rop 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 major 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. - Jonathan Morton