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