[Cerowrt-devel] better mixing in fq_codel

[Dave Taht]

I have finally found the source of the issues I was having with htb +
fq_codel at low bandwidths, and it wasn't htb to the extent I thought
it was.

It was fq_codel's use of byte quantums, which was resulting in head of
line blocking for multiple streams.

The undesirable behavior (quantum of 1500)

A new stream, 15 acks (1500 bytes or so)
B new stream, 4 acks (66 bytes each)
C new stream, 1 packet, 1500 bytes

Each stream would be delivered in an entire quantum's quantity before
the next. This is basically something that is nearly unnoticable at
higher bandwidths, but down here in the slow moving mud, it's quite
significant. At 1 mbit, 1500 bytes is forever...

Better mixing behavior results from

A 1 packet
B 1 packet
C 1 packet (if not larger than quantum)
A 1 packet ""
B 1 packet ""
...

While I have a patch for this (all 5 lines of it), which does this
sort of mixing, it crashes under load, but I'll get there. Behavior
before it crashes is rather nice, where before I was observing
something like 36 ms of delay with htb for: small packets, "sparse" or
ANT streams under a variety of loads, it drops below 3ms in the
general case for those. Both qos-scripts and simple-qos benefit
hugely.

One of these three sets of changes to fq_codel_dequeue or enqueue is
dubious. (well, I have a half dozen other patches and fixups to codel
and fq_codel in the queue too, so have to rip out each). But yea! this
is the low bandwidth behavior we want!

fq_codel_enqueue
...

        if (list_empty(&flow->flowchain)) {
                list_add_tail(&flow->flowchain, deprio(skb) ?
                              &q->old_flows : &q->new_flows);
// the deprio routine looks at diffserv CS1 and kicks anything marked
that way always to the old flows
// it would be better if this was policy set in userspace, this is
just a hack for now
                q->new_flow_count++;
                flow->deficit = min(q->quantum, qdisc_pkt_len(skb));
// Alway deliver 1 packet in a new flow unless it's less than quantum
(in which case it too will be kicked to old flows)
        }

...

fq_codel_dequeue()

        if (!skb) {
                /* force a pass through old_flows to prevent starvation */
                if ((head == &q->new_flows) && !list_empty(&q->old_flows))
                        list_move_tail(&flow->flowchain, &q->old_flows);
                else
                        list_del_init(&flow->flowchain);
                goto begin;
        }
        qdisc_bstats_update(sch, skb);
        flow->deficit -= qdisc_pkt_len(skb);
/* do DRR instead */
//      if (!list_empty(&flow->flowchain) && !list_empty(head))
//              list_move_tail(&flow->flowchain, head);
// and various clueless combinations of this go boom. Or I busted
something else somewhere.