[RFC v2] mac80211: implement eBDP algorithm to fight bufferbloat
Dave Täht
d at taht.net
Sat Feb 19 20:59:01 EST 2011
>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 <post at gwene.org> 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 details and
> have to derive it again. But, it’s easy enough to derive that it’s 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’re talking about here. The mean \mu of a
> data set { x_1, x_2, \ldots, x_n } is defined to be \frac{1}{n} \sum_{i=1}^n
> x_i. The variance \sigma^2 is defined to be \frac{1}{n} \sum_{i=1}^n (x_i - \
> mu)^2.
>
> A naïve approach to calculating the variance then goes something like 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 calculate
> the mean, and once to calculate the variance. It is easy to see how we could
> count the items at the same time we are summing them. It is not as obvious how
> we can calculate the sum of squared terms involving the mean until we’ve
> 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} = \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} = \mu and \sum_{i=1}^n 1 = n, we get:
> \sigma^2 = \frac{\sum x_i^2}{n} - \mu^2 = \frac{\sum x_i^2}{n} - \left( \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 variance 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
--
Dave Taht
http://nex-6.taht.net
More information about the Bloat-devel
mailing list