Quick Fair Queue Scheduler maturity and examples

Quick Fair Queue Scheduler maturity and examples

[Karel Rericha]

Hi list,

has anyone some experience about QFQ and its maturity ? I was not able
to find anything more than patches and papers, real world examples and
info are nonexistent.

Thanks, Karel

Re: Quick Fair Queue Scheduler maturity and examples

[Andrew Beverley]

On Mon, 2011-10-24 at 11:58 +0200, Karel Rericha wrote:
> Hi list,
> 
> has anyone some experience about QFQ and its maturity ? I was not able
> to find anything more than patches and papers, real world examples and
> info are nonexistent.

You might be better posting your question to the netdev mailing list
(see http://vger.kernel.org/vger-lists.html#netdev). Strictly speaking
this is the netfilter list and QFQ falls outside of that.

Andy

Re: Quick Fair Queue Scheduler maturity and examples

[Karel Rericha]

2011/10/25 Andrew Beverley <andy@andybev.com>:
> On Mon, 2011-10-24 at 11:58 +0200, Karel Rericha wrote:
>> Hi list,
>>
>> has anyone some experience about QFQ and its maturity ? I was not able
>> to find anything more than patches and papers, real world examples and
>> info are nonexistent.
>
> You might be better posting your question to the netdev mailing list
> (see http://vger.kernel.org/vger-lists.html#netdev). Strictly speaking
> this is the netfilter list and QFQ falls outside of that.
>
> Andy
>

Well, I am somewhat confused now, because I see that packet schedulers
(HTB, HFSC) are discussed here, but for some reason QFQ is in netdev
list as you pointed out. I will try there, thanks.

Karel

Re: Quick Fair Queue Scheduler maturity and examples

[Andrew Beverley]

On Thu, 2011-10-27 at 10:41 +0200, Karel Rericha wrote:
> 2011/10/25 Andrew Beverley <andy@andybev.com>:
> > On Mon, 2011-10-24 at 11:58 +0200, Karel Rericha wrote:
> >> Hi list,
> >>
> >> has anyone some experience about QFQ and its maturity ? I was not able
> >> to find anything more than patches and papers, real world examples and
> >> info are nonexistent.
> >
> > You might be better posting your question to the netdev mailing list
> > (see http://vger.kernel.org/vger-lists.html#netdev). Strictly speaking
> > this is the netfilter list and QFQ falls outside of that.
> >
> > Andy
> >
> 
> Well, I am somewhat confused now, because I see that packet schedulers
> (HTB, HFSC) are discussed here,

Strictly speaking this list is just for netfilter related discussions,
which all of the packet schedulers fall outside of. However, since the
demise of the LARTC mailing list, this list tends to get used for other
discussions, as there is a good chance you'll get an answer here anyway.

Andy

Re: Quick Fair Queue scheduler maturity and examples

[David Täht]

[-- Attachment #1: Type: text/plain, Size: 2924 bytes --]

On 11/02/2011 11:31 AM, Eric Dumazet wrote:
> Le mercredi 02 novembre 2011 à 11:05 +0100, David Täht a écrit :
>> (Example elided, see thread on netdev)
>>
>> On 11/02/2011 10:36 AM, Karel Rericha wrote:
>>> 2011/10/27 Eric Dumazet<eric.dumazet@gmail.com>:
>>> Thanks for example Eric. But it only added more confusion to me now
>>> :-) I was under impression (and read somewhere) that QFQ is non work
>>> conserving scheduler so I can use it more or less like HTB or HFSC to
>>> set bandwidth constraints to flows. But from this example (and from
>>> sources/patches/papers I try not to pretend I fully understand) it
>>> looks to me like some multiqueue scheduler with arbitrary number of
>>> queues and ability to arbitrary assign flows to this queues. So some
>>> sort of fair division of available bandwidth to flows without
>>> arbitrary bandwidth caps to these flows.
>> This is what I want! It may not be what you want...
>>> I really dont see what is non work conserving here :-S Please save my
>>> soul and enlighten me because I am at dead end now :-)
>> I initially had great hope for QFQ as I've been saying (mostly
>> privately) that "PFIFO_FAST must die" for over a year now. What to
>> replace it with is a rather large question, but I felt a start would be
>> to adopt some FQ algorithm. Over the last couple weeks I read all the
>> papers regarding DRR and QFQ and also poked into the source code and
>> like you, am seriously un-enlightened.
>>
>> I think eric's example is misleading as he divided up the queues by
>> bandwidth, rather than flow, in the first tier of his tc hierarchy.
>> useful as a test...
> It seems there is a bit of misunderstanding here.
>
> QFQ is not a 'all is included' in one qdisc, like SFQ
I grok. (or rather, I did after some reading last week)
>
> You really need to setup qfq classes, and describe how packets are
> mapped to qfq classes (this is done by an external flow classifier)

It would be mildly better (in the case of wireless) to be able to do
flow classification based on the nexthop mac, which while introducing an
extra routing table lookup, would improve packet aggregation
probabilities in the multiple ip or multi-hop wireless case.

I don't know if a route lookup of dest mac could be correctly done at 
this layer.

> It also has no internal (default) flow classifier like SFQ did.
>
> It has of course no bandwidth constraints. If you need to shape and use
> QFQ, you'll have to use QFQ + a shaping qdisc. (This is why I used HTB
> in my script because I wanted to shape)

