[Cake] Proposing COBALT

[Luis E. Garcia]

It sounds like COBALT should be a bit smoother in terms of recovery/switch
time from one state to another - if this is the case, I would say that it
is a nice improvement - FQ_CODEL is smooth/fast in it's transition (at
least in my observations on a ping test while running multiple streams to
the bandwidth cap), and if the transition of the states is improved - I'm
all for it :)

Shorter & simpler code is always welcomed - I look forward to testing it.
Now I just need to reconfigure the network with a test router, without
breaking the internet at home so my wife doesn't notice.

Luis

On Mon, May 23, 2016 at 12:30 PM, Jonathan Morton <chromatix99 at gmail.com>
wrote:

>
> > 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.bufferbloat.net/pipermail/cake/attachments/20160523/b3a10328/attachment.html>