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 "webrtc/modules/congestion_controller/delay_based_bwe.h"
12
13 #include <algorithm>
14 #include <cmath>
15 #include <string>
16
17 #include "webrtc/base/checks.h"
18 #include "webrtc/base/constructormagic.h"
19 #include "webrtc/base/logging.h"
20 #include "webrtc/base/thread_annotations.h"
21 #include "webrtc/modules/congestion_controller/include/congestion_controller.h"
22 #include "webrtc/modules/pacing/paced_sender.h"
23 #include "webrtc/modules/remote_bitrate_estimator/include/remote_bitrate_estimator.h"
24 #include "webrtc/modules/remote_bitrate_estimator/test/bwe_test_logging.h"
25 #include "webrtc/system_wrappers/include/field_trial.h"
26 #include "webrtc/system_wrappers/include/metrics.h"
27 #include "webrtc/typedefs.h"
28
29 namespace {
30 constexpr int kTimestampGroupLengthMs = 5;
31 constexpr int kAbsSendTimeFraction = 18;
32 constexpr int kAbsSendTimeInterArrivalUpshift = 8;
33 constexpr int kInterArrivalShift =
34 kAbsSendTimeFraction + kAbsSendTimeInterArrivalUpshift;
35 constexpr double kTimestampToMs =
36 1000.0 / static_cast<double>(1 << kInterArrivalShift);
37 // This ssrc is used to fulfill the current API but will be removed
38 // after the API has been changed.
39 constexpr uint32_t kFixedSsrc = 0;
40 constexpr int kInitialRateWindowMs = 500;
41 constexpr int kRateWindowMs = 150;
42
43 // Parameters for linear least squares fit of regression line to noisy data.
44 constexpr size_t kDefaultTrendlineWindowSize = 15;
45 constexpr double kDefaultTrendlineSmoothingCoeff = 0.9;
46 constexpr double kDefaultTrendlineThresholdGain = 4.0;
47
48 // Parameters for Theil-Sen robust fitting of line to noisy data.
49 constexpr size_t kDefaultMedianSlopeWindowSize = 20;
50 constexpr double kDefaultMedianSlopeThresholdGain = 4.0;
51
52 const char kBitrateEstimateExperiment[] = "WebRTC-ImprovedBitrateEstimate";
53 const char kBweTrendlineFilterExperiment[] = "WebRTC-BweTrendlineFilter";
54 const char kBweMedianSlopeFilterExperiment[] = "WebRTC-BweMedianSlopeFilter";
55
BitrateEstimateExperimentIsEnabled()56 bool BitrateEstimateExperimentIsEnabled() {
57 return webrtc::field_trial::FindFullName(kBitrateEstimateExperiment) ==
58 "Enabled";
59 }
60
TrendlineFilterExperimentIsEnabled()61 bool TrendlineFilterExperimentIsEnabled() {
62 std::string experiment_string =
63 webrtc::field_trial::FindFullName(kBweTrendlineFilterExperiment);
64 // The experiment is enabled iff the field trial string begins with "Enabled".
65 return experiment_string.find("Enabled") == 0;
66 }
67
MedianSlopeFilterExperimentIsEnabled()68 bool MedianSlopeFilterExperimentIsEnabled() {
69 std::string experiment_string =
70 webrtc::field_trial::FindFullName(kBweMedianSlopeFilterExperiment);
71 // The experiment is enabled iff the field trial string begins with "Enabled".
72 return experiment_string.find("Enabled") == 0;
73 }
74
ReadTrendlineFilterExperimentParameters(size_t * window_size,double * smoothing_coef,double * threshold_gain)75 bool ReadTrendlineFilterExperimentParameters(size_t* window_size,
76 double* smoothing_coef,
77 double* threshold_gain) {
78 RTC_DCHECK(TrendlineFilterExperimentIsEnabled());
79 RTC_DCHECK(!MedianSlopeFilterExperimentIsEnabled());
80 RTC_DCHECK(window_size != nullptr);
81 RTC_DCHECK(smoothing_coef != nullptr);
82 RTC_DCHECK(threshold_gain != nullptr);
83 std::string experiment_string =
84 webrtc::field_trial::FindFullName(kBweTrendlineFilterExperiment);
85 int parsed_values = sscanf(experiment_string.c_str(), "Enabled-%zu,%lf,%lf",
86 window_size, smoothing_coef, threshold_gain);
87 if (parsed_values == 3) {
88 RTC_CHECK_GT(*window_size, 1) << "Need at least 2 points to fit a line.";
89 RTC_CHECK(0 <= *smoothing_coef && *smoothing_coef <= 1)
90 << "Coefficient needs to be between 0 and 1 for weighted average.";
91 RTC_CHECK_GT(*threshold_gain, 0) << "Threshold gain needs to be positive.";
92 return true;
93 }
94 LOG(LS_WARNING) << "Failed to parse parameters for BweTrendlineFilter "
95 "experiment from field trial string. Using default.";
96 *window_size = kDefaultTrendlineWindowSize;
97 *smoothing_coef = kDefaultTrendlineSmoothingCoeff;
98 *threshold_gain = kDefaultTrendlineThresholdGain;
99 return false;
100 }
101
ReadMedianSlopeFilterExperimentParameters(size_t * window_size,double * threshold_gain)102 bool ReadMedianSlopeFilterExperimentParameters(size_t* window_size,
103 double* threshold_gain) {
104 RTC_DCHECK(!TrendlineFilterExperimentIsEnabled());
105 RTC_DCHECK(MedianSlopeFilterExperimentIsEnabled());
106 RTC_DCHECK(window_size != nullptr);
107 RTC_DCHECK(threshold_gain != nullptr);
108 std::string experiment_string =
109 webrtc::field_trial::FindFullName(kBweMedianSlopeFilterExperiment);
110 int parsed_values = sscanf(experiment_string.c_str(), "Enabled-%zu,%lf",
111 window_size, threshold_gain);
112 if (parsed_values == 2) {
113 RTC_CHECK_GT(*window_size, 1) << "Need at least 2 points to fit a line.";
114 RTC_CHECK_GT(*threshold_gain, 0) << "Threshold gain needs to be positive.";
115 return true;
116 }
117 LOG(LS_WARNING) << "Failed to parse parameters for BweMedianSlopeFilter "
118 "experiment from field trial string. Using default.";
119 *window_size = kDefaultMedianSlopeWindowSize;
120 *threshold_gain = kDefaultMedianSlopeThresholdGain;
121 return false;
122 }
123 } // namespace
124
125 namespace webrtc {
126
BitrateEstimator()127 DelayBasedBwe::BitrateEstimator::BitrateEstimator()
128 : sum_(0),
129 current_win_ms_(0),
130 prev_time_ms_(-1),
131 bitrate_estimate_(-1.0f),
132 bitrate_estimate_var_(50.0f),
133 old_estimator_(kBitrateWindowMs, 8000),
134 in_experiment_(BitrateEstimateExperimentIsEnabled()) {}
135
Update(int64_t now_ms,int bytes)136 void DelayBasedBwe::BitrateEstimator::Update(int64_t now_ms, int bytes) {
137 if (!in_experiment_) {
138 old_estimator_.Update(bytes, now_ms);
139 rtc::Optional<uint32_t> rate = old_estimator_.Rate(now_ms);
140 bitrate_estimate_ = -1.0f;
141 if (rate)
142 bitrate_estimate_ = *rate / 1000.0f;
143 return;
144 }
145 int rate_window_ms = kRateWindowMs;
146 // We use a larger window at the beginning to get a more stable sample that
147 // we can use to initialize the estimate.
148 if (bitrate_estimate_ < 0.f)
149 rate_window_ms = kInitialRateWindowMs;
150 float bitrate_sample = UpdateWindow(now_ms, bytes, rate_window_ms);
151 if (bitrate_sample < 0.0f)
152 return;
153 if (bitrate_estimate_ < 0.0f) {
154 // This is the very first sample we get. Use it to initialize the estimate.
155 bitrate_estimate_ = bitrate_sample;
156 return;
157 }
158 // Define the sample uncertainty as a function of how far away it is from the
159 // current estimate.
160 float sample_uncertainty =
161 10.0f * std::abs(bitrate_estimate_ - bitrate_sample) / bitrate_estimate_;
162 float sample_var = sample_uncertainty * sample_uncertainty;
163 // Update a bayesian estimate of the rate, weighting it lower if the sample
164 // uncertainty is large.
165 // The bitrate estimate uncertainty is increased with each update to model
166 // that the bitrate changes over time.
167 float pred_bitrate_estimate_var = bitrate_estimate_var_ + 5.f;
168 bitrate_estimate_ = (sample_var * bitrate_estimate_ +
169 pred_bitrate_estimate_var * bitrate_sample) /
170 (sample_var + pred_bitrate_estimate_var);
171 bitrate_estimate_var_ = sample_var * pred_bitrate_estimate_var /
172 (sample_var + pred_bitrate_estimate_var);
173 }
174
UpdateWindow(int64_t now_ms,int bytes,int rate_window_ms)175 float DelayBasedBwe::BitrateEstimator::UpdateWindow(int64_t now_ms,
176 int bytes,
177 int rate_window_ms) {
178 // Reset if time moves backwards.
179 if (now_ms < prev_time_ms_) {
180 prev_time_ms_ = -1;
181 sum_ = 0;
182 current_win_ms_ = 0;
183 }
184 if (prev_time_ms_ >= 0) {
185 current_win_ms_ += now_ms - prev_time_ms_;
186 // Reset if nothing has been received for more than a full window.
187 if (now_ms - prev_time_ms_ > rate_window_ms) {
188 sum_ = 0;
189 current_win_ms_ %= rate_window_ms;
190 }
191 }
192 prev_time_ms_ = now_ms;
193 float bitrate_sample = -1.0f;
194 if (current_win_ms_ >= rate_window_ms) {
195 bitrate_sample = 8.0f * sum_ / static_cast<float>(rate_window_ms);
196 current_win_ms_ -= rate_window_ms;
197 sum_ = 0;
198 }
199 sum_ += bytes;
200 return bitrate_sample;
201 }
202
bitrate_bps() const203 rtc::Optional<uint32_t> DelayBasedBwe::BitrateEstimator::bitrate_bps() const {
204 if (bitrate_estimate_ < 0.f)
205 return rtc::Optional<uint32_t>();
206 return rtc::Optional<uint32_t>(bitrate_estimate_ * 1000);
207 }
208
DelayBasedBwe(Clock * clock)209 DelayBasedBwe::DelayBasedBwe(Clock* clock)
210 : in_trendline_experiment_(TrendlineFilterExperimentIsEnabled()),
211 in_median_slope_experiment_(MedianSlopeFilterExperimentIsEnabled()),
212 clock_(clock),
213 inter_arrival_(),
214 kalman_estimator_(),
215 trendline_estimator_(),
216 detector_(),
217 receiver_incoming_bitrate_(),
218 last_update_ms_(-1),
219 last_seen_packet_ms_(-1),
220 uma_recorded_(false),
221 trendline_window_size_(kDefaultTrendlineWindowSize),
222 trendline_smoothing_coeff_(kDefaultTrendlineSmoothingCoeff),
223 trendline_threshold_gain_(kDefaultTrendlineThresholdGain),
224 probing_interval_estimator_(&rate_control_),
225 median_slope_window_size_(kDefaultMedianSlopeWindowSize),
226 median_slope_threshold_gain_(kDefaultMedianSlopeThresholdGain) {
227 if (in_trendline_experiment_) {
228 ReadTrendlineFilterExperimentParameters(&trendline_window_size_,
229 &trendline_smoothing_coeff_,
230 &trendline_threshold_gain_);
231 }
232 if (in_median_slope_experiment_) {
233 ReadMedianSlopeFilterExperimentParameters(&median_slope_window_size_,
234 &median_slope_threshold_gain_);
235 }
236
237 network_thread_.DetachFromThread();
238 }
239
IncomingPacketFeedbackVector(const std::vector<PacketInfo> & packet_feedback_vector)240 DelayBasedBwe::Result DelayBasedBwe::IncomingPacketFeedbackVector(
241 const std::vector<PacketInfo>& packet_feedback_vector) {
242 RTC_DCHECK(network_thread_.CalledOnValidThread());
243 if (!uma_recorded_) {
244 RTC_HISTOGRAM_ENUMERATION(kBweTypeHistogram,
245 BweNames::kSendSideTransportSeqNum,
246 BweNames::kBweNamesMax);
247 uma_recorded_ = true;
248 }
249 Result aggregated_result;
250 for (const auto& packet_info : packet_feedback_vector) {
251 Result result = IncomingPacketInfo(packet_info);
252 if (result.updated)
253 aggregated_result = result;
254 }
255 return aggregated_result;
256 }
257
IncomingPacketInfo(const PacketInfo & info)258 DelayBasedBwe::Result DelayBasedBwe::IncomingPacketInfo(
259 const PacketInfo& info) {
260 int64_t now_ms = clock_->TimeInMilliseconds();
261
262 receiver_incoming_bitrate_.Update(info.arrival_time_ms, info.payload_size);
263 Result result;
264 // Reset if the stream has timed out.
265 if (last_seen_packet_ms_ == -1 ||
266 now_ms - last_seen_packet_ms_ > kStreamTimeOutMs) {
267 inter_arrival_.reset(
268 new InterArrival((kTimestampGroupLengthMs << kInterArrivalShift) / 1000,
269 kTimestampToMs, true));
270 kalman_estimator_.reset(new OveruseEstimator(OverUseDetectorOptions()));
271 trendline_estimator_.reset(new TrendlineEstimator(
272 trendline_window_size_, trendline_smoothing_coeff_,
273 trendline_threshold_gain_));
274 median_slope_estimator_.reset(new MedianSlopeEstimator(
275 median_slope_window_size_, median_slope_threshold_gain_));
276 }
277 last_seen_packet_ms_ = now_ms;
278
279 uint32_t send_time_24bits =
280 static_cast<uint32_t>(
281 ((static_cast<uint64_t>(info.send_time_ms) << kAbsSendTimeFraction) +
282 500) /
283 1000) &
284 0x00FFFFFF;
285 // Shift up send time to use the full 32 bits that inter_arrival works with,
286 // so wrapping works properly.
287 uint32_t timestamp = send_time_24bits << kAbsSendTimeInterArrivalUpshift;
288
289 uint32_t ts_delta = 0;
290 int64_t t_delta = 0;
291 int size_delta = 0;
292 if (inter_arrival_->ComputeDeltas(timestamp, info.arrival_time_ms, now_ms,
293 info.payload_size, &ts_delta, &t_delta,
294 &size_delta)) {
295 double ts_delta_ms = (1000.0 * ts_delta) / (1 << kInterArrivalShift);
296 if (in_trendline_experiment_) {
297 trendline_estimator_->Update(t_delta, ts_delta_ms, info.arrival_time_ms);
298 detector_.Detect(trendline_estimator_->trendline_slope(), ts_delta_ms,
299 trendline_estimator_->num_of_deltas(),
300 info.arrival_time_ms);
301 } else if (in_median_slope_experiment_) {
302 median_slope_estimator_->Update(t_delta, ts_delta_ms,
303 info.arrival_time_ms);
304 detector_.Detect(median_slope_estimator_->trendline_slope(), ts_delta_ms,
305 median_slope_estimator_->num_of_deltas(),
306 info.arrival_time_ms);
307 } else {
308 kalman_estimator_->Update(t_delta, ts_delta_ms, size_delta,
309 detector_.State(), info.arrival_time_ms);
310 detector_.Detect(kalman_estimator_->offset(), ts_delta_ms,
311 kalman_estimator_->num_of_deltas(),
312 info.arrival_time_ms);
313 }
314 }
315
316 int probing_bps = 0;
317 if (info.probe_cluster_id != PacketInfo::kNotAProbe) {
318 probing_bps = probe_bitrate_estimator_.HandleProbeAndEstimateBitrate(info);
319 }
320 rtc::Optional<uint32_t> acked_bitrate_bps =
321 receiver_incoming_bitrate_.bitrate_bps();
322 // Currently overusing the bandwidth.
323 if (detector_.State() == kBwOverusing) {
324 if (acked_bitrate_bps &&
325 rate_control_.TimeToReduceFurther(now_ms, *acked_bitrate_bps)) {
326 result.updated =
327 UpdateEstimate(info.arrival_time_ms, now_ms, acked_bitrate_bps,
328 &result.target_bitrate_bps);
329 }
330 } else if (probing_bps > 0) {
331 // No overuse, but probing measured a bitrate.
332 rate_control_.SetEstimate(probing_bps, info.arrival_time_ms);
333 result.probe = true;
334 result.updated =
335 UpdateEstimate(info.arrival_time_ms, now_ms, acked_bitrate_bps,
336 &result.target_bitrate_bps);
337 }
338 if (!result.updated &&
339 (last_update_ms_ == -1 ||
340 now_ms - last_update_ms_ > rate_control_.GetFeedbackInterval())) {
341 result.updated =
342 UpdateEstimate(info.arrival_time_ms, now_ms, acked_bitrate_bps,
343 &result.target_bitrate_bps);
344 }
345 if (result.updated) {
346 last_update_ms_ = now_ms;
347 BWE_TEST_LOGGING_PLOT(1, "target_bitrate_bps", now_ms,
348 result.target_bitrate_bps);
349 }
350
351 return result;
352 }
353
UpdateEstimate(int64_t arrival_time_ms,int64_t now_ms,rtc::Optional<uint32_t> acked_bitrate_bps,uint32_t * target_bitrate_bps)354 bool DelayBasedBwe::UpdateEstimate(int64_t arrival_time_ms,
355 int64_t now_ms,
356 rtc::Optional<uint32_t> acked_bitrate_bps,
357 uint32_t* target_bitrate_bps) {
358 // TODO(terelius): RateControlInput::noise_var is deprecated and will be
359 // removed. In the meantime, we set it to zero.
360 const RateControlInput input(detector_.State(), acked_bitrate_bps, 0);
361 rate_control_.Update(&input, now_ms);
362 *target_bitrate_bps = rate_control_.UpdateBandwidthEstimate(now_ms);
363 return rate_control_.ValidEstimate();
364 }
365
OnRttUpdate(int64_t avg_rtt_ms,int64_t max_rtt_ms)366 void DelayBasedBwe::OnRttUpdate(int64_t avg_rtt_ms, int64_t max_rtt_ms) {
367 rate_control_.SetRtt(avg_rtt_ms);
368 }
369
LatestEstimate(std::vector<uint32_t> * ssrcs,uint32_t * bitrate_bps) const370 bool DelayBasedBwe::LatestEstimate(std::vector<uint32_t>* ssrcs,
371 uint32_t* bitrate_bps) const {
372 // Currently accessed from both the process thread (see
373 // ModuleRtpRtcpImpl::Process()) and the configuration thread (see
374 // Call::GetStats()). Should in the future only be accessed from a single
375 // thread.
376 RTC_DCHECK(ssrcs);
377 RTC_DCHECK(bitrate_bps);
378 if (!rate_control_.ValidEstimate())
379 return false;
380
381 *ssrcs = {kFixedSsrc};
382 *bitrate_bps = rate_control_.LatestEstimate();
383 return true;
384 }
385
SetMinBitrate(int min_bitrate_bps)386 void DelayBasedBwe::SetMinBitrate(int min_bitrate_bps) {
387 // Called from both the configuration thread and the network thread. Shouldn't
388 // be called from the network thread in the future.
389 rate_control_.SetMinBitrate(min_bitrate_bps);
390 }
391
GetProbingIntervalMs() const392 int64_t DelayBasedBwe::GetProbingIntervalMs() const {
393 return probing_interval_estimator_.GetIntervalMs();
394 }
395 } // namespace webrtc
396