-
Notifications
You must be signed in to change notification settings - Fork 35
/
utilities.hh
182 lines (152 loc) · 4.49 KB
/
utilities.hh
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#ifndef UTILITIES_HH
#define UTILITIES_HH
#include <cassert>
#include <iostream>
#include <list>
#include <math.h>
#include <queue>
class TimeEwma {
double ewma;
double denominator;
double alpha;
double last_update_timestamp;
public:
// lower the alpha, slower the moving average
TimeEwma(const double s_alpha)
: ewma(),
denominator(),
alpha(1.0 - s_alpha),
last_update_timestamp()
{
assert(alpha < 1.0);
}
void reset();
void update(double value, double timestamp);
void add(double value) {ewma += value;}
void round() {ewma = int(ewma*100000) / 100000.0;}
void force_set(double value, double timestamp);
operator double() const {return ewma;}
// true if update has been called atleast once
bool is_valid() const {return denominator != 0.0;}
};
class PlainEwma {
double ewma;
double alpha;
bool valid;
public:
PlainEwma(const double alpha)
: ewma(),
alpha(alpha),
valid(false)
{}
// Note: The tmp argument in the functions below is to maintain compatibility
// with TimeEwma
void force_set(const double value, const double tmp __attribute((unused)) = 0) {
valid = true;
ewma = value;
}
void update(const double value, const double tmp __attribute((unused)) = 0) {
valid = true;
ewma = alpha * value + (1.0 - alpha) * ewma;
}
void round() {
ewma = int(ewma * 100000) / 100000.0;
}
void reset() {
ewma = 0.0;
}
operator double() const { return ewma; }
bool is_valid() const { return valid; }
};
// Maintains a sliding window of values for which the average is
// computed. The window contains values younger than a given
// constant. Computes a time average, so each time instant is given
// equal weightage.
class WindowAverage {
// Format: (value, timestamp)
std::queue< std::pair<double, double> > window;
double window_size; // In time units
double sum;
// Timestamp of the value last popped. If 0.0, no value has been
// popped yet.
double prev_popped_timestamp;
public:
WindowAverage(double window_size)
: window(),
window_size(window_size),
sum(0.0),
prev_popped_timestamp(0.0)
{}
void force_set(double value, double timestamp) {
reset();
update(value, timestamp);
}
void update(double value, double timestamp) {
if (window.size() == 0) {
// Push two nearby values into the window
window.push(std::make_pair(value, timestamp - 1e-3));
assert(prev_popped_timestamp == 0.0);
update(value, timestamp);
return;
}
sum += value * (timestamp - window.back().second);
window.push(std::make_pair(value, timestamp));
// std::cout << "Sum = " << sum << " for " << window.size() << " at " << double(*(this)) << std::endl;
while (window.front().second < timestamp - window_size && window.size() > 2) {
// std::cout << "Deleting: " << window.front().first << " " << sum << " " << window.front().second << " " << timestamp << " " << window_size << " at " << double(*(this)) << std::endl;
if (prev_popped_timestamp != 0.0)
sum -= window.front().first * (window.front().second - prev_popped_timestamp);
prev_popped_timestamp = window.front().second;
window.pop();
}
}
void round() {assert(false);}
void reset() {
while (!window.empty())
window.pop();
sum = 0.0;
prev_popped_timestamp = 0.0;
}
operator double() const {
assert(window.size() != 1);
if (window.size() < 2)return 0.0;
return sum / (window.back().second - window.front().second);
}
bool valid() const {
return !window.empty();
}
};
// Maintains the x percentile value over a small window
class Percentile {
// The following can be dynamic too. Constant makes it a little more
// efficient and to emphasize that the implementation is not
// efficient for large window sizes.
static constexpr int window_len = 100;
double percentile;
typedef double ValType;
std::queue<ValType> window;
public:
Percentile(double percentile) :
percentile(percentile),
window()
{}
void push(ValType val);
ValType get_percentile_value();
void reset();
};
// Estimates the packet loss rate for TCP friendliness. Uses the
// method described in "Equation Based Congestion Control for Unicast
// Applications"
class LossRateEstimate {
const int window = 8;
std::list<double> loss_events;
int cur_loss_interval;
public:
LossRateEstimate() : loss_events(), cur_loss_interval() {}
void reset() {loss_events.clear(); cur_loss_interval = 0; }
void update(bool lost);
double value();
// true if update has been called atleast once
bool is_valid() const {return loss_events.size() == (unsigned)window;}
};
#endif