Jonathan Morton <chromati...@gmail.com> writes: >> On 10 Feb, 2024, at 7:05 pm, Toke Høiland-Jørgensen via Bloat >> <bloat@lists.bufferbloat.net> 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