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