I just want FQ... for now.

> If you dont need to shape, you still need to describe/setup qfq classes
> and chose appropriate flow classifier.
>

Trying for two levels of flow classification here, which I still doubt I
can do here... hmm, perhaps with ifb...

don't want to shape, want to ultimately apply some level of a post-RED 
AQM to the overall flows
>


-- 
Dave Täht


[-- Attachment #2: dave_taht.vcf --]
[-- Type: text/x-vcard, Size: 214 bytes --]

begin:vcard
fn;quoted-printable:Dave T=C3=A4ht
n;quoted-printable:T=C3=A4ht;Dave
email;internet:dave.taht@gmail.com
tel;home:1-239-829-5608
tel;cell:0638645374
x-mozilla-html:FALSE
version:2.1
end:vcard

Re: Quick Fair Queue scheduler maturity and examples

[Eric Dumazet]

Le mercredi 02 novembre 2011 à 11:05 +0100, David Täht a écrit :
> (Example elided, see thread on netdev)
> 
> On 11/02/2011 10:36 AM, Karel Rericha wrote:
> > 2011/10/27 Eric Dumazet<eric.dumazet@gmail.com>:
> > Thanks for example Eric. But it only added more confusion to me now 
> > :-) I was under impression (and read somewhere) that QFQ is non work 
> > conserving scheduler so I can use it more or less like HTB or HFSC to 
> > set bandwidth constraints to flows. But from this example (and from 
> > sources/patches/papers I try not to pretend I fully understand) it 
> > looks to me like some multiqueue scheduler with arbitrary number of 
> > queues and ability to arbitrary assign flows to this queues. So some 
> > sort of fair division of available bandwidth to flows without 
> > arbitrary bandwidth caps to these flows. 
> This is what I want! It may not be what you want...
> > I really dont see what is non work conserving here :-S Please save my 
> > soul and enlighten me because I am at dead end now :-)
> 
> I initially had great hope for QFQ as I've been saying (mostly 
> privately) that "PFIFO_FAST must die" for over a year now. What to 
> replace it with is a rather large question, but I felt a start would be 
> to adopt some FQ algorithm. Over the last couple weeks I read all the 
> papers regarding DRR and QFQ and also poked into the source code and 
> like you, am seriously un-enlightened.
> 
> I think eric's example is misleading as he divided up the queues by 
> bandwidth, rather than flow, in the first tier of his tc hierarchy. 
> useful as a test...

