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