[Codel] fq_codel: revenge of the standing queue

[Dave Taht]

As presently implemented, multi-queue fq_codel has a few FIFO codel
assumptions baked into it.

The first, already fixed, was that codel's state was completely reset
when a fq_codel queue was emptied. This has been fixed via a patch to
mainline.

However there are other places where codel's state is reset where
(perhaps!) it shouldn't. I note that I am NOT at this time
recommending these
changes to the codebase, the current behavior "does little harm", and
eventually gets the standing queue down to a reasonable, if not ideal,
minimum. I think it has the potential to run away at seriously high
numbers of flows, but haven't tested that.

I've tried various combinations of fixes below and run into multiple
issues. I think some of the stability/fairness problems I've had might
be an interaction with TSQ, and need to revise the testbed to be a
pure routing environment, and that is going to take time that I don't
have right now.

I hope that in pointing out these issue others will fiddle, and I do
have various patches that I can make available, that try different
stuff.

My basic test is running 75 TCP_MAERTS streams and 75 TCP_STREAM
streams at 10 or 100Mbit, for 60 seconds or more, with which I end up
with a standing queue of 80-150 packets (depending on codel version
and TSQ) and consequent large RTT. I am mostly using the
nearly-current-ns2 model (ported to linux) of codel.h. These results
hold as a function of the number of streams.

1) An empty queue in fq_codel has no meaningful information.

in: codel_should_drop

        if (!skb) {
                vars->first_above_time = 0;
                return false;
        }

I believe the codel intent here was to reset codel's state when the
single FIFO queue was emptied. In fq_codel's case, an empty queue
contains no information about the state, really, and a

        if (!skb) {
                if(sch->qstats.backlog <= mtu)
                         vars->first_above_time = 0;
                return false;
        }

comes closer to the intent. That said, the null skb then bleeds into
the rest of the algorithm

in codel_dequeue


        if (!skb) {
                 vars->dropping = false;
                return skb;
        }

later on there's

        if (vars->dropping) {
                if (!drop) {
                        /* sojourn time below target - leave dropping state */
                        vars->dropping = false;

and the same assumption within the while loop and in the else if(drop)...

I'm pretty sure that leaving of dropping state just because this
fq_codel queue is (temporarily) empty is not the right thing, and that
the main reason for exiting the dropping state should be getting under
the target delay. It might make sense to reschedule the next drop on a
null skb, perhaps after reducing count...

While I've fiddled with these ideas, and got some drainage, I do get
fairly big oscillations in queue depth, and starvation of some flows,
in various versions of my explorations.  Which led me to looking at
quantums and...

2) New flows

The next issue (at these 10 and 100Mbit rates) is the "new flow" idea
in fq_codel. It is VERY useful pushing sparse flows to the fore of the
queues, and also provided a boost to long RTT flows. However at high
levels of occupancy and low bandwidth, flows empty their queue
rapidly, become "new flows", and then mislead codel for that flow into
resetting itself again, since we end up with a short delay for the
re-entrance. This isn't a particularly horrible behavior, but as my
own hope for this feature was to make voip better primarily, and
everything else we got from it was a bonus.

TSQ really made this oddity show up big.  I think on routed traffic it
will be less of an issue.

Anyway, instead of depending on "empty queue" as a sign of a new flow,
I have fiddled with adding the consideration


        if (list_empty(&flow->flowchain)) {

if(codel_time_after(now - flow->cvars.last_delivery,
                                            q->cparams.target)) {
                                list_add_tail(&flow->flowchain, &q->new_flows);
                                q->new_flow_count++;
                                flow->deficit = q->quantum;
                        } else {
                                list_add_tail(&flow->flowchain, &q->old_flows);
                        }
}


which seems to do more of what I'd wanted in the first place. (last
delivery is set on every delivery from the flow)


...

3) I do kind of like amortizing the slope of the delay over an
interval (are we winning? Losing? By how much?) and trying
to inform decisions that way...





-- 
Dave Täht
http://www.bufferbloat.net/projects/cerowrt/wiki - "3.3.8-17 is out
with fq_codel!"