From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pj1-x1030.google.com (mail-pj1-x1030.google.com [IPv6:2607:f8b0:4864:20::1030]) (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 3FDCB3B2A4 for ; Wed, 14 Feb 2024 11:25:41 -0500 (EST) Received: by mail-pj1-x1030.google.com with SMTP id 98e67ed59e1d1-296e22f85abso3622127a91.3 for ; Wed, 14 Feb 2024 08:25:41 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1707927940; x=1708532740; darn=lists.bufferbloat.net; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=LQ9+v5R7liDYW1/eWJkcRNO2jZoPokLApIUMpMvXNJQ=; b=YB9Gu0l1DrG4hiaN3FosXvDi+Kp7im3gjugug3UIo0xEiHxZhVOFYqdSTaFc2uQfSt KkKM1sbiB2S9+K3gripKC1kREb5Ng4ZtXsJFKOGr3DhNsTaQDD0E/NChgZPHL6M+6W0W raH81Ls8bIO8GpamFGrrLSIVg1hMbPK3ruvltfAKt054Pd/8u3Fxxe+QAoA6ifvRyrwz 8rw01HpYTGlIeabAVJPWfdAQL31x36Vo0qAB92z9ZSH+CDhoHDKG34YbOLFmX8R5VhVs rqt0dYeMPLABdgZzsovc2AQVz8mjtSwLZpLl+jVmAfUuEYqZAykzBXOLoKVFbkv+etHk SC7Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1707927940; x=1708532740; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=LQ9+v5R7liDYW1/eWJkcRNO2jZoPokLApIUMpMvXNJQ=; b=EoC5PDwUABeQ7WP8LxqpHbt0jGezL24Y8FEgWags1OgajufKC+Td3kIOKUdeAbCB+h Nh7W7KiIka7rejHjQ9a2yIFwtqXYzC/UCOntLh4lcgyT7ngjExFeCo6O1s9K0PYoip6t z7wUl0ym2JkPXbmjwFKf28IR5zmVTyDmKYPkc/DHWkA31inXdThNiCaxU5XnZrwgMqp4 ubSFTGgxvIIbXNIEAotCQU+G1CRwlzdYc6Gr9hd4o7CPQNnyO6NxoTw19+fadmymMHq0 bOxTWr1wY+wKyXA/T/6MWtQBoiSwyWgDmMOhPwWHXr/vimM9n135KuX+JL0hQOb+DDti 19eQ== X-Forwarded-Encrypted: i=1; AJvYcCVdPK7byYogSY2hqsrTPk7kDfYdk1FVQpdCPR6qiOLnhiVJ9SivTDP1ou3SebznxIo9TMt5vaL8J1P0vRXL/dAL0W5LatKwyqMzI8U= X-Gm-Message-State: AOJu0YycIDIgmQYG4pKzBWCn47P3s/MnBk19Q/cqW37A+MSGd6Vrlj41 4x7RHR/i7rSR4VEQ2fglxhwt7ma7m4HG8XRkygmMg0hbe+00TRHm2ZOM4+96bcnSMIe1bQW1Ow9 0mHwaHtYi399mJ+RtnCD/VTo6rVw= X-Google-Smtp-Source: AGHT+IFF1ljD0XscnCKFELmsyf/qHciwKj9eaRAu1mx0aYD4C/koMIn3uUut7s3tW+0RhcdDzzw6D/erx5HYrkJMpg0= X-Received: by 2002:a17:90a:cb81:b0:297:1d34:7ded with SMTP id a1-20020a17090acb8100b002971d347dedmr3007088pju.10.1707927939814; Wed, 14 Feb 2024 08:25:39 -0800 (PST) MIME-Version: 1.0 References: <87jzncs116.fsf@toke.dk> <2F4A44B6-2347-4976-A933-7F547D63D167@gmail.com> <874jebdngm.fsf@toke.dk> In-Reply-To: <874jebdngm.fsf@toke.dk> From: Dave Taht Date: Wed, 14 Feb 2024 11:25:27 -0500 Message-ID: To: =?UTF-8?B?VG9rZSBIw7hpbGFuZC1Kw7hyZ2Vuc2Vu?= Cc: Jonathan Morton , bloat 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:25:41 -0000 Thank you as well. Lacking source code, and them using copa, I was dubious about digging any deeper. It also did not appear they understood the dynamics of slow start very well, although I appreciated them hitting it with IW10 bursts. It also seemed that they were doing inbound shaping rather than egress shap= ing? On Wed, Feb 14, 2024 at 11:23=E2=80=AFAM Toke H=C3=B8iland-J=C3=B8rgensen v= ia Bloat wrote: > > Jonathan Morton writes: > > >> On 10 Feb, 2024, at 7:05 pm, Toke H=C3=B8iland-J=C3=B8rgensen via Bloa= t wrote: > >> > >> This looks interesting: https://arxiv.org/pdf/2310.18030.pdf > >> > >> 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 > _______________________________________________ > Bloat mailing list > Bloat@lists.bufferbloat.net > https://lists.bufferbloat.net/listinfo/bloat --=20 40 years of net history, a couple songs: https://www.youtube.com/watch?v=3DD9RGX6QFm5E Dave T=C3=A4ht CSO, LibreQos