1 /*
2 * Copyright 2021 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_bwe_v2.h"
12
13 #include <algorithm>
14 #include <cmath>
15 #include <complex>
16 #include <cstddef>
17 #include <cstdlib>
18 #include <limits>
19 #include <utility>
20 #include <vector>
21
22 #include "absl/algorithm/container.h"
23 #include "absl/types/optional.h"
24 #include "api/array_view.h"
25 #include "api/field_trials_view.h"
26 #include "api/network_state_predictor.h"
27 #include "api/transport/network_types.h"
28 #include "api/units/data_rate.h"
29 #include "api/units/data_size.h"
30 #include "api/units/time_delta.h"
31 #include "api/units/timestamp.h"
32 #include "modules/remote_bitrate_estimator/include/bwe_defines.h"
33 #include "rtc_base/experiments/field_trial_list.h"
34 #include "rtc_base/experiments/field_trial_parser.h"
35 #include "rtc_base/logging.h"
36
37 namespace webrtc {
38
39 namespace {
40
IsValid(DataRate datarate)41 bool IsValid(DataRate datarate) {
42 return datarate.IsFinite();
43 }
44
IsValid(absl::optional<DataRate> datarate)45 bool IsValid(absl::optional<DataRate> datarate) {
46 return datarate.has_value() && IsValid(datarate.value());
47 }
48
IsValid(Timestamp timestamp)49 bool IsValid(Timestamp timestamp) {
50 return timestamp.IsFinite();
51 }
52
53 struct PacketResultsSummary {
54 int num_packets = 0;
55 int num_lost_packets = 0;
56 DataSize total_size = DataSize::Zero();
57 Timestamp first_send_time = Timestamp::PlusInfinity();
58 Timestamp last_send_time = Timestamp::MinusInfinity();
59 };
60
61 // Returns a `PacketResultsSummary` where `first_send_time` is `PlusInfinity,
62 // and `last_send_time` is `MinusInfinity`, if `packet_results` is empty.
GetPacketResultsSummary(rtc::ArrayView<const PacketResult> packet_results)63 PacketResultsSummary GetPacketResultsSummary(
64 rtc::ArrayView<const PacketResult> packet_results) {
65 PacketResultsSummary packet_results_summary;
66
67 packet_results_summary.num_packets = packet_results.size();
68 for (const PacketResult& packet : packet_results) {
69 if (!packet.IsReceived()) {
70 packet_results_summary.num_lost_packets++;
71 }
72 packet_results_summary.total_size += packet.sent_packet.size;
73 packet_results_summary.first_send_time = std::min(
74 packet_results_summary.first_send_time, packet.sent_packet.send_time);
75 packet_results_summary.last_send_time = std::max(
76 packet_results_summary.last_send_time, packet.sent_packet.send_time);
77 }
78
79 return packet_results_summary;
80 }
81
GetLossProbability(double inherent_loss,DataRate loss_limited_bandwidth,DataRate sending_rate)82 double GetLossProbability(double inherent_loss,
83 DataRate loss_limited_bandwidth,
84 DataRate sending_rate) {
85 if (inherent_loss < 0.0 || inherent_loss > 1.0) {
86 RTC_LOG(LS_WARNING) << "The inherent loss must be in [0,1]: "
87 << inherent_loss;
88 inherent_loss = std::min(std::max(inherent_loss, 0.0), 1.0);
89 }
90 if (!sending_rate.IsFinite()) {
91 RTC_LOG(LS_WARNING) << "The sending rate must be finite: "
92 << ToString(sending_rate);
93 }
94 if (!loss_limited_bandwidth.IsFinite()) {
95 RTC_LOG(LS_WARNING) << "The loss limited bandwidth must be finite: "
96 << ToString(loss_limited_bandwidth);
97 }
98
99 double loss_probability = inherent_loss;
100 if (IsValid(sending_rate) && IsValid(loss_limited_bandwidth) &&
101 (sending_rate > loss_limited_bandwidth)) {
102 loss_probability += (1 - inherent_loss) *
103 (sending_rate - loss_limited_bandwidth) / sending_rate;
104 }
105 return std::min(std::max(loss_probability, 1.0e-6), 1.0 - 1.0e-6);
106 }
107
108 } // namespace
109
LossBasedBweV2(const FieldTrialsView * key_value_config)110 LossBasedBweV2::LossBasedBweV2(const FieldTrialsView* key_value_config)
111 : config_(CreateConfig(key_value_config)) {
112 if (!config_.has_value()) {
113 RTC_LOG(LS_VERBOSE) << "The configuration does not specify that the "
114 "estimator should be enabled, disabling it.";
115 return;
116 }
117 if (!IsConfigValid()) {
118 RTC_LOG(LS_WARNING)
119 << "The configuration is not valid, disabling the estimator.";
120 config_.reset();
121 return;
122 }
123
124 current_estimate_.inherent_loss = config_->initial_inherent_loss_estimate;
125 observations_.resize(config_->observation_window_size);
126 temporal_weights_.resize(config_->observation_window_size);
127 instant_upper_bound_temporal_weights_.resize(
128 config_->observation_window_size);
129 CalculateTemporalWeights();
130 }
131
IsEnabled() const132 bool LossBasedBweV2::IsEnabled() const {
133 return config_.has_value();
134 }
135
IsReady() const136 bool LossBasedBweV2::IsReady() const {
137 return IsEnabled() && IsValid(current_estimate_.loss_limited_bandwidth) &&
138 num_observations_ > 0;
139 }
140
GetLossBasedResult() const141 LossBasedBweV2::Result LossBasedBweV2::GetLossBasedResult() const {
142 Result result;
143 result.state = current_state_;
144 if (!IsReady()) {
145 if (!IsEnabled()) {
146 RTC_LOG(LS_WARNING)
147 << "The estimator must be enabled before it can be used.";
148 } else {
149 if (!IsValid(current_estimate_.loss_limited_bandwidth)) {
150 RTC_LOG(LS_WARNING)
151 << "The estimator must be initialized before it can be used.";
152 }
153 if (num_observations_ <= 0) {
154 RTC_LOG(LS_WARNING) << "The estimator must receive enough loss "
155 "statistics before it can be used.";
156 }
157 }
158 result.bandwidth_estimate = IsValid(delay_based_estimate_)
159 ? delay_based_estimate_
160 : DataRate::PlusInfinity();
161 return result;
162 }
163
164 if (IsValid(delay_based_estimate_)) {
165 result.bandwidth_estimate =
166 std::min({current_estimate_.loss_limited_bandwidth,
167 GetInstantUpperBound(), delay_based_estimate_});
168 } else {
169 result.bandwidth_estimate = std::min(
170 current_estimate_.loss_limited_bandwidth, GetInstantUpperBound());
171 }
172 return result;
173 }
174
SetAcknowledgedBitrate(DataRate acknowledged_bitrate)175 void LossBasedBweV2::SetAcknowledgedBitrate(DataRate acknowledged_bitrate) {
176 if (IsValid(acknowledged_bitrate)) {
177 acknowledged_bitrate_ = acknowledged_bitrate;
178 } else {
179 RTC_LOG(LS_WARNING) << "The acknowledged bitrate must be finite: "
180 << ToString(acknowledged_bitrate);
181 }
182 }
183
SetBandwidthEstimate(DataRate bandwidth_estimate)184 void LossBasedBweV2::SetBandwidthEstimate(DataRate bandwidth_estimate) {
185 if (IsValid(bandwidth_estimate)) {
186 current_estimate_.loss_limited_bandwidth = bandwidth_estimate;
187 } else {
188 RTC_LOG(LS_WARNING) << "The bandwidth estimate must be finite: "
189 << ToString(bandwidth_estimate);
190 }
191 }
192
SetMinMaxBitrate(DataRate min_bitrate,DataRate max_bitrate)193 void LossBasedBweV2::SetMinMaxBitrate(DataRate min_bitrate,
194 DataRate max_bitrate) {
195 if (IsValid(min_bitrate)) {
196 min_bitrate_ = min_bitrate;
197 } else {
198 RTC_LOG(LS_WARNING) << "The min bitrate must be finite: "
199 << ToString(min_bitrate);
200 }
201
202 if (IsValid(max_bitrate)) {
203 max_bitrate_ = max_bitrate;
204 } else {
205 RTC_LOG(LS_WARNING) << "The max bitrate must be finite: "
206 << ToString(max_bitrate);
207 }
208 }
209
SetProbeBitrate(absl::optional<DataRate> probe_bitrate)210 void LossBasedBweV2::SetProbeBitrate(absl::optional<DataRate> probe_bitrate) {
211 if (probe_bitrate.has_value() && IsValid(probe_bitrate.value())) {
212 if (!IsValid(probe_bitrate_) || probe_bitrate_ > probe_bitrate.value()) {
213 probe_bitrate_ = probe_bitrate.value();
214 }
215 }
216 }
217
UpdateBandwidthEstimate(rtc::ArrayView<const PacketResult> packet_results,DataRate delay_based_estimate,BandwidthUsage delay_detector_state,absl::optional<DataRate> probe_bitrate,DataRate upper_link_capacity)218 void LossBasedBweV2::UpdateBandwidthEstimate(
219 rtc::ArrayView<const PacketResult> packet_results,
220 DataRate delay_based_estimate,
221 BandwidthUsage delay_detector_state,
222 absl::optional<DataRate> probe_bitrate,
223 DataRate upper_link_capacity) {
224 delay_based_estimate_ = delay_based_estimate;
225 upper_link_capacity_ = upper_link_capacity;
226 if (!IsEnabled()) {
227 RTC_LOG(LS_WARNING)
228 << "The estimator must be enabled before it can be used.";
229 return;
230 }
231 SetProbeBitrate(probe_bitrate);
232 if (packet_results.empty()) {
233 RTC_LOG(LS_VERBOSE)
234 << "The estimate cannot be updated without any loss statistics.";
235 return;
236 }
237
238 if (!PushBackObservation(packet_results, delay_detector_state)) {
239 return;
240 }
241
242 if (!IsValid(current_estimate_.loss_limited_bandwidth)) {
243 RTC_LOG(LS_VERBOSE)
244 << "The estimator must be initialized before it can be used.";
245 return;
246 }
247
248 ChannelParameters best_candidate = current_estimate_;
249 double objective_max = std::numeric_limits<double>::lowest();
250 for (ChannelParameters candidate : GetCandidates()) {
251 NewtonsMethodUpdate(candidate);
252
253 const double candidate_objective = GetObjective(candidate);
254 if (candidate_objective > objective_max) {
255 objective_max = candidate_objective;
256 best_candidate = candidate;
257 }
258 }
259 if (best_candidate.loss_limited_bandwidth <
260 current_estimate_.loss_limited_bandwidth) {
261 last_time_estimate_reduced_ = last_send_time_most_recent_observation_;
262 }
263
264 // Do not increase the estimate if the average loss is greater than current
265 // inherent loss.
266 if (GetAverageReportedLossRatio() > best_candidate.inherent_loss &&
267 config_->not_increase_if_inherent_loss_less_than_average_loss &&
268 current_estimate_.loss_limited_bandwidth <
269 best_candidate.loss_limited_bandwidth) {
270 best_candidate.loss_limited_bandwidth =
271 current_estimate_.loss_limited_bandwidth;
272 }
273
274 if (IsBandwidthLimitedDueToLoss()) {
275 // Bound the estimate increase if:
276 // 1. The estimate has been increased for less than
277 // `delayed_increase_window` ago, and
278 // 2. The best candidate is greater than bandwidth_limit_in_current_window.
279 if (recovering_after_loss_timestamp_.IsFinite() &&
280 recovering_after_loss_timestamp_ + config_->delayed_increase_window >
281 last_send_time_most_recent_observation_ &&
282 best_candidate.loss_limited_bandwidth >
283 bandwidth_limit_in_current_window_) {
284 best_candidate.loss_limited_bandwidth =
285 bandwidth_limit_in_current_window_;
286 }
287
288 bool increasing_when_loss_limited =
289 IsEstimateIncreasingWhenLossLimited(best_candidate);
290 // Bound the best candidate by the acked bitrate unless there is a recent
291 // probe result.
292 if (increasing_when_loss_limited && !IsValid(probe_bitrate_) &&
293 IsValid(acknowledged_bitrate_)) {
294 best_candidate.loss_limited_bandwidth =
295 IsValid(best_candidate.loss_limited_bandwidth)
296 ? std::min(best_candidate.loss_limited_bandwidth,
297 config_->bandwidth_rampup_upper_bound_factor *
298 (*acknowledged_bitrate_))
299 : config_->bandwidth_rampup_upper_bound_factor *
300 (*acknowledged_bitrate_);
301 }
302
303 // Use probe bitrate as the estimate as probe bitrate is trusted to be
304 // correct. After being used, the probe bitrate is reset.
305 if (config_->probe_integration_enabled && IsValid(probe_bitrate_)) {
306 best_candidate.loss_limited_bandwidth =
307 std::min(probe_bitrate_, best_candidate.loss_limited_bandwidth);
308 probe_bitrate_ = DataRate::MinusInfinity();
309 }
310 }
311
312 if (IsEstimateIncreasingWhenLossLimited(best_candidate) &&
313 best_candidate.loss_limited_bandwidth < delay_based_estimate) {
314 current_state_ = LossBasedState::kIncreasing;
315 } else if (best_candidate.loss_limited_bandwidth < delay_based_estimate_) {
316 current_state_ = LossBasedState::kDecreasing;
317 } else if (best_candidate.loss_limited_bandwidth >= delay_based_estimate_) {
318 current_state_ = LossBasedState::kDelayBasedEstimate;
319 }
320 current_estimate_ = best_candidate;
321
322 if (IsBandwidthLimitedDueToLoss() &&
323 (recovering_after_loss_timestamp_.IsInfinite() ||
324 recovering_after_loss_timestamp_ + config_->delayed_increase_window <
325 last_send_time_most_recent_observation_)) {
326 bandwidth_limit_in_current_window_ =
327 std::max(kCongestionControllerMinBitrate,
328 current_estimate_.loss_limited_bandwidth *
329 config_->max_increase_factor);
330 recovering_after_loss_timestamp_ = last_send_time_most_recent_observation_;
331 }
332 }
333
IsEstimateIncreasingWhenLossLimited(const ChannelParameters & best_candidate)334 bool LossBasedBweV2::IsEstimateIncreasingWhenLossLimited(
335 const ChannelParameters& best_candidate) {
336 return (current_estimate_.loss_limited_bandwidth <
337 best_candidate.loss_limited_bandwidth ||
338 (current_estimate_.loss_limited_bandwidth ==
339 best_candidate.loss_limited_bandwidth &&
340 current_state_ == LossBasedState::kIncreasing)) &&
341 IsBandwidthLimitedDueToLoss();
342 }
343
344 // Returns a `LossBasedBweV2::Config` iff the `key_value_config` specifies a
345 // configuration for the `LossBasedBweV2` which is explicitly enabled.
CreateConfig(const FieldTrialsView * key_value_config)346 absl::optional<LossBasedBweV2::Config> LossBasedBweV2::CreateConfig(
347 const FieldTrialsView* key_value_config) {
348 FieldTrialParameter<bool> enabled("Enabled", false);
349 FieldTrialParameter<double> bandwidth_rampup_upper_bound_factor(
350 "BwRampupUpperBoundFactor", 1.1);
351 FieldTrialParameter<double> rampup_acceleration_max_factor(
352 "BwRampupAccelMaxFactor", 0.0);
353 FieldTrialParameter<TimeDelta> rampup_acceleration_maxout_time(
354 "BwRampupAccelMaxoutTime", TimeDelta::Seconds(60));
355 FieldTrialList<double> candidate_factors("CandidateFactors",
356 {1.05, 1.0, 0.95});
357 FieldTrialParameter<double> higher_bandwidth_bias_factor("HigherBwBiasFactor",
358 0.00001);
359 FieldTrialParameter<double> higher_log_bandwidth_bias_factor(
360 "HigherLogBwBiasFactor", 0.001);
361 FieldTrialParameter<double> inherent_loss_lower_bound(
362 "InherentLossLowerBound", 1.0e-3);
363 FieldTrialParameter<double> loss_threshold_of_high_bandwidth_preference(
364 "LossThresholdOfHighBandwidthPreference", 0.99);
365 FieldTrialParameter<double> bandwidth_preference_smoothing_factor(
366 "BandwidthPreferenceSmoothingFactor", 0.002);
367 FieldTrialParameter<DataRate> inherent_loss_upper_bound_bandwidth_balance(
368 "InherentLossUpperBoundBwBalance", DataRate::KilobitsPerSec(15.0));
369 FieldTrialParameter<double> inherent_loss_upper_bound_offset(
370 "InherentLossUpperBoundOffset", 0.05);
371 FieldTrialParameter<double> initial_inherent_loss_estimate(
372 "InitialInherentLossEstimate", 0.01);
373 FieldTrialParameter<int> newton_iterations("NewtonIterations", 1);
374 FieldTrialParameter<double> newton_step_size("NewtonStepSize", 0.5);
375 FieldTrialParameter<bool> append_acknowledged_rate_candidate(
376 "AckedRateCandidate", true);
377 FieldTrialParameter<bool> append_delay_based_estimate_candidate(
378 "DelayBasedCandidate", false);
379 FieldTrialParameter<TimeDelta> observation_duration_lower_bound(
380 "ObservationDurationLowerBound", TimeDelta::Seconds(1));
381 FieldTrialParameter<int> observation_window_size("ObservationWindowSize", 20);
382 FieldTrialParameter<double> sending_rate_smoothing_factor(
383 "SendingRateSmoothingFactor", 0.0);
384 FieldTrialParameter<double> instant_upper_bound_temporal_weight_factor(
385 "InstantUpperBoundTemporalWeightFactor", 0.99);
386 FieldTrialParameter<DataRate> instant_upper_bound_bandwidth_balance(
387 "InstantUpperBoundBwBalance", DataRate::KilobitsPerSec(15.0));
388 FieldTrialParameter<double> instant_upper_bound_loss_offset(
389 "InstantUpperBoundLossOffset", 0.05);
390 FieldTrialParameter<double> temporal_weight_factor("TemporalWeightFactor",
391 0.99);
392 FieldTrialParameter<double> bandwidth_backoff_lower_bound_factor(
393 "BwBackoffLowerBoundFactor", 1.0);
394 FieldTrialParameter<bool> trendline_integration_enabled(
395 "TrendlineIntegrationEnabled", false);
396 FieldTrialParameter<int> trendline_observations_window_size(
397 "TrendlineObservationsWindowSize", 20);
398 FieldTrialParameter<double> max_increase_factor("MaxIncreaseFactor", 1000.0);
399 FieldTrialParameter<TimeDelta> delayed_increase_window(
400 "DelayedIncreaseWindow", TimeDelta::Millis(300));
401 FieldTrialParameter<bool> use_acked_bitrate_only_when_overusing(
402 "UseAckedBitrateOnlyWhenOverusing", false);
403 FieldTrialParameter<bool>
404 not_increase_if_inherent_loss_less_than_average_loss(
405 "NotIncreaseIfInherentLossLessThanAverageLoss", false);
406 FieldTrialParameter<double> high_loss_rate_threshold("HighLossRateThreshold",
407 1.0);
408 FieldTrialParameter<DataRate> bandwidth_cap_at_high_loss_rate(
409 "BandwidthCapAtHighLossRate", DataRate::KilobitsPerSec(500.0));
410 FieldTrialParameter<double> slope_of_bwe_high_loss_func(
411 "SlopeOfBweHighLossFunc", 1000);
412 FieldTrialParameter<bool> probe_integration_enabled("ProbeIntegrationEnabled",
413 false);
414 FieldTrialParameter<bool> bound_by_upper_link_capacity_when_loss_limited(
415 "BoundByUpperLinkCapacityWhenLossLimited", true);
416 if (key_value_config) {
417 ParseFieldTrial({&enabled,
418 &bandwidth_rampup_upper_bound_factor,
419 &rampup_acceleration_max_factor,
420 &rampup_acceleration_maxout_time,
421 &candidate_factors,
422 &higher_bandwidth_bias_factor,
423 &higher_log_bandwidth_bias_factor,
424 &inherent_loss_lower_bound,
425 &loss_threshold_of_high_bandwidth_preference,
426 &bandwidth_preference_smoothing_factor,
427 &inherent_loss_upper_bound_bandwidth_balance,
428 &inherent_loss_upper_bound_offset,
429 &initial_inherent_loss_estimate,
430 &newton_iterations,
431 &newton_step_size,
432 &append_acknowledged_rate_candidate,
433 &append_delay_based_estimate_candidate,
434 &observation_duration_lower_bound,
435 &observation_window_size,
436 &sending_rate_smoothing_factor,
437 &instant_upper_bound_temporal_weight_factor,
438 &instant_upper_bound_bandwidth_balance,
439 &instant_upper_bound_loss_offset,
440 &temporal_weight_factor,
441 &bandwidth_backoff_lower_bound_factor,
442 &trendline_integration_enabled,
443 &trendline_observations_window_size,
444 &max_increase_factor,
445 &delayed_increase_window,
446 &use_acked_bitrate_only_when_overusing,
447 ¬_increase_if_inherent_loss_less_than_average_loss,
448 &probe_integration_enabled,
449 &high_loss_rate_threshold,
450 &bandwidth_cap_at_high_loss_rate,
451 &slope_of_bwe_high_loss_func,
452 &bound_by_upper_link_capacity_when_loss_limited},
453 key_value_config->Lookup("WebRTC-Bwe-LossBasedBweV2"));
454 }
455
456 absl::optional<Config> config;
457 if (!enabled.Get()) {
458 return config;
459 }
460 config.emplace();
461 config->bandwidth_rampup_upper_bound_factor =
462 bandwidth_rampup_upper_bound_factor.Get();
463 config->rampup_acceleration_max_factor = rampup_acceleration_max_factor.Get();
464 config->rampup_acceleration_maxout_time =
465 rampup_acceleration_maxout_time.Get();
466 config->candidate_factors = candidate_factors.Get();
467 config->higher_bandwidth_bias_factor = higher_bandwidth_bias_factor.Get();
468 config->higher_log_bandwidth_bias_factor =
469 higher_log_bandwidth_bias_factor.Get();
470 config->inherent_loss_lower_bound = inherent_loss_lower_bound.Get();
471 config->loss_threshold_of_high_bandwidth_preference =
472 loss_threshold_of_high_bandwidth_preference.Get();
473 config->bandwidth_preference_smoothing_factor =
474 bandwidth_preference_smoothing_factor.Get();
475 config->inherent_loss_upper_bound_bandwidth_balance =
476 inherent_loss_upper_bound_bandwidth_balance.Get();
477 config->inherent_loss_upper_bound_offset =
478 inherent_loss_upper_bound_offset.Get();
479 config->initial_inherent_loss_estimate = initial_inherent_loss_estimate.Get();
480 config->newton_iterations = newton_iterations.Get();
481 config->newton_step_size = newton_step_size.Get();
482 config->append_acknowledged_rate_candidate =
483 append_acknowledged_rate_candidate.Get();
484 config->append_delay_based_estimate_candidate =
485 append_delay_based_estimate_candidate.Get();
486 config->observation_duration_lower_bound =
487 observation_duration_lower_bound.Get();
488 config->observation_window_size = observation_window_size.Get();
489 config->sending_rate_smoothing_factor = sending_rate_smoothing_factor.Get();
490 config->instant_upper_bound_temporal_weight_factor =
491 instant_upper_bound_temporal_weight_factor.Get();
492 config->instant_upper_bound_bandwidth_balance =
493 instant_upper_bound_bandwidth_balance.Get();
494 config->instant_upper_bound_loss_offset =
495 instant_upper_bound_loss_offset.Get();
496 config->temporal_weight_factor = temporal_weight_factor.Get();
497 config->bandwidth_backoff_lower_bound_factor =
498 bandwidth_backoff_lower_bound_factor.Get();
499 config->trendline_integration_enabled = trendline_integration_enabled.Get();
500 config->trendline_observations_window_size =
501 trendline_observations_window_size.Get();
502 config->max_increase_factor = max_increase_factor.Get();
503 config->delayed_increase_window = delayed_increase_window.Get();
504 config->use_acked_bitrate_only_when_overusing =
505 use_acked_bitrate_only_when_overusing.Get();
506 config->not_increase_if_inherent_loss_less_than_average_loss =
507 not_increase_if_inherent_loss_less_than_average_loss.Get();
508 config->high_loss_rate_threshold = high_loss_rate_threshold.Get();
509 config->bandwidth_cap_at_high_loss_rate =
510 bandwidth_cap_at_high_loss_rate.Get();
511 config->slope_of_bwe_high_loss_func = slope_of_bwe_high_loss_func.Get();
512 config->probe_integration_enabled = probe_integration_enabled.Get();
513 config->bound_by_upper_link_capacity_when_loss_limited =
514 bound_by_upper_link_capacity_when_loss_limited.Get();
515
516 return config;
517 }
518
IsConfigValid() const519 bool LossBasedBweV2::IsConfigValid() const {
520 if (!config_.has_value()) {
521 return false;
522 }
523
524 bool valid = true;
525
526 if (config_->bandwidth_rampup_upper_bound_factor <= 1.0) {
527 RTC_LOG(LS_WARNING)
528 << "The bandwidth rampup upper bound factor must be greater than 1: "
529 << config_->bandwidth_rampup_upper_bound_factor;
530 valid = false;
531 }
532 if (config_->rampup_acceleration_max_factor < 0.0) {
533 RTC_LOG(LS_WARNING)
534 << "The rampup acceleration max factor must be non-negative.: "
535 << config_->rampup_acceleration_max_factor;
536 valid = false;
537 }
538 if (config_->rampup_acceleration_maxout_time <= TimeDelta::Zero()) {
539 RTC_LOG(LS_WARNING)
540 << "The rampup acceleration maxout time must be above zero: "
541 << config_->rampup_acceleration_maxout_time.seconds();
542 valid = false;
543 }
544 for (double candidate_factor : config_->candidate_factors) {
545 if (candidate_factor <= 0.0) {
546 RTC_LOG(LS_WARNING) << "All candidate factors must be greater than zero: "
547 << candidate_factor;
548 valid = false;
549 }
550 }
551
552 // Ensure that the configuration allows generation of at least one candidate
553 // other than the current estimate.
554 if (!config_->append_acknowledged_rate_candidate &&
555 !config_->append_delay_based_estimate_candidate &&
556 !absl::c_any_of(config_->candidate_factors,
557 [](double cf) { return cf != 1.0; })) {
558 RTC_LOG(LS_WARNING)
559 << "The configuration does not allow generating candidates. Specify "
560 "a candidate factor other than 1.0, allow the acknowledged rate "
561 "to be a candidate, and/or allow the delay based estimate to be a "
562 "candidate.";
563 valid = false;
564 }
565
566 if (config_->higher_bandwidth_bias_factor < 0.0) {
567 RTC_LOG(LS_WARNING)
568 << "The higher bandwidth bias factor must be non-negative: "
569 << config_->higher_bandwidth_bias_factor;
570 valid = false;
571 }
572 if (config_->inherent_loss_lower_bound < 0.0 ||
573 config_->inherent_loss_lower_bound >= 1.0) {
574 RTC_LOG(LS_WARNING) << "The inherent loss lower bound must be in [0, 1): "
575 << config_->inherent_loss_lower_bound;
576 valid = false;
577 }
578 if (config_->loss_threshold_of_high_bandwidth_preference < 0.0 ||
579 config_->loss_threshold_of_high_bandwidth_preference >= 1.0) {
580 RTC_LOG(LS_WARNING)
581 << "The loss threshold of high bandwidth preference must be in [0, 1): "
582 << config_->loss_threshold_of_high_bandwidth_preference;
583 valid = false;
584 }
585 if (config_->bandwidth_preference_smoothing_factor <= 0.0 ||
586 config_->bandwidth_preference_smoothing_factor > 1.0) {
587 RTC_LOG(LS_WARNING)
588 << "The bandwidth preference smoothing factor must be in (0, 1]: "
589 << config_->bandwidth_preference_smoothing_factor;
590 valid = false;
591 }
592 if (config_->inherent_loss_upper_bound_bandwidth_balance <=
593 DataRate::Zero()) {
594 RTC_LOG(LS_WARNING)
595 << "The inherent loss upper bound bandwidth balance "
596 "must be positive: "
597 << ToString(config_->inherent_loss_upper_bound_bandwidth_balance);
598 valid = false;
599 }
600 if (config_->inherent_loss_upper_bound_offset <
601 config_->inherent_loss_lower_bound ||
602 config_->inherent_loss_upper_bound_offset >= 1.0) {
603 RTC_LOG(LS_WARNING) << "The inherent loss upper bound must be greater "
604 "than or equal to the inherent "
605 "loss lower bound, which is "
606 << config_->inherent_loss_lower_bound
607 << ", and less than 1: "
608 << config_->inherent_loss_upper_bound_offset;
609 valid = false;
610 }
611 if (config_->initial_inherent_loss_estimate < 0.0 ||
612 config_->initial_inherent_loss_estimate >= 1.0) {
613 RTC_LOG(LS_WARNING)
614 << "The initial inherent loss estimate must be in [0, 1): "
615 << config_->initial_inherent_loss_estimate;
616 valid = false;
617 }
618 if (config_->newton_iterations <= 0) {
619 RTC_LOG(LS_WARNING) << "The number of Newton iterations must be positive: "
620 << config_->newton_iterations;
621 valid = false;
622 }
623 if (config_->newton_step_size <= 0.0) {
624 RTC_LOG(LS_WARNING) << "The Newton step size must be positive: "
625 << config_->newton_step_size;
626 valid = false;
627 }
628 if (config_->observation_duration_lower_bound <= TimeDelta::Zero()) {
629 RTC_LOG(LS_WARNING)
630 << "The observation duration lower bound must be positive: "
631 << ToString(config_->observation_duration_lower_bound);
632 valid = false;
633 }
634 if (config_->observation_window_size < 2) {
635 RTC_LOG(LS_WARNING) << "The observation window size must be at least 2: "
636 << config_->observation_window_size;
637 valid = false;
638 }
639 if (config_->sending_rate_smoothing_factor < 0.0 ||
640 config_->sending_rate_smoothing_factor >= 1.0) {
641 RTC_LOG(LS_WARNING)
642 << "The sending rate smoothing factor must be in [0, 1): "
643 << config_->sending_rate_smoothing_factor;
644 valid = false;
645 }
646 if (config_->instant_upper_bound_temporal_weight_factor <= 0.0 ||
647 config_->instant_upper_bound_temporal_weight_factor > 1.0) {
648 RTC_LOG(LS_WARNING)
649 << "The instant upper bound temporal weight factor must be in (0, 1]"
650 << config_->instant_upper_bound_temporal_weight_factor;
651 valid = false;
652 }
653 if (config_->instant_upper_bound_bandwidth_balance <= DataRate::Zero()) {
654 RTC_LOG(LS_WARNING)
655 << "The instant upper bound bandwidth balance must be positive: "
656 << ToString(config_->instant_upper_bound_bandwidth_balance);
657 valid = false;
658 }
659 if (config_->instant_upper_bound_loss_offset < 0.0 ||
660 config_->instant_upper_bound_loss_offset >= 1.0) {
661 RTC_LOG(LS_WARNING)
662 << "The instant upper bound loss offset must be in [0, 1): "
663 << config_->instant_upper_bound_loss_offset;
664 valid = false;
665 }
666 if (config_->temporal_weight_factor <= 0.0 ||
667 config_->temporal_weight_factor > 1.0) {
668 RTC_LOG(LS_WARNING) << "The temporal weight factor must be in (0, 1]: "
669 << config_->temporal_weight_factor;
670 valid = false;
671 }
672 if (config_->bandwidth_backoff_lower_bound_factor > 1.0) {
673 RTC_LOG(LS_WARNING)
674 << "The bandwidth backoff lower bound factor must not be greater than "
675 "1: "
676 << config_->bandwidth_backoff_lower_bound_factor;
677 valid = false;
678 }
679 if (config_->trendline_observations_window_size < 1) {
680 RTC_LOG(LS_WARNING) << "The trendline window size must be at least 1: "
681 << config_->trendline_observations_window_size;
682 valid = false;
683 }
684 if (config_->max_increase_factor <= 0.0) {
685 RTC_LOG(LS_WARNING) << "The maximum increase factor must be positive: "
686 << config_->max_increase_factor;
687 valid = false;
688 }
689 if (config_->delayed_increase_window <= TimeDelta::Zero()) {
690 RTC_LOG(LS_WARNING) << "The delayed increase window must be positive: "
691 << config_->delayed_increase_window.ms();
692 valid = false;
693 }
694 if (config_->high_loss_rate_threshold <= 0.0 ||
695 config_->high_loss_rate_threshold > 1.0) {
696 RTC_LOG(LS_WARNING) << "The high loss rate threshold must be in (0, 1]: "
697 << config_->high_loss_rate_threshold;
698 valid = false;
699 }
700 return valid;
701 }
702
GetAverageReportedLossRatio() const703 double LossBasedBweV2::GetAverageReportedLossRatio() const {
704 if (num_observations_ <= 0) {
705 return 0.0;
706 }
707
708 double num_packets = 0;
709 double num_lost_packets = 0;
710 for (const Observation& observation : observations_) {
711 if (!observation.IsInitialized()) {
712 continue;
713 }
714
715 double instant_temporal_weight =
716 instant_upper_bound_temporal_weights_[(num_observations_ - 1) -
717 observation.id];
718 num_packets += instant_temporal_weight * observation.num_packets;
719 num_lost_packets += instant_temporal_weight * observation.num_lost_packets;
720 }
721
722 return num_lost_packets / num_packets;
723 }
724
GetCandidateBandwidthUpperBound() const725 DataRate LossBasedBweV2::GetCandidateBandwidthUpperBound() const {
726 DataRate candidate_bandwidth_upper_bound = max_bitrate_;
727 if (IsBandwidthLimitedDueToLoss() &&
728 IsValid(bandwidth_limit_in_current_window_)) {
729 candidate_bandwidth_upper_bound = bandwidth_limit_in_current_window_;
730 }
731
732 if (config_->trendline_integration_enabled) {
733 candidate_bandwidth_upper_bound =
734 std::min(GetInstantUpperBound(), candidate_bandwidth_upper_bound);
735 if (IsValid(delay_based_estimate_)) {
736 candidate_bandwidth_upper_bound =
737 std::min(delay_based_estimate_, candidate_bandwidth_upper_bound);
738 }
739 }
740
741 if (!acknowledged_bitrate_.has_value())
742 return candidate_bandwidth_upper_bound;
743
744 if (config_->rampup_acceleration_max_factor > 0.0) {
745 const TimeDelta time_since_bandwidth_reduced = std::min(
746 config_->rampup_acceleration_maxout_time,
747 std::max(TimeDelta::Zero(), last_send_time_most_recent_observation_ -
748 last_time_estimate_reduced_));
749 const double rampup_acceleration = config_->rampup_acceleration_max_factor *
750 time_since_bandwidth_reduced /
751 config_->rampup_acceleration_maxout_time;
752
753 candidate_bandwidth_upper_bound +=
754 rampup_acceleration * (*acknowledged_bitrate_);
755 }
756 return candidate_bandwidth_upper_bound;
757 }
758
GetCandidates() const759 std::vector<LossBasedBweV2::ChannelParameters> LossBasedBweV2::GetCandidates()
760 const {
761 std::vector<DataRate> bandwidths;
762 bool can_increase_bitrate = TrendlineEsimateAllowBitrateIncrease();
763 for (double candidate_factor : config_->candidate_factors) {
764 if (!can_increase_bitrate && candidate_factor > 1.0) {
765 continue;
766 }
767 bandwidths.push_back(candidate_factor *
768 current_estimate_.loss_limited_bandwidth);
769 }
770
771 if (acknowledged_bitrate_.has_value() &&
772 config_->append_acknowledged_rate_candidate &&
773 TrendlineEsimateAllowEmergencyBackoff()) {
774 bandwidths.push_back(*acknowledged_bitrate_ *
775 config_->bandwidth_backoff_lower_bound_factor);
776 }
777
778 if (IsValid(delay_based_estimate_) &&
779 config_->append_delay_based_estimate_candidate) {
780 if (can_increase_bitrate &&
781 delay_based_estimate_ > current_estimate_.loss_limited_bandwidth) {
782 bandwidths.push_back(delay_based_estimate_);
783 }
784 }
785
786 const DataRate candidate_bandwidth_upper_bound =
787 GetCandidateBandwidthUpperBound();
788
789 std::vector<ChannelParameters> candidates;
790 candidates.resize(bandwidths.size());
791 for (size_t i = 0; i < bandwidths.size(); ++i) {
792 ChannelParameters candidate = current_estimate_;
793 if (config_->trendline_integration_enabled) {
794 candidate.loss_limited_bandwidth =
795 std::min(bandwidths[i], candidate_bandwidth_upper_bound);
796 } else {
797 candidate.loss_limited_bandwidth = std::min(
798 bandwidths[i], std::max(current_estimate_.loss_limited_bandwidth,
799 candidate_bandwidth_upper_bound));
800 }
801 candidate.inherent_loss = GetFeasibleInherentLoss(candidate);
802 candidates[i] = candidate;
803 }
804 return candidates;
805 }
806
GetDerivatives(const ChannelParameters & channel_parameters) const807 LossBasedBweV2::Derivatives LossBasedBweV2::GetDerivatives(
808 const ChannelParameters& channel_parameters) const {
809 Derivatives derivatives;
810
811 for (const Observation& observation : observations_) {
812 if (!observation.IsInitialized()) {
813 continue;
814 }
815
816 double loss_probability = GetLossProbability(
817 channel_parameters.inherent_loss,
818 channel_parameters.loss_limited_bandwidth, observation.sending_rate);
819
820 double temporal_weight =
821 temporal_weights_[(num_observations_ - 1) - observation.id];
822
823 derivatives.first +=
824 temporal_weight *
825 ((observation.num_lost_packets / loss_probability) -
826 (observation.num_received_packets / (1.0 - loss_probability)));
827 derivatives.second -=
828 temporal_weight *
829 ((observation.num_lost_packets / std::pow(loss_probability, 2)) +
830 (observation.num_received_packets /
831 std::pow(1.0 - loss_probability, 2)));
832 }
833
834 if (derivatives.second >= 0.0) {
835 RTC_LOG(LS_ERROR) << "The second derivative is mathematically guaranteed "
836 "to be negative but is "
837 << derivatives.second << ".";
838 derivatives.second = -1.0e-6;
839 }
840
841 return derivatives;
842 }
843
GetFeasibleInherentLoss(const ChannelParameters & channel_parameters) const844 double LossBasedBweV2::GetFeasibleInherentLoss(
845 const ChannelParameters& channel_parameters) const {
846 return std::min(
847 std::max(channel_parameters.inherent_loss,
848 config_->inherent_loss_lower_bound),
849 GetInherentLossUpperBound(channel_parameters.loss_limited_bandwidth));
850 }
851
GetInherentLossUpperBound(DataRate bandwidth) const852 double LossBasedBweV2::GetInherentLossUpperBound(DataRate bandwidth) const {
853 if (bandwidth.IsZero()) {
854 return 1.0;
855 }
856
857 double inherent_loss_upper_bound =
858 config_->inherent_loss_upper_bound_offset +
859 config_->inherent_loss_upper_bound_bandwidth_balance / bandwidth;
860 return std::min(inherent_loss_upper_bound, 1.0);
861 }
862
AdjustBiasFactor(double loss_rate,double bias_factor) const863 double LossBasedBweV2::AdjustBiasFactor(double loss_rate,
864 double bias_factor) const {
865 return bias_factor *
866 (config_->loss_threshold_of_high_bandwidth_preference - loss_rate) /
867 (config_->bandwidth_preference_smoothing_factor +
868 std::abs(config_->loss_threshold_of_high_bandwidth_preference -
869 loss_rate));
870 }
871
GetHighBandwidthBias(DataRate bandwidth) const872 double LossBasedBweV2::GetHighBandwidthBias(DataRate bandwidth) const {
873 if (IsValid(bandwidth)) {
874 const double average_reported_loss_ratio = GetAverageReportedLossRatio();
875 return AdjustBiasFactor(average_reported_loss_ratio,
876 config_->higher_bandwidth_bias_factor) *
877 bandwidth.kbps() +
878 AdjustBiasFactor(average_reported_loss_ratio,
879 config_->higher_log_bandwidth_bias_factor) *
880 std::log(1.0 + bandwidth.kbps());
881 }
882 return 0.0;
883 }
884
GetObjective(const ChannelParameters & channel_parameters) const885 double LossBasedBweV2::GetObjective(
886 const ChannelParameters& channel_parameters) const {
887 double objective = 0.0;
888
889 const double high_bandwidth_bias =
890 GetHighBandwidthBias(channel_parameters.loss_limited_bandwidth);
891
892 for (const Observation& observation : observations_) {
893 if (!observation.IsInitialized()) {
894 continue;
895 }
896
897 double loss_probability = GetLossProbability(
898 channel_parameters.inherent_loss,
899 channel_parameters.loss_limited_bandwidth, observation.sending_rate);
900
901 double temporal_weight =
902 temporal_weights_[(num_observations_ - 1) - observation.id];
903
904 objective +=
905 temporal_weight *
906 ((observation.num_lost_packets * std::log(loss_probability)) +
907 (observation.num_received_packets * std::log(1.0 - loss_probability)));
908 objective +=
909 temporal_weight * high_bandwidth_bias * observation.num_packets;
910 }
911
912 return objective;
913 }
914
GetSendingRate(DataRate instantaneous_sending_rate) const915 DataRate LossBasedBweV2::GetSendingRate(
916 DataRate instantaneous_sending_rate) const {
917 if (num_observations_ <= 0) {
918 return instantaneous_sending_rate;
919 }
920
921 const int most_recent_observation_idx =
922 (num_observations_ - 1) % config_->observation_window_size;
923 const Observation& most_recent_observation =
924 observations_[most_recent_observation_idx];
925 DataRate sending_rate_previous_observation =
926 most_recent_observation.sending_rate;
927
928 return config_->sending_rate_smoothing_factor *
929 sending_rate_previous_observation +
930 (1.0 - config_->sending_rate_smoothing_factor) *
931 instantaneous_sending_rate;
932 }
933
GetInstantUpperBound() const934 DataRate LossBasedBweV2::GetInstantUpperBound() const {
935 return cached_instant_upper_bound_.value_or(max_bitrate_);
936 }
937
CalculateInstantUpperBound()938 void LossBasedBweV2::CalculateInstantUpperBound() {
939 DataRate instant_limit = max_bitrate_;
940 const double average_reported_loss_ratio = GetAverageReportedLossRatio();
941 if (average_reported_loss_ratio > config_->instant_upper_bound_loss_offset) {
942 instant_limit = config_->instant_upper_bound_bandwidth_balance /
943 (average_reported_loss_ratio -
944 config_->instant_upper_bound_loss_offset);
945 if (average_reported_loss_ratio > config_->high_loss_rate_threshold) {
946 instant_limit = std::min(
947 instant_limit, DataRate::KilobitsPerSec(std::max(
948 static_cast<double>(min_bitrate_.kbps()),
949 config_->bandwidth_cap_at_high_loss_rate.kbps() -
950 config_->slope_of_bwe_high_loss_func *
951 average_reported_loss_ratio)));
952 }
953 }
954
955 if (IsBandwidthLimitedDueToLoss()) {
956 if (IsValid(upper_link_capacity_) &&
957 config_->bound_by_upper_link_capacity_when_loss_limited) {
958 instant_limit = std::min(instant_limit, upper_link_capacity_);
959 }
960 }
961 cached_instant_upper_bound_ = instant_limit;
962 }
963
CalculateTemporalWeights()964 void LossBasedBweV2::CalculateTemporalWeights() {
965 for (int i = 0; i < config_->observation_window_size; ++i) {
966 temporal_weights_[i] = std::pow(config_->temporal_weight_factor, i);
967 instant_upper_bound_temporal_weights_[i] =
968 std::pow(config_->instant_upper_bound_temporal_weight_factor, i);
969 }
970 }
971
NewtonsMethodUpdate(ChannelParameters & channel_parameters) const972 void LossBasedBweV2::NewtonsMethodUpdate(
973 ChannelParameters& channel_parameters) const {
974 if (num_observations_ <= 0) {
975 return;
976 }
977
978 for (int i = 0; i < config_->newton_iterations; ++i) {
979 const Derivatives derivatives = GetDerivatives(channel_parameters);
980 channel_parameters.inherent_loss -=
981 config_->newton_step_size * derivatives.first / derivatives.second;
982 channel_parameters.inherent_loss =
983 GetFeasibleInherentLoss(channel_parameters);
984 }
985 }
986
TrendlineEsimateAllowBitrateIncrease() const987 bool LossBasedBweV2::TrendlineEsimateAllowBitrateIncrease() const {
988 if (!config_->trendline_integration_enabled) {
989 return true;
990 }
991
992 for (const auto& detector_state : delay_detector_states_) {
993 if (detector_state == BandwidthUsage::kBwOverusing ||
994 detector_state == BandwidthUsage::kBwUnderusing) {
995 return false;
996 }
997 }
998 return true;
999 }
1000
TrendlineEsimateAllowEmergencyBackoff() const1001 bool LossBasedBweV2::TrendlineEsimateAllowEmergencyBackoff() const {
1002 if (!config_->trendline_integration_enabled) {
1003 return true;
1004 }
1005
1006 if (!config_->use_acked_bitrate_only_when_overusing) {
1007 return true;
1008 }
1009
1010 for (const auto& detector_state : delay_detector_states_) {
1011 if (detector_state == BandwidthUsage::kBwOverusing) {
1012 return true;
1013 }
1014 }
1015
1016 return false;
1017 }
1018
PushBackObservation(rtc::ArrayView<const PacketResult> packet_results,BandwidthUsage delay_detector_state)1019 bool LossBasedBweV2::PushBackObservation(
1020 rtc::ArrayView<const PacketResult> packet_results,
1021 BandwidthUsage delay_detector_state) {
1022 delay_detector_states_.push_front(delay_detector_state);
1023 if (static_cast<int>(delay_detector_states_.size()) >
1024 config_->trendline_observations_window_size) {
1025 delay_detector_states_.pop_back();
1026 }
1027
1028 if (packet_results.empty()) {
1029 return false;
1030 }
1031
1032 PacketResultsSummary packet_results_summary =
1033 GetPacketResultsSummary(packet_results);
1034
1035 partial_observation_.num_packets += packet_results_summary.num_packets;
1036 partial_observation_.num_lost_packets +=
1037 packet_results_summary.num_lost_packets;
1038 partial_observation_.size += packet_results_summary.total_size;
1039
1040 // This is the first packet report we have received.
1041 if (!IsValid(last_send_time_most_recent_observation_)) {
1042 last_send_time_most_recent_observation_ =
1043 packet_results_summary.first_send_time;
1044 }
1045
1046 const Timestamp last_send_time = packet_results_summary.last_send_time;
1047 const TimeDelta observation_duration =
1048 last_send_time - last_send_time_most_recent_observation_;
1049 // Too small to be meaningful.
1050 if (observation_duration <= TimeDelta::Zero() ||
1051 (observation_duration < config_->observation_duration_lower_bound &&
1052 (delay_detector_state != BandwidthUsage::kBwOverusing ||
1053 !config_->trendline_integration_enabled))) {
1054 return false;
1055 }
1056
1057 last_send_time_most_recent_observation_ = last_send_time;
1058
1059 Observation observation;
1060 observation.num_packets = partial_observation_.num_packets;
1061 observation.num_lost_packets = partial_observation_.num_lost_packets;
1062 observation.num_received_packets =
1063 observation.num_packets - observation.num_lost_packets;
1064 observation.sending_rate =
1065 GetSendingRate(partial_observation_.size / observation_duration);
1066 observation.id = num_observations_++;
1067 observations_[observation.id % config_->observation_window_size] =
1068 observation;
1069
1070 partial_observation_ = PartialObservation();
1071
1072 CalculateInstantUpperBound();
1073 return true;
1074 }
1075
IsBandwidthLimitedDueToLoss() const1076 bool LossBasedBweV2::IsBandwidthLimitedDueToLoss() const {
1077 return current_state_ != LossBasedState::kDelayBasedEstimate;
1078 }
1079
1080 } // namespace webrtc
1081