It seems there is a bit of misunderstanding here.

QFQ is not a 'all is included' in one qdisc, like SFQ

You really need to setup qfq classes, and describe how packets are
mapped to qfq classes (this is done by an external flow classifier)

It also has no internal (default) flow classifier like SFQ did.

It has of course no bandwidth constraints. If you need to shape and use
QFQ, you'll have to use QFQ + a shaping qdisc. (This is why I used HTB
in my script because I wanted to shape)

If you dont need to shape, you still need to describe/setup qfq classes
and chose appropriate flow classifier.



_______________________________________________
Bloat mailing list
Bloat@lists.bufferbloat.net
https://lists.bufferbloat.net/listinfo/bloat

Re: Quick Fair Queue scheduler maturity and examples

[David Täht]

[-- Attachment #1: Type: text/plain, Size: 3011 bytes --]

(Example elided, see thread on netdev)

On 11/02/2011 10:36 AM, Karel Rericha wrote:
> 2011/10/27 Eric Dumazet<eric.dumazet@gmail.com>:
> Thanks for example Eric. But it only added more confusion to me now 
> :-) I was under impression (and read somewhere) that QFQ is non work 
> conserving scheduler so I can use it more or less like HTB or HFSC to 
> set bandwidth constraints to flows. But from this example (and from 
> sources/patches/papers I try not to pretend I fully understand) it 
> looks to me like some multiqueue scheduler with arbitrary number of 
> queues and ability to arbitrary assign flows to this queues. So some 
> sort of fair division of available bandwidth to flows without 
> arbitrary bandwidth caps to these flows. 
This is what I want! It may not be what you want...
> I really dont see what is non work conserving here :-S Please save my 
> soul and enlighten me because I am at dead end now :-)

I initially had great hope for QFQ as I've been saying (mostly 
privately) that "PFIFO_FAST must die" for over a year now. What to 
replace it with is a rather large question, but I felt a start would be 
to adopt some FQ algorithm. Over the last couple weeks I read all the 
papers regarding DRR and QFQ and also poked into the source code and 
like you, am seriously un-enlightened.

I think eric's example is misleading as he divided up the queues by 
bandwidth, rather than flow, in the first tier of his tc hierarchy. 
useful as a test...

That said, buried in one of the papers on QFQ is the item that it isn't 
entirely fair queuing, as it has a maximum MSS of 5, rather than 1. 
Still that would be an improvement over diffserv based classification in 
the general case, and being somewhat bursty actually helps with 802.11n 
packet aggregation (at present).

Anyway, I've built QFQ into the latest cerowrt and am building it for 
another machine, and will try to come up with good ways to configure it 
this week.

My use cases are different than yours, however.

On a wireless STA (a laptop) - FQ all flows originating from that box. 
This would, for example, jump a DNS packet, ping, or TCP SYN attempt - 
to near the beginning of the transmit buffer while another elephant flow 
is taking place.

On the AP, FQ across the clients (so aggregation works better and 
bittorrent is suppressed), and FQ within each flow from/to that client 
(so as to reduce head of line blocking and have better performance for 
things like dns/ping/etc) - this would apply to the internal wireless 
and wired interfaces. As for the gateway interface, FQ across 
originating clients as well (but far more stuff than that needs to happen)

Haven't a clue how to do any of that right at all, at present. Clues 
wanted. I emailed one of the authors of QFQ for a clue, no reply as yet....

PS Also along the way whilst poking into that source code I found that 
there was already a fifo_drop_head tc queue type, which strikes me as 
almost useful for VO and VI wireless queues...

-- 
Dave Täht


