blob: 8598cadab172d2847cf3089db6b73c1f6d98f56d [file] [log] [blame]
/*
* Copyright (c) 2018 The WebRTC project authors. All Rights Reserved.
*
* Use of this source code is governed by a BSD-style license
* that can be found in the LICENSE file in the root of the source
* tree. An additional intellectual property rights grant can be found
* in the file PATENTS. All contributing project authors may
* be found in the AUTHORS file in the root of the source tree.
*/
// BBR (Bottleneck Bandwidth and RTT) congestion control algorithm.
// Based on the Quic BBR implementation in Chromium.
#ifndef MODULES_CONGESTION_CONTROLLER_BBR_BBR_NETWORK_CONTROLLER_H_
#define MODULES_CONGESTION_CONTROLLER_BBR_BBR_NETWORK_CONTROLLER_H_
#include <cstdint>
#include <memory>
#include <string>
#include <vector>
#include "api/transport/network_control.h"
#include "api/transport/network_types.h"
#include "modules/congestion_controller/bbr/bandwidth_sampler.h"
#include "modules/congestion_controller/bbr/loss_rate_filter.h"
#include "modules/congestion_controller/bbr/rtt_stats.h"
#include "modules/congestion_controller/bbr/windowed_filter.h"
#include "absl/types/optional.h"
#include "rtc_base/experiments/field_trial_parser.h"
#include "rtc_base/experiments/field_trial_units.h"
#include "rtc_base/random.h"
namespace webrtc {
namespace bbr {
typedef int64_t BbrRoundTripCount;
// 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.
class BbrNetworkController : public NetworkControllerInterface {
public:
enum Mode {
// Startup phase of the connection.
STARTUP,
// After achieving the highest possible bandwidth during the startup, lower
// the pacing rate in order to drain the queue.
DRAIN,
// Cruising mode.
PROBE_BW,
// Temporarily slow down sending in order to empty the buffer and measure
// the real minimum RTT.
PROBE_RTT,
};
// Indicates how the congestion control limits the amount of bytes in flight.
enum RecoveryState {
// Do not limit.
NOT_IN_RECOVERY = 0,
// Allow an extra outstanding byte for each byte acknowledged.
CONSERVATION = 1,
// Allow 1.5 extra outstanding bytes for each byte acknowledged.
MEDIUM_GROWTH = 2,
// Allow two extra outstanding bytes for each byte acknowledged (slow
// start).
GROWTH = 3
};
struct BbrControllerConfig {
FieldTrialParameter<double> probe_bw_pacing_gain_offset;
FieldTrialParameter<double> encoder_rate_gain;
FieldTrialParameter<double> encoder_rate_gain_in_probe_rtt;
// RTT delta to determine if startup should be exited due to increased RTT.
FieldTrialParameter<TimeDelta> exit_startup_rtt_threshold;
FieldTrialParameter<DataSize> initial_congestion_window;
FieldTrialParameter<DataSize> min_congestion_window;
FieldTrialParameter<DataSize> max_congestion_window;
FieldTrialParameter<double> probe_rtt_congestion_window_gain;
FieldTrialParameter<bool> pacing_rate_as_target;
// Configurable in QUIC BBR:
FieldTrialParameter<bool> exit_startup_on_loss;
// The number of RTTs to stay in STARTUP mode. Defaults to 3.
FieldTrialParameter<int> num_startup_rtts;
// When true, recovery is rate based rather than congestion window based.
FieldTrialParameter<bool> rate_based_recovery;
FieldTrialParameter<double> max_aggregation_bytes_multiplier;
// When true, pace at 1.5x and disable packet conservation in STARTUP.
FieldTrialParameter<bool> slower_startup;
// When true, disables packet conservation in STARTUP.
FieldTrialParameter<bool> rate_based_startup;
// Used as the initial packet conservation mode when first entering
// recovery.
FieldTrialEnum<RecoveryState> initial_conservation_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.
FieldTrialParameter<bool> fully_drain_queue;
FieldTrialParameter<double> max_ack_height_window_multiplier;
// If true, use a CWND of 0.75*BDP during probe_rtt instead of 4 packets.
FieldTrialParameter<bool> probe_rtt_based_on_bdp;
// If true, skip probe_rtt and update the timestamp of the existing min_rtt
// to now if min_rtt over the last cycle is within 12.5% of the current
// min_rtt. Even if the min_rtt is 12.5% too low, the 25% gain cycling and
// 2x CWND gain should overcome an overly small min_rtt.
FieldTrialParameter<bool> probe_rtt_skipped_if_similar_rtt;
// If true, disable PROBE_RTT entirely as long as the connection was
// recently app limited.
FieldTrialParameter<bool> probe_rtt_disabled_if_app_limited;
explicit BbrControllerConfig(std::string field_trial);
~BbrControllerConfig();
BbrControllerConfig(const BbrControllerConfig&);
static BbrControllerConfig FromTrial();
};
// Debug state can be exported in order to troubleshoot potential congestion
// control issues.
struct DebugState {
explicit DebugState(const BbrNetworkController& sender);
DebugState(const DebugState& state);
Mode mode;
DataRate max_bandwidth;
BbrRoundTripCount round_trip_count;
int gain_cycle_index;
DataSize congestion_window;
bool is_at_full_bandwidth;
DataRate bandwidth_at_last_round;
BbrRoundTripCount rounds_without_bandwidth_gain;
TimeDelta min_rtt;
Timestamp min_rtt_timestamp;
RecoveryState recovery_state;
DataSize recovery_window;
bool last_sample_is_app_limited;
int64_t end_of_app_limited_phase;
};
explicit BbrNetworkController(NetworkControllerConfig config);
~BbrNetworkController() override;
// NetworkControllerInterface
NetworkControlUpdate OnNetworkAvailability(NetworkAvailability msg) override;
NetworkControlUpdate OnNetworkRouteChange(NetworkRouteChange msg) override;
NetworkControlUpdate OnProcessInterval(ProcessInterval msg) override;
NetworkControlUpdate OnSentPacket(SentPacket msg) override;
NetworkControlUpdate OnStreamsConfig(StreamsConfig msg) override;
NetworkControlUpdate OnTargetRateConstraints(
TargetRateConstraints msg) override;
NetworkControlUpdate OnTransportPacketsFeedback(
TransportPacketsFeedback msg) override;
// Part of remote bitrate estimation api, not implemented for BBR
NetworkControlUpdate OnRemoteBitrateReport(RemoteBitrateReport msg) override;
NetworkControlUpdate OnRoundTripTimeUpdate(RoundTripTimeUpdate msg) override;
NetworkControlUpdate OnTransportLossReport(TransportLossReport msg) override;
NetworkControlUpdate OnReceivedPacket(ReceivedPacket msg) override;
NetworkControlUpdate CreateRateUpdate(Timestamp at_time) const;
private:
void Reset();
bool InSlowStart() const;
bool InRecovery() const;
bool IsProbingForMoreBandwidth() const;
bool CanSend(DataSize bytes_in_flight);
DataRate PacingRate() const;
DataRate BandwidthEstimate() const;
DataSize GetCongestionWindow() const;
double GetPacingGain(int round_offset) const;
void OnApplicationLimited(DataSize bytes_in_flight);
// End implementation of SendAlgorithmInterface.
typedef WindowedFilter<DataRate,
MaxFilter<DataRate>,
BbrRoundTripCount,
BbrRoundTripCount>
MaxBandwidthFilter;
typedef WindowedFilter<TimeDelta,
MaxFilter<TimeDelta>,
BbrRoundTripCount,
BbrRoundTripCount>
MaxAckDelayFilter;
typedef WindowedFilter<DataSize,
MaxFilter<DataSize>,
BbrRoundTripCount,
BbrRoundTripCount>
MaxAckHeightFilter;
// Returns the current estimate of the RTT of the connection. Outside of the
// edge cases, this is minimum RTT.
TimeDelta GetMinRtt() const;
// Returns whether the connection has achieved full bandwidth required to exit
// the slow start.
bool IsAtFullBandwidth() const;
// Computes the target congestion window using the specified gain.
DataSize GetTargetCongestionWindow(double gain) const;
// The target congestion window during PROBE_RTT.
DataSize ProbeRttCongestionWindow() const;
// Returns true if the current min_rtt should be kept and we should not enter
// PROBE_RTT immediately.
bool ShouldExtendMinRttExpiry() const;
// Enters the STARTUP mode.
void EnterStartupMode();
// Enters the PROBE_BW mode.
void EnterProbeBandwidthMode(Timestamp now);
// Discards the lost packets from BandwidthSampler state.
void DiscardLostPackets(const std::vector<PacketResult>& lost_packets);
// Updates the round-trip counter if a round-trip has passed. Returns true if
// the counter has been advanced.
// |last_acked_packet| is the sequence number of the last acked packet.
bool UpdateRoundTripCounter(int64_t last_acked_packet);
// Updates the current bandwidth and min_rtt estimate based on the samples for
// the received acknowledgements. Returns true if min_rtt has expired.
bool UpdateBandwidthAndMinRtt(Timestamp now,
const std::vector<PacketResult>& acked_packets);
// Updates the current gain used in PROBE_BW mode.
void UpdateGainCyclePhase(Timestamp now,
DataSize prior_in_flight,
bool has_losses);
// Tracks for how many round-trips the bandwidth has not increased
// significantly.
void CheckIfFullBandwidthReached();
// Transitions from STARTUP to DRAIN and from DRAIN to PROBE_BW if
// appropriate.
void MaybeExitStartupOrDrain(const TransportPacketsFeedback&);
// Decides whether to enter or exit PROBE_RTT.
void MaybeEnterOrExitProbeRtt(const TransportPacketsFeedback& msg,
bool is_round_start,
bool min_rtt_expired);
// Determines whether BBR needs to enter, exit or advance state of the
// recovery.
void UpdateRecoveryState(int64_t last_acked_packet,
bool has_losses,
bool is_round_start);
// Updates the ack aggregation max filter in bytes.
void UpdateAckAggregationBytes(Timestamp ack_time,
DataSize newly_acked_bytes);
// Determines the appropriate pacing rate for the connection.
void CalculatePacingRate();
// Determines the appropriate congestion window for the connection.
void CalculateCongestionWindow(DataSize bytes_acked);
// Determines the approriate window that constrains the
// in-flight during recovery.
void CalculateRecoveryWindow(DataSize bytes_acked,
DataSize bytes_lost,
DataSize bytes_in_flight);
BbrControllerConfig config_;
RttStats rtt_stats_;
webrtc::Random random_;
LossRateFilter loss_rate_;
absl::optional<TargetRateConstraints> constraints_;
Mode mode_;
// Bandwidth sampler provides BBR with the bandwidth measurements at
// individual points.
std::unique_ptr<BandwidthSampler> sampler_;
// The number of the round trips that have occurred during the connection.
BbrRoundTripCount round_trip_count_ = 0;
// The packet number of the most recently sent packet.
int64_t last_sent_packet_;
// Acknowledgement of any packet after |current_round_trip_end_| will cause
// the round trip counter to advance.
int64_t current_round_trip_end_;
// The filter that tracks the maximum bandwidth over the multiple recent
// round-trips.
MaxBandwidthFilter max_bandwidth_;
DataRate default_bandwidth_;
// Tracks the maximum number of bytes acked faster than the sending rate.
MaxAckHeightFilter max_ack_height_;
// The time this aggregation started and the number of bytes acked during it.
absl::optional<Timestamp> aggregation_epoch_start_time_;
DataSize aggregation_epoch_bytes_;
// The number of bytes acknowledged since the last time bytes in flight
// dropped below the target window.
DataSize bytes_acked_since_queue_drained_;
// The muliplier for calculating the max amount of extra CWND to add to
// compensate for ack aggregation.
double max_aggregation_bytes_multiplier_;
// Minimum RTT estimate. Automatically expires within 10 seconds (and
// triggers PROBE_RTT mode) if no new value is sampled during that period.
TimeDelta min_rtt_;
TimeDelta last_rtt_;
// The time at which the current value of |min_rtt_| was assigned.
Timestamp min_rtt_timestamp_;
// The maximum allowed number of bytes in flight.
DataSize congestion_window_;
// The initial value of the |congestion_window_|.
DataSize initial_congestion_window_;
// The smallest value the |congestion_window_| can achieve.
DataSize min_congestion_window_;
// The largest value the |congestion_window_| can achieve.
DataSize max_congestion_window_;
// The current pacing rate of the connection.
DataRate pacing_rate_;
// The gain currently applied to the pacing rate.
double pacing_gain_;
// The gain currently applied to the congestion window.
double congestion_window_gain_;
// The gain used for the congestion window during PROBE_BW. Latched from
// quic_bbr_cwnd_gain flag.
const double congestion_window_gain_constant_;
// The coefficient by which mean RTT variance is added to the congestion
// window. Latched from quic_bbr_rtt_variation_weight flag.
const double rtt_variance_weight_;
// 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.
Timestamp 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.
BbrRoundTripCount rounds_without_bandwidth_gain_;
// The bandwidth compared to which the increase is measured.
DataRate 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.
absl::optional<Timestamp> 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_;
// 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 set value indicates at least one
// loss has been detected, so it must not be reset.
absl::optional<int64_t> end_recovery_at_;
// A window used to limit the number of bytes in flight during loss recovery.
DataSize recovery_window_;
bool app_limited_since_last_probe_rtt_;
TimeDelta min_rtt_since_last_probe_rtt_;
RTC_DISALLOW_COPY_AND_ASSIGN(BbrNetworkController);
};
// Used in log output
std::ostream& operator<<( // no-presubmit-check TODO(webrtc:8982)
std::ostream& os, // no-presubmit-check TODO(webrtc:8982)
const BbrNetworkController::Mode& mode);
} // namespace bbr
} // namespace webrtc
#endif // MODULES_CONGESTION_CONTROLLER_BBR_BBR_NETWORK_CONTROLLER_H_