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 // BBR (Bottleneck Bandwidth and RTT) congestion control algorithm. 6 7 #ifndef QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR_SENDER_H_ 8 #define QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR_SENDER_H_ 9 10 #include <cstdint> 11 #include <ostream> 12 #include <string> 13 14 #include "net/third_party/quiche/src/quic/core/congestion_control/bandwidth_sampler.h" 15 #include "net/third_party/quiche/src/quic/core/congestion_control/send_algorithm_interface.h" 16 #include "net/third_party/quiche/src/quic/core/congestion_control/windowed_filter.h" 17 #include "net/third_party/quiche/src/quic/core/crypto/quic_random.h" 18 #include "net/third_party/quiche/src/quic/core/quic_bandwidth.h" 19 #include "net/third_party/quiche/src/quic/core/quic_packet_number.h" 20 #include "net/third_party/quiche/src/quic/core/quic_packets.h" 21 #include "net/third_party/quiche/src/quic/core/quic_time.h" 22 #include "net/third_party/quiche/src/quic/core/quic_unacked_packet_map.h" 23 #include "net/third_party/quiche/src/quic/platform/api/quic_export.h" 24 #include "net/third_party/quiche/src/quic/platform/api/quic_flags.h" 25 26 namespace quic { 27 28 class RttStats; 29 30 // BbrSender implements BBR congestion control algorithm. BBR aims to estimate 31 // the current available Bottleneck Bandwidth and RTT (hence the name), and 32 // regulates the pacing rate and the size of the congestion window based on 33 // those signals. 34 // 35 // BBR relies on pacing in order to function properly. Do not use BBR when 36 // pacing is disabled. 37 // 38 // TODO(vasilvv): implement traffic policer (long-term sampling) mode. 39 class QUIC_EXPORT_PRIVATE BbrSender : public SendAlgorithmInterface { 40 public: 41 enum Mode { 42 // Startup phase of the connection. 43 STARTUP, 44 // After achieving the highest possible bandwidth during the startup, lower 45 // the pacing rate in order to drain the queue. 46 DRAIN, 47 // Cruising mode. 48 PROBE_BW, 49 // Temporarily slow down sending in order to empty the buffer and measure 50 // the real minimum RTT. 51 PROBE_RTT, 52 }; 53 54 // Indicates how the congestion control limits the amount of bytes in flight. 55 enum RecoveryState { 56 // Do not limit. 57 NOT_IN_RECOVERY, 58 // Allow an extra outstanding byte for each byte acknowledged. 59 CONSERVATION, 60 // Allow two extra outstanding bytes for each byte acknowledged (slow 61 // start). 62 GROWTH 63 }; 64 65 // Debug state can be exported in order to troubleshoot potential congestion 66 // control issues. 67 struct QUIC_EXPORT_PRIVATE DebugState { 68 explicit DebugState(const BbrSender& sender); 69 DebugState(const DebugState& state); 70 71 Mode mode; 72 QuicBandwidth max_bandwidth; 73 QuicRoundTripCount round_trip_count; 74 int gain_cycle_index; 75 QuicByteCount congestion_window; 76 77 bool is_at_full_bandwidth; 78 QuicBandwidth bandwidth_at_last_round; 79 QuicRoundTripCount rounds_without_bandwidth_gain; 80 81 QuicTime::Delta min_rtt; 82 QuicTime min_rtt_timestamp; 83 84 RecoveryState recovery_state; 85 QuicByteCount recovery_window; 86 87 bool last_sample_is_app_limited; 88 QuicPacketNumber end_of_app_limited_phase; 89 }; 90 91 BbrSender(QuicTime now, 92 const RttStats* rtt_stats, 93 const QuicUnackedPacketMap* unacked_packets, 94 QuicPacketCount initial_tcp_congestion_window, 95 QuicPacketCount max_tcp_congestion_window, 96 QuicRandom* random, 97 QuicConnectionStats* stats); 98 BbrSender(const BbrSender&) = delete; 99 BbrSender& operator=(const BbrSender&) = delete; 100 ~BbrSender() override; 101 102 // Start implementation of SendAlgorithmInterface. 103 bool InSlowStart() const override; 104 bool InRecovery() const override; 105 bool ShouldSendProbingPacket() const override; 106 107 void SetFromConfig(const QuicConfig& config, 108 Perspective perspective) override; 109 void ApplyConnectionOptions(const QuicTagVector& connection_options) override; 110 111 void AdjustNetworkParameters(const NetworkParams& params) override; 112 void SetInitialCongestionWindowInPackets( 113 QuicPacketCount congestion_window) override; 114 void OnCongestionEvent(bool rtt_updated, 115 QuicByteCount prior_in_flight, 116 QuicTime event_time, 117 const AckedPacketVector& acked_packets, 118 const LostPacketVector& lost_packets) override; 119 void OnPacketSent(QuicTime sent_time, 120 QuicByteCount bytes_in_flight, 121 QuicPacketNumber packet_number, 122 QuicByteCount bytes, 123 HasRetransmittableData is_retransmittable) override; 124 void OnPacketNeutered(QuicPacketNumber packet_number) override; OnRetransmissionTimeout(bool)125 void OnRetransmissionTimeout(bool /*packets_retransmitted*/) override {} OnConnectionMigration()126 void OnConnectionMigration() override {} 127 bool CanSend(QuicByteCount bytes_in_flight) override; 128 QuicBandwidth PacingRate(QuicByteCount bytes_in_flight) const override; 129 QuicBandwidth BandwidthEstimate() const override; 130 QuicByteCount GetCongestionWindow() const override; 131 QuicByteCount GetSlowStartThreshold() const override; 132 CongestionControlType GetCongestionControlType() const override; 133 std::string GetDebugState() const override; 134 void OnApplicationLimited(QuicByteCount bytes_in_flight) override; 135 void PopulateConnectionStats(QuicConnectionStats* stats) const override; 136 // End implementation of SendAlgorithmInterface. 137 138 // Gets the number of RTTs BBR remains in STARTUP phase. num_startup_rtts()139 QuicRoundTripCount num_startup_rtts() const { return num_startup_rtts_; } has_non_app_limited_sample()140 bool has_non_app_limited_sample() const { 141 return has_non_app_limited_sample_; 142 } 143 144 // Sets the pacing gain used in STARTUP. Must be greater than 1. set_high_gain(float high_gain)145 void set_high_gain(float high_gain) { 146 DCHECK_LT(1.0f, high_gain); 147 high_gain_ = high_gain; 148 if (mode_ == STARTUP) { 149 pacing_gain_ = high_gain; 150 } 151 } 152 153 // Sets the CWND gain used in STARTUP. Must be greater than 1. set_high_cwnd_gain(float high_cwnd_gain)154 void set_high_cwnd_gain(float high_cwnd_gain) { 155 DCHECK_LT(1.0f, high_cwnd_gain); 156 high_cwnd_gain_ = high_cwnd_gain; 157 if (mode_ == STARTUP) { 158 congestion_window_gain_ = high_cwnd_gain; 159 } 160 } 161 162 // Sets the gain used in DRAIN. Must be less than 1. set_drain_gain(float drain_gain)163 void set_drain_gain(float drain_gain) { 164 DCHECK_GT(1.0f, drain_gain); 165 drain_gain_ = drain_gain; 166 } 167 168 // Returns the current estimate of the RTT of the connection. Outside of the 169 // edge cases, this is minimum RTT. 170 QuicTime::Delta GetMinRtt() const; 171 172 DebugState ExportDebugState() const; 173 174 private: 175 // For switching send algorithm mid connection. 176 friend class Bbr2Sender; 177 178 using MaxBandwidthFilter = WindowedFilter<QuicBandwidth, 179 MaxFilter<QuicBandwidth>, 180 QuicRoundTripCount, 181 QuicRoundTripCount>; 182 183 using MaxAckHeightFilter = WindowedFilter<QuicByteCount, 184 MaxFilter<QuicByteCount>, 185 QuicRoundTripCount, 186 QuicRoundTripCount>; 187 188 // Returns whether the connection has achieved full bandwidth required to exit 189 // the slow start. 190 bool IsAtFullBandwidth() const; 191 // Computes the target congestion window using the specified gain. 192 QuicByteCount GetTargetCongestionWindow(float gain) const; 193 // The target congestion window during PROBE_RTT. 194 QuicByteCount ProbeRttCongestionWindow() const; 195 // Returns true if the current min_rtt should be kept and we should not enter 196 // PROBE_RTT immediately. 197 bool ShouldExtendMinRttExpiry() const; 198 bool MaybeUpdateMinRtt(QuicTime now, QuicTime::Delta sample_min_rtt); 199 200 // Enters the STARTUP mode. 201 void EnterStartupMode(QuicTime now); 202 // Enters the PROBE_BW mode. 203 void EnterProbeBandwidthMode(QuicTime now); 204 205 // Updates the round-trip counter if a round-trip has passed. Returns true if 206 // the counter has been advanced. 207 bool UpdateRoundTripCounter(QuicPacketNumber last_acked_packet); 208 209 // Updates the current gain used in PROBE_BW mode. 210 void UpdateGainCyclePhase(QuicTime now, 211 QuicByteCount prior_in_flight, 212 bool has_losses); 213 // Tracks for how many round-trips the bandwidth has not increased 214 // significantly. 215 void CheckIfFullBandwidthReached(const SendTimeState& last_packet_send_state); 216 // Transitions from STARTUP to DRAIN and from DRAIN to PROBE_BW if 217 // appropriate. 218 void MaybeExitStartupOrDrain(QuicTime now); 219 // Decides whether to enter or exit PROBE_RTT. 220 void MaybeEnterOrExitProbeRtt(QuicTime now, 221 bool is_round_start, 222 bool min_rtt_expired); 223 // Determines whether BBR needs to enter, exit or advance state of the 224 // recovery. 225 void UpdateRecoveryState(QuicPacketNumber last_acked_packet, 226 bool has_losses, 227 bool is_round_start); 228 229 // Updates the ack aggregation max filter in bytes. 230 // Returns the most recent addition to the filter, or |newly_acked_bytes| if 231 // nothing was fed in to the filter. 232 QuicByteCount UpdateAckAggregationBytes(QuicTime ack_time, 233 QuicByteCount newly_acked_bytes); 234 235 // Determines the appropriate pacing rate for the connection. 236 void CalculatePacingRate(QuicByteCount bytes_lost); 237 // Determines the appropriate congestion window for the connection. 238 void CalculateCongestionWindow(QuicByteCount bytes_acked, 239 QuicByteCount excess_acked); 240 // Determines the appropriate window that constrains the in-flight during 241 // recovery. 242 void CalculateRecoveryWindow(QuicByteCount bytes_acked, 243 QuicByteCount bytes_lost); 244 245 // Called right before exiting STARTUP. 246 void OnExitStartup(QuicTime now); 247 248 // Return whether we should exit STARTUP due to excessive loss. 249 bool ShouldExitStartupDueToLoss( 250 const SendTimeState& last_packet_send_state) const; 251 252 const RttStats* rtt_stats_; 253 const QuicUnackedPacketMap* unacked_packets_; 254 QuicRandom* random_; 255 QuicConnectionStats* stats_; 256 257 Mode mode_; 258 259 // Bandwidth sampler provides BBR with the bandwidth measurements at 260 // individual points. 261 BandwidthSampler sampler_; 262 263 // The number of the round trips that have occurred during the connection. 264 QuicRoundTripCount round_trip_count_; 265 266 // The packet number of the most recently sent packet. 267 QuicPacketNumber last_sent_packet_; 268 // Acknowledgement of any packet after |current_round_trip_end_| will cause 269 // the round trip counter to advance. 270 QuicPacketNumber current_round_trip_end_; 271 272 // Number of congestion events with some losses, in the current round. 273 int64_t num_loss_events_in_round_; 274 275 // Number of total bytes lost in the current round. 276 QuicByteCount bytes_lost_in_round_; 277 278 // The filter that tracks the maximum bandwidth over the multiple recent 279 // round-trips. 280 MaxBandwidthFilter max_bandwidth_; 281 282 // Minimum RTT estimate. Automatically expires within 10 seconds (and 283 // triggers PROBE_RTT mode) if no new value is sampled during that period. 284 QuicTime::Delta min_rtt_; 285 // The time at which the current value of |min_rtt_| was assigned. 286 QuicTime min_rtt_timestamp_; 287 288 // The maximum allowed number of bytes in flight. 289 QuicByteCount congestion_window_; 290 291 // The initial value of the |congestion_window_|. 292 QuicByteCount initial_congestion_window_; 293 294 // The largest value the |congestion_window_| can achieve. 295 QuicByteCount max_congestion_window_; 296 297 // The smallest value the |congestion_window_| can achieve. 298 QuicByteCount min_congestion_window_; 299 300 // The pacing gain applied during the STARTUP phase. 301 float high_gain_; 302 303 // The CWND gain applied during the STARTUP phase. 304 float high_cwnd_gain_; 305 306 // The pacing gain applied during the DRAIN phase. 307 float drain_gain_; 308 309 // The current pacing rate of the connection. 310 QuicBandwidth pacing_rate_; 311 312 // The gain currently applied to the pacing rate. 313 float pacing_gain_; 314 // The gain currently applied to the congestion window. 315 float congestion_window_gain_; 316 317 // The gain used for the congestion window during PROBE_BW. Latched from 318 // quic_bbr_cwnd_gain flag. 319 const float congestion_window_gain_constant_; 320 // The number of RTTs to stay in STARTUP mode. Defaults to 3. 321 QuicRoundTripCount num_startup_rtts_; 322 323 // Number of round-trips in PROBE_BW mode, used for determining the current 324 // pacing gain cycle. 325 int cycle_current_offset_; 326 // The time at which the last pacing gain cycle was started. 327 QuicTime last_cycle_start_; 328 329 // Indicates whether the connection has reached the full bandwidth mode. 330 bool is_at_full_bandwidth_; 331 // Number of rounds during which there was no significant bandwidth increase. 332 QuicRoundTripCount rounds_without_bandwidth_gain_; 333 // The bandwidth compared to which the increase is measured. 334 QuicBandwidth bandwidth_at_last_round_; 335 336 // Set to true upon exiting quiescence. 337 bool exiting_quiescence_; 338 339 // Time at which PROBE_RTT has to be exited. Setting it to zero indicates 340 // that the time is yet unknown as the number of packets in flight has not 341 // reached the required value. 342 QuicTime exit_probe_rtt_at_; 343 // Indicates whether a round-trip has passed since PROBE_RTT became active. 344 bool probe_rtt_round_passed_; 345 346 // Indicates whether the most recent bandwidth sample was marked as 347 // app-limited. 348 bool last_sample_is_app_limited_; 349 // Indicates whether any non app-limited samples have been recorded. 350 bool has_non_app_limited_sample_; 351 352 // Current state of recovery. 353 RecoveryState recovery_state_; 354 // Receiving acknowledgement of a packet after |end_recovery_at_| will cause 355 // BBR to exit the recovery mode. A value above zero indicates at least one 356 // loss has been detected, so it must not be set back to zero. 357 QuicPacketNumber end_recovery_at_; 358 // A window used to limit the number of bytes in flight during loss recovery. 359 QuicByteCount recovery_window_; 360 // If true, consider all samples in recovery app-limited. 361 bool is_app_limited_recovery_; 362 363 // When true, pace at 1.5x and disable packet conservation in STARTUP. 364 bool slower_startup_; 365 // When true, disables packet conservation in STARTUP. 366 bool rate_based_startup_; 367 368 // When true, add the most recent ack aggregation measurement during STARTUP. 369 bool enable_ack_aggregation_during_startup_; 370 // When true, expire the windowed ack aggregation values in STARTUP when 371 // bandwidth increases more than 25%. 372 bool expire_ack_aggregation_in_startup_; 373 374 // If true, will not exit low gain mode until bytes_in_flight drops below BDP 375 // or it's time for high gain mode. 376 bool drain_to_target_; 377 378 // If true, slow down pacing rate in STARTUP when overshooting is detected. 379 bool detect_overshooting_; 380 // Bytes lost while detect_overshooting_ is true. 381 QuicByteCount bytes_lost_while_detecting_overshooting_; 382 // Slow down pacing rate if 383 // bytes_lost_while_detecting_overshooting_ * 384 // bytes_lost_multiplier_while_detecting_overshooting_ > IW. 385 uint8_t bytes_lost_multiplier_while_detecting_overshooting_; 386 // When overshooting is detected, do not drop pacing_rate_ below this value / 387 // min_rtt. 388 QuicByteCount cwnd_to_calculate_min_pacing_rate_; 389 390 // Max congestion window when adjusting network parameters. 391 QuicByteCount max_congestion_window_with_network_parameters_adjusted_; 392 }; 393 394 QUIC_EXPORT_PRIVATE std::ostream& operator<<(std::ostream& os, 395 const BbrSender::Mode& mode); 396 QUIC_EXPORT_PRIVATE std::ostream& operator<<( 397 std::ostream& os, 398 const BbrSender::DebugState& state); 399 400 } // namespace quic 401 402 #endif // QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR_SENDER_H_ 403