A Discrete-Event Network Simulator
Home
Tutorials ▼
English
Documentation ▼
Installation
Manual
Models
Contributing
Wiki
Development ▼
API Docs
Issue Tracker
Merge Requests
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
* Redistribution and use in source and binary forms, with or without
5
* modification, are permitted provided that the following conditions are
6
* met:
7
*
8
* * Redistributions of source code must retain the above copyright
9
* notice, this list of conditions and the following disclaimer.
10
* * Redistributions in binary form must reproduce the above
11
* copyright notice, this list of conditions and the following disclaimer
12
* in the documentation and/or other materials provided with the
13
* distribution.
14
* * Neither the name of Google Inc. nor the names of its
15
* contributors may be used to endorse or promote products derived from
16
* this software without specific prior written permission.
17
*
18
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
*/
30
31
/*
32
* Note: This code is modified to work under ns-3's environment.
33
* Modified by: Vivek Jain <jain.vivek.anand@gmail.com>
34
* Viyom Mittal <viyommittal@gmail.com>
35
* Mohit P. Tahiliani <tahiliani@nitk.edu.in>
36
*/
37
38
// Implements Kathleen Nichols' algorithm for tracking the minimum (or maximum)
39
// estimate of a stream of samples over some fixed time interval. (E.g.,
40
// the minimum RTT over the past five minutes.) The algorithm keeps track of
41
// the best, second best, and third best min (or max) estimates, maintaining an
42
// invariant that the measurement time of the n'th best >= n-1'th best.
43
// The algorithm works as follows. On a reset, all three estimates are set to
44
// the same sample. The second best estimate is then recorded in the second
45
// quarter of the window, and a third best estimate is recorded in the second
46
// half of the window, bounding the worst case error when the true min is
47
// monotonically increasing (or true max is monotonically decreasing) over the
48
// window.
49
//
50
// A new best sample replaces all three estimates, since the new best is lower
51
// (or higher) than everything else in the window and it is the most recent.
52
// The window thus effectively gets reset on every new min. The same property
53
// holds true for second best and third best estimates. Specifically, when a
54
// sample arrives that is better than the second best but not better than the
55
// best, it replaces the second and third best estimates but not the best
56
// estimate. Similarly, a sample that is better than the third best estimate
57
// but not the other estimates replaces only the third best estimate.
58
//
59
// Finally, when the best expires, it is replaced by the second best, which in
60
// turn is replaced by the third best. The newest sample replaces the third
61
// best.
62
63
#ifndef WINDOWED_FILTER_H_
64
#define WINDOWED_FILTER_H_
65
66
namespace
ns3
67
{
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
};
92
97
template
<
class
T>
98
struct
MaxFilter
99
{
100
public
:
108
bool
operator()
(
const
T& lhs,
const
T& rhs)
const
109
{
110
if
(rhs == 0 || lhs == 0)
111
{
112
return
false
;
113
}
114
return
lhs >= rhs;
115
}
116
};
117
134
template
<
class
T,
class
Compare,
typename
TimeT,
typename
TimeDeltaT>
135
class
WindowedFilter
136
{
137
public
:
141
WindowedFilter
()
142
{
143
}
144
152
WindowedFilter
(TimeDeltaT windowLength, T zeroValue, TimeT zeroTime)
153
:
m_windowLength
(windowLength),
154
m_zeroValue
(zeroValue),
155
m_samples
{
Sample
(
m_zeroValue
, zeroTime),
156
Sample
(
m_zeroValue
, zeroTime),
157
Sample
(
m_zeroValue
, zeroTime)}
158
{
159
}
160
165
void
SetWindowLength
(TimeDeltaT windowLength)
166
{
167
m_windowLength
= windowLength;
168
}
169
177
void
Update
(T new_sample, TimeT new_time)
178
{
179
// Reset all estimates if they have not yet been initialized, if new sample
180
// is a new best, or if the newest recorded estimate is too old.
181
if
(
m_samples
[0].sample ==
m_zeroValue
|| Compare()(new_sample,
m_samples
[0].sample) ||
182
new_time -
m_samples
[2].time >
m_windowLength
)
183
{
184
Reset
(new_sample, new_time);
185
return
;
186
}
187
if
(Compare()(new_sample,
m_samples
[1].sample))
188
{
189
m_samples
[1] =
Sample
(new_sample, new_time);
190
m_samples
[2] =
m_samples
[1];
191
}
192
else
if
(Compare()(new_sample,
m_samples
[2].sample))
193
{
194
m_samples
[2] =
Sample
(new_sample, new_time);
195
}
196
// Expire and update estimates as necessary.
197
if
(new_time -
m_samples
[0].time >
m_windowLength
)
198
{
199
// The best estimate hasn't been updated for an entire window, so promote
200
// second and third best estimates.
201
m_samples
[0] =
m_samples
[1];
202
m_samples
[1] =
m_samples
[2];
203
m_samples
[2] =
Sample
(new_sample, new_time);
204
// Need to iterate one more time. Check if the new best estimate is
205
// outside the window as well, since it may also have been recorded a
206
// long time ago. Don't need to iterate once more since we cover that
207
// case at the beginning of the method.
208
if
(new_time -
m_samples
[0].time >
m_windowLength
)
209
{
210
m_samples
[0] =
m_samples
[1];
211
m_samples
[1] =
m_samples
[2];
212
}
213
return
;
214
}
215
if
(
m_samples
[1].sample ==
m_samples
[0].sample &&
216
new_time -
m_samples
[1].time >
m_windowLength
>> 2)
217
{
218
// A quarter of the window has passed without a better sample, so the
219
// second-best estimate is taken from the second quarter of the window.
220
m_samples
[2] =
m_samples
[1] =
Sample
(new_sample, new_time);
221
return
;
222
}
223
if
(
m_samples
[2].sample ==
m_samples
[1].sample &&
224
new_time -
m_samples
[2].time >
m_windowLength
>> 1)
225
{
226
// We've passed a half of the window without a better estimate, so take
227
// a third-best estimate from the second half of the window.
228
m_samples
[2] =
Sample
(new_sample, new_time);
229
}
230
}
231
237
void
Reset
(T new_sample, TimeT new_time)
238
{
239
m_samples
[0] =
m_samples
[1] =
m_samples
[2] =
Sample
(new_sample, new_time);
240
}
241
246
T
GetBest
()
const
247
{
248
return
m_samples
[0].
sample
;
249
}
250
255
T
GetSecondBest
()
const
256
{
257
return
m_samples
[1].
sample
;
258
}
259
264
T
GetThirdBest
()
const
265
{
266
return
m_samples
[2].
sample
;
267
}
268
272
struct
Sample
273
{
274
T
sample
;
275
TimeT
time
;
276
280
Sample
()
281
{
282
}
283
289
Sample
(T init_sample, TimeT init_time)
290
:
sample
(init_sample),
291
time
(init_time)
292
{
293
}
294
};
295
296
TimeDeltaT
m_windowLength
;
297
T
m_zeroValue
;
298
Sample
m_samples
[3];
299
};
300
301
}
// namespace ns3
302
#endif
// WINDOWED_FILTER_H_
ns3::WindowedFilter
Construct a windowed filter.
Definition:
windowed-filter.h:136
ns3::WindowedFilter::WindowedFilter
WindowedFilter(TimeDeltaT windowLength, T zeroValue, TimeT zeroTime)
constructor
Definition:
windowed-filter.h:152
ns3::WindowedFilter::Update
void Update(T new_sample, TimeT new_time)
Updates best estimates with |sample|, and expires and updates best estimates as necessary.
Definition:
windowed-filter.h:177
ns3::WindowedFilter::GetSecondBest
T GetSecondBest() const
Returns second Max/Min value so far among the windowed samples.
Definition:
windowed-filter.h:255
ns3::WindowedFilter::WindowedFilter
WindowedFilter()
constructor
Definition:
windowed-filter.h:141
ns3::WindowedFilter::m_samples
Sample m_samples[3]
Best estimate is element 0.
Definition:
windowed-filter.h:298
ns3::WindowedFilter::m_zeroValue
T m_zeroValue
Uninitialized value of T.
Definition:
windowed-filter.h:297
ns3::WindowedFilter::m_windowLength
TimeDeltaT m_windowLength
Time length of window.
Definition:
windowed-filter.h:296
ns3::WindowedFilter::GetBest
T GetBest() const
Returns Max/Min value so far among the windowed samples.
Definition:
windowed-filter.h:246
ns3::WindowedFilter::GetThirdBest
T GetThirdBest() const
Returns third Max/Min value so far among the windowed samples.
Definition:
windowed-filter.h:264
ns3::WindowedFilter::SetWindowLength
void SetWindowLength(TimeDeltaT windowLength)
Changes the window length.
Definition:
windowed-filter.h:165
ns3::WindowedFilter::Reset
void Reset(T new_sample, TimeT new_time)
Resets all estimates to new sample.
Definition:
windowed-filter.h:237
ns3
Every class exported by the ns3 library is enclosed in the ns3 namespace.
ns3::MaxFilter
Compares two values.
Definition:
windowed-filter.h:99
ns3::MaxFilter::operator()
bool operator()(const T &lhs, const T &rhs) const
Compares two values.
Definition:
windowed-filter.h:108
ns3::MinFilter
Compares two values.
Definition:
windowed-filter.h:74
ns3::MinFilter::operator()
bool operator()(const T &lhs, const T &rhs) const
Compares two values.
Definition:
windowed-filter.h:83
ns3::WindowedFilter::Sample
sample.
Definition:
windowed-filter.h:273
ns3::WindowedFilter::Sample::Sample
Sample()
constructor
Definition:
windowed-filter.h:280
ns3::WindowedFilter::Sample::Sample
Sample(T init_sample, TimeT init_time)
constructor
Definition:
windowed-filter.h:289
ns3::WindowedFilter::Sample::time
TimeT time
time when the sample was recorded.
Definition:
windowed-filter.h:275
ns3::WindowedFilter::Sample::sample
T sample
recorded sample.
Definition:
windowed-filter.h:274
src
internet
model
windowed-filter.h
Generated on Sun Jul 2 2023 18:21:42 for ns-3 by
1.9.6