From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ob0-x22f.google.com (mail-ob0-x22f.google.com [IPv6:2607:f8b0:4003:c01::22f]) (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 DD6A921F384; Sat, 9 May 2015 20:35:56 -0700 (PDT) Received: by obcus9 with SMTP id us9so50101550obc.2; Sat, 09 May 2015 20:35:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=rJrsS4hbQros0MuFdah+MUEzcLhqL6J1ZIQixyZjVUE=; b=xr+88Fe7ym0LY/CJG1M+ExIEP8GYpAjF2+iZo2LAl69K//lKB4Pw8HSGYsw9N7+f1g 8Ywk+JW3VMcqssZTIujXn2aUodEUjqcJFD9TFmeTsh81uuJqx7FqHM5MOhVuNgoOuV6D lXtdyhCOi+nL4DP4cvfpbT/mO/UPOFAz8mnL+vH5mAaD3fvpw/zRFA92aYvej7ah3CUX L8ShkpK6yKjSIiyodbAmsGWuPewjCJThoi3/5oUuFfA/zVpsa29uHh1GEbc8OD9Lhz9J mEe+AP4W6OzwWB04ekH3DgY5UBzB4xO1lvAw/OVTiFlCNk1Whx/3AOTB65Gna1JuQ512 ll3Q== MIME-Version: 1.0 X-Received: by 10.60.78.232 with SMTP id e8mr3716338oex.24.1431228955755; Sat, 09 May 2015 20:35:55 -0700 (PDT) Received: by 10.202.71.139 with HTTP; Sat, 9 May 2015 20:35:55 -0700 (PDT) In-Reply-To: References: Date: Sat, 9 May 2015 20:35:55 -0700 Message-ID: From: Dave Taht To: Jonathan Morton Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Cc: cake@lists.bufferbloat.net, "codel@lists.bufferbloat.net" , bloat Subject: Re: [Codel] [Cake] 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: Sun, 10 May 2015 03:36:26 -0000 On Sat, May 9, 2015 at 12:02 PM, Jonathan Morton wr= ote: >> The "right" amount of buffering is *1* packet, all the time (the goal is >> nearly 0 latency with 100% utilization). We are quite far from achieving >> that on anything... > > And control theory shows, I think, that we never will unless the mechanis= ms > available to us for signalling congestion improve. ECN is good, but it's = not > sufficient to achieve that ultimate goal. I'll try to explain why. The conex and dctcp work explored using ecn for multi-bit signalling. While this is a great set of analogies below (and why I am broadening the cc) there are two things missing from it. > > Aside from computer networking, I also dabble in computer simulated train= s. > Some of my bigger projects involve detailed simulations of what goes on > inside them, especially the older ones which are relatively simple. These > were built at a time when the idea of putting anything as delicate as a > transistor inside what was effectively a megawatt-class power station was > unthinkable, so the control gear tended to be electromechanical or even > electropneumatic. The control laws therefore tended to be the simplest on= es > they could get away with. > > The bulk of the generated power went into the main traction circuit, wher= e a > dedicated main generator is connected rather directly to the traction mot= ors > through a small amount of switchgear (mainly to reverse the fields on the > motors at either end off the line). Control of the megawatts of power > surging through this circuit was effected by varying the excitation of th= e > main generator. Excitation is in turn provided by shunting the auxiliary > voltage through an automatic rheostat known as the Load Regulator before = it > reaches the field winding of the generator. Without field current, the > generator produces no power. > > The load regulator is what I want to focus on here. Its job was to adjust > the output of the generator to match the power - more precisely the torqu= e - > that the engine was capable of producing (or, in English Electric locos a= t > least, the torque set by the driver's controls, which wasn't always the > maximum). The load regulator had a little electric motor to move it up an= d > down. A good proxy for engine torque was available in the form of the fue= l > rack position; the torque output of a diesel engine is closely related to > the amount of fuel injected per cycle. The fuel rack, of course, was > controlled by the governor which was set to maintain a particular engine > speed; a straightforward PI control problem solved by a reasonably simple > mechanical device. > > So it looks like a simple control problem; if the torque is too low, > increase the excitation, and vice versa. > > Congestion control looks like a simple problem too. If there is no > congestion, increase the amount of data in flight; if there is, reduce it= . > We even have Explicit Congestion Notification now to tell us that crucial > data point, but we could always infer it from dropped packets before. > > So what does the load regulator's control system look like? It has as man= y > as five states: fast down, slow down, hold, slow up, fast up. It turns ou= t > that trains really like changes in tractive effort to be slow and smooth, > and as infrequent as possible. So while a very simple "bang bang" control > scheme would be possible, it would inevitably oscillate around the set po= int > instead of settling on it. Introducing a central hold state allows it to > settle when cruising at constant speed, and the two slow states allow the > sort of fine adjustments needed as a train gradually accelerates or slows= , > putting the generator only slightly out of balance with the engine. The f= ast > states remain to allow for quick response to large changes - the driver > moves the throttle, or the motors abruptly reconfigure for a different sp= eed > range (the electrical equivalent of changing gear). > > On the Internet, we're firmly stuck with bang-bang control. As big an > improvement as ECN is, it still provides only one bit of information to t= he > sender: whether or not there was congestion reported during the last RTT. > Thus we can only use the "slow up" and "fast down" states of our virtual > load regulator (except for slow start, which ironically uses the "fast up= " > state), and we are doomed to oscillate around the ideal congestion window= , > never actually settling on it. > > Bufferbloat is fundamentally about having insufficient information at the > endpoints about conditions in the network. Well said. > We've done a lot to improve that, > by moving from zero information to one bit per RTT. But to achieve that h= oly > grail, we need more information still. context being aqm + ecn, fq, fq+aqm, fq+aqm+ecn, dctcp, conex, etc. > Specifically, we need to know when we're at the correct BDP, not just whe= n > it's too high. And it'd be nice if we also knew if we were close to it. B= ut > there is currently no way to provide that information from the network to > the endpoints. This is where I was pointing out that FQ and the behavior of multiple flows in their two phases (slow start and congestion avoidance) provides a few pieces of useful information that could possibly be used to get closer to the ideal. We know total service times for all active flows. We also have a separate calculable service time for "sparse flows" in two algorithms we understand deeply. We could have some grip on the history for flows that are not currently que= ued. We know that the way we currently seek new set points tend to be bursty ("chasing the inchworm" - I still gotta use that title on a paper!). New flows tend to be extremely bursty - and new flows in the real world also tend to be pretty short, with 95% of all web traffic fitting into a single IW10. If e2e we know we are being FQ=C2=B4d, and yet are bursting to find new setpoints we can infer from the spacing on the other endpoint what the contention really is. There was a stanford result for 10s of thousands of flows that found an ideal setpoint much lower than we are achieving for dozens, at much higher rates. A control theory-ish issue with codel is that it depends on an arbitrary ideal (5ms) as a definition for "good queue", where "a gooder queue" is, in my definition at the moment, "1 packet outstanding ever closer to 100% of the time while there is 100% utilization". We could continue to bang on things (reducing the target or other methods) and aim for a lower ideal setpoint until utilization dropped below 100%. Which becomes easier the more flows we know are in progress. > - Jonathan Morton > > > _______________________________________________ > Cake mailing list > Cake@lists.bufferbloat.net > https://lists.bufferbloat.net/listinfo/cake > --=20 Dave T=C3=A4ht Open Networking needs **Open Source Hardware** https://plus.google.com/u/0/+EricRaymond/posts/JqxCe2pFr67