trendline_estimator.cc (12026B)
1 /* 2 * Copyright (c) 2016 The WebRTC project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11 #include "modules/congestion_controller/goog_cc/trendline_estimator.h" 12 13 #include <algorithm> 14 #include <cmath> 15 #include <cstddef> 16 #include <cstdint> 17 #include <cstdio> 18 #include <deque> 19 #include <memory> 20 #include <optional> 21 #include <string> 22 #include <utility> 23 24 #include "api/field_trials_view.h" 25 #include "api/network_state_predictor.h" 26 #include "api/transport/bandwidth_usage.h" 27 #include "rtc_base/checks.h" 28 #include "rtc_base/experiments/struct_parameters_parser.h" 29 #include "rtc_base/logging.h" 30 #include "rtc_base/numerics/safe_minmax.h" 31 32 namespace webrtc { 33 34 namespace { 35 36 // Parameters for linear least squares fit of regression line to noisy data. 37 constexpr double kDefaultTrendlineSmoothingCoeff = 0.9; 38 constexpr double kDefaultTrendlineThresholdGain = 4.0; 39 const char kBweWindowSizeInPacketsExperiment[] = 40 "WebRTC-BweWindowSizeInPackets"; 41 42 size_t ReadTrendlineFilterWindowSize(const FieldTrialsView& key_value_config) { 43 std::string experiment_string = 44 key_value_config.Lookup(kBweWindowSizeInPacketsExperiment); 45 size_t window_size; 46 int parsed_values = 47 sscanf(experiment_string.c_str(), "Enabled-%zu", &window_size); 48 if (parsed_values == 1) { 49 if (window_size > 1) 50 return window_size; 51 RTC_LOG(LS_WARNING) << "Window size must be greater than 1."; 52 } 53 RTC_LOG(LS_WARNING) << "Failed to parse parameters for BweWindowSizeInPackets" 54 " experiment from field trial string. Using default."; 55 return TrendlineEstimatorSettings::kDefaultTrendlineWindowSize; 56 } 57 58 std::optional<double> LinearFitSlope( 59 const std::deque<TrendlineEstimator::PacketTiming>& packets) { 60 RTC_DCHECK(packets.size() >= 2); 61 // Compute the "center of mass". 62 double sum_x = 0; 63 double sum_y = 0; 64 for (const auto& packet : packets) { 65 sum_x += packet.arrival_time_ms; 66 sum_y += packet.smoothed_delay_ms; 67 } 68 double x_avg = sum_x / packets.size(); 69 double y_avg = sum_y / packets.size(); 70 // Compute the slope k = \sum (x_i-x_avg)(y_i-y_avg) / \sum (x_i-x_avg)^2 71 double numerator = 0; 72 double denominator = 0; 73 for (const auto& packet : packets) { 74 double x = packet.arrival_time_ms; 75 double y = packet.smoothed_delay_ms; 76 numerator += (x - x_avg) * (y - y_avg); 77 denominator += (x - x_avg) * (x - x_avg); 78 } 79 if (denominator == 0) 80 return std::nullopt; 81 return numerator / denominator; 82 } 83 84 std::optional<double> ComputeSlopeCap( 85 const std::deque<TrendlineEstimator::PacketTiming>& packets, 86 const TrendlineEstimatorSettings& settings) { 87 RTC_DCHECK(1 <= settings.beginning_packets && 88 settings.beginning_packets < packets.size()); 89 RTC_DCHECK(1 <= settings.end_packets && 90 settings.end_packets < packets.size()); 91 RTC_DCHECK(settings.beginning_packets + settings.end_packets <= 92 packets.size()); 93 TrendlineEstimator::PacketTiming early = packets[0]; 94 for (size_t i = 1; i < settings.beginning_packets; ++i) { 95 if (packets[i].raw_delay_ms < early.raw_delay_ms) 96 early = packets[i]; 97 } 98 size_t late_start = packets.size() - settings.end_packets; 99 TrendlineEstimator::PacketTiming late = packets[late_start]; 100 for (size_t i = late_start + 1; i < packets.size(); ++i) { 101 if (packets[i].raw_delay_ms < late.raw_delay_ms) 102 late = packets[i]; 103 } 104 if (late.arrival_time_ms - early.arrival_time_ms < 1) { 105 return std::nullopt; 106 } 107 return (late.raw_delay_ms - early.raw_delay_ms) / 108 (late.arrival_time_ms - early.arrival_time_ms) + 109 settings.cap_uncertainty; 110 } 111 112 constexpr double kMaxAdaptOffsetMs = 15.0; 113 constexpr double kOverUsingTimeThreshold = 10; 114 constexpr int kMinNumDeltas = 60; 115 constexpr int kDeltaCounterMax = 1000; 116 117 } // namespace 118 119 TrendlineEstimatorSettings::TrendlineEstimatorSettings( 120 const FieldTrialsView& key_value_config) { 121 if (key_value_config.IsEnabled(kBweWindowSizeInPacketsExperiment)) { 122 window_size = ReadTrendlineFilterWindowSize(key_value_config); 123 } 124 Parser()->Parse(key_value_config.Lookup(TrendlineEstimatorSettings::kKey)); 125 if (window_size < 10 || 200 < window_size) { 126 RTC_LOG(LS_WARNING) << "Window size must be between 10 and 200 packets"; 127 window_size = kDefaultTrendlineWindowSize; 128 } 129 if (enable_cap) { 130 if (beginning_packets < 1 || end_packets < 1 || 131 beginning_packets > window_size || end_packets > window_size) { 132 RTC_LOG(LS_WARNING) << "Size of beginning and end must be between 1 and " 133 << window_size; 134 enable_cap = false; 135 beginning_packets = end_packets = 0; 136 cap_uncertainty = 0.0; 137 } 138 if (beginning_packets + end_packets > window_size) { 139 RTC_LOG(LS_WARNING) 140 << "Size of beginning plus end can't exceed the window size"; 141 enable_cap = false; 142 beginning_packets = end_packets = 0; 143 cap_uncertainty = 0.0; 144 } 145 if (cap_uncertainty < 0.0 || 0.025 < cap_uncertainty) { 146 RTC_LOG(LS_WARNING) << "Cap uncertainty must be between 0 and 0.025"; 147 cap_uncertainty = 0.0; 148 } 149 } 150 } 151 152 std::unique_ptr<StructParametersParser> TrendlineEstimatorSettings::Parser() { 153 return StructParametersParser::Create("sort", &enable_sort, // 154 "cap", &enable_cap, // 155 "beginning_packets", 156 &beginning_packets, // 157 "end_packets", &end_packets, // 158 "cap_uncertainty", &cap_uncertainty, // 159 "window_size", &window_size); 160 } 161 162 TrendlineEstimator::TrendlineEstimator( 163 const FieldTrialsView& key_value_config, 164 NetworkStatePredictor* network_state_predictor) 165 : settings_(key_value_config), 166 smoothing_coef_(kDefaultTrendlineSmoothingCoeff), 167 threshold_gain_(kDefaultTrendlineThresholdGain), 168 num_of_deltas_(0), 169 first_arrival_time_ms_(-1), 170 accumulated_delay_(0), 171 smoothed_delay_(0), 172 delay_hist_(), 173 k_up_(0.0087), 174 k_down_(0.039), 175 overusing_time_threshold_(kOverUsingTimeThreshold), 176 threshold_(12.5), 177 prev_modified_trend_(NAN), 178 last_update_ms_(-1), 179 prev_trend_(0.0), 180 time_over_using_(-1), 181 overuse_counter_(0), 182 hypothesis_(BandwidthUsage::kBwNormal), 183 hypothesis_predicted_(BandwidthUsage::kBwNormal), 184 network_state_predictor_(network_state_predictor) { 185 RTC_LOG(LS_INFO) 186 << "Using Trendline filter for delay change estimation with settings " 187 << settings_.Parser()->Encode() << " and " 188 << (network_state_predictor_ ? "injected" : "no") 189 << " network state predictor"; 190 } 191 192 TrendlineEstimator::~TrendlineEstimator() {} 193 194 void TrendlineEstimator::UpdateTrendline(double recv_delta_ms, 195 double send_delta_ms, 196 int64_t /* send_time_ms */, 197 int64_t arrival_time_ms, 198 size_t /* packet_size */) { 199 const double delta_ms = recv_delta_ms - send_delta_ms; 200 ++num_of_deltas_; 201 num_of_deltas_ = std::min(num_of_deltas_, kDeltaCounterMax); 202 if (first_arrival_time_ms_ == -1) 203 first_arrival_time_ms_ = arrival_time_ms; 204 205 // Exponential backoff filter. 206 accumulated_delay_ += delta_ms; 207 smoothed_delay_ = smoothing_coef_ * smoothed_delay_ + 208 (1 - smoothing_coef_) * accumulated_delay_; 209 210 // Maintain packet window 211 delay_hist_.emplace_back( 212 static_cast<double>(arrival_time_ms - first_arrival_time_ms_), 213 smoothed_delay_, accumulated_delay_); 214 if (settings_.enable_sort) { 215 for (size_t i = delay_hist_.size() - 1; 216 i > 0 && 217 delay_hist_[i].arrival_time_ms < delay_hist_[i - 1].arrival_time_ms; 218 --i) { 219 std::swap(delay_hist_[i], delay_hist_[i - 1]); 220 } 221 } 222 if (delay_hist_.size() > settings_.window_size) 223 delay_hist_.pop_front(); 224 225 // Simple linear regression. 226 double trend = prev_trend_; 227 if (delay_hist_.size() == settings_.window_size) { 228 // Update trend_ if it is possible to fit a line to the data. The delay 229 // trend can be seen as an estimate of (send_rate - capacity)/capacity. 230 // 0 < trend < 1 -> the delay increases, queues are filling up 231 // trend == 0 -> the delay does not change 232 // trend < 0 -> the delay decreases, queues are being emptied 233 trend = LinearFitSlope(delay_hist_).value_or(trend); 234 if (settings_.enable_cap) { 235 std::optional<double> cap = ComputeSlopeCap(delay_hist_, settings_); 236 // We only use the cap to filter out overuse detections, not 237 // to detect additional underuses. 238 if (trend >= 0 && cap.has_value() && trend > cap.value()) { 239 trend = cap.value(); 240 } 241 } 242 } 243 244 Detect(trend, send_delta_ms, arrival_time_ms); 245 } 246 247 void TrendlineEstimator::Update(double recv_delta_ms, 248 double send_delta_ms, 249 int64_t send_time_ms, 250 int64_t arrival_time_ms, 251 size_t packet_size, 252 bool calculated_deltas) { 253 if (calculated_deltas) { 254 UpdateTrendline(recv_delta_ms, send_delta_ms, send_time_ms, arrival_time_ms, 255 packet_size); 256 } 257 if (network_state_predictor_) { 258 hypothesis_predicted_ = network_state_predictor_->Update( 259 send_time_ms, arrival_time_ms, hypothesis_); 260 } 261 } 262 263 BandwidthUsage TrendlineEstimator::State() const { 264 return network_state_predictor_ ? hypothesis_predicted_ : hypothesis_; 265 } 266 267 void TrendlineEstimator::Detect(double trend, double ts_delta, int64_t now_ms) { 268 if (num_of_deltas_ < 2) { 269 hypothesis_ = BandwidthUsage::kBwNormal; 270 return; 271 } 272 const double modified_trend = 273 std::min(num_of_deltas_, kMinNumDeltas) * trend * threshold_gain_; 274 prev_modified_trend_ = modified_trend; 275 if (modified_trend > threshold_) { 276 if (time_over_using_ == -1) { 277 // Initialize the timer. Assume that we've been 278 // over-using half of the time since the previous 279 // sample. 280 time_over_using_ = ts_delta / 2; 281 } else { 282 // Increment timer 283 time_over_using_ += ts_delta; 284 } 285 overuse_counter_++; 286 if (time_over_using_ > overusing_time_threshold_ && overuse_counter_ > 1) { 287 if (trend >= prev_trend_) { 288 time_over_using_ = 0; 289 overuse_counter_ = 0; 290 hypothesis_ = BandwidthUsage::kBwOverusing; 291 } 292 } 293 } else if (modified_trend < -threshold_) { 294 time_over_using_ = -1; 295 overuse_counter_ = 0; 296 hypothesis_ = BandwidthUsage::kBwUnderusing; 297 } else { 298 time_over_using_ = -1; 299 overuse_counter_ = 0; 300 hypothesis_ = BandwidthUsage::kBwNormal; 301 } 302 prev_trend_ = trend; 303 UpdateThreshold(modified_trend, now_ms); 304 } 305 306 void TrendlineEstimator::UpdateThreshold(double modified_trend, 307 int64_t now_ms) { 308 if (last_update_ms_ == -1) 309 last_update_ms_ = now_ms; 310 311 if (fabs(modified_trend) > threshold_ + kMaxAdaptOffsetMs) { 312 // Avoid adapting the threshold to big latency spikes, caused e.g., 313 // by a sudden capacity drop. 314 last_update_ms_ = now_ms; 315 return; 316 } 317 318 const double k = fabs(modified_trend) < threshold_ ? k_down_ : k_up_; 319 const int64_t kMaxTimeDeltaMs = 100; 320 int64_t time_delta_ms = std::min(now_ms - last_update_ms_, kMaxTimeDeltaMs); 321 threshold_ += k * (fabs(modified_trend) - threshold_) * time_delta_ms; 322 threshold_ = SafeClamp(threshold_, 6.f, 600.f); 323 last_update_ms_ = now_ms; 324 } 325 326 } // namespace webrtc