blob: 8729895d9e081038cfd75bcd66f739ac02c58086 [file] [log] [blame]
// Copyright (c) 2016 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
// Implements Kathleen Nichols' algorithm for tracking the minimum (or maximum)
// estimate of a stream of samples over some fixed time interval. (E.g.,
// the minimum RTT over the past five minutes.) The algorithm keeps track of
// the best, second best, and third best min (or max) estimates, maintaining an
// invariant that the measurement time of the n'th best >= n-1'th best.
// The algorithm works as follows. On a reset, all three estimates are set to
// the same sample. The second best estimate is then recorded in the second
// quarter of the window, and a third best estimate is recorded in the second
// half of the window, bounding the worst case error when the true min is
// monotonically increasing (or true max is monotonically decreasing) over the
// window.
// A new best sample replaces all three estimates, since the new best is lower
// (or higher) than everything else in the window and it is the most recent.
// The window thus effectively gets reset on every new min. The same property
// holds true for second best and third best estimates. Specifically, when a
// sample arrives that is better than the second best but not better than the
// best, it replaces the second and third best estimates but not the best
// estimate. Similarly, a sample that is better than the third best estimate
// but not the other estimates replaces only the third best estimate.
// Finally, when the best expires, it is replaced by the second best, which in
// turn is replaced by the third best. The newest sample replaces the third
// best.
#include "net/third_party/quiche/src/quic/core/quic_time.h"
namespace quic {
// Compares two values and returns true if the first is less than or equal
// to the second.
template <class T>
struct MinFilter {
bool operator()(const T& lhs, const T& rhs) const { return lhs <= rhs; }
// Compares two values and returns true if the first is greater than or equal
// to the second.
template <class T>
struct MaxFilter {
bool operator()(const T& lhs, const T& rhs) const { return lhs >= rhs; }
// Use the following to construct a windowed filter object of type T.
// For example, a min filter using QuicTime as the time type:
// WindowedFilter<T, MinFilter<T>, QuicTime, QuicTime::Delta> ObjectName;
// A max filter using 64-bit integers as the time type:
// WindowedFilter<T, MaxFilter<T>, uint64_t, int64_t> ObjectName;
// Specifically, this template takes four arguments:
// 1. T -- type of the measurement that is being filtered.
// 2. Compare -- MinFilter<T> or MaxFilter<T>, depending on the type of filter
// desired.
// 3. TimeT -- the type used to represent timestamps.
// 4. TimeDeltaT -- the type used to represent continuous time intervals between
// two timestamps. Has to be the type of (a - b) if both |a| and |b| are
// of type TimeT.
template <class T, class Compare, typename TimeT, typename TimeDeltaT>
class WindowedFilter {
// |window_length| is the period after which a best estimate expires.
// |zero_value| is used as the uninitialized value for objects of T.
// Importantly, |zero_value| should be an invalid value for a true sample.
WindowedFilter(TimeDeltaT window_length, T zero_value, TimeT zero_time)
: window_length_(window_length),
estimates_{Sample(zero_value_, zero_time),
Sample(zero_value_, zero_time),
Sample(zero_value_, zero_time)} {}
// Changes the window length. Does not update any current samples.
void SetWindowLength(TimeDeltaT window_length) {
window_length_ = window_length;
// Updates best estimates with |sample|, and expires and updates best
// estimates as necessary.
void Update(T new_sample, TimeT new_time) {
// Reset all estimates if they have not yet been initialized, if new sample
// is a new best, or if the newest recorded estimate is too old.
if (estimates_[0].sample == zero_value_ ||
Compare()(new_sample, estimates_[0].sample) ||
new_time - estimates_[2].time > window_length_) {
Reset(new_sample, new_time);
if (Compare()(new_sample, estimates_[1].sample)) {
estimates_[1] = Sample(new_sample, new_time);
estimates_[2] = estimates_[1];
} else if (Compare()(new_sample, estimates_[2].sample)) {
estimates_[2] = Sample(new_sample, new_time);
// Expire and update estimates as necessary.
if (new_time - estimates_[0].time > window_length_) {
// The best estimate hasn't been updated for an entire window, so promote
// second and third best estimates.
estimates_[0] = estimates_[1];
estimates_[1] = estimates_[2];
estimates_[2] = Sample(new_sample, new_time);
// Need to iterate one more time. Check if the new best estimate is
// outside the window as well, since it may also have been recorded a
// long time ago. Don't need to iterate once more since we cover that
// case at the beginning of the method.
if (new_time - estimates_[0].time > window_length_) {
estimates_[0] = estimates_[1];
estimates_[1] = estimates_[2];
if (estimates_[1].sample == estimates_[0].sample &&
new_time - estimates_[1].time > window_length_ >> 2) {
// A quarter of the window has passed without a better sample, so the
// second-best estimate is taken from the second quarter of the window.
estimates_[2] = estimates_[1] = Sample(new_sample, new_time);
if (estimates_[2].sample == estimates_[1].sample &&
new_time - estimates_[2].time > window_length_ >> 1) {
// We've passed a half of the window without a better estimate, so take
// a third-best estimate from the second half of the window.
estimates_[2] = Sample(new_sample, new_time);
// Resets all estimates to new sample.
void Reset(T new_sample, TimeT new_time) {
estimates_[0] = estimates_[1] = estimates_[2] =
Sample(new_sample, new_time);
T GetBest() const { return estimates_[0].sample; }
T GetSecondBest() const { return estimates_[1].sample; }
T GetThirdBest() const { return estimates_[2].sample; }
struct Sample {
T sample;
TimeT time;
Sample(T init_sample, TimeT init_time)
: sample(init_sample), time(init_time) {}
TimeDeltaT window_length_; // Time length of window.
T zero_value_; // Uninitialized value of T.
Sample estimates_[3]; // Best estimate is element 0.
} // namespace quic