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/median_slope_estimator.h"
12
13 #include <algorithm>
14 #include <vector>
15
16 #include "modules/remote_bitrate_estimator/include/bwe_defines.h"
17 #include "modules/remote_bitrate_estimator/test/bwe_test_logging.h"
18 #include "rtc_base/logging.h"
19
20 namespace webrtc {
21
22 constexpr unsigned int kDeltaCounterMax = 1000;
23
MedianSlopeEstimator(size_t window_size,double threshold_gain)24 MedianSlopeEstimator::MedianSlopeEstimator(size_t window_size,
25 double threshold_gain)
26 : window_size_(window_size),
27 threshold_gain_(threshold_gain),
28 num_of_deltas_(0),
29 accumulated_delay_(0),
30 delay_hist_(),
31 median_filter_(0.5),
32 trendline_(0) {}
33
~MedianSlopeEstimator()34 MedianSlopeEstimator::~MedianSlopeEstimator() {}
35
DelayInfo(int64_t time,double delay,size_t slope_count)36 MedianSlopeEstimator::DelayInfo::DelayInfo(int64_t time,
37 double delay,
38 size_t slope_count)
39 : time(time), delay(delay) {
40 slopes.reserve(slope_count);
41 }
42
43 MedianSlopeEstimator::DelayInfo::~DelayInfo() = default;
44
Update(double recv_delta_ms,double send_delta_ms,int64_t arrival_time_ms)45 void MedianSlopeEstimator::Update(double recv_delta_ms,
46 double send_delta_ms,
47 int64_t arrival_time_ms) {
48 const double delta_ms = recv_delta_ms - send_delta_ms;
49 ++num_of_deltas_;
50 if (num_of_deltas_ > kDeltaCounterMax)
51 num_of_deltas_ = kDeltaCounterMax;
52
53 accumulated_delay_ += delta_ms;
54 BWE_TEST_LOGGING_PLOT(1, "accumulated_delay_ms", arrival_time_ms,
55 accumulated_delay_);
56
57 // If the window is full, remove the |window_size_| - 1 slopes that belong to
58 // the oldest point.
59 if (delay_hist_.size() == window_size_) {
60 for (double slope : delay_hist_.front().slopes) {
61 const bool success = median_filter_.Erase(slope);
62 RTC_CHECK(success);
63 }
64 delay_hist_.pop_front();
65 }
66 // Add |window_size_| - 1 new slopes.
67 for (auto& old_delay : delay_hist_) {
68 if (arrival_time_ms - old_delay.time != 0) {
69 // The C99 standard explicitly states that casts and assignments must
70 // perform the associated conversions. This means that |slope| will be
71 // a 64-bit double even if the division is computed using, e.g., 80-bit
72 // extended precision. I believe this also holds in C++ even though the
73 // C++11 standard isn't as explicit. Furthermore, there are good reasons
74 // to believe that compilers couldn't perform optimizations that break
75 // this assumption even if they wanted to.
76 double slope = (accumulated_delay_ - old_delay.delay) /
77 static_cast<double>(arrival_time_ms - old_delay.time);
78 median_filter_.Insert(slope);
79 // We want to avoid issues with different rounding mode / precision
80 // which we might get if we recomputed the slope when we remove it.
81 old_delay.slopes.push_back(slope);
82 }
83 }
84 delay_hist_.emplace_back(arrival_time_ms, accumulated_delay_,
85 window_size_ - 1);
86 // Recompute the median slope.
87 if (delay_hist_.size() == window_size_)
88 trendline_ = median_filter_.GetPercentileValue();
89
90 BWE_TEST_LOGGING_PLOT(1, "trendline_slope", arrival_time_ms, trendline_);
91 }
92
93 } // namespace webrtc
94