[aqm] Control Theoretic Analyses of PI(E) (was Gen-art LC review of draft-ietf-aqm-recommendation-08)
Vishal Misra <misra@cs.columbia.edu> Mon, 26 January 2015 09:29 UTC
Return-Path: <vm2020@columbia.edu>
X-Original-To: aqm@ietfa.amsl.com
Delivered-To: aqm@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 8B6DC1A8855 for <aqm@ietfa.amsl.com>; Mon, 26 Jan 2015 01:29:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.609
X-Spam-Level:
X-Spam-Status: No, score=-3.609 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, J_CHICKENPOX_22=0.6, RCVD_IN_DNSWL_MED=-2.3, T_RP_MATCHES_RCVD=-0.01] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id L4lJLNUyeOyW for <aqm@ietfa.amsl.com>; Mon, 26 Jan 2015 01:29:22 -0800 (PST)
Received: from buckwheat.cc.columbia.edu (buckwheat.cc.columbia.edu [128.59.72.251]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 2CFDE1A8852 for <aqm@ietf.org>; Mon, 26 Jan 2015 01:29:22 -0800 (PST)
Received: from hazelnut (hazelnut.cc.columbia.edu [128.59.213.250]) by buckwheat.cc.columbia.edu (8.13.8/8.13.8) with ESMTP id t0Q9S4QM030682 for <aqm@ietf.org>; Mon, 26 Jan 2015 04:29:21 -0500
Received: from hazelnut (localhost.localdomain [127.0.0.1]) by hazelnut (Postfix) with ESMTP id E4E1F38 for <aqm@ietf.org>; Mon, 26 Jan 2015 04:29:20 -0500 (EST)
Received: from rambutan.cc.columbia.edu (rambutan.cc.columbia.edu [128.59.29.5]) by hazelnut (Postfix) with ESMTP id CE1E638 for <aqm@ietf.org>; Mon, 26 Jan 2015 04:29:20 -0500 (EST)
Received: from mail-qa0-f42.google.com (mail-qa0-f42.google.com [209.85.216.42]) by rambutan.cc.columbia.edu (8.14.4/8.14.3) with ESMTP id t0Q9TKec005941 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for <aqm@ietf.org>; Mon, 26 Jan 2015 04:29:20 -0500 (EST)
Received: by mail-qa0-f42.google.com with SMTP id dc16so5928877qab.1 for <aqm@ietf.org>; Mon, 26 Jan 2015 01:29:20 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:content-type:subject:message-id:date:to :mime-version; bh=JfdGHwgUB3mASVl/BMG6UqvWUAGri4iPViu0GBwsh7U=; b=GqX1AhnZtUsqrmcjy7UM3uViJckrVA4ylC2HsPRoiCNwrCJAU3ABfyDB9wVfUu3x9r GDs4ti8lCLDsQqHWji2oZ+H3/ZPQ+nROt4sijP2Lm1KI/PcLbcZ8Ipiz9IHIhJGS62Jz pHNkv41248xoJf0OnJpvVHWj7Mz7aOksC3wLo/349+Htuj0K/rOPS5omeKR1bkYCHWPS k9R9BCdvMuEpFAnQ7Gy6nb7rVE0UwHE8YAOUgXjDGYwHKqYxH4Zuar3uu6nEaUDFJDPl pzgvuSDF3FtbnWC2T95WnwzrJbZr5IIhowmhFqLQTF6BJm9fmDd+3I4t80GRxg4mNBsZ dyWg==
X-Gm-Message-State: ALoCoQnfyn6Nvj7tgH7aax+g1sBNRDNtqYi88HSodMyzyOsRBsNAwbmNpWmWSB10qQTv/dtuW8JmCQNHDvy1URJIAdZaYrvuVDZlGp265ALgqn/lcA0/qRkFMJELIRQmJ5OUmGzu1kq7
X-Received: by 10.229.236.129 with SMTP id kk1mr14741476qcb.20.1422264560270; Mon, 26 Jan 2015 01:29:20 -0800 (PST)
X-Received: by 10.229.236.129 with SMTP id kk1mr14741461qcb.20.1422264560084; Mon, 26 Jan 2015 01:29:20 -0800 (PST)
Received: from ?IPv6:2001:18d8:ffff:16:6d80:4a54:250d:3cf1? ([2001:18d8:ffff:16:6d80:4a54:250d:3cf1]) by mx.google.com with ESMTPSA id r2sm9426061qab.46.2015.01.26.01.29.18 for <aqm@ietf.org> (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Mon, 26 Jan 2015 01:29:18 -0800 (PST)
From: Vishal Misra <misra@cs.columbia.edu>
Content-Type: multipart/alternative; boundary="Apple-Mail=_9608AFCE-D20E-4F1C-998E-AD569E51EF46"
Message-Id: <039049E6-71E2-4E55-8678-E1E0E472F87B@cs.columbia.edu>
Date: Mon, 26 Jan 2015 04:29:17 -0500
To: aqm@ietf.org
Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2070.4\))
X-Mailer: Apple Mail (2.2070.4)
X-No-Spam-Score: Local
X-Scanned-By: MIMEDefang 2.68 on 128.59.29.5
Archived-At: <http://mailarchive.ietf.org/arch/msg/aqm/hAsLOyo-GeBMHbcQZ4t9QnPXXvU>
Subject: [aqm] Control Theoretic Analyses of PI(E) (was Gen-art LC review of draft-ietf-aqm-recommendation-08)
X-BeenThere: aqm@ietf.org
X-Mailman-Version: 2.1.15
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: Mon, 26 Jan 2015 09:29:24 -0000
On 08/01/15 01:20, Fred Baker (fred) wrote: >> Yes. I think something like this would be good. The buffer bloat >> example is probably an extreme case of things not having AQM at all >> and interacting badly. It would maybe be worth mentioning that any >> AQM mechanism has also got to work in series with boxes that don't >> have any active AQM - just tail drop. Ultimately, I would say this >> is just a matter of control engineering principles: You are >> potentially making a network in which various control algorithms >> are implemented on different legs/nodes and the combination of >> transfer functions could possibly be unstable. Has anybody applied >> any of the raft of control theoretic methods to these algorithms? >> I have no idea! > Well, PIE basically came out of control theory (a basic equation that > describes a phase-locked loop), and I believe that Van and Kathy will > say something similar about Codel. But that’s not a question for this > paper, it’s a question for the various algorithmic papers. Elwyn, I would like to expand on a comment that Fred made above. He is absolutely correct, about PIE coming out of control theory. PIE is based on the PI AQM algorithm proposed by us back in 2001 (http://dna-pubs.cs.columbia.edu/citation/paperfile/23/MisraInfocom01-AQM-Controller.pdf <http://dna-pubs.cs.columbia.edu/citation/paperfile/23/MisraInfocom01-AQM-Controller.pdf>), where we showed the benefits of using a PI controller to regulate queue lengths and delays through a formal control theoretic analysis. The PI algorithm itself came from a fluid model of TCP+AQM that we developed (http://dna-pubs.cs.columbia.edu/citation/paperfile/27/sigcomm2000.pdf <http://dna-pubs.cs.columbia.edu/citation/paperfile/27/sigcomm2000.pdf>) and the model is referenced in the IETF draft. When we designed PI, we took great care in designing an algorithm that was amenable to a very simple implementation at line speeds. We could have gone in the direction of sophisticated (non-linear/optimal) control algorithms but we instead kept simplicity of implementation front and center and it is great to see that the standards community has come to appreciate the work. The PIE update algorithm is very similar to the original PI algorithm (we controlled queue length to a reference value whereas PIE controls delay by dividing the queue length by measured link capacity) - Rong Pan and the PIE team have done great work in adapting the originial algorithm for implementation in production environments and all our original analyses carries through to PIE. I am happy to provide references to more control theoretic analyses (including ours) that look at the behavior and stability of the AQM algorithms. One thing to note though that hasn't changed all these years is if you look at Section VII.A of our PI paper linked above, the full benefits of AQM are realized in conjunction with ECN. On a bottlenecked link, if you reduce delay (by controlling it via a mechanims like PI(E) or CoDel), unless you have ECN implemented you will end up increasing loss rates which may not be a good thing. Lastly, I had contributed pi.cc <http://pi.cc/> to ns2 back in 2001 - a version seems to have survived all these years if anyone is interested in playing with it: https://github.com/jridgewell/ns2/blob/master/queue/pi.cc <https://github.com/jridgewell/ns2/blob/master/queue/pi.cc> Thanks, -Vishal -- http://www.cs.columbia.edu/~misra/
- [aqm] Control Theoretic Analyses of PI(E) (was Ge… Vishal Misra
- [aqm] Control Theoretic Analyses of PI(E) (was Ge… Vishal Misra
- [aqm] ECN: was Control Theoretic Analyses of PI(E) John Leslie
- Re: [aqm] ECN: was Control Theoretic Analyses of … Vishal Misra
- Re: [aqm] ECN: was Control Theoretic Analyses of … Dave Taht
- Re: [aqm] ECN: was Control Theoretic Analyses of … Dave Taht
- Re: [aqm] ECN: was Control Theoretic Analyses of … Vishal Misra
- Re: [aqm] ECN: was Control Theoretic Analyses of … KK
- Re: [aqm] ECN: was Control Theoretic Analyses of … Vishal Misra
- Re: [aqm] ECN: was Control Theoretic Analyses of … KK
- Re: [aqm] ECN: was Control Theoretic Analyses of … Dave Taht