1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ 2 /* 3 * Copyright (c) 2016 The Chromium Authors. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * * Redistributions in binary form must reproduce the above 12 * copyright notice, this list of conditions and the following disclaimer 13 * in the documentation and/or other materials provided with the 14 * distribution. 15 * * Neither the name of Google Inc. nor the names of its 16 * contributors may be used to endorse or promote products derived from 17 * this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 /* 33 * Note: This code is modified to work under ns-3's environment. 34 * Modified by: Vivek Jain <jain.vivek.anand@gmail.com> 35 * Viyom Mittal <viyommittal@gmail.com> 36 * Mohit P. Tahiliani <tahiliani@nitk.edu.in> 37 */ 38 39 // Implements Kathleen Nichols' algorithm for tracking the minimum (or maximum) 40 // estimate of a stream of samples over some fixed time interval. (E.g., 41 // the minimum RTT over the past five minutes.) The algorithm keeps track of 42 // the best, second best, and third best min (or max) estimates, maintaining an 43 // invariant that the measurement time of the n'th best >= n-1'th best. 44 // The algorithm works as follows. On a reset, all three estimates are set to 45 // the same sample. The second best estimate is then recorded in the second 46 // quarter of the window, and a third best estimate is recorded in the second 47 // half of the window, bounding the worst case error when the true min is 48 // monotonically increasing (or true max is monotonically decreasing) over the 49 // window. 50 // 51 // A new best sample replaces all three estimates, since the new best is lower 52 // (or higher) than everything else in the window and it is the most recent. 53 // The window thus effectively gets reset on every new min. The same property 54 // holds true for second best and third best estimates. Specifically, when a 55 // sample arrives that is better than the second best but not better than the 56 // best, it replaces the second and third best estimates but not the best 57 // estimate. Similarly, a sample that is better than the third best estimate 58 // but not the other estimates replaces only the third best estimate. 59 // 60 // Finally, when the best expires, it is replaced by the second best, which in 61 // turn is replaced by the third best. The newest sample replaces the third 62 // best. 63 64 #ifndef WINDOWED_FILTER_H_ 65 #define WINDOWED_FILTER_H_ 66 67 namespace ns3 { 68 /** 69 * \brief Compares two values 70 * \param T type of the measurement that is being filtered. 71 */ 72 template <class T> 73 struct MinFilter 74 { 75 public: 76 /** 77 * \brief Compares two values 78 * 79 * \param lhs left hand value 80 * \param rhs right hand value 81 * \return returns true if the first is less than or equal to the second. 82 */ operatorMinFilter83 bool operator() (const T& lhs, const T& rhs) const 84 { 85 if (rhs == 0 || lhs == 0) 86 { 87 return false; 88 } 89 return lhs <= rhs; 90 } 91 }; 92 /** 93 * \brief Compares two values 94 * \param T type of the measurement that is being filtered. 95 */ 96 template <class T> 97 struct MaxFilter 98 { 99 public: 100 /** 101 * \brief Compares two values 102 * 103 * \param lhs left hand value 104 * \param rhs right hand value 105 * \return returns true if the first is greater than or equal to the second. 106 */ operatorMaxFilter107 bool operator() (const T& lhs, const T& rhs) const 108 { 109 if (rhs == 0 || lhs == 0) 110 { 111 return false; 112 } 113 return lhs >= rhs; 114 } 115 }; 116 /** 117 * \brief Construct a windowed filter 118 * 119 * Use the following to construct a windowed filter object of type T. 120 * For example, a min filter using QuicTime as the time type: 121 * WindowedFilter<T, MinFilter<T>, QuicTime, QuicTime::Delta> ObjectName; 122 * max filter using 64-bit integers as the time type: 123 * WindowedFilter<T, MaxFilter<T>, uint64_t, int64_t> ObjectName; 124 * 125 * \param T -- type of the measurement that is being filtered. 126 * \param Compare -- MinFilter<T> or MaxFilter<T>, depending on the type of filter desired. 127 * \param TimeT -- the type used to represent timestamps. 128 * \param TimeDeltaT -- the type used to represent continuous time intervals between 129 * two timestamps. Has to be the type of (a - b) if both |a| and |b| are 130 * of type TimeT. 131 */ 132 template <class T, class Compare, typename TimeT, typename TimeDeltaT> 133 class WindowedFilter 134 { 135 public: 136 /** 137 * \brief contructor 138 */ WindowedFilter()139 WindowedFilter () 140 { 141 } 142 143 /** 144 * \brief contructor 145 * \param windowLength is the period after which a best estimate expires. 146 * \param zeroValue is used as the uninitialized value for objects of T. Importantly, 147 * zeroValue should be an invalid value for a true sample. 148 * \param zeroTime is the time of instance record time. 149 */ WindowedFilter(TimeDeltaT windowLength,T zeroValue,TimeT zeroTime)150 WindowedFilter (TimeDeltaT windowLength, T zeroValue, TimeT zeroTime) 151 : m_windowLength (windowLength), 152 m_zeroValue (zeroValue), 153 m_samples 154 { 155 Sample (m_zeroValue, zeroTime), 156 Sample (m_zeroValue, zeroTime), 157 Sample (m_zeroValue, zeroTime) 158 } {} 159 /** 160 * \brief Changes the window length. Does not update any current samples. 161 * \param windowLength is the period after which a best estimate expires. 162 */ SetWindowLength(TimeDeltaT windowLength)163 void SetWindowLength (TimeDeltaT windowLength) 164 { 165 m_windowLength = windowLength; 166 } 167 /** 168 * \brief Updates best estimates with |sample|, and expires and updates best 169 * estimates as necessary. 170 * 171 * \param new_sample update new sample. 172 * \param new_time record time of the new sample. 173 */ Update(T new_sample,TimeT new_time)174 void Update (T new_sample, TimeT new_time) 175 { 176 // Reset all estimates if they have not yet been initialized, if new sample 177 // is a new best, or if the newest recorded estimate is too old. 178 if (m_samples[0].sample == m_zeroValue 179 || Compare () (new_sample, m_samples[0].sample) 180 || new_time - m_samples[2].time > m_windowLength) 181 { 182 Reset (new_sample, new_time); 183 return; 184 } 185 if (Compare () (new_sample, m_samples[1].sample)) 186 { 187 m_samples[1] = Sample (new_sample, new_time); 188 m_samples[2] = m_samples[1]; 189 } 190 else if (Compare () (new_sample, m_samples[2].sample)) 191 { 192 m_samples[2] = Sample (new_sample, new_time); 193 } 194 // Expire and update estimates as necessary. 195 if (new_time - m_samples[0].time > m_windowLength) 196 { 197 // The best estimate hasn't been updated for an entire window, so promote 198 // second and third best estimates. 199 m_samples[0] = m_samples[1]; 200 m_samples[1] = m_samples[2]; 201 m_samples[2] = Sample (new_sample, new_time); 202 // Need to iterate one more time. Check if the new best estimate is 203 // outside the window as well, since it may also have been recorded a 204 // long time ago. Don't need to iterate once more since we cover that 205 // case at the beginning of the method. 206 if (new_time - m_samples[0].time > m_windowLength) 207 { 208 m_samples[0] = m_samples[1]; 209 m_samples[1] = m_samples[2]; 210 } 211 return; 212 } 213 if (m_samples[1].sample == m_samples[0].sample 214 && new_time - m_samples[1].time > m_windowLength >> 2) 215 { 216 // A quarter of the window has passed without a better sample, so the 217 // second-best estimate is taken from the second quarter of the window. 218 m_samples[2] = m_samples[1] = Sample (new_sample, new_time); 219 return; 220 } 221 if (m_samples[2].sample == m_samples[1].sample 222 && new_time - m_samples[2].time > m_windowLength >> 1) 223 { 224 // We've passed a half of the window without a better estimate, so take 225 // a third-best estimate from the second half of the window. 226 m_samples[2] = Sample (new_sample, new_time); 227 } 228 } 229 230 /** 231 * \brief Resets all estimates to new sample. 232 * \param new_sample update new sample. 233 * \param new_time record time of the new sample. 234 */ Reset(T new_sample,TimeT new_time)235 void Reset (T new_sample, TimeT new_time) 236 { 237 m_samples[0] = m_samples[1] = m_samples[2] = Sample (new_sample, new_time); 238 } 239 240 /** 241 * \brief Returns Max/Min value so far among the windowed samples. 242 * \return returns Best (max/min) value so far among the windowed samples. 243 */ GetBest()244 T GetBest () const 245 { 246 return m_samples[0].sample; 247 } 248 249 /** 250 * \brief Returns second Max/Min value so far among the windowed samples. 251 * \return returns second Best (max/min) value so far among the windowed samples. 252 */ GetSecondBest()253 T GetSecondBest () const 254 { 255 return m_samples[1].sample; 256 } 257 258 /** 259 * \brief Returns third Max/Min value so far among the windowed samples. 260 * \return returns third Best (max/min) value so far among the windowed samples. 261 */ GetThirdBest()262 T GetThirdBest () const 263 { 264 return m_samples[2].sample; 265 } 266 267 /** 268 * \brief sample. 269 */ 270 struct Sample 271 { 272 T sample; //!< recorded sample. 273 TimeT time; //!< time when the sample was recorded. 274 /** 275 * \brief constructor 276 */ SampleSample277 Sample () 278 { 279 } 280 281 /** 282 * \brief constructor 283 * \param init_sample value of sample. 284 * \param init_time time when the sample was recorded.. 285 */ SampleSample286 Sample (T init_sample, TimeT init_time) 287 : sample (init_sample), 288 time (init_time) 289 { 290 } 291 }; 292 293 TimeDeltaT m_windowLength; //!< Time length of window. 294 T m_zeroValue; //!< Uninitialized value of T. 295 Sample m_samples[3]; //!< Best estimate is element 0. 296 }; 297 298 } // namespace ns3 299 #endif // WINDOWED_FILTER_H_ 300