Re: [aqm] AQM schemes: Queue length vs. delay based

Michael Welzl <michawe@ifi.uio.no> Fri, 08 November 2013 21:11 UTC

Return-Path: <michawe@ifi.uio.no>
X-Original-To: aqm@ietfa.amsl.com
Delivered-To: aqm@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 609C321E819F for <aqm@ietfa.amsl.com>; Fri, 8 Nov 2013 13:11:38 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -102.327
X-Spam-Level:
X-Spam-Status: No, score=-102.327 tagged_above=-999 required=5 tests=[AWL=0.044, BAYES_00=-2.599, HTML_MESSAGE=0.001, SARE_SUB_OBFU_Q1=0.227, USER_IN_WHITELIST=-100]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 0HBw3Vg4L2dN for <aqm@ietfa.amsl.com>; Fri, 8 Nov 2013 13:11:33 -0800 (PST)
Received: from mail-out4.uio.no (mail-out4.uio.no [IPv6:2001:700:100:10::15]) by ietfa.amsl.com (Postfix) with ESMTP id EA5C721E814E for <aqm@ietf.org>; Fri, 8 Nov 2013 13:11:15 -0800 (PST)
Received: from mail-mx4.uio.no ([129.240.10.45]) by mail-out4.uio.no with esmtp (Exim 4.80.1) (envelope-from <michawe@ifi.uio.no>) id 1VetKa-00089T-Vv; Fri, 08 Nov 2013 22:11:04 +0100
Received: from dhcp-98ed.meeting.ietf.org ([31.133.152.237]) by mail-mx4.uio.no with esmtpsa (TLSv1:AES128-SHA:128) user michawe (Exim 4.80) (envelope-from <michawe@ifi.uio.no>) id 1VetKZ-0000OP-HK; Fri, 08 Nov 2013 22:11:04 +0100
Content-Type: multipart/alternative; boundary="Apple-Mail=_37DD1630-F207-4B53-8A19-0FFFA3B2827E"
Mime-Version: 1.0 (Mac OS X Mail 6.6 \(1510\))
From: Michael Welzl <michawe@ifi.uio.no>
In-Reply-To: <CEA27FCC.4AF01%prenatar@cisco.com>
Date: Fri, 08 Nov 2013 13:11:00 -0800
Message-Id: <40D660CC-6A01-43DD-AF72-EE0A1C4503F6@ifi.uio.no>
References: <CEA27FCC.4AF01%prenatar@cisco.com>
To: Preethi Natarajan <preethi.cis@gmail.com>
X-Mailer: Apple Mail (2.1510)
X-UiO-SPF-Received:
X-UiO-Ratelimit-Test: rcpts/h 3 msgs/h 1 sum rcpts/h 3 sum msgs/h 1 total rcpts 9620 max rcpts/h 44 ratelimit 0
X-UiO-Spam-info: not spam, SpamAssassin (score=-5.0, required=5.0, autolearn=disabled, HTML_MESSAGE=0.001, UIO_MAIL_IS_INTERNAL=-5, uiobl=NO, uiouri=NO)
X-UiO-Scanned: DCE61B5D7A234AD153540D68066CD8EF66B44A6F
X-UiO-SPAM-Test: remote_host: 31.133.152.237 spam_score: -49 maxlevel 80 minaction 2 bait 0 mail/h: 1 total 25 max/h 7 blacklist 0 greylist 0 ratelimit 0
Cc: Naeem Khademi <naeem.khademi@gmail.com>, "aqm@ietf.org" <aqm@ietf.org>
Subject: Re: [aqm] AQM schemes: Queue length vs. delay based
X-BeenThere: aqm@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: "Discussion list for active queue management and flow isolation." <aqm.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/aqm>, <mailto:aqm-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/aqm>
List-Post: <mailto:aqm@ietf.org>
List-Help: <mailto:aqm-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/aqm>, <mailto:aqm-request@ietf.org?subject=subscribe>
X-List-Received-Date: Fri, 08 Nov 2013 21:11:38 -0000

On 8. nov. 2013, at 11:00, Preethi Natarajan <preethi.cis@gmail.com> wrote:

