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