observation_buffer.cc 6.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172
  1. // Copyright 2017 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "net/nqe/observation_buffer.h"
  5. #include <float.h>
  6. #include <algorithm>
  7. #include <utility>
  8. #include "base/containers/cxx20_erase.h"
  9. #include "base/cxx17_backports.h"
  10. #include "base/time/default_tick_clock.h"
  11. #include "base/time/time.h"
  12. #include "net/nqe/network_quality_estimator_params.h"
  13. #include "net/nqe/weighted_observation.h"
  14. namespace net::nqe::internal {
  15. ObservationBuffer::ObservationBuffer(
  16. const NetworkQualityEstimatorParams* params,
  17. const base::TickClock* tick_clock,
  18. double weight_multiplier_per_second,
  19. double weight_multiplier_per_signal_level)
  20. : params_(params),
  21. weight_multiplier_per_second_(weight_multiplier_per_second),
  22. weight_multiplier_per_signal_level_(weight_multiplier_per_signal_level),
  23. tick_clock_(tick_clock) {
  24. DCHECK_LT(0u, params_->observation_buffer_size());
  25. DCHECK_LE(0.0, weight_multiplier_per_second_);
  26. DCHECK_GE(1.0, weight_multiplier_per_second_);
  27. DCHECK_LE(0.0, weight_multiplier_per_signal_level_);
  28. DCHECK_GE(1.0, weight_multiplier_per_signal_level_);
  29. DCHECK(params_);
  30. DCHECK(tick_clock_);
  31. }
  32. ObservationBuffer::ObservationBuffer(const ObservationBuffer& other)
  33. : params_(other.params_),
  34. weight_multiplier_per_second_(other.weight_multiplier_per_second_),
  35. weight_multiplier_per_signal_level_(
  36. other.weight_multiplier_per_signal_level_),
  37. tick_clock_(other.tick_clock_) {
  38. DCHECK(other.observations_.empty());
  39. }
  40. ObservationBuffer::~ObservationBuffer() = default;
  41. void ObservationBuffer::AddObservation(const Observation& observation) {
  42. DCHECK_LE(observations_.size(), params_->observation_buffer_size());
  43. // Observations must be in the non-decreasing order of the timestamps.
  44. DCHECK(observations_.empty() ||
  45. observation.timestamp() >= observations_.back().timestamp());
  46. DCHECK(observation.signal_strength() == INT32_MIN ||
  47. (observation.signal_strength() >= 0 &&
  48. observation.signal_strength() <= 4));
  49. // Evict the oldest element if the buffer is already full.
  50. if (observations_.size() == params_->observation_buffer_size())
  51. observations_.pop_front();
  52. observations_.push_back(observation);
  53. DCHECK_LE(observations_.size(), params_->observation_buffer_size());
  54. }
  55. absl::optional<int32_t> ObservationBuffer::GetPercentile(
  56. base::TimeTicks begin_timestamp,
  57. int32_t current_signal_strength,
  58. int percentile,
  59. size_t* observations_count) const {
  60. DCHECK(current_signal_strength == INT32_MIN ||
  61. (current_signal_strength >= 0 && current_signal_strength <= 4));
  62. // Stores weighted observations in increasing order by value.
  63. std::vector<WeightedObservation> weighted_observations;
  64. // Total weight of all observations in |weighted_observations|.
  65. double total_weight = 0.0;
  66. ComputeWeightedObservations(begin_timestamp, current_signal_strength,
  67. &weighted_observations, &total_weight);
  68. if (observations_count) {
  69. // |observations_count| may be null.
  70. *observations_count = weighted_observations.size();
  71. }
  72. if (weighted_observations.empty())
  73. return absl::nullopt;
  74. double desired_weight = percentile / 100.0 * total_weight;
  75. double cumulative_weight_seen_so_far = 0.0;
  76. for (const auto& weighted_observation : weighted_observations) {
  77. cumulative_weight_seen_so_far += weighted_observation.weight;
  78. if (cumulative_weight_seen_so_far >= desired_weight)
  79. return weighted_observation.value;
  80. }
  81. // Computation may reach here due to floating point errors. This may happen
  82. // if |percentile| was 100 (or close to 100), and |desired_weight| was
  83. // slightly larger than |total_weight| (due to floating point errors).
  84. // In this case, we return the highest |value| among all observations.
  85. // This is same as value of the last observation in the sorted vector.
  86. return weighted_observations.at(weighted_observations.size() - 1).value;
  87. }
  88. void ObservationBuffer::RemoveObservationsWithSource(
  89. bool deleted_observation_sources[NETWORK_QUALITY_OBSERVATION_SOURCE_MAX]) {
  90. base::EraseIf(observations_,
  91. [deleted_observation_sources](const Observation& observation) {
  92. return deleted_observation_sources[static_cast<size_t>(
  93. observation.source())];
  94. });
  95. }
  96. void ObservationBuffer::ComputeWeightedObservations(
  97. const base::TimeTicks& begin_timestamp,
  98. int32_t current_signal_strength,
  99. std::vector<WeightedObservation>* weighted_observations,
  100. double* total_weight) const {
  101. DCHECK_GE(Capacity(), Size());
  102. weighted_observations->clear();
  103. double total_weight_observations = 0.0;
  104. base::TimeTicks now = tick_clock_->NowTicks();
  105. for (const auto& observation : observations_) {
  106. if (observation.timestamp() < begin_timestamp)
  107. continue;
  108. base::TimeDelta time_since_sample_taken = now - observation.timestamp();
  109. double time_weight =
  110. pow(weight_multiplier_per_second_, time_since_sample_taken.InSeconds());
  111. double signal_strength_weight = 1.0;
  112. if (current_signal_strength >= 0 && observation.signal_strength() >= 0) {
  113. int32_t signal_strength_weight_diff =
  114. std::abs(current_signal_strength - observation.signal_strength());
  115. signal_strength_weight =
  116. pow(weight_multiplier_per_signal_level_, signal_strength_weight_diff);
  117. }
  118. double weight = time_weight * signal_strength_weight;
  119. weight = base::clamp(weight, DBL_MIN, 1.0);
  120. weighted_observations->push_back(
  121. WeightedObservation(observation.value(), weight));
  122. total_weight_observations += weight;
  123. }
  124. // Sort the samples by value in ascending order.
  125. std::sort(weighted_observations->begin(), weighted_observations->end());
  126. *total_weight = total_weight_observations;
  127. DCHECK_LE(0.0, *total_weight);
  128. DCHECK(weighted_observations->empty() || 0.0 < *total_weight);
  129. // |weighted_observations| may have a smaller size than |observations_|
  130. // since the former contains only the observations later than
  131. // |begin_timestamp|.
  132. DCHECK_GE(observations_.size(), weighted_observations->size());
  133. }
  134. size_t ObservationBuffer::Capacity() const {
  135. return params_->observation_buffer_size();
  136. }
  137. } // namespace net::nqe::internal