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
* 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
42
namespace
ns3
43
{
44
/**
45
* \brief Compares two values
46
* \param T type of the measurement that is being filtered.
47
*/
48
template
<
class
T>
49
struct
MinFilter
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
*/
73
template
<
class
T>
74
struct
MaxFilter
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
*/
110
template
<
class
T,
class
Compare,
typename
TimeT,
typename
TimeDeltaT>
111
class
WindowedFilter
112
{
113
public
:
114
/**
115
* \brief constructor
116
*/
117
WindowedFilter
()
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
*/
231
T
GetSecondBest
()
const
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
*/
256
Sample
()
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_
ns3::WindowedFilter
Construct a windowed filter.
Definition
windowed-filter.h:112
ns3::WindowedFilter::WindowedFilter
WindowedFilter(TimeDeltaT windowLength, T zeroValue, TimeT zeroTime)
constructor
Definition
windowed-filter.h:128
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:153
ns3::WindowedFilter::GetSecondBest
T GetSecondBest() const
Returns second Max/Min value so far among the windowed samples.
Definition
windowed-filter.h:231
ns3::WindowedFilter::WindowedFilter
WindowedFilter()
constructor
Definition
windowed-filter.h:117
ns3::WindowedFilter::m_samples
Sample m_samples[3]
Best estimate is element 0.
Definition
windowed-filter.h:274
ns3::WindowedFilter::m_zeroValue
T m_zeroValue
Uninitialized value of T.
Definition
windowed-filter.h:273
ns3::WindowedFilter::m_windowLength
TimeDeltaT m_windowLength
Time length of window.
Definition
windowed-filter.h:272
ns3::WindowedFilter::GetBest
T GetBest() const
Returns Max/Min value so far among the windowed samples.
Definition
windowed-filter.h:222
ns3::WindowedFilter::GetThirdBest
T GetThirdBest() const
Returns third Max/Min value so far among the windowed samples.
Definition
windowed-filter.h:240
ns3::WindowedFilter::SetWindowLength
void SetWindowLength(TimeDeltaT windowLength)
Changes the window length.
Definition
windowed-filter.h:141
ns3::WindowedFilter::Reset
void Reset(T new_sample, TimeT new_time)
Resets all estimates to new sample.
Definition
windowed-filter.h:213
ns3
Every class exported by the ns3 library is enclosed in the ns3 namespace.
ns3::MaxFilter
Compares two values.
Definition
windowed-filter.h:75
ns3::MaxFilter::operator()
bool operator()(const T &lhs, const T &rhs) const
Compares two values.
Definition
windowed-filter.h:84
ns3::MinFilter
Compares two values.
Definition
windowed-filter.h:50
ns3::MinFilter::operator()
bool operator()(const T &lhs, const T &rhs) const
Compares two values.
Definition
windowed-filter.h:59
ns3::WindowedFilter::Sample
sample.
Definition
windowed-filter.h:249
ns3::WindowedFilter::Sample::Sample
Sample()
constructor
Definition
windowed-filter.h:256
ns3::WindowedFilter::Sample::Sample
Sample(T init_sample, TimeT init_time)
constructor
Definition
windowed-filter.h:265
ns3::WindowedFilter::Sample::time
TimeT time
time when the sample was recorded.
Definition
windowed-filter.h:251
ns3::WindowedFilter::Sample::sample
T sample
recorded sample.
Definition
windowed-filter.h:250
src
internet
model
windowed-filter.h
Generated on Fri Nov 8 2024 13:59:01 for ns-3 by
1.11.0