blob: 47c8f52e9bf915c49e851c85a30a9befeefd0eba [file] [log] [blame]
// Copyright 2017 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "net/nqe/observation_buffer.h"
#include <float.h>
#include <algorithm>
#include <utility>
#include "base/macros.h"
#include "base/time/default_tick_clock.h"
#include "base/time/time.h"
#include "net/nqe/weighted_observation.h"
namespace net {
namespace nqe {
namespace internal {
ObservationBuffer::ObservationBuffer(double weight_multiplier_per_second,
double weight_multiplier_per_signal_level)
: weight_multiplier_per_second_(weight_multiplier_per_second),
tick_clock_(new base::DefaultTickClock()) {
static_assert(kMaximumObservationsBufferSize > 0U,
"Minimum size of observation buffer must be > 0");
DCHECK_LE(0.0, weight_multiplier_per_second_);
DCHECK_GE(1.0, weight_multiplier_per_second_);
DCHECK_LE(0.0, weight_multiplier_per_signal_level_);
DCHECK_GE(1.0, weight_multiplier_per_signal_level_);
ObservationBuffer::~ObservationBuffer() {}
void ObservationBuffer::AddObservation(const Observation& observation) {
DCHECK_LE(observations_.size(), kMaximumObservationsBufferSize);
// Evict the oldest element if the buffer is already full.
if (observations_.size() == kMaximumObservationsBufferSize)
DCHECK_LE(observations_.size(), kMaximumObservationsBufferSize);
base::Optional<int32_t> ObservationBuffer::GetPercentile(
base::TimeTicks begin_timestamp,
const base::Optional<int32_t>& current_signal_strength,
int percentile,
const std::vector<NetworkQualityObservationSource>&
disallowed_observation_sources) const {
// Stores weighted observations in increasing order by value.
std::vector<WeightedObservation> weighted_observations;
// Total weight of all observations in |weighted_observations|.
double total_weight = 0.0;
ComputeWeightedObservations(begin_timestamp, current_signal_strength,
&weighted_observations, &total_weight,
if (weighted_observations.empty())
return base::nullopt;
double desired_weight = percentile / 100.0 * total_weight;
double cumulative_weight_seen_so_far = 0.0;
for (const auto& weighted_observation : weighted_observations) {
cumulative_weight_seen_so_far += weighted_observation.weight;
if (cumulative_weight_seen_so_far >= desired_weight)
return weighted_observation.value;
// Computation may reach here due to floating point errors. This may happen
// if |percentile| was 100 (or close to 100), and |desired_weight| was
// slightly larger than |total_weight| (due to floating point errors).
// In this case, we return the highest |value| among all observations.
// This is same as value of the last observation in the sorted vector.
return - 1).value;
void ObservationBuffer::GetPercentileForEachHostWithCounts(
base::TimeTicks begin_timestamp,
int percentile,
const std::vector<NetworkQualityObservationSource>&
const base::Optional<std::set<IPHash>>& host_filter,
std::map<IPHash, int32_t>* host_keyed_percentiles,
std::map<IPHash, size_t>* host_keyed_counts) const {
DCHECK_GE(Capacity(), Size());
DCHECK_LE(0, percentile);
DCHECK_GE(100, percentile);
// Filter the observations based on timestamp, disallowed sources and the
// presence of a valid host tag. Split the observations into a map keyed by
// the remote host to make it easy to calculate percentiles for each host.
std::map<IPHash, std::vector<int32_t>> host_keyed_observations;
for (const auto& observation : observations_) {
// Look at only those observations which have a |host|.
if (!
IPHash host =;
if (host_filter && (host_filter->find(host) == host_filter->end()))
// Filter the observations recorded before |begin_timestamp|.
if (observation.timestamp() < begin_timestamp)
// If the source of the observation is in the list of disallowed sources,
// skip that observation.
bool disallowed = false;
for (const auto& disallowed_source : disallowed_observation_sources) {
if (disallowed_source == observation.source())
disallowed = true;
if (disallowed)
// Skip 0 values of RTT.
if (observation.value() < 1)
// Create the map entry if it did not already exist. Does nothing if
// |host| was seen before.
host_keyed_observations.emplace(host, std::vector<int32_t>());
if (host_keyed_observations.empty())
// Calculate the percentile values for each host.
for (auto& host_observations : host_keyed_observations) {
IPHash host = host_observations.first;
auto& observations = host_observations.second;
std::sort(observations.begin(), observations.end());
size_t count = observations.size();
DCHECK_GT(count, 0u);
(*host_keyed_counts)[host] = count;
int percentile_index = ((count - 1) * percentile) / 100;
(*host_keyed_percentiles)[host] = observations[percentile_index];
void ObservationBuffer::ComputeWeightedObservations(
const base::TimeTicks& begin_timestamp,
const base::Optional<int32_t>& current_signal_strength,
std::vector<WeightedObservation>* weighted_observations,
double* total_weight,
const std::vector<NetworkQualityObservationSource>&
disallowed_observation_sources) const {
DCHECK_GE(Capacity(), Size());
double total_weight_observations = 0.0;
base::TimeTicks now = tick_clock_->NowTicks();
for (const auto& observation : observations_) {
if (observation.timestamp() < begin_timestamp)
bool disallowed = false;
for (const auto& disallowed_source : disallowed_observation_sources) {
if (disallowed_source == observation.source())
disallowed = true;
if (disallowed)
base::TimeDelta time_since_sample_taken = now - observation.timestamp();
double time_weight =
pow(weight_multiplier_per_second_, time_since_sample_taken.InSeconds());
double signal_strength_weight = 1.0;
if (current_signal_strength && observation.signal_strength()) {
int32_t signal_strength_weight_diff =
std::abs(current_signal_strength.value() -
signal_strength_weight =
pow(weight_multiplier_per_signal_level_, signal_strength_weight_diff);
double weight = time_weight * signal_strength_weight;
weight = std::max(DBL_MIN, std::min(1.0, weight));
WeightedObservation(observation.value(), weight));
total_weight_observations += weight;
// Sort the samples by value in ascending order.
std::sort(weighted_observations->begin(), weighted_observations->end());
*total_weight = total_weight_observations;
DCHECK_LE(0.0, *total_weight);
DCHECK(weighted_observations->empty() || 0.0 < *total_weight);
// |weighted_observations| may have a smaller size than |observations_|
// since the former contains only the observations later than
// |begin_timestamp|.
DCHECK_GE(observations_.size(), weighted_observations->size());
} // namespace internal
} // namespace nqe
} // namespace net