[Bloat] Fw: video about QFQ+ and DRR

[Bloat] Fw: video about QFQ+ and DRR

[Stephen Hemminger]

Thought this might be interesting to this list.
---
From: Paolo Valente 

Hi,
I just uploaded the following 7-minute video showing the QoS and the execution time of QFQ+, compared to those of DRR:
http://youtu.be/bG2ACt4na7A

I would like to advertise this video. If I may ask for your help, do you think that linux-kernel, linux-net or linux-netdev may be appropriate?
Any other suggestion is more than welcome.

Thanks,
Paolo

Re: [Bloat] Fw: video about QFQ+ and DRR

[Luigi Rizzo]

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

very nice and convincing demo.

good job paolo!

luigi

On Thu, Aug 8, 2013 at 5:49 PM, Stephen Hemminger <
stephen@networkplumber.org> wrote:

> Thought this might be interesting to this list.
> ---
> From: Paolo Valente
>
> Hi,
> I just uploaded the following 7-minute video showing the QoS and the
> execution time of QFQ+, compared to those of DRR:
> http://youtu.be/bG2ACt4na7A
>
> I would like to advertise this video. If I may ask for your help, do you
> think that linux-kernel, linux-net or linux-netdev may be appropriate?
> Any other suggestion is more than welcome.
>
> Thanks,
> Paolo
>
> _______________________________________________
> Bloat mailing list
> Bloat@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/bloat
>



-- 
-----------------------------------------+-------------------------------
 Prof. Luigi RIZZO, rizzo@iet.unipi.it  . Dip. di Ing. dell'Informazione
 http://www.iet.unipi.it/~luigi/        . Universita` di Pisa
 TEL      +39-050-2211611               . via Diotisalvi 2
 Mobile   +39-338-6809875               . 56122 PISA (Italy)
-----------------------------------------+-------------------------------

