[Codel] fq_codel: revenge of the standing queue

[Dave Taht]

On Tue, Sep 4, 2012 at 12:02 PM, Eric Dumazet <eric.dumazet at gmail.com> wrote:
> On Tue, 2012-09-04 at 11:35 -0700, Dave Taht wrote:
>
>> 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...
>
> I have no idea of what you try to say.
>
> Each flow has its own cvars :
>
> skb = codel_dequeue(sch, &q->cparams, &flow->cvars, &q->cstats,
> dequeue);

- and we exit dropping state when that queue empties, when globally,
across all the fq_codel queues, we still need to be dropping in order
to get to the target.

And that first_above time for that cvars for that fq_codel queue is
reset to 0 for that fq_codel queue when it empties, forcing a recalc
of the right interval (sojourn) for re-entering dropping state, with a
"hands off" interval...

It's seems reasonably ok for a fq_codel queue to go empty for a while
but not have to go through a sojourn again to start dropping. It makes
sense to always deliver one packet after going empty...

these thoughts are half formed, and I did my damnedest to describe the
behavior I was seeing.

> So each flow has its own codel unit.
>
> Try to view fq_codel as a multiplexor, then a Codel unit for each flow.

I do.

> So if you believe there is a bug in Codel, try to describe the big in
> Codel, not in fq_codel, because fq_codel is _not_ a codel variant.

No, this thread was about fq_codel's assumptions differences from
codel's assumptions.

Codel has it's own bugs, which I didn't talk to in this thread.

> The only thing that fq_codel codel units share are the parameters and
> stats.

Understood.

>
>
>
>
>



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