[Bloat] The Confucius queue management scheme

[Jonathan Morton]

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

 - Jonathan Morton