• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 <math.h>
14 
15 #include <algorithm>
16 #include <string>
17 
18 #include "absl/strings/match.h"
19 #include "absl/types/optional.h"
20 #include "modules/remote_bitrate_estimator/include/bwe_defines.h"
21 #include "modules/remote_bitrate_estimator/test/bwe_test_logging.h"
22 #include "rtc_base/checks.h"
23 #include "rtc_base/experiments/struct_parameters_parser.h"
24 #include "rtc_base/logging.h"
25 #include "rtc_base/numerics/safe_minmax.h"
26 
27 namespace webrtc {
28 
29 namespace {
30 
31 // Parameters for linear least squares fit of regression line to noisy data.
32 constexpr double kDefaultTrendlineSmoothingCoeff = 0.9;
33 constexpr double kDefaultTrendlineThresholdGain = 4.0;
34 const char kBweWindowSizeInPacketsExperiment[] =
35     "WebRTC-BweWindowSizeInPackets";
36 
ReadTrendlineFilterWindowSize(const WebRtcKeyValueConfig * key_value_config)37 size_t ReadTrendlineFilterWindowSize(
38     const WebRtcKeyValueConfig* key_value_config) {
39   std::string experiment_string =
40       key_value_config->Lookup(kBweWindowSizeInPacketsExperiment);
41   size_t window_size;
42   int parsed_values =
43       sscanf(experiment_string.c_str(), "Enabled-%zu", &window_size);
44   if (parsed_values == 1) {
45     if (window_size > 1)
46       return window_size;
47     RTC_LOG(WARNING) << "Window size must be greater than 1.";
48   }
49   RTC_LOG(LS_WARNING) << "Failed to parse parameters for BweWindowSizeInPackets"
50                          " experiment from field trial string. Using default.";
51   return TrendlineEstimatorSettings::kDefaultTrendlineWindowSize;
52 }
53 
LinearFitSlope(const std::deque<TrendlineEstimator::PacketTiming> & packets)54 absl::optional<double> LinearFitSlope(
55     const std::deque<TrendlineEstimator::PacketTiming>& packets) {
56   RTC_DCHECK(packets.size() >= 2);
57   // Compute the "center of mass".
58   double sum_x = 0;
59   double sum_y = 0;
60   for (const auto& packet : packets) {
61     sum_x += packet.arrival_time_ms;
62     sum_y += packet.smoothed_delay_ms;
63   }
64   double x_avg = sum_x / packets.size();
65   double y_avg = sum_y / packets.size();
66   // Compute the slope k = \sum (x_i-x_avg)(y_i-y_avg) / \sum (x_i-x_avg)^2
67   double numerator = 0;
68   double denominator = 0;
69   for (const auto& packet : packets) {
70     double x = packet.arrival_time_ms;
71     double y = packet.smoothed_delay_ms;
72     numerator += (x - x_avg) * (y - y_avg);
73     denominator += (x - x_avg) * (x - x_avg);
74   }
75   if (denominator == 0)
76     return absl::nullopt;
77   return numerator / denominator;
78 }
79 
ComputeSlopeCap(const std::deque<TrendlineEstimator::PacketTiming> & packets,const TrendlineEstimatorSettings & settings)80 absl::optional<double> ComputeSlopeCap(
81     const std::deque<TrendlineEstimator::PacketTiming>& packets,
82     const TrendlineEstimatorSettings& settings) {
83   RTC_DCHECK(1 <= settings.beginning_packets &&
84              settings.beginning_packets < packets.size());
85   RTC_DCHECK(1 <= settings.end_packets &&
86              settings.end_packets < packets.size());
87   RTC_DCHECK(settings.beginning_packets + settings.end_packets <=
88              packets.size());
89   TrendlineEstimator::PacketTiming early = packets[0];
90   for (size_t i = 1; i < settings.beginning_packets; ++i) {
91     if (packets[i].raw_delay_ms < early.raw_delay_ms)
92       early = packets[i];
93   }
94   size_t late_start = packets.size() - settings.end_packets;
95   TrendlineEstimator::PacketTiming late = packets[late_start];
96   for (size_t i = late_start + 1; i < packets.size(); ++i) {
97     if (packets[i].raw_delay_ms < late.raw_delay_ms)
98       late = packets[i];
99   }
100   if (late.arrival_time_ms - early.arrival_time_ms < 1) {
101     return absl::nullopt;
102   }
103   return (late.raw_delay_ms - early.raw_delay_ms) /
104              (late.arrival_time_ms - early.arrival_time_ms) +
105          settings.cap_uncertainty;
106 }
107 
108 constexpr double kMaxAdaptOffsetMs = 15.0;
109 constexpr double kOverUsingTimeThreshold = 10;
110 constexpr int kMinNumDeltas = 60;
111 constexpr int kDeltaCounterMax = 1000;
112 
113 }  // namespace
114 
115 constexpr char TrendlineEstimatorSettings::kKey[];
116 
TrendlineEstimatorSettings(const WebRtcKeyValueConfig * key_value_config)117 TrendlineEstimatorSettings::TrendlineEstimatorSettings(
118     const WebRtcKeyValueConfig* key_value_config) {
119   if (absl::StartsWith(
120           key_value_config->Lookup(kBweWindowSizeInPacketsExperiment),
121           "Enabled")) {
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 
Parser()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 
TrendlineEstimator(const WebRtcKeyValueConfig * key_value_config,NetworkStatePredictor * network_state_predictor)162 TrendlineEstimator::TrendlineEstimator(
163     const WebRtcKeyValueConfig* 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 
~TrendlineEstimator()192 TrendlineEstimator::~TrendlineEstimator() {}
193 
UpdateTrendline(double recv_delta_ms,double send_delta_ms,int64_t send_time_ms,int64_t arrival_time_ms,size_t packet_size)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   BWE_TEST_LOGGING_PLOT(1, "accumulated_delay_ms", arrival_time_ms,
208                         accumulated_delay_);
209   smoothed_delay_ = smoothing_coef_ * smoothed_delay_ +
210                     (1 - smoothing_coef_) * accumulated_delay_;
211   BWE_TEST_LOGGING_PLOT(1, "smoothed_delay_ms", arrival_time_ms,
212                         smoothed_delay_);
213 
214   // Maintain packet window
215   delay_hist_.emplace_back(
216       static_cast<double>(arrival_time_ms - first_arrival_time_ms_),
217       smoothed_delay_, accumulated_delay_);
218   if (settings_.enable_sort) {
219     for (size_t i = delay_hist_.size() - 1;
220          i > 0 &&
221          delay_hist_[i].arrival_time_ms < delay_hist_[i - 1].arrival_time_ms;
222          --i) {
223       std::swap(delay_hist_[i], delay_hist_[i - 1]);
224     }
225   }
226   if (delay_hist_.size() > settings_.window_size)
227     delay_hist_.pop_front();
228 
229   // Simple linear regression.
230   double trend = prev_trend_;
231   if (delay_hist_.size() == settings_.window_size) {
232     // Update trend_ if it is possible to fit a line to the data. The delay
233     // trend can be seen as an estimate of (send_rate - capacity)/capacity.
234     // 0 < trend < 1   ->  the delay increases, queues are filling up
235     //   trend == 0    ->  the delay does not change
236     //   trend < 0     ->  the delay decreases, queues are being emptied
237     trend = LinearFitSlope(delay_hist_).value_or(trend);
238     if (settings_.enable_cap) {
239       absl::optional<double> cap = ComputeSlopeCap(delay_hist_, settings_);
240       // We only use the cap to filter out overuse detections, not
241       // to detect additional underuses.
242       if (trend >= 0 && cap.has_value() && trend > cap.value()) {
243         trend = cap.value();
244       }
245     }
246   }
247   BWE_TEST_LOGGING_PLOT(1, "trendline_slope", arrival_time_ms, trend);
248 
249   Detect(trend, send_delta_ms, arrival_time_ms);
250 }
251 
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)252 void TrendlineEstimator::Update(double recv_delta_ms,
253                                 double send_delta_ms,
254                                 int64_t send_time_ms,
255                                 int64_t arrival_time_ms,
256                                 size_t packet_size,
257                                 bool calculated_deltas) {
258   if (calculated_deltas) {
259     UpdateTrendline(recv_delta_ms, send_delta_ms, send_time_ms, arrival_time_ms,
260                     packet_size);
261   }
262   if (network_state_predictor_) {
263     hypothesis_predicted_ = network_state_predictor_->Update(
264         send_time_ms, arrival_time_ms, hypothesis_);
265   }
266 }
267 
State() const268 BandwidthUsage TrendlineEstimator::State() const {
269   return network_state_predictor_ ? hypothesis_predicted_ : hypothesis_;
270 }
271 
Detect(double trend,double ts_delta,int64_t now_ms)272 void TrendlineEstimator::Detect(double trend, double ts_delta, int64_t now_ms) {
273   if (num_of_deltas_ < 2) {
274     hypothesis_ = BandwidthUsage::kBwNormal;
275     return;
276   }
277   const double modified_trend =
278       std::min(num_of_deltas_, kMinNumDeltas) * trend * threshold_gain_;
279   prev_modified_trend_ = modified_trend;
280   BWE_TEST_LOGGING_PLOT(1, "T", now_ms, modified_trend);
281   BWE_TEST_LOGGING_PLOT(1, "threshold", now_ms, threshold_);
282   if (modified_trend > threshold_) {
283     if (time_over_using_ == -1) {
284       // Initialize the timer. Assume that we've been
285       // over-using half of the time since the previous
286       // sample.
287       time_over_using_ = ts_delta / 2;
288     } else {
289       // Increment timer
290       time_over_using_ += ts_delta;
291     }
292     overuse_counter_++;
293     if (time_over_using_ > overusing_time_threshold_ && overuse_counter_ > 1) {
294       if (trend >= prev_trend_) {
295         time_over_using_ = 0;
296         overuse_counter_ = 0;
297         hypothesis_ = BandwidthUsage::kBwOverusing;
298       }
299     }
300   } else if (modified_trend < -threshold_) {
301     time_over_using_ = -1;
302     overuse_counter_ = 0;
303     hypothesis_ = BandwidthUsage::kBwUnderusing;
304   } else {
305     time_over_using_ = -1;
306     overuse_counter_ = 0;
307     hypothesis_ = BandwidthUsage::kBwNormal;
308   }
309   prev_trend_ = trend;
310   UpdateThreshold(modified_trend, now_ms);
311 }
312 
UpdateThreshold(double modified_trend,int64_t now_ms)313 void TrendlineEstimator::UpdateThreshold(double modified_trend,
314                                          int64_t now_ms) {
315   if (last_update_ms_ == -1)
316     last_update_ms_ = now_ms;
317 
318   if (fabs(modified_trend) > threshold_ + kMaxAdaptOffsetMs) {
319     // Avoid adapting the threshold to big latency spikes, caused e.g.,
320     // by a sudden capacity drop.
321     last_update_ms_ = now_ms;
322     return;
323   }
324 
325   const double k = fabs(modified_trend) < threshold_ ? k_down_ : k_up_;
326   const int64_t kMaxTimeDeltaMs = 100;
327   int64_t time_delta_ms = std::min(now_ms - last_update_ms_, kMaxTimeDeltaMs);
328   threshold_ += k * (fabs(modified_trend) - threshold_) * time_delta_ms;
329   threshold_ = rtc::SafeClamp(threshold_, 6.f, 600.f);
330   last_update_ms_ = now_ms;
331 }
332 
333 }  // namespace webrtc
334