Subject: Immediate ECN: Autotuning AQM for RTT

From: Bob Briscoe <[email-masked]>
Date: Thu, 7 Nov 2013 20:03:08 +0000

Folks,

"Immediate ECN" slides:
<http://bobbriscoe.net/presents/1311ietf/1311tsvarea-iecn.pptx>
<http://bobbriscoe.net/presents/1311ietf/1311tsvarea-iecn.pdf>

PS. This talk fell off the end of the TSVAREA agenda. It's mostly 
relevant to AQM, but I didn't originally bring it to AQM, because it 
affects 3 wgs: tsvwg, aqm & tcpm.

In the AQM wg, there was dismay about CableLabs not including 
anything about ECN in DOCSIS3.1. This talk is about AQM dynamics; and 
how ECN can take out the 100ms of delay that CoDel and PIE introduce 
- it's essentially about auto-tuning for RTT.

It gives an interim recommendation for hardware designers that there 
should be a second instance of the AQM algo for ECN packets so that 
it can be configured with different parameters (think of WRED instead of RED).

Specifically, for ECN packets:
interval = 0 (for CoDel)
max_burst = 0 (for PIE)

Bob

PS. We have a paper under submission, which we can supply on request.
We plan to document this in the IETF too.

________________________________________________________________
Bob Briscoe,                                                  BT

---

From: Bob Briscoe <[email-masked]>
Date: Mon, 11 Nov 2013 16:17:59 +0000

Rong,

At 07:26 09/11/2013, Rong Pan (ropan) wrote:
>I just got a better understanding of Bob's proposal. Great direction
>indeed! I fully agreed that doing the smoothing at the end hosts and
>simple network congestion signals is the best way to achieve low averaging
>latency.
>
>We do need these three working groups working together to get this done.
>But since folks usually attend all these three meetings at IETF, I am
>hopeful that IETF can make it happen with all our efforts together here.

It seems the IETF is willing to move quickly on this. We brought this 
work to the IETF earlier than I would normally have liked, given the 
urgency. We will try continue to move quickly, but it would be great 
if different groups could work in parallel. For instance, if your 
group and/or others could focus on testing this out with PIE.

more...

>Bob,
>
>a technical question. If we do no averaging for ECN, and hosts use the
>tradition ECN-capable TCP, I am afraid its window might get cut too much
>to achieve any reasonable throughput. Any thought on how to handle that?
>Or maybe you already covered in your slides and I missed it?

Bear in mind that altho traditional ECN hosts (we call them classic 
ECN) cut their rate by half in response to one CE mark they only do 
this once per RTT, then they ignore all the other marks in the same 
RTT. DCTCP only cuts its rate a little per mark, but it does so for 
every mark.

So it's not obvious what the outcome will be, but I'm hopeful that 
classic ECN hosts will achieve sufficient througput when competing 
with DCTCP, for some definition of 'sufficient'. Testing incremental 
deployment cases like this is next on our list of experiments to do.

I intended to say this on slide 13 (there's a brief footnote to this 
effect), but I had to cut short, because I had to squeeze a 20min 
presentation into the last 15 mins of tsvwg.

Regards

Bob

>Thanks,
>
>Rong
>
>
>
>On 11/7/13 12:03 PM, "Bob Briscoe" <[email-masked]> wrote:
>
> >Folks,
> >
> >"Immediate ECN" slides:
> >_______________________________________________
> >aqm mailing list
> >[email-masked]
> >https://www.ietf.org/mailman/listinfo/aqm

---

From: Bob Briscoe <[email-masked]>
Date: Mon, 11 Nov 2013 16:02:36 +0000

Greg,

