Subject: Re: [aqm] draft-ietf-aqm-pie-01: review

From: Bob Briscoe <[email-masked]>
Date: Fri, 03 Jul 2015 11:10:46 +0100

Vishal,

Pls note my new interim email @.

Sorry for extended delay replying - your mail arrived after I left my 
office for the last time (I've left BT).
I'm still "between jobs", but I'm trying to catch up on unfinished 
threads - inline.

On 22/05/15 19:01, Vishal Misra wrote:
> Bob, Rong
>
> Let me present our rationale for choosing the PI controller (hope it 
> will be helpful to present the rationale for PIE).
Thank you. Pls put this text in the draft.

In my review I wasn't questioning the use of a PI controller, I was just 
pointing out that the draft doesn't include any text that justifies 
using PI. Here's what I actually said:

/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
4 Articulate the Rationale for a PI Controller

The draft doesn't actually say that a PI controller is chosen to keep 
the average latency constant even
under high load. The 3rd para of Intro says that, unlike RED's use of 
queue length, PIE uses latency as
the metric. However, that alone could just mean that the latency still 
increases with load.
All the rationale in section 4.2 doesn't state this fundamental 
reasoning either, except by reference, citing
the original paper on PI [HMTG01].
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\

However, since writing that review, we've got results that /do/ question 
whether a hard delay threshold is the correct goal (see next email).

> When we were working on the issue in 2001-2001, RED had been deployed 
> everywhere but also disabled everywhere. People had trouble 
> understanding and tuning RED. Our fluid modeling and control theoretic 
> analysis showed that RED was a classical Proportional Controller with 
> a delay element (the queue averaging mechanism. We identified the 
> following flaws with RED
>
> 1. The Proportional control meant that RED could not control the 
> queue length to a specified value, it is an inherent limitation of 
> Proportion al control. RED always controlled the queue (and hence 
> delay) to some value between min_thresh and max_thresh depending on 
> the load.
>
> 2. The delay element (queue averaging) introduced an additional 
> instability to the control loop making it more difficult to control 
> (and as Bob has said, the instability is  oscillations causing jitter 
> and loss of some link throughput due to the oscillations).
>
> We decided to redesign the controller but since RED was already 
> implemented, create a controller that could use the same deployment 
> with some minor modifications. So what we did to fix the issues was:
>
> 1. In classical control theory Integral control drives the steady 
> state error to zero, so we changed the Proportional Control to 
> Proportional Integral, or PI control which lets you control the buffer 
> queue length to a specific, target value independent of the load.
> 2. We simply removed the queue averaging mechanism.

For the record (I know you know this), it's not as simple as just 
removing averaging, because one doesn't want to introduce loss until 
it's likely that there's persistent load not just a transient burst. PIE 
introduces different smoothing delays (with magnitude based on stability 
theory).

>
> The resultant controller could work with existing RED implementations 
> with a slight modification to the update equation.

The implementation of PIE is much more complex than RED. I assume you 
mean you could build PIE on top of the parts of RED implemented in 
hardware (but this statement might not be true for all vendors' 
implementations).

Bob

>
>
> -Vishal
> --
> http://www.cs.columbia.edu/~misra/ <http://www.cs.columbia.edu/%7Emisra/>
>
>
>> On May 22, 2015, at 9:38 AM, Bob Briscoe <[email-masked] 
>> <mailto:[email-masked]>> wrote:
>>
>>
>> I didn't mean that you need to justify b etter why you chose a PI 
>> controller. I said you need to "Articulate the Rationale for a PI 
>> Controller"
>
> _______________________________________________ aqm mailing list 
> [email-masked] https://www.ietf.org/mailman/listinfo/aqm 

-- 
________________________________________________________________
Bob Briscoe                               http://bobbriscoe.net/

---

From: Bob Briscoe <[email-masked]>
Date: Fri, 03 Jul 2015 11:32:51 +0100

Rong,

On 22/05/15 21:49, Rong Pan (ropan) wrote:
> Content-Language: en-US Content-Type: multipart/alternative; 
> boundary="_000_D184CA8CF0F2ropanciscocom_"
> >>[Bob] AFAICT, limiting the change in beta to no more than 2% will 
> prevent PIE reacting fast to slow-start. Are you saying you intended 
> to make PIE >>delay its response to a slow start? If so, ... eh? what? 
> why?
>
> >>Once a slow start has reached capacity, and is heading towards twice 
> capacity in the next RTT (remembering the AQM doesn't know what a RTT 
> is), >>an AQM could take a bet on whether the flow will finish before 
> it gets to twice capacity, or not.
> >>* If yes, then in hindsight the AQM wouldn't have needed to drop a 
> packet.
> >>* If no, then in hindsight the AQM should have dropped a packet (in 
> hindsight ideally when the queue first started to grow).
>
> [RONG]: because the queue is filling up very fast during TCP's slow 
> start, dropping too quickly would cause a timeout. As you mentioned, 
> hopefully they will finish. In CableModem SpeedTest scenarios, 
> however, we need to show the speed in the fast 10sec or so. The test 
> flow is very long and we can not afford to incur a time out. In 
> generic access link scenarios when flow multiplexing is low, this 
> twist should help. Clapping it makes the convergences time slower. 
> However, the drop probability should eventually catch up. Maybe 
> changing this to "MAY" is more appropriate?

I am concerned that this arbitrary limit on changes to beta might have 
been introduced for the specific traffic used in the CableModem 
SpeedTests. That might be a good representation of tomorrow's traffic, 
but it might not. For instance, did the TCP implementations use hybrid 
slow-start (HSS), which is now the default in Linux?

My main concern is that slow-start is probably going to become a major 
focus of improvement over the next few years. Hybrid slow-start is an 
improvement, but a lot more can and will be done. If PIE assumes that 
slow-start is like Van Jacobson designed it, and guesses when to 
introduce losses on that assumption, In future, it could make it much 
more difficult to improve slow start 'properly' (in the end-systems).

So, yes, in summary, MAY would be appropriate. Perhaps with a sentence 
saying more research is needed on the interaction between AQMs and 
improvements to the slow-start algorithm (e.g. HSS).

Bob

PS. Pls note my new interim email @.

Sorry for extended delay replying - your mail arrived after I left my 
office for the last time (I've left BT).
I'm still "between jobs", but I'm trying to catch up on unfinished threads.

>
> Thanks,
>
> Rong
>
>
> From: Bob Briscoe <[email-masked] <mailto:[email-masked]>>
> Date: Friday, May 22, 2015 9:38 AM
> To: rong <[email-masked] <mailto:[email-masked]>>
> Cc: Richard Scheffenegger <[email-masked] <mailto:[email-masked]>>, 
> "[email-masked] 
> <mailto:[email-masked]>" 
> <[email-masked] 
> <mailto:[email-masked]>>, Dave Taht 
> <[email-masked] <mailto:[email-masked]>>, Greg White 
> <[email-masked] <mailto:[email-masked]>>, AQM IETF list 
> <[email-masked] <mailto:[email-masked]>>, "Eddy Wesley M. [VZ]" 
> <[email-masked] <mailto:[email-masked]>>
> Subject: Re: [aqm] draft-ietf-aqm-pie-01: review
>
> Rong,
>
> I've snipped inline...
>
> At 22:15 21/05/2015, Rong Pan (ropan) wrote:
>> Content-Language: en-US
>> Content-Type: multipart/alternative;
>> boundary="_000_D183961BF09Cropanciscocom_"
>>
>> Sorry that I have not fully read Bob's report so I have been 
>> hesitating of speaking up. Let me just comment on the following 
>> thread. I will spend more time on Bob's detailed comments and give 
>> feedback later.  For now, please see inline&
>>
>> >
>> Thanks,
>> Rong
>>
>>
>> From: Greg White <[email-masked] <mailto:[email-masked]> >
>> Date: Wednesday, May 13, 2015 10:02 AM
>> To: Bob Briscoe <[email-masked] <mailto:[email-masked]>>
>> Cc: Richard Scheffenegger <[email-masked] <mailto:[email-masked]>>, 
>> "Eddy Wesley M. [VZ]" <[email-masked] 
>> <mailto:[email-masked]> >, Dave Taht <[email-masked] 
>> <mailto:[email-masked]>>, "[email-masked] 
>> <mailto:[email-masked]>" 
>> <[email-masked] 
>> <mailto:[email-masked]>>, AQM IETF list 
>> <[email-masked] <mailto:[email-masked]>>
>> Subject: Re: [aqm] draft-ietf-aqm-pie-01: review
>>
>>
>>
>> On 5/12/15, 7:31 PM, "Bob Briscoe" <[email-masked] 
>>     My comment was in response to discovering an
>>     arbitrary limit had been added to the Linux
>>     implementation: "Limit the change in p per
>>     T_UPDATE to 2%". The whole point of the rest of
>>     the PIE algorithm is to automatically limit how
>>     rapidly p changes, by steering a mid-course far
>>     enough away from two cliffs known to be out there
>>     somewhere (probably not where the theory says
>>     they are, but at least it gives a feel).
>>
>>     So to write in a hard-coded limit that completely
>>     overrides all the autotuning is IMO just plain
>>     ignorant (I'll eat my words if someone like Rong
>>     wrote that code!). It will make PIE unnecessarily
>>     sluggish when conditions are changing fast and
>>     the rest of the code has judged that it will be quite safe to
>>     react fast.
>>
>>
>> [Greg] I don't know the origin of the 2% limit, but IMO it could very 
>> reasonably be that actual (simulated) traffic pointed out that the 
>> control theory prediction (based on linearized models of steady-state 
>> Reno IIRC) really wasn't the best guidance in all cases.  In fact, I 
>> really can't think of another reason why it would have been added.  
>> To me your reaction precisely points out the danger of assuming that 
>> a bit of theory should be taken as guidance when the assumptions 
>> underlying the theory are known to only approximate reality in a 
>> constrained set of scenarios.  I did control theory and control 
>> system design for a while (e.g. 
>> Ã¢¬}www.ri.cmu.edu/pub_fifiles/pub3/white_greg_1992_1/white_greg_1992_1.pdf 
>> <http://www.ri.cmu.edu/pub_files/pub3/white_greg_1992_1/white_greg_1992_1.pdf> 
>> ).  I don't claim to be an expert anymore, but I know from experience 
>> that incorrect system modeling will result in incorrect controller 
>> design, and even in simple systems, reality needs to be considered 
>> strongly over theory.  In my testing of PIE, the algorithm (with the 
>> 2% limit) works. 
>
> Any AQM 'works'. As you say below, the important test is whether it 
> 'works' better without the limit? And if so under what assumptions and 
> what definition of 'works'?
>
>> I don't have simulation results with and without the limit, but I'm 
>> going to believe (until shown otherwise) that it was added for a real 
>> reason.
>>
>> >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>Rong: It is designed to help in the 
>> one single TCP test during slow start phase. In this case, queue 
>> could quickly goes up during slow start and demands high drop 
>> probability. In Cable Modem SpeedTest environment, one could not 
>> afford triggering timeout and lose throughput as throughput is shown 
>> to customers who are testing his/her connection speed. TCP is not a 
>> good test for this, but that is what we do now. As Bob mentioned in 
>> his previous emails, we need to distinguish what are MUST, SHOULD, 
>> and MAY items of PIE. I consider this as SHOULD, not MUST.
>
> [Bob] AFAICT, limiting the change in beta to no more than 2% will 
> prevent PIE reacting fast to slow-start. Are you saying you intended 
> to make PIE delay its response to a slow start? If so, ... eh? what? why?
>
> Once a slow start has reached capacity, and is heading towards twice 
> capacity in the next RTT (remembering the AQM doesn't know what a RTT 
> is), an AQM could take a bet on whether the flow will finish before it 
> gets to twice capacity, or not.
> * If yes, then in hindsight the AQM wouldn't have needed to drop a packet.
> * If no, then in hindsight the AQM should have dropped a packet (in 
> hindsight ideally when the queue first started to grow).
>
> By arbitrarily clamping the increase at 2%, it's making a judgement on 
> the risk of each of these, and on the harm that would ensue if it 
> makes the wrong call either way.
>
> Delaying a drop improves performance of the flow in question if its 
> going to end anyway (as you say), but it certainly means the 
> slow-start will spike other flows harder (if the flow doesn't end of 
> its own accord).
>
> Good practice is for a host to use HSS (hybrid slow-start) or a 
> similar technique to detect the end of slow start so it can stop SS 
> just as it reaches capacity, not one RTT later. By putting off the 
> drop that would end SS, you are rewarding flows that do not use HSS, 
> which is the wrong incentive.
>
> You are also potentially confusing HSS. From packet spacings, it 
> thinks it's detected the approach of the end of SS. If the drop it 
> expects doesn't actually appear, there's a strong danger that the 
> sender will reverse its guess that SS is about to end, and move back 
> into full SS. Then slam into the buffers, which are actually right 
> where it thought they were.
>
>> >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Rong: I believe in the control theoretical analysis to study the 
>> basis of the design. The analysis does help give the guidelines of 
>> how to choose the parameters: it may not need to be accurate to the 
>> hundredth decimal point, but we can not be order of magnitude off. If 
>> one does change alpha and beta parameters (and their relative weight) 
>> in PIE by an order of magnitude, I am sure the system will be off. 
>> This is the value that control theory brings us. Of course, there are 
>> real system challenges that we have to deal with like the above comment.
>
> Yup.
>
>> >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>Rong: Bob has a question of why choosing PI. I like the PI controller 
>> because AQM naturally has proportional (rate) and integral (queue 
>> length) components to it. It is the best fit for our setup. I see it 
>> as AQM providing two knobs for us to control it :-), what a waste not 
>> to take advantage of it!
>
> I think I must have phrased one of my comments badly (altho perhaps 
> you're solely responding to a heading).
>
> I didn't mean that you need to justify better why you chose a PI 
> Controller". I meant (and said) that you do not actually even say what 
> the aim of a PI controller is - i.e. to keep queuing delay at the same 
> level under a wide range of loads.
>
> It wasn't a criticism of the choice of a PI controller, it was 
> intended to be a helpful hint that you haven't explained your 
> rationale well, for someone reading this who doesn't know the background.
>
>
> Bob
>
> Bob Briscoe, BT