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/trendline_estimator.h"
      12             : 
      13             : #include <algorithm>
      14             : 
      15             : #include "webrtc/base/checks.h"
      16             : #include "webrtc/base/optional.h"
      17             : #include "webrtc/modules/remote_bitrate_estimator/test/bwe_test_logging.h"
      18             : 
      19             : namespace webrtc {
      20             : 
      21             : namespace {
      22           0 : rtc::Optional<double> LinearFitSlope(
      23             :     const std::list<std::pair<double, double>> points) {
      24           0 :   RTC_DCHECK(points.size() >= 2);
      25             :   // Compute the "center of mass".
      26           0 :   double sum_x = 0;
      27           0 :   double sum_y = 0;
      28           0 :   for (const auto& point : points) {
      29           0 :     sum_x += point.first;
      30           0 :     sum_y += point.second;
      31             :   }
      32           0 :   double x_avg = sum_x / points.size();
      33           0 :   double y_avg = sum_y / points.size();
      34             :   // Compute the slope k = \sum (x_i-x_avg)(y_i-y_avg) / \sum (x_i-x_avg)^2
      35           0 :   double numerator = 0;
      36           0 :   double denominator = 0;
      37           0 :   for (const auto& point : points) {
      38           0 :     numerator += (point.first - x_avg) * (point.second - y_avg);
      39           0 :     denominator += (point.first - x_avg) * (point.first - x_avg);
      40             :   }
      41           0 :   if (denominator == 0)
      42           0 :     return rtc::Optional<double>();
      43           0 :   return rtc::Optional<double>(numerator / denominator);
      44             : }
      45             : }  // namespace
      46             : 
      47             : enum { kDeltaCounterMax = 1000 };
      48             : 
      49           0 : TrendlineEstimator::TrendlineEstimator(size_t window_size,
      50             :                                        double smoothing_coef,
      51           0 :                                        double threshold_gain)
      52             :     : window_size_(window_size),
      53             :       smoothing_coef_(smoothing_coef),
      54             :       threshold_gain_(threshold_gain),
      55             :       num_of_deltas_(0),
      56             :       first_arrival_time_ms(-1),
      57             :       accumulated_delay_(0),
      58             :       smoothed_delay_(0),
      59             :       delay_hist_(),
      60           0 :       trendline_(0) {}
      61             : 
      62           0 : TrendlineEstimator::~TrendlineEstimator() {}
      63             : 
      64           0 : void TrendlineEstimator::Update(double recv_delta_ms,
      65             :                                 double send_delta_ms,
      66             :                                 int64_t arrival_time_ms) {
      67           0 :   const double delta_ms = recv_delta_ms - send_delta_ms;
      68           0 :   ++num_of_deltas_;
      69           0 :   if (num_of_deltas_ > kDeltaCounterMax)
      70           0 :     num_of_deltas_ = kDeltaCounterMax;
      71           0 :   if (first_arrival_time_ms == -1)
      72           0 :     first_arrival_time_ms = arrival_time_ms;
      73             : 
      74             :   // Exponential backoff filter.
      75           0 :   accumulated_delay_ += delta_ms;
      76             :   BWE_TEST_LOGGING_PLOT(1, "accumulated_delay_ms", arrival_time_ms,
      77             :                         accumulated_delay_);
      78           0 :   smoothed_delay_ = smoothing_coef_ * smoothed_delay_ +
      79           0 :                     (1 - smoothing_coef_) * accumulated_delay_;
      80             :   BWE_TEST_LOGGING_PLOT(1, "smoothed_delay_ms", arrival_time_ms,
      81             :                         smoothed_delay_);
      82             : 
      83             :   // Simple linear regression.
      84           0 :   delay_hist_.push_back(std::make_pair(
      85           0 :       static_cast<double>(arrival_time_ms - first_arrival_time_ms),
      86           0 :       smoothed_delay_));
      87           0 :   if (delay_hist_.size() > window_size_)
      88           0 :     delay_hist_.pop_front();
      89           0 :   if (delay_hist_.size() == window_size_) {
      90             :     // Only update trendline_ if it is possible to fit a line to the data.
      91           0 :     trendline_ = LinearFitSlope(delay_hist_).value_or(trendline_);
      92             :   }
      93             : 
      94             :   BWE_TEST_LOGGING_PLOT(1, "trendline_slope", arrival_time_ms, trendline_);
      95           0 : }
      96             : 
      97             : }  // namespace webrtc