FQ-CoDel queue disc

FQ-CoDel queue disc

[Pasquale Imputato, 2016-04-27 17:06:13]

Hi all,

we have created a review request about the introduction of FQ-CoDel queue disc
in ns-3. Our review request is in [1], the github repository is in [2].
Our code is based on the last FQ-CoDel IETF draft in [3] and on the Linux
implementation of FQ-CoDel.

We would be happy to get feedbacks/comments about our implementation.

Thanks,

[1] https://codereview.appspot.com/293290043/
[2] https://github.com/pasquimp/ns-3-dev-git/tree/fq-codel-new
[3] https://tools.ietf.org/html/draft-ietf-aqm-fq-codel-06

[Stefano Avallone, 2016-04-27 17:37:24]

Just to point out that this implementation requires:

- the fix proposed for bug #2384: when a packet is dropped by a CoDel queue, the
statistics (packet count) kept by FqCoDel must be updated, otherwise
FqCoDel::GetNPackets () does not return the correct number of packets stored by
FqCoDel

- the fix proposed for bug #2389 and code review 292540043: when the packet
limit is exceeded, FqCodel has to remove a packet from the head of the queue
having the largest backlog. Requesting the CoDel queue to dequeue a packet is
not correct (as pointed out by Matìas) because CoDel::Dequeue might also drop
some other packets. Thus, it is necessary to have a Queue::Remove method that
properly notifies the queue disc of packet drops.

[dave.taht, 2016-04-27 23:23:51]

I am happy to see this re-re-landing again. If there is a tree I can pull from
more directly, that would be great.

On 2016/04/27 17:37:24, Stefano Avallone wrote:
> Just to point out that this implementation requires:
> 
> - the fix proposed for bug #2384: when a packet is dropped by a CoDel queue,
the
> statistics (packet count) kept by FqCoDel must be updated, otherwise
> FqCoDel::GetNPackets () does not return the correct number of packets stored
by
> FqCoDel
> 
> - the fix proposed for bug #2389 and code review 292540043: when the packet
> limit is exceeded, FqCodel has to remove a packet from the head of the queue
> having the largest backlog. Requesting the CoDel queue to dequeue a packet is
> not correct (as pointed out by Matìas) because CoDel::Dequeue might also drop
> some other packets. Thus, it is necessary to have a Queue::Remove method that
> properly notifies the queue disc of packet drops.

[Stefano Avallone, 2016-04-28 07:57:54]

On 2016/04/27 23:23:51, dave.taht wrote:
> I am happy to see this re-re-landing again.

Yeah, I am confident this time it will land for real :-)

> If there is a tree I can pull from
> more directly, that would be great.

Sure, you can git clone from here:

https://github.com/pasquimp/ns-3-dev-git.git

or have a look at the commits via the web interface:

https://github.com/pasquimp/ns-3-dev-git/commits/fq-codel-new

Looking forward to feedbacks and comments.

[Stefano Avallone, 2016-04-28 08:03:24]

On 2016/04/28 07:57:54, Stefano Avallone wrote:
> Sure, you can git clone from here:
> 
> https://github.com/pasquimp/ns-3-dev-git.git

and then git checkout -b fq-codel-new --track origin/fq-codel-new

[dave.taht, 2016-06-26 06:29:32]

There was a "rrul" like test program in the original patch set, 4 up, 4 down, 4
measurement flows. Did it die?

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
File src/traffic-control/model/fq-codel-queue-disc.cc (right):

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
src/traffic-control/model/fq-codel-queue-disc.cc:54: void
I do not know why there is this "semantic pull" towards taking something based
on "deficit round robin" and switching it to credit round robin. I don't mind, I
just would like someone to explain.

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
src/traffic-control/model/fq-codel-queue-disc.cc:331: uint32_t
We just changed this function significantly in mainline linux to be far more
agressive about dropping the fat flow.

[Tom Henderson, 2016-07-17 22:13:56]

I'd like to see a bit more work on this before merging.

- finish class doxygen
- provide an example program with typical user configuration statements under
normal traffic loading
- more testing under heavier traffic loading (more flows)
- sphinx documentation (possibly stating what parts of the internet draft are
supported or unsupported)

