Source code
Revision control
Copy as Markdown
Other Tools
/*
* Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
*
* Use of this source code is governed by a BSD-style license
* that can be found in the LICENSE file in the root of the source
* tree. An additional intellectual property rights grant can be found
* in the file PATENTS. All contributing project authors may
* be found in the AUTHORS file in the root of the source tree.
*/
#include "modules/congestion_controller/goog_cc/trendline_estimator.h"
#include <math.h>
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <memory>
#include <string>
#include <utility>
#include "absl/strings/match.h"
#include "absl/types/optional.h"
#include "api/field_trials_view.h"
#include "api/network_state_predictor.h"
#include "api/transport/bandwidth_usage.h"
#include "rtc_base/checks.h"
#include "rtc_base/experiments/struct_parameters_parser.h"
#include "rtc_base/logging.h"
#include "rtc_base/numerics/safe_minmax.h"
namespace webrtc {
namespace {
// Parameters for linear least squares fit of regression line to noisy data.
constexpr double kDefaultTrendlineSmoothingCoeff = 0.9;
constexpr double kDefaultTrendlineThresholdGain = 4.0;
const char kBweWindowSizeInPacketsExperiment[] =
"WebRTC-BweWindowSizeInPackets";
size_t ReadTrendlineFilterWindowSize(const FieldTrialsView* key_value_config) {
std::string experiment_string =
key_value_config->Lookup(kBweWindowSizeInPacketsExperiment);
size_t window_size;
int parsed_values =
sscanf(experiment_string.c_str(), "Enabled-%zu", &window_size);
if (parsed_values == 1) {
if (window_size > 1)
return window_size;
RTC_LOG(LS_WARNING) << "Window size must be greater than 1.";
}
RTC_LOG(LS_WARNING) << "Failed to parse parameters for BweWindowSizeInPackets"
" experiment from field trial string. Using default.";
return TrendlineEstimatorSettings::kDefaultTrendlineWindowSize;
}
absl::optional<double> LinearFitSlope(
const std::deque<TrendlineEstimator::PacketTiming>& packets) {
RTC_DCHECK(packets.size() >= 2);
// Compute the "center of mass".
double sum_x = 0;
double sum_y = 0;
for (const auto& packet : packets) {
sum_x += packet.arrival_time_ms;
sum_y += packet.smoothed_delay_ms;
}
double x_avg = sum_x / packets.size();
double y_avg = sum_y / packets.size();
// Compute the slope k = \sum (x_i-x_avg)(y_i-y_avg) / \sum (x_i-x_avg)^2
double numerator = 0;
double denominator = 0;
for (const auto& packet : packets) {
double x = packet.arrival_time_ms;
double y = packet.smoothed_delay_ms;
numerator += (x - x_avg) * (y - y_avg);
denominator += (x - x_avg) * (x - x_avg);
}
if (denominator == 0)
return absl::nullopt;
return numerator / denominator;
}
absl::optional<double> ComputeSlopeCap(
const std::deque<TrendlineEstimator::PacketTiming>& packets,
const TrendlineEstimatorSettings& settings) {
RTC_DCHECK(1 <= settings.beginning_packets &&
settings.beginning_packets < packets.size());
RTC_DCHECK(1 <= settings.end_packets &&
settings.end_packets < packets.size());
RTC_DCHECK(settings.beginning_packets + settings.end_packets <=
packets.size());
TrendlineEstimator::PacketTiming early = packets[0];
for (size_t i = 1; i < settings.beginning_packets; ++i) {
if (packets[i].raw_delay_ms < early.raw_delay_ms)
early = packets[i];
}
size_t late_start = packets.size() - settings.end_packets;
TrendlineEstimator::PacketTiming late = packets[late_start];
for (size_t i = late_start + 1; i < packets.size(); ++i) {
if (packets[i].raw_delay_ms < late.raw_delay_ms)
late = packets[i];
}
if (late.arrival_time_ms - early.arrival_time_ms < 1) {
return absl::nullopt;
}
return (late.raw_delay_ms - early.raw_delay_ms) /
(late.arrival_time_ms - early.arrival_time_ms) +
settings.cap_uncertainty;
}
constexpr double kMaxAdaptOffsetMs = 15.0;
constexpr double kOverUsingTimeThreshold = 10;
constexpr int kMinNumDeltas = 60;
constexpr int kDeltaCounterMax = 1000;
} // namespace
constexpr char TrendlineEstimatorSettings::kKey[];
TrendlineEstimatorSettings::TrendlineEstimatorSettings(
const FieldTrialsView* key_value_config) {
if (absl::StartsWith(
key_value_config->Lookup(kBweWindowSizeInPacketsExperiment),
"Enabled")) {
window_size = ReadTrendlineFilterWindowSize(key_value_config);
}
Parser()->Parse(key_value_config->Lookup(TrendlineEstimatorSettings::kKey));
if (window_size < 10 || 200 < window_size) {
RTC_LOG(LS_WARNING) << "Window size must be between 10 and 200 packets";
window_size = kDefaultTrendlineWindowSize;
}
if (enable_cap) {
if (beginning_packets < 1 || end_packets < 1 ||
beginning_packets > window_size || end_packets > window_size) {
RTC_LOG(LS_WARNING) << "Size of beginning and end must be between 1 and "
<< window_size;
enable_cap = false;
beginning_packets = end_packets = 0;
cap_uncertainty = 0.0;
}
if (beginning_packets + end_packets > window_size) {
RTC_LOG(LS_WARNING)
<< "Size of beginning plus end can't exceed the window size";
enable_cap = false;
beginning_packets = end_packets = 0;
cap_uncertainty = 0.0;
}
if (cap_uncertainty < 0.0 || 0.025 < cap_uncertainty) {
RTC_LOG(LS_WARNING) << "Cap uncertainty must be between 0 and 0.025";
cap_uncertainty = 0.0;
}
}
}
std::unique_ptr<StructParametersParser> TrendlineEstimatorSettings::Parser() {
return StructParametersParser::Create("sort", &enable_sort, //
"cap", &enable_cap, //
"beginning_packets",
&beginning_packets, //
"end_packets", &end_packets, //
"cap_uncertainty", &cap_uncertainty, //
"window_size", &window_size);
}
TrendlineEstimator::TrendlineEstimator(
const FieldTrialsView* key_value_config,
NetworkStatePredictor* network_state_predictor)
: settings_(key_value_config),
smoothing_coef_(kDefaultTrendlineSmoothingCoeff),
threshold_gain_(kDefaultTrendlineThresholdGain),
num_of_deltas_(0),
first_arrival_time_ms_(-1),
accumulated_delay_(0),
smoothed_delay_(0),
delay_hist_(),
k_up_(0.0087),
k_down_(0.039),
overusing_time_threshold_(kOverUsingTimeThreshold),
threshold_(12.5),
prev_modified_trend_(NAN),
last_update_ms_(-1),
prev_trend_(0.0),
time_over_using_(-1),
overuse_counter_(0),
hypothesis_(BandwidthUsage::kBwNormal),
hypothesis_predicted_(BandwidthUsage::kBwNormal),
network_state_predictor_(network_state_predictor) {
RTC_LOG(LS_INFO)
<< "Using Trendline filter for delay change estimation with settings "
<< settings_.Parser()->Encode() << " and "
<< (network_state_predictor_ ? "injected" : "no")
<< " network state predictor";
}
TrendlineEstimator::~TrendlineEstimator() {}
void TrendlineEstimator::UpdateTrendline(double recv_delta_ms,
double send_delta_ms,
int64_t send_time_ms,
int64_t arrival_time_ms,
size_t packet_size) {
const double delta_ms = recv_delta_ms - send_delta_ms;
++num_of_deltas_;
num_of_deltas_ = std::min(num_of_deltas_, kDeltaCounterMax);
if (first_arrival_time_ms_ == -1)
first_arrival_time_ms_ = arrival_time_ms;
// Exponential backoff filter.
accumulated_delay_ += delta_ms;
smoothed_delay_ = smoothing_coef_ * smoothed_delay_ +
(1 - smoothing_coef_) * accumulated_delay_;
// Maintain packet window
delay_hist_.emplace_back(
static_cast<double>(arrival_time_ms - first_arrival_time_ms_),
smoothed_delay_, accumulated_delay_);
if (settings_.enable_sort) {
for (size_t i = delay_hist_.size() - 1;
i > 0 &&
delay_hist_[i].arrival_time_ms < delay_hist_[i - 1].arrival_time_ms;
--i) {
std::swap(delay_hist_[i], delay_hist_[i - 1]);
}
}
if (delay_hist_.size() > settings_.window_size)
delay_hist_.pop_front();
// Simple linear regression.
double trend = prev_trend_;
if (delay_hist_.size() == settings_.window_size) {
// Update trend_ if it is possible to fit a line to the data. The delay
// trend can be seen as an estimate of (send_rate - capacity)/capacity.
// 0 < trend < 1 -> the delay increases, queues are filling up
// trend == 0 -> the delay does not change
// trend < 0 -> the delay decreases, queues are being emptied
trend = LinearFitSlope(delay_hist_).value_or(trend);
if (settings_.enable_cap) {
absl::optional<double> cap = ComputeSlopeCap(delay_hist_, settings_);
// We only use the cap to filter out overuse detections, not
// to detect additional underuses.
if (trend >= 0 && cap.has_value() && trend > cap.value()) {
trend = cap.value();
}
}
}
Detect(trend, send_delta_ms, arrival_time_ms);
}
void TrendlineEstimator::Update(double recv_delta_ms,
double send_delta_ms,
int64_t send_time_ms,
int64_t arrival_time_ms,
size_t packet_size,
bool calculated_deltas) {
if (calculated_deltas) {
UpdateTrendline(recv_delta_ms, send_delta_ms, send_time_ms, arrival_time_ms,
packet_size);
}
if (network_state_predictor_) {
hypothesis_predicted_ = network_state_predictor_->Update(
send_time_ms, arrival_time_ms, hypothesis_);
}
}
BandwidthUsage TrendlineEstimator::State() const {
return network_state_predictor_ ? hypothesis_predicted_ : hypothesis_;
}
void TrendlineEstimator::Detect(double trend, double ts_delta, int64_t now_ms) {
if (num_of_deltas_ < 2) {
hypothesis_ = BandwidthUsage::kBwNormal;
return;
}
const double modified_trend =
std::min(num_of_deltas_, kMinNumDeltas) * trend * threshold_gain_;
prev_modified_trend_ = modified_trend;
if (modified_trend > threshold_) {
if (time_over_using_ == -1) {
// Initialize the timer. Assume that we've been
// over-using half of the time since the previous
// sample.
time_over_using_ = ts_delta / 2;
} else {
// Increment timer
time_over_using_ += ts_delta;
}
overuse_counter_++;
if (time_over_using_ > overusing_time_threshold_ && overuse_counter_ > 1) {
if (trend >= prev_trend_) {
time_over_using_ = 0;
overuse_counter_ = 0;
hypothesis_ = BandwidthUsage::kBwOverusing;
}
}
} else if (modified_trend < -threshold_) {
time_over_using_ = -1;
overuse_counter_ = 0;
hypothesis_ = BandwidthUsage::kBwUnderusing;
} else {
time_over_using_ = -1;
overuse_counter_ = 0;
hypothesis_ = BandwidthUsage::kBwNormal;
}
prev_trend_ = trend;
UpdateThreshold(modified_trend, now_ms);
}
void TrendlineEstimator::UpdateThreshold(double modified_trend,
int64_t now_ms) {
if (last_update_ms_ == -1)
last_update_ms_ = now_ms;
if (fabs(modified_trend) > threshold_ + kMaxAdaptOffsetMs) {
// Avoid adapting the threshold to big latency spikes, caused e.g.,
// by a sudden capacity drop.
last_update_ms_ = now_ms;
return;
}
const double k = fabs(modified_trend) < threshold_ ? k_down_ : k_up_;
const int64_t kMaxTimeDeltaMs = 100;
int64_t time_delta_ms = std::min(now_ms - last_update_ms_, kMaxTimeDeltaMs);
threshold_ += k * (fabs(modified_trend) - threshold_) * time_delta_ms;
threshold_ = rtc::SafeClamp(threshold_, 6.f, 600.f);
last_update_ms_ = now_ms;
}
} // namespace webrtc