Re: [PATCH net-next-2.6] sch_sfq: allow big packets and be fair

Jarek Poplawski
2010-12-21T11:39:29Z

On Tue, Dec 21, 2010 at 11:57:17AM +0100, Eric Dumazet wrote:
> Le mardi 21 décembre 2010 ?? 10:15 +0000, Jarek Poplawski a écrit :
> > On 2010-12-21 00:16, Eric Dumazet wrote:
> > > SFQ is currently 'limited' to small packets, because it uses a 16bit
> > > allotment number per flow. Switch it to 18bit, and use appropriate
> > > handling to make sure this allotment is in [1 .. quantum] range before a
> > > new packet is dequeued, so that fairness is respected.
> >
> > Well, such two important changes should be in separate patches.
> >
> > The change of allotment limit looks OK (but I would try scaling, e.g.
> > in 16-byte chunks, btw).
> >
>
> Hmm, we could scale by 2 or 3 and keep 16bit allot/hash (faster than
> 18/14 bit bitfields on x86). Not sure its worth it (it adds two shifts
> per packet)

I'm OK with any of those methods.

> > The change in fair treatment looks dubious. A flow which uses exactly
> > it's quantum in one round will be skipped in the next round. A flow
> > which uses a bit more than its quantum in one round, will be skipped
> > too, while we should only give it less this time to keep the sum up to
> > 2 quantums. (The usual algorithm is to check if a flow has enough
> > "tickets" for sending its next packet.)
>
> Hmm...
>
> A flow which uses exactly its quantum in one round wont be skipped in
> the next round.
>
> I only made the "I pass my round to next slot in chain" in one place
> instead of two, maybe you missed the removal at the end of
> sfq_dequeue() ?
>
> - } else if ((slot->allot -= qdisc_pkt_len(skb)) <= 0) {
> - q->tail = slot;
> - slot->allot += q->quantum;
> + } else {
> + slot->allot -= qdisc_pkt_len(skb);
> }
>
> Now the check is performed at the beginning of sfq_dequeue(), to be able
> to charge a previously sent 'big packet' multiple times (faulty flow
> wont send a packet before passing xx rounds)
>
> I believe I just did the right thing. The "allot" is incremented when
> current flow "pass its round to next slot", and decremented when a
> packet is dequeued from this slot. Before being allowed to dequeue a
> packet, "allot" must be 'positive'.

Simply try to check my examples before and after. There is no skipping
of a round now. It's a serious change. Somebody tried to avoid it at
all in the current implementation. You should also think about fairness
of normal (but different) size packets.

Jarek P.