lib/win_minmax: windowed min or max estimator
authorNeal Cardwell <ncardwell@google.com>
Tue, 20 Sep 2016 03:39:09 +0000 (23:39 -0400)
committerDavid S. Miller <davem@davemloft.net>
Wed, 21 Sep 2016 04:22:59 +0000 (00:22 -0400)
commita4f1f9ac8153e22869b6408832b5a9bb9c762bf6
treed1db0c9b204eeca86084b17e394c6174d05cf4d9
parentf78e73e27fdeab6f9317667f7e9676b59c1ec1fb
lib/win_minmax: windowed min or max estimator

This commit introduces a generic library to estimate either the min or
max value of a time-varying variable over a recent time window. This
is code originally from Kathleen Nichols. The current form of the code
is from Van Jacobson.

A single struct minmax_sample will track the estimated windowed-max
value of the series if you call minmax_running_max() or the estimated
windowed-min value of the series if you call minmax_running_min().

Nearly equivalent code is already in place for minimum RTT estimation
in the TCP stack. This commit extracts that code and generalizes it to
handle both min and max. Moving the code here reduces the footprint
and complexity of the TCP code base and makes the filter generally
available for other parts of the codebase, including an upcoming TCP
congestion control module.

This library works well for time series where the measurements are
smoothly increasing or decreasing.

Signed-off-by: Van Jacobson <vanj@google.com>
Signed-off-by: Neal Cardwell <ncardwell@google.com>
Signed-off-by: Yuchung Cheng <ycheng@google.com>
Signed-off-by: Nandita Dukkipati <nanditad@google.com>
Signed-off-by: Eric Dumazet <edumazet@google.com>
Signed-off-by: Soheil Hassas Yeganeh <soheil@google.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
include/linux/win_minmax.h [new file with mode: 0644]
lib/Makefile
lib/win_minmax.c [new file with mode: 0644]