At 06:54 09/11/2013, Greg White wrote:
>This is very interesting work.  There are a lot of unanswered questions
>about ecn / no-ecn coexistence and differential treatment in an AQM, and
>this could provide some answers.
>
>To those who groaned that ECN was not included in DOCSIS 3.1, read these
>slides (and Naeem Khademi's).

Indeed. However, I think it would be safe to recommend that ECN 
support should at least be implemented and separately configurable, 
then it can be turned on or off by operators later.

I'm aware that this doubles the amount of configuration, but we've 
had some success already (with RED) in relating all the ECN 
parameters to the drop parameters by a formula, so hopefully the 
vendor could configure the ECN parameters automatically based on the 
drop parameters.

>Bob, CoDel uses "interval" both as a hold-off for the first packet drop
>and as the numerator in the invsqrt drop scheduling.  Setting interval = 0
>would result in ECN being signaled on *every* ECN capable packet when the
>sojourn time is above threshold.    This jibes with some of your charts
>for RED, but others show a ramp up in mark probability rather than a step
>function. Could you clarify?

We've only looked at WRED in detail, because it was much more 
interesting (to us) to reconfigure existing implementations than have 
to wait for new code to be implemented and tested.

The suggestions for PIE and CoDel are just conceptual at this stage - 
we've done no implementation of this idea with either. (I said this 
verbally when presenting the slides, but I should have put it in 
writing too). Please read my suggestions for PIE and CoDel in this light.

I'm not surprised that CoDel derives other parameters from 'interval' 
that should have been declared and set separately. Andrew McGregor 
also pointed out to me that CoDel sets threshold = 0.2*interval, so 
threshold would have to be declared separately as well. This starts 
to reveal just how many magic numbers there really are in the CoDel algorithm.

>Setting max_burst = 0 in PIE would not result in the step function
>behavior.

It's not meant to result in a step-function.

In the WRED example, it solely avoids the delay of queue averaging, 
so that once the /instantaneous/ queue exceeds min_thresh it marks 
with increasing probability (not intended to be a step).

Similarly with PIE, the formula:
         p = p + alpha*(est_del-target_del) + beta*(est_del-est_del_old);
would still gradually increase the probability of drop (not a step 
function), but it would start to do so as soon as the queue exceeded 
target_del, rather than waiting for max_burst.

Is that what you meant?

Bob

>-Greg
>
>
>On 11/7/13, 1:03 PM, "Bob Briscoe" <[email-masked]> wrote:
>
> >Folks,
> >
> >"Immediate ECN" slides:

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Tue, 12 Nov 2013 13:18:28 +0000

Hi Greg et.al.,

(chair hat off)

> I don't have a lot of confidence that I can recommend something to be
> burned into silicon at this point (and doing it in software is a non-
> starter).  The "turned on or off by operators later" would be a given, but
> if implemented based on what we know now, I don't have a lot of confidence
> that the switch would be ever set to the "turned on" state.  I can't
> recommend that vendors add gates for a feature that my intuition tells me
> would never be used.  If separately configurable means something that
> would increase the probability of the feature being used, then that's
> great, but what specifically are we talking about?  It could be a lot of
> gates.

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

Apparently, as state needs to be kept separately for ECN and non-ECN flows, additional memory plus some way of switching between which memory is used for what packet is necessary; however, the hardcoded algos should be the same (as far as some tuneables are stored in memory instead of hardwired gates).

> Also, you've suggested *not* differentiating between "classic ECN" and
> "immediate ECN" in the ECT flags, but this is just a suggestion at this
> point.  Again, not something I feel confident about taking for granted.
> We'll continue to track this discussion though.

As Bob pointed out in another email, classic ECN will react to any number of marks within one RTT (of that particular flow) with only a single halving of the congestion window. Most other transports that have been modeled after TCP/ECN will behave similarly. Immediate ECN will react to each mark to a smaller extent, and only a full window (RTT) of marks will reduce the window by half. Thus immediate ECN would be much more aggressive when used with traditional RED, ie. push the AQM to higher marking probabilities.

One venue that presents itself here, of course, is to use 2nd order effect - i.e. the exact marking pattern - to achive reasonable fairness between transports making use of immediate and classic reactions. However, I can not say offhand, if this would be a practical method (may require too much state in the scheduling/aqm, including fine grained flow separation).

