[Cerowrt-devel] [Bloat] [Codel] FQ_Codel lwn draft article review

[Eric Dumazet]

On Sun, 2012-12-02 at 22:37 +0100, Toke Høiland-Jørgensen wrote:
> Eric Dumazet <eric.dumazet at gmail.com> writes:
> 
> > This can help if you really want to avoid a thick flow sharing a thin
> > flow bucket, but given that all packets are going eventually into the
> > Internet (or equivalent crowded network), its not really a clear win.
> 
> I've been trying to grok the fq_codel code by reading through it while
> following the discussion in the article, and I'm having a bit of trouble
> squaring the thin/thick (or "hog"/"non-hog") flow designation of the
> article with the code. As far as I can tell from the code, there are two
> lists, called new_flows and old_flows; and a flow starts out as 'new'
> and stays that way until it has sent a quantum of bytes or codel fails
> to dequeue a packet from it, whereupon it is moved to the end of the
> old_flows list. It then stays in the old_flows list for the rest of its
> "life".

Not at all.

If a cell has :
  - a positive credit/deficit
  - no more packets to send
Then 
  if is part of old_flows list, we remove it
  else we move it from new_flows to old_flows


The algo has a special shortcut to avoid a pass to old_flows if
old_flows is empty, but thats basically :

                /* force a pass through old_flows to prevent starvation */
                if (head == &q->new_flows)
                        list_move_tail(&flow->flowchain, &q->old_flows);
                else
                        list_del_init(&flow->flowchain);


Next time a packet re-activates the flow (or more exactly the bucket in
hash table), we move it to 'new_flows' only for one quantum.

> 
> Now, talking about thin flows being distinguished from thick ones, it
> seems to me that if a flow sends packets at a low enough rate it can in
> principle stay 'thin' indefinitely. So I'm assuming I've missed
> something in the code that allows a flow to stay in the new_flows list
> if it is sufficiently thin. Could someone please point out to me what
> I'm missing? :)
> 

I dont know, this new_flow/old_flows seems too hard to understand for
most readers of the code.

I saw many people confused by this algo.

Of course, a thin flow stay thin, if the bucket can be in the following
states, forever :

- empty
- packet arrives -> bucket queued to end of new_flows
- packet is dequeued.
- as bucket is empty, move bucket to end of old_flows
- next time we hit this bucket (because we processed all packets from
old_flows), we remove it from the list and its state becomes 'empty'

If the next packet arrives while the bucket is still in old_flows,
we wont put the bucket in new_flow, its bucket have to wait its turn in
the RR list.

Think of it this way : If a bucket lost its turn in the RRR mechanism
and became idle, it has its deficit refilled to 'q->quantum', and it has
the right to be elected as a new_flow next time a packet wants to use
this bucket.