1 /*
2 * Copyright (c) 2014 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/remote_bitrate_estimator/aimd_rate_control.h"
12
13 #include <inttypes.h>
14
15 #include <algorithm>
16 #include <cmath>
17 #include <cstdio>
18 #include <string>
19
20 #include "absl/strings/match.h"
21 #include "api/transport/network_types.h"
22 #include "api/units/data_rate.h"
23 #include "modules/remote_bitrate_estimator/include/bwe_defines.h"
24 #include "modules/remote_bitrate_estimator/overuse_detector.h"
25 #include "rtc_base/checks.h"
26 #include "rtc_base/experiments/field_trial_parser.h"
27 #include "rtc_base/logging.h"
28 #include "rtc_base/numerics/safe_minmax.h"
29
30 namespace webrtc {
31 namespace {
32
33 constexpr TimeDelta kDefaultRtt = TimeDelta::Millis(200);
34 constexpr double kDefaultBackoffFactor = 0.85;
35
36 constexpr char kBweBackOffFactorExperiment[] = "WebRTC-BweBackOffFactor";
37
IsEnabled(const FieldTrialsView & field_trials,absl::string_view key)38 bool IsEnabled(const FieldTrialsView& field_trials, absl::string_view key) {
39 return absl::StartsWith(field_trials.Lookup(key), "Enabled");
40 }
41
IsNotDisabled(const FieldTrialsView & field_trials,absl::string_view key)42 bool IsNotDisabled(const FieldTrialsView& field_trials, absl::string_view key) {
43 return !absl::StartsWith(field_trials.Lookup(key), "Disabled");
44 }
45
ReadBackoffFactor(const FieldTrialsView & key_value_config)46 double ReadBackoffFactor(const FieldTrialsView& key_value_config) {
47 std::string experiment_string =
48 key_value_config.Lookup(kBweBackOffFactorExperiment);
49 double backoff_factor;
50 int parsed_values =
51 sscanf(experiment_string.c_str(), "Enabled-%lf", &backoff_factor);
52 if (parsed_values == 1) {
53 if (backoff_factor >= 1.0) {
54 RTC_LOG(LS_WARNING) << "Back-off factor must be less than 1.";
55 } else if (backoff_factor <= 0.0) {
56 RTC_LOG(LS_WARNING) << "Back-off factor must be greater than 0.";
57 } else {
58 return backoff_factor;
59 }
60 }
61 RTC_LOG(LS_WARNING) << "Failed to parse parameters for AimdRateControl "
62 "experiment from field trial string. Using default.";
63 return kDefaultBackoffFactor;
64 }
65
66 } // namespace
67
AimdRateControl(const FieldTrialsView * key_value_config)68 AimdRateControl::AimdRateControl(const FieldTrialsView* key_value_config)
69 : AimdRateControl(key_value_config, /* send_side =*/false) {}
70
AimdRateControl(const FieldTrialsView * key_value_config,bool send_side)71 AimdRateControl::AimdRateControl(const FieldTrialsView* key_value_config,
72 bool send_side)
73 : min_configured_bitrate_(kCongestionControllerMinBitrate),
74 max_configured_bitrate_(DataRate::KilobitsPerSec(30000)),
75 current_bitrate_(max_configured_bitrate_),
76 latest_estimated_throughput_(current_bitrate_),
77 link_capacity_(),
78 rate_control_state_(RateControlState::kRcHold),
79 time_last_bitrate_change_(Timestamp::MinusInfinity()),
80 time_last_bitrate_decrease_(Timestamp::MinusInfinity()),
81 time_first_throughput_estimate_(Timestamp::MinusInfinity()),
82 bitrate_is_initialized_(false),
83 beta_(IsEnabled(*key_value_config, kBweBackOffFactorExperiment)
84 ? ReadBackoffFactor(*key_value_config)
85 : kDefaultBackoffFactor),
86 in_alr_(false),
87 rtt_(kDefaultRtt),
88 send_side_(send_side),
89 no_bitrate_increase_in_alr_(
90 IsEnabled(*key_value_config,
91 "WebRTC-DontIncreaseDelayBasedBweInAlr")),
92 estimate_bounded_backoff_(
93 IsNotDisabled(*key_value_config,
94 "WebRTC-Bwe-EstimateBoundedBackoff")),
95 initial_backoff_interval_("initial_backoff_interval"),
96 link_capacity_fix_("link_capacity_fix") {
97 ParseFieldTrial(
98 {&disable_estimate_bounded_increase_, &estimate_bounded_increase_ratio_,
99 &ignore_throughput_limit_if_network_estimate_,
100 &ignore_network_estimate_decrease_, &increase_to_network_estimate_},
101 key_value_config->Lookup("WebRTC-Bwe-EstimateBoundedIncrease"));
102 // E.g
103 // WebRTC-BweAimdRateControlConfig/initial_backoff_interval:100ms/
104 ParseFieldTrial({&initial_backoff_interval_, &link_capacity_fix_},
105 key_value_config->Lookup("WebRTC-BweAimdRateControlConfig"));
106 if (initial_backoff_interval_) {
107 RTC_LOG(LS_INFO) << "Using aimd rate control with initial back-off interval"
108 " "
109 << ToString(*initial_backoff_interval_) << ".";
110 }
111 RTC_LOG(LS_INFO) << "Using aimd rate control with back off factor " << beta_;
112 }
113
~AimdRateControl()114 AimdRateControl::~AimdRateControl() {}
115
SetStartBitrate(DataRate start_bitrate)116 void AimdRateControl::SetStartBitrate(DataRate start_bitrate) {
117 current_bitrate_ = start_bitrate;
118 latest_estimated_throughput_ = current_bitrate_;
119 bitrate_is_initialized_ = true;
120 }
121
SetMinBitrate(DataRate min_bitrate)122 void AimdRateControl::SetMinBitrate(DataRate min_bitrate) {
123 min_configured_bitrate_ = min_bitrate;
124 current_bitrate_ = std::max(min_bitrate, current_bitrate_);
125 }
126
ValidEstimate() const127 bool AimdRateControl::ValidEstimate() const {
128 return bitrate_is_initialized_;
129 }
130
GetFeedbackInterval() const131 TimeDelta AimdRateControl::GetFeedbackInterval() const {
132 // Estimate how often we can send RTCP if we allocate up to 5% of bandwidth
133 // to feedback.
134 const DataSize kRtcpSize = DataSize::Bytes(80);
135 const DataRate rtcp_bitrate = current_bitrate_ * 0.05;
136 const TimeDelta interval = kRtcpSize / rtcp_bitrate;
137 const TimeDelta kMinFeedbackInterval = TimeDelta::Millis(200);
138 const TimeDelta kMaxFeedbackInterval = TimeDelta::Millis(1000);
139 return interval.Clamped(kMinFeedbackInterval, kMaxFeedbackInterval);
140 }
141
TimeToReduceFurther(Timestamp at_time,DataRate estimated_throughput) const142 bool AimdRateControl::TimeToReduceFurther(Timestamp at_time,
143 DataRate estimated_throughput) const {
144 const TimeDelta bitrate_reduction_interval =
145 rtt_.Clamped(TimeDelta::Millis(10), TimeDelta::Millis(200));
146 if (at_time - time_last_bitrate_change_ >= bitrate_reduction_interval) {
147 return true;
148 }
149 if (ValidEstimate()) {
150 // TODO(terelius/holmer): Investigate consequences of increasing
151 // the threshold to 0.95 * LatestEstimate().
152 const DataRate threshold = 0.5 * LatestEstimate();
153 return estimated_throughput < threshold;
154 }
155 return false;
156 }
157
InitialTimeToReduceFurther(Timestamp at_time) const158 bool AimdRateControl::InitialTimeToReduceFurther(Timestamp at_time) const {
159 if (!initial_backoff_interval_) {
160 return ValidEstimate() &&
161 TimeToReduceFurther(at_time,
162 LatestEstimate() / 2 - DataRate::BitsPerSec(1));
163 }
164 // TODO(terelius): We could use the RTT (clamped to suitable limits) instead
165 // of a fixed bitrate_reduction_interval.
166 if (time_last_bitrate_decrease_.IsInfinite() ||
167 at_time - time_last_bitrate_decrease_ >= *initial_backoff_interval_) {
168 return true;
169 }
170 return false;
171 }
172
LatestEstimate() const173 DataRate AimdRateControl::LatestEstimate() const {
174 return current_bitrate_;
175 }
176
SetRtt(TimeDelta rtt)177 void AimdRateControl::SetRtt(TimeDelta rtt) {
178 rtt_ = rtt;
179 }
180
Update(const RateControlInput * input,Timestamp at_time)181 DataRate AimdRateControl::Update(const RateControlInput* input,
182 Timestamp at_time) {
183 RTC_CHECK(input);
184
185 // Set the initial bit rate value to what we're receiving the first half
186 // second.
187 // TODO(bugs.webrtc.org/9379): The comment above doesn't match to the code.
188 if (!bitrate_is_initialized_) {
189 const TimeDelta kInitializationTime = TimeDelta::Seconds(5);
190 RTC_DCHECK_LE(kBitrateWindowMs, kInitializationTime.ms());
191 if (time_first_throughput_estimate_.IsInfinite()) {
192 if (input->estimated_throughput)
193 time_first_throughput_estimate_ = at_time;
194 } else if (at_time - time_first_throughput_estimate_ >
195 kInitializationTime &&
196 input->estimated_throughput) {
197 current_bitrate_ = *input->estimated_throughput;
198 bitrate_is_initialized_ = true;
199 }
200 }
201
202 ChangeBitrate(*input, at_time);
203 return current_bitrate_;
204 }
205
SetInApplicationLimitedRegion(bool in_alr)206 void AimdRateControl::SetInApplicationLimitedRegion(bool in_alr) {
207 in_alr_ = in_alr;
208 }
209
SetEstimate(DataRate bitrate,Timestamp at_time)210 void AimdRateControl::SetEstimate(DataRate bitrate, Timestamp at_time) {
211 bitrate_is_initialized_ = true;
212 DataRate prev_bitrate = current_bitrate_;
213 current_bitrate_ = ClampBitrate(bitrate);
214 time_last_bitrate_change_ = at_time;
215 if (current_bitrate_ < prev_bitrate) {
216 time_last_bitrate_decrease_ = at_time;
217 }
218 }
219
SetNetworkStateEstimate(const absl::optional<NetworkStateEstimate> & estimate)220 void AimdRateControl::SetNetworkStateEstimate(
221 const absl::optional<NetworkStateEstimate>& estimate) {
222 network_estimate_ = estimate;
223 }
224
GetNearMaxIncreaseRateBpsPerSecond() const225 double AimdRateControl::GetNearMaxIncreaseRateBpsPerSecond() const {
226 RTC_DCHECK(!current_bitrate_.IsZero());
227 const TimeDelta kFrameInterval = TimeDelta::Seconds(1) / 30;
228 DataSize frame_size = current_bitrate_ * kFrameInterval;
229 const DataSize kPacketSize = DataSize::Bytes(1200);
230 double packets_per_frame = std::ceil(frame_size / kPacketSize);
231 DataSize avg_packet_size = frame_size / packets_per_frame;
232
233 // Approximate the over-use estimator delay to 100 ms.
234 TimeDelta response_time = rtt_ + TimeDelta::Millis(100);
235
236 response_time = response_time * 2;
237 double increase_rate_bps_per_second =
238 (avg_packet_size / response_time).bps<double>();
239 double kMinIncreaseRateBpsPerSecond = 4000;
240 return std::max(kMinIncreaseRateBpsPerSecond, increase_rate_bps_per_second);
241 }
242
GetExpectedBandwidthPeriod() const243 TimeDelta AimdRateControl::GetExpectedBandwidthPeriod() const {
244 const TimeDelta kMinPeriod = TimeDelta::Seconds(2);
245 const TimeDelta kDefaultPeriod = TimeDelta::Seconds(3);
246 const TimeDelta kMaxPeriod = TimeDelta::Seconds(50);
247
248 double increase_rate_bps_per_second = GetNearMaxIncreaseRateBpsPerSecond();
249 if (!last_decrease_)
250 return kDefaultPeriod;
251 double time_to_recover_decrease_seconds =
252 last_decrease_->bps() / increase_rate_bps_per_second;
253 TimeDelta period = TimeDelta::Seconds(time_to_recover_decrease_seconds);
254 return period.Clamped(kMinPeriod, kMaxPeriod);
255 }
256
ChangeBitrate(const RateControlInput & input,Timestamp at_time)257 void AimdRateControl::ChangeBitrate(const RateControlInput& input,
258 Timestamp at_time) {
259 absl::optional<DataRate> new_bitrate;
260 DataRate estimated_throughput =
261 input.estimated_throughput.value_or(latest_estimated_throughput_);
262 if (input.estimated_throughput)
263 latest_estimated_throughput_ = *input.estimated_throughput;
264
265 // An over-use should always trigger us to reduce the bitrate, even though
266 // we have not yet established our first estimate. By acting on the over-use,
267 // we will end up with a valid estimate.
268 if (!bitrate_is_initialized_ &&
269 input.bw_state != BandwidthUsage::kBwOverusing)
270 return;
271
272 ChangeState(input, at_time);
273
274 switch (rate_control_state_) {
275 case RateControlState::kRcHold:
276 break;
277
278 case RateControlState::kRcIncrease: {
279 if (estimated_throughput > link_capacity_.UpperBound())
280 link_capacity_.Reset();
281
282 // We limit the new bitrate based on the troughput to avoid unlimited
283 // bitrate increases. We allow a bit more lag at very low rates to not too
284 // easily get stuck if the encoder produces uneven outputs.
285 DataRate increase_limit =
286 1.5 * estimated_throughput + DataRate::KilobitsPerSec(10);
287 if (ignore_throughput_limit_if_network_estimate_ && network_estimate_ &&
288 network_estimate_->link_capacity_upper.IsFinite()) {
289 // If we have a Network estimate, we do allow the estimate to increase.
290 increase_limit = network_estimate_->link_capacity_upper *
291 estimate_bounded_increase_ratio_.Get();
292 } else if (send_side_ && in_alr_ && no_bitrate_increase_in_alr_) {
293 // Do not increase the delay based estimate in alr since the estimator
294 // will not be able to get transport feedback necessary to detect if
295 // the new estimate is correct.
296 // If we have previously increased above the limit (for instance due to
297 // probing), we don't allow further changes.
298 increase_limit = current_bitrate_;
299 }
300
301 if (current_bitrate_ < increase_limit) {
302 DataRate increased_bitrate = DataRate::MinusInfinity();
303 if (increase_to_network_estimate_ && network_estimate_ &&
304 network_estimate_->link_capacity_upper.IsFinite()) {
305 increased_bitrate = increase_limit;
306 } else if (link_capacity_.has_estimate()) {
307 // The link_capacity estimate is reset if the measured throughput
308 // is too far from the estimate. We can therefore assume that our
309 // target rate is reasonably close to link capacity and use additive
310 // increase.
311 DataRate additive_increase =
312 AdditiveRateIncrease(at_time, time_last_bitrate_change_);
313 increased_bitrate = current_bitrate_ + additive_increase;
314 } else {
315 // If we don't have an estimate of the link capacity, use faster ramp
316 // up to discover the capacity.
317 DataRate multiplicative_increase = MultiplicativeRateIncrease(
318 at_time, time_last_bitrate_change_, current_bitrate_);
319 increased_bitrate = current_bitrate_ + multiplicative_increase;
320 }
321 new_bitrate = std::min(increased_bitrate, increase_limit);
322 }
323 time_last_bitrate_change_ = at_time;
324 break;
325 }
326
327 case RateControlState::kRcDecrease: {
328 DataRate decreased_bitrate = DataRate::PlusInfinity();
329
330 // Set bit rate to something slightly lower than the measured throughput
331 // to get rid of any self-induced delay.
332 decreased_bitrate = estimated_throughput * beta_;
333 if (decreased_bitrate > current_bitrate_ && !link_capacity_fix_) {
334 // TODO(terelius): The link_capacity estimate may be based on old
335 // throughput measurements. Relying on them may lead to unnecessary
336 // BWE drops.
337 if (link_capacity_.has_estimate()) {
338 decreased_bitrate = beta_ * link_capacity_.estimate();
339 }
340 }
341 // Avoid increasing the rate when over-using.
342 if (decreased_bitrate < current_bitrate_) {
343 new_bitrate = decreased_bitrate;
344 }
345
346 if (bitrate_is_initialized_ && estimated_throughput < current_bitrate_) {
347 if (!new_bitrate.has_value()) {
348 last_decrease_ = DataRate::Zero();
349 } else {
350 last_decrease_ = current_bitrate_ - *new_bitrate;
351 }
352 }
353 if (estimated_throughput < link_capacity_.LowerBound()) {
354 // The current throughput is far from the estimated link capacity. Clear
355 // the estimate to allow an immediate update in OnOveruseDetected.
356 link_capacity_.Reset();
357 }
358
359 bitrate_is_initialized_ = true;
360 link_capacity_.OnOveruseDetected(estimated_throughput);
361 // Stay on hold until the pipes are cleared.
362 rate_control_state_ = RateControlState::kRcHold;
363 time_last_bitrate_change_ = at_time;
364 time_last_bitrate_decrease_ = at_time;
365 break;
366 }
367 default:
368 RTC_DCHECK_NOTREACHED();
369 }
370
371 current_bitrate_ = ClampBitrate(new_bitrate.value_or(current_bitrate_));
372 }
373
ClampBitrate(DataRate new_bitrate) const374 DataRate AimdRateControl::ClampBitrate(DataRate new_bitrate) const {
375 if (!disable_estimate_bounded_increase_ && network_estimate_ &&
376 network_estimate_->link_capacity_upper.IsFinite()) {
377 DataRate upper_bound = network_estimate_->link_capacity_upper *
378 estimate_bounded_increase_ratio_.Get();
379 if (ignore_network_estimate_decrease_) {
380 upper_bound = std::max(upper_bound, current_bitrate_);
381 }
382 new_bitrate = std::min(upper_bound, new_bitrate);
383 }
384 if (estimate_bounded_backoff_ && network_estimate_ &&
385 network_estimate_->link_capacity_lower.IsFinite() &&
386 new_bitrate < current_bitrate_) {
387 new_bitrate = std::min(
388 current_bitrate_,
389 std::max(new_bitrate, network_estimate_->link_capacity_lower * beta_));
390 }
391 new_bitrate = std::max(new_bitrate, min_configured_bitrate_);
392 return new_bitrate;
393 }
394
MultiplicativeRateIncrease(Timestamp at_time,Timestamp last_time,DataRate current_bitrate) const395 DataRate AimdRateControl::MultiplicativeRateIncrease(
396 Timestamp at_time,
397 Timestamp last_time,
398 DataRate current_bitrate) const {
399 double alpha = 1.08;
400 if (last_time.IsFinite()) {
401 auto time_since_last_update = at_time - last_time;
402 alpha = pow(alpha, std::min(time_since_last_update.seconds<double>(), 1.0));
403 }
404 DataRate multiplicative_increase =
405 std::max(current_bitrate * (alpha - 1.0), DataRate::BitsPerSec(1000));
406 return multiplicative_increase;
407 }
408
AdditiveRateIncrease(Timestamp at_time,Timestamp last_time) const409 DataRate AimdRateControl::AdditiveRateIncrease(Timestamp at_time,
410 Timestamp last_time) const {
411 double time_period_seconds = (at_time - last_time).seconds<double>();
412 double data_rate_increase_bps =
413 GetNearMaxIncreaseRateBpsPerSecond() * time_period_seconds;
414 return DataRate::BitsPerSec(data_rate_increase_bps);
415 }
416
ChangeState(const RateControlInput & input,Timestamp at_time)417 void AimdRateControl::ChangeState(const RateControlInput& input,
418 Timestamp at_time) {
419 switch (input.bw_state) {
420 case BandwidthUsage::kBwNormal:
421 if (rate_control_state_ == RateControlState::kRcHold) {
422 time_last_bitrate_change_ = at_time;
423 rate_control_state_ = RateControlState::kRcIncrease;
424 }
425 break;
426 case BandwidthUsage::kBwOverusing:
427 if (rate_control_state_ != RateControlState::kRcDecrease) {
428 rate_control_state_ = RateControlState::kRcDecrease;
429 }
430 break;
431 case BandwidthUsage::kBwUnderusing:
432 rate_control_state_ = RateControlState::kRcHold;
433 break;
434 default:
435 RTC_DCHECK_NOTREACHED();
436 }
437 }
438
439 } // namespace webrtc
440