[Codel] better mixing in fq_codel

[Codel] 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.

Re: [Codel] better mixing in fq_codel

[Eric Dumazet]

On Thu, 2012-08-30 at 15:59 -0700, Dave Taht wrote:
> 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!


You dont need a patch, fq_codel has a quantum parameter, default to 1514

Just set it to 256 if you really feel the need.

Re: [Codel] better mixing in fq_codel

[Dave Taht]

On Thu, Aug 30, 2012 at 4:06 PM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> On Thu, 2012-08-30 at 15:59 -0700, Dave Taht wrote:
>> 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!
>
>
> You dont need a patch, fq_codel has a quantum parameter, default to 1514
>
> Just set it to 256 if you really feel the need.

In that case it will deliver 3 acks in a row from
stream A, and then 3 acks in stream B, in the linux 3.5 version, and
push the the 1500 byte packet from my example to the old flows queue -
instead of delivering A 1 ack, B 1 ack, push the C 1500 byte packet to
the old flows queue, then deliver A,B,A,B,A,B, A, A, A etc (and note
with more flows mixing gets better) as I just proposed.

(actually I got the idea from the current ns2 sfqcodel model.)

This variant however preserves the "prioritize the new stream slightly
idea", admittedly less than before...

>
>
>



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

Re: [Codel] better mixing in fq_codel

[Eric Dumazet]

On Thu, 2012-08-30 at 16:19 -0700, Dave Taht wrote:

> In that case it will deliver 3 acks in a row from
> stream A, and then 3 acks in stream B, in the linux 3.5 version, and
> push the the 1500 byte packet from my example to the old flows queue -

Nope, the 1500 byte packet will be sent as normal (we obviously cant
split a packet). If its the first packet (new flow), there wont be any
penalty.

> instead of delivering A 1 ack, B 1 ack, push the C 1500 byte packet to
> the old flows queue, then deliver A,B,A,B,A,B, A, A, A etc (and note
> with more flows mixing gets better) as I just proposed.

Try to change quantum, and it will just work out of the box.

Anyway, I dont think it changes anything, unless you want to use an RTC
modem ;)

Re: [Codel] better mixing in fq_codel

[Dave Taht]

On Thu, Aug 30, 2012 at 6:40 PM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> On Thu, 2012-08-30 at 16:19 -0700, Dave Taht wrote:
>
>> In that case it will deliver 3 acks in a row from
>> stream A, and then 3 acks in stream B, in the linux 3.5 version, and
>> push the the 1500 byte packet from my example to the old flows queue -
>
> Nope, the 1500 byte packet will be sent as normal (we obviously cant
> split a packet). If its the first packet (new flow), there wont be any
> penalty.
>
>> instead of delivering A 1 ack, B 1 ack, push the C 1500 byte packet to
>> the old flows queue, then deliver A,B,A,B,A,B, A, A, A etc (and note
>> with more flows mixing gets better) as I just proposed.
>
> Try to change quantum, and it will just work out of the box.

I think, eric, that you missed this portion of the idea, and that I
mis-commented it, and worse, overstated the effect of what I was
trying to do while watching it crash...

...and seeing through the dust and clouds... off in the distance...
the desirable behavior I'd been aiming for.

...

in fq_codel_enqueue...

                flow->deficit = min(q->quantum, qdisc_pkt_len(skb));
// put only 1 packet into the new flow queue unless it's more than
quantum (in which case it too will be kicked to old flows)



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