Line data Source code
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 :
56 0 : bool BitrateEstimateExperimentIsEnabled() {
57 0 : return webrtc::field_trial::FindFullName(kBitrateEstimateExperiment) ==
58 0 : "Enabled";
59 : }
60 :
61 0 : bool TrendlineFilterExperimentIsEnabled() {
62 : std::string experiment_string =
63 0 : webrtc::field_trial::FindFullName(kBweTrendlineFilterExperiment);
64 : // The experiment is enabled iff the field trial string begins with "Enabled".
65 0 : return experiment_string.find("Enabled") == 0;
66 : }
67 :
68 0 : bool MedianSlopeFilterExperimentIsEnabled() {
69 : std::string experiment_string =
70 0 : webrtc::field_trial::FindFullName(kBweMedianSlopeFilterExperiment);
71 : // The experiment is enabled iff the field trial string begins with "Enabled".
72 0 : return experiment_string.find("Enabled") == 0;
73 : }
74 :
75 0 : bool ReadTrendlineFilterExperimentParameters(size_t* window_size,
76 : double* smoothing_coef,
77 : double* threshold_gain) {
78 0 : RTC_DCHECK(TrendlineFilterExperimentIsEnabled());
79 0 : RTC_DCHECK(!MedianSlopeFilterExperimentIsEnabled());
80 0 : RTC_DCHECK(window_size != nullptr);
81 0 : RTC_DCHECK(smoothing_coef != nullptr);
82 0 : RTC_DCHECK(threshold_gain != nullptr);
83 : std::string experiment_string =
84 0 : webrtc::field_trial::FindFullName(kBweTrendlineFilterExperiment);
85 0 : int parsed_values = sscanf(experiment_string.c_str(), "Enabled-%zu,%lf,%lf",
86 0 : window_size, smoothing_coef, threshold_gain);
87 0 : if (parsed_values == 3) {
88 0 : RTC_CHECK_GT(*window_size, 1) << "Need at least 2 points to fit a line.";
89 0 : RTC_CHECK(0 <= *smoothing_coef && *smoothing_coef <= 1)
90 0 : << "Coefficient needs to be between 0 and 1 for weighted average.";
91 0 : RTC_CHECK_GT(*threshold_gain, 0) << "Threshold gain needs to be positive.";
92 0 : return true;
93 : }
94 0 : LOG(LS_WARNING) << "Failed to parse parameters for BweTrendlineFilter "
95 0 : "experiment from field trial string. Using default.";
96 0 : *window_size = kDefaultTrendlineWindowSize;
97 0 : *smoothing_coef = kDefaultTrendlineSmoothingCoeff;
98 0 : *threshold_gain = kDefaultTrendlineThresholdGain;
99 0 : return false;
100 : }
101 :
102 0 : bool ReadMedianSlopeFilterExperimentParameters(size_t* window_size,
103 : double* threshold_gain) {
104 0 : RTC_DCHECK(!TrendlineFilterExperimentIsEnabled());
105 0 : RTC_DCHECK(MedianSlopeFilterExperimentIsEnabled());
106 0 : RTC_DCHECK(window_size != nullptr);
107 0 : RTC_DCHECK(threshold_gain != nullptr);
108 : std::string experiment_string =
109 0 : webrtc::field_trial::FindFullName(kBweMedianSlopeFilterExperiment);
110 0 : int parsed_values = sscanf(experiment_string.c_str(), "Enabled-%zu,%lf",
111 0 : window_size, threshold_gain);
112 0 : if (parsed_values == 2) {
113 0 : RTC_CHECK_GT(*window_size, 1) << "Need at least 2 points to fit a line.";
114 0 : RTC_CHECK_GT(*threshold_gain, 0) << "Threshold gain needs to be positive.";
115 0 : return true;
116 : }
117 0 : LOG(LS_WARNING) << "Failed to parse parameters for BweMedianSlopeFilter "
118 0 : "experiment from field trial string. Using default.";
119 0 : *window_size = kDefaultMedianSlopeWindowSize;
120 0 : *threshold_gain = kDefaultMedianSlopeThresholdGain;
121 0 : return false;
122 : }
123 : } // namespace
124 :
125 : namespace webrtc {
126 :
127 0 : 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 0 : in_experiment_(BitrateEstimateExperimentIsEnabled()) {}
135 :
136 0 : void DelayBasedBwe::BitrateEstimator::Update(int64_t now_ms, int bytes) {
137 0 : if (!in_experiment_) {
138 0 : old_estimator_.Update(bytes, now_ms);
139 0 : rtc::Optional<uint32_t> rate = old_estimator_.Rate(now_ms);
140 0 : bitrate_estimate_ = -1.0f;
141 0 : if (rate)
142 0 : bitrate_estimate_ = *rate / 1000.0f;
143 0 : return;
144 : }
145 0 : 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 0 : if (bitrate_estimate_ < 0.f)
149 0 : rate_window_ms = kInitialRateWindowMs;
150 0 : float bitrate_sample = UpdateWindow(now_ms, bytes, rate_window_ms);
151 0 : if (bitrate_sample < 0.0f)
152 0 : return;
153 0 : if (bitrate_estimate_ < 0.0f) {
154 : // This is the very first sample we get. Use it to initialize the estimate.
155 0 : bitrate_estimate_ = bitrate_sample;
156 0 : 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 0 : 10.0f * std::abs(bitrate_estimate_ - bitrate_sample) / bitrate_estimate_;
162 0 : 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 0 : float pred_bitrate_estimate_var = bitrate_estimate_var_ + 5.f;
168 0 : bitrate_estimate_ = (sample_var * bitrate_estimate_ +
169 0 : pred_bitrate_estimate_var * bitrate_sample) /
170 0 : (sample_var + pred_bitrate_estimate_var);
171 0 : bitrate_estimate_var_ = sample_var * pred_bitrate_estimate_var /
172 0 : (sample_var + pred_bitrate_estimate_var);
173 : }
174 :
175 0 : float DelayBasedBwe::BitrateEstimator::UpdateWindow(int64_t now_ms,
176 : int bytes,
177 : int rate_window_ms) {
178 : // Reset if time moves backwards.
179 0 : if (now_ms < prev_time_ms_) {
180 0 : prev_time_ms_ = -1;
181 0 : sum_ = 0;
182 0 : current_win_ms_ = 0;
183 : }
184 0 : if (prev_time_ms_ >= 0) {
185 0 : current_win_ms_ += now_ms - prev_time_ms_;
186 : // Reset if nothing has been received for more than a full window.
187 0 : if (now_ms - prev_time_ms_ > rate_window_ms) {
188 0 : sum_ = 0;
189 0 : current_win_ms_ %= rate_window_ms;
190 : }
191 : }
192 0 : prev_time_ms_ = now_ms;
193 0 : float bitrate_sample = -1.0f;
194 0 : if (current_win_ms_ >= rate_window_ms) {
195 0 : bitrate_sample = 8.0f * sum_ / static_cast<float>(rate_window_ms);
196 0 : current_win_ms_ -= rate_window_ms;
197 0 : sum_ = 0;
198 : }
199 0 : sum_ += bytes;
200 0 : return bitrate_sample;
201 : }
202 :
203 0 : rtc::Optional<uint32_t> DelayBasedBwe::BitrateEstimator::bitrate_bps() const {
204 0 : if (bitrate_estimate_ < 0.f)
205 0 : return rtc::Optional<uint32_t>();
206 0 : return rtc::Optional<uint32_t>(bitrate_estimate_ * 1000);
207 : }
208 :
209 0 : DelayBasedBwe::DelayBasedBwe(Clock* clock)
210 0 : : in_trendline_experiment_(TrendlineFilterExperimentIsEnabled()),
211 0 : 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 0 : probing_interval_estimator_(&rate_control_),
225 : median_slope_window_size_(kDefaultMedianSlopeWindowSize),
226 0 : median_slope_threshold_gain_(kDefaultMedianSlopeThresholdGain) {
227 0 : if (in_trendline_experiment_) {
228 0 : ReadTrendlineFilterExperimentParameters(&trendline_window_size_,
229 : &trendline_smoothing_coeff_,
230 0 : &trendline_threshold_gain_);
231 : }
232 0 : if (in_median_slope_experiment_) {
233 0 : ReadMedianSlopeFilterExperimentParameters(&median_slope_window_size_,
234 0 : &median_slope_threshold_gain_);
235 : }
236 :
237 0 : network_thread_.DetachFromThread();
238 0 : }
239 :
240 0 : DelayBasedBwe::Result DelayBasedBwe::IncomingPacketFeedbackVector(
241 : const std::vector<PacketInfo>& packet_feedback_vector) {
242 0 : RTC_DCHECK(network_thread_.CalledOnValidThread());
243 0 : if (!uma_recorded_) {
244 0 : RTC_HISTOGRAM_ENUMERATION(kBweTypeHistogram,
245 : BweNames::kSendSideTransportSeqNum,
246 : BweNames::kBweNamesMax);
247 0 : uma_recorded_ = true;
248 : }
249 0 : Result aggregated_result;
250 0 : for (const auto& packet_info : packet_feedback_vector) {
251 0 : Result result = IncomingPacketInfo(packet_info);
252 0 : if (result.updated)
253 0 : aggregated_result = result;
254 : }
255 0 : return aggregated_result;
256 : }
257 :
258 0 : DelayBasedBwe::Result DelayBasedBwe::IncomingPacketInfo(
259 : const PacketInfo& info) {
260 0 : int64_t now_ms = clock_->TimeInMilliseconds();
261 :
262 0 : receiver_incoming_bitrate_.Update(info.arrival_time_ms, info.payload_size);
263 0 : Result result;
264 : // Reset if the stream has timed out.
265 0 : if (last_seen_packet_ms_ == -1 ||
266 0 : now_ms - last_seen_packet_ms_ > kStreamTimeOutMs) {
267 0 : inter_arrival_.reset(
268 : new InterArrival((kTimestampGroupLengthMs << kInterArrivalShift) / 1000,
269 0 : kTimestampToMs, true));
270 0 : kalman_estimator_.reset(new OveruseEstimator(OverUseDetectorOptions()));
271 0 : trendline_estimator_.reset(new TrendlineEstimator(
272 : trendline_window_size_, trendline_smoothing_coeff_,
273 0 : trendline_threshold_gain_));
274 0 : median_slope_estimator_.reset(new MedianSlopeEstimator(
275 0 : median_slope_window_size_, median_slope_threshold_gain_));
276 : }
277 0 : last_seen_packet_ms_ = now_ms;
278 :
279 : uint32_t send_time_24bits =
280 : static_cast<uint32_t>(
281 0 : ((static_cast<uint64_t>(info.send_time_ms) << kAbsSendTimeFraction) +
282 0 : 500) /
283 0 : 1000) &
284 0 : 0x00FFFFFF;
285 : // Shift up send time to use the full 32 bits that inter_arrival works with,
286 : // so wrapping works properly.
287 0 : uint32_t timestamp = send_time_24bits << kAbsSendTimeInterArrivalUpshift;
288 :
289 0 : uint32_t ts_delta = 0;
290 0 : int64_t t_delta = 0;
291 0 : int size_delta = 0;
292 0 : if (inter_arrival_->ComputeDeltas(timestamp, info.arrival_time_ms, now_ms,
293 0 : info.payload_size, &ts_delta, &t_delta,
294 : &size_delta)) {
295 0 : double ts_delta_ms = (1000.0 * ts_delta) / (1 << kInterArrivalShift);
296 0 : if (in_trendline_experiment_) {
297 0 : trendline_estimator_->Update(t_delta, ts_delta_ms, info.arrival_time_ms);
298 0 : detector_.Detect(trendline_estimator_->trendline_slope(), ts_delta_ms,
299 0 : trendline_estimator_->num_of_deltas(),
300 0 : info.arrival_time_ms);
301 0 : } else if (in_median_slope_experiment_) {
302 0 : median_slope_estimator_->Update(t_delta, ts_delta_ms,
303 0 : info.arrival_time_ms);
304 0 : detector_.Detect(median_slope_estimator_->trendline_slope(), ts_delta_ms,
305 0 : median_slope_estimator_->num_of_deltas(),
306 0 : info.arrival_time_ms);
307 : } else {
308 0 : kalman_estimator_->Update(t_delta, ts_delta_ms, size_delta,
309 0 : detector_.State(), info.arrival_time_ms);
310 0 : detector_.Detect(kalman_estimator_->offset(), ts_delta_ms,
311 0 : kalman_estimator_->num_of_deltas(),
312 0 : info.arrival_time_ms);
313 : }
314 : }
315 :
316 0 : int probing_bps = 0;
317 0 : if (info.probe_cluster_id != PacketInfo::kNotAProbe) {
318 0 : probing_bps = probe_bitrate_estimator_.HandleProbeAndEstimateBitrate(info);
319 : }
320 : rtc::Optional<uint32_t> acked_bitrate_bps =
321 0 : receiver_incoming_bitrate_.bitrate_bps();
322 : // Currently overusing the bandwidth.
323 0 : if (detector_.State() == kBwOverusing) {
324 0 : if (acked_bitrate_bps &&
325 0 : rate_control_.TimeToReduceFurther(now_ms, *acked_bitrate_bps)) {
326 0 : result.updated =
327 0 : UpdateEstimate(info.arrival_time_ms, now_ms, acked_bitrate_bps,
328 : &result.target_bitrate_bps);
329 : }
330 0 : } else if (probing_bps > 0) {
331 : // No overuse, but probing measured a bitrate.
332 0 : rate_control_.SetEstimate(probing_bps, info.arrival_time_ms);
333 0 : result.probe = true;
334 0 : result.updated =
335 0 : UpdateEstimate(info.arrival_time_ms, now_ms, acked_bitrate_bps,
336 : &result.target_bitrate_bps);
337 : }
338 0 : if (!result.updated &&
339 0 : (last_update_ms_ == -1 ||
340 0 : now_ms - last_update_ms_ > rate_control_.GetFeedbackInterval())) {
341 0 : result.updated =
342 0 : UpdateEstimate(info.arrival_time_ms, now_ms, acked_bitrate_bps,
343 : &result.target_bitrate_bps);
344 : }
345 0 : if (result.updated) {
346 0 : last_update_ms_ = now_ms;
347 : BWE_TEST_LOGGING_PLOT(1, "target_bitrate_bps", now_ms,
348 : result.target_bitrate_bps);
349 : }
350 :
351 0 : return result;
352 : }
353 :
354 0 : 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 0 : const RateControlInput input(detector_.State(), acked_bitrate_bps, 0);
361 0 : rate_control_.Update(&input, now_ms);
362 0 : *target_bitrate_bps = rate_control_.UpdateBandwidthEstimate(now_ms);
363 0 : return rate_control_.ValidEstimate();
364 : }
365 :
366 0 : void DelayBasedBwe::OnRttUpdate(int64_t avg_rtt_ms, int64_t max_rtt_ms) {
367 0 : rate_control_.SetRtt(avg_rtt_ms);
368 0 : }
369 :
370 0 : 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 0 : RTC_DCHECK(ssrcs);
377 0 : RTC_DCHECK(bitrate_bps);
378 0 : if (!rate_control_.ValidEstimate())
379 0 : return false;
380 :
381 0 : *ssrcs = {kFixedSsrc};
382 0 : *bitrate_bps = rate_control_.LatestEstimate();
383 0 : return true;
384 : }
385 :
386 0 : 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 0 : rate_control_.SetMinBitrate(min_bitrate_bps);
390 0 : }
391 :
392 0 : int64_t DelayBasedBwe::GetProbingIntervalMs() const {
393 0 : return probing_interval_estimator_.GetIntervalMs();
394 : }
395 : } // namespace webrtc
|