> Hi Naeem, all:
> 
> Please see detailed responses inline.
> 
> From: Naeem Khademi <naeem.khademi@gmail.com>
> Date: Thursday, November 7, 2013 10:50 PM
> To: Preethi Natarajan <preethi.cis@gmail.com>
> Cc: "aqm@ietf.org" <aqm@ietf.org>
> Subject: Re: [aqm] AQM schemes: Queue length vs. delay based
> 
>> I fully agree with the need to have AQMs that use "queuing delay" as metric and not "queue length" and this is already a bonus for algorithms that use this metric (e.g. PIE). However, I believe that one can possibly modify RED or its derivatives (e.g. Adaptive RED) to set their thresholds based on "queuing delay" as well (although such algorithms don't exists yet as of now). Whether the outcome of these modifications to xRED algorithms would make them better than PIE and/or CoDel is another subject and I'm not going to speculate on that here. 
> 
> 
> Of course. Our initial discussions considered a latency based RED derivative. We later decided to focus on a proportional integral based control law instead of RED (see below for more). 
> 
>> 
>> One specific issue with PIE is that it tries to *estimate* the queuing delay over a certain time interval (t_update) and still somehow uses the "queue length" and departure rate (over the interval) to estimate the queuing delay. So saying that PIE uses the queueing delay instead of queue length may not be 100% accurate. 
> 
> 
> Any latency based scheme requires the queueing delay to work with. The fact of the matter is, the queueing delay is not directly available on platforms. Some platforms can afford timestamping to figure the queuing delay but not all platforms  can. In fact, over the past months we've come to realize that a latency based scheme is actually two different items at work — (i) the control law and (ii) the mechanism which provides the queueing delay to this control law. This would be true for any latency based scheme, be it, PIE, CoDEL, FQ_CoDEL or xRED. Based on this observation, we plan to separate out the two components in PIE, possibly in the next version of the draft. The objective being that (ii) would vary with the platform and it could be direct input (if platform maintains it), timestamp-based (like in CoDEL derivatives), dequeue-based, or even others that we are exploring at the moment. 
> 
> The current version of the PIE draft fully acknowledges the fact that what PIE acquires with the dequee-based rate estimation is only an estimate of the queuing delay and not the actual (Section 4.2 of v00). The larger point for discussion here is a latency based AQM that uses queuing delay instead of queue length. 
> 
> 
>> 
>> Moreover, in a varying bandwidth scenario, depending on how often the bandwidth changes and at what granularity, the derived "estimated queuing delay" by PIE might be an outdated information e.g. it shows how the channel has been (in term of delay) in the last 30ms and now how it is now! if I'm not mistaken that has been somehow resolved in DOCSIS 3.1 by coupling PIE's departure rate to the actual link layer rate.  
> 
> 
> We've experimented with timestamp-based delay inputs to PIE. We have not seen any noticeable difference between the dequeue-based scheme and the timestamp-based for all the scenarios Rong has presented at IETF thus far. Even in extreme bandwidth changing conditions dequeue-based scheme can adapt within few tupdate cycles. Again, PIE is flexible in its delay input mechanism and will go with whatever is the best possible option available on the platform. I don't think any latency based scheme can get better than that :). 

An AQM scheme should also work when the bandwidth is *not* changing. The results that Naeem presented in ICCRG don't indicate that PIE is consistently better than CoDel (which is also delay-based). I'm not trying to say if this or that is better, just that statements like this one are rather handwavy.


>> In overall, while there are of course significant improvements made in PIE's (and (FQ)-CoDel's) design, there are probably still lessons to be learned from xRED family (check http://urn.nb.no/URN:NBN:no-38868 to see some examples). Throwing away all the knowledge and improvement gained from RED-like AQMs, CHoKe, etc and coming up with brand-new AQMs without (experimentally) comparing them to the gallery of existing ones wouldn't be great!
> 
> 
> Our initial discussions considered more than just the RED varieties. As we've mentioned before, PIE is based on the concept of proportional integral (PI). PI is not something we discovered. PI controller has been around for long and you can refer to Hollot, Towsley et. al's paper from a decade ago for more information on PI based AQM scheme. We believe PI's strong theoretical stability is valuable for diverse deployment conditions and incorporated PI into our PIE design. We did our own set of theoretical analysis for PIE and we were proved right. You can find more details about that in our HPSR paper (http://www.ieee-hpsr.org/2013/)

Another handwavy statement. Using a PI controller may be a good design idea, but that alone doesn't really tell us much about the overall behavior.

Cheers,
Michael