[-- Attachment #2: Type: text/html, Size: 2143 bytes --]

Re: [Bloat] Fw: video about QFQ+ and DRR

[MUSCARIELLO Luca OLNC/OLN]

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

Hi,

nice demo.

While I am not surprised about the good performance of QFQ+,
I do not understand why DRR (I guess linux SFQ, i.e. per-flow DRR+SQdrop)
works so bad.

If the two schedulers are serving the same kind of flow (IP 5-tuple) the 
level
of protection to low rate (< fair rate) flows should be the same (approx).

Maybe Paolo said that in the talk and I might have missed something.
Is QFQ+ working on a different definition of flow than DRR?, and is DRR 
Linux SFQ?


Luca



On 08/08/2013 06:09 PM, Luigi Rizzo wrote:
> very nice and convincing demo.
>
> good job paolo!
>
> luigi
>
> On Thu, Aug 8, 2013 at 5:49 PM, Stephen Hemminger 
> <stephen@networkplumber.org <mailto:stephen@networkplumber.org>> wrote:
>
>     Thought this might be interesting to this list.
>     ---
>     From: Paolo Valente
>
>     Hi,
>     I just uploaded the following 7-minute video showing the QoS and
>     the execution time of QFQ+, compared to those of DRR:
>     http://youtu.be/bG2ACt4na7A
>
>     I would like to advertise this video. If I may ask for your help,
>     do you think that linux-kernel, linux-net or linux-netdev may be
>     appropriate?
>     Any other suggestion is more than welcome.
>
>     Thanks,
>     Paolo
>
>     _______________________________________________
>     Bloat mailing list
>     Bloat@lists.bufferbloat.net <mailto:Bloat@lists.bufferbloat.net>
>     https://lists.bufferbloat.net/listinfo/bloat
>
>
>
>
> -- 
> -----------------------------------------+-------------------------------
>  Prof. Luigi RIZZO, rizzo@iet.unipi.it <mailto:rizzo@iet.unipi.it>  . 
> Dip. di Ing. dell'Informazione
> http://www.iet.unipi.it/~luigi/ <http://www.iet.unipi.it/%7Eluigi/>   
>      . Universita` di Pisa
>  TEL      +39-050-2211611               . via Diotisalvi 2
>  Mobile   +39-338-6809875               . 56122 PISA (Italy)
> -----------------------------------------+-------------------------------
>
>
> _______________________________________________
> Bloat mailing list
> Bloat@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/bloat


[-- Attachment #2: Type: text/html, Size: 4730 bytes --]

Re: [Bloat] Fw: video about QFQ+ and DRR

[Paolo Valente]

Il giorno 09/ago/2013, alle ore 08:45, MUSCARIELLO Luca OLNC/OLN ha scritto:

> Hi,
> 
> nice demo.
> 
Thanks.

> While I am not surprised about the good performance of QFQ+,
> I do not understand why DRR (I guess linux SFQ, i.e. per-flow DRR+SQdrop)
> works so bad.
> 
> If the two schedulers are serving the same kind of flow (IP 5-tuple) the level
> of protection to low rate (< fair rate) flows should be the same (approx).
> 
That 'approx' plays a critical role for the bad results with DRR. In particular, problems arise because of the following theoretical issue.
Consider the packet service time for a flow, i.e., the time to transmit one maximum-size packet of the flow at the rate reserved to the flow. For each flow, the worst-case packet delay/jitter guaranteed by QFQ+, with respect to packet completion times in an ideal, perfectly fair system, is equal to a few times the packet service time for the flow. In contrast, with DRR this delay/jitter is independent of the packet service time, and grows linearly with the number of flows.
Hence, the shorter the packet service time is, the higher this delay becomes with respect to the packet service time.

In the In the test, 
1) the total number of flows N is equal to 501,
2) the video-streaming server is reserved a bandwidth such that its packet service time complies with the frame playback period,
3) the time to transmit 500 maximum-size packets at line rate is much higher than the packet service for the video-streaming server, and hence, of the frame period.

As a consequence, when DRR incurs its physiological O(N) delay, the playback buffer on the client side runs out of frames.

> Maybe Paolo said that in the talk and I might have missed something.
> Is QFQ+ working on a different definition of flow than DRR?,
No, on the same.
> and is DRR Linux SFQ?
> 
No, it is just DRR (sch_drr.c).

I hope I was not too confusing, and I am willing to answer any further question,
Paolo
> 
> Luca
> 
> 
> 
> On 08/08/2013 06:09 PM, Luigi Rizzo wrote:
>> very nice and convincing demo.
>> 
>> good job paolo!
>> 
>> luigi
>> 
>> On Thu, Aug 8, 2013 at 5:49 PM, Stephen Hemminger <stephen@networkplumber.org> wrote:
>> Thought this might be interesting to this list.
>> ---
>> From: Paolo Valente
>> 
>> Hi,
>> I just uploaded the following 7-minute video showing the QoS and the execution time of QFQ+, compared to those of DRR:
>> http://youtu.be/bG2ACt4na7A
>> 
>> I would like to advertise this video. If I may ask for your help, do you think that linux-kernel, linux-net or linux-netdev may be appropriate?
>> Any other suggestion is more than welcome.
>> 
>> Thanks,
>> Paolo
>> 
>> _______________________________________________
>> Bloat mailing list
>> Bloat@lists.bufferbloat.net
>> https://lists.bufferbloat.net/listinfo/bloat
>> 
>> 
>> 
>> -- 
>> -----------------------------------------+-------------------------------
>>  Prof. Luigi RIZZO, rizzo@iet.unipi.it  . Dip. di Ing. dell'Informazione
>>  http://www.iet.unipi.it/~luigi/        . Universita` di Pisa
>>  TEL      +39-050-2211611               . via Diotisalvi 2
>>  Mobile   +39-338-6809875               . 56122 PISA (Italy)
>> -----------------------------------------+-------------------------------
>> 
>> 
>> _______________________________________________
>> Bloat mailing list
>> 
>> Bloat@lists.bufferbloat.net
>> https://lists.bufferbloat.net/listinfo/bloat
> 


--
Paolo Valente                                                 
Algogroup
Dipartimento di Fisica, Informatica e Matematica		
Via Campi, 213/B
41125 Modena - Italy        				  
homepage:  http://algogroup.unimore.it/people/paolo/

Re: [Bloat] Fw: video about QFQ+ and DRR

[MUSCARIELLO Luca OLNC/OLN]

Hi,

few questions in line.

Luca


On 08/09/2013 09:58 AM, Paolo Valente wrote:
> Il giorno 09/ago/2013, alle ore 08:45, MUSCARIELLO Luca OLNC/OLN ha scritto:
>
>> Hi,
>>
>> nice demo.
>>
> Thanks.
>
>> While I am not surprised about the good performance of QFQ+,
>> I do not understand why DRR (I guess linux SFQ, i.e. per-flow DRR+SQdrop)
>> works so bad.
>>
>> If the two schedulers are serving the same kind of flow (IP 5-tuple) the level
>> of protection to low rate (< fair rate) flows should be the same (approx).
>>
> That 'approx' plays a critical role for the bad results with DRR. In particular, problems arise because of the following theoretical issue.
> Consider the packet service time for a flow, i.e., the time to transmit one maximum-size packet of the flow at the rate reserved to the flow. For each flow, the worst-case packet delay/jitter guaranteed by QFQ+, with respect to packet completion times in an ideal, perfectly fair system, is equal to a few times the packet service time for the flow. In contrast, with DRR this delay/jitter is independent of the packet service time, and grows linearly with the number of flows.
> Hence, the shorter the packet service time is, the higher this delay becomes with respect to the packet service time.
>
> In the In the test,
> 1) the total number of flows N is equal to 501,
> 2) the video-streaming server is reserved a bandwidth such that its packet service time complies with the frame playback period,
> 3) the time to transmit 500 maximum-size packets at line rate is much higher than the packet service for the video-streaming server, and hence, of the frame period.