[-- Attachment #2: dave_taht.vcf --]
[-- Type: text/x-vcard, Size: 204 bytes --]

begin:vcard
fn;quoted-printable:Dave T=C3=A4ht
n;quoted-printable:T=C3=A4ht;Dave
email;internet:dave.taht@gmail.com
tel;home:1-239-829-5608
tel;cell:0638645374
x-mozilla-html:FALSE
version:2.1
end:vcard

Re: Quick Fair Queue scheduler maturity and examples

[Karel Rericha]

2011/10/27 Eric Dumazet <eric.dumazet@gmail.com>:
> Le jeudi 27 octobre 2011 à 18:08 +0200, Eric Dumazet a écrit :
>> Le jeudi 27 octobre 2011 à 14:46 +0200, Karel Rericha a écrit :
>>
>> > Actually I am doing some reseach to replace our main shaping machine
>> > with 60 000+ htb classes, which now saturates 12 core Xeon Westmere to
>> > 30% (there are five gigabit network ports on each interface affinited
>> > to cores). AFAIK QFQ should be O(1) complexity so it would bring
>> > saturation a requirements for number of cores down considerably (HTB
>> > has O(log(N)) complexity).
>> >
>> > I have test machine and about two months to decide if we will stay
>> > with HTB or we will try something else. So it would be VERY helpful,
>> > if you would search you memory instead your dead disk :-) and send me
>> > some example of QFQ usage, if I can ask for a little of your time. I
>> > promise to have results published here in return.
>> >
>> > Thanks, Karel
>> >
>>
>> That seems a good challenge to me ;)
>>
>> First upgrade to a recent kernel with QFQ included.
>> Also upgrade iproute2 to a recent enough version as well.
>>
>> Then you discover "tc  ... qfq help" is not that helpful :(
>>
>> # tc qdisc add dev eth3 root qfq help
>> Usage: ... qfq
>>
>> OK, its parameters are :
>>
>>       qfq weight num1 [maxpkt BYTES]
>>
>> You should not touch maxpkt, its default value being 2048
>>
>> Oh well, I just tried the obvious and my (remote) machine doesnt answer
>> to me anymore...
>>
>> Time for a bit of debugging I am afraid :(
>
> Never mind, it was an user error :)
>
> Here is what I used during my tests, I guess you can adapt your
> scripts...
>
> DEV=eth3
> RATE="rate 40Mbit"
> TNETS="10.2.2.0/25"
> ALLOT="allot 20000"
>
> tc qdisc del dev dummy0 root 2>/dev/null
>
> tc qdisc add dev $DEV root handle 1: cbq avpkt 1000 rate 1000Mbit \
>        bandwidth 1000Mbit
> tc class add dev $DEV parent 1: classid 1:1 \
>        est 1sec 8sec cbq allot 10000 mpu 64 \
>        rate 1000Mbit prio 1 avpkt 1500 bounded
>
> # output to test nets :  40 Mbit limit
> tc class add dev $DEV parent 1:1 classid 1:11 \
>        est 1sec 8sec cbq $ALLOT mpu 64      \
>        $RATE prio 2 avpkt 1400 bounded
>
> tc qdisc add dev $DEV parent 1:11 handle 11:  \
>        est 1sec 8sec qfq
>
> tc filter add dev $DEV protocol ip parent 11: handle 3 \
>        flow hash keys rxhash divisor 8
>
> for i in `seq 1 8`
> do
>  classid=11:$(printf %x $i)
>  tc class add dev $DEV classid $classid qfq
>  tc qdisc add dev $DEV parent $classid pfifo limit 30
> done
>
> for privnet in $TNETS
> do
>        tc filter add dev $DEV parent 1: protocol ip prio 100 u32 \
>                match ip dst $privnet flowid 1:11
> done
>
> tc filter add dev $DEV parent 1: protocol ip prio 100 u32 \
>        match ip protocol 0 0x00 flowid 1:1
>
> iperf -u -c 10.2.2.1 -P 32 -l 50
>
>
>

Thanks for example Eric.

But it only added more confusion to me now :-) I was under impression
(and read somewhere) that QFQ is non work conserving scheduler so I
can use it more or less like HTB or HFSC to set bandwidth constraints
to flows. But from this example (and from sources/patches/papers I try
not to pretend I fully understand) it looks to me like some multiqueue
scheduler with arbitrary number of queues and ability to arbitrary
assign flows to this queues. So some sort of fair division of
available bandwidth to flows without arbitrary bandwidth caps to these
flows. I really dont see what is non work conserving here :-S

