From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-11-iad.dyndns.com (mxout-107-iad.mailhop.org [216.146.32.107]) by lists.bufferbloat.net (Postfix) with ESMTP id CF26B2E016E for ; Sat, 19 Feb 2011 17:59:14 -0800 (PST) Received: from scan-12-iad.mailhop.org (scan-12-iad.local [10.150.0.209]) by mail-11-iad.dyndns.com (Postfix) with ESMTP id CBCDA17163C for ; Sun, 20 Feb 2011 01:59:10 +0000 (UTC) X-Spam-Score: 0.1 () X-Mail-Handler: MailHop by DynDNS X-Originating-IP: 75.145.127.229 Received: from gw.co.teklibre.org (75-145-127-229-Colorado.hfc.comcastbusiness.net [75.145.127.229]) by mail-11-iad.dyndns.com (Postfix) with ESMTP id D27A917107A for ; Sun, 20 Feb 2011 01:59:03 +0000 (UTC) Received: from cruithne.co.teklibre.org (unknown [IPv6:2002:4b91:7fe5:2:21c:25ff:fe80:46f9]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "cruithne.co.teklibre.org", Issuer "CA Cert Signing Authority" (verified OK)) by gw.co.teklibre.org (Postfix) with ESMTPS id 198AC5F074 for ; Sat, 19 Feb 2011 18:59:03 -0700 (MST) Received: by cruithne.co.teklibre.org (Postfix, from userid 1000) id 0C671122005; Sat, 19 Feb 2011 18:59:01 -0700 (MST) From: d@taht.net (Dave =?utf-8?Q?T=C3=A4ht?=) To: bloat-devel@lists.bufferbloat.net Subject: Re: [RFC v2] mac80211: implement eBDP algorithm to fight bufferbloat Organization: Teklibre - http://www.teklibre.com References: Date: Sat, 19 Feb 2011 18:59:01 -0700 In-Reply-To: (unknown's message of "Tue, 15 Feb 2011 23:17:07 +0100") Message-ID: <87pqqnzct6.fsf@cruithne.co.teklibre.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-BeenThere: bloat-devel@lists.bufferbloat.net X-Mailman-Version: 2.1.13 Precedence: list List-Id: "Developers working on AQM, device drivers, and networking stacks" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 20 Feb 2011 01:59:15 -0000 >Should we be somehow filtering out and ignoring the packets that get >dropped, when we're calculating the average packet transmission rate? >Presumably they're getting dropped almost instantly, so they don't >really take up queue space and they have abnormally fast transmission >times, which will tend to cause us to overestimate max_enqueued? They >should be rare, though, at least. (And presumably we *should* include >packets that get dropped because their retry timer ran out, since they >were sitting in the queue for that long.) Possibly we should just >ignore any packet that was handled in less than, oh, say, a few >microseconds? Perhaps doing continuous mean variance against time would be simpler than what you propose. Sorry, LISP example, with latex: unknown writes: > A friend showed me this about 15 years ago. I use it every time I need to > calculate the variance of some data set. I always forget the exact detail= s and > have to derive it again. But, it=E2=80=99s easy enough to derive that it= =E2=80=99s never a > problem. > > I had to derive it again on Friday and thought, `I should make sure more = people > get this tool into their utility belts'. > > First, a quick refresher on what we=E2=80=99re talking about here. The me= an \mu of a > data set { x_1, x_2, \ldots, x_n } is defined to be \frac{1}{n} \sum_{i= =3D1}^n > x_i. The variance \sigma^2 is defined to be \frac{1}{n} \sum_{i=3D1}^n (x= _i - \ > mu)^2. > > A na=C3=AFve approach to calculating the variance then goes something lik= e this: > > (defun mean-variance (data) > (flet ((square (x) (* x x))) > (let* ((n (length data)) > (sum (reduce #'+ data :initial-value 0)) > (mu (/ sum n)) > (vv (reduce #'(lambda (accum xi) > (+ accum (square (- xi mu)))) > data :initial-value 0))) > (values mu (/ vv n))))) > > This code runs through the data list once to count the items, once to cal= culate > the mean, and once to calculate the variance. It is easy to see how we co= uld > count the items at the same time we are summing them. It is not as obviou= s how > we can calculate the sum of squared terms involving the mean until we=E2= =80=99ve > calculated the mean. > > If we expand the squared term and pull the constant \mu outside of the > summations it ends up in, we find that: > \frac{\sum (x_i - \mu)^2}{n} =3D \frac{\sum x_i^2}{n} - 2 \mu \frac{\sum = x_i}{n} > + \mu^2 \frac{\sum 1}{n} > > When we recognize that \frac{\sum x_i}{n} =3D \mu and \sum_{i=3D1}^n 1 = =3D n, we get: > \sigma^2 =3D \frac{\sum x_i^2}{n} - \mu^2 =3D \frac{\sum x_i^2}{n} - \lef= t( \frac{\ > sum x_i}{n} \right)^2 > . > > This leads to the following code: > > (defun mean-variance (data) > (flet ((square (x) (* x x))) > (destructuring-bind (n xs x2s) > (reduce #'(lambda (accum xi) > (list (1+ (first accum)) > (+ (second accum) xi) > (+ (third accum) (square xi)))) > data :initial-value '(0 0 0)) > (let ((mu (/ xs n))) > (values mu (- (/ x2s n) (square mu))))))) > > The code is not as simple, but you gain a great deal of flexibility. You = can > easily convert the above concept to continuously track the mean and varia= nce as > you iterate through an input stream. You do not have to keep data around = to > iterate through later. You can deal with things one sample at a time. > > The same concept extends to higher-order moments, too. > > Happy counting. > > Link --=20 Dave Taht http://nex-6.taht.net