Re: [aqm] [tsvwg] Immediate ECN: Autotuning AQM for RTT

["Fred Baker (fred)" <[e-mail]>]

On Nov 13, 2013, at 10:48 AM, Fred Baker (fred) <[e-mail]> wrote:

> With CoDel, the key issue is the sqrt. As the algorithm is described, it happens in the data path - upon interval expiration, a packet is dropped, and a new interval is calculated in inverse proportion to the square root of the number of drops since the dropping state was entered. I'll argue that the actual value could be calculated in the background and placed into a register to be copied to the interval register the next time a packet is actually dropped. The square root calculation itself can be pretty simple. Most chips these days have an instruction to tell you the bit number of the most significant "one" in a register, and have barrel shifters. OK, pick up the number, determine its most significant bit number, shift that right one bit (divide by two), shift the argument of the sqrt right the resulting number of bits, and then do one or two Newton-Raphston iterations. So a reasonable approximation to the sqrt can be implemented using RISC approaches.

The sort could also be implemented as a table, given some assumptions. use the number of drops since the epoch as an index and read the sqrt (or actually, the calculation that results from it). At some point, we reach the minimum interval that is acceptable - we are perhaps dropping every packet, or dropping some limit percentage. At that point, there isn't a real value in tracking the actual value, as the interval ceases decreasing.