blob: 49737443c45a53132ce66f9d808d2fa2c78087f5 [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"
wub967ba572019-04-01 09:27:52 -070013#include "net/third_party/quiche/src/quic/core/quic_time.h"
wubbe29b9e2019-11-24 06:56:04 -080014#include "net/third_party/quiche/src/quic/core/quic_time_accumulator.h"
QUICHE teama6ef0a62019-03-07 20:34:33 -050015#include "net/third_party/quiche/src/quic/platform/api/quic_bug_tracker.h"
16#include "net/third_party/quiche/src/quic/platform/api/quic_fallthrough.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"
QUICHE teama6ef0a62019-03-07 20:34:33 -050020
21namespace quic {
22
23namespace {
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.
27const QuicByteCount kDefaultMinimumCongestionWindow = 4 * kMaxSegmentSize;
28
29// The gain used for the STARTUP, equal to 2/ln(2).
30const float kDefaultHighGain = 2.885f;
31// The newly derived gain for STARTUP, equal to 4 * ln(2)
32const float kDerivedHighGain = 2.773f;
33// The newly derived CWND gain for STARTUP, 2.
wub5b352f12019-05-07 11:45:26 -070034const float kDerivedHighCWNDGain = 2.0f;
QUICHE teama6ef0a62019-03-07 20:34:33 -050035// The gain used in STARTUP after loss has been detected.
36// 1.5 is enough to allow for 25% exogenous loss and still observe a 25% growth
37// in measured bandwidth.
38const float kStartupAfterLossGain = 1.5f;
39// The cycle of gains used during the PROBE_BW stage.
40const float kPacingGain[] = {1.25, 0.75, 1, 1, 1, 1, 1, 1};
41
42// The length of the gain cycle.
43const size_t kGainCycleLength = sizeof(kPacingGain) / sizeof(kPacingGain[0]);
44// The size of the bandwidth filter window, in round-trips.
45const QuicRoundTripCount kBandwidthWindowSize = kGainCycleLength + 2;
46
47// The time after which the current min_rtt value expires.
48const QuicTime::Delta kMinRttExpiry = QuicTime::Delta::FromSeconds(10);
49// The minimum time the connection can spend in PROBE_RTT mode.
50const QuicTime::Delta kProbeRttTime = QuicTime::Delta::FromMilliseconds(200);
51// If the bandwidth does not increase by the factor of |kStartupGrowthTarget|
52// within |kRoundTripsWithoutGrowthBeforeExitingStartup| rounds, the connection
53// will exit the STARTUP mode.
54const float kStartupGrowthTarget = 1.25;
55const QuicRoundTripCount kRoundTripsWithoutGrowthBeforeExitingStartup = 3;
56// Coefficient of target congestion window to use when basing PROBE_RTT on BDP.
57const float kModerateProbeRttMultiplier = 0.75;
58// Coefficient to determine if a new RTT is sufficiently similar to min_rtt that
59// we don't need to enter PROBE_RTT.
60const float kSimilarMinRttThreshold = 1.125;
61
62} // namespace
63
64BbrSender::DebugState::DebugState(const BbrSender& sender)
65 : mode(sender.mode_),
66 max_bandwidth(sender.max_bandwidth_.GetBest()),
67 round_trip_count(sender.round_trip_count_),
68 gain_cycle_index(sender.cycle_current_offset_),
69 congestion_window(sender.congestion_window_),
70 is_at_full_bandwidth(sender.is_at_full_bandwidth_),
71 bandwidth_at_last_round(sender.bandwidth_at_last_round_),
72 rounds_without_bandwidth_gain(sender.rounds_without_bandwidth_gain_),
73 min_rtt(sender.min_rtt_),
74 min_rtt_timestamp(sender.min_rtt_timestamp_),
75 recovery_state(sender.recovery_state_),
76 recovery_window(sender.recovery_window_),
77 last_sample_is_app_limited(sender.last_sample_is_app_limited_),
78 end_of_app_limited_phase(sender.sampler_.end_of_app_limited_phase()) {}
79
80BbrSender::DebugState::DebugState(const DebugState& state) = default;
81
wub967ba572019-04-01 09:27:52 -070082BbrSender::BbrSender(QuicTime now,
83 const RttStats* rtt_stats,
QUICHE teama6ef0a62019-03-07 20:34:33 -050084 const QuicUnackedPacketMap* unacked_packets,
85 QuicPacketCount initial_tcp_congestion_window,
86 QuicPacketCount max_tcp_congestion_window,
wub967ba572019-04-01 09:27:52 -070087 QuicRandom* random,
88 QuicConnectionStats* stats)
QUICHE teama6ef0a62019-03-07 20:34:33 -050089 : rtt_stats_(rtt_stats),
90 unacked_packets_(unacked_packets),
91 random_(random),
wub967ba572019-04-01 09:27:52 -070092 stats_(stats),
QUICHE teama6ef0a62019-03-07 20:34:33 -050093 mode_(STARTUP),
vasilvv4abb5662019-08-14 08:23:49 -070094 sampler_(unacked_packets, kBandwidthWindowSize),
QUICHE teama6ef0a62019-03-07 20:34:33 -050095 round_trip_count_(0),
96 max_bandwidth_(kBandwidthWindowSize, QuicBandwidth::Zero(), 0),
QUICHE teama6ef0a62019-03-07 20:34:33 -050097 min_rtt_(QuicTime::Delta::Zero()),
98 min_rtt_timestamp_(QuicTime::Zero()),
99 congestion_window_(initial_tcp_congestion_window * kDefaultTCPMSS),
100 initial_congestion_window_(initial_tcp_congestion_window *
101 kDefaultTCPMSS),
102 max_congestion_window_(max_tcp_congestion_window * kDefaultTCPMSS),
103 min_congestion_window_(kDefaultMinimumCongestionWindow),
104 high_gain_(kDefaultHighGain),
105 high_cwnd_gain_(kDefaultHighGain),
106 drain_gain_(1.f / kDefaultHighGain),
107 pacing_rate_(QuicBandwidth::Zero()),
108 pacing_gain_(1),
109 congestion_window_gain_(1),
110 congestion_window_gain_constant_(
danzh88e3e052019-06-13 11:47:18 -0700111 static_cast<float>(GetQuicFlag(FLAGS_quic_bbr_cwnd_gain))),
QUICHE teama6ef0a62019-03-07 20:34:33 -0500112 num_startup_rtts_(kRoundTripsWithoutGrowthBeforeExitingStartup),
113 exit_startup_on_loss_(false),
114 cycle_current_offset_(0),
115 last_cycle_start_(QuicTime::Zero()),
116 is_at_full_bandwidth_(false),
117 rounds_without_bandwidth_gain_(0),
118 bandwidth_at_last_round_(QuicBandwidth::Zero()),
119 exiting_quiescence_(false),
120 exit_probe_rtt_at_(QuicTime::Zero()),
121 probe_rtt_round_passed_(false),
122 last_sample_is_app_limited_(false),
123 has_non_app_limited_sample_(false),
124 flexible_app_limited_(false),
125 recovery_state_(NOT_IN_RECOVERY),
126 recovery_window_(max_congestion_window_),
QUICHE teama6ef0a62019-03-07 20:34:33 -0500127 slower_startup_(false),
128 rate_based_startup_(false),
129 startup_rate_reduction_multiplier_(0),
130 startup_bytes_lost_(0),
131 enable_ack_aggregation_during_startup_(false),
132 expire_ack_aggregation_in_startup_(false),
133 drain_to_target_(false),
134 probe_rtt_based_on_bdp_(false),
135 probe_rtt_skipped_if_similar_rtt_(false),
136 probe_rtt_disabled_if_app_limited_(false),
137 app_limited_since_last_probe_rtt_(false),
wub64c34112019-08-19 11:54:55 -0700138 min_rtt_since_last_probe_rtt_(QuicTime::Delta::Infinite()) {
wub967ba572019-04-01 09:27:52 -0700139 if (stats_) {
wubbe29b9e2019-11-24 06:56:04 -0800140 // Clear some startup stats if |stats_| has been used by another sender,
141 // which happens e.g. when QuicConnection switch send algorithms.
wub967ba572019-04-01 09:27:52 -0700142 stats_->slowstart_count = 0;
wubbe29b9e2019-11-24 06:56:04 -0800143 stats_->slowstart_duration = QuicTimeAccumulator();
wub967ba572019-04-01 09:27:52 -0700144 }
145 EnterStartupMode(now);
QUICHE teama6ef0a62019-03-07 20:34:33 -0500146}
147
148BbrSender::~BbrSender() {}
149
150void BbrSender::SetInitialCongestionWindowInPackets(
151 QuicPacketCount congestion_window) {
152 if (mode_ == STARTUP) {
153 initial_congestion_window_ = congestion_window * kDefaultTCPMSS;
154 congestion_window_ = congestion_window * kDefaultTCPMSS;
155 }
156}
157
158bool BbrSender::InSlowStart() const {
159 return mode_ == STARTUP;
160}
161
162void BbrSender::OnPacketSent(QuicTime sent_time,
163 QuicByteCount bytes_in_flight,
164 QuicPacketNumber packet_number,
165 QuicByteCount bytes,
166 HasRetransmittableData is_retransmittable) {
wub967ba572019-04-01 09:27:52 -0700167 if (stats_ && InSlowStart()) {
168 ++stats_->slowstart_packets_sent;
169 stats_->slowstart_bytes_sent += bytes;
170 }
171
QUICHE teama6ef0a62019-03-07 20:34:33 -0500172 last_sent_packet_ = packet_number;
173
174 if (bytes_in_flight == 0 && sampler_.is_app_limited()) {
175 exiting_quiescence_ = true;
176 }
177
QUICHE teama6ef0a62019-03-07 20:34:33 -0500178 sampler_.OnPacketSent(sent_time, packet_number, bytes, bytes_in_flight,
179 is_retransmittable);
180}
181
182bool BbrSender::CanSend(QuicByteCount bytes_in_flight) {
183 return bytes_in_flight < GetCongestionWindow();
184}
185
dschinazi17d42422019-06-18 16:35:07 -0700186QuicBandwidth BbrSender::PacingRate(QuicByteCount /*bytes_in_flight*/) const {
QUICHE teama6ef0a62019-03-07 20:34:33 -0500187 if (pacing_rate_.IsZero()) {
188 return high_gain_ * QuicBandwidth::FromBytesAndTimeDelta(
189 initial_congestion_window_, GetMinRtt());
190 }
191 return pacing_rate_;
192}
193
194QuicBandwidth BbrSender::BandwidthEstimate() const {
195 return max_bandwidth_.GetBest();
196}
197
198QuicByteCount BbrSender::GetCongestionWindow() const {
199 if (mode_ == PROBE_RTT) {
200 return ProbeRttCongestionWindow();
201 }
202
203 if (InRecovery() && !(rate_based_startup_ && mode_ == STARTUP)) {
204 return std::min(congestion_window_, recovery_window_);
205 }
206
207 return congestion_window_;
208}
209
210QuicByteCount BbrSender::GetSlowStartThreshold() const {
211 return 0;
212}
213
214bool BbrSender::InRecovery() const {
215 return recovery_state_ != NOT_IN_RECOVERY;
216}
217
218bool BbrSender::ShouldSendProbingPacket() const {
219 if (pacing_gain_ <= 1) {
220 return false;
221 }
222
223 // TODO(b/77975811): If the pipe is highly under-utilized, consider not
224 // sending a probing transmission, because the extra bandwidth is not needed.
225 // If flexible_app_limited is enabled, check if the pipe is sufficiently full.
226 if (flexible_app_limited_) {
227 return !IsPipeSufficientlyFull();
228 } else {
229 return true;
230 }
231}
232
233bool BbrSender::IsPipeSufficientlyFull() const {
234 // See if we need more bytes in flight to see more bandwidth.
235 if (mode_ == STARTUP) {
236 // STARTUP exits if it doesn't observe a 25% bandwidth increase, so the CWND
237 // must be more than 25% above the target.
238 return unacked_packets_->bytes_in_flight() >=
239 GetTargetCongestionWindow(1.5);
240 }
241 if (pacing_gain_ > 1) {
242 // Super-unity PROBE_BW doesn't exit until 1.25 * BDP is achieved.
243 return unacked_packets_->bytes_in_flight() >=
244 GetTargetCongestionWindow(pacing_gain_);
245 }
246 // If bytes_in_flight are above the target congestion window, it should be
247 // possible to observe the same or more bandwidth if it's available.
248 return unacked_packets_->bytes_in_flight() >= GetTargetCongestionWindow(1.1);
249}
250
251void BbrSender::SetFromConfig(const QuicConfig& config,
252 Perspective perspective) {
253 if (config.HasClientRequestedIndependentOption(kLRTT, perspective)) {
254 exit_startup_on_loss_ = true;
255 }
256 if (config.HasClientRequestedIndependentOption(k1RTT, perspective)) {
257 num_startup_rtts_ = 1;
258 }
259 if (config.HasClientRequestedIndependentOption(k2RTT, perspective)) {
260 num_startup_rtts_ = 2;
261 }
262 if (config.HasClientRequestedIndependentOption(kBBRS, perspective)) {
263 slower_startup_ = true;
264 }
265 if (config.HasClientRequestedIndependentOption(kBBR3, perspective)) {
266 drain_to_target_ = true;
267 }
268 if (config.HasClientRequestedIndependentOption(kBBS1, perspective)) {
269 rate_based_startup_ = true;
270 }
271 if (GetQuicReloadableFlag(quic_bbr_startup_rate_reduction) &&
272 config.HasClientRequestedIndependentOption(kBBS4, perspective)) {
ianswettf0f94d62019-12-08 06:22:35 -0800273 QUIC_RELOADABLE_FLAG_COUNT_N(quic_bbr_startup_rate_reduction, 1, 2);
QUICHE teama6ef0a62019-03-07 20:34:33 -0500274 rate_based_startup_ = true;
275 // Hits 1.25x pacing multiplier when ~2/3 CWND is lost.
276 startup_rate_reduction_multiplier_ = 1;
277 }
278 if (GetQuicReloadableFlag(quic_bbr_startup_rate_reduction) &&
279 config.HasClientRequestedIndependentOption(kBBS5, perspective)) {
ianswettf0f94d62019-12-08 06:22:35 -0800280 QUIC_RELOADABLE_FLAG_COUNT_N(quic_bbr_startup_rate_reduction, 2, 2);
QUICHE teama6ef0a62019-03-07 20:34:33 -0500281 rate_based_startup_ = true;
282 // Hits 1.25x pacing multiplier when ~1/3 CWND is lost.
283 startup_rate_reduction_multiplier_ = 2;
284 }
285 if (config.HasClientRequestedIndependentOption(kBBR4, perspective)) {
wub38f86522019-10-07 11:54:53 -0700286 sampler_.SetMaxAckHeightTrackerWindowLength(2 * kBandwidthWindowSize);
QUICHE teama6ef0a62019-03-07 20:34:33 -0500287 }
288 if (config.HasClientRequestedIndependentOption(kBBR5, perspective)) {
wub38f86522019-10-07 11:54:53 -0700289 sampler_.SetMaxAckHeightTrackerWindowLength(4 * kBandwidthWindowSize);
QUICHE teama6ef0a62019-03-07 20:34:33 -0500290 }
291 if (GetQuicReloadableFlag(quic_bbr_less_probe_rtt) &&
292 config.HasClientRequestedIndependentOption(kBBR6, perspective)) {
293 QUIC_RELOADABLE_FLAG_COUNT_N(quic_bbr_less_probe_rtt, 1, 3);
294 probe_rtt_based_on_bdp_ = true;
295 }
296 if (GetQuicReloadableFlag(quic_bbr_less_probe_rtt) &&
297 config.HasClientRequestedIndependentOption(kBBR7, perspective)) {
298 QUIC_RELOADABLE_FLAG_COUNT_N(quic_bbr_less_probe_rtt, 2, 3);
299 probe_rtt_skipped_if_similar_rtt_ = true;
300 }
301 if (GetQuicReloadableFlag(quic_bbr_less_probe_rtt) &&
302 config.HasClientRequestedIndependentOption(kBBR8, perspective)) {
303 QUIC_RELOADABLE_FLAG_COUNT_N(quic_bbr_less_probe_rtt, 3, 3);
304 probe_rtt_disabled_if_app_limited_ = true;
305 }
306 if (GetQuicReloadableFlag(quic_bbr_flexible_app_limited) &&
307 config.HasClientRequestedIndependentOption(kBBR9, perspective)) {
308 QUIC_RELOADABLE_FLAG_COUNT(quic_bbr_flexible_app_limited);
309 flexible_app_limited_ = true;
310 }
ianswettcfef5c92019-06-18 07:58:39 -0700311 if (config.HasClientRequestedIndependentOption(kBBQ1, perspective)) {
QUICHE teama6ef0a62019-03-07 20:34:33 -0500312 set_high_gain(kDerivedHighGain);
313 set_high_cwnd_gain(kDerivedHighGain);
314 set_drain_gain(1.f / kDerivedHighGain);
315 }
ianswettcfef5c92019-06-18 07:58:39 -0700316 if (config.HasClientRequestedIndependentOption(kBBQ2, perspective)) {
QUICHE teama6ef0a62019-03-07 20:34:33 -0500317 set_high_cwnd_gain(kDerivedHighCWNDGain);
318 }
ianswettcfef5c92019-06-18 07:58:39 -0700319 if (config.HasClientRequestedIndependentOption(kBBQ3, perspective)) {
QUICHE teama6ef0a62019-03-07 20:34:33 -0500320 enable_ack_aggregation_during_startup_ = true;
321 }
QUICHE teama6ef0a62019-03-07 20:34:33 -0500322 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
QUICHE teamfdcfe3b2019-11-06 10:54:25 -0800332void BbrSender::AdjustNetworkParameters(const NetworkParams& params) {
QUICHE teamb4e187c2019-11-14 06:22:50 -0800333 const QuicBandwidth& bandwidth = params.bandwidth;
334 const QuicTime::Delta& rtt = params.rtt;
QUICHE teamfdcfe3b2019-11-06 10:54:25 -0800335
fayangbbe9a1b2019-11-07 10:44:08 -0800336 if (GetQuicReloadableFlag(quic_bbr_donot_inject_bandwidth)) {
337 QUIC_RELOADABLE_FLAG_COUNT(quic_bbr_donot_inject_bandwidth);
338 } else if (!bandwidth.IsZero()) {
QUICHE teama6ef0a62019-03-07 20:34:33 -0500339 max_bandwidth_.Update(bandwidth, round_trip_count_);
340 }
341 if (!rtt.IsZero() && (min_rtt_ > rtt || min_rtt_.IsZero())) {
342 min_rtt_ = rtt;
343 }
QUICHE teamb4e187c2019-11-14 06:22:50 -0800344
345 if (params.quic_fix_bbr_cwnd_in_bandwidth_resumption && mode_ == STARTUP) {
fayangc050d7a2019-05-17 11:20:38 -0700346 if (bandwidth.IsZero()) {
347 // Ignore bad bandwidth samples.
fayangc050d7a2019-05-17 11:20:38 -0700348 return;
349 }
fayangbbe9a1b2019-11-07 10:44:08 -0800350 const QuicByteCount new_cwnd = std::max(
351 kMinInitialCongestionWindow * kDefaultTCPMSS,
352 std::min(
353 kMaxInitialCongestionWindow * kDefaultTCPMSS,
354 bandwidth * (GetQuicReloadableFlag(quic_bbr_donot_inject_bandwidth)
355 ? GetMinRtt()
356 : rtt_stats_->SmoothedOrInitialRtt())));
fayang14650e42019-06-04 10:30:33 -0700357 if (!rtt_stats_->smoothed_rtt().IsZero()) {
358 QUIC_CODE_COUNT(quic_smoothed_rtt_available);
359 } else if (rtt_stats_->initial_rtt() !=
360 QuicTime::Delta::FromMilliseconds(kInitialRttMs)) {
361 QUIC_CODE_COUNT(quic_client_initial_rtt_available);
362 } else {
363 QUIC_CODE_COUNT(quic_default_initial_rtt);
364 }
QUICHE teamb4e187c2019-11-14 06:22:50 -0800365 if (new_cwnd < congestion_window_ && !params.allow_cwnd_to_decrease) {
fayangc050d7a2019-05-17 11:20:38 -0700366 // Only decrease cwnd if allow_cwnd_to_decrease is true.
fayangf1b99dc2019-05-14 06:29:18 -0700367 return;
368 }
fayang8cafde02019-06-04 06:21:04 -0700369 if (GetQuicReloadableFlag(quic_conservative_cwnd_and_pacing_gains)) {
370 // Decreases cwnd gain and pacing gain. Please note, if pacing_rate_ has
371 // been calculated, it cannot decrease in STARTUP phase.
372 QUIC_RELOADABLE_FLAG_COUNT(quic_conservative_cwnd_and_pacing_gains);
373 set_high_gain(kDerivedHighCWNDGain);
374 set_high_cwnd_gain(kDerivedHighCWNDGain);
375 }
fayangf1b99dc2019-05-14 06:29:18 -0700376 congestion_window_ = new_cwnd;
QUICHE teamb4e187c2019-11-14 06:22:50 -0800377 if (params.quic_bbr_fix_pacing_rate) {
fayangf2c4e3e2019-10-30 07:46:51 -0700378 // Pace at the rate of new_cwnd / RTT.
379 QuicBandwidth new_pacing_rate =
380 QuicBandwidth::FromBytesAndTimeDelta(congestion_window_, GetMinRtt());
381 pacing_rate_ = std::max(pacing_rate_, new_pacing_rate);
382 }
fayangbe83ecd2019-04-26 13:58:09 -0700383 }
QUICHE teama6ef0a62019-03-07 20:34:33 -0500384}
385
386void BbrSender::OnCongestionEvent(bool /*rtt_updated*/,
387 QuicByteCount prior_in_flight,
388 QuicTime event_time,
389 const AckedPacketVector& acked_packets,
390 const LostPacketVector& lost_packets) {
391 const QuicByteCount total_bytes_acked_before = sampler_.total_bytes_acked();
392
393 bool is_round_start = false;
394 bool min_rtt_expired = false;
395
396 DiscardLostPackets(lost_packets);
397
398 // Input the new data into the BBR model of the connection.
399 QuicByteCount excess_acked = 0;
400 if (!acked_packets.empty()) {
401 QuicPacketNumber last_acked_packet = acked_packets.rbegin()->packet_number;
402 is_round_start = UpdateRoundTripCounter(last_acked_packet);
403 min_rtt_expired = UpdateBandwidthAndMinRtt(event_time, acked_packets);
404 UpdateRecoveryState(last_acked_packet, !lost_packets.empty(),
405 is_round_start);
406
wub38f86522019-10-07 11:54:53 -0700407 excess_acked =
408 sampler_.OnAckEventEnd(max_bandwidth_.GetBest(), round_trip_count_);
QUICHE teama6ef0a62019-03-07 20:34:33 -0500409 }
410
411 // Handle logic specific to PROBE_BW mode.
412 if (mode_ == PROBE_BW) {
413 UpdateGainCyclePhase(event_time, prior_in_flight, !lost_packets.empty());
414 }
415
416 // Handle logic specific to STARTUP and DRAIN modes.
417 if (is_round_start && !is_at_full_bandwidth_) {
418 CheckIfFullBandwidthReached();
419 }
420 MaybeExitStartupOrDrain(event_time);
421
422 // Handle logic specific to PROBE_RTT.
423 MaybeEnterOrExitProbeRtt(event_time, is_round_start, min_rtt_expired);
424
425 // Calculate number of packets acked and lost.
426 QuicByteCount bytes_acked =
427 sampler_.total_bytes_acked() - total_bytes_acked_before;
428 QuicByteCount bytes_lost = 0;
429 for (const auto& packet : lost_packets) {
430 bytes_lost += packet.bytes_lost;
431 }
432
433 // After the model is updated, recalculate the pacing rate and congestion
434 // window.
435 CalculatePacingRate();
436 CalculateCongestionWindow(bytes_acked, excess_acked);
437 CalculateRecoveryWindow(bytes_acked, bytes_lost);
438
439 // Cleanup internal state.
440 sampler_.RemoveObsoletePackets(unacked_packets_->GetLeastUnacked());
441}
442
443CongestionControlType BbrSender::GetCongestionControlType() const {
444 return kBBR;
445}
446
447QuicTime::Delta BbrSender::GetMinRtt() const {
448 return !min_rtt_.IsZero() ? min_rtt_ : rtt_stats_->initial_rtt();
449}
450
451QuicByteCount BbrSender::GetTargetCongestionWindow(float gain) const {
452 QuicByteCount bdp = GetMinRtt() * BandwidthEstimate();
453 QuicByteCount congestion_window = gain * bdp;
454
455 // BDP estimate will be zero if no bandwidth samples are available yet.
456 if (congestion_window == 0) {
457 congestion_window = gain * initial_congestion_window_;
458 }
459
460 return std::max(congestion_window, min_congestion_window_);
461}
462
463QuicByteCount BbrSender::ProbeRttCongestionWindow() const {
464 if (probe_rtt_based_on_bdp_) {
465 return GetTargetCongestionWindow(kModerateProbeRttMultiplier);
466 }
467 return min_congestion_window_;
468}
469
wub967ba572019-04-01 09:27:52 -0700470void BbrSender::EnterStartupMode(QuicTime now) {
471 if (stats_) {
472 ++stats_->slowstart_count;
wubbe29b9e2019-11-24 06:56:04 -0800473 stats_->slowstart_duration.Start(now);
wub967ba572019-04-01 09:27:52 -0700474 }
QUICHE teama6ef0a62019-03-07 20:34:33 -0500475 mode_ = STARTUP;
476 pacing_gain_ = high_gain_;
477 congestion_window_gain_ = high_cwnd_gain_;
478}
479
480void BbrSender::EnterProbeBandwidthMode(QuicTime now) {
481 mode_ = PROBE_BW;
482 congestion_window_gain_ = congestion_window_gain_constant_;
483
484 // Pick a random offset for the gain cycle out of {0, 2..7} range. 1 is
485 // excluded because in that case increased gain and decreased gain would not
486 // follow each other.
487 cycle_current_offset_ = random_->RandUint64() % (kGainCycleLength - 1);
488 if (cycle_current_offset_ >= 1) {
489 cycle_current_offset_ += 1;
490 }
491
492 last_cycle_start_ = now;
493 pacing_gain_ = kPacingGain[cycle_current_offset_];
494}
495
496void BbrSender::DiscardLostPackets(const LostPacketVector& lost_packets) {
497 for (const LostPacket& packet : lost_packets) {
wuba545ca12019-12-11 19:27:43 -0800498 sampler_.OnPacketLost(packet.packet_number, packet.bytes_lost);
wub967ba572019-04-01 09:27:52 -0700499 if (mode_ == STARTUP) {
500 if (stats_) {
501 ++stats_->slowstart_packets_lost;
502 stats_->slowstart_bytes_lost += packet.bytes_lost;
503 }
504 if (startup_rate_reduction_multiplier_ != 0) {
505 startup_bytes_lost_ += packet.bytes_lost;
506 }
QUICHE teama6ef0a62019-03-07 20:34:33 -0500507 }
508 }
509}
510
511bool BbrSender::UpdateRoundTripCounter(QuicPacketNumber last_acked_packet) {
512 if (!current_round_trip_end_.IsInitialized() ||
513 last_acked_packet > current_round_trip_end_) {
514 round_trip_count_++;
515 current_round_trip_end_ = last_sent_packet_;
wub967ba572019-04-01 09:27:52 -0700516 if (stats_ && InSlowStart()) {
517 ++stats_->slowstart_num_rtts;
518 }
QUICHE teama6ef0a62019-03-07 20:34:33 -0500519 return true;
520 }
521
522 return false;
523}
524
525bool BbrSender::UpdateBandwidthAndMinRtt(
526 QuicTime now,
527 const AckedPacketVector& acked_packets) {
528 QuicTime::Delta sample_min_rtt = QuicTime::Delta::Infinite();
529 for (const auto& packet : acked_packets) {
QUICHE teama6ef0a62019-03-07 20:34:33 -0500530 BandwidthSample bandwidth_sample =
531 sampler_.OnPacketAcknowledged(now, packet.packet_number);
wub03637f52019-05-30 10:52:20 -0700532 if (!bandwidth_sample.state_at_send.is_valid) {
wubfb4e2132019-04-05 12:30:09 -0700533 // From the sampler's perspective, the packet has never been sent, or the
534 // packet has been acked or marked as lost previously.
535 continue;
536 }
537
wub254545c2019-04-04 13:56:52 -0700538 last_sample_is_app_limited_ = bandwidth_sample.state_at_send.is_app_limited;
539 has_non_app_limited_sample_ |=
540 !bandwidth_sample.state_at_send.is_app_limited;
QUICHE teama6ef0a62019-03-07 20:34:33 -0500541 if (!bandwidth_sample.rtt.IsZero()) {
542 sample_min_rtt = std::min(sample_min_rtt, bandwidth_sample.rtt);
543 }
544
wub254545c2019-04-04 13:56:52 -0700545 if (!bandwidth_sample.state_at_send.is_app_limited ||
QUICHE teama6ef0a62019-03-07 20:34:33 -0500546 bandwidth_sample.bandwidth > BandwidthEstimate()) {
547 max_bandwidth_.Update(bandwidth_sample.bandwidth, round_trip_count_);
548 }
549 }
550
551 // If none of the RTT samples are valid, return immediately.
552 if (sample_min_rtt.IsInfinite()) {
553 return false;
554 }
555 min_rtt_since_last_probe_rtt_ =
556 std::min(min_rtt_since_last_probe_rtt_, sample_min_rtt);
557
558 // Do not expire min_rtt if none was ever available.
559 bool min_rtt_expired =
560 !min_rtt_.IsZero() && (now > (min_rtt_timestamp_ + kMinRttExpiry));
561
562 if (min_rtt_expired || sample_min_rtt < min_rtt_ || min_rtt_.IsZero()) {
563 QUIC_DVLOG(2) << "Min RTT updated, old value: " << min_rtt_
564 << ", new value: " << sample_min_rtt
565 << ", current time: " << now.ToDebuggingValue();
566
567 if (min_rtt_expired && ShouldExtendMinRttExpiry()) {
568 min_rtt_expired = false;
569 } else {
570 min_rtt_ = sample_min_rtt;
571 }
572 min_rtt_timestamp_ = now;
573 // Reset since_last_probe_rtt fields.
574 min_rtt_since_last_probe_rtt_ = QuicTime::Delta::Infinite();
575 app_limited_since_last_probe_rtt_ = false;
576 }
577 DCHECK(!min_rtt_.IsZero());
578
579 return min_rtt_expired;
580}
581
582bool BbrSender::ShouldExtendMinRttExpiry() const {
583 if (probe_rtt_disabled_if_app_limited_ && app_limited_since_last_probe_rtt_) {
584 // Extend the current min_rtt if we've been app limited recently.
585 return true;
586 }
587 const bool min_rtt_increased_since_last_probe =
588 min_rtt_since_last_probe_rtt_ > min_rtt_ * kSimilarMinRttThreshold;
589 if (probe_rtt_skipped_if_similar_rtt_ && app_limited_since_last_probe_rtt_ &&
590 !min_rtt_increased_since_last_probe) {
591 // Extend the current min_rtt if we've been app limited recently and an rtt
592 // has been measured in that time that's less than 12.5% more than the
593 // current min_rtt.
594 return true;
595 }
596 return false;
597}
598
599void BbrSender::UpdateGainCyclePhase(QuicTime now,
600 QuicByteCount prior_in_flight,
601 bool has_losses) {
602 const QuicByteCount bytes_in_flight = unacked_packets_->bytes_in_flight();
603 // In most cases, the cycle is advanced after an RTT passes.
604 bool should_advance_gain_cycling = now - last_cycle_start_ > GetMinRtt();
605
606 // If the pacing gain is above 1.0, the connection is trying to probe the
607 // bandwidth by increasing the number of bytes in flight to at least
608 // pacing_gain * BDP. Make sure that it actually reaches the target, as long
609 // as there are no losses suggesting that the buffers are not able to hold
610 // that much.
611 if (pacing_gain_ > 1.0 && !has_losses &&
612 prior_in_flight < GetTargetCongestionWindow(pacing_gain_)) {
613 should_advance_gain_cycling = false;
614 }
615
616 // If pacing gain is below 1.0, the connection is trying to drain the extra
617 // queue which could have been incurred by probing prior to it. If the number
618 // of bytes in flight falls down to the estimated BDP value earlier, conclude
619 // that the queue has been successfully drained and exit this cycle early.
620 if (pacing_gain_ < 1.0 && bytes_in_flight <= GetTargetCongestionWindow(1)) {
621 should_advance_gain_cycling = true;
622 }
623
624 if (should_advance_gain_cycling) {
625 cycle_current_offset_ = (cycle_current_offset_ + 1) % kGainCycleLength;
626 last_cycle_start_ = now;
627 // Stay in low gain mode until the target BDP is hit.
628 // Low gain mode will be exited immediately when the target BDP is achieved.
629 if (drain_to_target_ && pacing_gain_ < 1 &&
630 kPacingGain[cycle_current_offset_] == 1 &&
631 bytes_in_flight > GetTargetCongestionWindow(1)) {
632 return;
633 }
634 pacing_gain_ = kPacingGain[cycle_current_offset_];
635 }
636}
637
638void BbrSender::CheckIfFullBandwidthReached() {
639 if (last_sample_is_app_limited_) {
640 return;
641 }
642
643 QuicBandwidth target = bandwidth_at_last_round_ * kStartupGrowthTarget;
644 if (BandwidthEstimate() >= target) {
645 bandwidth_at_last_round_ = BandwidthEstimate();
646 rounds_without_bandwidth_gain_ = 0;
647 if (expire_ack_aggregation_in_startup_) {
648 // Expire old excess delivery measurements now that bandwidth increased.
wub38f86522019-10-07 11:54:53 -0700649 sampler_.ResetMaxAckHeightTracker(0, round_trip_count_);
QUICHE teama6ef0a62019-03-07 20:34:33 -0500650 }
651 return;
652 }
653
654 rounds_without_bandwidth_gain_++;
655 if ((rounds_without_bandwidth_gain_ >= num_startup_rtts_) ||
656 (exit_startup_on_loss_ && InRecovery())) {
657 DCHECK(has_non_app_limited_sample_);
658 is_at_full_bandwidth_ = true;
659 }
660}
661
662void BbrSender::MaybeExitStartupOrDrain(QuicTime now) {
663 if (mode_ == STARTUP && is_at_full_bandwidth_) {
wub967ba572019-04-01 09:27:52 -0700664 OnExitStartup(now);
QUICHE teama6ef0a62019-03-07 20:34:33 -0500665 mode_ = DRAIN;
666 pacing_gain_ = drain_gain_;
667 congestion_window_gain_ = high_cwnd_gain_;
668 }
669 if (mode_ == DRAIN &&
670 unacked_packets_->bytes_in_flight() <= GetTargetCongestionWindow(1)) {
671 EnterProbeBandwidthMode(now);
672 }
673}
674
wub967ba572019-04-01 09:27:52 -0700675void BbrSender::OnExitStartup(QuicTime now) {
676 DCHECK_EQ(mode_, STARTUP);
677 if (stats_) {
wubbe29b9e2019-11-24 06:56:04 -0800678 stats_->slowstart_duration.Stop(now);
wub967ba572019-04-01 09:27:52 -0700679 }
680}
681
QUICHE teama6ef0a62019-03-07 20:34:33 -0500682void BbrSender::MaybeEnterOrExitProbeRtt(QuicTime now,
683 bool is_round_start,
684 bool min_rtt_expired) {
685 if (min_rtt_expired && !exiting_quiescence_ && mode_ != PROBE_RTT) {
wub967ba572019-04-01 09:27:52 -0700686 if (InSlowStart()) {
687 OnExitStartup(now);
688 }
QUICHE teama6ef0a62019-03-07 20:34:33 -0500689 mode_ = PROBE_RTT;
690 pacing_gain_ = 1;
691 // Do not decide on the time to exit PROBE_RTT until the |bytes_in_flight|
692 // is at the target small value.
693 exit_probe_rtt_at_ = QuicTime::Zero();
694 }
695
696 if (mode_ == PROBE_RTT) {
697 sampler_.OnAppLimited();
698
699 if (exit_probe_rtt_at_ == QuicTime::Zero()) {
700 // If the window has reached the appropriate size, schedule exiting
701 // PROBE_RTT. The CWND during PROBE_RTT is kMinimumCongestionWindow, but
702 // we allow an extra packet since QUIC checks CWND before sending a
703 // packet.
704 if (unacked_packets_->bytes_in_flight() <
dschinazi66dea072019-04-09 11:41:06 -0700705 ProbeRttCongestionWindow() + kMaxOutgoingPacketSize) {
QUICHE teama6ef0a62019-03-07 20:34:33 -0500706 exit_probe_rtt_at_ = now + kProbeRttTime;
707 probe_rtt_round_passed_ = false;
708 }
709 } else {
710 if (is_round_start) {
711 probe_rtt_round_passed_ = true;
712 }
713 if (now >= exit_probe_rtt_at_ && probe_rtt_round_passed_) {
714 min_rtt_timestamp_ = now;
715 if (!is_at_full_bandwidth_) {
wub967ba572019-04-01 09:27:52 -0700716 EnterStartupMode(now);
QUICHE teama6ef0a62019-03-07 20:34:33 -0500717 } else {
718 EnterProbeBandwidthMode(now);
719 }
720 }
721 }
722 }
723
724 exiting_quiescence_ = false;
725}
726
727void BbrSender::UpdateRecoveryState(QuicPacketNumber last_acked_packet,
728 bool has_losses,
729 bool is_round_start) {
730 // Exit recovery when there are no losses for a round.
731 if (has_losses) {
732 end_recovery_at_ = last_sent_packet_;
733 }
734
735 switch (recovery_state_) {
736 case NOT_IN_RECOVERY:
737 // Enter conservation on the first loss.
738 if (has_losses) {
739 recovery_state_ = CONSERVATION;
740 // This will cause the |recovery_window_| to be set to the correct
741 // value in CalculateRecoveryWindow().
742 recovery_window_ = 0;
743 // Since the conservation phase is meant to be lasting for a whole
744 // round, extend the current round as if it were started right now.
745 current_round_trip_end_ = last_sent_packet_;
QUICHE teama6ef0a62019-03-07 20:34:33 -0500746 }
747 break;
748
749 case CONSERVATION:
750 if (is_round_start) {
751 recovery_state_ = GROWTH;
752 }
753 QUIC_FALLTHROUGH_INTENDED;
754
755 case GROWTH:
756 // Exit recovery if appropriate.
757 if (!has_losses && last_acked_packet > end_recovery_at_) {
758 recovery_state_ = NOT_IN_RECOVERY;
QUICHE teama6ef0a62019-03-07 20:34:33 -0500759 }
760
761 break;
762 }
QUICHE teama6ef0a62019-03-07 20:34:33 -0500763}
764
QUICHE teama6ef0a62019-03-07 20:34:33 -0500765void BbrSender::CalculatePacingRate() {
766 if (BandwidthEstimate().IsZero()) {
767 return;
768 }
769
770 QuicBandwidth target_rate = pacing_gain_ * BandwidthEstimate();
771 if (is_at_full_bandwidth_) {
772 pacing_rate_ = target_rate;
773 return;
774 }
775
776 // Pace at the rate of initial_window / RTT as soon as RTT measurements are
777 // available.
778 if (pacing_rate_.IsZero() && !rtt_stats_->min_rtt().IsZero()) {
779 pacing_rate_ = QuicBandwidth::FromBytesAndTimeDelta(
780 initial_congestion_window_, rtt_stats_->min_rtt());
781 return;
782 }
783 // Slow the pacing rate in STARTUP once loss has ever been detected.
784 const bool has_ever_detected_loss = end_recovery_at_.IsInitialized();
785 if (slower_startup_ && has_ever_detected_loss &&
786 has_non_app_limited_sample_) {
787 pacing_rate_ = kStartupAfterLossGain * BandwidthEstimate();
788 return;
789 }
790
791 // Slow the pacing rate in STARTUP by the bytes_lost / CWND.
792 if (startup_rate_reduction_multiplier_ != 0 && has_ever_detected_loss &&
793 has_non_app_limited_sample_) {
794 pacing_rate_ =
795 (1 - (startup_bytes_lost_ * startup_rate_reduction_multiplier_ * 1.0f /
796 congestion_window_)) *
797 target_rate;
798 // Ensure the pacing rate doesn't drop below the startup growth target times
799 // the bandwidth estimate.
800 pacing_rate_ =
801 std::max(pacing_rate_, kStartupGrowthTarget * BandwidthEstimate());
802 return;
803 }
804
805 // Do not decrease the pacing rate during startup.
806 pacing_rate_ = std::max(pacing_rate_, target_rate);
807}
808
809void BbrSender::CalculateCongestionWindow(QuicByteCount bytes_acked,
810 QuicByteCount excess_acked) {
811 if (mode_ == PROBE_RTT) {
812 return;
813 }
814
815 QuicByteCount target_window =
816 GetTargetCongestionWindow(congestion_window_gain_);
817 if (is_at_full_bandwidth_) {
818 // Add the max recently measured ack aggregation to CWND.
wub38f86522019-10-07 11:54:53 -0700819 target_window += sampler_.max_ack_height();
QUICHE teama6ef0a62019-03-07 20:34:33 -0500820 } else if (enable_ack_aggregation_during_startup_) {
821 // Add the most recent excess acked. Because CWND never decreases in
822 // STARTUP, this will automatically create a very localized max filter.
823 target_window += excess_acked;
824 }
825
826 // Instead of immediately setting the target CWND as the new one, BBR grows
827 // the CWND towards |target_window| by only increasing it |bytes_acked| at a
828 // time.
829 const bool add_bytes_acked =
830 !GetQuicReloadableFlag(quic_bbr_no_bytes_acked_in_startup_recovery) ||
831 !InRecovery();
832 if (is_at_full_bandwidth_) {
833 congestion_window_ =
834 std::min(target_window, congestion_window_ + bytes_acked);
835 } else if (add_bytes_acked &&
836 (congestion_window_ < target_window ||
837 sampler_.total_bytes_acked() < initial_congestion_window_)) {
838 // If the connection is not yet out of startup phase, do not decrease the
839 // window.
840 congestion_window_ = congestion_window_ + bytes_acked;
841 }
842
843 // Enforce the limits on the congestion window.
844 congestion_window_ = std::max(congestion_window_, min_congestion_window_);
845 congestion_window_ = std::min(congestion_window_, max_congestion_window_);
846}
847
848void BbrSender::CalculateRecoveryWindow(QuicByteCount bytes_acked,
849 QuicByteCount bytes_lost) {
850 if (rate_based_startup_ && mode_ == STARTUP) {
851 return;
852 }
853
854 if (recovery_state_ == NOT_IN_RECOVERY) {
855 return;
856 }
857
858 // Set up the initial recovery window.
859 if (recovery_window_ == 0) {
860 recovery_window_ = unacked_packets_->bytes_in_flight() + bytes_acked;
861 recovery_window_ = std::max(min_congestion_window_, recovery_window_);
862 return;
863 }
864
865 // Remove losses from the recovery window, while accounting for a potential
866 // integer underflow.
867 recovery_window_ = recovery_window_ >= bytes_lost
868 ? recovery_window_ - bytes_lost
869 : kMaxSegmentSize;
870
871 // In CONSERVATION mode, just subtracting losses is sufficient. In GROWTH,
872 // release additional |bytes_acked| to achieve a slow-start-like behavior.
873 if (recovery_state_ == GROWTH) {
874 recovery_window_ += bytes_acked;
875 }
876
877 // Sanity checks. Ensure that we always allow to send at least an MSS or
878 // |bytes_acked| in response, whichever is larger.
879 recovery_window_ = std::max(
880 recovery_window_, unacked_packets_->bytes_in_flight() + bytes_acked);
881 if (GetQuicReloadableFlag(quic_bbr_one_mss_conservation)) {
ianswettec9bf882019-11-11 08:21:00 -0800882 QUIC_RELOADABLE_FLAG_COUNT(quic_bbr_one_mss_conservation);
QUICHE teama6ef0a62019-03-07 20:34:33 -0500883 recovery_window_ =
884 std::max(recovery_window_,
885 unacked_packets_->bytes_in_flight() + kMaxSegmentSize);
886 }
887 recovery_window_ = std::max(min_congestion_window_, recovery_window_);
888}
889
vasilvvc48c8712019-03-11 13:38:16 -0700890std::string BbrSender::GetDebugState() const {
QUICHE teama6ef0a62019-03-07 20:34:33 -0500891 std::ostringstream stream;
892 stream << ExportDebugState();
893 return stream.str();
894}
895
896void BbrSender::OnApplicationLimited(QuicByteCount bytes_in_flight) {
897 if (bytes_in_flight >= GetCongestionWindow()) {
898 return;
899 }
900 if (flexible_app_limited_ && IsPipeSufficientlyFull()) {
901 return;
902 }
903
904 app_limited_since_last_probe_rtt_ = true;
905 sampler_.OnAppLimited();
906 QUIC_DVLOG(2) << "Becoming application limited. Last sent packet: "
907 << last_sent_packet_ << ", CWND: " << GetCongestionWindow();
908}
909
wub5cd49592019-11-25 15:17:13 -0800910void BbrSender::PopulateConnectionStats(QuicConnectionStats* stats) const {
911 stats->num_ack_aggregation_epochs = sampler_.num_ack_aggregation_epochs();
912}
913
QUICHE teama6ef0a62019-03-07 20:34:33 -0500914BbrSender::DebugState BbrSender::ExportDebugState() const {
915 return DebugState(*this);
916}
917
vasilvvc48c8712019-03-11 13:38:16 -0700918static std::string ModeToString(BbrSender::Mode mode) {
QUICHE teama6ef0a62019-03-07 20:34:33 -0500919 switch (mode) {
920 case BbrSender::STARTUP:
921 return "STARTUP";
922 case BbrSender::DRAIN:
923 return "DRAIN";
924 case BbrSender::PROBE_BW:
925 return "PROBE_BW";
926 case BbrSender::PROBE_RTT:
927 return "PROBE_RTT";
928 }
929 return "???";
930}
931
932std::ostream& operator<<(std::ostream& os, const BbrSender::Mode& mode) {
933 os << ModeToString(mode);
934 return os;
935}
936
937std::ostream& operator<<(std::ostream& os, const BbrSender::DebugState& state) {
938 os << "Mode: " << ModeToString(state.mode) << std::endl;
939 os << "Maximum bandwidth: " << state.max_bandwidth << std::endl;
940 os << "Round trip counter: " << state.round_trip_count << std::endl;
941 os << "Gain cycle index: " << static_cast<int>(state.gain_cycle_index)
942 << std::endl;
943 os << "Congestion window: " << state.congestion_window << " bytes"
944 << std::endl;
945
946 if (state.mode == BbrSender::STARTUP) {
947 os << "(startup) Bandwidth at last round: " << state.bandwidth_at_last_round
948 << std::endl;
949 os << "(startup) Rounds without gain: "
950 << state.rounds_without_bandwidth_gain << std::endl;
951 }
952
953 os << "Minimum RTT: " << state.min_rtt << std::endl;
954 os << "Minimum RTT timestamp: " << state.min_rtt_timestamp.ToDebuggingValue()
955 << std::endl;
956
957 os << "Last sample is app-limited: "
958 << (state.last_sample_is_app_limited ? "yes" : "no");
959
960 return os;
961}
962
963} // namespace quic