tor-browser

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

overuse_estimator.cc (4778B)

      1 /*
      2 *  Copyright (c) 2013 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/overuse_estimator.h"
     12 
     13 #include <algorithm>
     14 #include <cmath>
     15 #include <cstdint>
     16 
     17 #include "api/transport/bandwidth_usage.h"
     18 #include "rtc_base/checks.h"
     19 #include "rtc_base/logging.h"
     20 
     21 namespace webrtc {
     22 namespace {
     23 
     24 constexpr int kMinFramePeriodHistoryLength = 60;
     25 constexpr int kDeltaCounterMax = 1000;
     26 
     27 }  // namespace
     28 
     29 OveruseEstimator::OveruseEstimator() = default;
     30 
     31 void OveruseEstimator::Update(int64_t t_delta,
     32                              double ts_delta,
     33                              int size_delta,
     34                              BandwidthUsage current_hypothesis,
     35                              int64_t /* now_ms */) {
     36  const double min_frame_period = UpdateMinFramePeriod(ts_delta);
     37  const double t_ts_delta = t_delta - ts_delta;
     38  double fs_delta = size_delta;
     39 
     40  ++num_of_deltas_;
     41  if (num_of_deltas_ > kDeltaCounterMax) {
     42    num_of_deltas_ = kDeltaCounterMax;
     43  }
     44 
     45  // Update the Kalman filter.
     46  E_[0][0] += process_noise_[0];
     47  E_[1][1] += process_noise_[1];
     48 
     49  if ((current_hypothesis == BandwidthUsage::kBwOverusing &&
     50       offset_ < prev_offset_) ||
     51      (current_hypothesis == BandwidthUsage::kBwUnderusing &&
     52       offset_ > prev_offset_)) {
     53    E_[1][1] += 10 * process_noise_[1];
     54  }
     55 
     56  const double h[2] = {fs_delta, 1.0};
     57  const double Eh[2] = {E_[0][0] * h[0] + E_[0][1] * h[1],
     58                        E_[1][0] * h[0] + E_[1][1] * h[1]};
     59 
     60  const double residual = t_ts_delta - slope_ * h[0] - offset_;
     61 
     62  const bool in_stable_state =
     63      (current_hypothesis == BandwidthUsage::kBwNormal);
     64  const double max_residual = 3.0 * sqrt(var_noise_);
     65  // We try to filter out very late frames. For instance periodic key
     66  // frames doesn't fit the Gaussian model well.
     67  if (fabs(residual) < max_residual) {
     68    UpdateNoiseEstimate(residual, min_frame_period, in_stable_state);
     69  } else {
     70    UpdateNoiseEstimate(residual < 0 ? -max_residual : max_residual,
     71                        min_frame_period, in_stable_state);
     72  }
     73 
     74  const double denom = var_noise_ + h[0] * Eh[0] + h[1] * Eh[1];
     75 
     76  const double K[2] = {Eh[0] / denom, Eh[1] / denom};
     77 
     78  const double IKh[2][2] = {{1.0 - K[0] * h[0], -K[0] * h[1]},
     79                            {-K[1] * h[0], 1.0 - K[1] * h[1]}};
     80  const double e00 = E_[0][0];
     81  const double e01 = E_[0][1];
     82 
     83  // Update state.
     84  E_[0][0] = e00 * IKh[0][0] + E_[1][0] * IKh[0][1];
     85  E_[0][1] = e01 * IKh[0][0] + E_[1][1] * IKh[0][1];
     86  E_[1][0] = e00 * IKh[1][0] + E_[1][0] * IKh[1][1];
     87  E_[1][1] = e01 * IKh[1][0] + E_[1][1] * IKh[1][1];
     88 
     89  // The covariance matrix must be positive semi-definite.
     90  bool positive_semi_definite =
     91      E_[0][0] + E_[1][1] >= 0 &&
     92      E_[0][0] * E_[1][1] - E_[0][1] * E_[1][0] >= 0 && E_[0][0] >= 0;
     93  RTC_DCHECK(positive_semi_definite);
     94  if (!positive_semi_definite) {
     95    RTC_LOG(LS_ERROR)
     96        << "The over-use estimator's covariance matrix is no longer "
     97           "semi-definite.";
     98  }
     99 
    100  slope_ = slope_ + K[0] * residual;
    101  prev_offset_ = offset_;
    102  offset_ = offset_ + K[1] * residual;
    103 }
    104 
    105 double OveruseEstimator::UpdateMinFramePeriod(double ts_delta) {
    106  double min_frame_period = ts_delta;
    107  if (ts_delta_hist_.size() >= kMinFramePeriodHistoryLength) {
    108    ts_delta_hist_.pop_front();
    109  }
    110  for (const double old_ts_delta : ts_delta_hist_) {
    111    min_frame_period = std::min(old_ts_delta, min_frame_period);
    112  }
    113  ts_delta_hist_.push_back(ts_delta);
    114  return min_frame_period;
    115 }
    116 
    117 void OveruseEstimator::UpdateNoiseEstimate(double residual,
    118                                           double ts_delta,
    119                                           bool stable_state) {
    120  if (!stable_state) {
    121    return;
    122  }
    123  // Faster filter during startup to faster adapt to the jitter level
    124  // of the network. `alpha` is tuned for 30 frames per second, but is scaled
    125  // according to `ts_delta`.
    126  double alpha = 0.01;
    127  if (num_of_deltas_ > 10 * 30) {
    128    alpha = 0.002;
    129  }
    130  // Only update the noise estimate if we're not over-using. `beta` is a
    131  // function of alpha and the time delta since the previous update.
    132  const double beta = pow(1 - alpha, ts_delta * 30.0 / 1000.0);
    133  avg_noise_ = beta * avg_noise_ + (1 - beta) * residual;
    134  var_noise_ = beta * var_noise_ +
    135               (1 - beta) * (avg_noise_ - residual) * (avg_noise_ - residual);
    136  if (var_noise_ < 1) {
    137    var_noise_ = 1;
    138  }
    139 }
    140 }  // namespace webrtc