I couldn't see how it is actually configured in practice, in user programs.  It
seems to me that there needs to be some addition of Ipv4 and/or Ipv6 packet
filters to the queue disc.  What is the user API (including any helpers) for
this?

Since the fq-codel internet draft states "This scheduling scheme has some
subtlety to it, which is explained in detail in the remainder of this
document.", I think it is important to test these subtle aspects somehow.  For
example, putting more flows through and testing somehow that the proper queues
are 'new' or 'old' at the right times.  Or testing that the hash algorithm is
working more or less as expected.

If there has been more extensive testing done elsewhere (e.g. documented in a
technical report) please provide the citation.

https://codereview.appspot.com/293290043/diff/1/src/internet/model/ipv4-packe...
File src/internet/model/ipv4-packet-filter.cc (right):

https://codereview.appspot.com/293290043/diff/1/src/internet/model/ipv4-packe...
src/internet/model/ipv4-packet-filter.cc:217: m_perturbation = uv->GetValue (0,
std::numeric_limits<uint32_t>::max ());
I'd like to see a means to allow the random variable have its stream number
assigned, which means that the rrandom variable should be accessible through a
pointer to the object somehow, such as in the internet stack helper.

Seeing that this random variable is only used once, it seems to me that it may
be easier to pass in the value for perturbation from outside, and keep the
random variable outside of this class.

https://codereview.appspot.com/293290043/diff/1/src/internet/model/ipv4-packe...
src/internet/model/ipv4-packet-filter.cc:274: uint32_t hash = Hash32 ((char*)
buf, 17);
I don't think it should matter too much, but is there a need to provide a means
to change the hash function?  By the way, I implemented jenkins hash during the
GSOC project that worked on this (can send to you out of band).

https://codereview.appspot.com/293290043/diff/1/src/internet/test/fq-codel-qu...
File src/internet/test/fq-codel-queue-disc-test-suite.cc (right):

https://codereview.appspot.com/293290043/diff/1/src/internet/test/fq-codel-qu...
src/internet/test/fq-codel-queue-disc-test-suite.cc:62: // Packets with non-IP
headers should enqueue into the same class
this is not a non-IP header, it is an Ipv6 header on an Ipv4 filter.

