tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

aimd_rate_control.cc (15312B)

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