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

[Dave Taht]

---------- Forwarded message ----------
From: Roland Bless <roland.bless at kit.edu>
Date: Mon, Jul 20, 2015 at 6:49 PM
Subject: [aqm] Codel's count variable and re-entering dropping state
at small time intervals
To: aqm at ietf.org


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)

_______________________________________________
aqm mailing list
aqm at ietf.org
https://www.ietf.org/mailman/listinfo/aqm


-- 
Dave Täht
worldwide bufferbloat report:
http://www.dslreports.com/speedtest/results/bufferbloat
And:
What will it take to vastly improve wifi for everyone?
https://plus.google.com/u/0/explore/makewififast