blob: ea6410ff753c75d4f0e7cd7b0e5c4afd49de0cbd [file] [log] [blame]
// Copyright 2016 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
// BBR (Bottleneck Bandwidth and RTT) congestion control algorithm.
#include <cstdint>
#include <ostream>
#include <string>
#include "quic/core/congestion_control/bandwidth_sampler.h"
#include "quic/core/congestion_control/send_algorithm_interface.h"
#include "quic/core/congestion_control/windowed_filter.h"
#include "quic/core/crypto/quic_random.h"
#include "quic/core/quic_bandwidth.h"
#include "quic/core/quic_packet_number.h"
#include "quic/core/quic_packets.h"
#include "quic/core/quic_time.h"
#include "quic/core/quic_unacked_packet_map.h"
#include "quic/platform/api/quic_export.h"
#include "quic/platform/api/quic_flags.h"
namespace quic {
class RttStats;
// BbrSender implements BBR congestion control algorithm. BBR aims to estimate
// the current available Bottleneck Bandwidth and RTT (hence the name), and
// regulates the pacing rate and the size of the congestion window based on
// those signals.
// BBR relies on pacing in order to function properly. Do not use BBR when
// pacing is disabled.
// TODO(vasilvv): implement traffic policer (long-term sampling) mode.
class QUIC_EXPORT_PRIVATE BbrSender : public SendAlgorithmInterface {
enum Mode {
// Startup phase of the connection.
// After achieving the highest possible bandwidth during the startup, lower
// the pacing rate in order to drain the queue.
// Cruising mode.
// Temporarily slow down sending in order to empty the buffer and measure
// the real minimum RTT.
// Indicates how the congestion control limits the amount of bytes in flight.
enum RecoveryState {
// Do not limit.
// Allow an extra outstanding byte for each byte acknowledged.
// Allow two extra outstanding bytes for each byte acknowledged (slow
// start).
// Debug state can be exported in order to troubleshoot potential congestion
// control issues.
struct QUIC_EXPORT_PRIVATE DebugState {
explicit DebugState(const BbrSender& sender);
DebugState(const DebugState& state);
Mode mode;
QuicBandwidth max_bandwidth;
QuicRoundTripCount round_trip_count;
int gain_cycle_index;
QuicByteCount congestion_window;
bool is_at_full_bandwidth;
QuicBandwidth bandwidth_at_last_round;
QuicRoundTripCount rounds_without_bandwidth_gain;
QuicTime::Delta min_rtt;
QuicTime min_rtt_timestamp;
RecoveryState recovery_state;
QuicByteCount recovery_window;
bool last_sample_is_app_limited;
QuicPacketNumber end_of_app_limited_phase;
BbrSender(QuicTime now,
const RttStats* rtt_stats,
const QuicUnackedPacketMap* unacked_packets,
QuicPacketCount initial_tcp_congestion_window,
QuicPacketCount max_tcp_congestion_window,
QuicRandom* random,
QuicConnectionStats* stats);
BbrSender(const BbrSender&) = delete;
BbrSender& operator=(const BbrSender&) = delete;
~BbrSender() override;
// Start implementation of SendAlgorithmInterface.
bool InSlowStart() const override;
bool InRecovery() const override;
bool ShouldSendProbingPacket() const override;
void SetFromConfig(const QuicConfig& config,
Perspective perspective) override;
void ApplyConnectionOptions(const QuicTagVector& connection_options) override;
void AdjustNetworkParameters(const NetworkParams& params) override;
void SetInitialCongestionWindowInPackets(
QuicPacketCount congestion_window) override;
void OnCongestionEvent(bool rtt_updated,
QuicByteCount prior_in_flight,
QuicTime event_time,
const AckedPacketVector& acked_packets,
const LostPacketVector& lost_packets) override;
void OnPacketSent(QuicTime sent_time,
QuicByteCount bytes_in_flight,
QuicPacketNumber packet_number,
QuicByteCount bytes,
HasRetransmittableData is_retransmittable) override;
void OnPacketNeutered(QuicPacketNumber packet_number) override;
void OnRetransmissionTimeout(bool /*packets_retransmitted*/) override {}
void OnConnectionMigration() override {}
bool CanSend(QuicByteCount bytes_in_flight) override;
QuicBandwidth PacingRate(QuicByteCount bytes_in_flight) const override;
QuicBandwidth BandwidthEstimate() const override;
QuicByteCount GetCongestionWindow() const override;
QuicByteCount GetSlowStartThreshold() const override;
CongestionControlType GetCongestionControlType() const override;
std::string GetDebugState() const override;
void OnApplicationLimited(QuicByteCount bytes_in_flight) override;
void PopulateConnectionStats(QuicConnectionStats* stats) const override;
// End implementation of SendAlgorithmInterface.
// Gets the number of RTTs BBR remains in STARTUP phase.
QuicRoundTripCount num_startup_rtts() const { return num_startup_rtts_; }
bool has_non_app_limited_sample() const {
return has_non_app_limited_sample_;
// Sets the pacing gain used in STARTUP. Must be greater than 1.
void set_high_gain(float high_gain) {
QUICHE_DCHECK_LT(1.0f, high_gain);
high_gain_ = high_gain;
if (mode_ == STARTUP) {
pacing_gain_ = high_gain;
// Sets the CWND gain used in STARTUP. Must be greater than 1.
void set_high_cwnd_gain(float high_cwnd_gain) {
QUICHE_DCHECK_LT(1.0f, high_cwnd_gain);
high_cwnd_gain_ = high_cwnd_gain;
if (mode_ == STARTUP) {
congestion_window_gain_ = high_cwnd_gain;
// Sets the gain used in DRAIN. Must be less than 1.
void set_drain_gain(float drain_gain) {
QUICHE_DCHECK_GT(1.0f, drain_gain);
drain_gain_ = drain_gain;
// Returns the current estimate of the RTT of the connection. Outside of the
// edge cases, this is minimum RTT.
QuicTime::Delta GetMinRtt() const;
DebugState ExportDebugState() const;
// For switching send algorithm mid connection.
friend class Bbr2Sender;
using MaxBandwidthFilter = WindowedFilter<QuicBandwidth,
using MaxAckHeightFilter = WindowedFilter<QuicByteCount,
// Computes the target congestion window using the specified gain.
QuicByteCount GetTargetCongestionWindow(float gain) const;
// The target congestion window during PROBE_RTT.
QuicByteCount ProbeRttCongestionWindow() const;
bool MaybeUpdateMinRtt(QuicTime now, QuicTime::Delta sample_min_rtt);
// Enters the STARTUP mode.
void EnterStartupMode(QuicTime now);
// Enters the PROBE_BW mode.
void EnterProbeBandwidthMode(QuicTime now);
// Updates the round-trip counter if a round-trip has passed. Returns true if
// the counter has been advanced.
bool UpdateRoundTripCounter(QuicPacketNumber last_acked_packet);
// Updates the current gain used in PROBE_BW mode.
void UpdateGainCyclePhase(QuicTime now,
QuicByteCount prior_in_flight,
bool has_losses);
// Tracks for how many round-trips the bandwidth has not increased
// significantly.
void CheckIfFullBandwidthReached(const SendTimeState& last_packet_send_state);
// Transitions from STARTUP to DRAIN and from DRAIN to PROBE_BW if
// appropriate.
void MaybeExitStartupOrDrain(QuicTime now);
// Decides whether to enter or exit PROBE_RTT.
void MaybeEnterOrExitProbeRtt(QuicTime now,
bool is_round_start,
bool min_rtt_expired);
// Determines whether BBR needs to enter, exit or advance state of the
// recovery.
void UpdateRecoveryState(QuicPacketNumber last_acked_packet,
bool has_losses,
bool is_round_start);
// Updates the ack aggregation max filter in bytes.
// Returns the most recent addition to the filter, or |newly_acked_bytes| if
// nothing was fed in to the filter.
QuicByteCount UpdateAckAggregationBytes(QuicTime ack_time,
QuicByteCount newly_acked_bytes);
// Determines the appropriate pacing rate for the connection.
void CalculatePacingRate(QuicByteCount bytes_lost);
// Determines the appropriate congestion window for the connection.
void CalculateCongestionWindow(QuicByteCount bytes_acked,
QuicByteCount excess_acked);
// Determines the appropriate window that constrains the in-flight during
// recovery.
void CalculateRecoveryWindow(QuicByteCount bytes_acked,
QuicByteCount bytes_lost);
// Called right before exiting STARTUP.
void OnExitStartup(QuicTime now);
// Return whether we should exit STARTUP due to excessive loss.
bool ShouldExitStartupDueToLoss(
const SendTimeState& last_packet_send_state) const;
const RttStats* rtt_stats_;
const QuicUnackedPacketMap* unacked_packets_;
QuicRandom* random_;
QuicConnectionStats* stats_;
Mode mode_;
// Bandwidth sampler provides BBR with the bandwidth measurements at
// individual points.
BandwidthSampler sampler_;
// The number of the round trips that have occurred during the connection.
QuicRoundTripCount round_trip_count_;
// The packet number of the most recently sent packet.
QuicPacketNumber last_sent_packet_;
// Acknowledgement of any packet after |current_round_trip_end_| will cause
// the round trip counter to advance.
QuicPacketNumber current_round_trip_end_;
// Number of congestion events with some losses, in the current round.
int64_t num_loss_events_in_round_;
// Number of total bytes lost in the current round.
QuicByteCount bytes_lost_in_round_;
// The filter that tracks the maximum bandwidth over the multiple recent
// round-trips.
MaxBandwidthFilter max_bandwidth_;
// Minimum RTT estimate. Automatically expires within 10 seconds (and
// triggers PROBE_RTT mode) if no new value is sampled during that period.
QuicTime::Delta min_rtt_;
// The time at which the current value of |min_rtt_| was assigned.
QuicTime min_rtt_timestamp_;
// The maximum allowed number of bytes in flight.
QuicByteCount congestion_window_;
// The initial value of the |congestion_window_|.
QuicByteCount initial_congestion_window_;
// The largest value the |congestion_window_| can achieve.
QuicByteCount max_congestion_window_;
// The smallest value the |congestion_window_| can achieve.
QuicByteCount min_congestion_window_;
// The pacing gain applied during the STARTUP phase.
float high_gain_;
// The CWND gain applied during the STARTUP phase.
float high_cwnd_gain_;
// The pacing gain applied during the DRAIN phase.
float drain_gain_;
// The current pacing rate of the connection.
QuicBandwidth pacing_rate_;
// The gain currently applied to the pacing rate.
float pacing_gain_;
// The gain currently applied to the congestion window.
float congestion_window_gain_;
// The gain used for the congestion window during PROBE_BW. Latched from
// quic_bbr_cwnd_gain flag.
const float congestion_window_gain_constant_;
// The number of RTTs to stay in STARTUP mode. Defaults to 3.
QuicRoundTripCount num_startup_rtts_;
// Number of round-trips in PROBE_BW mode, used for determining the current
// pacing gain cycle.
int cycle_current_offset_;
// The time at which the last pacing gain cycle was started.
QuicTime last_cycle_start_;
// Indicates whether the connection has reached the full bandwidth mode.
bool is_at_full_bandwidth_;
// Number of rounds during which there was no significant bandwidth increase.
QuicRoundTripCount rounds_without_bandwidth_gain_;
// The bandwidth compared to which the increase is measured.
QuicBandwidth bandwidth_at_last_round_;
// Set to true upon exiting quiescence.
bool exiting_quiescence_;
// Time at which PROBE_RTT has to be exited. Setting it to zero indicates
// that the time is yet unknown as the number of packets in flight has not
// reached the required value.
QuicTime exit_probe_rtt_at_;
// Indicates whether a round-trip has passed since PROBE_RTT became active.
bool probe_rtt_round_passed_;
// Indicates whether the most recent bandwidth sample was marked as
// app-limited.
bool last_sample_is_app_limited_;
// Indicates whether any non app-limited samples have been recorded.
bool has_non_app_limited_sample_;
// Current state of recovery.
RecoveryState recovery_state_;
// Receiving acknowledgement of a packet after |end_recovery_at_| will cause
// BBR to exit the recovery mode. A value above zero indicates at least one
// loss has been detected, so it must not be set back to zero.
QuicPacketNumber end_recovery_at_;
// A window used to limit the number of bytes in flight during loss recovery.
QuicByteCount recovery_window_;
// If true, consider all samples in recovery app-limited.
bool is_app_limited_recovery_;
// When true, pace at 1.5x and disable packet conservation in STARTUP.
bool slower_startup_;
// When true, disables packet conservation in STARTUP.
bool rate_based_startup_;
// When true, add the most recent ack aggregation measurement during STARTUP.
bool enable_ack_aggregation_during_startup_;
// When true, expire the windowed ack aggregation values in STARTUP when
// bandwidth increases more than 25%.
bool expire_ack_aggregation_in_startup_;
// If true, will not exit low gain mode until bytes_in_flight drops below BDP
// or it's time for high gain mode.
bool drain_to_target_;
// If true, slow down pacing rate in STARTUP when overshooting is detected.
bool detect_overshooting_;
// Bytes lost while detect_overshooting_ is true.
QuicByteCount bytes_lost_while_detecting_overshooting_;
// Slow down pacing rate if
// bytes_lost_while_detecting_overshooting_ *
// bytes_lost_multiplier_while_detecting_overshooting_ > IW.
uint8_t bytes_lost_multiplier_while_detecting_overshooting_;
// When overshooting is detected, do not drop pacing_rate_ below this value /
// min_rtt.
QuicByteCount cwnd_to_calculate_min_pacing_rate_;
// Max congestion window when adjusting network parameters.
QuicByteCount max_congestion_window_with_network_parameters_adjusted_;
QUIC_EXPORT_PRIVATE std::ostream& operator<<(std::ostream& os,
const BbrSender::Mode& mode);
QUIC_EXPORT_PRIVATE std::ostream& operator<<(
std::ostream& os,
const BbrSender::DebugState& state);
} // namespace quic