Please save my soul and enlighten me because I am at dead end now :-)

Re: Quick Fair Queue scheduler maturity and examples

[Eric Dumazet]

Le jeudi 27 octobre 2011 à 18:08 +0200, Eric Dumazet a écrit :
> Le jeudi 27 octobre 2011 à 14:46 +0200, Karel Rericha a écrit :
> 
> > Actually I am doing some reseach to replace our main shaping machine
> > with 60 000+ htb classes, which now saturates 12 core Xeon Westmere to
> > 30% (there are five gigabit network ports on each interface affinited
> > to cores). AFAIK QFQ should be O(1) complexity so it would bring
> > saturation a requirements for number of cores down considerably (HTB
> > has O(log(N)) complexity).
> > 
> > I have test machine and about two months to decide if we will stay
> > with HTB or we will try something else. So it would be VERY helpful,
> > if you would search you memory instead your dead disk :-) and send me
> > some example of QFQ usage, if I can ask for a little of your time. I
> > promise to have results published here in return.
> > 
> > Thanks, Karel
> > 
> 
> That seems a good challenge to me ;)
> 
> First upgrade to a recent kernel with QFQ included.
> Also upgrade iproute2 to a recent enough version as well.
> 
> Then you discover "tc  ... qfq help" is not that helpful :(
> 
> # tc qdisc add dev eth3 root qfq help
> Usage: ... qfq
> 
> OK, its parameters are :
> 
> 	qfq weight num1 [maxpkt BYTES]
> 
> You should not touch maxpkt, its default value being 2048
> 
> Oh well, I just tried the obvious and my (remote) machine doesnt answer
> to me anymore...
> 
> Time for a bit of debugging I am afraid :(

Never mind, it was an user error :)

Here is what I used during my tests, I guess you can adapt your
scripts...

DEV=eth3
RATE="rate 40Mbit"
TNETS="10.2.2.0/25"
ALLOT="allot 20000"

tc qdisc del dev dummy0 root 2>/dev/null

tc qdisc add dev $DEV root handle 1: cbq avpkt 1000 rate 1000Mbit \
	bandwidth 1000Mbit
tc class add dev $DEV parent 1: classid 1:1 \
	est 1sec 8sec cbq allot 10000 mpu 64 \
	rate 1000Mbit prio 1 avpkt 1500 bounded

# output to test nets :  40 Mbit limit
tc class add dev $DEV parent 1:1 classid 1:11 \
	est 1sec 8sec cbq $ALLOT mpu 64      \
	$RATE prio 2 avpkt 1400 bounded

tc qdisc add dev $DEV parent 1:11 handle 11:  \
	est 1sec 8sec qfq

tc filter add dev $DEV protocol ip parent 11: handle 3 \
	flow hash keys rxhash divisor 8

for i in `seq 1 8`
do
 classid=11:$(printf %x $i)
 tc class add dev $DEV classid $classid qfq 
 tc qdisc add dev $DEV parent $classid pfifo limit 30
done

for privnet in $TNETS
do
	tc filter add dev $DEV parent 1: protocol ip prio 100 u32 \
		match ip dst $privnet flowid 1:11
done

tc filter add dev $DEV parent 1: protocol ip prio 100 u32 \
	match ip protocol 0 0x00 flowid 1:1

iperf -u -c 10.2.2.1 -P 32 -l 50

Re: Quick Fair Queue scheduler maturity and examples

[Eric Dumazet]

Le jeudi 27 octobre 2011 à 14:46 +0200, Karel Rericha a écrit :

> Actually I am doing some reseach to replace our main shaping machine
> with 60 000+ htb classes, which now saturates 12 core Xeon Westmere to
> 30% (there are five gigabit network ports on each interface affinited
> to cores). AFAIK QFQ should be O(1) complexity so it would bring
> saturation a requirements for number of cores down considerably (HTB
> has O(log(N)) complexity).
> 
> I have test machine and about two months to decide if we will stay
> with HTB or we will try something else. So it would be VERY helpful,
> if you would search you memory instead your dead disk :-) and send me
> some example of QFQ usage, if I can ask for a little of your time. I
> promise to have results published here in return.
> 
> Thanks, Karel
> 

