From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lb0-x22e.google.com (mail-lb0-x22e.google.com [IPv6:2a00:1450:4010:c04::22e]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by huchra.bufferbloat.net (Postfix) with ESMTPS id 70D2821F2DA; Mon, 11 May 2015 07:02:18 -0700 (PDT) Received: by lbbzk7 with SMTP id zk7so94591460lbb.0; Mon, 11 May 2015 07:02:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=content-type:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=FmSH/mouefeP/jCOlv57buY9rLMRt/g1pCkwfEzs40M=; b=caVM92n7qz6vm0WcMoOyXOdn0yF2dLo4R0MdhpG0QT04xyCgKyscmOnpwglid+Sflz Q1d+/rJE2jmbMd7iLLFizVR7gShsv9qfiHGY2MlLBli3V7xIOhOa68hJ955q4qR8ivGK 63qk6CGt79XJrhdPvBQ16Ybnu8h0PxlXqjXt/wfBgLPh0b4c5QK21sATGUE1LDCRPkg1 qkae3pD+FPgxMWELnxBd9PpfC9KbIQ2DFgzoNQx+0aFC6zkLIAcpKOcFqSqqzZCitPLS 9jzI01uFRO2nKnDJlatF2NkACe6pXe1WEWAUYVcATIxqZ06KlvsbLvS4qORPRxPzd8c/ YnyQ== X-Received: by 10.152.87.204 with SMTP id ba12mr8320830lab.35.1431352464571; Mon, 11 May 2015 06:54:24 -0700 (PDT) Received: from bass.home.chromatix.fi (87-95-62-72.bb.dnainternet.fi. [87.95.62.72]) by mx.google.com with ESMTPSA id xs12sm3066026lac.16.2015.05.11.06.54.18 (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Mon, 11 May 2015 06:54:23 -0700 (PDT) Content-Type: text/plain; charset=windows-1252 Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2098\)) From: Jonathan Morton In-Reply-To: Date: Mon, 11 May 2015 16:54:11 +0300 Content-Transfer-Encoding: quoted-printable Message-Id: <25B7AFB1-A7F4-40FC-8010-DAB114EBE489@gmail.com> References: <152DD781-725D-4DD7-AB94-C7412D92F82C@gmx.de> <1F323E22-817A-4212-A354-C6A14D2F1DBB@gmail.com> To: cake@lists.bufferbloat.net X-Mailer: Apple Mail (2.2098) Cc: codel@lists.bufferbloat.net, bloat Subject: [Codel] Explicit Load Regulation - was: Control theory and congestion control X-BeenThere: codel@lists.bufferbloat.net X-Mailman-Version: 2.1.13 Precedence: list List-Id: CoDel AQM discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 11 May 2015 14:02:56 -0000 X-List-Received-Date: Mon, 11 May 2015 14:02:56 -0000 X-List-Received-Date: Mon, 11 May 2015 14:02:56 -0000 X-List-Received-Date: Mon, 11 May 2015 14:02:56 -0000 X-List-Received-Date: Mon, 11 May 2015 14:02:56 -0000 X-List-Received-Date: Mon, 11 May 2015 14:02:56 -0000 X-List-Received-Date: Mon, 11 May 2015 14:02:56 -0000 X-List-Received-Date: Mon, 11 May 2015 14:02:56 -0000 X-List-Received-Date: Mon, 11 May 2015 14:02:56 -0000 X-List-Received-Date: Mon, 11 May 2015 14:02:56 -0000 X-List-Received-Date: Mon, 11 May 2015 14:02:56 -0000 X-List-Received-Date: Mon, 11 May 2015 14:02:56 -0000 X-List-Received-Date: Mon, 11 May 2015 14:02:56 -0000 X-List-Received-Date: Mon, 11 May 2015 14:02:56 -0000 > On 11 May, 2015, at 14:34, Jonathan Morton = wrote: >=20 > I=92m also now thinking about how to approximate fairness between ELR = flows *without* flow isolation. Since ELR would aim to provide a = continuous signal rather than a stochastic one, this is actually a = harder problem than it sounds; naively, a new flow would stay at minimum = cwnd as long as a competing flow was saturating the link, since both = would be given the same up/down signals. There might need to be some = non-obvious properties in the way the signal is provided to overcome = that; I have the beginnings of an idea, but need to work it out. And the result of a good wander is that I think we can, in fact, use the = distinction between ECT(0) and ECT(1) to perform this signalling, and = therefore we don=92t need to somehow find extra bits in the IP headers. = This might take a little while to explain: When an ELR flow is negotiated by the endpoints, senders set ECT(1) on = all relevant packets they originate. Since most ECN senders currently = set ECT(0), and those that use ECT(1) at all tend to alternate between = ECT(0) and ECT(1), routers are able to assume with sufficient safety = that an ECT(1) packet can be used to carry an ELR signal, and that an = ECT(0) packet belongs to a legacy ECN flow. The =93fast down=94 signal for both ECN and ELR flows is the ECN = codepoint set in any packet during one RTT. This is echoed back to the = sender by the receiver, as for legacy ECN. Compliant senders should = halve their congestion window, or perform an equivalent backoff. In an ELR flow, the ratio of ECT(1) to ECT(0) packets received is = significant, and carries the remaining four states of the ELR protocol. = Receivers keep a history of the ECN codepoints in the most recent three = data-bearing packets received on the flow. They echo back to the sender = the number of such packets which had ECT(1) set. The significance of = this number is as follows: 0: slow down - sender should perform a small, multiplicative = (exponential) backoff in this RTT 1: hold - sender should not increase send rate in this RTT 2: slow up - sender may perform only additive (linear) increase in = this RTT 3: fast up - sender may perform multiplicative (exponential) increase = (eg. slow start) in this RTT Since one byte can hold four of these indications, the receiver may = indicate a twelve-packet history in this way, allowing for sparse and = lost acks. Senders should perform all of the actions indicated by these = signals which have *not* yet been performed, allowing for the = possibility of overlap between subsequent signals. Queues implementing ELR maintain one or more five-state control = variables, which may be per flow, per traffic class or global, and = reflect the queue's opinion of whether senders associated with each = control variable may increase, should hold or should decrease their send = rates (and how quickly) in order to match link capacity, or a fair share = thereof, at that queue. In most cases, there will be at most one queue = on a given network path for which this opinion is not =93may increase = rapidly=94; this is known as the bottleneck queue. In the =93may increase rapidly=94 state, the queue performs no = modifications to the ECN field. In the =93may increase gradually=94 state, the queue changes one out of = every three ECT(1) packets to ECT(0), and leaves all other packets = unchanged. In the =93should hold=94 state, the queue changes two out of every three = ECT(1) packets to ECT(0), and leaves all other packets unchanged. In the =93should decrease gradually=94 state, the queue changes all = ECT(1) packets to ECT(0), and additionally changes some proportion of = originally ECT(0) packets to the ECN codepoint, and drops the same = proportion of Not-ECT packets. In the =93should decrease rapidly=94 state, all of the actions performed = in =93should decrease gradually=94 state are performed, but also ECT(1) = packets are changed to the ECN codepoint at the same rate as ECT(0) = packets. It should be obvious that these five states correspond precisely to the = =93fast up=94, =93slow up=94, =93hold=94, =93slow down=94 and =93fast = down=94 signals observed by the receiver of a single flow. Thus an = ELR-compliant queue implementing flow isolation is able to precisely = control the send rates of each flow passing through it. The behaviour of multiple flows sharing a single ELR queue with a single = control variable is more complex. Consider the case where one ELR flow = is established on the link, and has stabilised in the =93hold=94 state, = when a new ELR flow begins. After the new flow=92s initial congestion = window is sent and acknowledged, it will also see the same = two-out-of-three ECT(0) pattern (on average) as the established flow, = and might then appear to be stuck in the =93hold=94 state with its = initial congestion window for all subsequent traffic. However, packets for the new flow will disrupt the regular pattern of = the established flow=92s ELR signal, and vice versa, resulting in a = stochastic distribution of =93slow down=94 and =93slow up=94 signals = actually being received by both flows. The resulting low-amplitude AIMD = behaviour should result in the congestion windows of the two flows = converging, eventually giving fair sharing of the link. While = convergence time and sensitivity to RTT are both inferior to a = flow-isolating queue, they should be no worse than for conventional AQM = queues. - Jonathan Morton