OLD | NEW |
1 // Copyright 2016 The Chromium Authors. All rights reserved. | 1 // Copyright 2016 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef NET_NQE_OBSERVATION_BUFFER_H_ | 5 #ifndef NET_NQE_OBSERVATION_BUFFER_H_ |
6 #define NET_NQE_OBSERVATION_BUFFER_H_ | 6 #define NET_NQE_OBSERVATION_BUFFER_H_ |
7 | 7 |
8 #include <float.h> | 8 #include <float.h> |
| 9 #include <stdint.h> |
9 | 10 |
10 #include <algorithm> | 11 #include <algorithm> |
11 #include <deque> | 12 #include <deque> |
12 #include <memory> | 13 #include <memory> |
13 #include <utility> | 14 #include <utility> |
14 #include <vector> | 15 #include <vector> |
15 | 16 |
16 #include "base/macros.h" | 17 #include "base/macros.h" |
| 18 #include "base/optional.h" |
17 #include "base/time/default_tick_clock.h" | 19 #include "base/time/default_tick_clock.h" |
18 #include "base/time/tick_clock.h" | 20 #include "base/time/tick_clock.h" |
19 #include "base/time/time.h" | 21 #include "base/time/time.h" |
20 #include "net/base/net_export.h" | 22 #include "net/base/net_export.h" |
21 #include "net/nqe/network_quality_observation.h" | 23 #include "net/nqe/network_quality_observation.h" |
22 #include "net/nqe/network_quality_observation_source.h" | 24 #include "net/nqe/network_quality_observation_source.h" |
23 #include "net/nqe/weighted_observation.h" | 25 #include "net/nqe/weighted_observation.h" |
24 | 26 |
25 namespace net { | 27 namespace net { |
26 | 28 |
27 namespace nqe { | 29 namespace nqe { |
28 | 30 |
29 namespace internal { | 31 namespace internal { |
30 | 32 |
31 // Stores observations sorted by time. | 33 // Stores observations sorted by time. |
32 template <typename ValueType> | 34 template <typename ValueType> |
33 class NET_EXPORT_PRIVATE ObservationBuffer { | 35 class NET_EXPORT_PRIVATE ObservationBuffer { |
34 public: | 36 public: |
35 ObservationBuffer(double weight_multiplier_per_second, | 37 ObservationBuffer(double weight_multiplier_per_second, |
36 double weight_multiplier_per_dbm) | 38 double weight_multiplier_per_signal_level) |
37 : weight_multiplier_per_second_(weight_multiplier_per_second), | 39 : weight_multiplier_per_second_(weight_multiplier_per_second), |
38 weight_multiplier_per_dbm_(weight_multiplier_per_dbm), | 40 weight_multiplier_per_signal_level_(weight_multiplier_per_signal_level), |
39 tick_clock_(new base::DefaultTickClock()) { | 41 tick_clock_(new base::DefaultTickClock()) { |
40 static_assert(kMaximumObservationsBufferSize > 0U, | 42 static_assert(kMaximumObservationsBufferSize > 0U, |
41 "Minimum size of observation buffer must be > 0"); | 43 "Minimum size of observation buffer must be > 0"); |
42 DCHECK_LE(0.0, weight_multiplier_per_second_); | 44 DCHECK_LE(0.0, weight_multiplier_per_second_); |
43 DCHECK_GE(1.0, weight_multiplier_per_second_); | 45 DCHECK_GE(1.0, weight_multiplier_per_second_); |
44 DCHECK_LE(0.0, weight_multiplier_per_dbm_); | 46 DCHECK_LE(0.0, weight_multiplier_per_signal_level_); |
45 DCHECK_GE(1.0, weight_multiplier_per_dbm_); | 47 DCHECK_GE(1.0, weight_multiplier_per_signal_level_); |
46 } | 48 } |
47 | 49 |
48 ~ObservationBuffer() {} | 50 ~ObservationBuffer() {} |
49 | 51 |
50 // Adds |observation| to the buffer. The oldest observation in the buffer | 52 // Adds |observation| to the buffer. The oldest observation in the buffer |
51 // will be evicted to make room if the buffer is already full. | 53 // will be evicted to make room if the buffer is already full. |
52 void AddObservation(const Observation<ValueType>& observation) { | 54 void AddObservation(const Observation<ValueType>& observation) { |
53 DCHECK_LE(observations_.size(), | 55 DCHECK_LE(observations_.size(), |
54 static_cast<size_t>(kMaximumObservationsBufferSize)); | 56 static_cast<size_t>(kMaximumObservationsBufferSize)); |
55 // Evict the oldest element if the buffer is already full. | 57 // Evict the oldest element if the buffer is already full. |
(...skipping 14 matching lines...) Expand all Loading... |
70 } | 72 } |
71 | 73 |
72 // Clears the observations stored in this buffer. | 74 // Clears the observations stored in this buffer. |
73 void Clear() { observations_.clear(); } | 75 void Clear() { observations_.clear(); } |
74 | 76 |
75 // Returns true iff the |percentile| value of the observations in this | 77 // Returns true iff the |percentile| value of the observations in this |
76 // buffer is available. Sets |result| to the computed |percentile| | 78 // buffer is available. Sets |result| to the computed |percentile| |
77 // value of all observations made on or after |begin_timestamp|. If the | 79 // value of all observations made on or after |begin_timestamp|. If the |
78 // value is unavailable, false is returned and |result| is not modified. | 80 // value is unavailable, false is returned and |result| is not modified. |
79 // Percentile value is unavailable if all the values in observation buffer are | 81 // Percentile value is unavailable if all the values in observation buffer are |
80 // older than |begin_timestamp|. |current_signal_strength_dbm| is the current | 82 // older than |begin_timestamp|. |current_signal_strength| is the current |
81 // signal strength in dBm. | 83 // signal strength. |result| must not be null. |
82 // |result| must not be null. | |
83 // TODO(tbansal): Move out param |result| as the last param of the function. | 84 // TODO(tbansal): Move out param |result| as the last param of the function. |
84 bool GetPercentile(base::TimeTicks begin_timestamp, | 85 bool GetPercentile(base::TimeTicks begin_timestamp, |
85 int32_t current_signal_strength_dbm, | 86 const base::Optional<int32_t>& current_signal_strength, |
86 ValueType* result, | 87 ValueType* result, |
87 int percentile, | 88 int percentile, |
88 const std::vector<NetworkQualityObservationSource>& | 89 const std::vector<NetworkQualityObservationSource>& |
89 disallowed_observation_sources) const { | 90 disallowed_observation_sources) const { |
90 // Stores weighted observations in increasing order by value. | 91 // Stores weighted observations in increasing order by value. |
91 std::vector<WeightedObservation<ValueType>> weighted_observations; | 92 std::vector<WeightedObservation<ValueType>> weighted_observations; |
92 | 93 |
93 // Total weight of all observations in |weighted_observations|. | 94 // Total weight of all observations in |weighted_observations|. |
94 double total_weight = 0.0; | 95 double total_weight = 0.0; |
95 | 96 |
96 ComputeWeightedObservations(begin_timestamp, current_signal_strength_dbm, | 97 ComputeWeightedObservations(begin_timestamp, current_signal_strength, |
97 &weighted_observations, &total_weight, | 98 &weighted_observations, &total_weight, |
98 disallowed_observation_sources); | 99 disallowed_observation_sources); |
99 if (weighted_observations.empty()) | 100 if (weighted_observations.empty()) |
100 return false; | 101 return false; |
101 | 102 |
102 double desired_weight = percentile / 100.0 * total_weight; | 103 double desired_weight = percentile / 100.0 * total_weight; |
103 | 104 |
104 double cumulative_weight_seen_so_far = 0.0; | 105 double cumulative_weight_seen_so_far = 0.0; |
105 for (const auto& weighted_observation : weighted_observations) { | 106 for (const auto& weighted_observation : weighted_observations) { |
106 cumulative_weight_seen_so_far += weighted_observation.weight; | 107 cumulative_weight_seen_so_far += weighted_observation.weight; |
(...skipping 11 matching lines...) Expand all Loading... |
118 // This is same as value of the last observation in the sorted vector. | 119 // This is same as value of the last observation in the sorted vector. |
119 *result = weighted_observations.at(weighted_observations.size() - 1).value; | 120 *result = weighted_observations.at(weighted_observations.size() - 1).value; |
120 return true; | 121 return true; |
121 } | 122 } |
122 | 123 |
123 // Returns true iff the weighted average of the observations in this | 124 // Returns true iff the weighted average of the observations in this |
124 // buffer is available. Sets |result| to the computed weighted average value | 125 // buffer is available. Sets |result| to the computed weighted average value |
125 // of all observations made on or after |begin_timestamp|. If the value is | 126 // of all observations made on or after |begin_timestamp|. If the value is |
126 // unavailable, false is returned and |result| is not modified. The unweighted | 127 // unavailable, false is returned and |result| is not modified. The unweighted |
127 // average value is unavailable if all the values in the observation buffer | 128 // average value is unavailable if all the values in the observation buffer |
128 // are older than |begin_timestamp|. |current_signal_strength_dbm| is the | 129 // are older than |begin_timestamp|. |current_signal_strength| is the |
129 // current signal strength in dBm. |result| must not be null. | 130 // current signal strength. |result| must not be null. |
130 bool GetWeightedAverage(base::TimeTicks begin_timestamp, | 131 bool GetWeightedAverage( |
131 int32_t current_signal_strength_dbm, | 132 base::TimeTicks begin_timestamp, |
132 const std::vector<NetworkQualityObservationSource>& | 133 const base::Optional<int32_t>& current_signal_strength, |
133 disallowed_observation_sources, | 134 const std::vector<NetworkQualityObservationSource>& |
134 ValueType* result) const { | 135 disallowed_observation_sources, |
| 136 ValueType* result) const { |
135 // Stores weighted observations in increasing order by value. | 137 // Stores weighted observations in increasing order by value. |
136 std::vector<WeightedObservation<ValueType>> weighted_observations; | 138 std::vector<WeightedObservation<ValueType>> weighted_observations; |
137 | 139 |
138 // Total weight of all observations in |weighted_observations|. | 140 // Total weight of all observations in |weighted_observations|. |
139 double total_weight = 0.0; | 141 double total_weight = 0.0; |
140 | 142 |
141 ComputeWeightedObservations(begin_timestamp, current_signal_strength_dbm, | 143 ComputeWeightedObservations(begin_timestamp, current_signal_strength, |
142 &weighted_observations, &total_weight, | 144 &weighted_observations, &total_weight, |
143 disallowed_observation_sources); | 145 disallowed_observation_sources); |
144 if (weighted_observations.empty()) | 146 if (weighted_observations.empty()) |
145 return false; | 147 return false; |
146 | 148 |
147 // Weighted average is the sum of observations times their respective | 149 // Weighted average is the sum of observations times their respective |
148 // weights, divided by the sum of the weights of all observations. | 150 // weights, divided by the sum of the weights of all observations. |
149 double total_weight_times_value = 0.0; | 151 double total_weight_times_value = 0.0; |
150 for (const auto& weighted_observation : weighted_observations) { | 152 for (const auto& weighted_observation : weighted_observations) { |
151 total_weight_times_value += | 153 total_weight_times_value += |
152 (weighted_observation.weight * | 154 (weighted_observation.weight * |
153 ConvertValueTypeToDouble(weighted_observation.value)); | 155 ConvertValueTypeToDouble(weighted_observation.value)); |
154 } | 156 } |
155 | 157 |
156 ConvertDoubleToValueType(total_weight_times_value / total_weight, result); | 158 ConvertDoubleToValueType(total_weight_times_value / total_weight, result); |
157 return true; | 159 return true; |
158 } | 160 } |
159 | 161 |
160 // Returns true iff the unweighted average of the observations in this buffer | 162 // Returns true iff the unweighted average of the observations in this buffer |
161 // is available. Sets |result| to the computed unweighted average value of | 163 // is available. Sets |result| to the computed unweighted average value of |
162 // all observations made on or after |begin_timestamp|. If the value is | 164 // all observations made on or after |begin_timestamp|. If the value is |
163 // unavailable, false is returned and |result| is not modified. The weighted | 165 // unavailable, false is returned and |result| is not modified. The weighted |
164 // average value is unavailable if all the values in the observation buffer | 166 // average value is unavailable if all the values in the observation buffer |
165 // are older than |begin_timestamp|. |current_signal_strength_dbm| is the | 167 // are older than |begin_timestamp|. |current_signal_strength| is the |
166 // current signal strength in dBm. |result| must not be null. | 168 // current signal strength. |result| must not be null. |
167 bool GetUnweightedAverage(base::TimeTicks begin_timestamp, | 169 bool GetUnweightedAverage( |
168 int32_t current_signal_strength_dbm, | 170 base::TimeTicks begin_timestamp, |
169 const std::vector<NetworkQualityObservationSource>& | 171 const base::Optional<int32_t>& current_signal_strength, |
170 disallowed_observation_sources, | 172 const std::vector<NetworkQualityObservationSource>& |
171 ValueType* result) const { | 173 disallowed_observation_sources, |
| 174 ValueType* result) const { |
172 // Stores weighted observations in increasing order by value. | 175 // Stores weighted observations in increasing order by value. |
173 std::vector<WeightedObservation<ValueType>> weighted_observations; | 176 std::vector<WeightedObservation<ValueType>> weighted_observations; |
174 | 177 |
175 // Total weight of all observations in |weighted_observations|. | 178 // Total weight of all observations in |weighted_observations|. |
176 double total_weight = 0.0; | 179 double total_weight = 0.0; |
177 | 180 |
178 ComputeWeightedObservations(begin_timestamp, current_signal_strength_dbm, | 181 ComputeWeightedObservations(begin_timestamp, current_signal_strength, |
179 &weighted_observations, &total_weight, | 182 &weighted_observations, &total_weight, |
180 disallowed_observation_sources); | 183 disallowed_observation_sources); |
181 if (weighted_observations.empty()) | 184 if (weighted_observations.empty()) |
182 return false; | 185 return false; |
183 | 186 |
184 // The unweighted average is the sum of all observations divided by the | 187 // The unweighted average is the sum of all observations divided by the |
185 // number of observations. | 188 // number of observations. |
186 double total_value = 0.0; | 189 double total_value = 0.0; |
187 for (const auto& weighted_observation : weighted_observations) | 190 for (const auto& weighted_observation : weighted_observations) |
188 total_value += ConvertValueTypeToDouble(weighted_observation.value); | 191 total_value += ConvertValueTypeToDouble(weighted_observation.value); |
(...skipping 22 matching lines...) Expand all Loading... |
211 void ConvertDoubleToValueType(double input, base::TimeDelta* output) const { | 214 void ConvertDoubleToValueType(double input, base::TimeDelta* output) const { |
212 *output = base::TimeDelta::FromMilliseconds(input); | 215 *output = base::TimeDelta::FromMilliseconds(input); |
213 } | 216 } |
214 void ConvertDoubleToValueType(double input, int32_t* output) const { | 217 void ConvertDoubleToValueType(double input, int32_t* output) const { |
215 *output = input; | 218 *output = input; |
216 } | 219 } |
217 | 220 |
218 // Computes the weighted observations and stores them in | 221 // Computes the weighted observations and stores them in |
219 // |weighted_observations| sorted by ascending |WeightedObservation.value|. | 222 // |weighted_observations| sorted by ascending |WeightedObservation.value|. |
220 // Only the observations with timestamp later than |begin_timestamp| are | 223 // Only the observations with timestamp later than |begin_timestamp| are |
221 // considered. |current_signal_strength_dbm| is the current signal strength | 224 // considered. |current_signal_strength| is the current signal strength |
222 // (in dBm) when the observation was taken, and is set to INT32_MIN if the | 225 // when the observation was taken. This method also sets |total_weight| to |
223 // signal strength is currently unavailable. This method also sets | 226 // the total weight of all observations. Should be called only when there is |
224 // |total_weight| to the total weight of all observations. Should be called | 227 // at least one observation in the buffer. |
225 // only when there is at least one observation in the buffer. | |
226 void ComputeWeightedObservations( | 228 void ComputeWeightedObservations( |
227 const base::TimeTicks& begin_timestamp, | 229 const base::TimeTicks& begin_timestamp, |
228 int32_t current_signal_strength_dbm, | 230 const base::Optional<int32_t>& current_signal_strength, |
229 std::vector<WeightedObservation<ValueType>>* weighted_observations, | 231 std::vector<WeightedObservation<ValueType>>* weighted_observations, |
230 double* total_weight, | 232 double* total_weight, |
231 const std::vector<NetworkQualityObservationSource>& | 233 const std::vector<NetworkQualityObservationSource>& |
232 disallowed_observation_sources) const { | 234 disallowed_observation_sources) const { |
233 DCHECK_GE(Capacity(), Size()); | 235 DCHECK_GE(Capacity(), Size()); |
234 | 236 |
235 weighted_observations->clear(); | 237 weighted_observations->clear(); |
236 double total_weight_observations = 0.0; | 238 double total_weight_observations = 0.0; |
237 base::TimeTicks now = tick_clock_->NowTicks(); | 239 base::TimeTicks now = tick_clock_->NowTicks(); |
238 | 240 |
239 for (const auto& observation : observations_) { | 241 for (const auto& observation : observations_) { |
240 if (observation.timestamp < begin_timestamp) | 242 if (observation.timestamp < begin_timestamp) |
241 continue; | 243 continue; |
242 bool disallowed = false; | 244 bool disallowed = false; |
243 for (const auto& disallowed_source : disallowed_observation_sources) { | 245 for (const auto& disallowed_source : disallowed_observation_sources) { |
244 if (disallowed_source == observation.source) | 246 if (disallowed_source == observation.source) |
245 disallowed = true; | 247 disallowed = true; |
246 } | 248 } |
247 if (disallowed) | 249 if (disallowed) |
248 continue; | 250 continue; |
249 base::TimeDelta time_since_sample_taken = now - observation.timestamp; | 251 base::TimeDelta time_since_sample_taken = now - observation.timestamp; |
250 double time_weight = pow(weight_multiplier_per_second_, | 252 double time_weight = pow(weight_multiplier_per_second_, |
251 time_since_sample_taken.InSeconds()); | 253 time_since_sample_taken.InSeconds()); |
252 | 254 |
253 double signal_strength_weight = 1.0; | 255 double signal_strength_weight = 1.0; |
254 if (current_signal_strength_dbm != INT32_MIN && | 256 if (current_signal_strength && observation.signal_strength) { |
255 observation.signal_strength_dbm != INT32_MIN && | 257 int32_t signal_strength_weight_diff = |
256 current_signal_strength_dbm != INT32_MAX && | 258 std::abs(current_signal_strength.value() - |
257 observation.signal_strength_dbm != INT32_MAX) { | 259 observation.signal_strength.value()); |
258 int32_t signal_strength_weight_diff = std::abs( | 260 signal_strength_weight = pow(weight_multiplier_per_signal_level_, |
259 current_signal_strength_dbm - observation.signal_strength_dbm); | 261 signal_strength_weight_diff); |
260 signal_strength_weight = | |
261 pow(weight_multiplier_per_dbm_, signal_strength_weight_diff); | |
262 } | 262 } |
263 | 263 |
264 double weight = time_weight * signal_strength_weight; | 264 double weight = time_weight * signal_strength_weight; |
265 | 265 |
266 weight = std::max(DBL_MIN, std::min(1.0, weight)); | 266 weight = std::max(DBL_MIN, std::min(1.0, weight)); |
267 | 267 |
268 weighted_observations->push_back( | 268 weighted_observations->push_back( |
269 WeightedObservation<ValueType>(observation.value, weight)); | 269 WeightedObservation<ValueType>(observation.value, weight)); |
270 total_weight_observations += weight; | 270 total_weight_observations += weight; |
271 } | 271 } |
(...skipping 15 matching lines...) Expand all Loading... |
287 // front of the queue. | 287 // front of the queue. |
288 std::deque<Observation<ValueType>> observations_; | 288 std::deque<Observation<ValueType>> observations_; |
289 | 289 |
290 // The factor by which the weight of an observation reduces every second. | 290 // The factor by which the weight of an observation reduces every second. |
291 // For example, if an observation is 6 seconds old, its weight would be: | 291 // For example, if an observation is 6 seconds old, its weight would be: |
292 // weight_multiplier_per_second_ ^ 6 | 292 // weight_multiplier_per_second_ ^ 6 |
293 // Calculated from |kHalfLifeSeconds| by solving the following equation: | 293 // Calculated from |kHalfLifeSeconds| by solving the following equation: |
294 // weight_multiplier_per_second_ ^ kHalfLifeSeconds = 0.5 | 294 // weight_multiplier_per_second_ ^ kHalfLifeSeconds = 0.5 |
295 const double weight_multiplier_per_second_; | 295 const double weight_multiplier_per_second_; |
296 | 296 |
297 // The factor by which the weight of an observation reduces for every dbM | 297 // The factor by which the weight of an observation reduces for every unit |
298 // difference in the current signal strength, and the signal strength at | 298 // difference in the current signal strength, and the signal strength at |
299 // which the observation was taken. | 299 // which the observation was taken. |
300 // For example, if the observation was taken at 90 dBm, and current signal | 300 // For example, if the observation was taken at 1 unit, and current signal |
301 // strength is 95 dBm, the weight of the observation would be: | 301 // strength is 4 units, the weight of the observation would be: |
302 // |weight_multiplier_per_dbm_| ^ 5. | 302 // |weight_multiplier_per_signal_level_| ^ 3. |
303 const double weight_multiplier_per_dbm_; | 303 const double weight_multiplier_per_signal_level_; |
304 | 304 |
305 std::unique_ptr<base::TickClock> tick_clock_; | 305 std::unique_ptr<base::TickClock> tick_clock_; |
306 | 306 |
307 DISALLOW_COPY_AND_ASSIGN(ObservationBuffer); | 307 DISALLOW_COPY_AND_ASSIGN(ObservationBuffer); |
308 }; | 308 }; |
309 | 309 |
310 } // namespace internal | 310 } // namespace internal |
311 | 311 |
312 } // namespace nqe | 312 } // namespace nqe |
313 | 313 |
314 } // namespace net | 314 } // namespace net |
315 | 315 |
316 #endif // NET_NQE_OBSERVATION_BUFFER_H_ | 316 #endif // NET_NQE_OBSERVATION_BUFFER_H_ |
OLD | NEW |