A Discrete-Event Network Simulator
API
windowed-filter.h
Go to the documentation of this file.
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 {
72 template <class T>
73 struct MinFilter
74 {
75 public:
83  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 };
96 template <class T>
97 struct MaxFilter
98 {
99 public:
107  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 };
132 template <class T, class Compare, typename TimeT, typename TimeDeltaT>
134 {
135 public:
140  {
141  }
142 
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  } {}
163  void SetWindowLength (TimeDeltaT windowLength)
164  {
165  m_windowLength = windowLength;
166  }
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 
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 
244  T GetBest () const
245  {
246  return m_samples[0].sample;
247  }
248 
253  T GetSecondBest () const
254  {
255  return m_samples[1].sample;
256  }
257 
262  T GetThirdBest () const
263  {
264  return m_samples[2].sample;
265  }
266 
270  struct Sample
271  {
272  T sample;
273  TimeT time;
274 
278  {
279  }
280 
286  Sample (T init_sample, TimeT init_time)
287  : sample (init_sample),
288  time (init_time)
289  {
290  }
291  };
292 
293  TimeDeltaT m_windowLength;
295  Sample m_samples[3];
296 };
297 
298 } // namespace ns3
299 #endif // WINDOWED_FILTER_H_
Compares two values.
T GetBest() const
Returns Max/Min value so far among the windowed samples.
void Update(T new_sample, TimeT new_time)
Updates best estimates with |sample|, and expires and updates best estimates as necessary.
WindowedFilter(TimeDeltaT windowLength, T zeroValue, TimeT zeroTime)
contructor
T GetThirdBest() const
Returns third Max/Min value so far among the windowed samples.
TimeT time
time when the sample was recorded.
T m_zeroValue
Uninitialized value of T.
Construct a windowed filter.
bool operator()(const T &lhs, const T &rhs) const
Compares two values.
WindowedFilter()
contructor
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Compares two values.
T GetSecondBest() const
Returns second Max/Min value so far among the windowed samples.
Sample m_samples[3]
Best estimate is element 0.
Sample(T init_sample, TimeT init_time)
constructor
TimeDeltaT m_windowLength
Time length of window.
bool operator()(const T &lhs, const T &rhs) const
Compares two values.
void SetWindowLength(TimeDeltaT windowLength)
Changes the window length.
void Reset(T new_sample, TimeT new_time)
Resets all estimates to new sample.