diff options
Diffstat (limited to 'third_party/libwebrtc/modules/remote_bitrate_estimator/aimd_rate_control.cc')
-rw-r--r-- | third_party/libwebrtc/modules/remote_bitrate_estimator/aimd_rate_control.cc | 401 |
1 files changed, 401 insertions, 0 deletions
diff --git a/third_party/libwebrtc/modules/remote_bitrate_estimator/aimd_rate_control.cc b/third_party/libwebrtc/modules/remote_bitrate_estimator/aimd_rate_control.cc new file mode 100644 index 0000000000..fde66657e7 --- /dev/null +++ b/third_party/libwebrtc/modules/remote_bitrate_estimator/aimd_rate_control.cc @@ -0,0 +1,401 @@ +/* + * Copyright (c) 2014 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "modules/remote_bitrate_estimator/aimd_rate_control.h" + +#include <inttypes.h> + +#include <algorithm> +#include <cmath> +#include <cstdio> +#include <string> + +#include "absl/strings/match.h" +#include "api/transport/network_types.h" +#include "api/units/data_rate.h" +#include "modules/remote_bitrate_estimator/include/bwe_defines.h" +#include "modules/remote_bitrate_estimator/overuse_detector.h" +#include "rtc_base/checks.h" +#include "rtc_base/experiments/field_trial_parser.h" +#include "rtc_base/logging.h" +#include "rtc_base/numerics/safe_minmax.h" + +namespace webrtc { +namespace { + +constexpr TimeDelta kDefaultRtt = TimeDelta::Millis(200); +constexpr double kDefaultBackoffFactor = 0.85; + +constexpr char kBweBackOffFactorExperiment[] = "WebRTC-BweBackOffFactor"; + +double ReadBackoffFactor(const FieldTrialsView& key_value_config) { + std::string experiment_string = + key_value_config.Lookup(kBweBackOffFactorExperiment); + double backoff_factor; + int parsed_values = + sscanf(experiment_string.c_str(), "Enabled-%lf", &backoff_factor); + if (parsed_values == 1) { + if (backoff_factor >= 1.0) { + RTC_LOG(LS_WARNING) << "Back-off factor must be less than 1."; + } else if (backoff_factor <= 0.0) { + RTC_LOG(LS_WARNING) << "Back-off factor must be greater than 0."; + } else { + return backoff_factor; + } + } + RTC_LOG(LS_WARNING) << "Failed to parse parameters for AimdRateControl " + "experiment from field trial string. Using default."; + return kDefaultBackoffFactor; +} + +} // namespace + +AimdRateControl::AimdRateControl(const FieldTrialsView& key_value_config) + : AimdRateControl(key_value_config, /* send_side =*/false) {} + +AimdRateControl::AimdRateControl(const FieldTrialsView& key_value_config, + bool send_side) + : min_configured_bitrate_(kCongestionControllerMinBitrate), + max_configured_bitrate_(DataRate::KilobitsPerSec(30000)), + current_bitrate_(max_configured_bitrate_), + latest_estimated_throughput_(current_bitrate_), + link_capacity_(), + rate_control_state_(RateControlState::kRcHold), + time_last_bitrate_change_(Timestamp::MinusInfinity()), + time_last_bitrate_decrease_(Timestamp::MinusInfinity()), + time_first_throughput_estimate_(Timestamp::MinusInfinity()), + bitrate_is_initialized_(false), + beta_(key_value_config.IsEnabled(kBweBackOffFactorExperiment) + ? ReadBackoffFactor(key_value_config) + : kDefaultBackoffFactor), + in_alr_(false), + rtt_(kDefaultRtt), + send_side_(send_side), + no_bitrate_increase_in_alr_( + key_value_config.IsEnabled("WebRTC-DontIncreaseDelayBasedBweInAlr")), + subtract_additional_backoff_term_(!key_value_config.IsDisabled( + "WebRTC-Bwe-SubtractAdditionalBackoffTerm")) { + ParseFieldTrial( + {&disable_estimate_bounded_increase_, + &use_current_estimate_as_min_upper_bound_}, + key_value_config.Lookup("WebRTC-Bwe-EstimateBoundedIncrease")); + RTC_LOG(LS_INFO) << "Using aimd rate control with back off factor " << beta_; +} + +AimdRateControl::~AimdRateControl() {} + +void AimdRateControl::SetStartBitrate(DataRate start_bitrate) { + current_bitrate_ = start_bitrate; + latest_estimated_throughput_ = current_bitrate_; + bitrate_is_initialized_ = true; +} + +void AimdRateControl::SetMinBitrate(DataRate min_bitrate) { + min_configured_bitrate_ = min_bitrate; + current_bitrate_ = std::max(min_bitrate, current_bitrate_); +} + +bool AimdRateControl::ValidEstimate() const { + return bitrate_is_initialized_; +} + +TimeDelta AimdRateControl::GetFeedbackInterval() const { + // Estimate how often we can send RTCP if we allocate up to 5% of bandwidth + // to feedback. + const DataSize kRtcpSize = DataSize::Bytes(80); + const DataRate rtcp_bitrate = current_bitrate_ * 0.05; + const TimeDelta interval = kRtcpSize / rtcp_bitrate; + const TimeDelta kMinFeedbackInterval = TimeDelta::Millis(200); + const TimeDelta kMaxFeedbackInterval = TimeDelta::Millis(1000); + return interval.Clamped(kMinFeedbackInterval, kMaxFeedbackInterval); +} + +bool AimdRateControl::TimeToReduceFurther(Timestamp at_time, + DataRate estimated_throughput) const { + const TimeDelta bitrate_reduction_interval = + rtt_.Clamped(TimeDelta::Millis(10), TimeDelta::Millis(200)); + if (at_time - time_last_bitrate_change_ >= bitrate_reduction_interval) { + return true; + } + if (ValidEstimate()) { + // TODO(terelius/holmer): Investigate consequences of increasing + // the threshold to 0.95 * LatestEstimate(). + const DataRate threshold = 0.5 * LatestEstimate(); + return estimated_throughput < threshold; + } + return false; +} + +bool AimdRateControl::InitialTimeToReduceFurther(Timestamp at_time) const { + return ValidEstimate() && + TimeToReduceFurther(at_time, + LatestEstimate() / 2 - DataRate::BitsPerSec(1)); +} + +DataRate AimdRateControl::LatestEstimate() const { + return current_bitrate_; +} + +void AimdRateControl::SetRtt(TimeDelta rtt) { + rtt_ = rtt; +} + +DataRate AimdRateControl::Update(const RateControlInput& input, + Timestamp at_time) { + // Set the initial bit rate value to what we're receiving the first half + // second. + // TODO(bugs.webrtc.org/9379): The comment above doesn't match to the code. + if (!bitrate_is_initialized_) { + const TimeDelta kInitializationTime = TimeDelta::Seconds(5); + RTC_DCHECK_LE(kBitrateWindow, kInitializationTime); + if (time_first_throughput_estimate_.IsInfinite()) { + if (input.estimated_throughput) + time_first_throughput_estimate_ = at_time; + } else if (at_time - time_first_throughput_estimate_ > + kInitializationTime && + input.estimated_throughput) { + current_bitrate_ = *input.estimated_throughput; + bitrate_is_initialized_ = true; + } + } + + ChangeBitrate(input, at_time); + return current_bitrate_; +} + +void AimdRateControl::SetInApplicationLimitedRegion(bool in_alr) { + in_alr_ = in_alr; +} + +void AimdRateControl::SetEstimate(DataRate bitrate, Timestamp at_time) { + bitrate_is_initialized_ = true; + DataRate prev_bitrate = current_bitrate_; + current_bitrate_ = ClampBitrate(bitrate); + time_last_bitrate_change_ = at_time; + if (current_bitrate_ < prev_bitrate) { + time_last_bitrate_decrease_ = at_time; + } +} + +void AimdRateControl::SetNetworkStateEstimate( + const absl::optional<NetworkStateEstimate>& estimate) { + network_estimate_ = estimate; +} + +double AimdRateControl::GetNearMaxIncreaseRateBpsPerSecond() const { + RTC_DCHECK(!current_bitrate_.IsZero()); + const TimeDelta kFrameInterval = TimeDelta::Seconds(1) / 30; + DataSize frame_size = current_bitrate_ * kFrameInterval; + const DataSize kPacketSize = DataSize::Bytes(1200); + double packets_per_frame = std::ceil(frame_size / kPacketSize); + DataSize avg_packet_size = frame_size / packets_per_frame; + + // Approximate the over-use estimator delay to 100 ms. + TimeDelta response_time = rtt_ + TimeDelta::Millis(100); + + response_time = response_time * 2; + double increase_rate_bps_per_second = + (avg_packet_size / response_time).bps<double>(); + double kMinIncreaseRateBpsPerSecond = 4000; + return std::max(kMinIncreaseRateBpsPerSecond, increase_rate_bps_per_second); +} + +TimeDelta AimdRateControl::GetExpectedBandwidthPeriod() const { + const TimeDelta kMinPeriod = TimeDelta::Seconds(2); + const TimeDelta kDefaultPeriod = TimeDelta::Seconds(3); + const TimeDelta kMaxPeriod = TimeDelta::Seconds(50); + + double increase_rate_bps_per_second = GetNearMaxIncreaseRateBpsPerSecond(); + if (!last_decrease_) + return kDefaultPeriod; + double time_to_recover_decrease_seconds = + last_decrease_->bps() / increase_rate_bps_per_second; + TimeDelta period = TimeDelta::Seconds(time_to_recover_decrease_seconds); + return period.Clamped(kMinPeriod, kMaxPeriod); +} + +void AimdRateControl::ChangeBitrate(const RateControlInput& input, + Timestamp at_time) { + absl::optional<DataRate> new_bitrate; + DataRate estimated_throughput = + input.estimated_throughput.value_or(latest_estimated_throughput_); + if (input.estimated_throughput) + latest_estimated_throughput_ = *input.estimated_throughput; + + // An over-use should always trigger us to reduce the bitrate, even though + // we have not yet established our first estimate. By acting on the over-use, + // we will end up with a valid estimate. + if (!bitrate_is_initialized_ && + input.bw_state != BandwidthUsage::kBwOverusing) + return; + + ChangeState(input, at_time); + + switch (rate_control_state_) { + case RateControlState::kRcHold: + break; + + case RateControlState::kRcIncrease: { + if (estimated_throughput > link_capacity_.UpperBound()) + link_capacity_.Reset(); + + // We limit the new bitrate based on the troughput to avoid unlimited + // bitrate increases. We allow a bit more lag at very low rates to not too + // easily get stuck if the encoder produces uneven outputs. + DataRate increase_limit = + 1.5 * estimated_throughput + DataRate::KilobitsPerSec(10); + if (send_side_ && in_alr_ && no_bitrate_increase_in_alr_) { + // Do not increase the delay based estimate in alr since the estimator + // will not be able to get transport feedback necessary to detect if + // the new estimate is correct. + // If we have previously increased above the limit (for instance due to + // probing), we don't allow further changes. + increase_limit = current_bitrate_; + } + + if (current_bitrate_ < increase_limit) { + DataRate increased_bitrate = DataRate::MinusInfinity(); + if (link_capacity_.has_estimate()) { + // The link_capacity estimate is reset if the measured throughput + // is too far from the estimate. We can therefore assume that our + // target rate is reasonably close to link capacity and use additive + // increase. + DataRate additive_increase = + AdditiveRateIncrease(at_time, time_last_bitrate_change_); + increased_bitrate = current_bitrate_ + additive_increase; + } else { + // If we don't have an estimate of the link capacity, use faster ramp + // up to discover the capacity. + DataRate multiplicative_increase = MultiplicativeRateIncrease( + at_time, time_last_bitrate_change_, current_bitrate_); + increased_bitrate = current_bitrate_ + multiplicative_increase; + } + new_bitrate = std::min(increased_bitrate, increase_limit); + } + time_last_bitrate_change_ = at_time; + break; + } + + case RateControlState::kRcDecrease: { + DataRate decreased_bitrate = DataRate::PlusInfinity(); + + // Set bit rate to something slightly lower than the measured throughput + // to get rid of any self-induced delay. + decreased_bitrate = estimated_throughput * beta_; + if (decreased_bitrate > DataRate::KilobitsPerSec(5) && + subtract_additional_backoff_term_) { + decreased_bitrate -= DataRate::KilobitsPerSec(5); + } + + if (decreased_bitrate > current_bitrate_) { + // TODO(terelius): The link_capacity estimate may be based on old + // throughput measurements. Relying on them may lead to unnecessary + // BWE drops. + if (link_capacity_.has_estimate()) { + decreased_bitrate = beta_ * link_capacity_.estimate(); + } + } + // Avoid increasing the rate when over-using. + if (decreased_bitrate < current_bitrate_) { + new_bitrate = decreased_bitrate; + } + + if (bitrate_is_initialized_ && estimated_throughput < current_bitrate_) { + if (!new_bitrate.has_value()) { + last_decrease_ = DataRate::Zero(); + } else { + last_decrease_ = current_bitrate_ - *new_bitrate; + } + } + if (estimated_throughput < link_capacity_.LowerBound()) { + // The current throughput is far from the estimated link capacity. Clear + // the estimate to allow an immediate update in OnOveruseDetected. + link_capacity_.Reset(); + } + + bitrate_is_initialized_ = true; + link_capacity_.OnOveruseDetected(estimated_throughput); + // Stay on hold until the pipes are cleared. + rate_control_state_ = RateControlState::kRcHold; + time_last_bitrate_change_ = at_time; + time_last_bitrate_decrease_ = at_time; + break; + } + default: + RTC_DCHECK_NOTREACHED(); + } + + current_bitrate_ = ClampBitrate(new_bitrate.value_or(current_bitrate_)); +} + +DataRate AimdRateControl::ClampBitrate(DataRate new_bitrate) const { + if (!disable_estimate_bounded_increase_ && network_estimate_ && + network_estimate_->link_capacity_upper.IsFinite()) { + DataRate upper_bound = + use_current_estimate_as_min_upper_bound_ + ? std::max(network_estimate_->link_capacity_upper, current_bitrate_) + : network_estimate_->link_capacity_upper; + new_bitrate = std::min(upper_bound, new_bitrate); + } + if (network_estimate_ && network_estimate_->link_capacity_lower.IsFinite() && + new_bitrate < current_bitrate_) { + new_bitrate = std::min( + current_bitrate_, + std::max(new_bitrate, network_estimate_->link_capacity_lower * beta_)); + } + new_bitrate = std::max(new_bitrate, min_configured_bitrate_); + return new_bitrate; +} + +DataRate AimdRateControl::MultiplicativeRateIncrease( + Timestamp at_time, + Timestamp last_time, + DataRate current_bitrate) const { + double alpha = 1.08; + if (last_time.IsFinite()) { + auto time_since_last_update = at_time - last_time; + alpha = pow(alpha, std::min(time_since_last_update.seconds<double>(), 1.0)); + } + DataRate multiplicative_increase = + std::max(current_bitrate * (alpha - 1.0), DataRate::BitsPerSec(1000)); + return multiplicative_increase; +} + +DataRate AimdRateControl::AdditiveRateIncrease(Timestamp at_time, + Timestamp last_time) const { + double time_period_seconds = (at_time - last_time).seconds<double>(); + double data_rate_increase_bps = + GetNearMaxIncreaseRateBpsPerSecond() * time_period_seconds; + return DataRate::BitsPerSec(data_rate_increase_bps); +} + +void AimdRateControl::ChangeState(const RateControlInput& input, + Timestamp at_time) { + switch (input.bw_state) { + case BandwidthUsage::kBwNormal: + if (rate_control_state_ == RateControlState::kRcHold) { + time_last_bitrate_change_ = at_time; + rate_control_state_ = RateControlState::kRcIncrease; + } + break; + case BandwidthUsage::kBwOverusing: + if (rate_control_state_ != RateControlState::kRcDecrease) { + rate_control_state_ = RateControlState::kRcDecrease; + } + break; + case BandwidthUsage::kBwUnderusing: + rate_control_state_ = RateControlState::kRcHold; + break; + default: + RTC_DCHECK_NOTREACHED(); + } +} + +} // namespace webrtc |