[Bloat] Thoughts on Stochastic Fair Blue

[Jonathan Morton]

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.

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.

My second observation is that marking and dropping both happen at the tail of the queue, not the head.  This delays the congestion information reaching the receiver, and from there to the sender, by 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.

Another observation is that packets are not re-ordered by SFB, which (given the Bloom filter) is potentially a missed opportunity.  However, they can be re-ordered in the current implementation by using child qdiscs such as SFQ, with or without HTB in tandem to capture the queue from a downstream "dumb" device.  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.

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.

 - Jonathan