windowed_filter.h | Explore in Territory

// 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.

#ifndef QUICHE_QUIC_CORE_CONGESTION_CONTROL_WINDOWED_FILTER_H_
#define QUICHE_QUIC_CORE_CONGESTION_CONTROL_WINDOWED_FILTER_H_

// 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 "quiche/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 QUICHE_EXPORT MinFilter { … };

// Compares two values and returns true if the first is greater than or equal
// to the second.
template <class T>
struct QUICHE_EXPORT MaxFilter { … };

// 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 QUICHE_EXPORT WindowedFilter { … };

}  // namespace quic

#endif  // QUICHE_QUIC_CORE_CONGESTION_CONTROL_WINDOWED_FILTER_H_
chromium/net/third_party/quiche/src/quiche/quic/core/congestion_control/windowed_filter.h