1) AFAIK, sch_drr.c is class-based queuing and not per-flow queuing 
(correct me if I am wrong).
So, when you say N = 501 flows, do you mean that in your demo you 
configured class = flow (e.g. 5-tuple)
or you have multiple applications in the same class sharing a single 
(class) queue?

2) do you mean that the class "video" gets a weight (per-class weight, 
with one single video flow in this case?)
such that, in average, it gets a weighted fair share large enough for 
the video rate?

3) can you plug other qdiscs in QFQ+? Is  QFQ+  a candidate to replace 
HTB (or DRR) in Linux?,
or maybe  HTB is already outdated and sch_drr.c  might replace sch_htb.c 
in linux 3.7.

> As a consequence, when DRR incurs its physiological O(N) delay, the playback buffer on the client side runs out of frames.
>
>> Maybe Paolo said that in the talk and I might have missed something.
>> Is QFQ+ working on a different definition of flow than DRR?,
> No, on the same.
what is the definition of flow used or class?

Re: [Bloat] Fw: video about QFQ+ and DRR

[Paolo Valente]

Il giorno 09/ago/2013, alle ore 10:48, MUSCARIELLO Luca OLNC/OLN ha scritto:

> Hi,
> 
> few questions in line.
> 
> Luca
> 
> 
> On 08/09/2013 09:58 AM, Paolo Valente wrote:
>> Il giorno 09/ago/2013, alle ore 08:45, MUSCARIELLO Luca OLNC/OLN ha scritto:
>> 
>>> Hi,
>>> 
>>> nice demo.
>>> 
>> Thanks.
>> 
>>> While I am not surprised about the good performance of QFQ+,
>>> I do not understand why DRR (I guess linux SFQ, i.e. per-flow DRR+SQdrop)
>>> works so bad.
>>> 
>>> If the two schedulers are serving the same kind of flow (IP 5-tuple) the level
>>> of protection to low rate (< fair rate) flows should be the same (approx).
>>> 
>> That 'approx' plays a critical role for the bad results with DRR. In particular, problems arise because of the following theoretical issue.
>> Consider the packet service time for a flow, i.e., the time to transmit one maximum-size packet of the flow at the rate reserved to the flow. For each flow, the worst-case packet delay/jitter guaranteed by QFQ+, with respect to packet completion times in an ideal, perfectly fair system, is equal to a few times the packet service time for the flow. In contrast, with DRR this delay/jitter is independent of the packet service time, and grows linearly with the number of flows.
>> Hence, the shorter the packet service time is, the higher this delay becomes with respect to the packet service time.
>> 
>> In the In the test,
>> 1) the total number of flows N is equal to 501,
>> 2) the video-streaming server is reserved a bandwidth such that its packet service time complies with the frame playback period,
>> 3) the time to transmit 500 maximum-size packets at line rate is much higher than the packet service for the video-streaming server, and hence, of the frame period.
> 
> 1) AFAIK, sch_drr.c is class-based queuing and not per-flow queuing (correct me if I am wrong).
Certainly it is a classful queueing discipline. Just to sync with you, what do you mean with per-flow as opposed to class-based?
Do you mean that the scheduler internally and autonomously differentiates packets into distinct flows according to some internal classification rule (as it is the case for SFQ)?
If so, then you are right.

> So, when you say N = 501 flows, do you mean that in your demo you configured class = flow (e.g. 5-tuple)
> or you have multiple applications in the same class sharing a single (class) queue?
> 
500 classes, one for each UDP flow, plus one class for the video stream.

