From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-we0-f171.google.com (mail-we0-f171.google.com [74.125.82.171]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority" (verified OK)) by huchra.bufferbloat.net (Postfix) with ESMTPS id 753E621F091; Wed, 9 May 2012 20:24:57 -0700 (PDT) Received: by wejx9 with SMTP id x9so1225653wej.16 for ; Wed, 09 May 2012 20:24:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:content-type:content-transfer-encoding:subject:date:message-id :cc:to:mime-version:x-mailer; bh=5RdLcQui7ElumhowEtDd/3K42Ul23yGBoxE/bomh2Aw=; b=v1UT5CzBf93MU3b3BmRK/CLcC4Q2yOTCc3xfGygBV/bzI/xT+OKpeefxLGfQw3NH5G 9r1mF/7zMpiL/BW9BA/DtPn2+5C1MLAxMWipf0FVBpuOXAw+f27PZk7BlyIDQ9gYsc9Q zQLWQTp9uC2pcXFe1/9GTHcNqA8VHPrc4eMzAqt+PW4SdAnQMekP3f7t0tJwhaA6tGR9 j/pwoDMlZlG3lFVJY85/yzxUrrXqdy9JU+Xele3uIOKMDG83NFQTfud+NmXteva0CJ8y 5fwzb9a9gezG7SgChOP/71qQywUYLateVy6NBszJ2ByHFif/neGJJ4e6tcstNkHmqsw+ 47nA== Received: by 10.216.136.100 with SMTP id v78mr1367989wei.88.1336620295520; Wed, 09 May 2012 20:24:55 -0700 (PDT) Received: from [192.168.1.4] (xdsl-83-150-84-172.nebulazone.fi. [83.150.84.172]) by mx.google.com with ESMTPS id j3sm416830wiw.1.2012.05.09.20.24.54 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 09 May 2012 20:24:54 -0700 (PDT) From: Jonathan Morton Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: quoted-printable Date: Thu, 10 May 2012 06:24:52 +0300 Message-Id: To: codel@lists.bufferbloat.net Mime-Version: 1.0 (Apple Message framework v1084) X-Mailer: Apple Mail (2.1084) Cc: bloat Mainlinglist Subject: [Codel] The Inverse Square Root control law 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: Thu, 10 May 2012 03:24:58 -0000 I said just now: > Now about the inverse sqrt: qualitatively, it is just a convenient = method of gradually varying the mark/drop rate in terms of a time = interval rather than a packet count interval. The longer the queue = remains overfull - controlled by the number of mark/drop events that = have occurred - the higher the marking/dropping rate gets. If the queue = then empties (and stays empty-ish for a few RTTs), the rate is reset. = Meanwhile, if the queue regularly oscillates between "full" and "empty" = states, the marking/dropping rate is remembered so that aggressive TCPs = receive the correct magnitude signal. >=20 > Now as for the *quantitative* reason behind it, it is because as the = interval between drops gets shorter, the number of increments per RTT = goes up because there is one increment per drop. If the interval is = shortened linearly per increment, that means it will in practice shorten = exponentially faster, such that the drop rate runs away faster than the = TCP can reasonably be expected to respond. This would result in = excessive drop rates and oscillatory behaviour typical of an = over-sensitive control system. By basing the drop rate on the square = root of the incremented variable, the runaway behaviour is curtailed = since the drop interval now shortens linearly per RTT. >=20 > Maybe a diagram or animation would help to clarify that last = paragraph. I'm fairly sure I can draw one. Well, here's the diagram. I produced it by simulating the first 200 or = so drop events under each control law in a spreadsheet. http://dl.dropbox.com/u/60111136/InverseSqrt.pdf The exponential behaviour of the "linear" control law is immediately = apparent - it is clearly out of control within the first half-second, = and triples the drop rate again within the following nominal RTT - as is = the linear and much gentler behaviour of the "isqrt" control law = actually implemented. - Jonathan Morton