1 // Copyright 2016 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "net/third_party/quiche/src/quic/core/congestion_control/bbr_sender.h"
6
7 #include <algorithm>
8 #include <sstream>
9 #include <string>
10
11 #include "absl/base/attributes.h"
12 #include "net/third_party/quiche/src/quic/core/congestion_control/rtt_stats.h"
13 #include "net/third_party/quiche/src/quic/core/crypto/crypto_protocol.h"
14 #include "net/third_party/quiche/src/quic/core/quic_time.h"
15 #include "net/third_party/quiche/src/quic/core/quic_time_accumulator.h"
16 #include "net/third_party/quiche/src/quic/platform/api/quic_bug_tracker.h"
17 #include "net/third_party/quiche/src/quic/platform/api/quic_flag_utils.h"
18 #include "net/third_party/quiche/src/quic/platform/api/quic_flags.h"
19 #include "net/third_party/quiche/src/quic/platform/api/quic_logging.h"
20
21 namespace quic {
22
23 namespace {
24 // Constants based on TCP defaults.
25 // The minimum CWND to ensure delayed acks don't reduce bandwidth measurements.
26 // Does not inflate the pacing rate.
27 const QuicByteCount kDefaultMinimumCongestionWindow = 4 * kMaxSegmentSize;
28
29 // The gain used for the STARTUP, equal to 2/ln(2).
30 const float kDefaultHighGain = 2.885f;
31 // The newly derived gain for STARTUP, equal to 4 * ln(2)
32 const float kDerivedHighGain = 2.773f;
33 // The newly derived CWND gain for STARTUP, 2.
34 const float kDerivedHighCWNDGain = 2.0f;
35 // The cycle of gains used during the PROBE_BW stage.
36 const float kPacingGain[] = {1.25, 0.75, 1, 1, 1, 1, 1, 1};
37
38 // The length of the gain cycle.
39 const size_t kGainCycleLength = sizeof(kPacingGain) / sizeof(kPacingGain[0]);
40 // The size of the bandwidth filter window, in round-trips.
41 const QuicRoundTripCount kBandwidthWindowSize = kGainCycleLength + 2;
42
43 // The time after which the current min_rtt value expires.
44 const QuicTime::Delta kMinRttExpiry = QuicTime::Delta::FromSeconds(10);
45 // The minimum time the connection can spend in PROBE_RTT mode.
46 const QuicTime::Delta kProbeRttTime = QuicTime::Delta::FromMilliseconds(200);
47 // If the bandwidth does not increase by the factor of |kStartupGrowthTarget|
48 // within |kRoundTripsWithoutGrowthBeforeExitingStartup| rounds, the connection
49 // will exit the STARTUP mode.
50 const float kStartupGrowthTarget = 1.25;
51 const QuicRoundTripCount kRoundTripsWithoutGrowthBeforeExitingStartup = 3;
52 } // namespace
53
DebugState(const BbrSender & sender)54 BbrSender::DebugState::DebugState(const BbrSender& sender)
55 : mode(sender.mode_),
56 max_bandwidth(sender.max_bandwidth_.GetBest()),
57 round_trip_count(sender.round_trip_count_),
58 gain_cycle_index(sender.cycle_current_offset_),
59 congestion_window(sender.congestion_window_),
60 is_at_full_bandwidth(sender.is_at_full_bandwidth_),
61 bandwidth_at_last_round(sender.bandwidth_at_last_round_),
62 rounds_without_bandwidth_gain(sender.rounds_without_bandwidth_gain_),
63 min_rtt(sender.min_rtt_),
64 min_rtt_timestamp(sender.min_rtt_timestamp_),
65 recovery_state(sender.recovery_state_),
66 recovery_window(sender.recovery_window_),
67 last_sample_is_app_limited(sender.last_sample_is_app_limited_),
68 end_of_app_limited_phase(sender.sampler_.end_of_app_limited_phase()) {}
69
70 BbrSender::DebugState::DebugState(const DebugState& state) = default;
71
BbrSender(QuicTime now,const RttStats * rtt_stats,const QuicUnackedPacketMap * unacked_packets,QuicPacketCount initial_tcp_congestion_window,QuicPacketCount max_tcp_congestion_window,QuicRandom * random,QuicConnectionStats * stats)72 BbrSender::BbrSender(QuicTime now,
73 const RttStats* rtt_stats,
74 const QuicUnackedPacketMap* unacked_packets,
75 QuicPacketCount initial_tcp_congestion_window,
76 QuicPacketCount max_tcp_congestion_window,
77 QuicRandom* random,
78 QuicConnectionStats* stats)
79 : rtt_stats_(rtt_stats),
80 unacked_packets_(unacked_packets),
81 random_(random),
82 stats_(stats),
83 mode_(STARTUP),
84 sampler_(unacked_packets, kBandwidthWindowSize),
85 round_trip_count_(0),
86 num_loss_events_in_round_(0),
87 bytes_lost_in_round_(0),
88 max_bandwidth_(kBandwidthWindowSize, QuicBandwidth::Zero(), 0),
89 min_rtt_(QuicTime::Delta::Zero()),
90 min_rtt_timestamp_(QuicTime::Zero()),
91 congestion_window_(initial_tcp_congestion_window * kDefaultTCPMSS),
92 initial_congestion_window_(initial_tcp_congestion_window *
93 kDefaultTCPMSS),
94 max_congestion_window_(max_tcp_congestion_window * kDefaultTCPMSS),
95 min_congestion_window_(kDefaultMinimumCongestionWindow),
96 high_gain_(kDefaultHighGain),
97 high_cwnd_gain_(kDefaultHighGain),
98 drain_gain_(1.f / kDefaultHighGain),
99 pacing_rate_(QuicBandwidth::Zero()),
100 pacing_gain_(1),
101 congestion_window_gain_(1),
102 congestion_window_gain_constant_(
103 static_cast<float>(GetQuicFlag(FLAGS_quic_bbr_cwnd_gain))),
104 num_startup_rtts_(kRoundTripsWithoutGrowthBeforeExitingStartup),
105 cycle_current_offset_(0),
106 last_cycle_start_(QuicTime::Zero()),
107 is_at_full_bandwidth_(false),
108 rounds_without_bandwidth_gain_(0),
109 bandwidth_at_last_round_(QuicBandwidth::Zero()),
110 exiting_quiescence_(false),
111 exit_probe_rtt_at_(QuicTime::Zero()),
112 probe_rtt_round_passed_(false),
113 last_sample_is_app_limited_(false),
114 has_non_app_limited_sample_(false),
115 recovery_state_(NOT_IN_RECOVERY),
116 recovery_window_(max_congestion_window_),
117 slower_startup_(false),
118 rate_based_startup_(false),
119 enable_ack_aggregation_during_startup_(false),
120 expire_ack_aggregation_in_startup_(false),
121 drain_to_target_(false),
122 detect_overshooting_(false),
123 bytes_lost_while_detecting_overshooting_(0),
124 bytes_lost_multiplier_while_detecting_overshooting_(2),
125 cwnd_to_calculate_min_pacing_rate_(initial_congestion_window_),
126 max_congestion_window_with_network_parameters_adjusted_(
127 kMaxInitialCongestionWindow * kDefaultTCPMSS) {
128 if (stats_) {
129 // Clear some startup stats if |stats_| has been used by another sender,
130 // which happens e.g. when QuicConnection switch send algorithms.
131 stats_->slowstart_count = 0;
132 stats_->slowstart_duration = QuicTimeAccumulator();
133 }
134 EnterStartupMode(now);
135 set_high_cwnd_gain(kDerivedHighCWNDGain);
136 }
137
~BbrSender()138 BbrSender::~BbrSender() {}
139
SetInitialCongestionWindowInPackets(QuicPacketCount congestion_window)140 void BbrSender::SetInitialCongestionWindowInPackets(
141 QuicPacketCount congestion_window) {
142 if (mode_ == STARTUP) {
143 initial_congestion_window_ = congestion_window * kDefaultTCPMSS;
144 congestion_window_ = congestion_window * kDefaultTCPMSS;
145 cwnd_to_calculate_min_pacing_rate_ = std::min(
146 initial_congestion_window_, cwnd_to_calculate_min_pacing_rate_);
147 }
148 }
149
InSlowStart() const150 bool BbrSender::InSlowStart() const {
151 return mode_ == STARTUP;
152 }
153
OnPacketSent(QuicTime sent_time,QuicByteCount bytes_in_flight,QuicPacketNumber packet_number,QuicByteCount bytes,HasRetransmittableData is_retransmittable)154 void BbrSender::OnPacketSent(QuicTime sent_time,
155 QuicByteCount bytes_in_flight,
156 QuicPacketNumber packet_number,
157 QuicByteCount bytes,
158 HasRetransmittableData is_retransmittable) {
159 if (stats_ && InSlowStart()) {
160 ++stats_->slowstart_packets_sent;
161 stats_->slowstart_bytes_sent += bytes;
162 }
163
164 last_sent_packet_ = packet_number;
165
166 if (bytes_in_flight == 0 && sampler_.is_app_limited()) {
167 exiting_quiescence_ = true;
168 }
169
170 sampler_.OnPacketSent(sent_time, packet_number, bytes, bytes_in_flight,
171 is_retransmittable);
172 }
173
OnPacketNeutered(QuicPacketNumber packet_number)174 void BbrSender::OnPacketNeutered(QuicPacketNumber packet_number) {
175 sampler_.OnPacketNeutered(packet_number);
176 }
177
CanSend(QuicByteCount bytes_in_flight)178 bool BbrSender::CanSend(QuicByteCount bytes_in_flight) {
179 return bytes_in_flight < GetCongestionWindow();
180 }
181
PacingRate(QuicByteCount) const182 QuicBandwidth BbrSender::PacingRate(QuicByteCount /*bytes_in_flight*/) const {
183 if (pacing_rate_.IsZero()) {
184 return high_gain_ * QuicBandwidth::FromBytesAndTimeDelta(
185 initial_congestion_window_, GetMinRtt());
186 }
187 return pacing_rate_;
188 }
189
BandwidthEstimate() const190 QuicBandwidth BbrSender::BandwidthEstimate() const {
191 return max_bandwidth_.GetBest();
192 }
193
GetCongestionWindow() const194 QuicByteCount BbrSender::GetCongestionWindow() const {
195 if (mode_ == PROBE_RTT) {
196 return ProbeRttCongestionWindow();
197 }
198
199 if (InRecovery()) {
200 return std::min(congestion_window_, recovery_window_);
201 }
202
203 return congestion_window_;
204 }
205
GetSlowStartThreshold() const206 QuicByteCount BbrSender::GetSlowStartThreshold() const {
207 return 0;
208 }
209
InRecovery() const210 bool BbrSender::InRecovery() const {
211 return recovery_state_ != NOT_IN_RECOVERY;
212 }
213
ShouldSendProbingPacket() const214 bool BbrSender::ShouldSendProbingPacket() const {
215 if (pacing_gain_ <= 1) {
216 return false;
217 }
218
219 // TODO(b/77975811): If the pipe is highly under-utilized, consider not
220 // sending a probing transmission, because the extra bandwidth is not needed.
221 return true;
222 }
223
SetFromConfig(const QuicConfig & config,Perspective perspective)224 void BbrSender::SetFromConfig(const QuicConfig& config,
225 Perspective perspective) {
226 if (config.HasClientRequestedIndependentOption(k1RTT, perspective)) {
227 num_startup_rtts_ = 1;
228 }
229 if (config.HasClientRequestedIndependentOption(k2RTT, perspective)) {
230 num_startup_rtts_ = 2;
231 }
232 if (config.HasClientRequestedIndependentOption(kBBR3, perspective)) {
233 drain_to_target_ = true;
234 }
235 if (config.HasClientRequestedIndependentOption(kBWM3, perspective)) {
236 bytes_lost_multiplier_while_detecting_overshooting_ = 3;
237 }
238 if (config.HasClientRequestedIndependentOption(kBWM4, perspective)) {
239 bytes_lost_multiplier_while_detecting_overshooting_ = 4;
240 }
241 if (config.HasClientRequestedIndependentOption(kBBR4, perspective)) {
242 sampler_.SetMaxAckHeightTrackerWindowLength(2 * kBandwidthWindowSize);
243 }
244 if (config.HasClientRequestedIndependentOption(kBBR5, perspective)) {
245 sampler_.SetMaxAckHeightTrackerWindowLength(4 * kBandwidthWindowSize);
246 }
247 if (config.HasClientRequestedIndependentOption(kBBQ1, perspective)) {
248 set_high_gain(kDerivedHighGain);
249 set_high_cwnd_gain(kDerivedHighGain);
250 set_drain_gain(1.f / kDerivedHighGain);
251 }
252 if (config.HasClientRequestedIndependentOption(kBBQ3, perspective)) {
253 enable_ack_aggregation_during_startup_ = true;
254 }
255 if (config.HasClientRequestedIndependentOption(kBBQ5, perspective)) {
256 expire_ack_aggregation_in_startup_ = true;
257 }
258 if (config.HasClientRequestedIndependentOption(kMIN1, perspective)) {
259 min_congestion_window_ = kMaxSegmentSize;
260 }
261 if (config.HasClientRequestedIndependentOption(kICW1, perspective)) {
262 max_congestion_window_with_network_parameters_adjusted_ =
263 100 * kDefaultTCPMSS;
264 }
265 if (config.HasClientRequestedIndependentOption(kDTOS, perspective)) {
266 detect_overshooting_ = true;
267 // DTOS would allow pacing rate drop to IW 10 / min_rtt if overshooting is
268 // detected.
269 cwnd_to_calculate_min_pacing_rate_ =
270 std::min(initial_congestion_window_, 10 * kDefaultTCPMSS);
271 }
272
273 ApplyConnectionOptions(config.ClientRequestedIndependentOptions(perspective));
274 }
275
ApplyConnectionOptions(const QuicTagVector & connection_options)276 void BbrSender::ApplyConnectionOptions(
277 const QuicTagVector& connection_options) {
278 if (ContainsQuicTag(connection_options, kBSAO)) {
279 sampler_.EnableOverestimateAvoidance();
280 }
281 }
282
AdjustNetworkParameters(const NetworkParams & params)283 void BbrSender::AdjustNetworkParameters(const NetworkParams& params) {
284 const QuicBandwidth& bandwidth = params.bandwidth;
285 const QuicTime::Delta& rtt = params.rtt;
286
287 if (!params.quic_bbr_donot_inject_bandwidth && !bandwidth.IsZero()) {
288 max_bandwidth_.Update(bandwidth, round_trip_count_);
289 }
290 if (!rtt.IsZero() && (min_rtt_ > rtt || min_rtt_.IsZero())) {
291 min_rtt_ = rtt;
292 }
293
294 if (params.quic_fix_bbr_cwnd_in_bandwidth_resumption && mode_ == STARTUP) {
295 if (bandwidth.IsZero()) {
296 // Ignore bad bandwidth samples.
297 return;
298 }
299
300 auto cwnd_bootstrapping_rtt = params.quic_bbr_donot_inject_bandwidth
301 ? GetMinRtt()
302 : rtt_stats_->SmoothedOrInitialRtt();
303 if (params.max_initial_congestion_window > 0) {
304 max_congestion_window_with_network_parameters_adjusted_ =
305 params.max_initial_congestion_window * kDefaultTCPMSS;
306 }
307 const QuicByteCount new_cwnd = std::max(
308 kMinInitialCongestionWindow * kDefaultTCPMSS,
309 std::min(max_congestion_window_with_network_parameters_adjusted_,
310 bandwidth * cwnd_bootstrapping_rtt));
311
312 stats_->cwnd_bootstrapping_rtt_us = cwnd_bootstrapping_rtt.ToMicroseconds();
313 if (!rtt_stats_->smoothed_rtt().IsZero()) {
314 QUIC_CODE_COUNT(quic_smoothed_rtt_available);
315 } else if (rtt_stats_->initial_rtt() !=
316 QuicTime::Delta::FromMilliseconds(kInitialRttMs)) {
317 QUIC_CODE_COUNT(quic_client_initial_rtt_available);
318 } else {
319 QUIC_CODE_COUNT(quic_default_initial_rtt);
320 }
321 if (new_cwnd < congestion_window_ && !params.allow_cwnd_to_decrease) {
322 // Only decrease cwnd if allow_cwnd_to_decrease is true.
323 return;
324 }
325 if (GetQuicReloadableFlag(quic_conservative_cwnd_and_pacing_gains)) {
326 // Decreases cwnd gain and pacing gain. Please note, if pacing_rate_ has
327 // been calculated, it cannot decrease in STARTUP phase.
328 QUIC_RELOADABLE_FLAG_COUNT(quic_conservative_cwnd_and_pacing_gains);
329 set_high_gain(kDerivedHighCWNDGain);
330 set_high_cwnd_gain(kDerivedHighCWNDGain);
331 }
332 congestion_window_ = new_cwnd;
333 if (params.quic_bbr_fix_pacing_rate) {
334 // Pace at the rate of new_cwnd / RTT.
335 QuicBandwidth new_pacing_rate =
336 QuicBandwidth::FromBytesAndTimeDelta(congestion_window_, GetMinRtt());
337 pacing_rate_ = std::max(pacing_rate_, new_pacing_rate);
338 detect_overshooting_ = true;
339 }
340 }
341 }
342
OnCongestionEvent(bool,QuicByteCount prior_in_flight,QuicTime event_time,const AckedPacketVector & acked_packets,const LostPacketVector & lost_packets)343 void BbrSender::OnCongestionEvent(bool /*rtt_updated*/,
344 QuicByteCount prior_in_flight,
345 QuicTime event_time,
346 const AckedPacketVector& acked_packets,
347 const LostPacketVector& lost_packets) {
348 const QuicByteCount total_bytes_acked_before = sampler_.total_bytes_acked();
349 const QuicByteCount total_bytes_lost_before = sampler_.total_bytes_lost();
350
351 bool is_round_start = false;
352 bool min_rtt_expired = false;
353 QuicByteCount excess_acked = 0;
354 QuicByteCount bytes_lost = 0;
355
356 // The send state of the largest packet in acked_packets, unless it is
357 // empty. If acked_packets is empty, it's the send state of the largest
358 // packet in lost_packets.
359 SendTimeState last_packet_send_state;
360
361 if (!acked_packets.empty()) {
362 QuicPacketNumber last_acked_packet = acked_packets.rbegin()->packet_number;
363 is_round_start = UpdateRoundTripCounter(last_acked_packet);
364 UpdateRecoveryState(last_acked_packet, !lost_packets.empty(),
365 is_round_start);
366 }
367
368 BandwidthSamplerInterface::CongestionEventSample sample =
369 sampler_.OnCongestionEvent(event_time, acked_packets, lost_packets,
370 max_bandwidth_.GetBest(),
371 QuicBandwidth::Infinite(), round_trip_count_);
372 if (sample.last_packet_send_state.is_valid) {
373 last_sample_is_app_limited_ = sample.last_packet_send_state.is_app_limited;
374 has_non_app_limited_sample_ |= !last_sample_is_app_limited_;
375 if (stats_) {
376 stats_->has_non_app_limited_sample = has_non_app_limited_sample_;
377 }
378 }
379 // Avoid updating |max_bandwidth_| if a) this is a loss-only event, or b) all
380 // packets in |acked_packets| did not generate valid samples. (e.g. ack of
381 // ack-only packets). In both cases, sampler_.total_bytes_acked() will not
382 // change.
383 if (total_bytes_acked_before != sampler_.total_bytes_acked()) {
384 QUIC_LOG_IF(WARNING, sample.sample_max_bandwidth.IsZero())
385 << sampler_.total_bytes_acked() - total_bytes_acked_before
386 << " bytes from " << acked_packets.size()
387 << " packets have been acked, but sample_max_bandwidth is zero.";
388 if (!sample.sample_is_app_limited ||
389 sample.sample_max_bandwidth > max_bandwidth_.GetBest()) {
390 max_bandwidth_.Update(sample.sample_max_bandwidth, round_trip_count_);
391 }
392 }
393
394 if (!sample.sample_rtt.IsInfinite()) {
395 min_rtt_expired = MaybeUpdateMinRtt(event_time, sample.sample_rtt);
396 }
397 bytes_lost = sampler_.total_bytes_lost() - total_bytes_lost_before;
398 if (mode_ == STARTUP) {
399 if (stats_) {
400 stats_->slowstart_packets_lost += lost_packets.size();
401 stats_->slowstart_bytes_lost += bytes_lost;
402 }
403 }
404 excess_acked = sample.extra_acked;
405 last_packet_send_state = sample.last_packet_send_state;
406
407 if (!lost_packets.empty()) {
408 ++num_loss_events_in_round_;
409 bytes_lost_in_round_ += bytes_lost;
410 }
411
412 // Handle logic specific to PROBE_BW mode.
413 if (mode_ == PROBE_BW) {
414 UpdateGainCyclePhase(event_time, prior_in_flight, !lost_packets.empty());
415 }
416
417 // Handle logic specific to STARTUP and DRAIN modes.
418 if (is_round_start && !is_at_full_bandwidth_) {
419 CheckIfFullBandwidthReached(last_packet_send_state);
420 }
421 MaybeExitStartupOrDrain(event_time);
422
423 // Handle logic specific to PROBE_RTT.
424 MaybeEnterOrExitProbeRtt(event_time, is_round_start, min_rtt_expired);
425
426 // Calculate number of packets acked and lost.
427 QuicByteCount bytes_acked =
428 sampler_.total_bytes_acked() - total_bytes_acked_before;
429
430 // After the model is updated, recalculate the pacing rate and congestion
431 // window.
432 CalculatePacingRate(bytes_lost);
433 CalculateCongestionWindow(bytes_acked, excess_acked);
434 CalculateRecoveryWindow(bytes_acked, bytes_lost);
435
436 // Cleanup internal state.
437 sampler_.RemoveObsoletePackets(unacked_packets_->GetLeastUnacked());
438 if (is_round_start) {
439 num_loss_events_in_round_ = 0;
440 bytes_lost_in_round_ = 0;
441 }
442 }
443
GetCongestionControlType() const444 CongestionControlType BbrSender::GetCongestionControlType() const {
445 return kBBR;
446 }
447
GetMinRtt() const448 QuicTime::Delta BbrSender::GetMinRtt() const {
449 if (!min_rtt_.IsZero()) {
450 return min_rtt_;
451 }
452 // min_rtt could be available if the handshake packet gets neutered then
453 // gets acknowledged. This could only happen for QUIC crypto where we do not
454 // drop keys.
455 return rtt_stats_->MinOrInitialRtt();
456 }
457
GetTargetCongestionWindow(float gain) const458 QuicByteCount BbrSender::GetTargetCongestionWindow(float gain) const {
459 QuicByteCount bdp = GetMinRtt() * BandwidthEstimate();
460 QuicByteCount congestion_window = gain * bdp;
461
462 // BDP estimate will be zero if no bandwidth samples are available yet.
463 if (congestion_window == 0) {
464 congestion_window = gain * initial_congestion_window_;
465 }
466
467 return std::max(congestion_window, min_congestion_window_);
468 }
469
ProbeRttCongestionWindow() const470 QuicByteCount BbrSender::ProbeRttCongestionWindow() const {
471 return min_congestion_window_;
472 }
473
EnterStartupMode(QuicTime now)474 void BbrSender::EnterStartupMode(QuicTime now) {
475 if (stats_) {
476 ++stats_->slowstart_count;
477 stats_->slowstart_duration.Start(now);
478 }
479 mode_ = STARTUP;
480 pacing_gain_ = high_gain_;
481 congestion_window_gain_ = high_cwnd_gain_;
482 }
483
EnterProbeBandwidthMode(QuicTime now)484 void BbrSender::EnterProbeBandwidthMode(QuicTime now) {
485 mode_ = PROBE_BW;
486 congestion_window_gain_ = congestion_window_gain_constant_;
487
488 // Pick a random offset for the gain cycle out of {0, 2..7} range. 1 is
489 // excluded because in that case increased gain and decreased gain would not
490 // follow each other.
491 cycle_current_offset_ = random_->RandUint64() % (kGainCycleLength - 1);
492 if (cycle_current_offset_ >= 1) {
493 cycle_current_offset_ += 1;
494 }
495
496 last_cycle_start_ = now;
497 pacing_gain_ = kPacingGain[cycle_current_offset_];
498 }
499
UpdateRoundTripCounter(QuicPacketNumber last_acked_packet)500 bool BbrSender::UpdateRoundTripCounter(QuicPacketNumber last_acked_packet) {
501 if (!current_round_trip_end_.IsInitialized() ||
502 last_acked_packet > current_round_trip_end_) {
503 round_trip_count_++;
504 current_round_trip_end_ = last_sent_packet_;
505 if (stats_ && InSlowStart()) {
506 ++stats_->slowstart_num_rtts;
507 }
508 return true;
509 }
510
511 return false;
512 }
513
MaybeUpdateMinRtt(QuicTime now,QuicTime::Delta sample_min_rtt)514 bool BbrSender::MaybeUpdateMinRtt(QuicTime now,
515 QuicTime::Delta sample_min_rtt) {
516 // Do not expire min_rtt if none was ever available.
517 bool min_rtt_expired =
518 !min_rtt_.IsZero() && (now > (min_rtt_timestamp_ + kMinRttExpiry));
519
520 if (min_rtt_expired || sample_min_rtt < min_rtt_ || min_rtt_.IsZero()) {
521 QUIC_DVLOG(2) << "Min RTT updated, old value: " << min_rtt_
522 << ", new value: " << sample_min_rtt
523 << ", current time: " << now.ToDebuggingValue();
524
525 min_rtt_ = sample_min_rtt;
526 min_rtt_timestamp_ = now;
527 }
528 DCHECK(!min_rtt_.IsZero());
529
530 return min_rtt_expired;
531 }
532
UpdateGainCyclePhase(QuicTime now,QuicByteCount prior_in_flight,bool has_losses)533 void BbrSender::UpdateGainCyclePhase(QuicTime now,
534 QuicByteCount prior_in_flight,
535 bool has_losses) {
536 const QuicByteCount bytes_in_flight = unacked_packets_->bytes_in_flight();
537 // In most cases, the cycle is advanced after an RTT passes.
538 bool should_advance_gain_cycling = now - last_cycle_start_ > GetMinRtt();
539
540 // If the pacing gain is above 1.0, the connection is trying to probe the
541 // bandwidth by increasing the number of bytes in flight to at least
542 // pacing_gain * BDP. Make sure that it actually reaches the target, as long
543 // as there are no losses suggesting that the buffers are not able to hold
544 // that much.
545 if (pacing_gain_ > 1.0 && !has_losses &&
546 prior_in_flight < GetTargetCongestionWindow(pacing_gain_)) {
547 should_advance_gain_cycling = false;
548 }
549
550 // If pacing gain is below 1.0, the connection is trying to drain the extra
551 // queue which could have been incurred by probing prior to it. If the number
552 // of bytes in flight falls down to the estimated BDP value earlier, conclude
553 // that the queue has been successfully drained and exit this cycle early.
554 if (pacing_gain_ < 1.0 && bytes_in_flight <= GetTargetCongestionWindow(1)) {
555 should_advance_gain_cycling = true;
556 }
557
558 if (should_advance_gain_cycling) {
559 cycle_current_offset_ = (cycle_current_offset_ + 1) % kGainCycleLength;
560 if (cycle_current_offset_ == 0) {
561 ++stats_->bbr_num_cycles;
562 }
563 last_cycle_start_ = now;
564 // Stay in low gain mode until the target BDP is hit.
565 // Low gain mode will be exited immediately when the target BDP is achieved.
566 if (drain_to_target_ && pacing_gain_ < 1 &&
567 kPacingGain[cycle_current_offset_] == 1 &&
568 bytes_in_flight > GetTargetCongestionWindow(1)) {
569 return;
570 }
571 pacing_gain_ = kPacingGain[cycle_current_offset_];
572 }
573 }
574
CheckIfFullBandwidthReached(const SendTimeState & last_packet_send_state)575 void BbrSender::CheckIfFullBandwidthReached(
576 const SendTimeState& last_packet_send_state) {
577 if (last_sample_is_app_limited_) {
578 return;
579 }
580
581 QuicBandwidth target = bandwidth_at_last_round_ * kStartupGrowthTarget;
582 if (BandwidthEstimate() >= target) {
583 bandwidth_at_last_round_ = BandwidthEstimate();
584 rounds_without_bandwidth_gain_ = 0;
585 if (expire_ack_aggregation_in_startup_) {
586 // Expire old excess delivery measurements now that bandwidth increased.
587 sampler_.ResetMaxAckHeightTracker(0, round_trip_count_);
588 }
589 return;
590 }
591
592 rounds_without_bandwidth_gain_++;
593 if ((rounds_without_bandwidth_gain_ >= num_startup_rtts_) ||
594 ShouldExitStartupDueToLoss(last_packet_send_state)) {
595 DCHECK(has_non_app_limited_sample_);
596 is_at_full_bandwidth_ = true;
597 }
598 }
599
MaybeExitStartupOrDrain(QuicTime now)600 void BbrSender::MaybeExitStartupOrDrain(QuicTime now) {
601 if (mode_ == STARTUP && is_at_full_bandwidth_) {
602 OnExitStartup(now);
603 mode_ = DRAIN;
604 pacing_gain_ = drain_gain_;
605 congestion_window_gain_ = high_cwnd_gain_;
606 }
607 if (mode_ == DRAIN &&
608 unacked_packets_->bytes_in_flight() <= GetTargetCongestionWindow(1)) {
609 EnterProbeBandwidthMode(now);
610 }
611 }
612
OnExitStartup(QuicTime now)613 void BbrSender::OnExitStartup(QuicTime now) {
614 DCHECK_EQ(mode_, STARTUP);
615 if (stats_) {
616 stats_->slowstart_duration.Stop(now);
617 }
618 }
619
ShouldExitStartupDueToLoss(const SendTimeState & last_packet_send_state) const620 bool BbrSender::ShouldExitStartupDueToLoss(
621 const SendTimeState& last_packet_send_state) const {
622 if (num_loss_events_in_round_ <
623 GetQuicFlag(FLAGS_quic_bbr2_default_startup_full_loss_count) ||
624 !last_packet_send_state.is_valid) {
625 return false;
626 }
627
628 const QuicByteCount inflight_at_send = last_packet_send_state.bytes_in_flight;
629
630 if (inflight_at_send > 0 && bytes_lost_in_round_ > 0) {
631 if (bytes_lost_in_round_ >
632 inflight_at_send *
633 GetQuicFlag(FLAGS_quic_bbr2_default_loss_threshold)) {
634 stats_->bbr_exit_startup_due_to_loss = true;
635 return true;
636 }
637 return false;
638 }
639
640 return false;
641 }
642
MaybeEnterOrExitProbeRtt(QuicTime now,bool is_round_start,bool min_rtt_expired)643 void BbrSender::MaybeEnterOrExitProbeRtt(QuicTime now,
644 bool is_round_start,
645 bool min_rtt_expired) {
646 if (min_rtt_expired && !exiting_quiescence_ && mode_ != PROBE_RTT) {
647 if (InSlowStart()) {
648 OnExitStartup(now);
649 }
650 mode_ = PROBE_RTT;
651 pacing_gain_ = 1;
652 // Do not decide on the time to exit PROBE_RTT until the |bytes_in_flight|
653 // is at the target small value.
654 exit_probe_rtt_at_ = QuicTime::Zero();
655 }
656
657 if (mode_ == PROBE_RTT) {
658 sampler_.OnAppLimited();
659
660 if (exit_probe_rtt_at_ == QuicTime::Zero()) {
661 // If the window has reached the appropriate size, schedule exiting
662 // PROBE_RTT. The CWND during PROBE_RTT is kMinimumCongestionWindow, but
663 // we allow an extra packet since QUIC checks CWND before sending a
664 // packet.
665 if (unacked_packets_->bytes_in_flight() <
666 ProbeRttCongestionWindow() + kMaxOutgoingPacketSize) {
667 exit_probe_rtt_at_ = now + kProbeRttTime;
668 probe_rtt_round_passed_ = false;
669 }
670 } else {
671 if (is_round_start) {
672 probe_rtt_round_passed_ = true;
673 }
674 if (now >= exit_probe_rtt_at_ && probe_rtt_round_passed_) {
675 min_rtt_timestamp_ = now;
676 if (!is_at_full_bandwidth_) {
677 EnterStartupMode(now);
678 } else {
679 EnterProbeBandwidthMode(now);
680 }
681 }
682 }
683 }
684
685 exiting_quiescence_ = false;
686 }
687
UpdateRecoveryState(QuicPacketNumber last_acked_packet,bool has_losses,bool is_round_start)688 void BbrSender::UpdateRecoveryState(QuicPacketNumber last_acked_packet,
689 bool has_losses,
690 bool is_round_start) {
691 // Disable recovery in startup, if loss-based exit is enabled.
692 if (!is_at_full_bandwidth_) {
693 return;
694 }
695
696 // Exit recovery when there are no losses for a round.
697 if (has_losses) {
698 end_recovery_at_ = last_sent_packet_;
699 }
700
701 switch (recovery_state_) {
702 case NOT_IN_RECOVERY:
703 // Enter conservation on the first loss.
704 if (has_losses) {
705 recovery_state_ = CONSERVATION;
706 // This will cause the |recovery_window_| to be set to the correct
707 // value in CalculateRecoveryWindow().
708 recovery_window_ = 0;
709 // Since the conservation phase is meant to be lasting for a whole
710 // round, extend the current round as if it were started right now.
711 current_round_trip_end_ = last_sent_packet_;
712 }
713 break;
714
715 case CONSERVATION:
716 if (is_round_start) {
717 recovery_state_ = GROWTH;
718 }
719 ABSL_FALLTHROUGH_INTENDED;
720
721 case GROWTH:
722 // Exit recovery if appropriate.
723 if (!has_losses && last_acked_packet > end_recovery_at_) {
724 recovery_state_ = NOT_IN_RECOVERY;
725 }
726
727 break;
728 }
729 }
730
CalculatePacingRate(QuicByteCount bytes_lost)731 void BbrSender::CalculatePacingRate(QuicByteCount bytes_lost) {
732 if (BandwidthEstimate().IsZero()) {
733 return;
734 }
735
736 QuicBandwidth target_rate = pacing_gain_ * BandwidthEstimate();
737 if (is_at_full_bandwidth_) {
738 pacing_rate_ = target_rate;
739 return;
740 }
741
742 // Pace at the rate of initial_window / RTT as soon as RTT measurements are
743 // available.
744 if (pacing_rate_.IsZero() && !rtt_stats_->min_rtt().IsZero()) {
745 pacing_rate_ = QuicBandwidth::FromBytesAndTimeDelta(
746 initial_congestion_window_, rtt_stats_->min_rtt());
747 return;
748 }
749
750 if (detect_overshooting_) {
751 bytes_lost_while_detecting_overshooting_ += bytes_lost;
752 // Check for overshooting with network parameters adjusted when pacing rate
753 // > target_rate and loss has been detected.
754 if (pacing_rate_ > target_rate &&
755 bytes_lost_while_detecting_overshooting_ > 0) {
756 if (has_non_app_limited_sample_ ||
757 bytes_lost_while_detecting_overshooting_ *
758 bytes_lost_multiplier_while_detecting_overshooting_ >
759 initial_congestion_window_) {
760 // We are fairly sure overshoot happens if 1) there is at least one
761 // non app-limited bw sample or 2) half of IW gets lost. Slow pacing
762 // rate.
763 pacing_rate_ = std::max(
764 target_rate, QuicBandwidth::FromBytesAndTimeDelta(
765 cwnd_to_calculate_min_pacing_rate_, GetMinRtt()));
766 if (stats_) {
767 stats_->overshooting_detected_with_network_parameters_adjusted = true;
768 }
769 bytes_lost_while_detecting_overshooting_ = 0;
770 detect_overshooting_ = false;
771 }
772 }
773 }
774
775 // Do not decrease the pacing rate during startup.
776 pacing_rate_ = std::max(pacing_rate_, target_rate);
777 }
778
CalculateCongestionWindow(QuicByteCount bytes_acked,QuicByteCount excess_acked)779 void BbrSender::CalculateCongestionWindow(QuicByteCount bytes_acked,
780 QuicByteCount excess_acked) {
781 if (mode_ == PROBE_RTT) {
782 return;
783 }
784
785 QuicByteCount target_window =
786 GetTargetCongestionWindow(congestion_window_gain_);
787 if (is_at_full_bandwidth_) {
788 // Add the max recently measured ack aggregation to CWND.
789 target_window += sampler_.max_ack_height();
790 } else if (enable_ack_aggregation_during_startup_) {
791 // Add the most recent excess acked. Because CWND never decreases in
792 // STARTUP, this will automatically create a very localized max filter.
793 target_window += excess_acked;
794 }
795
796 // Instead of immediately setting the target CWND as the new one, BBR grows
797 // the CWND towards |target_window| by only increasing it |bytes_acked| at a
798 // time.
799 if (is_at_full_bandwidth_) {
800 congestion_window_ =
801 std::min(target_window, congestion_window_ + bytes_acked);
802 } else if (congestion_window_ < target_window ||
803 sampler_.total_bytes_acked() < initial_congestion_window_) {
804 // If the connection is not yet out of startup phase, do not decrease the
805 // window.
806 congestion_window_ = congestion_window_ + bytes_acked;
807 }
808
809 // Enforce the limits on the congestion window.
810 congestion_window_ = std::max(congestion_window_, min_congestion_window_);
811 congestion_window_ = std::min(congestion_window_, max_congestion_window_);
812 }
813
CalculateRecoveryWindow(QuicByteCount bytes_acked,QuicByteCount bytes_lost)814 void BbrSender::CalculateRecoveryWindow(QuicByteCount bytes_acked,
815 QuicByteCount bytes_lost) {
816 if (recovery_state_ == NOT_IN_RECOVERY) {
817 return;
818 }
819
820 // Set up the initial recovery window.
821 if (recovery_window_ == 0) {
822 recovery_window_ = unacked_packets_->bytes_in_flight() + bytes_acked;
823 recovery_window_ = std::max(min_congestion_window_, recovery_window_);
824 return;
825 }
826
827 // Remove losses from the recovery window, while accounting for a potential
828 // integer underflow.
829 recovery_window_ = recovery_window_ >= bytes_lost
830 ? recovery_window_ - bytes_lost
831 : kMaxSegmentSize;
832
833 // In CONSERVATION mode, just subtracting losses is sufficient. In GROWTH,
834 // release additional |bytes_acked| to achieve a slow-start-like behavior.
835 if (recovery_state_ == GROWTH) {
836 recovery_window_ += bytes_acked;
837 }
838
839 // Always allow sending at least |bytes_acked| in response.
840 recovery_window_ = std::max(
841 recovery_window_, unacked_packets_->bytes_in_flight() + bytes_acked);
842 recovery_window_ = std::max(min_congestion_window_, recovery_window_);
843 }
844
GetDebugState() const845 std::string BbrSender::GetDebugState() const {
846 std::ostringstream stream;
847 stream << ExportDebugState();
848 return stream.str();
849 }
850
OnApplicationLimited(QuicByteCount bytes_in_flight)851 void BbrSender::OnApplicationLimited(QuicByteCount bytes_in_flight) {
852 if (bytes_in_flight >= GetCongestionWindow()) {
853 return;
854 }
855
856 sampler_.OnAppLimited();
857 QUIC_DVLOG(2) << "Becoming application limited. Last sent packet: "
858 << last_sent_packet_ << ", CWND: " << GetCongestionWindow();
859 }
860
PopulateConnectionStats(QuicConnectionStats * stats) const861 void BbrSender::PopulateConnectionStats(QuicConnectionStats* stats) const {
862 stats->num_ack_aggregation_epochs = sampler_.num_ack_aggregation_epochs();
863 }
864
ExportDebugState() const865 BbrSender::DebugState BbrSender::ExportDebugState() const {
866 return DebugState(*this);
867 }
868
ModeToString(BbrSender::Mode mode)869 static std::string ModeToString(BbrSender::Mode mode) {
870 switch (mode) {
871 case BbrSender::STARTUP:
872 return "STARTUP";
873 case BbrSender::DRAIN:
874 return "DRAIN";
875 case BbrSender::PROBE_BW:
876 return "PROBE_BW";
877 case BbrSender::PROBE_RTT:
878 return "PROBE_RTT";
879 }
880 return "???";
881 }
882
operator <<(std::ostream & os,const BbrSender::Mode & mode)883 std::ostream& operator<<(std::ostream& os, const BbrSender::Mode& mode) {
884 os << ModeToString(mode);
885 return os;
886 }
887
operator <<(std::ostream & os,const BbrSender::DebugState & state)888 std::ostream& operator<<(std::ostream& os, const BbrSender::DebugState& state) {
889 os << "Mode: " << ModeToString(state.mode) << std::endl;
890 os << "Maximum bandwidth: " << state.max_bandwidth << std::endl;
891 os << "Round trip counter: " << state.round_trip_count << std::endl;
892 os << "Gain cycle index: " << static_cast<int>(state.gain_cycle_index)
893 << std::endl;
894 os << "Congestion window: " << state.congestion_window << " bytes"
895 << std::endl;
896
897 if (state.mode == BbrSender::STARTUP) {
898 os << "(startup) Bandwidth at last round: " << state.bandwidth_at_last_round
899 << std::endl;
900 os << "(startup) Rounds without gain: "
901 << state.rounds_without_bandwidth_gain << std::endl;
902 }
903
904 os << "Minimum RTT: " << state.min_rtt << std::endl;
905 os << "Minimum RTT timestamp: " << state.min_rtt_timestamp.ToDebuggingValue()
906 << std::endl;
907
908 os << "Last sample is app-limited: "
909 << (state.last_sample_is_app_limited ? "yes" : "no");
910
911 return os;
912 }
913
914 } // namespace quic
915