A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
windowed-filter.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2016 The Chromium Authors. All rights reserved.
3 *
4 * SPDX-License-Identifier: BSD-3-Clause
5 */
6
7/*
8 * Note: This code is modified to work under ns-3's environment.
9 * Modified by: Vivek Jain <jain.vivek.anand@gmail.com>
10 * Viyom Mittal <viyommittal@gmail.com>
11 * Mohit P. Tahiliani <tahiliani@nitk.edu.in>
12 */
13
14// Implements Kathleen Nichols' algorithm for tracking the minimum (or maximum)
15// estimate of a stream of samples over some fixed time interval. (E.g.,
16// the minimum RTT over the past five minutes.) The algorithm keeps track of
17// the best, second best, and third best min (or max) estimates, maintaining an
18// invariant that the measurement time of the n'th best >= n-1'th best.
19// The algorithm works as follows. On a reset, all three estimates are set to
20// the same sample. The second best estimate is then recorded in the second
21// quarter of the window, and a third best estimate is recorded in the second
22// half of the window, bounding the worst case error when the true min is
23// monotonically increasing (or true max is monotonically decreasing) over the
24// window.
25//
26// A new best sample replaces all three estimates, since the new best is lower
27// (or higher) than everything else in the window and it is the most recent.
28// The window thus effectively gets reset on every new min. The same property
29// holds true for second best and third best estimates. Specifically, when a
30// sample arrives that is better than the second best but not better than the
31// best, it replaces the second and third best estimates but not the best
32// estimate. Similarly, a sample that is better than the third best estimate
33// but not the other estimates replaces only the third best estimate.
34//
35// Finally, when the best expires, it is replaced by the second best, which in
36// turn is replaced by the third best. The newest sample replaces the third
37// best.
38
39#ifndef WINDOWED_FILTER_H_
40#define WINDOWED_FILTER_H_
41
42namespace ns3
43{
44/**
45 * \brief Compares two values
46 * \param T type of the measurement that is being filtered.
47 */
48template <class T>
50{
51 public:
52 /**
53 * \brief Compares two values
54 *
55 * \param lhs left hand value
56 * \param rhs right hand value
57 * \return returns true if the first is less than or equal to the second.
58 */
59 bool operator()(const T& lhs, const T& rhs) const
60 {
61 if (rhs == 0 || lhs == 0)
62 {
63 return false;
64 }
65 return lhs <= rhs;
66 }
67};
68
69/**
70 * \brief Compares two values
71 * \param T type of the measurement that is being filtered.
72 */
73template <class T>
75{
76 public:
77 /**
78 * \brief Compares two values
79 *
80 * \param lhs left hand value
81 * \param rhs right hand value
82 * \return returns true if the first is greater than or equal to the second.
83 */
84 bool operator()(const T& lhs, const T& rhs) const
85 {
86 if (rhs == 0 || lhs == 0)
87 {
88 return false;
89 }
90 return lhs >= rhs;
91 }
92};
93
94/**
95 * \brief Construct a windowed filter
96 *
97 * Use the following to construct a windowed filter object of type T.
98 * For example, a min filter using QuicTime as the time type:
99 * WindowedFilter<T, MinFilter<T>, QuicTime, QuicTime::Delta> ObjectName;
100 * max filter using 64-bit integers as the time type:
101 * WindowedFilter<T, MaxFilter<T>, uint64_t, int64_t> ObjectName;
102 *
103 * \param T -- type of the measurement that is being filtered.
104 * \param Compare -- MinFilter<T> or MaxFilter<T>, depending on the type of filter desired.
105 * \param TimeT -- the type used to represent timestamps.
106 * \param TimeDeltaT -- the type used to represent continuous time intervals between
107 * two timestamps. Has to be the type of (a - b) if both |a| and |b| are
108 * of type TimeT.
109 */
110template <class T, class Compare, typename TimeT, typename TimeDeltaT>
112{
113 public:
114 /**
115 * \brief constructor
116 */
118 {
119 }
120
121 /**
122 * \brief constructor
123 * \param windowLength is the period after which a best estimate expires.
124 * \param zeroValue is used as the uninitialized value for objects of T. Importantly,
125 * zeroValue should be an invalid value for a true sample.
126 * \param zeroTime is the time of instance record time.
127 */
128 WindowedFilter(TimeDeltaT windowLength, T zeroValue, TimeT zeroTime)
129 : m_windowLength(windowLength),
130 m_zeroValue(zeroValue),
131 m_samples{Sample(m_zeroValue, zeroTime),
132 Sample(m_zeroValue, zeroTime),
133 Sample(m_zeroValue, zeroTime)}
134 {
135 }
136
137 /**
138 * \brief Changes the window length. Does not update any current samples.
139 * \param windowLength is the period after which a best estimate expires.
140 */
141 void SetWindowLength(TimeDeltaT windowLength)
142 {
143 m_windowLength = windowLength;
144 }
145
146 /**
147 * \brief Updates best estimates with |sample|, and expires and updates best
148 * estimates as necessary.
149 *
150 * \param new_sample update new sample.
151 * \param new_time record time of the new sample.
152 */
153 void Update(T new_sample, TimeT new_time)
154 {
155 // Reset all estimates if they have not yet been initialized, if new sample
156 // is a new best, or if the newest recorded estimate is too old.
157 if (m_samples[0].sample == m_zeroValue || Compare()(new_sample, m_samples[0].sample) ||
158 new_time - m_samples[2].time > m_windowLength)
159 {
160 Reset(new_sample, new_time);
161 return;
162 }
163 if (Compare()(new_sample, m_samples[1].sample))
164 {
165 m_samples[1] = Sample(new_sample, new_time);
166 m_samples[2] = m_samples[1];
167 }
168 else if (Compare()(new_sample, m_samples[2].sample))
169 {
170 m_samples[2] = Sample(new_sample, new_time);
171 }
172 // Expire and update estimates as necessary.
173 if (new_time - m_samples[0].time > m_windowLength)
174 {
175 // The best estimate hasn't been updated for an entire window, so promote
176 // second and third best estimates.
177 m_samples[0] = m_samples[1];
178 m_samples[1] = m_samples[2];
179 m_samples[2] = Sample(new_sample, new_time);
180 // Need to iterate one more time. Check if the new best estimate is
181 // outside the window as well, since it may also have been recorded a
182 // long time ago. Don't need to iterate once more since we cover that
183 // case at the beginning of the method.
184 if (new_time - m_samples[0].time > m_windowLength)
185 {
186 m_samples[0] = m_samples[1];
187 m_samples[1] = m_samples[2];
188 }
189 return;
190 }
191 if (m_samples[1].sample == m_samples[0].sample &&
192 new_time - m_samples[1].time > m_windowLength >> 2)
193 {
194 // A quarter of the window has passed without a better sample, so the
195 // second-best estimate is taken from the second quarter of the window.
196 m_samples[2] = m_samples[1] = Sample(new_sample, new_time);
197 return;
198 }
199 if (m_samples[2].sample == m_samples[1].sample &&
200 new_time - m_samples[2].time > m_windowLength >> 1)
201 {
202 // We've passed a half of the window without a better estimate, so take
203 // a third-best estimate from the second half of the window.
204 m_samples[2] = Sample(new_sample, new_time);
205 }
206 }
207
208 /**
209 * \brief Resets all estimates to new sample.
210 * \param new_sample update new sample.
211 * \param new_time record time of the new sample.
212 */
213 void Reset(T new_sample, TimeT new_time)
214 {
215 m_samples[0] = m_samples[1] = m_samples[2] = Sample(new_sample, new_time);
216 }
217
218 /**
219 * \brief Returns Max/Min value so far among the windowed samples.
220 * \return returns Best (max/min) value so far among the windowed samples.
221 */
222 T GetBest() const
223 {
224 return m_samples[0].sample;
225 }
226
227 /**
228 * \brief Returns second Max/Min value so far among the windowed samples.
229 * \return returns second Best (max/min) value so far among the windowed samples.
230 */
232 {
233 return m_samples[1].sample;
234 }
235
236 /**
237 * \brief Returns third Max/Min value so far among the windowed samples.
238 * \return returns third Best (max/min) value so far among the windowed samples.
239 */
240 T GetThirdBest() const
241 {
242 return m_samples[2].sample;
243 }
244
245 /**
246 * \brief sample.
247 */
248 struct Sample
249 {
250 T sample; //!< recorded sample.
251 TimeT time; //!< time when the sample was recorded.
252
253 /**
254 * \brief constructor
255 */
257 {
258 }
259
260 /**
261 * \brief constructor
262 * \param init_sample value of sample.
263 * \param init_time time when the sample was recorded..
264 */
265 Sample(T init_sample, TimeT init_time)
266 : sample(init_sample),
267 time(init_time)
268 {
269 }
270 };
271
272 TimeDeltaT m_windowLength; //!< Time length of window.
273 T m_zeroValue; //!< Uninitialized value of T.
274 Sample m_samples[3]; //!< Best estimate is element 0.
275};
276
277} // namespace ns3
278#endif // WINDOWED_FILTER_H_
Construct a windowed filter.
WindowedFilter(TimeDeltaT windowLength, T zeroValue, TimeT zeroTime)
constructor
void Update(T new_sample, TimeT new_time)
Updates best estimates with |sample|, and expires and updates best estimates as necessary.
T GetSecondBest() const
Returns second Max/Min value so far among the windowed samples.
WindowedFilter()
constructor
Sample m_samples[3]
Best estimate is element 0.
T m_zeroValue
Uninitialized value of T.
TimeDeltaT m_windowLength
Time length of window.
T GetBest() const
Returns Max/Min value so far among the windowed samples.
T GetThirdBest() const
Returns third Max/Min value so far among the windowed samples.
void SetWindowLength(TimeDeltaT windowLength)
Changes the window length.
void Reset(T new_sample, TimeT new_time)
Resets all estimates to new sample.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Compares two values.
bool operator()(const T &lhs, const T &rhs) const
Compares two values.
Compares two values.
bool operator()(const T &lhs, const T &rhs) const
Compares two values.
Sample(T init_sample, TimeT init_time)
constructor
TimeT time
time when the sample was recorded.