> 2) do you mean that the class "video" gets a weight (per-class weight, with one single video flow in this case?)
> such that, in average, it gets a weighted fair share large enough for the video rate?
> 
Yes

> 3) can you plug other qdiscs in QFQ+?
If you mean creating a hierarchy in which some of the classes scheduled by QFQ+ contain both a different queueing discipline and other classes scheduled by that internal discipline, then yes.

> Is  QFQ+  a candidate to replace HTB (or DRR) in Linux?,
Of course in my position I can answer such a question only in principle. HTB does things that QFQ+ does not, such as rate limitation. In my demo I used exactly HTB to limit the rate.
Instead, as for DRR, its final goal perfectly matches that of QFQ+. There are however scenarios where DRR is faster than QFQ+, and may even provide a better delay/jitter. Basically, it happens when all flows/classes have the same weight and the same packet length, i.e., exactly in the cases where you do not need a more accurate fair-queueing scheduler than DRR.

> or maybe  HTB is already outdated and sch_drr.c  might replace sch_htb.c in linux 3.7.
> 
>> As a consequence, when DRR incurs its physiological O(N) delay, the playback buffer on the client side runs out of frames.
>> 
>>> Maybe Paolo said that in the talk and I might have missed something.
>>> Is QFQ+ working on a different definition of flow than DRR?,
>> No, on the same.
> what is the definition of flow used or class?
> 
flow = class in the test

Paolo

--
Paolo Valente                                                 
Algogroup
Dipartimento di Fisica, Informatica e Matematica		
Via Campi, 213/B
41125 Modena - Italy        				  
homepage:  http://algogroup.unimore.it/people/paolo/

Re: [Bloat] Fw: video about QFQ+ and DRR

[MUSCARIELLO Luca OLNC/OLN]

On 08/09/2013 11:35 AM, Paolo Valente wrote:
>> >1) AFAIK, sch_drr.c is class-based queuing and not per-flow queuing (correct me if I am wrong).
> Certainly it is a classful queueing discipline. Just to sync with you, what do you mean with per-flow as opposed to class-based?
> Do you mean that the scheduler internally and autonomously differentiates packets into distinct flows according to some internal classification rule (as it is the case for SFQ)?
> If so, then you are right.

Class-based queuing and flow-based queuing of course are different things,
but from your demo I got the impressions that you were using class and flow
interchangeably.

In practice, I do not see when you would need 500 classes while it might 
happen
to have 500 flows (active and in progress ) on a link.

I think both are needed but while class-based queuing is well accepted 
flow-based is not.

Luca

Re: [Bloat] Fw: video about QFQ+ and DRR

[Luigi Rizzo]

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

On Fri, Aug 9, 2013 at 1:02 PM, MUSCARIELLO Luca OLNC/OLN <
luca.muscariello@orange.com> wrote:

>
> On 08/09/2013 11:35 AM, Paolo Valente wrote:
>
>> >1) AFAIK, sch_drr.c is class-based queuing and not per-flow queuing
>>> (correct me if I am wrong).
>>>
>> Certainly it is a classful queueing discipline. Just to sync with you,
>> what do you mean with per-flow as opposed to class-based?
>> Do you mean that the scheduler internally and autonomously differentiates
>> packets into distinct flows according to some internal classification rule
>> (as it is the case for SFQ)?
>> If so, then you are right.
>>
>
> Class-based queuing and flow-based queuing of course are different things,
> but from your demo I got the impressions that you were using class and flow
> interchangeably.
>
> In practice, I do not see when you would need 500 classes while it might
> happen
> to have 500 flows (active and in progress ) on a link.
>
>
think of an ISP that sells bandwidth to multiple customers.
Then you really want to have one class per customer, instead
of imposing hard limits on each of them (leading to poor use
of spare resources), or putting all of them in the same bucket.

As a matter of fact, for almost a decade ISPs in various places
have been using ipfw+dummynet (which includes qfq and other schedulers)
to sell bandwidth to customers.

ipfw has some very cheap instructions to flexibly group flows into classes,
even large numbers of them.

cheers
luigi

