[Codel] The Inverse Square Root control law

[Codel] The Inverse Square Root control law

[Jonathan Morton]

[-- Attachment #1: Type: text/plain, Size: 1544 bytes --]

I said just now:

> Now about the inverse sqrt: qualitatively, it is just a convenient method of gradually varying the mark/drop rate in terms of a time interval rather than a packet count interval.  The longer the queue remains overfull - controlled by the number of mark/drop events that have occurred - the higher the marking/dropping rate gets.  If the queue then empties (and stays empty-ish for a few RTTs), the rate is reset.  Meanwhile, if the queue regularly oscillates between "full" and "empty" states, the marking/dropping rate is remembered so that aggressive TCPs receive the correct magnitude signal.
> 
> Now as for the *quantitative* reason behind it, it is because as the interval between drops gets shorter, the number of increments per RTT goes up because there is one increment per drop.  If the interval is shortened linearly per increment, that means it will in practice shorten exponentially faster, such that the drop rate runs away faster than the TCP can reasonably be expected to respond.  This would result in excessive drop rates and oscillatory behaviour typical of an over-sensitive control system.  By basing the drop rate on the square root of the incremented variable, the runaway behaviour is curtailed since the drop interval now shortens linearly per RTT.
> 
> Maybe a diagram or animation would help to clarify that last paragraph.  I'm fairly sure I can draw one.


Well, here's the diagram.  I produced it by simulating the first 200 or so drop events under each control law in a spreadsheet.

[-- Attachment #2: InverseSqrt.pdf --]
[-- Type: application/pdf, Size: 58612 bytes --]

[-- Attachment #3: Type: text/plain, Size: 328 bytes --]



The exponential behaviour of the "linear" control law is immediately apparent - it is clearly out of control within the first half-second, and triples the drop rate again within the following nominal RTT - as is the linear and much gentler behaviour of the "isqrt" control law actually implemented.

 - Jonathan Morton

[Codel] The Inverse Square Root control law

[Jonathan Morton]

I said just now:

> Now about the inverse sqrt: qualitatively, it is just a convenient method of gradually varying the mark/drop rate in terms of a time interval rather than a packet count interval.  The longer the queue remains overfull - controlled by the number of mark/drop events that have occurred - the higher the marking/dropping rate gets.  If the queue then empties (and stays empty-ish for a few RTTs), the rate is reset.  Meanwhile, if the queue regularly oscillates between "full" and "empty" states, the marking/dropping rate is remembered so that aggressive TCPs receive the correct magnitude signal.
> 
> Now as for the *quantitative* reason behind it, it is because as the interval between drops gets shorter, the number of increments per RTT goes up because there is one increment per drop.  If the interval is shortened linearly per increment, that means it will in practice shorten exponentially faster, such that the drop rate runs away faster than the TCP can reasonably be expected to respond.  This would result in excessive drop rates and oscillatory behaviour typical of an over-sensitive control system.  By basing the drop rate on the square root of the incremented variable, the runaway behaviour is curtailed since the drop interval now shortens linearly per RTT.
> 
> Maybe a diagram or animation would help to clarify that last paragraph.  I'm fairly sure I can draw one.

Well, here's the diagram.  I produced it by simulating the first 200 or so drop events under each control law in a spreadsheet.

http://dl.dropbox.com/u/60111136/InverseSqrt.pdf

The exponential behaviour of the "linear" control law is immediately apparent - it is clearly out of control within the first half-second, and triples the drop rate again within the following nominal RTT - as is the linear and much gentler behaviour of the "isqrt" control law actually implemented.

- Jonathan Morton