[RFC,net-next,0/2] net: sched: add Flow Queue PIE AQM

Flow Queue PIE packet scheduler

This patch series implements the Flow Queue Proportional
Integral Controller (FQ-PIE) active queue management
algorithm. It is an enhancement over the PIE algorithm.
It integrates the PIE aqm with a deficit round robin
scheme.

It is implemented over RFC 8033 aligned version of PIE.
In this patch, Little's law is used for queue delay
estimation like PIE. This patch doesn't yet have the
timestamp based queue delay estimator like freebsd, that
Dave Taht thinks is better.

We are looking for suggestions on cleanups and
improvements for this patch.

For more information: 
https://tools.ietf.org/html/rfc8033

Mohit P. Tahiliani (2):
  net: sched: pie: refactor PIE
  net: sched: fq_pie: Flow Queue PIE AQM

 include/net/pie.h              | 330 ++++++++++++++++++++++
 include/uapi/linux/pkt_sched.h |  28 ++
 net/sched/Kconfig              |  14 +-
 net/sched/Makefile             |   1 +
 net/sched/sch_fq_pie.c         | 485 +++++++++++++++++++++++++++++++++
 net/sched/sch_pie.c            | 314 +--------------------
 6 files changed, 863 insertions(+), 309 deletions(-)
 create mode 100644 include/net/pie.h
 create mode 100644 net/sched/sch_fq_pie.c

Gautam Ramakrishnan <gautamramk@gmail.com> writes:

> Flow Queue PIE packet scheduler
>
> This patch series implements the Flow Queue Proportional
> Integral Controller (FQ-PIE) active queue management
> algorithm. It is an enhancement over the PIE algorithm.
> It integrates the PIE aqm with a deficit round robin
> scheme.
>
> It is implemented over RFC 8033 aligned version of PIE.
> In this patch, Little's law is used for queue delay
> estimation like PIE. This patch doesn't yet have the
> timestamp based queue delay estimator like freebsd, that
> Dave Taht thinks is better.
>
> We are looking for suggestions on cleanups and
> improvements for this patch.

Is the fq_ part basically identical to fq_codel? Might make sense to
share some code in that case; might not be a trivial refactoring,
though...

-Toke

On Mon, Apr 01, 2019 at 02:04:19PM +0200, Toke Høiland-Jørgensen wrote:
> Gautam Ramakrishnan <gautamramk@gmail.com> writes:
>
> > Flow Queue PIE packet scheduler
> >
> > This patch series implements the Flow Queue Proportional
> > Integral Controller (FQ-PIE) active queue management
> > algorithm. It is an enhancement over the PIE algorithm.
> > It integrates the PIE aqm with a deficit round robin
> > scheme.
> >
> > It is implemented over RFC 8033 aligned version of PIE.
> > In this patch, Little's law is used for queue delay
> > estimation like PIE. This patch doesn't yet have the
> > timestamp based queue delay estimator like freebsd, that
> > Dave Taht thinks is better.
> >
> > We are looking for suggestions on cleanups and
> > improvements for this patch.
>
> Is the fq_ part basically identical to fq_codel? Might make sense to
> share some code in that case; might not be a trivial refactoring,
> though...
>
> -Toke

The fq_ part is mostly the same, except for the batch dropping. But the
structure of flows are different. Any particular suggestions on the
refactoring?


-Gautam

Gautam Ramakrishnan <gautamramk@gmail.com> writes:

> On Mon, Apr 01, 2019 at 02:04:19PM +0200, Toke Høiland-Jørgensen wrote:
>> Gautam Ramakrishnan <gautamramk@gmail.com> writes:
>>
>> > Flow Queue PIE packet scheduler
>> >
>> > This patch series implements the Flow Queue Proportional
>> > Integral Controller (FQ-PIE) active queue management
>> > algorithm. It is an enhancement over the PIE algorithm.
>> > It integrates the PIE aqm with a deficit round robin
>> > scheme.
>> >
>> > It is implemented over RFC 8033 aligned version of PIE.
>> > In this patch, Little's law is used for queue delay
>> > estimation like PIE. This patch doesn't yet have the
>> > timestamp based queue delay estimator like freebsd, that
>> > Dave Taht thinks is better.
>> >
>> > We are looking for suggestions on cleanups and
>> > improvements for this patch.
>>
>> Is the fq_ part basically identical to fq_codel? Might make sense to
>> share some code in that case; might not be a trivial refactoring,
>> though...
>>
>> -Toke
>
> The fq_ part is mostly the same, except for the batch dropping. But
> the structure of flows are different. Any particular suggestions on
> the refactoring?

Well, fq_pie_enqueue() is quite close to fq_codel_enqueue(); same thing
for *_dequeue(). So it should be possible to divide them up into a
common part, followed by the bits that differ. Then the common parts can
be factored out into a common function to be included by both.

You don't have to do the actual factoring out of the common bits in this
patch series, but it would be good if you could structure the fq_pie
code so it is as close to the fq_codel code as possible, to make it
easier to split out common parts later. This includes the enqueue and
dequeue functions, as well as the data structures. Doing this also has
the added bonus that you'll have to think about (and preferably explain
the reasoning behind) any deviations between the two variants.

I'll send a couple of concrete suggestions in a separate email.

-Toke