> However, it seemed to me that what you were proposing was to move the
> intelligence to the transport, and keep the queue simple. In that regard,
> would a very simple threshold:  always mark when instantaneous queue
> exceeds the threshold, never mark when it doesn¹t, be an acceptable way to
> do things?
> 
> This would be easily implementable, and could be straightforwardly
> combined (I think) with any AQM that is controlling drops (including
> CoDel).

That is what DCTCP currently does. However, a simple step function is incompatible with classic ECN. 

While reading Bob's earlier comment on classic vs immediate ECN, I thought that probably an exponential increase in marking probability, above a specific threshold (lower than drop) could "autotune" to a reasonable marking rate, without necessarily locking classic out when immediate is used. If the linear/step function employed with RED (and shown on Bobs slides) is a good enough approximation needs to be verified. However, the details will probably also depend on the mixure of number of classic vs. immediate ECN flows at the bottleneck, and their respective RTTs...

Finally, as the gateways (switches) cannot rely on ECN to work (either on the required timescales, as the RTT is too large for small buffers, or the transport/sender is not reacting), even ECN traffic has to be exposed to drops - and ideally here not to the tail-drop variant.

Richard Scheffenegger

---

From: Bob Briscoe <[email-masked]>
Date: Tue, 12 Nov 2013 22:20:41 +0000

Greg, inline...

At 18:57 11/11/2013, Greg White wrote:

>On 11/11/13, 9:02 AM, "Bob Briscoe" <[email-masked]> wrote:
>
> >Greg,
> >
>burned into silicon at this point (and doing it in software is a
>non-starter).  The "turned on or off by operators later" would be a given,
>but if implemented based on what we know now, I don't have a lot of
>confidence that the switch would be ever set to the "turned on" state.  I
>can't recommend that vendors add gates for a feature that my intuition
>tells me would never be used.  If separately configurable means something
>that would increase the probability of the feature being used, then that's

Understood.

Given the cable industry has decided to move on 
this early schedule, we can now do the necessary 
research so that competing access technologies can properly exploit ECN ;)

more...

>In the ns2 CoDel code that we've used (from Kathie), there are two
>independent parameters, threshold and interval, and the defaults are 5ms
>for threshold and 100ms for interval, so I don¹t know where the "threshold
>= 0.2*interval" is coming from (maybe it is different in the current linux
>or openWRT distros).

Sorry, altho it turns out I was wrong anyway (see below), I meant to say:
         0.05 * interval
         (= interval / 20)
I was working from memory and I knew there was a 2 in there somewhere.

Andrew McGregor said at the mic in tsvwg last 
Friday that threshold was defined relative to 
interval, and I remembered it from when I first 
looked at the CoDel code. However, I've just 
checked and even Andrew's ns3 port of CoDel sets 
threshold to 5ms, independent of the setting of 
interval. So consider this a memory thow-back on everyone's part and ignore it.

>To be more clear about my earlier statement, CoDel actually uses
>"interval" to control a single aspect of the drop policy, however, the
>code (and descriptions of it) imply that there are two different
>functions, and my comments above were written in that vein. However,
>here's how I would describe it more succinctly:  the "next drop time" is
>always set according to interval/sqrt(count).  In the specific case of
>sojourn time crossing above threshold from below, count happens to equal
>1, so the first drop is set at one interval in the future.  This is what
>is sometimes described as the "hold off" period.

OK. From an admittedly hasty scan through Andrew 
McGregor's port of CoDel to ns3 (not the Linux 
code), it seems to introduce this hold-off time 
in the ControlLaw() function, but it only calls 
ControlLaw() from the ShouldDrop() function if 
the queue has remained above threshold for duration interval.

That implies that CoDel holds off signalling 
anything for 2 * interval, ie 200ms for the 
default setting of interval = 100ms.

>That said, there are some "magic numbers" in the algorithm, specifically
>the part that regulates very low drop probabilities (e.g. 8*interval,
>count *= 0.9844), but that¹s about it.

And the following magic numbers, of course:
* threshold [5ms]
* the power used in the control law [0.5 in the sqrt function]

>I¹m still thinking about how to achieve differential treatment of marking
>vs dropping in CoDel in a logical way.

