Re: [Bloat] The Confucius queue management scheme

[Dave Taht <dave.taht@gmail.com>]

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 shaping?

On Wed, Feb 14, 2024 at 11:23 AM Toke Høiland-Jørgensen via Bloat
<bloat@lists.bufferbloat.net> wrote:
>
> Jonathan Morton <chromatix99@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



-- 
40 years of net history, a couple songs:
https://www.youtube.com/watch?v=D9RGX6QFm5E
Dave Täht CSO, LibreQos