https://codereview.appspot.com/293290043/diff/1/src/internet/test/fq-codel-qu...
src/internet/test/fq-codel-queue-disc-test-suite.cc:65:
queueDisc->AddPacketFilter (filter);
has adding both an Ipv4 and Ipv6 packet filter to the same queue disc been
tested?

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
File src/traffic-control/model/fq-codel-queue-disc.h (right):

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
src/traffic-control/model/fq-codel-queue-disc.h:32: class FQCoDelFlow : public
QueueDiscClass {
Please rename class to 'FqCodelFlow' per naming guidelines:
https://www.nsnam.org/developers/contributing-code/coding-style/#Naming

This is missing class doxygen.

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
src/traffic-control/model/fq-codel-queue-disc.h:47: * \brief Set the credits for
this flow
It is not clear to me that setting a negative value should be allowed; should it
be a uint32_t, or should setting negative be disallowed?

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
src/traffic-control/model/fq-codel-queue-disc.h:52: * \brief Get the credits for
this flow
What does negative return value mean?

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
src/traffic-control/model/fq-codel-queue-disc.h:65: void SubCredits (int32_t
credits);
Again, if you are providing two methods, one for addition, one for subtraction,
should parameter be signed integer?

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
src/traffic-control/model/fq-codel-queue-disc.h:70: void SetActive (bool
active);
what does Active flag do?  elaborate

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
src/traffic-control/model/fq-codel-queue-disc.h:82: class FQCoDelQueueDisc :
public QueueDisc {
same comment about naming to 'FqCodelQueueDisc' and to provide class doxygen.

[Stefano Avallone, 2016-07-19 15:02:35]

Here it is an updated version that addresses your comments. Please browse the
previous version to see my replies to your comments.

Some other notes:

- the sphinx documentation has been added. An example usage is shown where the
traffic control helper is used to install the fq-codel queue disc and add two
packet filters to it.

- the test has been enhanced to test the DRR scheduler (and its subtleties),
thanks to the ability to get the status of a flow queue (i.e., new, old,
inactive). See, in particular, the third test of the suite.

- an RRUL-like example is proposed in https://codereview.appspot.com/298220043/.
The idea is that this example serves as a means to stress test all the queue
discs (with BQL enabled or not)

Thanks a lot for your comments.

https://codereview.appspot.com/293290043/diff/1/src/internet/model/ipv4-packe...
File src/internet/model/ipv4-packet-filter.cc (right):

https://codereview.appspot.com/293290043/diff/1/src/internet/model/ipv4-packe...
src/internet/model/ipv4-packet-filter.cc:217: m_perturbation = uv->GetValue (0,
std::numeric_limits<uint32_t>::max ());
On 2016/07/17 22:13:55, Tom Henderson wrote:
> I'd like to see a means to allow the random variable have its stream number
> assigned, which means that the rrandom variable should be accessible through a
> pointer to the object somehow, such as in the internet stack helper.
> 
> Seeing that this random variable is only used once, it seems to me that it may
> be easier to pass in the value for perturbation from outside, and keep the
> random variable outside of this class.

We go for the latter. We introduce a Perturbation attribute that can be set by
the user and remove the random variable from this class.

https://codereview.appspot.com/293290043/diff/1/src/internet/model/ipv4-packe...
src/internet/model/ipv4-packet-filter.cc:274: uint32_t hash = Hash32 ((char*)
buf, 17);
On 2016/07/17 22:13:55, Tom Henderson wrote:
> I don't think it should matter too much, but is there a need to provide a
means to change the hash function?

I think there is no such need.

> By the way, I implemented jenkins hash during the
> GSOC project that worked on this (can send to you out of band).

If you think the implementation of the jenkins hash is ready, you might push it
to ns-3-dev and then we make use of it.

https://codereview.appspot.com/293290043/diff/1/src/internet/test/fq-codel-qu...
File src/internet/test/fq-codel-queue-disc-test-suite.cc (right):

https://codereview.appspot.com/293290043/diff/1/src/internet/test/fq-codel-qu...
src/internet/test/fq-codel-queue-disc-test-suite.cc:62: // Packets with non-IP
headers should enqueue into the same class
It should be now clear that the purpose here is to test that packets that cannot
be classified by the available filters are dropped. We noticed that this is what
Linux does and changed the test and the Enqueue method accordingly.

https://codereview.appspot.com/293290043/diff/1/src/internet/test/fq-codel-qu...
src/internet/test/fq-codel-queue-disc-test-suite.cc:65:
queueDisc->AddPacketFilter (filter);
On 2016/07/17 22:13:56, Tom Henderson wrote:
> has adding both an Ipv4 and Ipv6 packet filter to the same queue disc been
> tested?

Done.

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
File src/traffic-control/model/fq-codel-queue-disc.cc (right):

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
src/traffic-control/model/fq-codel-queue-disc.cc:54: void
We used credits because the IETF draft uses such a term. However, we now
switched to using deficit in our code.

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
src/traffic-control/model/fq-codel-queue-disc.cc:120: .AddAttribute ("Quantum",
We removed the Quantum attribute and now provide a setter/getter pair of
methods. The reason is that Linux sets the quantum to the MTU size of the device
by default, but here we cannot access such information. Instead, the quantum is
set to 0 by the constructor. Then, at initialization time, if the user has not
set a positive value for the quantum, then the quantum is set to the MTU size of
the device.

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
src/traffic-control/model/fq-codel-queue-disc.cc:154: NS_LOG_ERROR ("No filter
has been able to classify this packet. Likely, "
If the packet filters are unable to classify a packet, that packet is dropped.
This is what the Linux implementation does.

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
src/traffic-control/model/fq-codel-queue-disc.cc:331: uint32_t
Thanks for letting us know. We modified this function to make it look like the
fq_codel_drop function of the upcoming kernel 4.7.

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
File src/traffic-control/model/fq-codel-queue-disc.h (right):

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
src/traffic-control/model/fq-codel-queue-disc.h:32: class FQCoDelFlow : public
QueueDiscClass {
On 2016/07/17 22:13:56, Tom Henderson wrote:
> Please rename class to 'FqCodelFlow' per naming guidelines:
> https://www.nsnam.org/developers/contributing-code/coding-style/#Naming
> 
> This is missing class doxygen.

Done.

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
src/traffic-control/model/fq-codel-queue-disc.h:47: * \brief Set the credits for
this flow
We make this param uint32_t, so that setting a negative deficit is disallowed.

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
src/traffic-control/model/fq-codel-queue-disc.h:52: * \brief Get the credits for
this flow
A negative value is returned when the amount of bytes dequeued from a queue
exceeds the quantum it is assigned.

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
src/traffic-control/model/fq-codel-queue-disc.h:65: void SubCredits (int32_t
credits);
We now provide a single method with a signed integer parameter.

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
src/traffic-control/model/fq-codel-queue-disc.h:70: void SetActive (bool
active);
We introduced an enum with three states: the flow is in the list of new queues,
the flow is in the list of old queues, the flow is inactive. This allows us to
better test the fq-codel scheduler, as we gain access to the status of each flow
queue.

https://codereview.appspot.com/293290043/diff/1/src/traffic-control/model/fq-...
src/traffic-control/model/fq-codel-queue-disc.h:82: class FQCoDelQueueDisc :
public QueueDisc {
On 2016/07/17 22:13:56, Tom Henderson wrote:
> same comment about naming to 'FqCodelQueueDisc' and to provide class doxygen.

Done.

[Tom Henderson, 2016-08-01 05:46:27]

On 2016/07/19 15:02:35, Stefano Avallone wrote:
> Here it is an updated version that addresses your comments. Please browse the
> previous version to see my replies to your comments.
> 

I am fine with the comment resolution; no further comments at this time.

[dave.taht, 2016-08-10 09:54:04]

On 2016/08/01 05:46:27, Tom Henderson wrote:
> On 2016/07/19 15:02:35, Stefano Avallone wrote:
> > Here it is an updated version that addresses your comments. Please browse
the
> > previous version to see my replies to your comments.
> > 
> 
> I am fine with the comment resolution; no further comments at this time.

I have not had time to review this myself, but if tom is fine with it, please
get it in there!!!

[Stefano Avallone, 2016-08-10 11:23:09]

Hi Dave,

I pushed not only FQ-CoDel, but also PIE and BQL to ns-3-dev.

Bests,
Stefano


On August 10, 2016 11:54:04 AM GMT+02:00, dave.taht@gmail.com wrote:
>On 2016/08/01 05:46:27, Tom Henderson wrote:
>> On 2016/07/19 15:02:35, Stefano Avallone wrote:
>> > Here it is an updated version that addresses your comments. Please
>browse the
>> > previous version to see my replies to your comments.
>> >
>
>> I am fine with the comment resolution; no further comments at this
>time.
>
>I have not had time to review this myself, but if tom is fine with it,
>please get it in there!!!
>
>https://codereview.appspot.com/293290043/

-- 
Sent from my Android device with K-9 Mail. Please excuse my brevity.

[dave.taht, 2016-08-10 11:31:55]

I am pretty sure that kissing you on both cheeks is appropo at this point.

THANK YOU VERY VERY VERY VERY VERY VERY MUCH!

I will pull the whole enchalada over the weekend. (notationally I'm on
vacation, and tomorrow is my bday, so again, thx)

In other news, the wifi patches are landing for openwrt....


On Wed, Aug 10, 2016 at 1:22 PM, Stefano Avallone <stavallo@gmail.com> wrote:
> Hi Dave,
>
> I pushed not only FQ-CoDel, but also PIE and BQL to ns-3-dev.
>
> Bests,
> Stefano
>
>
>
> On August 10, 2016 11:54:04 AM GMT+02:00, dave.taht@gmail.com wrote:
>>
>> On 2016/08/01 05:46:27, Tom Henderson wrote:
>>>
>>>  On 2016/07/19 15:02:35, Stefano Avallone wrote:
>>>>
>>>>  Here it is an updated version that addresses your comments. Please
>>
>> browse the
>>>>
>>>>  previous version to see my replies to your comments.
>>>
>>>
>>
>>>  I am fine with the comment resolution; no further comments at this
>>
>> time.
>>
>> I have not had time to review this myself, but if tom is fine with it,
>> please get it in there!!!
>>
>> https://codereview.appspot.com/293290043/
>
>
> --
> Sent from my Android device with K-9 Mail. Please excuse my brevity.



-- 
Dave Täht
Let's go make home routers and wifi faster! With better software!
http://blog.cerowrt.org

[tomh_tomh.org, 2016-08-10 15:21:18]

On 08/10/2016 04:31 AM, Dave Taht wrote:
> I am pretty sure that kissing you on both cheeks is appropo at this point.
>
> THANK YOU VERY VERY VERY VERY VERY VERY MUCH!

Hi Dave,
Stefano has indeed done a great job leading the effort to mainline 
traffic control and AQM models this year.  Let's also thank Pasquale 
Imputato (FQ-CoDel, BQL) and Mohit Tahiliani and his students (PIE) for 
their work on the individual models.   You can read more about these 
implementations at:

traffic control:  http://dl.acm.org/citation.cfm?id=2915382

PIE:  http://dl.acm.org/citation.cfm?id=2915385

- Tom

[dave.taht, 2016-08-10 15:24:48]

Kisses on all cheeks all around (where culturally accepted) !

(Didn't mean to leave anyone out sorry!)

On Aug 10, 2016 5:21 PM, "Tom Henderson" <tomh@tomh.org> wrote:

> On 08/10/2016 04:31 AM, Dave Taht wrote:
>
>> I am pretty sure that kissing you on both cheeks is appropo at this point.
>>
>> THANK YOU VERY VERY VERY VERY VERY VERY MUCH!
>>
>
> Hi Dave,
> Stefano has indeed done a great job leading the effort to mainline traffic
> control and AQM models this year.  Let's also thank Pasquale Imputato
> (FQ-CoDel, BQL) and Mohit Tahiliani and his students (PIE) for their work
> on the individual models.   You can read more about these implementations
> at:
>
> traffic control:  http://dl.acm.org/citation.cfm?id=2915382
>
> PIE:  http://dl.acm.org/citation.cfm?id=2915385
>
> - Tom
>

[Stefano Avallone, 2016-08-10 15:45:27]

My fault that I did not thank Pasquale and Mohit. Of course, alone I couldn't
have done all of this!

Another news that might be of interest to Dave is that ns-3 now supports packet
priorities and setting the user priority (and selecting the access category) for
wifi based on the DSCP like Linux currently does (I.e., taking the 3 most
significant bits). So, 802.11 EDCA can be fully stressed! I am aware there is an
IETF draft proposing a different DSCP to UP mapping: I will implement it as soon
as it gets finalized.

Happy birthday 🙂

Stefano


On August 10, 2016 5:24:47 PM GMT+02:00, Dave Taht <dave.taht@gmail.com> wrote:
>Kisses on all cheeks all around (where culturally accepted) !
>
>(Didn't mean to leave anyone out sorry!)
>
>On Aug 10, 2016 5:21 PM, "Tom Henderson" <tomh@tomh.org> wrote:
>
>> On 08/10/2016 04:31 AM, Dave Taht wrote:
>>
>>> I am pretty sure that kissing you on both cheeks is appropo at this
>point.
>>>
>>> THANK YOU VERY VERY VERY VERY VERY VERY MUCH!
>>>
>>
>> Hi Dave,
>> Stefano has indeed done a great job leading the effort to mainline
>traffic
>> control and AQM models this year.  Let's also thank Pasquale Imputato
>> (FQ-CoDel, BQL) and Mohit Tahiliani and his students (PIE) for their
>work
>> on the individual models.   You can read more about these
>implementations
>> at:
>>
>> traffic control:  http://dl.acm.org/citation.cfm?id=2915382
>>
>> PIE:  http://dl.acm.org/citation.cfm?id=2915385
>>
>> - Tom
>>

-- 
Sent from my Android device with K-9 Mail. Please excuse my brevity.