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