[RFC v2] mac80211: implement eBDP algorithm to fight bufferbloat

[Dave Täht]

>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