[Bloat] The Confucius queue management scheme

[Bloat] The Confucius queue management scheme

[Toke Høiland-Jørgensen]

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.

No code available, unfortunately, although they promise to release it
later...

-Toke

Re: [Bloat] The Confucius queue management scheme

[Dave Taht]

nice to see someone looking at slow start finally. Hilarious that they
do not call it by name. Slow start overshoot I have been now harping
on for a decade...

On Sat, Feb 10, 2024 at 12: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.
>
> No code available, unfortunately, although they promise to release it
> later...
>
> -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

Re: [Bloat] The Confucius queue management scheme

[Jonathan Morton]

> 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.

 - Jonathan Morton

Re: [Bloat] The Confucius queue management scheme

[Toke Høiland-Jørgensen]

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

Re: [Bloat] The Confucius queue management scheme

[Dave Taht]

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