That seems a good challenge to me ;)

First upgrade to a recent kernel with QFQ included.
Also upgrade iproute2 to a recent enough version as well.

Then you discover "tc  ... qfq help" is not that helpful :(

# tc qdisc add dev eth3 root qfq help
Usage: ... qfq

OK, its parameters are :

	qfq weight num1 [maxpkt BYTES]

You should not touch maxpkt, its default value being 2048

Oh well, I just tried the obvious and my (remote) machine doesnt answer
to me anymore...

Time for a bit of debugging I am afraid :(

Re: Quick Fair Queue scheduler maturity and examples

[Karel Rericha]

2011/10/27 Eric Dumazet <eric.dumazet@gmail.com>:
> Le jeudi 27 octobre 2011 à 13:30 +0200, Karel Rericha a écrit :
>> Hi list,
>>
>> has anyone some experience about QFQ and its maturity ? I was not able
>> to find anything more than patches and papers, real world examples and
>> info are nonexistent.
>>
>
> At its inclusion time (in linux 3.0), I did many tests and feedback to
> Stephen.
>
> By the way, QFQ is not only patches and papers, its now officially
> supported by linux netdev team ;)
>
> Unfortunately the machine where I kept traces of my qfq scripts was
> totally lost, no backups.... oh well...
>
> Given that not a single patch was added since initial commit, I guess
> nobody really uses the thing, or its perfect, who knows :)
>
> You definitely should be able to use it, and report here problems if
> any.
>

Actually I am doing some reseach to replace our main shaping machine
with 60 000+ htb classes, which now saturates 12 core Xeon Westmere to
30% (there are five gigabit network ports on each interface affinited
to cores). AFAIK QFQ should be O(1) complexity so it would bring
saturation a requirements for number of cores down considerably (HTB
has O(log(N)) complexity).

I have test machine and about two months to decide if we will stay
with HTB or we will try something else. So it would be VERY helpful,
if you would search you memory instead your dead disk :-) and send me
some example of QFQ usage, if I can ask for a little of your time. I
promise to have results published here in return.

Thanks, Karel

BTW I can provide some virtual Gentoo servers for test setup if you
would want participate in further testing.

Re: Quick Fair Queue scheduler maturity and examples

[Eric Dumazet]

Le jeudi 27 octobre 2011 à 13:30 +0200, Karel Rericha a écrit :
> Hi list,
> 
> has anyone some experience about QFQ and its maturity ? I was not able
> to find anything more than patches and papers, real world examples and
> info are nonexistent.
> 

At its inclusion time (in linux 3.0), I did many tests and feedback to
Stephen.

By the way, QFQ is not only patches and papers, its now officially
supported by linux netdev team ;)

Unfortunately the machine where I kept traces of my qfq scripts was
totally lost, no backups.... oh well...

Given that not a single patch was added since initial commit, I guess
nobody really uses the thing, or its perfect, who knows :)

You definitely should be able to use it, and report here problems if
any.

Quick Fair Queue scheduler maturity and examples

[Karel Rericha]

Hi list,

has anyone some experience about QFQ and its maturity ? I was not able
to find anything more than patches and papers, real world examples and
info are nonexistent.

Thanks, Karel