1 /* 2 * Copyright (c) 2018 The WebRTC project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11 // BBR (Bottleneck Bandwidth and RTT) congestion control algorithm. 12 // Based on the Quic BBR implementation in Chromium. 13 14 #ifndef MODULES_CONGESTION_CONTROLLER_BBR_BBR_NETWORK_CONTROLLER_H_ 15 #define MODULES_CONGESTION_CONTROLLER_BBR_BBR_NETWORK_CONTROLLER_H_ 16 17 #include <cstdint> 18 #include <memory> 19 #include <string> 20 #include <vector> 21 22 #include "absl/types/optional.h" 23 #include "api/transport/network_control.h" 24 #include "api/transport/network_types.h" 25 #include "modules/congestion_controller/bbr/bandwidth_sampler.h" 26 #include "modules/congestion_controller/bbr/loss_rate_filter.h" 27 #include "modules/congestion_controller/bbr/rtt_stats.h" 28 #include "modules/congestion_controller/bbr/windowed_filter.h" 29 #include "rtc_base/experiments/field_trial_parser.h" 30 #include "rtc_base/experiments/field_trial_units.h" 31 #include "rtc_base/random.h" 32 33 namespace webrtc { 34 namespace bbr { 35 36 typedef int64_t BbrRoundTripCount; 37 38 // BbrSender implements BBR congestion control algorithm. BBR aims to estimate 39 // the current available Bottleneck Bandwidth and RTT (hence the name), and 40 // regulates the pacing rate and the size of the congestion window based on 41 // those signals. 42 // 43 // BBR relies on pacing in order to function properly. Do not use BBR when 44 // pacing is disabled. 45 class BbrNetworkController : public NetworkControllerInterface { 46 public: 47 enum Mode { 48 // Startup phase of the connection. 49 STARTUP, 50 // After achieving the highest possible bandwidth during the startup, lower 51 // the pacing rate in order to drain the queue. 52 DRAIN, 53 // Cruising mode. 54 PROBE_BW, 55 // Temporarily slow down sending in order to empty the buffer and measure 56 // the real minimum RTT. 57 PROBE_RTT, 58 }; 59 60 // Indicates how the congestion control limits the amount of bytes in flight. 61 enum RecoveryState { 62 // Do not limit. 63 NOT_IN_RECOVERY = 0, 64 // Allow an extra outstanding byte for each byte acknowledged. 65 CONSERVATION = 1, 66 // Allow 1.5 extra outstanding bytes for each byte acknowledged. 67 MEDIUM_GROWTH = 2, 68 // Allow two extra outstanding bytes for each byte acknowledged (slow 69 // start). 70 GROWTH = 3 71 }; 72 struct BbrControllerConfig { 73 FieldTrialParameter<double> probe_bw_pacing_gain_offset; 74 FieldTrialParameter<double> encoder_rate_gain; 75 FieldTrialParameter<double> encoder_rate_gain_in_probe_rtt; 76 // RTT delta to determine if startup should be exited due to increased RTT. 77 FieldTrialParameter<TimeDelta> exit_startup_rtt_threshold; 78 79 FieldTrialParameter<DataSize> initial_congestion_window; 80 FieldTrialParameter<DataSize> min_congestion_window; 81 FieldTrialParameter<DataSize> max_congestion_window; 82 83 FieldTrialParameter<double> probe_rtt_congestion_window_gain; 84 FieldTrialParameter<bool> pacing_rate_as_target; 85 86 // Configurable in QUIC BBR: 87 FieldTrialParameter<bool> exit_startup_on_loss; 88 // The number of RTTs to stay in STARTUP mode. Defaults to 3. 89 FieldTrialParameter<int> num_startup_rtts; 90 // When true, recovery is rate based rather than congestion window based. 91 FieldTrialParameter<bool> rate_based_recovery; 92 FieldTrialParameter<double> max_aggregation_bytes_multiplier; 93 // When true, pace at 1.5x and disable packet conservation in STARTUP. 94 FieldTrialParameter<bool> slower_startup; 95 // When true, disables packet conservation in STARTUP. 96 FieldTrialParameter<bool> rate_based_startup; 97 // Used as the initial packet conservation mode when first entering 98 // recovery. 99 FieldTrialEnum<RecoveryState> initial_conservation_in_startup; 100 // If true, will not exit low gain mode until bytes_in_flight drops below 101 // BDP or it's time for high gain mode. 102 FieldTrialParameter<bool> fully_drain_queue; 103 104 FieldTrialParameter<double> max_ack_height_window_multiplier; 105 // If true, use a CWND of 0.75*BDP during probe_rtt instead of 4 packets. 106 FieldTrialParameter<bool> probe_rtt_based_on_bdp; 107 // If true, skip probe_rtt and update the timestamp of the existing min_rtt 108 // to now if min_rtt over the last cycle is within 12.5% of the current 109 // min_rtt. Even if the min_rtt is 12.5% too low, the 25% gain cycling and 110 // 2x CWND gain should overcome an overly small min_rtt. 111 FieldTrialParameter<bool> probe_rtt_skipped_if_similar_rtt; 112 // If true, disable PROBE_RTT entirely as long as the connection was 113 // recently app limited. 114 FieldTrialParameter<bool> probe_rtt_disabled_if_app_limited; 115 116 explicit BbrControllerConfig(std::string field_trial); 117 ~BbrControllerConfig(); 118 BbrControllerConfig(const BbrControllerConfig&); 119 static BbrControllerConfig FromTrial(); 120 }; 121 122 // Debug state can be exported in order to troubleshoot potential congestion 123 // control issues. 124 struct DebugState { 125 explicit DebugState(const BbrNetworkController& sender); 126 DebugState(const DebugState& state); 127 128 Mode mode; 129 DataRate max_bandwidth; 130 BbrRoundTripCount round_trip_count; 131 int gain_cycle_index; 132 DataSize congestion_window; 133 134 bool is_at_full_bandwidth; 135 DataRate bandwidth_at_last_round; 136 BbrRoundTripCount rounds_without_bandwidth_gain; 137 138 TimeDelta min_rtt; 139 Timestamp min_rtt_timestamp; 140 141 RecoveryState recovery_state; 142 DataSize recovery_window; 143 144 bool last_sample_is_app_limited; 145 int64_t end_of_app_limited_phase; 146 }; 147 148 explicit BbrNetworkController(NetworkControllerConfig config); 149 ~BbrNetworkController() override; 150 151 // NetworkControllerInterface 152 NetworkControlUpdate OnNetworkAvailability(NetworkAvailability msg) override; 153 NetworkControlUpdate OnNetworkRouteChange(NetworkRouteChange msg) override; 154 NetworkControlUpdate OnProcessInterval(ProcessInterval msg) override; 155 NetworkControlUpdate OnSentPacket(SentPacket msg) override; 156 NetworkControlUpdate OnStreamsConfig(StreamsConfig msg) override; 157 NetworkControlUpdate OnTargetRateConstraints( 158 TargetRateConstraints msg) override; 159 NetworkControlUpdate OnTransportPacketsFeedback( 160 TransportPacketsFeedback msg) override; 161 162 // Part of remote bitrate estimation api, not implemented for BBR 163 NetworkControlUpdate OnRemoteBitrateReport(RemoteBitrateReport msg) override; 164 NetworkControlUpdate OnRoundTripTimeUpdate(RoundTripTimeUpdate msg) override; 165 NetworkControlUpdate OnTransportLossReport(TransportLossReport msg) override; 166 NetworkControlUpdate OnReceivedPacket(ReceivedPacket msg) override; 167 NetworkControlUpdate OnNetworkStateEstimate( 168 NetworkStateEstimate msg) override; 169 170 NetworkControlUpdate CreateRateUpdate(Timestamp at_time) const; 171 172 private: 173 void Reset(); 174 bool InSlowStart() const; 175 bool InRecovery() const; 176 bool IsProbingForMoreBandwidth() const; 177 178 bool CanSend(DataSize bytes_in_flight); 179 DataRate PacingRate() const; 180 DataRate BandwidthEstimate() const; 181 DataSize GetCongestionWindow() const; 182 183 double GetPacingGain(int round_offset) const; 184 185 void OnApplicationLimited(DataSize bytes_in_flight); 186 // End implementation of SendAlgorithmInterface. 187 188 typedef WindowedFilter<DataRate, 189 MaxFilter<DataRate>, 190 BbrRoundTripCount, 191 BbrRoundTripCount> 192 MaxBandwidthFilter; 193 194 typedef WindowedFilter<TimeDelta, 195 MaxFilter<TimeDelta>, 196 BbrRoundTripCount, 197 BbrRoundTripCount> 198 MaxAckDelayFilter; 199 200 typedef WindowedFilter<DataSize, 201 MaxFilter<DataSize>, 202 BbrRoundTripCount, 203 BbrRoundTripCount> 204 MaxAckHeightFilter; 205 206 // Returns the current estimate of the RTT of the connection. Outside of the 207 // edge cases, this is minimum RTT. 208 TimeDelta GetMinRtt() const; 209 // Returns whether the connection has achieved full bandwidth required to exit 210 // the slow start. 211 bool IsAtFullBandwidth() const; 212 // Computes the target congestion window using the specified gain. 213 DataSize GetTargetCongestionWindow(double gain) const; 214 // The target congestion window during PROBE_RTT. 215 DataSize ProbeRttCongestionWindow() const; 216 // Returns true if the current min_rtt should be kept and we should not enter 217 // PROBE_RTT immediately. 218 bool ShouldExtendMinRttExpiry() const; 219 220 // Enters the STARTUP mode. 221 void EnterStartupMode(); 222 // Enters the PROBE_BW mode. 223 void EnterProbeBandwidthMode(Timestamp now); 224 225 // Discards the lost packets from BandwidthSampler state. 226 void DiscardLostPackets(const std::vector<PacketResult>& lost_packets); 227 // Updates the round-trip counter if a round-trip has passed. Returns true if 228 // the counter has been advanced. 229 // |last_acked_packet| is the sequence number of the last acked packet. 230 bool UpdateRoundTripCounter(int64_t last_acked_packet); 231 // Updates the current bandwidth and min_rtt estimate based on the samples for 232 // the received acknowledgements. Returns true if min_rtt has expired. 233 bool UpdateBandwidthAndMinRtt(Timestamp now, 234 const std::vector<PacketResult>& acked_packets); 235 // Updates the current gain used in PROBE_BW mode. 236 void UpdateGainCyclePhase(Timestamp now, 237 DataSize prior_in_flight, 238 bool has_losses); 239 // Tracks for how many round-trips the bandwidth has not increased 240 // significantly. 241 void CheckIfFullBandwidthReached(); 242 // Transitions from STARTUP to DRAIN and from DRAIN to PROBE_BW if 243 // appropriate. 244 void MaybeExitStartupOrDrain(const TransportPacketsFeedback&); 245 // Decides whether to enter or exit PROBE_RTT. 246 void MaybeEnterOrExitProbeRtt(const TransportPacketsFeedback& msg, 247 bool is_round_start, 248 bool min_rtt_expired); 249 // Determines whether BBR needs to enter, exit or advance state of the 250 // recovery. 251 void UpdateRecoveryState(int64_t last_acked_packet, 252 bool has_losses, 253 bool is_round_start); 254 255 // Updates the ack aggregation max filter in bytes. 256 void UpdateAckAggregationBytes(Timestamp ack_time, 257 DataSize newly_acked_bytes); 258 259 // Determines the appropriate pacing rate for the connection. 260 void CalculatePacingRate(); 261 // Determines the appropriate congestion window for the connection. 262 void CalculateCongestionWindow(DataSize bytes_acked); 263 // Determines the approriate window that constrains the 264 // in-flight during recovery. 265 void CalculateRecoveryWindow(DataSize bytes_acked, 266 DataSize bytes_lost, 267 DataSize bytes_in_flight); 268 269 BbrControllerConfig config_; 270 271 RttStats rtt_stats_; 272 webrtc::Random random_; 273 LossRateFilter loss_rate_; 274 275 absl::optional<TargetRateConstraints> constraints_; 276 277 Mode mode_; 278 279 // Bandwidth sampler provides BBR with the bandwidth measurements at 280 // individual points. 281 std::unique_ptr<BandwidthSampler> sampler_; 282 283 // The number of the round trips that have occurred during the connection. 284 BbrRoundTripCount round_trip_count_ = 0; 285 286 // The packet number of the most recently sent packet. 287 int64_t last_sent_packet_; 288 // Acknowledgement of any packet after |current_round_trip_end_| will cause 289 // the round trip counter to advance. 290 int64_t current_round_trip_end_; 291 292 // The filter that tracks the maximum bandwidth over the multiple recent 293 // round-trips. 294 MaxBandwidthFilter max_bandwidth_; 295 296 DataRate default_bandwidth_; 297 298 // Tracks the maximum number of bytes acked faster than the sending rate. 299 MaxAckHeightFilter max_ack_height_; 300 301 // The time this aggregation started and the number of bytes acked during it. 302 absl::optional<Timestamp> aggregation_epoch_start_time_; 303 DataSize aggregation_epoch_bytes_; 304 305 // The number of bytes acknowledged since the last time bytes in flight 306 // dropped below the target window. 307 DataSize bytes_acked_since_queue_drained_; 308 309 // The muliplier for calculating the max amount of extra CWND to add to 310 // compensate for ack aggregation. 311 double max_aggregation_bytes_multiplier_; 312 313 // Minimum RTT estimate. Automatically expires within 10 seconds (and 314 // triggers PROBE_RTT mode) if no new value is sampled during that period. 315 TimeDelta min_rtt_; 316 TimeDelta last_rtt_; 317 // The time at which the current value of |min_rtt_| was assigned. 318 Timestamp min_rtt_timestamp_; 319 320 // The maximum allowed number of bytes in flight. 321 DataSize congestion_window_; 322 323 // The initial value of the |congestion_window_|. 324 DataSize initial_congestion_window_; 325 326 // The smallest value the |congestion_window_| can achieve. 327 DataSize min_congestion_window_; 328 329 // The largest value the |congestion_window_| can achieve. 330 DataSize max_congestion_window_; 331 332 // The current pacing rate of the connection. 333 DataRate pacing_rate_; 334 335 // The gain currently applied to the pacing rate. 336 double pacing_gain_; 337 // The gain currently applied to the congestion window. 338 double congestion_window_gain_; 339 340 // The gain used for the congestion window during PROBE_BW. Latched from 341 // quic_bbr_cwnd_gain flag. 342 const double congestion_window_gain_constant_; 343 // The coefficient by which mean RTT variance is added to the congestion 344 // window. Latched from quic_bbr_rtt_variation_weight flag. 345 const double rtt_variance_weight_; 346 347 // Number of round-trips in PROBE_BW mode, used for determining the current 348 // pacing gain cycle. 349 int cycle_current_offset_; 350 // The time at which the last pacing gain cycle was started. 351 Timestamp last_cycle_start_; 352 353 // Indicates whether the connection has reached the full bandwidth mode. 354 bool is_at_full_bandwidth_; 355 // Number of rounds during which there was no significant bandwidth increase. 356 BbrRoundTripCount rounds_without_bandwidth_gain_; 357 // The bandwidth compared to which the increase is measured. 358 DataRate bandwidth_at_last_round_; 359 360 // Set to true upon exiting quiescence. 361 bool exiting_quiescence_; 362 363 // Time at which PROBE_RTT has to be exited. Setting it to zero indicates 364 // that the time is yet unknown as the number of packets in flight has not 365 // reached the required value. 366 absl::optional<Timestamp> exit_probe_rtt_at_; 367 // Indicates whether a round-trip has passed since PROBE_RTT became active. 368 bool probe_rtt_round_passed_; 369 370 // Indicates whether the most recent bandwidth sample was marked as 371 // app-limited. 372 bool last_sample_is_app_limited_; 373 374 // Current state of recovery. 375 RecoveryState recovery_state_; 376 // Receiving acknowledgement of a packet after |end_recovery_at_| will cause 377 // BBR to exit the recovery mode. A set value indicates at least one 378 // loss has been detected, so it must not be reset. 379 absl::optional<int64_t> end_recovery_at_; 380 // A window used to limit the number of bytes in flight during loss recovery. 381 DataSize recovery_window_; 382 383 bool app_limited_since_last_probe_rtt_; 384 TimeDelta min_rtt_since_last_probe_rtt_; 385 386 RTC_DISALLOW_COPY_AND_ASSIGN(BbrNetworkController); 387 }; 388 389 // Used in log output 390 std::ostream& operator<<( // no-presubmit-check TODO(webrtc:8982) 391 std::ostream& os, // no-presubmit-check TODO(webrtc:8982) 392 const BbrNetworkController::Mode& mode); 393 394 } // namespace bbr 395 } // namespace webrtc 396 397 #endif // MODULES_CONGESTION_CONTROLLER_BBR_BBR_NETWORK_CONTROLLER_H_ 398