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

From: Roland Bless <[email-masked]>
Date: Mon, 20 Jul 2015 18:49:25 +0200

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://tools.ietf.org/html/draft-ietf-aqm-codel-01#page-20
2) ns-2 code:
https://github.com/hbatmit/ns2.35/blob/master/queue/codel.cc#L144
3) linux code:
https://github.com/torvalds/linux/blob/110bc76729d448fdbcb5cdb63b83d9fd65ce5e26/include/net/codel.h
4) cake code: https://github.com/dtaht/sch_cake/blob/master/codel5.h

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://lists.bufferbloat.net/pipermail/cake/2015-June/000301.html,
https://lists.bufferbloat.net/pipermail/cake/2015-June/000302.html , 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)

---

From: "Agarwal, Anil" <[email-masked]>
Date: Mon, 20 Jul 2015 17:09:10 +0000

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:[email-masked]] On Behalf Of Roland Bless
Sent: Monday, July 20, 2015 12:49 PM
To: [email-masked]
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)?

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?

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,

_______________________________________________
aqm mailing list
[email-masked]
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=

---

From: Jonathan Morton <[email-masked]>
Date: Mon, 20 Jul 2015 22:34:59 +0300

I can’t speak for Kathy, but as Cake’s author I have some insight into the changes I’ve made to the associated version of Codel.

> Ronald Bless:

> next drop state is entered too close to the previous one”.

In fact, in most cases (ie. where the true RTT is near to or less than the one assumed by the interval parameter, and the flow is persistent) the drop state will be re-entered sufficiently soon to prevent the reset.  The backoff behaviour for that case is thus more significant in practice.

The standard backoff behaviour is to reduce count by just 2.  This is obviously wrong in the case where count has already reached a significant value; with a high drop frequency, count will climb a lot during a single RTT.  But if the elevated drop frequency is necessary and sufficient to control the flow, we don’t want it to grow indefinitely.

Cake’s version halves the count, reducing the drop frequency by a factor of sqrt(2) after a pause.  This multiplicative backoff prevents count from growing indefinitely, and allows it to reduce gradually to a lower value if that becomes appropriate due to reduced network load.

Anil's suggestion of continuously reducing count during the non-dropping state is an interesting alternative which might also make sense.  It has the pleasing property of relating the backoff rate to the length of time spent outside the dropping state.

> 16-, 32-, or 64-bit counter)?

It’s clear to me that a saturating increment is necessary to deal with unresponsive flows adequately.  Otherwise, the drop frequency will wrap around to a low value periodically when it needs to be consistently high.

My test case for this involves 50 upstream TCP flows on a narrow link (say 10Mbit) and a single downstream TCP flow on a wide link (say 100Mbit).  In this configuration, the acks for the downstream flow constitute an unresponsive (in fact, anti-responsive) upstream flow of greater throughput demand than the individual upstream TCP flows.  Anti-responsive means that dropping packets actually increases the network load, because reducing the ack density permits higher throughput on the downlink, which in turn generates additional acks on the uplink.

Since Cake uses very robust flow isolation, simply delivering all the acks in order, using a fair-share of the bandwidth, would severely limit the throughput of the downstream flow.  However, the standard Codel behaviour resulted in wildly oscillating throughput on the downstream flow.  Straightforward calculations suggested that the count variable was probably wrapping.

At first, I only put in the modified backoff behaviour mentioned above.  Since the downstream flow was often reaching full throughput, I thought that occasionally the drop rate was managing to empty the ack queue, making the backoff behaviour significant. This assumption turned out to be correct, but the backoff modification was insufficient to completely correct the behaviour.  Only when I changed count to use a saturating increment instead of a wrapping one did the downstream flow achieve full throughput consistently.

It’s possible that if count was a wider variable (32 instead of 16 bits) that the backoff modification would have been sufficient to prevent wrapping in this case.  However, using saturating arithmetic is inexpensive on modern CPUs (many have dedicated instructions which could be used by highly optimised implementations) and is the most robust solution.

Note that in the absence of robust flow isolation, eg. with plain Codel or PIE, the upstream TCP flows will back off to make room for all the acks.  This does not require a particularly high drop rate, but it reduces the upstream goodput significantly.  Cake instead achieves high goodput in both directions in this especially challenging case.

> Anil Agarwal:

There are indeed a lot of suggestions here, which I haven’t yet fully assimilated.  I’ll cherry-pick a few that stood out:

> When RTT is small compared to the default Interval, CoDel is slow in reacting and controlling queue size/delay during TCP slow start.

> For example, if Interval = 100 ms and RTT = 20 ms, CoDel will not drop or mark a packet for the first 100 ms of a new TCP connection; if link rate = 10 Mbps, initial window size = 14600 bytes, then during this period, the TCP cwnd will grow to 104 kbytes; queuing delay will be 63 ms.

Cake’s modified Codel does vary its sensitivity according to how quickly the queue is filling.  With the default parameters, it may trigger as quickly as 35ms after a large burst arrives, or as slowly as 200ms if the queue is growing very slowly.

It could be improved further in theory, by giving Codel visibility of the length and drain rate of the queue (and thus the ability to predict future delay) rather than only observing the exit delay.  However, in the general case the drain rate is variable, so this may be difficult to make robust.

Ultimately, triggering instantly when the queue begins to fill is optimal to deal with slow-start, which will double its cwnd further while the congestion signal is in transit, before responding with a halving.  However, an instant trigger is suboptimal for the congestion-avoidance phase of TCP, which is why Codel always delays its response.  Flow isolation is a good (if imperfect) countermeasure for the suboptimal slow-start behaviour this causes.

My “Explicit Load Regulation” proposal, which hasn’t yet been widely circulated, aims to get closer to optimal behaviour in both situations.  It is an extension to ECN behaviour, giving the option of more moderate signals than ECN permits, while being easier to deploy incrementally than DCTCP is.  Hopefully I’ll be able to write it up properly later.

> The draft rfc states - “For example, there is about an 86% probability that no more than two of the 100 VoIP sessions will be involved in any given collision”
> Based on analytical equations for hash collision probabilities (I derived them independently some time ago), the probability of no collision = 90.78%…

Cake’s set-associative hash function reduces the probability of flow collisions further, to negligible values for the above number of flows.

> Alternatively, codel_dequeue() can be re-structured as two routines…

Certainly a refactoring would be beneficial for readability.  I haven’t got around to doing it yet.

 - Jonathan Morton