That would only be possible if CoDel's control 
law for drop was based on some understandable 
logic in the first place. I've started another 
thread on that, based on analysis I've just done of CoDel's control law.

A naive answer would be to create a second 
variable for the interval used in ControlLaw(), 
let's call it I.  Then solely set interval = 0.

But that would still leave a signalling delay of 
I. As you say, CoDel's control law for increasing 
the dropping frequency is also based on the assumption that I = RTT = 100ms.

By my analysis (in the other email), the 
rationale for CoDel's current control law seems 
incorrect, which is probably why we're finding 
it's tough to base any new thinking on it.

>Yes, that is what I meant.
>

A simple step threshold would be fine if all 
traffic used ECN. DCTCP proves that such a really 
dumb AQM works well if complemented by a smarter 
TCP (which proved to me that our problem is with TCP).

But I don't think it's so easy to combine such a 
simple AQM for ECN traffic, with a complex AQM like CoDel for drop.

The logic I started from was:
* If starvation is going to happen, it will happen over time
* So we should be able to design two AQMs (for 
ECN and drop) that will not cause each other to 
starve, by only considering where they eventually 
converge to - solely in the presence of stable 
long-running flows. We can elide dynamics, like 
smoothing, that disappear over time.
* CoDel looks for the min queuing delay over 
interval, so we can elide that part of its 
behaviour. But the control law continues to 
increase drop with time, irrespective of how the 
queue is growing (as long as it is greater than 
threshold). Then, when drop is high enough, 
assuming responsive flows, the CoDel queue will 
fall below threshold and switch back to 
non-dropping mode. Then the cycle will repeat. 
It's not easy to elide away behaviour that 
stabilises by continually switching between two 
discrete modes, rather than stabilising in one mode.

This is what the short-term memory within CoDel 
does - if it returns to dropping mode soon enough 
after leaving it, it starts dropping from where 
it left off. So it's actually continually 
switching in and out of dropping mode, which 
makes it much harder to think about analytically. 
And much harder to design a complementary ECN behaviour for it.

________
I prefer the principle: "Design for 
Verifiability", which is why I always have an 
allergic reaction to CoDel. See John Doyle's 
paper below, which uses TCP and AQM design as a 
case study for how to use and abuse this principle:

Doyle, J.C., Carlson, J., Low, S.H., Paganini, 
F., Vinnicombe, G., Willinger, W., Hickey, J., 
Parrilo, P. & Vandenberghe, L., "Robustness and 
the Internet: Theoretical Foundations," Caltech Draft Paper (March 2002)
<http://netlab.caltech.edu/pub/papers/RIPartII.pdf>

The IRTF network complexity research group is 
trying to make this stuff understandable by us mere IETFers.

Bob

> >> >it can be configured with different parameters (think of WRED instead
> >>of
> >> >RED).
> >> >

---

From: Bob Briscoe <[email-masked]>
Date: Tue, 12 Nov 2013 23:03:20 +0000

Richard,

I've replied separately to Greg - apologies for splitting the thread. Inline...

At 13:18 12/11/2013, Scheffenegger, Richard wrote:
>Apparently, as state needs to be kept separately 
>for ECN and non-ECN flows, additional memory 
>plus some way of switching between which memory 
>is used for what packet is necessary; however, 
>the hardcoded algos should be the same (as far 
>as some tuneables are stored in memory instead of hardwired gates).

I'll let the hw people answer that, but it seems a reasonable point.

>As Bob pointed out in another email, classic ECN 
>will react to any number of marks within one RTT 
>(of that particular flow) with only a single 
>halving of the congestion window. Most other 
>transports that have been modeled after TCP/ECN 
>will behave similarly. Immediate ECN will react 
>to each mark to a smaller extent, and only a 
>full window (RTT) of marks will reduce the 
>window by half. Thus immediate ECN would be much 
>more aggressive when used with traditional RED, 
>ie. push the AQM to higher marking probabilities.

