[Bloat] The Confucius queue management scheme

[Toke Høiland-Jørgensen]

Jonathan Morton <chromatix99 at gmail.com> writes:

>> On 10 Feb, 2024, at 7:05 pm, Toke Høiland-Jørgensen via Bloat <bloat at 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