1 /*
2 * Copyright (c) 2018 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/goog_cc/loss_based_bandwidth_estimation.h"
12
13 #include <algorithm>
14 #include <string>
15 #include <vector>
16
17 #include "absl/strings/match.h"
18 #include "api/units/data_rate.h"
19 #include "api/units/time_delta.h"
20
21 namespace webrtc {
22 namespace {
23 const char kBweLossBasedControl[] = "WebRTC-Bwe-LossBasedControl";
24
25 // Expecting RTCP feedback to be sent with roughly 1s intervals, a 5s gap
26 // indicates a channel outage.
27 constexpr TimeDelta kMaxRtcpFeedbackInterval = TimeDelta::Millis(5000);
28
29 // Increase slower when RTT is high.
GetIncreaseFactor(const LossBasedControlConfig & config,TimeDelta rtt)30 double GetIncreaseFactor(const LossBasedControlConfig& config, TimeDelta rtt) {
31 // Clamp the RTT
32 if (rtt < config.increase_low_rtt) {
33 rtt = config.increase_low_rtt;
34 } else if (rtt > config.increase_high_rtt) {
35 rtt = config.increase_high_rtt;
36 }
37 auto rtt_range = config.increase_high_rtt.Get() - config.increase_low_rtt;
38 if (rtt_range <= TimeDelta::Zero()) {
39 RTC_DCHECK_NOTREACHED(); // Only on misconfiguration.
40 return config.min_increase_factor;
41 }
42 auto rtt_offset = rtt - config.increase_low_rtt;
43 auto relative_offset = std::max(0.0, std::min(rtt_offset / rtt_range, 1.0));
44 auto factor_range = config.max_increase_factor - config.min_increase_factor;
45 return config.min_increase_factor + (1 - relative_offset) * factor_range;
46 }
47
LossFromBitrate(DataRate bitrate,DataRate loss_bandwidth_balance,double exponent)48 double LossFromBitrate(DataRate bitrate,
49 DataRate loss_bandwidth_balance,
50 double exponent) {
51 if (loss_bandwidth_balance >= bitrate)
52 return 1.0;
53 return pow(loss_bandwidth_balance / bitrate, exponent);
54 }
55
BitrateFromLoss(double loss,DataRate loss_bandwidth_balance,double exponent)56 DataRate BitrateFromLoss(double loss,
57 DataRate loss_bandwidth_balance,
58 double exponent) {
59 if (exponent <= 0) {
60 RTC_DCHECK_NOTREACHED();
61 return DataRate::Infinity();
62 }
63 if (loss < 1e-5)
64 return DataRate::Infinity();
65 return loss_bandwidth_balance * pow(loss, -1.0 / exponent);
66 }
67
ExponentialUpdate(TimeDelta window,TimeDelta interval)68 double ExponentialUpdate(TimeDelta window, TimeDelta interval) {
69 // Use the convention that exponential window length (which is really
70 // infinite) is the time it takes to dampen to 1/e.
71 if (window <= TimeDelta::Zero()) {
72 RTC_DCHECK_NOTREACHED();
73 return 1.0f;
74 }
75 return 1.0f - exp(interval / window * -1.0);
76 }
77
IsEnabled(const webrtc::FieldTrialsView & key_value_config,absl::string_view name)78 bool IsEnabled(const webrtc::FieldTrialsView& key_value_config,
79 absl::string_view name) {
80 return absl::StartsWith(key_value_config.Lookup(name), "Enabled");
81 }
82
83 } // namespace
84
LossBasedControlConfig(const FieldTrialsView * key_value_config)85 LossBasedControlConfig::LossBasedControlConfig(
86 const FieldTrialsView* key_value_config)
87 : enabled(IsEnabled(*key_value_config, kBweLossBasedControl)),
88 min_increase_factor("min_incr", 1.02),
89 max_increase_factor("max_incr", 1.08),
90 increase_low_rtt("incr_low_rtt", TimeDelta::Millis(200)),
91 increase_high_rtt("incr_high_rtt", TimeDelta::Millis(800)),
92 decrease_factor("decr", 0.99),
93 loss_window("loss_win", TimeDelta::Millis(800)),
94 loss_max_window("loss_max_win", TimeDelta::Millis(800)),
95 acknowledged_rate_max_window("ackrate_max_win", TimeDelta::Millis(800)),
96 increase_offset("incr_offset", DataRate::BitsPerSec(1000)),
97 loss_bandwidth_balance_increase("balance_incr",
98 DataRate::KilobitsPerSec(0.5)),
99 loss_bandwidth_balance_decrease("balance_decr",
100 DataRate::KilobitsPerSec(4)),
101 loss_bandwidth_balance_reset("balance_reset",
102 DataRate::KilobitsPerSec(0.1)),
103 loss_bandwidth_balance_exponent("exponent", 0.5),
104 allow_resets("resets", false),
105 decrease_interval("decr_intvl", TimeDelta::Millis(300)),
106 loss_report_timeout("timeout", TimeDelta::Millis(6000)) {
107 ParseFieldTrial(
108 {&min_increase_factor, &max_increase_factor, &increase_low_rtt,
109 &increase_high_rtt, &decrease_factor, &loss_window, &loss_max_window,
110 &acknowledged_rate_max_window, &increase_offset,
111 &loss_bandwidth_balance_increase, &loss_bandwidth_balance_decrease,
112 &loss_bandwidth_balance_reset, &loss_bandwidth_balance_exponent,
113 &allow_resets, &decrease_interval, &loss_report_timeout},
114 key_value_config->Lookup(kBweLossBasedControl));
115 }
116 LossBasedControlConfig::LossBasedControlConfig(const LossBasedControlConfig&) =
117 default;
118 LossBasedControlConfig::~LossBasedControlConfig() = default;
119
LossBasedBandwidthEstimation(const FieldTrialsView * key_value_config)120 LossBasedBandwidthEstimation::LossBasedBandwidthEstimation(
121 const FieldTrialsView* key_value_config)
122 : config_(key_value_config),
123 average_loss_(0),
124 average_loss_max_(0),
125 loss_based_bitrate_(DataRate::Zero()),
126 acknowledged_bitrate_max_(DataRate::Zero()),
127 acknowledged_bitrate_last_update_(Timestamp::MinusInfinity()),
128 time_last_decrease_(Timestamp::MinusInfinity()),
129 has_decreased_since_last_loss_report_(false),
130 last_loss_packet_report_(Timestamp::MinusInfinity()),
131 last_loss_ratio_(0) {}
132
UpdateLossStatistics(const std::vector<PacketResult> & packet_results,Timestamp at_time)133 void LossBasedBandwidthEstimation::UpdateLossStatistics(
134 const std::vector<PacketResult>& packet_results,
135 Timestamp at_time) {
136 if (packet_results.empty()) {
137 RTC_DCHECK_NOTREACHED();
138 return;
139 }
140 int loss_count = 0;
141 for (const auto& pkt : packet_results) {
142 loss_count += !pkt.IsReceived() ? 1 : 0;
143 }
144 last_loss_ratio_ = static_cast<double>(loss_count) / packet_results.size();
145 const TimeDelta time_passed = last_loss_packet_report_.IsFinite()
146 ? at_time - last_loss_packet_report_
147 : TimeDelta::Seconds(1);
148 last_loss_packet_report_ = at_time;
149 has_decreased_since_last_loss_report_ = false;
150
151 average_loss_ += ExponentialUpdate(config_.loss_window, time_passed) *
152 (last_loss_ratio_ - average_loss_);
153 if (average_loss_ > average_loss_max_) {
154 average_loss_max_ = average_loss_;
155 } else {
156 average_loss_max_ +=
157 ExponentialUpdate(config_.loss_max_window, time_passed) *
158 (average_loss_ - average_loss_max_);
159 }
160 }
161
UpdateAcknowledgedBitrate(DataRate acknowledged_bitrate,Timestamp at_time)162 void LossBasedBandwidthEstimation::UpdateAcknowledgedBitrate(
163 DataRate acknowledged_bitrate,
164 Timestamp at_time) {
165 const TimeDelta time_passed =
166 acknowledged_bitrate_last_update_.IsFinite()
167 ? at_time - acknowledged_bitrate_last_update_
168 : TimeDelta::Seconds(1);
169 acknowledged_bitrate_last_update_ = at_time;
170 if (acknowledged_bitrate > acknowledged_bitrate_max_) {
171 acknowledged_bitrate_max_ = acknowledged_bitrate;
172 } else {
173 acknowledged_bitrate_max_ -=
174 ExponentialUpdate(config_.acknowledged_rate_max_window, time_passed) *
175 (acknowledged_bitrate_max_ - acknowledged_bitrate);
176 }
177 }
178
Update(Timestamp at_time,DataRate min_bitrate,DataRate wanted_bitrate,TimeDelta last_round_trip_time)179 DataRate LossBasedBandwidthEstimation::Update(Timestamp at_time,
180 DataRate min_bitrate,
181 DataRate wanted_bitrate,
182 TimeDelta last_round_trip_time) {
183 if (loss_based_bitrate_.IsZero()) {
184 loss_based_bitrate_ = wanted_bitrate;
185 }
186
187 // Only increase if loss has been low for some time.
188 const double loss_estimate_for_increase = average_loss_max_;
189 // Avoid multiple decreases from averaging over one loss spike.
190 const double loss_estimate_for_decrease =
191 std::min(average_loss_, last_loss_ratio_);
192 const bool allow_decrease =
193 !has_decreased_since_last_loss_report_ &&
194 (at_time - time_last_decrease_ >=
195 last_round_trip_time + config_.decrease_interval);
196 // If packet lost reports are too old, dont increase bitrate.
197 const bool loss_report_valid =
198 at_time - last_loss_packet_report_ < 1.2 * kMaxRtcpFeedbackInterval;
199
200 if (loss_report_valid && config_.allow_resets &&
201 loss_estimate_for_increase < loss_reset_threshold()) {
202 loss_based_bitrate_ = wanted_bitrate;
203 } else if (loss_report_valid &&
204 loss_estimate_for_increase < loss_increase_threshold()) {
205 // Increase bitrate by RTT-adaptive ratio.
206 DataRate new_increased_bitrate =
207 min_bitrate * GetIncreaseFactor(config_, last_round_trip_time) +
208 config_.increase_offset;
209 // The bitrate that would make the loss "just high enough".
210 const DataRate new_increased_bitrate_cap = BitrateFromLoss(
211 loss_estimate_for_increase, config_.loss_bandwidth_balance_increase,
212 config_.loss_bandwidth_balance_exponent);
213 new_increased_bitrate =
214 std::min(new_increased_bitrate, new_increased_bitrate_cap);
215 loss_based_bitrate_ = std::max(new_increased_bitrate, loss_based_bitrate_);
216 } else if (loss_estimate_for_decrease > loss_decrease_threshold() &&
217 allow_decrease) {
218 // The bitrate that would make the loss "just acceptable".
219 const DataRate new_decreased_bitrate_floor = BitrateFromLoss(
220 loss_estimate_for_decrease, config_.loss_bandwidth_balance_decrease,
221 config_.loss_bandwidth_balance_exponent);
222 DataRate new_decreased_bitrate =
223 std::max(decreased_bitrate(), new_decreased_bitrate_floor);
224 if (new_decreased_bitrate < loss_based_bitrate_) {
225 time_last_decrease_ = at_time;
226 has_decreased_since_last_loss_report_ = true;
227 loss_based_bitrate_ = new_decreased_bitrate;
228 }
229 }
230 return loss_based_bitrate_;
231 }
232
Initialize(DataRate bitrate)233 void LossBasedBandwidthEstimation::Initialize(DataRate bitrate) {
234 loss_based_bitrate_ = bitrate;
235 average_loss_ = 0;
236 average_loss_max_ = 0;
237 }
238
loss_reset_threshold() const239 double LossBasedBandwidthEstimation::loss_reset_threshold() const {
240 return LossFromBitrate(loss_based_bitrate_,
241 config_.loss_bandwidth_balance_reset,
242 config_.loss_bandwidth_balance_exponent);
243 }
244
loss_increase_threshold() const245 double LossBasedBandwidthEstimation::loss_increase_threshold() const {
246 return LossFromBitrate(loss_based_bitrate_,
247 config_.loss_bandwidth_balance_increase,
248 config_.loss_bandwidth_balance_exponent);
249 }
250
loss_decrease_threshold() const251 double LossBasedBandwidthEstimation::loss_decrease_threshold() const {
252 return LossFromBitrate(loss_based_bitrate_,
253 config_.loss_bandwidth_balance_decrease,
254 config_.loss_bandwidth_balance_exponent);
255 }
256
decreased_bitrate() const257 DataRate LossBasedBandwidthEstimation::decreased_bitrate() const {
258 return config_.decrease_factor * acknowledged_bitrate_max_;
259 }
260 } // namespace webrtc
261