The paper (available on request, because still 
under submission) records experiments that show 
we can get equal rates between otherwise 
equivalent ECN and drop flows as long as the 
parameters of the two ramps are connected by a 
formula. This formula was found by fitting to the 
very clear curve visible along the ridge of the 
3-D plot on our slide 11 
<http://www.ietf.org/proceedings/88/slides/slides-88-tsvwg-20.pdf>.

I'm sure this will not be the whole story, but 
it's a good start. I believe that such parameter 
settings only lead to equal rates between an ECN 
and a drop flow for one of each type of flow. I 
won't be particularly worried if the relative 
rates stray from precise equality under different 
conditions, as long as there is no starvation, 
and they remain in the same ball-park.

>One venue that presents itself here, of course, 
>is to use 2nd order effect - i.e. the exact 
>marking pattern - to achive reasonable fairness 
>between transports making use of immediate and 
>classic reactions. However, I can not say 
>offhand, if this would be a practical method 
>(may require too much state in the 
>scheduling/aqm, including fine grained flow separation).

Hopefully we won't need to go there.

>That is what DCTCP currently does.

I wasn't aware that DCTCP was already being used 
alongside non-ECN traffic. Is this what you meant?

>However, a simple step function is incompatible with classic ECN.

I think you mean classic ECN TCP flows. If so, I 
wouldn't state this quite so strongly (yet). I 
suspect there will be conditions where a classic 
ECN TCP will be somewhat disadvantaged. However, we need experiments to see:
* whether the disadvantage is slight,
* how many classic ECN hosts might be affected,
* and the likelihood that their owners would 
rapidly upgrade them (AFAIK, their owners must 
have already intervened manually for ECN hosts to 
already be in the wild, given I believe ECN is 
turned off by default in TCP clients under the major operating systems).

>While reading Bob's earlier comment on classic 
>vs immediate ECN, I thought that probably an 
>exponential increase in marking probability, 
>above a specific threshold (lower than drop) 
>could "autotune" to a reasonable marking rate, 
>without necessarily locking classic out when 
>immediate is used. If the linear/step function 
>employed with RED (and shown on Bobs slides) is 
>a good enough approximation needs to be 
>verified. However, the details will probably 
>also depend on the mixure of number of classic 
>vs. immediate ECN flows at the bottleneck, and their respective RTTs...

Agreed.

>Finally, as the gateways (switches) cannot rely 
>on ECN to work (either on the required 
>timescales, as the RTT is too large for small 
>buffers, or the transport/sender is not 
>reacting), even ECN traffic has to be exposed to drops

Agreed

>  - and ideally here not to the tail-drop variant.

It may not be necessary to switch an ECN flow to 
AQM-generated drops - it may be sufficient to 
switch both ECN and drop traffic to tail drop at 
the same time - when load exceeds the operating 
region of the AQM as a whole. But, you may be right - needs more experiments.

Bob

---

From: "Ilpo Järvinen" <[email-masked]>
Date: Wed, 13 Nov 2013 01:20:16 +0200 (EET)

> > >to reveal just how many magic numbers there really are in the CoDel

Btw, Van & Kathleen say about this in ID:

"A CoDel control law more independent of interval is future work."

I suppose it still is...

> OK. From an admittedly hasty scan through Andrew McGregor's port of CoDel to
> ns3 (not the Linux code), it seems to introduce this hold-off time in the
> ControlLaw() function, but it only calls ControlLaw() from the ShouldDrop()
> function if the queue has remained above threshold for duration interval.
> 
> That implies that CoDel holds off signalling anything for 2 * interval, ie
> 200ms for the default setting of interval = 100ms.

There are two calls to it at least in the ID. CoDel is also implemented 
like that in ns2, Linux, and (based on very brief check) also in ns3. The 
first call happens exactly at interval, not two away from crossing the 
target (/threshold) delay. Both calls are preceded by a "drop" (/signal).

-- 
 i.

---

From: "Fred Baker (fred)" <[email-masked]>
Date: Wed, 13 Nov 2013 18:48:56 +0000

> 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.

---

From: "Fred Baker (fred)" <[email-masked]>
Date: Wed, 13 Nov 2013 20:19:00 +0000

> 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 propor…

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.