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/bbr/bbr_network_controller.h"
12
13 #include <algorithm>
14 #include <array>
15 #include <string>
16 #include <vector>
17
18 #include "absl/base/macros.h"
19 #include "rtc_base/checks.h"
20 #include "rtc_base/logging.h"
21 #include "system_wrappers/include/field_trial.h"
22
23 namespace webrtc {
24 namespace bbr {
25 namespace {
26
27 // If greater than zero, mean RTT variation is multiplied by the specified
28 // factor and added to the congestion window limit.
29 const double kBbrRttVariationWeight = 0.0f;
30
31 // Congestion window gain for QUIC BBR during PROBE_BW phase.
32 const double kProbeBWCongestionWindowGain = 2.0f;
33
34 // The maximum packet size of any QUIC packet, based on ethernet's max size,
35 // minus the IP and UDP headers. IPv6 has a 40 byte header, UDP adds an
36 // additional 8 bytes. This is a total overhead of 48 bytes. Ethernet's
37 // max packet size is 1500 bytes, 1500 - 48 = 1452.
38 const DataSize kMaxPacketSize = DataSize::Bytes(1452);
39
40 // Default maximum packet size used in the Linux TCP implementation.
41 // Used in QUIC for congestion window computations in bytes.
42 constexpr DataSize kDefaultTCPMSS = DataSize::Bytes(1460);
43 // Constants based on TCP defaults.
44 constexpr DataSize kMaxSegmentSize = kDefaultTCPMSS;
45
46 // The gain used for the slow start, equal to 2/ln(2).
47 const double kHighGain = 2.885f;
48 // The gain used in STARTUP after loss has been detected.
49 // 1.5 is enough to allow for 25% exogenous loss and still observe a 25% growth
50 // in measured bandwidth.
51 const double kStartupAfterLossGain = 1.5;
52 // The gain used to drain the queue after the slow start.
53 const double kDrainGain = 1.f / kHighGain;
54
55 // The length of the gain cycle.
56 const size_t kGainCycleLength = 8;
57 // The size of the bandwidth filter window, in round-trips.
58 const BbrRoundTripCount kBandwidthWindowSize = kGainCycleLength + 2;
59
60 // The time after which the current min_rtt value expires.
61 constexpr int64_t kMinRttExpirySeconds = 10;
62 // The minimum time the connection can spend in PROBE_RTT mode.
63 constexpr int64_t kProbeRttTimeMs = 200;
64 // If the bandwidth does not increase by the factor of |kStartupGrowthTarget|
65 // within |kRoundTripsWithoutGrowthBeforeExitingStartup| rounds, the connection
66 // will exit the STARTUP mode.
67 const double kStartupGrowthTarget = 1.25;
68 // Coefficient to determine if a new RTT is sufficiently similar to min_rtt that
69 // we don't need to enter PROBE_RTT.
70 const double kSimilarMinRttThreshold = 1.125;
71
72 constexpr int64_t kInitialBandwidthKbps = 300;
73
74 const int64_t kInitialCongestionWindowPackets = 32;
75 // The minimum CWND to ensure delayed acks don't reduce bandwidth measurements.
76 // Does not inflate the pacing rate.
77 const int64_t kDefaultMinCongestionWindowPackets = 4;
78 const int64_t kDefaultMaxCongestionWindowPackets = 2000;
79
80 const char kBbrConfigTrial[] = "WebRTC-BweBbrConfig";
81
82 } // namespace
83
BbrControllerConfig(std::string field_trial)84 BbrNetworkController::BbrControllerConfig::BbrControllerConfig(
85 std::string field_trial)
86 : probe_bw_pacing_gain_offset("probe_bw_pacing_gain_offset", 0.25),
87 encoder_rate_gain("encoder_rate_gain", 1),
88 encoder_rate_gain_in_probe_rtt("encoder_rate_gain_in_probe_rtt", 1),
89 exit_startup_rtt_threshold("exit_startup_rtt_threshold",
90 TimeDelta::PlusInfinity()),
91 initial_congestion_window(
92 "initial_cwin",
93 kInitialCongestionWindowPackets * kDefaultTCPMSS),
94 min_congestion_window(
95 "min_cwin",
96 kDefaultMinCongestionWindowPackets * kDefaultTCPMSS),
97 max_congestion_window(
98 "max_cwin",
99 kDefaultMaxCongestionWindowPackets * kDefaultTCPMSS),
100 probe_rtt_congestion_window_gain("probe_rtt_cwin_gain", 0.75),
101 pacing_rate_as_target("pacing_rate_as_target", false),
102 exit_startup_on_loss("exit_startup_on_loss", true),
103 num_startup_rtts("num_startup_rtts", 3),
104 rate_based_recovery("rate_based_recovery", false),
105 max_aggregation_bytes_multiplier("max_aggregation_bytes_multiplier", 0),
106 slower_startup("slower_startup", false),
107 rate_based_startup("rate_based_startup", false),
108 initial_conservation_in_startup("initial_conservation",
109 CONSERVATION,
110 {
111 {"NOT_IN_RECOVERY", NOT_IN_RECOVERY},
112 {"CONSERVATION", CONSERVATION},
113 {"MEDIUM_GROWTH", MEDIUM_GROWTH},
114 {"GROWTH", GROWTH},
115 }),
116 fully_drain_queue("fully_drain_queue", false),
117 max_ack_height_window_multiplier("max_ack_height_window_multiplier", 1),
118 probe_rtt_based_on_bdp("probe_rtt_based_on_bdp", false),
119 probe_rtt_skipped_if_similar_rtt("probe_rtt_skipped_if_similar_rtt",
120 false),
121 probe_rtt_disabled_if_app_limited("probe_rtt_disabled_if_app_limited",
122 false) {
123 ParseFieldTrial(
124 {
125 &exit_startup_on_loss,
126 &encoder_rate_gain,
127 &encoder_rate_gain_in_probe_rtt,
128 &exit_startup_rtt_threshold,
129 &fully_drain_queue,
130 &initial_congestion_window,
131 &initial_conservation_in_startup,
132 &max_ack_height_window_multiplier,
133 &max_aggregation_bytes_multiplier,
134 &max_congestion_window,
135 &min_congestion_window,
136 &num_startup_rtts,
137 &pacing_rate_as_target,
138 &probe_bw_pacing_gain_offset,
139 &probe_rtt_based_on_bdp,
140 &probe_rtt_congestion_window_gain,
141 &probe_rtt_disabled_if_app_limited,
142 &probe_rtt_skipped_if_similar_rtt,
143 &rate_based_recovery,
144 &rate_based_startup,
145 &slower_startup,
146 },
147 field_trial);
148 }
149 BbrNetworkController::BbrControllerConfig::~BbrControllerConfig() = default;
150 BbrNetworkController::BbrControllerConfig::BbrControllerConfig(
151 const BbrControllerConfig&) = default;
152 BbrNetworkController::BbrControllerConfig
FromTrial()153 BbrNetworkController::BbrControllerConfig::FromTrial() {
154 return BbrControllerConfig(
155 webrtc::field_trial::FindFullName(kBbrConfigTrial));
156 }
157
DebugState(const BbrNetworkController & sender)158 BbrNetworkController::DebugState::DebugState(const BbrNetworkController& sender)
159 : mode(sender.mode_),
160 max_bandwidth(sender.max_bandwidth_.GetBest()),
161 round_trip_count(sender.round_trip_count_),
162 gain_cycle_index(sender.cycle_current_offset_),
163 congestion_window(sender.congestion_window_),
164 is_at_full_bandwidth(sender.is_at_full_bandwidth_),
165 bandwidth_at_last_round(sender.bandwidth_at_last_round_),
166 rounds_without_bandwidth_gain(sender.rounds_without_bandwidth_gain_),
167 min_rtt(sender.min_rtt_),
168 min_rtt_timestamp(sender.min_rtt_timestamp_),
169 recovery_state(sender.recovery_state_),
170 recovery_window(sender.recovery_window_),
171 last_sample_is_app_limited(sender.last_sample_is_app_limited_),
172 end_of_app_limited_phase(sender.sampler_->end_of_app_limited_phase()) {}
173
174 BbrNetworkController::DebugState::DebugState(const DebugState& state) = default;
175
BbrNetworkController(NetworkControllerConfig config)176 BbrNetworkController::BbrNetworkController(NetworkControllerConfig config)
177 : config_(BbrControllerConfig::FromTrial()),
178 rtt_stats_(),
179 random_(10),
180 loss_rate_(),
181 mode_(STARTUP),
182 sampler_(new BandwidthSampler()),
183 round_trip_count_(0),
184 last_sent_packet_(0),
185 current_round_trip_end_(0),
186 max_bandwidth_(kBandwidthWindowSize, DataRate::Zero(), 0),
187 default_bandwidth_(DataRate::KilobitsPerSec(kInitialBandwidthKbps)),
188 max_ack_height_(kBandwidthWindowSize, DataSize::Zero(), 0),
189 aggregation_epoch_start_time_(),
190 aggregation_epoch_bytes_(DataSize::Zero()),
191 bytes_acked_since_queue_drained_(DataSize::Zero()),
192 max_aggregation_bytes_multiplier_(0),
193 min_rtt_(TimeDelta::Zero()),
194 last_rtt_(TimeDelta::Zero()),
195 min_rtt_timestamp_(Timestamp::MinusInfinity()),
196 congestion_window_(config_.initial_congestion_window),
197 initial_congestion_window_(config_.initial_congestion_window),
198 min_congestion_window_(config_.min_congestion_window),
199 max_congestion_window_(config_.max_congestion_window),
200 pacing_rate_(DataRate::Zero()),
201 pacing_gain_(1),
202 congestion_window_gain_constant_(kProbeBWCongestionWindowGain),
203 rtt_variance_weight_(kBbrRttVariationWeight),
204 cycle_current_offset_(0),
205 last_cycle_start_(Timestamp::MinusInfinity()),
206 is_at_full_bandwidth_(false),
207 rounds_without_bandwidth_gain_(0),
208 bandwidth_at_last_round_(DataRate::Zero()),
209 exiting_quiescence_(false),
210 exit_probe_rtt_at_(),
211 probe_rtt_round_passed_(false),
212 last_sample_is_app_limited_(false),
213 recovery_state_(NOT_IN_RECOVERY),
214 end_recovery_at_(),
215 recovery_window_(max_congestion_window_),
216 app_limited_since_last_probe_rtt_(false),
217 min_rtt_since_last_probe_rtt_(TimeDelta::PlusInfinity()) {
218 RTC_LOG(LS_INFO) << "Creating BBR controller";
219 if (config.constraints.starting_rate)
220 default_bandwidth_ = *config.constraints.starting_rate;
221 constraints_ = config.constraints;
222 Reset();
223 }
224
~BbrNetworkController()225 BbrNetworkController::~BbrNetworkController() {}
226
Reset()227 void BbrNetworkController::Reset() {
228 round_trip_count_ = 0;
229 rounds_without_bandwidth_gain_ = 0;
230 if (config_.num_startup_rtts > 0) {
231 is_at_full_bandwidth_ = false;
232 EnterStartupMode();
233 } else {
234 is_at_full_bandwidth_ = true;
235 EnterProbeBandwidthMode(constraints_->at_time);
236 }
237 }
238
CreateRateUpdate(Timestamp at_time) const239 NetworkControlUpdate BbrNetworkController::CreateRateUpdate(
240 Timestamp at_time) const {
241 DataRate bandwidth = BandwidthEstimate();
242 if (bandwidth.IsZero())
243 bandwidth = default_bandwidth_;
244 TimeDelta rtt = GetMinRtt();
245 DataRate pacing_rate = PacingRate();
246 DataRate target_rate =
247 config_.pacing_rate_as_target ? pacing_rate : bandwidth;
248
249 if (mode_ == PROBE_RTT)
250 target_rate = target_rate * config_.encoder_rate_gain_in_probe_rtt;
251 else
252 target_rate = target_rate * config_.encoder_rate_gain;
253 target_rate = std::min(target_rate, pacing_rate);
254
255 if (constraints_) {
256 if (constraints_->max_data_rate) {
257 target_rate = std::min(target_rate, *constraints_->max_data_rate);
258 pacing_rate = std::min(pacing_rate, *constraints_->max_data_rate);
259 }
260 if (constraints_->min_data_rate) {
261 target_rate = std::max(target_rate, *constraints_->min_data_rate);
262 pacing_rate = std::max(pacing_rate, *constraints_->min_data_rate);
263 }
264 }
265
266 NetworkControlUpdate update;
267
268 TargetTransferRate target_rate_msg;
269 target_rate_msg.network_estimate.at_time = at_time;
270 target_rate_msg.network_estimate.round_trip_time = rtt;
271
272 // TODO(srte): Fill in field below with proper value.
273 target_rate_msg.network_estimate.loss_rate_ratio = 0;
274 // In in PROBE_BW, target bandwidth is expected to vary over the cycle period.
275 // In other modes the is no given period, therefore the same value as in
276 // PROBE_BW is used for consistency.
277 target_rate_msg.network_estimate.bwe_period =
278 rtt * static_cast<int64_t>(kGainCycleLength);
279
280 target_rate_msg.target_rate = target_rate;
281 target_rate_msg.at_time = at_time;
282 update.target_rate = target_rate_msg;
283
284 PacerConfig pacer_config;
285 // A small time window ensures an even pacing rate.
286 pacer_config.time_window = rtt * 0.25;
287 pacer_config.data_window = pacer_config.time_window * pacing_rate;
288
289 if (IsProbingForMoreBandwidth())
290 pacer_config.pad_window = pacer_config.data_window;
291 else
292 pacer_config.pad_window = DataSize::Zero();
293
294 pacer_config.at_time = at_time;
295 update.pacer_config = pacer_config;
296
297 update.congestion_window = GetCongestionWindow();
298 return update;
299 }
300
OnNetworkAvailability(NetworkAvailability msg)301 NetworkControlUpdate BbrNetworkController::OnNetworkAvailability(
302 NetworkAvailability msg) {
303 Reset();
304 rtt_stats_.OnConnectionMigration();
305 return CreateRateUpdate(msg.at_time);
306 }
307
OnNetworkRouteChange(NetworkRouteChange msg)308 NetworkControlUpdate BbrNetworkController::OnNetworkRouteChange(
309 NetworkRouteChange msg) {
310 constraints_ = msg.constraints;
311 Reset();
312 if (msg.constraints.starting_rate)
313 default_bandwidth_ = *msg.constraints.starting_rate;
314
315 rtt_stats_.OnConnectionMigration();
316 return CreateRateUpdate(msg.at_time);
317 }
318
OnProcessInterval(ProcessInterval msg)319 NetworkControlUpdate BbrNetworkController::OnProcessInterval(
320 ProcessInterval msg) {
321 return CreateRateUpdate(msg.at_time);
322 }
323
OnStreamsConfig(StreamsConfig msg)324 NetworkControlUpdate BbrNetworkController::OnStreamsConfig(StreamsConfig msg) {
325 return NetworkControlUpdate();
326 }
327
OnTargetRateConstraints(TargetRateConstraints msg)328 NetworkControlUpdate BbrNetworkController::OnTargetRateConstraints(
329 TargetRateConstraints msg) {
330 constraints_ = msg;
331 return CreateRateUpdate(msg.at_time);
332 }
333
InSlowStart() const334 bool BbrNetworkController::InSlowStart() const {
335 return mode_ == STARTUP;
336 }
337
OnSentPacket(SentPacket msg)338 NetworkControlUpdate BbrNetworkController::OnSentPacket(SentPacket msg) {
339 last_sent_packet_ = msg.sequence_number;
340
341 if (msg.data_in_flight.IsZero() && sampler_->is_app_limited()) {
342 exiting_quiescence_ = true;
343 }
344
345 if (!aggregation_epoch_start_time_) {
346 aggregation_epoch_start_time_ = msg.send_time;
347 }
348
349 sampler_->OnPacketSent(msg.send_time, msg.sequence_number, msg.size,
350 msg.data_in_flight);
351 return NetworkControlUpdate();
352 }
353
CanSend(DataSize bytes_in_flight)354 bool BbrNetworkController::CanSend(DataSize bytes_in_flight) {
355 return bytes_in_flight < GetCongestionWindow();
356 }
357
PacingRate() const358 DataRate BbrNetworkController::PacingRate() const {
359 if (pacing_rate_.IsZero()) {
360 return kHighGain * initial_congestion_window_ / GetMinRtt();
361 }
362 return pacing_rate_;
363 }
364
BandwidthEstimate() const365 DataRate BbrNetworkController::BandwidthEstimate() const {
366 return max_bandwidth_.GetBest();
367 }
368
GetCongestionWindow() const369 DataSize BbrNetworkController::GetCongestionWindow() const {
370 if (mode_ == PROBE_RTT) {
371 return ProbeRttCongestionWindow();
372 }
373
374 if (InRecovery() && !config_.rate_based_recovery &&
375 !(config_.rate_based_startup && mode_ == STARTUP)) {
376 return std::min(congestion_window_, recovery_window_);
377 }
378
379 return congestion_window_;
380 }
381
GetPacingGain(int round_offset) const382 double BbrNetworkController::GetPacingGain(int round_offset) const {
383 if (round_offset == 0)
384 return 1 + config_.probe_bw_pacing_gain_offset;
385 else if (round_offset == 1)
386 return 1 - config_.probe_bw_pacing_gain_offset;
387 else
388 return 1;
389 }
390
InRecovery() const391 bool BbrNetworkController::InRecovery() const {
392 return recovery_state_ != NOT_IN_RECOVERY;
393 }
394
IsProbingForMoreBandwidth() const395 bool BbrNetworkController::IsProbingForMoreBandwidth() const {
396 return (mode_ == PROBE_BW && pacing_gain_ > 1) || mode_ == STARTUP;
397 }
398
OnTransportPacketsFeedback(TransportPacketsFeedback msg)399 NetworkControlUpdate BbrNetworkController::OnTransportPacketsFeedback(
400 TransportPacketsFeedback msg) {
401 if (msg.packet_feedbacks.empty())
402 return NetworkControlUpdate();
403
404 Timestamp feedback_recv_time = msg.feedback_time;
405 SentPacket last_sent_packet = msg.PacketsWithFeedback().back().sent_packet;
406
407 Timestamp send_time = last_sent_packet.send_time;
408 TimeDelta send_delta = feedback_recv_time - send_time;
409 rtt_stats_.UpdateRtt(send_delta, TimeDelta::Zero(), feedback_recv_time);
410
411 const DataSize total_data_acked_before = sampler_->total_data_acked();
412
413 bool is_round_start = false;
414 bool min_rtt_expired = false;
415
416 std::vector<PacketResult> lost_packets = msg.LostWithSendInfo();
417 DiscardLostPackets(lost_packets);
418
419 std::vector<PacketResult> acked_packets = msg.ReceivedWithSendInfo();
420
421 int packets_sent =
422 static_cast<int>(lost_packets.size() + acked_packets.size());
423 int packets_lost = static_cast<int>(lost_packets.size());
424 loss_rate_.UpdateWithLossStatus(msg.feedback_time.ms(), packets_sent,
425 packets_lost);
426
427 // Input the new data into the BBR model of the connection.
428 if (!acked_packets.empty()) {
429 int64_t last_acked_packet =
430 acked_packets.rbegin()->sent_packet.sequence_number;
431
432 is_round_start = UpdateRoundTripCounter(last_acked_packet);
433 min_rtt_expired =
434 UpdateBandwidthAndMinRtt(msg.feedback_time, acked_packets);
435 UpdateRecoveryState(last_acked_packet, !lost_packets.empty(),
436 is_round_start);
437
438 const DataSize data_acked =
439 sampler_->total_data_acked() - total_data_acked_before;
440
441 UpdateAckAggregationBytes(msg.feedback_time, data_acked);
442 if (max_aggregation_bytes_multiplier_ > 0) {
443 if (msg.data_in_flight <=
444 1.25 * GetTargetCongestionWindow(pacing_gain_)) {
445 bytes_acked_since_queue_drained_ = DataSize::Zero();
446 } else {
447 bytes_acked_since_queue_drained_ += data_acked;
448 }
449 }
450 }
451
452 // Handle logic specific to PROBE_BW mode.
453 if (mode_ == PROBE_BW) {
454 UpdateGainCyclePhase(msg.feedback_time, msg.prior_in_flight,
455 !lost_packets.empty());
456 }
457
458 // Handle logic specific to STARTUP and DRAIN modes.
459 if (is_round_start && !is_at_full_bandwidth_) {
460 CheckIfFullBandwidthReached();
461 }
462 MaybeExitStartupOrDrain(msg);
463
464 // Handle logic specific to PROBE_RTT.
465 MaybeEnterOrExitProbeRtt(msg, is_round_start, min_rtt_expired);
466
467 // Calculate number of packets acked and lost.
468 DataSize data_acked = sampler_->total_data_acked() - total_data_acked_before;
469 DataSize data_lost = DataSize::Zero();
470 for (const PacketResult& packet : lost_packets) {
471 data_lost += packet.sent_packet.size;
472 }
473
474 // After the model is updated, recalculate the pacing rate and congestion
475 // window.
476 CalculatePacingRate();
477 CalculateCongestionWindow(data_acked);
478 CalculateRecoveryWindow(data_acked, data_lost, msg.data_in_flight);
479 // Cleanup internal state.
480 if (!acked_packets.empty()) {
481 sampler_->RemoveObsoletePackets(
482 acked_packets.back().sent_packet.sequence_number);
483 }
484 return CreateRateUpdate(msg.feedback_time);
485 }
486
OnRemoteBitrateReport(RemoteBitrateReport msg)487 NetworkControlUpdate BbrNetworkController::OnRemoteBitrateReport(
488 RemoteBitrateReport msg) {
489 return NetworkControlUpdate();
490 }
OnRoundTripTimeUpdate(RoundTripTimeUpdate msg)491 NetworkControlUpdate BbrNetworkController::OnRoundTripTimeUpdate(
492 RoundTripTimeUpdate msg) {
493 return NetworkControlUpdate();
494 }
OnTransportLossReport(TransportLossReport msg)495 NetworkControlUpdate BbrNetworkController::OnTransportLossReport(
496 TransportLossReport msg) {
497 return NetworkControlUpdate();
498 }
499
OnReceivedPacket(ReceivedPacket msg)500 NetworkControlUpdate BbrNetworkController::OnReceivedPacket(
501 ReceivedPacket msg) {
502 return NetworkControlUpdate();
503 }
504
OnNetworkStateEstimate(NetworkStateEstimate msg)505 NetworkControlUpdate BbrNetworkController::OnNetworkStateEstimate(
506 NetworkStateEstimate msg) {
507 return NetworkControlUpdate();
508 }
509
GetMinRtt() const510 TimeDelta BbrNetworkController::GetMinRtt() const {
511 return !min_rtt_.IsZero() ? min_rtt_
512 : TimeDelta::Micros(rtt_stats_.initial_rtt_us());
513 }
514
GetTargetCongestionWindow(double gain) const515 DataSize BbrNetworkController::GetTargetCongestionWindow(double gain) const {
516 DataSize bdp = GetMinRtt() * BandwidthEstimate();
517 DataSize congestion_window = gain * bdp;
518
519 // BDP estimate will be zero if no bandwidth samples are available yet.
520 if (congestion_window.IsZero()) {
521 congestion_window = gain * initial_congestion_window_;
522 }
523
524 return std::max(congestion_window, min_congestion_window_);
525 }
526
ProbeRttCongestionWindow() const527 DataSize BbrNetworkController::ProbeRttCongestionWindow() const {
528 if (config_.probe_rtt_based_on_bdp) {
529 return GetTargetCongestionWindow(config_.probe_rtt_congestion_window_gain);
530 }
531 return min_congestion_window_;
532 }
533
EnterStartupMode()534 void BbrNetworkController::EnterStartupMode() {
535 mode_ = STARTUP;
536 pacing_gain_ = kHighGain;
537 congestion_window_gain_ = kHighGain;
538 }
539
EnterProbeBandwidthMode(Timestamp now)540 void BbrNetworkController::EnterProbeBandwidthMode(Timestamp now) {
541 mode_ = PROBE_BW;
542 congestion_window_gain_ = congestion_window_gain_constant_;
543
544 // Pick a random offset for the gain cycle out of {0, 2..7} range. 1 is
545 // excluded because in that case increased gain and decreased gain would not
546 // follow each other.
547 cycle_current_offset_ = random_.Rand(kGainCycleLength - 2);
548 if (cycle_current_offset_ >= 1) {
549 cycle_current_offset_ += 1;
550 }
551
552 last_cycle_start_ = now;
553 pacing_gain_ = GetPacingGain(cycle_current_offset_);
554 }
555
DiscardLostPackets(const std::vector<PacketResult> & lost_packets)556 void BbrNetworkController::DiscardLostPackets(
557 const std::vector<PacketResult>& lost_packets) {
558 for (const PacketResult& packet : lost_packets) {
559 sampler_->OnPacketLost(packet.sent_packet.sequence_number);
560 }
561 }
562
UpdateRoundTripCounter(int64_t last_acked_packet)563 bool BbrNetworkController::UpdateRoundTripCounter(int64_t last_acked_packet) {
564 if (last_acked_packet > current_round_trip_end_) {
565 round_trip_count_++;
566 current_round_trip_end_ = last_sent_packet_;
567 return true;
568 }
569
570 return false;
571 }
572
UpdateBandwidthAndMinRtt(Timestamp now,const std::vector<PacketResult> & acked_packets)573 bool BbrNetworkController::UpdateBandwidthAndMinRtt(
574 Timestamp now,
575 const std::vector<PacketResult>& acked_packets) {
576 TimeDelta sample_rtt = TimeDelta::PlusInfinity();
577 for (const auto& packet : acked_packets) {
578 BandwidthSample bandwidth_sample =
579 sampler_->OnPacketAcknowledged(now, packet.sent_packet.sequence_number);
580 last_sample_is_app_limited_ = bandwidth_sample.is_app_limited;
581 if (!bandwidth_sample.rtt.IsZero()) {
582 sample_rtt = std::min(sample_rtt, bandwidth_sample.rtt);
583 }
584
585 if (!bandwidth_sample.is_app_limited ||
586 bandwidth_sample.bandwidth > BandwidthEstimate()) {
587 max_bandwidth_.Update(bandwidth_sample.bandwidth, round_trip_count_);
588 }
589 }
590
591 // If none of the RTT samples are valid, return immediately.
592 if (sample_rtt.IsInfinite()) {
593 return false;
594 }
595
596 last_rtt_ = sample_rtt;
597 min_rtt_since_last_probe_rtt_ =
598 std::min(min_rtt_since_last_probe_rtt_, sample_rtt);
599
600 const TimeDelta kMinRttExpiry = TimeDelta::Seconds(kMinRttExpirySeconds);
601 // Do not expire min_rtt if none was ever available.
602 bool min_rtt_expired =
603 !min_rtt_.IsZero() && (now > (min_rtt_timestamp_ + kMinRttExpiry));
604
605 if (min_rtt_expired || sample_rtt < min_rtt_ || min_rtt_.IsZero()) {
606 if (ShouldExtendMinRttExpiry()) {
607 min_rtt_expired = false;
608 } else {
609 min_rtt_ = sample_rtt;
610 }
611 min_rtt_timestamp_ = now;
612 // Reset since_last_probe_rtt fields.
613 min_rtt_since_last_probe_rtt_ = TimeDelta::PlusInfinity();
614 app_limited_since_last_probe_rtt_ = false;
615 }
616
617 return min_rtt_expired;
618 }
619
ShouldExtendMinRttExpiry() const620 bool BbrNetworkController::ShouldExtendMinRttExpiry() const {
621 if (config_.probe_rtt_disabled_if_app_limited &&
622 app_limited_since_last_probe_rtt_) {
623 // Extend the current min_rtt if we've been app limited recently.
624 return true;
625 }
626 const bool min_rtt_increased_since_last_probe =
627 min_rtt_since_last_probe_rtt_ > min_rtt_ * kSimilarMinRttThreshold;
628 if (config_.probe_rtt_skipped_if_similar_rtt &&
629 app_limited_since_last_probe_rtt_ &&
630 !min_rtt_increased_since_last_probe) {
631 // Extend the current min_rtt if we've been app limited recently and an rtt
632 // has been measured in that time that's less than 12.5% more than the
633 // current min_rtt.
634 return true;
635 }
636 return false;
637 }
638
UpdateGainCyclePhase(Timestamp now,DataSize prior_in_flight,bool has_losses)639 void BbrNetworkController::UpdateGainCyclePhase(Timestamp now,
640 DataSize prior_in_flight,
641 bool has_losses) {
642 // In most cases, the cycle is advanced after an RTT passes.
643 bool should_advance_gain_cycling = now - last_cycle_start_ > GetMinRtt();
644
645 // If the pacing gain is above 1.0, the connection is trying to probe the
646 // bandwidth by increasing the number of bytes in flight to at least
647 // pacing_gain * BDP. Make sure that it actually reaches the target, as long
648 // as there are no losses suggesting that the buffers are not able to hold
649 // that much.
650 if (pacing_gain_ > 1.0 && !has_losses &&
651 prior_in_flight < GetTargetCongestionWindow(pacing_gain_)) {
652 should_advance_gain_cycling = false;
653 }
654
655 // If pacing gain is below 1.0, the connection is trying to drain the extra
656 // queue which could have been incurred by probing prior to it. If the number
657 // of bytes in flight falls down to the estimated BDP value earlier, conclude
658 // that the queue has been successfully drained and exit this cycle early.
659 if (pacing_gain_ < 1.0 && prior_in_flight <= GetTargetCongestionWindow(1)) {
660 should_advance_gain_cycling = true;
661 }
662
663 if (should_advance_gain_cycling) {
664 cycle_current_offset_ = (cycle_current_offset_ + 1) % kGainCycleLength;
665 last_cycle_start_ = now;
666 // Stay in low gain mode until the target BDP is hit.
667 // Low gain mode will be exited immediately when the target BDP is achieved.
668 if (config_.fully_drain_queue && pacing_gain_ < 1 &&
669 GetPacingGain(cycle_current_offset_) == 1 &&
670 prior_in_flight > GetTargetCongestionWindow(1)) {
671 return;
672 }
673 pacing_gain_ = GetPacingGain(cycle_current_offset_);
674 }
675 }
676
CheckIfFullBandwidthReached()677 void BbrNetworkController::CheckIfFullBandwidthReached() {
678 if (last_sample_is_app_limited_) {
679 return;
680 }
681
682 DataRate target = bandwidth_at_last_round_ * kStartupGrowthTarget;
683 if (BandwidthEstimate() >= target) {
684 bandwidth_at_last_round_ = BandwidthEstimate();
685 rounds_without_bandwidth_gain_ = 0;
686 return;
687 }
688
689 rounds_without_bandwidth_gain_++;
690 if ((rounds_without_bandwidth_gain_ >= config_.num_startup_rtts) ||
691 (config_.exit_startup_on_loss && InRecovery())) {
692 is_at_full_bandwidth_ = true;
693 }
694 }
695
MaybeExitStartupOrDrain(const TransportPacketsFeedback & msg)696 void BbrNetworkController::MaybeExitStartupOrDrain(
697 const TransportPacketsFeedback& msg) {
698 TimeDelta exit_threshold = config_.exit_startup_rtt_threshold;
699 TimeDelta rtt_delta = last_rtt_ - min_rtt_;
700 if (mode_ == STARTUP &&
701 (is_at_full_bandwidth_ || rtt_delta > exit_threshold)) {
702 if (rtt_delta > exit_threshold)
703 RTC_LOG(LS_INFO) << "Exiting startup due to rtt increase from: "
704 << ToString(min_rtt_) << " to:" << ToString(last_rtt_)
705 << " > " << ToString(min_rtt_ + exit_threshold);
706 mode_ = DRAIN;
707 pacing_gain_ = kDrainGain;
708 congestion_window_gain_ = kHighGain;
709 }
710 if (mode_ == DRAIN && msg.data_in_flight <= GetTargetCongestionWindow(1)) {
711 EnterProbeBandwidthMode(msg.feedback_time);
712 }
713 }
714
MaybeEnterOrExitProbeRtt(const TransportPacketsFeedback & msg,bool is_round_start,bool min_rtt_expired)715 void BbrNetworkController::MaybeEnterOrExitProbeRtt(
716 const TransportPacketsFeedback& msg,
717 bool is_round_start,
718 bool min_rtt_expired) {
719 if (min_rtt_expired && !exiting_quiescence_ && mode_ != PROBE_RTT) {
720 mode_ = PROBE_RTT;
721 pacing_gain_ = 1;
722 // Do not decide on the time to exit PROBE_RTT until the |bytes_in_flight|
723 // is at the target small value.
724 exit_probe_rtt_at_.reset();
725 }
726
727 if (mode_ == PROBE_RTT) {
728 sampler_->OnAppLimited();
729
730 if (!exit_probe_rtt_at_) {
731 // If the window has reached the appropriate size, schedule exiting
732 // PROBE_RTT. The CWND during PROBE_RTT is kMinimumCongestionWindow, but
733 // we allow an extra packet since QUIC checks CWND before sending a
734 // packet.
735 if (msg.data_in_flight < ProbeRttCongestionWindow() + kMaxPacketSize) {
736 exit_probe_rtt_at_ =
737 msg.feedback_time + TimeDelta::Millis(kProbeRttTimeMs);
738 probe_rtt_round_passed_ = false;
739 }
740 } else {
741 if (is_round_start) {
742 probe_rtt_round_passed_ = true;
743 }
744 if (msg.feedback_time >= *exit_probe_rtt_at_ && probe_rtt_round_passed_) {
745 min_rtt_timestamp_ = msg.feedback_time;
746 if (!is_at_full_bandwidth_) {
747 EnterStartupMode();
748 } else {
749 EnterProbeBandwidthMode(msg.feedback_time);
750 }
751 }
752 }
753 }
754
755 exiting_quiescence_ = false;
756 }
757
UpdateRecoveryState(int64_t last_acked_packet,bool has_losses,bool is_round_start)758 void BbrNetworkController::UpdateRecoveryState(int64_t last_acked_packet,
759 bool has_losses,
760 bool is_round_start) {
761 // Exit recovery when there are no losses for a round.
762 if (has_losses) {
763 end_recovery_at_ = last_sent_packet_;
764 }
765
766 switch (recovery_state_) {
767 case NOT_IN_RECOVERY:
768 // Enter conservation on the first loss.
769 if (has_losses) {
770 recovery_state_ = CONSERVATION;
771 if (mode_ == STARTUP) {
772 recovery_state_ = config_.initial_conservation_in_startup;
773 }
774 // This will cause the |recovery_window_| to be set to the correct
775 // value in CalculateRecoveryWindow().
776 recovery_window_ = DataSize::Zero();
777 // Since the conservation phase is meant to be lasting for a whole
778 // round, extend the current round as if it were started right now.
779 current_round_trip_end_ = last_sent_packet_;
780 }
781 break;
782
783 case CONSERVATION:
784 case MEDIUM_GROWTH:
785 if (is_round_start) {
786 recovery_state_ = GROWTH;
787 }
788 ABSL_FALLTHROUGH_INTENDED;
789 case GROWTH:
790 // Exit recovery if appropriate.
791 if (!has_losses &&
792 (!end_recovery_at_ || last_acked_packet > *end_recovery_at_)) {
793 recovery_state_ = NOT_IN_RECOVERY;
794 }
795
796 break;
797 }
798 }
799
UpdateAckAggregationBytes(Timestamp ack_time,DataSize newly_acked_bytes)800 void BbrNetworkController::UpdateAckAggregationBytes(
801 Timestamp ack_time,
802 DataSize newly_acked_bytes) {
803 if (!aggregation_epoch_start_time_) {
804 RTC_LOG(LS_ERROR)
805 << "Received feedback before information about sent packets.";
806 RTC_DCHECK(aggregation_epoch_start_time_.has_value());
807 return;
808 }
809 // Compute how many bytes are expected to be delivered, assuming max bandwidth
810 // is correct.
811 DataSize expected_bytes_acked =
812 max_bandwidth_.GetBest() * (ack_time - *aggregation_epoch_start_time_);
813 // Reset the current aggregation epoch as soon as the ack arrival rate is less
814 // than or equal to the max bandwidth.
815 if (aggregation_epoch_bytes_ <= expected_bytes_acked) {
816 // Reset to start measuring a new aggregation epoch.
817 aggregation_epoch_bytes_ = newly_acked_bytes;
818 aggregation_epoch_start_time_ = ack_time;
819 return;
820 }
821
822 // Compute how many extra bytes were delivered vs max bandwidth.
823 // Include the bytes most recently acknowledged to account for stretch acks.
824 aggregation_epoch_bytes_ += newly_acked_bytes;
825 max_ack_height_.Update(aggregation_epoch_bytes_ - expected_bytes_acked,
826 round_trip_count_);
827 }
828
CalculatePacingRate()829 void BbrNetworkController::CalculatePacingRate() {
830 if (BandwidthEstimate().IsZero()) {
831 return;
832 }
833
834 DataRate target_rate = pacing_gain_ * BandwidthEstimate();
835 if (config_.rate_based_recovery && InRecovery()) {
836 pacing_rate_ = pacing_gain_ * max_bandwidth_.GetThirdBest();
837 }
838 if (is_at_full_bandwidth_) {
839 pacing_rate_ = target_rate;
840 return;
841 }
842
843 // Pace at the rate of initial_window / RTT as soon as RTT measurements are
844 // available.
845 if (pacing_rate_.IsZero() && !rtt_stats_.min_rtt().IsZero()) {
846 pacing_rate_ = initial_congestion_window_ / rtt_stats_.min_rtt();
847 return;
848 }
849 // Slow the pacing rate in STARTUP once loss has ever been detected.
850 const bool has_ever_detected_loss = end_recovery_at_.has_value();
851 if (config_.slower_startup && has_ever_detected_loss) {
852 pacing_rate_ = kStartupAfterLossGain * BandwidthEstimate();
853 return;
854 }
855
856 // Do not decrease the pacing rate during the startup.
857 pacing_rate_ = std::max(pacing_rate_, target_rate);
858 }
859
CalculateCongestionWindow(DataSize bytes_acked)860 void BbrNetworkController::CalculateCongestionWindow(DataSize bytes_acked) {
861 if (mode_ == PROBE_RTT) {
862 return;
863 }
864
865 DataSize target_window = GetTargetCongestionWindow(congestion_window_gain_);
866
867 if (rtt_variance_weight_ > 0.f && !BandwidthEstimate().IsZero()) {
868 target_window += rtt_variance_weight_ * rtt_stats_.mean_deviation() *
869 BandwidthEstimate();
870 } else if (max_aggregation_bytes_multiplier_ > 0 && is_at_full_bandwidth_) {
871 // Subtracting only half the bytes_acked_since_queue_drained ensures sending
872 // doesn't completely stop for a long period of time if the queue hasn't
873 // been drained recently.
874 if (max_aggregation_bytes_multiplier_ * max_ack_height_.GetBest() >
875 bytes_acked_since_queue_drained_ / 2) {
876 target_window +=
877 max_aggregation_bytes_multiplier_ * max_ack_height_.GetBest() -
878 bytes_acked_since_queue_drained_ / 2;
879 }
880 } else if (is_at_full_bandwidth_) {
881 target_window += max_ack_height_.GetBest();
882 }
883
884 // Instead of immediately setting the target CWND as the new one, BBR grows
885 // the CWND towards |target_window| by only increasing it |bytes_acked| at a
886 // time.
887 if (is_at_full_bandwidth_) {
888 congestion_window_ =
889 std::min(target_window, congestion_window_ + bytes_acked);
890 } else if (congestion_window_ < target_window ||
891 sampler_->total_data_acked() < initial_congestion_window_) {
892 // If the connection is not yet out of startup phase, do not decrease the
893 // window.
894 congestion_window_ = congestion_window_ + bytes_acked;
895 }
896
897 // Enforce the limits on the congestion window.
898 congestion_window_ = std::max(congestion_window_, min_congestion_window_);
899 congestion_window_ = std::min(congestion_window_, max_congestion_window_);
900 }
901
CalculateRecoveryWindow(DataSize bytes_acked,DataSize bytes_lost,DataSize bytes_in_flight)902 void BbrNetworkController::CalculateRecoveryWindow(DataSize bytes_acked,
903 DataSize bytes_lost,
904 DataSize bytes_in_flight) {
905 if (config_.rate_based_recovery ||
906 (config_.rate_based_startup && mode_ == STARTUP)) {
907 return;
908 }
909
910 if (recovery_state_ == NOT_IN_RECOVERY) {
911 return;
912 }
913
914 // Set up the initial recovery window.
915 if (recovery_window_.IsZero()) {
916 recovery_window_ = bytes_in_flight + bytes_acked;
917 recovery_window_ = std::max(min_congestion_window_, recovery_window_);
918 return;
919 }
920
921 // Remove losses from the recovery window, while accounting for a potential
922 // integer underflow.
923 recovery_window_ = recovery_window_ >= bytes_lost
924 ? recovery_window_ - bytes_lost
925 : kMaxSegmentSize;
926
927 // In CONSERVATION mode, just subtracting losses is sufficient. In GROWTH,
928 // release additional |bytes_acked| to achieve a slow-start-like behavior.
929 // In MEDIUM_GROWTH, release |bytes_acked| / 2 to split the difference.
930 if (recovery_state_ == GROWTH) {
931 recovery_window_ += bytes_acked;
932 } else if (recovery_state_ == MEDIUM_GROWTH) {
933 recovery_window_ += bytes_acked / 2;
934 }
935
936 // Sanity checks. Ensure that we always allow to send at least
937 // |bytes_acked| in response.
938 recovery_window_ = std::max(recovery_window_, bytes_in_flight + bytes_acked);
939 recovery_window_ = std::max(min_congestion_window_, recovery_window_);
940 }
941
OnApplicationLimited(DataSize bytes_in_flight)942 void BbrNetworkController::OnApplicationLimited(DataSize bytes_in_flight) {
943 if (bytes_in_flight >= GetCongestionWindow()) {
944 return;
945 }
946
947 app_limited_since_last_probe_rtt_ = true;
948 sampler_->OnAppLimited();
949
950 RTC_LOG(LS_INFO) << "Becoming application limited. Last sent packet: "
951 << last_sent_packet_
952 << ", CWND: " << ToString(GetCongestionWindow());
953 }
954 } // namespace bbr
955 } // namespace webrtc
956