[-- Attachment #2: Type: text/html, Size: 2211 bytes --]

Re: [Bloat] Fw: video about QFQ+ and DRR

[MUSCARIELLO Luca OLNC/OLN]

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

On 08/09/2013 01:30 PM, Luigi Rizzo wrote:
>
>
> On Fri, Aug 9, 2013 at 1:02 PM, MUSCARIELLO Luca OLNC/OLN 
> <luca.muscariello@orange.com <mailto:luca.muscariello@orange.com>> wrote:
>
>
>     On 08/09/2013 11:35 AM, Paolo Valente wrote:
>
>             >1) AFAIK, sch_drr.c is class-based queuing and not
>             per-flow queuing (correct me if I am wrong).
>
>         Certainly it is a classful queueing discipline. Just to sync
>         with you, what do you mean with per-flow as opposed to
>         class-based?
>         Do you mean that the scheduler internally and autonomously
>         differentiates packets into distinct flows according to some
>         internal classification rule (as it is the case for SFQ)?
>         If so, then you are right.
>
>
>     Class-based queuing and flow-based queuing of course are different
>     things,
>     but from your demo I got the impressions that you were using class
>     and flow
>     interchangeably.
>
>     In practice, I do not see when you would need 500 classes while it
>     might happen
>     to have 500 flows (active and in progress ) on a link.
>
>
> think of an ISP that sells bandwidth to multiple customers.
> Then you really want to have one class per customer, instead
> of imposing hard limits on each of them (leading to poor use
> of spare resources), or putting all of them in the same bucket.

This indeed might happen in the BAS for ADSL users.

>
> As a matter of fact, for almost a decade ISPs in various places
> have been using ipfw+dummynet (which includes qfq and other schedulers)
> to sell bandwidth to customers.

I only see the VPN market where this might happen (QoS in various places),
however queuing is not (hopefully) much deep in the network, and ISPs 
(usually)
rely on link over provisioning; so that classes never compete for bandwidth
(not in the back-haul nor in the transit).

>
> ipfw has some very cheap instructions to flexibly group flows into 
> classes,
> even large numbers of them.

I know, and that's great.
Maybe class is not anymore the right term in this case. It's an 
aggregate of flows,
do not know how to call it but not really a class.

Cheers
Luca




[-- Attachment #2: Type: text/html, Size: 4310 bytes --]

Re: [Bloat] Fw: video about QFQ+ and DRR

[Paolo Valente]

Il giorno 09/ago/2013, alle ore 15:06, MUSCARIELLO Luca OLNC/OLN ha scritto:

> Maybe class is not anymore the right term in this case. It's an aggregate of flows,
> do not know how to call it but not really a class.
> 
Maybe this is also the source of the misunderstanding: I referred to Linux classes, which are just generic containers of packets. Packets can be redirected into Linux classes by defining filters.
In other words, by defining a pair (desired filter, Linux class) one can redirect the desired packets into the class.

I used this mechanism to put each UDP flow, as well as the video stream, in a separate Linux class, and then perform per-flow scheduling among these flows.
I think that, in Linux, using these classes is the only way to perform per-flow queueing with differentiated weights.

Paolo

> Cheers
> Luca
> 
> 
> 


--
Paolo Valente                                                 
Algogroup
Dipartimento di Fisica, Informatica e Matematica		
Via Campi, 213/B
41125 Modena - Italy        				  
homepage:  http://algogroup.unimore.it/people/paolo/

Re: [Bloat] Fw: video about QFQ+ and DRR

[Dave Taht]

Dear Paolo:

I have been at a conference (cluecon) giving a talk on webrtc and
fq_codel: (https://plus.google.com/u/0/107942175615993706558/posts/hqitKPqAHkc
)

and am behind on this thread. Can you put sources up for your demo somewhere?


-- 
Dave Täht

Fixing bufferbloat with cerowrt: http://www.teklibre.com/cerowrt/subscribe.html

Re: [Bloat] video about QFQ+ and DRR

[Paolo Valente]

Il giorno 09/ago/2013, alle ore 18:08, Dave Taht ha scritto:

> Dear Paolo:
> 
> I have been at a conference (cluecon) giving a talk on webrtc and
> fq_codel: (https://plus.google.com/u/0/107942175615993706558/posts/hqitKPqAHkc
> )
> 
> and am behind on this thread. Can you put sources up for your demo somewhere?
> 
> 
Added to the homepage of QFQ+:
http://www.algogroup.unimore.it/people/paolo/agg-sched/

Paolo
> -- 
> Dave Täht
> 
> Fixing bufferbloat with cerowrt: http://www.teklibre.com/cerowrt/subscribe.html


--
Paolo Valente                                                 
Algogroup
Dipartimento di Fisica, Informatica e Matematica		
Via Campi, 213/B
41125 Modena - Italy        				  
homepage:  http://algogroup.unimore.it/people/paolo/