From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf1-x132.google.com (mail-lf1-x132.google.com [IPv6:2a00:1450:4864:20::132]) (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 6D03B3B2A4 for ; Wed, 14 Feb 2024 09:24:31 -0500 (EST) Received: by mail-lf1-x132.google.com with SMTP id 2adb3069b0e04-51178bbb5d9so5354059e87.2 for ; Wed, 14 Feb 2024 06:24:31 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1707920668; x=1708525468; darn=lists.bufferbloat.net; h=to:references:message-id:content-transfer-encoding:cc:date :in-reply-to:from:subject:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=sEVpfHKxbU5kWvWIRbNBKDQL39/bUVgYwVaQ0KV7Vhs=; b=RyE4B5dDGCr13z/Qsh9W8gmCuN3t8SXyM+wS8uhXftBIXVgHVefcI+twj+Cib1kRAc ZZ56Tol4GJ4/+kBPN93vOj0Vs5dzRyYVGK3r5Ag916Vn9r9Af8/pB7OUK8746HllksFX 6Yxqr+vobbgEeUXdqKmqda9jVmv7H06ILIAA8i0phQIo1+b2XXWQaAHMgN+AhVfBL70F dCLI0vVk9MtzulZkWFSNTnHpEUyu3H4w4laicOgF3te6nbPudxi1na2Skvhyewx5BXrW ys9/DYt6ukTMKOAzVMP8wIRp2MaR/TQHL+LjCTmEiIvC6dwIF8cU5uCq/9vtaoJkq/2q 5xNA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1707920668; x=1708525468; h=to:references:message-id:content-transfer-encoding:cc:date :in-reply-to:from:subject:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=sEVpfHKxbU5kWvWIRbNBKDQL39/bUVgYwVaQ0KV7Vhs=; b=kgCr+GcQyHx3TV7LiDzrZkWFKxywNE/+VJYr0/IcE8IywVLgx3SJyBFrU2DxQW/TFP tBtNxUUfNNKQZWO9AFDtaRN0gPM+u4S90e6qf+H+1igrVN1Q4YuOU9o/0ZEzMb+9TVkD iepcOg3FVE+ccH5+llTbJxjScz7p9REchVJFkmQRZT5gA/yCtnRx2exUm63PVGIz9Pi4 8FkQR4Z2a/tgsKa4Kj23uXpTaUq4ngOqoo8yAsarXJ02iLDE/vF4RLLjzFWNhT3p8kNY GmAJccI4EclgTPMwcziF8i4NlI/sxglGHeyMfNpTSugumV0MO10KmSgqguNGQE8Iep0F tbsg== X-Gm-Message-State: AOJu0YzIt5Qor4FF8P42Z5m6xAKZFBAPeg33kTXfQt9SF28IFObu4iLT 7qsWNo1sart/1EUi2kwmamGnmxl4QlhVQ4kR7dakWph0difg1V+Y3sfgUBl3 X-Google-Smtp-Source: AGHT+IF9BFCF72MHajOisH7/zkmY7oTUSrF5Cli5E8EEkkgaa/yNo7vNoNG9gyV0ug8cixPgPKzFnA== X-Received: by 2002:ac2:5a01:0:b0:511:577d:10de with SMTP id q1-20020ac25a01000000b00511577d10demr2028032lfn.37.1707920668332; Wed, 14 Feb 2024 06:24:28 -0800 (PST) Received: from smtpclient.apple (178-55-39-192.bb.dnainternet.fi. [178.55.39.192]) by smtp.gmail.com with ESMTPSA id n6-20020a0565120ac600b00511a0d3bcdcsm364239lfu.184.2024.02.14.06.24.27 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Wed, 14 Feb 2024 06:24:27 -0800 (PST) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.100.0.2.22\)) From: Jonathan Morton In-Reply-To: <87jzncs116.fsf@toke.dk> Date: Wed, 14 Feb 2024 16:24:26 +0200 Cc: bloat Content-Transfer-Encoding: quoted-printable Message-Id: <2F4A44B6-2347-4976-A933-7F547D63D167@gmail.com> References: <87jzncs116.fsf@toke.dk> To: =?utf-8?Q?Toke_H=C3=B8iland-J=C3=B8rgensen?= X-Mailer: Apple Mail (2.3654.100.0.2.22) 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 14:24:31 -0000 > 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. - Jonathan Morton=