Re: [aqm] Codel's count variable and re-entering dropping state at small time intervals

["Agarwal, Anil" <[e-mail]>]

Hi Roland, Polina,

I had posted some suggestions on the bufferbloat forum, pointing out these issues (and a few more) and some suggestions to make the CoDel algorithm a bit stronger in these areas. It did not generate any feedback or discussion :(

https://lists.bufferbloat.net/pipermail/codel/2015-June/001023.html

I have attached the updated document.

Regards,
Anil

-----Original Message-----
From: aqm [mailto:[e-mail]] On Behalf Of Roland Bless
Sent: Monday, July 20, 2015 12:49 PM
To: [e-mail]
Subject: [aqm] Codel's count variable and re-entering dropping state at small time intervals

Dear All,

we (Polina and I) have two questions concerning the behavior of the `count` variable in Codel which can be summarized as:

1. after exiting dropping state, count is usually reset, unless "the next drop state is entered too close to the previous one". This special case is not explained in the text of the codel draft, but is present in all implementations, and, currently, there are at least three different versions of it (see below). We feel that implementers need more guidance here...

2. is 'count' supposed to be reset or saturated on overflow and what should be its maximum value (it makes a difference whether you are using 16-, 32-, or 64-bit counter)?

Regarding the first question:

Here are references to code that we looked to:
1) reference implementation in the draft:
https://urldefense.proofpoint.com/v2/url?u=https-3A__tools.ietf.org_html_draft-2Dietf-2Daqm-2Dcodel-2D01-23page-2D20&d=BQICAg&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=UBp2UfYrCphbTZ57lgJgIVIdsn7wHFOSnchRFuxYizo&s=mTvb-Ky9Q-6-QWZGaNbh-BFqG3eYeYwnb2Ce4HQgTwE&e=
2) ns-2 code:
https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_hbatmit_ns2.35_blob_master_queue_codel.cc-23L144&d=BQICAg&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=UBp2UfYrCphbTZ57lgJgIVIdsn7wHFOSnchRFuxYizo&s=p_7nQuMWbrfExiDTdfcnb6URkjaKpquZljRtBJzXS7E&e=
3) linux code:
https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_torvalds_linux_blob_110bc76729d448fdbcb5cdb63b83d9fd65ce5e26_include_net_codel.h&d=BQICAg&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=UBp2UfYrCphbTZ57lgJgIVIdsn7wHFOSnchRFuxYizo&s=9KiDPU9sBbzwqBltEg4S5BqSCoWyFWQ7rDYmbRs8whI&e=
4) cake code: https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_dtaht_sch-5Fcake_blob_master_codel5.h&d=BQICAg&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=UBp2UfYrCphbTZ57lgJgIVIdsn7wHFOSnchRFuxYizo&s=37wHZ75ipsCGBv0gWKnJMOrA2NGurvrgB82BmA1S7Gw&e= 

When codel encounters congestion it enters drop state, counts the number the of packets that were dropped since congestion was encountered, and drops packets in intervals of "interval" / sqrt (count). When there is no more congestion, the drop state is exited and this counter is reset unless "the next drop state is entered too close to the previous one".

This "too close to the previous one" is a part that is not well documented and differs in implementations:
1) In the ns-2 code it is in lines 187-200. The most important part is the comment that says that this control law is bad, but there is no better one available.
2) In the reference code these lines are the last lines on page 20. It has the same code (except // kmn decay tests line), but doesn't say that this solution is temporary.
3) In Linux code the lines in question are 334-348 and 352; first it uses 16 instead of 8, but this is consistent with comments, second it sets the count to something else that wasn't comprehensible (It doesn't look like the difference between previous count and count before that as the names would suggest, but rather a some improvement of count - 2, where 2 can be 3 or 1 or something ...)
4) For Cake the lines in question are 401-411, and in particular 404-405.

What is the "official" recommended version or is there any guidance on how to select one?

Regarding the second question:

In the reference implementation of the draft, count is 32-bit integer, but one cannot find any comments about the overflow behavior.
In Linux there is a comment to ignore overflow since there is no division, and due to the sqrt^-1 approximation it won't break at 0.
According to these two emails on the Cake archive:
https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.bufferbloat.net_pipermail_cake_2015-2DJune_000301.html&d=BQICAg&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=UBp2UfYrCphbTZ57lgJgIVIdsn7wHFOSnchRFuxYizo&s=ng4j5KlKbMFRTCqohAeT_JVpdk_dmurGUn-dOwVh8To&e= , https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.bufferbloat.net_pipermail_cake_2015-2DJune_000302.html&d=BQICAg&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=UBp2UfYrCphbTZ57lgJgIVIdsn7wHFOSnchRFuxYizo&s=vP5UapSOc8kBOg2pcCDrHLUnvtGvG25pp5NxZxkOf3k&e=  , it seems that the original intention of count was to be reset by overflow at 2^16, but according to experiments it is better to saturate it.

So, what is the desired overflow behavior for count: should it overflow or saturate, and if the latter applies, at which maximal value?

Best Regards,
 Roland and Polina (currently implementing stuff)

_______________________________________________
aqm mailing list
[e-mail]
https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_aqm&d=BQICAg&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=UBp2UfYrCphbTZ57lgJgIVIdsn7wHFOSnchRFuxYizo&s=zZz3_Y3bcShIVu57adw0GkG0wsaJsZBtGIV8z_YkyYQ&e=