1 // Copyright (c) 2016 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef QUICHE_QUIC_CORE_CONGESTION_CONTROL_WINDOWED_FILTER_H_ 6 #define QUICHE_QUIC_CORE_CONGESTION_CONTROL_WINDOWED_FILTER_H_ 7 8 // Implements Kathleen Nichols' algorithm for tracking the minimum (or maximum) 9 // estimate of a stream of samples over some fixed time interval. (E.g., 10 // the minimum RTT over the past five minutes.) The algorithm keeps track of 11 // the best, second best, and third best min (or max) estimates, maintaining an 12 // invariant that the measurement time of the n'th best >= n-1'th best. 13 14 // The algorithm works as follows. On a reset, all three estimates are set to 15 // the same sample. The second best estimate is then recorded in the second 16 // quarter of the window, and a third best estimate is recorded in the second 17 // half of the window, bounding the worst case error when the true min is 18 // monotonically increasing (or true max is monotonically decreasing) over the 19 // window. 20 // 21 // A new best sample replaces all three estimates, since the new best is lower 22 // (or higher) than everything else in the window and it is the most recent. 23 // The window thus effectively gets reset on every new min. The same property 24 // holds true for second best and third best estimates. Specifically, when a 25 // sample arrives that is better than the second best but not better than the 26 // best, it replaces the second and third best estimates but not the best 27 // estimate. Similarly, a sample that is better than the third best estimate 28 // but not the other estimates replaces only the third best estimate. 29 // 30 // Finally, when the best expires, it is replaced by the second best, which in 31 // turn is replaced by the third best. The newest sample replaces the third 32 // best. 33 34 #include "quiche/quic/core/quic_time.h" 35 36 namespace quic { 37 38 // Compares two values and returns true if the first is less than or equal 39 // to the second. 40 template <class T> 41 struct QUICHE_EXPORT MinFilter { operatorMinFilter42 bool operator()(const T& lhs, const T& rhs) const { return lhs <= rhs; } 43 }; 44 45 // Compares two values and returns true if the first is greater than or equal 46 // to the second. 47 template <class T> 48 struct QUICHE_EXPORT MaxFilter { operatorMaxFilter49 bool operator()(const T& lhs, const T& rhs) const { return lhs >= rhs; } 50 }; 51 52 // Use the following to construct a windowed filter object of type T. 53 // For example, a min filter using QuicTime as the time type: 54 // WindowedFilter<T, MinFilter<T>, QuicTime, QuicTime::Delta> ObjectName; 55 // A max filter using 64-bit integers as the time type: 56 // WindowedFilter<T, MaxFilter<T>, uint64_t, int64_t> ObjectName; 57 // Specifically, this template takes four arguments: 58 // 1. T -- type of the measurement that is being filtered. 59 // 2. Compare -- MinFilter<T> or MaxFilter<T>, depending on the type of filter 60 // desired. 61 // 3. TimeT -- the type used to represent timestamps. 62 // 4. TimeDeltaT -- the type used to represent continuous time intervals between 63 // two timestamps. Has to be the type of (a - b) if both |a| and |b| are 64 // of type TimeT. 65 template <class T, class Compare, typename TimeT, typename TimeDeltaT> 66 class QUICHE_EXPORT WindowedFilter { 67 public: 68 // |window_length| is the period after which a best estimate expires. 69 // |zero_value| is used as the uninitialized value for objects of T. 70 // Importantly, |zero_value| should be an invalid value for a true sample. WindowedFilter(TimeDeltaT window_length,T zero_value,TimeT zero_time)71 WindowedFilter(TimeDeltaT window_length, T zero_value, TimeT zero_time) 72 : window_length_(window_length), 73 zero_value_(zero_value), 74 zero_time_(zero_time), 75 estimates_{Sample(zero_value_, zero_time), 76 Sample(zero_value_, zero_time), 77 Sample(zero_value_, zero_time)} {} 78 79 // Changes the window length. Does not update any current samples. SetWindowLength(TimeDeltaT window_length)80 void SetWindowLength(TimeDeltaT window_length) { 81 window_length_ = window_length; 82 } 83 84 // Updates best estimates with |sample|, and expires and updates best 85 // estimates as necessary. Update(T new_sample,TimeT new_time)86 void Update(T new_sample, TimeT new_time) { 87 // Reset all estimates if they have not yet been initialized, if new sample 88 // is a new best, or if the newest recorded estimate is too old. 89 if (estimates_[0].sample == zero_value_ || 90 Compare()(new_sample, estimates_[0].sample) || 91 new_time - estimates_[2].time > window_length_) { 92 Reset(new_sample, new_time); 93 return; 94 } 95 96 if (Compare()(new_sample, estimates_[1].sample)) { 97 estimates_[1] = Sample(new_sample, new_time); 98 estimates_[2] = estimates_[1]; 99 } else if (Compare()(new_sample, estimates_[2].sample)) { 100 estimates_[2] = Sample(new_sample, new_time); 101 } 102 103 // Expire and update estimates as necessary. 104 if (new_time - estimates_[0].time > window_length_) { 105 // The best estimate hasn't been updated for an entire window, so promote 106 // second and third best estimates. 107 estimates_[0] = estimates_[1]; 108 estimates_[1] = estimates_[2]; 109 estimates_[2] = Sample(new_sample, new_time); 110 // Need to iterate one more time. Check if the new best estimate is 111 // outside the window as well, since it may also have been recorded a 112 // long time ago. Don't need to iterate once more since we cover that 113 // case at the beginning of the method. 114 if (new_time - estimates_[0].time > window_length_) { 115 estimates_[0] = estimates_[1]; 116 estimates_[1] = estimates_[2]; 117 } 118 return; 119 } 120 if (estimates_[1].sample == estimates_[0].sample && 121 new_time - estimates_[1].time > window_length_ >> 2) { 122 // A quarter of the window has passed without a better sample, so the 123 // second-best estimate is taken from the second quarter of the window. 124 estimates_[2] = estimates_[1] = Sample(new_sample, new_time); 125 return; 126 } 127 128 if (estimates_[2].sample == estimates_[1].sample && 129 new_time - estimates_[2].time > window_length_ >> 1) { 130 // We've passed a half of the window without a better estimate, so take 131 // a third-best estimate from the second half of the window. 132 estimates_[2] = Sample(new_sample, new_time); 133 } 134 } 135 136 // Resets all estimates to new sample. Reset(T new_sample,TimeT new_time)137 void Reset(T new_sample, TimeT new_time) { 138 estimates_[0] = estimates_[1] = estimates_[2] = 139 Sample(new_sample, new_time); 140 } 141 Clear()142 void Clear() { Reset(zero_value_, zero_time_); } 143 GetBest()144 T GetBest() const { return estimates_[0].sample; } GetSecondBest()145 T GetSecondBest() const { return estimates_[1].sample; } GetThirdBest()146 T GetThirdBest() const { return estimates_[2].sample; } 147 148 private: 149 struct QUICHE_EXPORT Sample { 150 T sample; 151 TimeT time; SampleSample152 Sample(T init_sample, TimeT init_time) 153 : sample(init_sample), time(init_time) {} 154 }; 155 156 TimeDeltaT window_length_; // Time length of window. 157 T zero_value_; // Uninitialized value of T. 158 TimeT zero_time_; // Uninitialized value of TimeT. 159 Sample estimates_[3]; // Best estimate is element 0. 160 }; 161 162 } // namespace quic 163 164 #endif // QUICHE_QUIC_CORE_CONGESTION_CONTROL_WINDOWED_FILTER_H_ 165