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

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

On Nov 12, 2013, at 5:18 AM, "Scheffenegger, Richard" <[e-mail]> wrote:

> So, as I am not a HW guy, how many gates does one need for (W)RED, PIE, CoDel?

I'm not a hardware guy either, but I think a predictor would be the registers and calculations implied in the data path (a supporting software/firmware process can use RISC approaches to implement non-data-path components). The calculations of importance are multiplies, divides, and square roots, each of which can take an interesting amount of silicon if literally implemented in hardware. 

For the hardware engineer, there are a number of analogs that can be used to simplify life. For example, where an algorithm calls for some number of milliseconds, s/he can divide down the clock rate of the chip and consider that to be a stated number of clock ticks rather than implementing a millisecond clock. Where an algorithm calls for a random number, there are ways the engineer can use noise to create it (http://en.wikipedia.org/wiki/Hardware_random_number_generator).

With RED, there are two basic calculations: maintaining the mean queue depth, which might mean an exponentially-weighted moving average with samples taken on events or at times, and determining the mark/drop probability as max(0, (mean_queue_depth-min_threshold)/(max_threshold-min_threshold)). An EWMA can be implemented using adds and shifts, so it's not a big deal. I'm not the guy that has done our chips, so I'm speaking out of turn, but I would expect that the divide in the mark/drop probability can be simplified to not require an actual division circuit. We need a random number; that comes down to a register.

With PIE, the data path calculation is "once per interval, pick up a random number, compare it to a threshold, and possibly mark/drop a packet". That comes down to a register for the random number generator. The math in the background process is "interesting", but - it's in the background process. Use RISC approaches.

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.

My take is that one can use silicon real estate if there is another reason to have the circuits, but the algorithms on the table can be implemented in microcode given the ability to run a supporting background process on a RISC computer.



Appendix on EWMAs using adds and shifts:

An EWMA calculates
    new_mean = W*sample + (1-W)*old_mean, 0 <= W <= 1
in successive steps, calculating the mean of a set of samples.

Let's constrain W to 2^(-N) for some value of N.

Now, store the mean shifted left N bits.

The calculation becomes 
    mean := sample + mean - (mean shifted right N bits).

Any time you need to use the mean, either you shift it right N bits, or you shift the rest of the calculation left N bits.