[Bloat] Thoughts on Stochastic Fair Blue

[Juliusz Chroboczek]

(I'm the original author of sch_sfb.)

> Having read some more documents and code, I have some extra insight into
> SFB that might prove helpful.  Note that I haven't actually tried it
> yet, but it looks good anyway.  In control-systems parlance, this is
> effectively a multichannel I-type controller, where RED is
> a single-channel P-type controller.

Methinks that it would be worthwile to implement plain BLUE, in order to
see how it compares.  (Of course, once Jim comes down from Mount Sinai
and hands us RED-Lite, it might also be worth thinking about SFRed.)

> My first thought after reading just the paper was that unconditionally
> dropping the packets which increase the marking probability was suspect.
> It should be quite possible to manage a queue using just ECN, without
> any packet loss, in simple cases such as a single bulk TCP flow.  Thus
> I am pleased to see that the SFB code in the debloat tree has separate
> thresholds for increasing the marking rate and tail-dropping.  They are
> fairly close together, but they are at least distinct.

I hesitated for a long time before doing that, and would dearly like to
see some conclusive experimental data that this is a good idea.  The
trouble is -- when the drop rate is too low, we risk receiving a burst
of packets from a traditional TCP sender.  Having the drop threshold
larger than the increase threshold will get such bursts into our
buffer.  I'm not going to explain on this particular list why such
bursts are ungood ;-)

The other, somewhat unrelated, issue you should be aware of is that
ECN marking has some issues in highly congested networks [1]; this is
the reason why sch_sfb will start dropping after the mark probability
has gone above 1/2.

> the length of the queue - which does not appear to be self-tuned by
> the flow rate.  However, the default values appear to be sensible.

Please clarify.

> The major concern with this arrangement is the incompatibility with
> qdiscs that can drop packets internally, since this is not necessarily
> obvious to end-user admins.

Agreed.  More generally, Linux' qdisc setup is error-prone, and
certainly beyond the abilities of the people we're targeting; we need to
get a bunch of reasonable defaults into distributions.  (Please start
with OpenWRT, whose qos-scripts package[2] is used by a fair number of
people.)

> I also thought of a different way to implement the hash rotation.
> Instead of shadowing the entire set of buckets, simply replace the hash
> on one row at a time.  This requires that the next-to-minimum values for
> q_len and p_mark are used, rather than the strict minima.  It is still
> necessary to calculate two hash values for each packet, but the memory
> requirements are reduced at the expense of effectively removing one row
> from the Bloom filter.

Interesting idea.

--Juliusz

[1] Aleksandar Kuzmanovic. The power of explicit congestion
    notification. In Proceedings of the 2005 conference on Applications,
    technologies, architectures, and protocols for computer
    communications. 2005.

[2] https://dev.openwrt.org/browser/trunk/package/qos-scripts/