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