[Cake] Proposing COBALT

[Jonathan Morton]

> On 20 May, 2016, at 19:43, Jonathan Morton <chromatix99 at gmail.com> wrote:
> 
>> On 20 May, 2016, at 19:37, Luis E. Garcia <luis at bitamins.net> wrote:
>> 
>> I think this would be a great idea to implement and test.
>> Can COBALT's behavior be easily implemented to test it using the OpenWRT or LEVE ?
> 
> I assume you mean LEDE.
> 
> Yes, the BLUE algorithm is very simple (and is already in Linux, if you want to see how it behaves independently).  It’s merely a case of modifying a fork of sch_codel and/or sch_fq_codel and/or sch_cake to run it in parallel with the Codel algorithm.
> 
> I’ll probably get around to it once I’ve got some current Cake changes out of the way.

While I don’t have COBALT working in an actual qdisc yet, I’ve coded the core algorithm - including a major refactoring of Codel.  This core code, containing *both* Codel and BLUE, is 90 lines *shorter* than codel5.h alone.  Quite a surprising amount of simplification.

There’s even a possibility that it’ll be faster, especially on embedded CPUs, simply because it’s smaller.

The simplification partly results from a change in API structure.  Rather than calling back into the qdisc to retrieve however many packets it wants, COBALT is handed one packet and a timestamp, and returns a flag indicating whether that packet should be dropped or delivered.  It becomes the qdisc’s responsibility to dequeue candidate packets and perform the actual dropping.  So there is no longer a gnarly branched loop in the middle of the AQM algorithm.

There were objections to Codel’s “callback” structure for other reasons, too.  The refactoring obviates them all.

The one remaining loop in the fast path is a new backoff strategy for the Codel phase where it’s just come out of the dropping state.  Originally Codel reduced count by 1 or 2 immediately, and reset count to zero after an arbitrary number of intervals had passed without the target delay being exceeded.  My previous modification changed the immediate reduction to a halving, in an attempt to avoid unbounded growth of the count value.

In COBALT, I keep the drop-scheduler running in this phase, but without actually dropping packets, and *decrementing* count instead of incrementing it; the backoff phase then naturally ends when count returns to zero, instead of after an arbitrary hard timeout.  The loop simply ensures that count will reduce by the correct amount, even if traffic temporarily ceases on the queue.  Ideally, this should cause Codel’s count value to stabilise where 50% of the time is spent above target sojourn time, and 50% below.  (Actual behaviour won’t quite be ideal, but it should be closer than before.)

As another simplification, I eliminated the “primed” state (waiting for interval to expire) as an explicit entity, by simply scheduling the first drop event to be at now+interval when entering the dropping state.  This also eliminates the first_above_time variable.  Any packets with sojourn times below target will bump Codel out of the dropping state anyway.

Yet another simplification is enabled by COBALT’s hybrid structure and the tacit assumption that it will be used with flow isolation.  Because BLUE is present to handle overloads, much logic to handle overloads and “extra” signalling in Codel is not replicated in the refactored version.  For example, there is no “drop then mark” logic any more; in all probability the traffic in one flow is either all ECN capable or all not so.

BLUE doesn’t add much code; only two lines in the fast path, and a couple of extra entry points for the qdisc to signal queue-full and queue-empty.

While going over codel5.h, I noticed that the invsqrt cache stored as u16 while calculations were being done in u32.  This probably caused some major weirdness with Codel’s behaviour in Cake, so I fixed it in the original.

Next step: get an actual qdisc working using this.

 - Jonathan Morton