From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail.toke.dk (mail.toke.dk [IPv6:2a0c:4d80:42:2001::664]) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id 9D0653B2A4 for ; Wed, 14 Feb 2024 11:23:24 -0500 (EST) From: Toke =?utf-8?Q?H=C3=B8iland-J=C3=B8rgensen?= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=toke.dk; s=20161023; t=1707927802; bh=0cLOiWJGEPBUSmpZOxxKk0fYhhG6Ze6cB9y5eR20AWQ=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=Dbe777sTHYItd+ugGEOStooKw9l6dpnKkM+UBM0oPeHujsX+c7gvrQCIFQWelV6TA +CoJjeSPKJLOqoda9y+uXYaCLHmHoeEs9mBX08Qx9bXFHMaaekXq581ye7Xjmy6+rT 8sJeof8n7MRd9qjpnDWXB74T3IgUlv6UgaqRDocv+FGWJL1NHQbOgRE0dfDf70iPyS EevArcG7tD/Oh2wBy3SPww5Z9sIztPU5fxBQhwEq+Chk4OucyTnrc5R40nJdAl0Fyv D/fR8vOt3fxsdhn5FtdlYiyEf4fBbxZ40WvGG5iLZAhPc/GskRcFaKsAA6A9KbIWnv 5wD7hTdAfmUhA== To: Jonathan Morton Cc: bloat In-Reply-To: <2F4A44B6-2347-4976-A933-7F547D63D167@gmail.com> References: <87jzncs116.fsf@toke.dk> <2F4A44B6-2347-4976-A933-7F547D63D167@gmail.com> Date: Wed, 14 Feb 2024 17:23:21 +0100 X-Clacks-Overhead: GNU Terry Pratchett Message-ID: <874jebdngm.fsf@toke.dk> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Subject: Re: [Bloat] The Confucius queue management scheme X-BeenThere: bloat@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: General list for discussing Bufferbloat List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 14 Feb 2024 16:23:24 -0000 Jonathan Morton writes: >> On 10 Feb, 2024, at 7:05 pm, Toke H=C3=B8iland-J=C3=B8rgensen via Bloat = wrote: >>=20 >> This looks interesting: https://arxiv.org/pdf/2310.18030.pdf >>=20 >> They propose a scheme to gradually let new flows achieve their fair >> share of the bandwidth, to avoid the sudden drops in the available >> capacity for existing flows that can happen with FQ if a lot of flows >> start up at the same time. > > I took some time to read and think about this. > > The basic idea is delightfully simple: "old" flows have a fixed weight > of 1.0; "new" flows have a weight of (old flows / new flows) * > 2^(k*t), where t is the age of the flow and k is a tuning constant, > and are reclassified as "old" flows when this quantity reaches 1.0. > They also describe a queuing mechanism which uses these weights, which > while mildly interesting in itself, isn't directly relevant since a > variant of DRR++ would also work here. > > I noticed four significant problems, three of which arise from > significant edge cases, and the fourth is an implementation detail > which can easily be remedied. I didn't see any discussion of these > edge cases in the paper, only the implementation detail. The latter is > just a discretisation of the exponential function into doubling > epochs, probably due to an unfamiliarity with fixed-point arithmetic > techniques. We can ignore it when thinking about the wider design > theory. > > The first edge case is already fatal unless somehow handled: starting > with an idle link, there are no "old" flows and thus the numerator of > the equation is zero, resulting in a zero weight for any number of new > flows which then arise. There are several reasonable and quite trivial > ways to handle this. > > The second edge case is the dynamic behaviour when "new" flows > transition to "old" ones. This increases the numerator and decreases > the denominator for other "new" flows, causing a cascade effect where > several "new" flows of similar but not identical age suddenly become > "old", and younger flows see a sudden jump in weight, thus available > capacity. This would become apparent in realistic traffic more easily > than in a lab setting. A formulation which remains smooth over this > transition would be preferable. > > The third edge case is that there is no described mechanism to remove > flows from the "old" set when they become idle. Most flows on the > Internet are in practice short, so they might even go permanently idle > before leaving the "new" set. If not addressed, this becomes either a > memory leak or a mechanism for the flow hash table to rapidly fill up, > so that in practice all flows are soon seen as "old". The DRR++ > mechanism doesn't suffice, because the state in Confucius is supposed > to evolve over longer time periods, much longer than the sojourn time > of an individual packet in the queue. > > The basic idea is interesting, but the algorithmic realisation of the > idea needs work. Thank you for taking a detailed look! I think you're basically echoing my immediate sentiment when reading this: neat idea, not quite convinced about the implementation details. But I didn't spend enough time thinking about it to express the problems in such concrete detail, so thank you for doing that! :) -Toke