Initial export of QUIC BBRv2. PiperOrigin-RevId: 259531121 Change-Id: Idbca8ab50bac5e098bda4ec0a752b1d68a4a3cd2
diff --git a/quic/core/congestion_control/bbr2_drain.cc b/quic/core/congestion_control/bbr2_drain.cc new file mode 100644 index 0000000..a4247a4 --- /dev/null +++ b/quic/core/congestion_control/bbr2_drain.cc
@@ -0,0 +1,64 @@ +// Copyright 2019 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. + +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_drain.h" + +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_sender.h" + +namespace quic { + +void Bbr2DrainMode::Enter(const Bbr2CongestionEvent& /*congestion_event*/) {} + +Bbr2Mode Bbr2DrainMode::OnCongestionEvent( + QuicByteCount /*prior_in_flight*/, + QuicTime /*event_time*/, + const AckedPacketVector& /*acked_packets*/, + const LostPacketVector& /*lost_packets*/, + const Bbr2CongestionEvent& congestion_event) { + model_->set_pacing_gain(Params().drain_pacing_gain); + + // Only STARTUP can transition to DRAIN, both of them use the same cwnd gain. + DCHECK_EQ(model_->cwnd_gain(), Params().drain_cwnd_gain); + model_->set_cwnd_gain(Params().drain_cwnd_gain); + + QuicByteCount drain_target = DrainTarget(); + if (congestion_event.bytes_in_flight <= drain_target) { + QUIC_DVLOG(3) << sender_ << " Exiting DRAIN. bytes_in_flight:" + << congestion_event.bytes_in_flight + << ", bdp:" << model_->BDP(model_->MaxBandwidth()) + << ", drain_target:" << drain_target << " @ " + << congestion_event.event_time; + return Bbr2Mode::PROBE_BW; + } + + QUIC_DVLOG(3) << sender_ << " Staying in DRAIN. bytes_in_flight:" + << congestion_event.bytes_in_flight + << ", bdp:" << model_->BDP(model_->MaxBandwidth()) + << ", drain_target:" << drain_target << " @ " + << congestion_event.event_time; + return Bbr2Mode::DRAIN; +} + +QuicByteCount Bbr2DrainMode::DrainTarget() const { + QuicByteCount bdp = model_->BDP(model_->MaxBandwidth()); + return std::max<QuicByteCount>(bdp, sender_->GetMinimumCongestionWindow()); +} + +Bbr2DrainMode::DebugState Bbr2DrainMode::ExportDebugState() const { + DebugState s; + s.drain_target = DrainTarget(); + return s; +} + +std::ostream& operator<<(std::ostream& os, + const Bbr2DrainMode::DebugState& state) { + os << "[DRAIN] drain_target: " << state.drain_target << "\n"; + return os; +} + +const Bbr2Params& Bbr2DrainMode::Params() const { + return sender_->Params(); +} + +} // namespace quic
diff --git a/quic/core/congestion_control/bbr2_drain.h b/quic/core/congestion_control/bbr2_drain.h new file mode 100644 index 0000000..546962b --- /dev/null +++ b/quic/core/congestion_control/bbr2_drain.h
@@ -0,0 +1,53 @@ +// Copyright 2019 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. + +#ifndef QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_DRAIN_H_ +#define QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_DRAIN_H_ + +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_misc.h" +#include "net/third_party/quiche/src/quic/core/quic_time.h" +#include "net/third_party/quiche/src/quic/core/quic_types.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_export.h" + +namespace quic { + +class Bbr2Sender; +class QUIC_EXPORT_PRIVATE Bbr2DrainMode final : public Bbr2ModeBase { + public: + using Bbr2ModeBase::Bbr2ModeBase; + + void Enter(const Bbr2CongestionEvent& congestion_event) override; + + Bbr2Mode OnCongestionEvent( + QuicByteCount prior_in_flight, + QuicTime event_time, + const AckedPacketVector& acked_packets, + const LostPacketVector& lost_packets, + const Bbr2CongestionEvent& congestion_event) override; + + Limits<QuicByteCount> GetCwndLimits() const override { + return NoGreaterThan(model_->inflight_lo()); + } + + bool IsProbingForBandwidth() const override { return false; } + + struct DebugState { + QuicByteCount drain_target; + }; + + DebugState ExportDebugState() const; + + private: + const Bbr2Params& Params() const; + + QuicByteCount DrainTarget() const; +}; + +QUIC_EXPORT_PRIVATE std::ostream& operator<<( + std::ostream& os, + const Bbr2DrainMode::DebugState& state); + +} // namespace quic + +#endif // QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_DRAIN_H_
diff --git a/quic/core/congestion_control/bbr2_misc.cc b/quic/core/congestion_control/bbr2_misc.cc new file mode 100644 index 0000000..507290b --- /dev/null +++ b/quic/core/congestion_control/bbr2_misc.cc
@@ -0,0 +1,327 @@ +// Copyright 2019 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. + +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_misc.h" + +#include "net/third_party/quiche/src/quic/core/congestion_control/bandwidth_sampler.h" +#include "net/third_party/quiche/src/quic/core/quic_bandwidth.h" +#include "net/third_party/quiche/src/quic/core/quic_time.h" +#include "net/third_party/quiche/src/quic/core/quic_types.h" + +namespace quic { + +namespace { +// Sensitivity in response to losses. 0 means no loss response. +// 0.3 is also used by TCP bbr and cubic. +const float kBeta = 0.3; + +const QuicTime::Delta kMinRttExpiry = QuicTime::Delta::FromSeconds(10); +} // namespace + +RoundTripCounter::RoundTripCounter() : round_trip_count_(0) {} + +void RoundTripCounter::OnPacketSent(QuicPacketNumber packet_number) { + DCHECK(!last_sent_packet_.IsInitialized() || + last_sent_packet_ < packet_number); + last_sent_packet_ = packet_number; +} + +bool RoundTripCounter::OnPacketsAcked(QuicPacketNumber last_acked_packet) { + if (!end_of_round_trip_.IsInitialized() || + last_acked_packet > end_of_round_trip_) { + round_trip_count_++; + end_of_round_trip_ = last_sent_packet_; + return true; + } + return false; +} + +void RoundTripCounter::RestartRound() { + end_of_round_trip_ = last_sent_packet_; +} + +MinRttFilter::MinRttFilter(QuicTime::Delta initial_min_rtt, + QuicTime initial_min_rtt_timestamp) + : min_rtt_(initial_min_rtt), + min_rtt_timestamp_(initial_min_rtt_timestamp) {} + +void MinRttFilter::Update(QuicTime::Delta sample_rtt, QuicTime now) { + if (sample_rtt < min_rtt_ || min_rtt_timestamp_ == QuicTime::Zero()) { + min_rtt_ = sample_rtt; + min_rtt_timestamp_ = now; + } +} + +void MinRttFilter::ForceUpdate(QuicTime::Delta sample_rtt, QuicTime now) { + min_rtt_ = sample_rtt; + min_rtt_timestamp_ = now; +} + +const SendTimeState& SendStateOfLargestPacket( + const Bbr2CongestionEvent& congestion_event) { + const auto& last_acked_sample = congestion_event.last_acked_sample; + const auto& last_lost_sample = congestion_event.last_lost_sample; + + if (!last_lost_sample.packet_number.IsInitialized()) { + return last_acked_sample.bandwidth_sample.state_at_send; + } + + if (!last_acked_sample.packet_number.IsInitialized()) { + return last_lost_sample.send_time_state; + } + + DCHECK_NE(last_acked_sample.packet_number, last_lost_sample.packet_number); + + if (last_acked_sample.packet_number < last_lost_sample.packet_number) { + return last_lost_sample.send_time_state; + } + return last_acked_sample.bandwidth_sample.state_at_send; +} + +QuicByteCount Bbr2MaxAckHeightTracker::Update( + const QuicBandwidth& bandwidth_estimate, + QuicRoundTripCount round_trip_count, + QuicTime ack_time, + QuicByteCount bytes_acked) { + // TODO(wub): Find out whether TCP adds bytes_acked before or after the check. + aggregation_epoch_bytes_ += bytes_acked; + + // Compute how many bytes are expected to be delivered, assuming max bandwidth + // is correct. + QuicByteCount expected_bytes_acked = + bandwidth_estimate * (ack_time - aggregation_epoch_start_time_); + // Reset the current aggregation epoch as soon as the ack arrival rate is less + // than or equal to the max bandwidth. + if (aggregation_epoch_bytes_ <= expected_bytes_acked) { + // Reset to start measuring a new aggregation epoch. + aggregation_epoch_bytes_ = bytes_acked; + aggregation_epoch_start_time_ = ack_time; + return 0; + } + + // Compute how many extra bytes were delivered vs max bandwidth. + QuicByteCount extra_bytes_acked = + aggregation_epoch_bytes_ - expected_bytes_acked; + max_ack_height_filter_.Update(extra_bytes_acked, round_trip_count); + return extra_bytes_acked; +} + +Bbr2NetworkModel::Bbr2NetworkModel(const Bbr2Params* params, + QuicTime::Delta initial_rtt, + QuicTime initial_rtt_timestamp, + float cwnd_gain, + float pacing_gain) + : params_(params), + min_rtt_filter_(initial_rtt, initial_rtt_timestamp), + max_ack_height_tracker_(params->initial_max_ack_height_filter_window), + cwnd_gain_(cwnd_gain), + pacing_gain_(pacing_gain) {} + +void Bbr2NetworkModel::OnPacketSent(QuicTime sent_time, + QuicByteCount bytes_in_flight, + QuicPacketNumber packet_number, + QuicByteCount bytes, + HasRetransmittableData is_retransmittable) { + round_trip_counter_.OnPacketSent(packet_number); + + bandwidth_sampler_.OnPacketSent(sent_time, packet_number, bytes, + bytes_in_flight, is_retransmittable); +} + +void Bbr2NetworkModel::OnCongestionEventStart( + QuicTime event_time, + const AckedPacketVector& acked_packets, + const LostPacketVector& lost_packets, + Bbr2CongestionEvent* congestion_event) { + const QuicByteCount prior_bytes_acked = total_bytes_acked(); + const QuicByteCount prior_bytes_lost = total_bytes_lost(); + + congestion_event->event_time = event_time; + congestion_event->end_of_round_trip = + acked_packets.empty() ? false + : round_trip_counter_.OnPacketsAcked( + acked_packets.rbegin()->packet_number); + + // TODO(wub): Get the max bandwidth sample from all acked_packets, then use it + // to update max_bandwidth_filter_ once after the loop. + for (const auto& packet : acked_packets) { + const BandwidthSample bandwidth_sample = + bandwidth_sampler_.OnPacketAcknowledged(event_time, + packet.packet_number); + if (!bandwidth_sample.state_at_send.is_valid) { + // From the sampler's perspective, the packet has never been sent, or + // the packet has been acked or marked as lost previously. + continue; + } + + congestion_event->last_sample_is_app_limited = + bandwidth_sample.state_at_send.is_app_limited; + if (!bandwidth_sample.rtt.IsZero()) { + congestion_event->sample_min_rtt = + std::min(congestion_event->sample_min_rtt, bandwidth_sample.rtt); + } + if (!bandwidth_sample.state_at_send.is_app_limited || + bandwidth_sample.bandwidth > MaxBandwidth()) { + max_bandwidth_filter_.Update(bandwidth_sample.bandwidth); + } + + if (bandwidth_sample.bandwidth > bandwidth_latest_) { + bandwidth_latest_ = bandwidth_sample.bandwidth; + } + + // |inflight_sample| is the total bytes acked while |packet| is inflight. + QuicByteCount inflight_sample = + total_bytes_acked() - bandwidth_sample.state_at_send.total_bytes_acked; + if (inflight_sample > inflight_latest_) { + inflight_latest_ = inflight_sample; + } + + congestion_event->last_acked_sample = {packet.packet_number, + bandwidth_sample, inflight_sample}; + } + + min_rtt_filter_.Update(congestion_event->sample_min_rtt, event_time); + + for (const LostPacket& packet : lost_packets) { + const SendTimeState send_time_state = + bandwidth_sampler_.OnPacketLost(packet.packet_number); + if (send_time_state.is_valid) { + congestion_event->last_lost_sample = {packet.packet_number, + send_time_state}; + } + } + + congestion_event->bytes_in_flight = bytes_in_flight(); + + congestion_event->bytes_acked = total_bytes_acked() - prior_bytes_acked; + congestion_event->bytes_lost = total_bytes_lost() - prior_bytes_lost; + bytes_lost_in_round_ += congestion_event->bytes_lost; + + max_ack_height_tracker_.Update(BandwidthEstimate(), RoundTripCount(), + event_time, congestion_event->bytes_acked); + + if (!congestion_event->end_of_round_trip) { + return; + } + + // Per round-trip updates. + AdaptLowerBounds(*congestion_event); +} + +void Bbr2NetworkModel::AdaptLowerBounds( + const Bbr2CongestionEvent& congestion_event) { + if (!congestion_event.end_of_round_trip || + congestion_event.is_probing_for_bandwidth) { + return; + } + + if (bytes_lost_in_round_ > 0) { + if (bandwidth_lo_.IsInfinite()) { + bandwidth_lo_ = MaxBandwidth(); + } + if (inflight_lo_ == inflight_lo_default()) { + inflight_lo_ = congestion_event.prior_cwnd; + } + + bandwidth_lo_ = std::max(bandwidth_latest_, bandwidth_lo_ * (1.0 - kBeta)); + QUIC_DVLOG(3) << "bandwidth_lo_ updated to " << bandwidth_lo_ + << ", bandwidth_latest_ is " << bandwidth_latest_; + + inflight_lo_ = + std::max<QuicByteCount>(inflight_latest_, inflight_lo_ * (1.0 - kBeta)); + } +} + +void Bbr2NetworkModel::OnCongestionEventFinish( + QuicPacketNumber least_unacked_packet, + const Bbr2CongestionEvent& congestion_event) { + if (congestion_event.end_of_round_trip) { + const auto& last_acked_sample = congestion_event.last_acked_sample; + if (last_acked_sample.bandwidth_sample.state_at_send.is_valid) { + bandwidth_latest_ = last_acked_sample.bandwidth_sample.bandwidth; + inflight_latest_ = last_acked_sample.inflight_sample; + } + + bytes_lost_in_round_ = 0; + } + + bandwidth_sampler_.RemoveObsoletePackets(least_unacked_packet); +} + +void Bbr2NetworkModel::UpdateNetworkParameters(QuicBandwidth bandwidth, + QuicTime::Delta rtt) { + if (!bandwidth.IsInfinite() && bandwidth > MaxBandwidth()) { + max_bandwidth_filter_.Update(bandwidth); + } + + if (!rtt.IsZero()) { + min_rtt_filter_.Update(rtt, MinRttTimestamp()); + } +} + +bool Bbr2NetworkModel::MaybeExpireMinRtt( + const Bbr2CongestionEvent& congestion_event) { + if (congestion_event.event_time < (MinRttTimestamp() + kMinRttExpiry)) { + return false; + } + if (congestion_event.sample_min_rtt.IsInfinite()) { + return false; + } + QUIC_DVLOG(3) << "Replacing expired min rtt of " << min_rtt_filter_.Get() + << " by " << congestion_event.sample_min_rtt << " @ " + << congestion_event.event_time; + min_rtt_filter_.ForceUpdate(congestion_event.sample_min_rtt, + congestion_event.event_time); + return true; +} + +bool Bbr2NetworkModel::IsCongestionWindowLimited( + const Bbr2CongestionEvent& congestion_event) const { + QuicByteCount prior_bytes_in_flight = congestion_event.bytes_in_flight + + congestion_event.bytes_acked + + congestion_event.bytes_lost; + return prior_bytes_in_flight >= congestion_event.prior_cwnd; +} + +bool Bbr2NetworkModel::IsInflightTooHigh( + const Bbr2CongestionEvent& congestion_event) const { + const SendTimeState& send_state = SendStateOfLargestPacket(congestion_event); + if (!send_state.is_valid) { + // Not enough information. + return false; + } + + const QuicByteCount inflight_at_send = BytesInFlight(send_state); + // TODO(wub): Consider total_bytes_lost() - send_state.total_bytes_lost, which + // is the total bytes lost when the largest numbered packet was inflight. + // bytes_lost_in_round_, OTOH, is the total bytes lost in the "current" round. + const QuicByteCount bytes_lost_in_round = bytes_lost_in_round_; + + QUIC_DVLOG(3) << "IsInflightTooHigh: bytes_lost_in_round:" + << bytes_lost_in_round << ", lost_in_round_threshold:" + << inflight_at_send * Params().loss_threshold; + + if (inflight_at_send > 0 && bytes_lost_in_round > 0) { + QuicByteCount lost_in_round_threshold = + inflight_at_send * Params().loss_threshold; + if (bytes_lost_in_round > lost_in_round_threshold) { + return true; + } + } + + return false; +} + +void Bbr2NetworkModel::RestartRound() { + bytes_lost_in_round_ = 0; + round_trip_counter_.RestartRound(); +} + +QuicByteCount Bbr2NetworkModel::inflight_hi_with_headroom() const { + QuicByteCount headroom = inflight_hi_ * Params().inflight_hi_headroom; + + return inflight_hi_ > headroom ? inflight_hi_ - headroom : 0; +} + +} // namespace quic
diff --git a/quic/core/congestion_control/bbr2_misc.h b/quic/core/congestion_control/bbr2_misc.h new file mode 100644 index 0000000..08717a2 --- /dev/null +++ b/quic/core/congestion_control/bbr2_misc.h
@@ -0,0 +1,513 @@ +// Copyright 2019 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. + +#ifndef QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_MISC_H_ +#define QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_MISC_H_ + +#include <algorithm> +#include <limits> + +#include "net/third_party/quiche/src/quic/core/congestion_control/bandwidth_sampler.h" +#include "net/third_party/quiche/src/quic/core/congestion_control/windowed_filter.h" +#include "net/third_party/quiche/src/quic/core/quic_bandwidth.h" +#include "net/third_party/quiche/src/quic/core/quic_packet_number.h" +#include "net/third_party/quiche/src/quic/core/quic_time.h" +#include "net/third_party/quiche/src/quic/core/quic_types.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_export.h" +#include "net/quic/platform/impl/quic_export_impl.h" + +namespace quic { + +typedef uint64_t QuicRoundTripCount; + +template <typename T> +class QUIC_EXPORT_PRIVATE Limits { + public: + Limits(T min, T max) : min_(min), max_(max) {} + + // If [min, max] is an empty range, i.e. min > max, this function returns max, + // because typically a value larger than max means "risky". + T ApplyLimits(T raw_value) const { + return std::min(max_, std::max(min_, raw_value)); + } + + T Min() const { return min_; } + T Max() const { return max_; } + + private: + T min_; + T max_; +}; + +template <typename T> +QUIC_EXPORT_PRIVATE inline Limits<T> MinMax(T min, T max) { + return Limits<T>(min, max); +} + +template <typename T> +QUIC_EXPORT_PRIVATE inline Limits<T> NoLessThan(T min) { + return Limits<T>(min, std::numeric_limits<T>::max()); +} + +template <typename T> +QUIC_EXPORT_PRIVATE inline Limits<T> NoGreaterThan(T max) { + return Limits<T>(std::numeric_limits<T>::min(), max); +} + +template <typename T> +QUIC_EXPORT_PRIVATE inline Limits<T> Unlimited() { + return Limits<T>(std::numeric_limits<T>::min(), + std::numeric_limits<T>::max()); +} + +template <typename T> +QUIC_EXPORT_PRIVATE inline std::ostream& operator<<(std::ostream& os, + const Limits<T>& limits) { + return os << "[" << limits.Min() << ", " << limits.Max() << "]"; +} + +// Bbr2Params contains all parameters of a Bbr2Sender. +struct QUIC_EXPORT_PRIVATE Bbr2Params { + Bbr2Params(QuicByteCount cwnd_min, QuicByteCount cwnd_max) + : cwnd_limits(cwnd_min, cwnd_max) {} + + /* + * STARTUP parameters. + */ + + // The gain for both CWND and PacingRate at startup. + // TODO(wub): Maybe change to the newly derived value of 2.773 (4 * ln(2)). + float startup_gain = 2.885; + + // Full bandwidth is declared if the total bandwidth growth is less than + // |startup_full_bw_threshold| times in the last |startup_full_bw_rounds| + // round trips. + float startup_full_bw_threshold = 1.25; + + QuicRoundTripCount startup_full_bw_rounds = 3; + + // The minimum number of loss marking events to exit STARTUP. + int64_t startup_full_loss_count = 8; + + /* + * DRAIN parameters. + */ + float drain_cwnd_gain = 2.885; + float drain_pacing_gain = 1.0 / 2.885; + + /* + * PROBE_BW parameters. + */ + // Max amount of randomness to inject in round counting for Reno-coexistence. + QuicRoundTripCount probe_bw_max_probe_rand_rounds = 2; + + // Max number of rounds before probing for Reno-coexistence. + uint32_t probe_bw_probe_max_rounds = 63; + + // Multiplier to get Reno-style probe epoch duration as: k * BDP round trips. + // If zero, disables Reno-style BDP-scaled coexistence mechanism. + float probe_bw_probe_reno_gain = 1.0; + + // Minimum duration for BBR-native probes. + QuicTime::Delta probe_bw_probe_base_duration = + QuicTime::Delta::FromSeconds(2); + + // The upper bound of the random amound of BBR-native probes. + QuicTime::Delta probe_bw_probe_max_rand_duration = + QuicTime::Delta::FromSeconds(1); + + // Multiplier to get target inflight (as multiple of BDP) for PROBE_UP phase. + float probe_bw_probe_inflight_gain = 1.25; + + // Pacing gains. + float probe_bw_probe_up_pacing_gain = 1.25; + float probe_bw_probe_down_pacing_gain = 0.75; + float probe_bw_default_pacing_gain = 1.0; + + float probe_bw_cwnd_gain = 2.0; + + /* + * PROBE_RTT parameters. + */ + float probe_rtt_inflight_target_bdp_fraction = 0.5; + QuicTime::Delta probe_rtt_duration = QuicTime::Delta::FromMilliseconds(200); + + /* + * Parameters used by multiple modes. + */ + + // The initial value of the max ack height filter's window length. + QuicRoundTripCount initial_max_ack_height_filter_window = 10; + + // Fraction of unutilized headroom to try to leave in path upon high loss. + float inflight_hi_headroom = 0.15; + + // Estimate startup/bw probing has gone too far if loss rate exceeds this. + float loss_threshold = 0.02; + + Limits<QuicByteCount> cwnd_limits; +}; + +class QUIC_EXPORT_PRIVATE RoundTripCounter { + public: + RoundTripCounter(); + + QuicRoundTripCount Count() const { return round_trip_count_; } + + QuicPacketNumber last_sent_packet() const { return last_sent_packet_; } + + // Must be called in ascending packet number order. + void OnPacketSent(QuicPacketNumber packet_number); + + // Return whether a round trip has just completed. + bool OnPacketsAcked(QuicPacketNumber last_acked_packet); + + void RestartRound(); + + private: + QuicRoundTripCount round_trip_count_; + QuicPacketNumber last_sent_packet_; + // The last sent packet number of the current round trip. + QuicPacketNumber end_of_round_trip_; +}; + +class QUIC_EXPORT_PRIVATE MinRttFilter { + public: + MinRttFilter(QuicTime::Delta initial_min_rtt, + QuicTime initial_min_rtt_timestamp); + + void Update(QuicTime::Delta sample_rtt, QuicTime now); + + void ForceUpdate(QuicTime::Delta sample_rtt, QuicTime now); + + QuicTime::Delta Get() const { return min_rtt_; } + + QuicTime GetTimestamp() const { return min_rtt_timestamp_; } + + private: + QuicTime::Delta min_rtt_; + // Time when the current value of |min_rtt_| was assigned. + QuicTime min_rtt_timestamp_; +}; + +class QUIC_EXPORT_PRIVATE Bbr2MaxBandwidthFilter { + public: + void Update(QuicBandwidth sample) { + max_bandwidth_[1] = std::max(sample, max_bandwidth_[1]); + } + + void Advance() { + if (max_bandwidth_[1].IsZero()) { + return; + } + + max_bandwidth_[0] = max_bandwidth_[1]; + max_bandwidth_[1] = QuicBandwidth::Zero(); + } + + QuicBandwidth Get() const { + return std::max(max_bandwidth_[0], max_bandwidth_[1]); + } + + private: + QuicBandwidth max_bandwidth_[2] = {QuicBandwidth::Zero(), + QuicBandwidth::Zero()}; +}; + +// Information that are meaningful only when Bbr2Sender::OnCongestionEvent is +// running. +struct QUIC_EXPORT_PRIVATE Bbr2CongestionEvent { + QuicTime event_time = QuicTime::Zero(); + + // The congestion window prior to the processing of the ack/loss events. + QuicByteCount prior_cwnd; + + // Total bytes inflight after the processing of the ack/loss events. + QuicByteCount bytes_in_flight = 0; + + // Total bytes acked from acks in this event. + QuicByteCount bytes_acked = 0; + + // Total bytes lost from losses in this event. + QuicByteCount bytes_lost = 0; + + // Whether acked_packets indicates the end of a round trip. + bool end_of_round_trip = false; + + // Whether the last bandwidth sample from acked_packets is app limited. + // false if acked_packets is empty. + bool last_sample_is_app_limited = false; + + // When the event happened, whether the sender is probing for bandwidth. + bool is_probing_for_bandwidth = false; + + // Minimum rtt of all bandwidth samples from acked_packets. + // QuicTime::Delta::Infinite() if acked_packets is empty. + QuicTime::Delta sample_min_rtt = QuicTime::Delta::Infinite(); + + // Send time state of the largest-numbered packet in this event. + // SendTimeState send_time_state; + struct { + QuicPacketNumber packet_number; + BandwidthSample bandwidth_sample; + // Total bytes acked while |packet| is inflight. + QuicByteCount inflight_sample; + } last_acked_sample; + + struct { + QuicPacketNumber packet_number; + SendTimeState send_time_state; + } last_lost_sample; +}; + +QUIC_EXPORT_PRIVATE const SendTimeState& SendStateOfLargestPacket( + const Bbr2CongestionEvent& congestion_event); + +class QUIC_EXPORT_PRIVATE Bbr2MaxAckHeightTracker { + public: + explicit Bbr2MaxAckHeightTracker(QuicRoundTripCount initial_filter_window) + : max_ack_height_filter_(initial_filter_window, 0, 0) {} + + QuicByteCount Get() const { return max_ack_height_filter_.GetBest(); } + + QuicByteCount Update(const QuicBandwidth& bandwidth_estimate, + QuicRoundTripCount round_trip_count, + QuicTime ack_time, + QuicByteCount bytes_acked); + + private: + // Tracks the maximum number of bytes acked faster than the sending rate. + typedef WindowedFilter<QuicByteCount, + MaxFilter<QuicByteCount>, + QuicRoundTripCount, + QuicRoundTripCount> + MaxAckHeightFilter; + MaxAckHeightFilter max_ack_height_filter_; + + // The time this aggregation started and the number of bytes acked during it. + QuicTime aggregation_epoch_start_time_ = QuicTime::Zero(); + QuicByteCount aggregation_epoch_bytes_ = 0; +}; + +// Bbr2NetworkModel takes low level congestion signals(packets sent/acked/lost) +// as input and produces BBRv2 model parameters like inflight_(hi|lo), +// bandwidth_(hi|lo), bandwidth and rtt estimates, etc. +class QUIC_EXPORT_PRIVATE Bbr2NetworkModel { + public: + Bbr2NetworkModel(const Bbr2Params* params, + QuicTime::Delta initial_rtt, + QuicTime initial_rtt_timestamp, + float cwnd_gain, + float pacing_gain); + + void OnPacketSent(QuicTime sent_time, + QuicByteCount bytes_in_flight, + QuicPacketNumber packet_number, + QuicByteCount bytes, + HasRetransmittableData is_retransmittable); + + void OnCongestionEventStart(QuicTime event_time, + const AckedPacketVector& acked_packets, + const LostPacketVector& lost_packets, + Bbr2CongestionEvent* congestion_event); + + void OnCongestionEventFinish(QuicPacketNumber least_unacked_packet, + const Bbr2CongestionEvent& congestion_event); + + // Update the model without a congestion event. + // Max bandwidth is updated if |bandwidth| is larger than existing max + // bandwidth. Min rtt is updated if |rtt| is non-zero and smaller than + // existing min rtt. + void UpdateNetworkParameters(QuicBandwidth bandwidth, QuicTime::Delta rtt); + + // Update inflight/bandwidth short-term lower bounds. + void AdaptLowerBounds(const Bbr2CongestionEvent& congestion_event); + + // Restart the current round trip as if it is starting now. + void RestartRound(); + + void AdvanceMaxBandwidthFilter() { max_bandwidth_filter_.Advance(); } + + void OnApplicationLimited() { bandwidth_sampler_.OnAppLimited(); } + + QuicByteCount BDP(QuicBandwidth bandwidth) const { + return bandwidth * MinRtt(); + } + + QuicByteCount BDP(QuicBandwidth bandwidth, float gain) const { + return bandwidth * MinRtt() * gain; + } + + QuicTime::Delta MinRtt() const { return min_rtt_filter_.Get(); } + + QuicTime MinRttTimestamp() const { return min_rtt_filter_.GetTimestamp(); } + + QuicBandwidth MaxBandwidth() const { return max_bandwidth_filter_.Get(); } + + QuicByteCount MaxAckHeight() const { return max_ack_height_tracker_.Get(); } + + bool MaybeExpireMinRtt(const Bbr2CongestionEvent& congestion_event); + + QuicBandwidth BandwidthEstimate() const { + return std::min(MaxBandwidth(), bandwidth_lo_); + } + + QuicRoundTripCount RoundTripCount() const { + return round_trip_counter_.Count(); + } + + bool IsCongestionWindowLimited( + const Bbr2CongestionEvent& congestion_event) const; + + bool IsInflightTooHigh(const Bbr2CongestionEvent& congestion_event) const; + + QuicPacketNumber last_sent_packet() const { + return round_trip_counter_.last_sent_packet(); + } + + QuicByteCount total_bytes_acked() const { + return bandwidth_sampler_.total_bytes_acked(); + } + + QuicByteCount total_bytes_lost() const { + return bandwidth_sampler_.total_bytes_lost(); + } + + QuicByteCount total_bytes_sent() const { + return bandwidth_sampler_.total_bytes_sent(); + } + + QuicByteCount bytes_in_flight() const { + return total_bytes_sent() - total_bytes_acked() - total_bytes_lost(); + } + + QuicPacketNumber end_of_app_limited_phase() const { + return bandwidth_sampler_.end_of_app_limited_phase(); + } + + QuicBandwidth bandwidth_latest() const { return bandwidth_latest_; } + QuicBandwidth bandwidth_lo() const { return bandwidth_lo_; } + void clear_bandwidth_lo() { bandwidth_lo_ = QuicBandwidth::Infinite(); } + + QuicByteCount inflight_latest() const { return inflight_latest_; } + QuicByteCount inflight_lo() const { return inflight_lo_; } + static QuicByteCount inflight_lo_default() { + return std::numeric_limits<QuicByteCount>::max(); + } + void clear_inflight_lo() { inflight_lo_ = inflight_lo_default(); } + + QuicByteCount inflight_hi_with_headroom() const; + QuicByteCount inflight_hi() const { return inflight_hi_; } + static QuicByteCount inflight_hi_default() { + return std::numeric_limits<QuicByteCount>::max(); + } + void set_inflight_hi(QuicByteCount inflight_hi) { + inflight_hi_ = inflight_hi; + } + + float cwnd_gain() const { return cwnd_gain_; } + void set_cwnd_gain(float cwnd_gain) { cwnd_gain_ = cwnd_gain; } + + float pacing_gain() const { return pacing_gain_; } + void set_pacing_gain(float pacing_gain) { pacing_gain_ = pacing_gain; } + + private: + const Bbr2Params& Params() const { return *params_; } + const Bbr2Params* const params_; + RoundTripCounter round_trip_counter_; + + // Bandwidth sampler provides BBR with the bandwidth measurements at + // individual points. + BandwidthSampler bandwidth_sampler_; + // The filter that tracks the maximum bandwidth over multiple recent round + // trips. + Bbr2MaxBandwidthFilter max_bandwidth_filter_; + MinRttFilter min_rtt_filter_; + + Bbr2MaxAckHeightTracker max_ack_height_tracker_; + + // Bytes lost in the current round. Updated once per congestion event. + QuicByteCount bytes_lost_in_round_ = 0; + + // Max bandwidth in the current round. Updated once per congestion event. + QuicBandwidth bandwidth_latest_ = QuicBandwidth::Zero(); + // Max bandwidth of recent rounds. Updated once per round. + QuicBandwidth bandwidth_lo_ = QuicBandwidth::Infinite(); + + // Max inflight in the current round. Updated once per congestion event. + QuicByteCount inflight_latest_ = 0; + // Max inflight of recent rounds. Updated once per round. + QuicByteCount inflight_lo_ = inflight_lo_default(); + QuicByteCount inflight_hi_ = inflight_hi_default(); + + float cwnd_gain_; + float pacing_gain_; +}; + +enum class Bbr2Mode : uint8_t { + // 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, +}; + +QUIC_EXPORT_PRIVATE inline std::ostream& operator<<(std::ostream& os, + const Bbr2Mode& mode) { + switch (mode) { + case Bbr2Mode::STARTUP: + return os << "STARTUP"; + case Bbr2Mode::DRAIN: + return os << "DRAIN"; + case Bbr2Mode::PROBE_BW: + return os << "PROBE_BW"; + case Bbr2Mode::PROBE_RTT: + return os << "PROBE_RTT"; + } + return os << "<Invalid Mode>"; +} + +// The base class for all BBRv2 modes. A Bbr2Sender is in one mode at a time, +// this interface is used to implement mode-specific behaviors. +class Bbr2Sender; +class QUIC_EXPORT_PRIVATE Bbr2ModeBase { + public: + Bbr2ModeBase(const Bbr2Sender* sender, Bbr2NetworkModel* model) + : sender_(sender), model_(model) {} + + virtual ~Bbr2ModeBase() = default; + + virtual void Enter(const Bbr2CongestionEvent& congestion_event) = 0; + + virtual Bbr2Mode OnCongestionEvent( + QuicByteCount prior_in_flight, + QuicTime event_time, + const AckedPacketVector& acked_packets, + const LostPacketVector& lost_packets, + const Bbr2CongestionEvent& congestion_event) = 0; + + virtual Limits<QuicByteCount> GetCwndLimits() const = 0; + + virtual bool IsProbingForBandwidth() const = 0; + + protected: + const Bbr2Sender* const sender_; + Bbr2NetworkModel* model_; +}; + +QUIC_EXPORT_PRIVATE inline QuicByteCount BytesInFlight( + const SendTimeState& send_state) { + DCHECK(send_state.is_valid); + return send_state.total_bytes_sent - send_state.total_bytes_acked - + send_state.total_bytes_lost; +} + +} // namespace quic + +#endif // QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_MISC_H_
diff --git a/quic/core/congestion_control/bbr2_probe_bw.cc b/quic/core/congestion_control/bbr2_probe_bw.cc new file mode 100644 index 0000000..ed65cf9 --- /dev/null +++ b/quic/core/congestion_control/bbr2_probe_bw.cc
@@ -0,0 +1,516 @@ +// Copyright 2019 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. + +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_probe_bw.h" + +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_misc.h" +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_sender.h" +#include "net/third_party/quiche/src/quic/core/quic_bandwidth.h" +#include "net/third_party/quiche/src/quic/core/quic_time.h" +#include "net/third_party/quiche/src/quic/core/quic_types.h" + +namespace quic { + +void Bbr2ProbeBwMode::Enter(const Bbr2CongestionEvent& congestion_event) { + if (cycle_.phase == CyclePhase::PROBE_NOT_STARTED) { + // First time entering PROBE_BW. Start a new probing cycle. + EnterProbeDown(/*probed_too_high=*/false, /*stopped_risky_probe=*/false, + congestion_event); + } else { + // Transitioning from PROBE_RTT to PROBE_BW. Re-enter the last phase before + // PROBE_RTT. + DCHECK(cycle_.phase == CyclePhase::PROBE_CRUISE || + cycle_.phase == CyclePhase::PROBE_REFILL); + cycle_.cycle_start_time = congestion_event.event_time; + if (cycle_.phase == CyclePhase::PROBE_CRUISE) { + EnterProbeCruise(congestion_event); + } else if (cycle_.phase == CyclePhase::PROBE_REFILL) { + EnterProbeRefill(cycle_.probe_up_rounds, congestion_event); + } + } +} + +Bbr2Mode Bbr2ProbeBwMode::OnCongestionEvent( + QuicByteCount prior_in_flight, + QuicTime event_time, + const AckedPacketVector& /*acked_packets*/, + const LostPacketVector& /*lost_packets*/, + const Bbr2CongestionEvent& congestion_event) { + DCHECK_NE(cycle_.phase, CyclePhase::PROBE_NOT_STARTED); + + if (congestion_event.end_of_round_trip) { + if (cycle_.cycle_start_time != event_time) { + ++cycle_.rounds_since_probe; + } + if (cycle_.phase_start_time != event_time) { + ++cycle_.rounds_in_phase; + } + } + + if (cycle_.phase == CyclePhase::PROBE_UP) { + UpdateProbeUp(prior_in_flight, congestion_event); + } else if (cycle_.phase == CyclePhase::PROBE_DOWN) { + UpdateProbeDown(prior_in_flight, congestion_event); + // Maybe transition to PROBE_RTT at the end of this cycle. + if (cycle_.phase != CyclePhase::PROBE_DOWN && + model_->MaybeExpireMinRtt(congestion_event)) { + return Bbr2Mode::PROBE_RTT; + } + } else if (cycle_.phase == CyclePhase::PROBE_CRUISE) { + UpdateProbeCruise(congestion_event); + } else if (cycle_.phase == CyclePhase::PROBE_REFILL) { + UpdateProbeRefill(congestion_event); + } + + model_->set_pacing_gain(PacingGainForPhase(cycle_.phase)); + model_->set_cwnd_gain(Params().probe_bw_cwnd_gain); + + return Bbr2Mode::PROBE_BW; +} + +Limits<QuicByteCount> Bbr2ProbeBwMode::GetCwndLimits() const { + if (cycle_.phase == CyclePhase::PROBE_CRUISE) { + return NoGreaterThan( + std::min(model_->inflight_lo(), model_->inflight_hi_with_headroom())); + } + + return NoGreaterThan(std::min(model_->inflight_lo(), model_->inflight_hi())); +} + +bool Bbr2ProbeBwMode::IsProbingForBandwidth() const { + return cycle_.phase == CyclePhase::PROBE_REFILL || + cycle_.phase == CyclePhase::PROBE_UP; +} + +void Bbr2ProbeBwMode::UpdateProbeDown( + QuicByteCount prior_in_flight, + const Bbr2CongestionEvent& congestion_event) { + DCHECK_EQ(cycle_.phase, CyclePhase::PROBE_DOWN); + + if (cycle_.rounds_in_phase == 1 && congestion_event.end_of_round_trip) { + cycle_.is_sample_from_probing = false; + + if (!congestion_event.last_sample_is_app_limited) { + QUIC_DVLOG(2) + << sender_ + << " Advancing max bw filter after one round in PROBE_DOWN."; + model_->AdvanceMaxBandwidthFilter(); + cycle_.has_advanced_max_bw = true; + } + + if (last_cycle_stopped_risky_probe_ && !last_cycle_probed_too_high_) { + EnterProbeRefill(/*probe_up_rounds=*/0, congestion_event); + return; + } + } + + MaybeAdaptUpperBounds(congestion_event); + + if (IsTimeToProbeBandwidth(congestion_event)) { + EnterProbeRefill(/*probe_up_rounds=*/0, congestion_event); + return; + } + + if (HasStayedLongEnoughInProbeDown(congestion_event)) { + QUIC_DVLOG(3) << sender_ << " Proportional time based PROBE_DOWN exit"; + EnterProbeCruise(congestion_event); + return; + } + + const QuicByteCount inflight_with_headroom = + model_->inflight_hi_with_headroom(); + QUIC_DVLOG(3) + << sender_ + << " Checking if have enough inflight headroom. prior_in_flight:" + << prior_in_flight + << ", inflight_with_headroom:" << inflight_with_headroom; + if (prior_in_flight > inflight_with_headroom) { + // Stay in PROBE_DOWN. + return; + } + + // Transition to PROBE_CRUISE iff we've drained to target. + QuicByteCount bdp = model_->BDP(model_->MaxBandwidth()); + QUIC_DVLOG(3) << sender_ << " Checking if drained to target. prior_in_flight:" + << prior_in_flight << ", bdp:" << bdp; + if (prior_in_flight < bdp) { + EnterProbeCruise(congestion_event); + } +} + +Bbr2ProbeBwMode::AdaptUpperBoundsResult Bbr2ProbeBwMode::MaybeAdaptUpperBounds( + const Bbr2CongestionEvent& congestion_event) { + const SendTimeState& send_state = SendStateOfLargestPacket(congestion_event); + if (!send_state.is_valid) { + QUIC_DVLOG(3) << sender_ << " " << cycle_.phase + << ": NOT_ADAPTED_INVALID_SAMPLE"; + return NOT_ADAPTED_INVALID_SAMPLE; + } + + if (model_->IsInflightTooHigh(congestion_event)) { + if (cycle_.is_sample_from_probing) { + cycle_.is_sample_from_probing = false; + + if (!send_state.is_app_limited) { + QuicByteCount inflight_at_send = BytesInFlight(send_state); + model_->set_inflight_hi(inflight_at_send); + } + + QUIC_DVLOG(3) << sender_ << " " << cycle_.phase + << ": ADAPTED_PROBED_TOO_HIGH"; + return ADAPTED_PROBED_TOO_HIGH; + } + return ADAPTED_OK; + } + + if (model_->inflight_hi() == model_->inflight_hi_default()) { + QUIC_DVLOG(3) << sender_ << " " << cycle_.phase + << ": NOT_ADAPTED_INFLIGHT_HIGH_NOT_SET"; + return NOT_ADAPTED_INFLIGHT_HIGH_NOT_SET; + } + + const QuicByteCount inflight_at_send = BytesInFlight(send_state); + + // Raise the upper bound for inflight. + if (inflight_at_send > model_->inflight_hi()) { + QUIC_DVLOG(3) + << sender_ << " " << cycle_.phase + << ": Adapting inflight_hi from inflight_at_send. inflight_at_send:" + << inflight_at_send << ", old inflight_hi:" << model_->inflight_hi(); + model_->set_inflight_hi(inflight_at_send); + } + + return ADAPTED_OK; +} + +bool Bbr2ProbeBwMode::IsTimeToProbeBandwidth( + const Bbr2CongestionEvent& congestion_event) const { + return HasCycleLasted(cycle_.probe_wait_time, congestion_event) || + IsTimeToProbeForRenoCoexistence(1.0, congestion_event); +} + +// QUIC only. Used to prevent a Bbr2 flow from staying in PROBE_DOWN for too +// long, as seen in some multi-sender simulator tests. +bool Bbr2ProbeBwMode::HasStayedLongEnoughInProbeDown( + const Bbr2CongestionEvent& congestion_event) const { + // The amount of time to stay in PROBE_DOWN, as a fraction of probe wait time. + const double kProbeWaitFraction = 0.2; + return HasCycleLasted(cycle_.probe_wait_time * kProbeWaitFraction, + congestion_event) || + IsTimeToProbeForRenoCoexistence(kProbeWaitFraction, congestion_event); +} + +bool Bbr2ProbeBwMode::HasCycleLasted( + QuicTime::Delta duration, + const Bbr2CongestionEvent& congestion_event) const { + bool result = + (congestion_event.event_time - cycle_.cycle_start_time) > duration; + QUIC_DVLOG(3) << sender_ << " " << cycle_.phase + << ": HasCycleLasted=" << result << ". elapsed:" + << (congestion_event.event_time - cycle_.cycle_start_time) + << ", duration:" << duration; + return result; +} + +bool Bbr2ProbeBwMode::HasPhaseLasted( + QuicTime::Delta duration, + const Bbr2CongestionEvent& congestion_event) const { + bool result = + (congestion_event.event_time - cycle_.phase_start_time) > duration; + QUIC_DVLOG(3) << sender_ << " " << cycle_.phase + << ": HasPhaseLasted=" << result << ". elapsed:" + << (congestion_event.event_time - cycle_.phase_start_time) + << ", duration:" << duration; + return result; +} + +bool Bbr2ProbeBwMode::IsTimeToProbeForRenoCoexistence( + double probe_wait_fraction, + const Bbr2CongestionEvent& /*congestion_event*/) const { + uint64_t rounds = Params().probe_bw_probe_max_rounds; + if (Params().probe_bw_probe_reno_gain > 0.0) { + QuicByteCount bdp = model_->BDP(model_->BandwidthEstimate()); + QuicByteCount inflight_bytes = + std::min(bdp, sender_->GetCongestionWindow()); + uint64_t reno_rounds = + Params().probe_bw_probe_reno_gain * inflight_bytes / kDefaultTCPMSS; + rounds = std::min(rounds, reno_rounds); + } + bool result = cycle_.rounds_since_probe >= (rounds * probe_wait_fraction); + QUIC_DVLOG(3) << sender_ << " " << cycle_.phase + << ": IsTimeToProbeForRenoCoexistence=" << result + << ". rounds_since_probe:" << cycle_.rounds_since_probe + << ", rounds:" << rounds + << ", probe_wait_fraction:" << probe_wait_fraction; + return result; +} + +void Bbr2ProbeBwMode::RaiseInflightHighSlope() { + DCHECK_EQ(cycle_.phase, CyclePhase::PROBE_UP); + uint64_t growth_this_round = 1 << cycle_.probe_up_rounds; + // The number 30 below means |growth_this_round| is capped at 1G and the lower + // bound of |probe_up_bytes| is (practically) 1 mss, at this speed inflight_hi + // grows by approximately 1 packet per packet acked. + cycle_.probe_up_rounds = std::min<uint64_t>(cycle_.probe_up_rounds + 1, 30); + uint64_t probe_up_bytes = sender_->GetCongestionWindow() / growth_this_round; + cycle_.probe_up_bytes = + std::max<QuicByteCount>(probe_up_bytes, kDefaultTCPMSS); + QUIC_DVLOG(3) << sender_ << " Rasing inflight_hi slope. probe_up_rounds:" + << cycle_.probe_up_rounds + << ", probe_up_bytes:" << cycle_.probe_up_bytes; +} + +void Bbr2ProbeBwMode::ProbeInflightHighUpward( + const Bbr2CongestionEvent& congestion_event) { + DCHECK_EQ(cycle_.phase, CyclePhase::PROBE_UP); + if (!model_->IsCongestionWindowLimited(congestion_event)) { + QUIC_DVLOG(3) << sender_ + << " Rasing inflight_hi early return: Not cwnd limited."; + // Not fully utilizing cwnd, so can't safely grow. + return; + } + + // Increase inflight_hi by the number of probe_up_bytes within probe_up_acked. + cycle_.probe_up_acked += congestion_event.bytes_acked; + if (cycle_.probe_up_acked >= cycle_.probe_up_bytes) { + uint64_t delta = cycle_.probe_up_acked / cycle_.probe_up_bytes; + cycle_.probe_up_acked -= delta * cycle_.probe_up_bytes; + QUIC_DVLOG(3) << sender_ << " Rasing inflight_hi from " + << model_->inflight_hi() << " to " + << model_->inflight_hi() + delta * kDefaultTCPMSS + << ". probe_up_bytes:" << cycle_.probe_up_bytes + << ", delta:" << delta + << ", (new)probe_up_acked:" << cycle_.probe_up_acked; + model_->set_inflight_hi(model_->inflight_hi() + delta * kDefaultTCPMSS); + } + + if (congestion_event.end_of_round_trip) { + RaiseInflightHighSlope(); + } +} + +void Bbr2ProbeBwMode::UpdateProbeCruise( + const Bbr2CongestionEvent& congestion_event) { + DCHECK_EQ(cycle_.phase, CyclePhase::PROBE_CRUISE); + MaybeAdaptUpperBounds(congestion_event); + DCHECK(!cycle_.is_sample_from_probing); + + if (IsTimeToProbeBandwidth(congestion_event)) { + EnterProbeRefill(/*probe_up_rounds=*/0, congestion_event); + return; + } +} + +void Bbr2ProbeBwMode::UpdateProbeRefill( + const Bbr2CongestionEvent& congestion_event) { + DCHECK_EQ(cycle_.phase, CyclePhase::PROBE_REFILL); + MaybeAdaptUpperBounds(congestion_event); + DCHECK(!cycle_.is_sample_from_probing); + + if (cycle_.rounds_in_phase > 0 && congestion_event.end_of_round_trip) { + EnterProbeUp(congestion_event); + return; + } +} + +void Bbr2ProbeBwMode::UpdateProbeUp( + QuicByteCount prior_in_flight, + const Bbr2CongestionEvent& congestion_event) { + DCHECK_EQ(cycle_.phase, CyclePhase::PROBE_UP); + if (MaybeAdaptUpperBounds(congestion_event) == ADAPTED_PROBED_TOO_HIGH) { + EnterProbeDown(/*probed_too_high=*/true, /*stopped_risky_probe=*/false, + congestion_event); + return; + } + + // TODO(wub): Consider exit PROBE_UP after a certain number(e.g. 64) of RTTs. + + ProbeInflightHighUpward(congestion_event); + + bool is_risky = false; + bool is_queuing = false; + if (last_cycle_probed_too_high_ && prior_in_flight >= model_->inflight_hi()) { + is_risky = true; + QUIC_DVLOG(3) << sender_ + << " Probe is too risky. last_cycle_probed_too_high_:" + << last_cycle_probed_too_high_ + << ", prior_in_flight:" << prior_in_flight + << ", inflight_hi:" << model_->inflight_hi(); + // TCP uses min_rtt instead of a full round: + // HasPhaseLasted(model_->MinRtt(), congestion_event) + } else if (cycle_.rounds_in_phase > 0) { + QuicByteCount bdp = model_->BDP(model_->MaxBandwidth()); + QuicByteCount queuing_threshold = + (Params().probe_bw_probe_inflight_gain * bdp) + 2 * kDefaultTCPMSS; + is_queuing = prior_in_flight >= queuing_threshold; + QUIC_DVLOG(3) << sender_ + << " Checking if building up a queue. prior_in_flight:" + << prior_in_flight << ", threshold:" << queuing_threshold + << ", is_queuing:" << is_queuing + << ", max_bw:" << model_->MaxBandwidth() + << ", min_rtt:" << model_->MinRtt(); + } + + if (is_risky || is_queuing) { + EnterProbeDown(/*probed_too_high=*/false, /*stopped_risky_probe=*/is_risky, + congestion_event); + } +} + +void Bbr2ProbeBwMode::EnterProbeDown( + bool probed_too_high, + bool stopped_risky_probe, + const Bbr2CongestionEvent& congestion_event) { + QUIC_DVLOG(2) << sender_ << " Phase change: " << cycle_.phase << " ==> " + << CyclePhase::PROBE_DOWN << " after " + << congestion_event.event_time - cycle_.phase_start_time + << ", or " << cycle_.rounds_in_phase + << " rounds. probed_too_high:" << probed_too_high + << ", stopped_risky_probe:" << stopped_risky_probe << " @ " + << congestion_event.event_time; + last_cycle_probed_too_high_ = probed_too_high; + last_cycle_stopped_risky_probe_ = stopped_risky_probe; + + cycle_.cycle_start_time = congestion_event.event_time; + cycle_.phase = CyclePhase::PROBE_DOWN; + cycle_.rounds_in_phase = 0; + cycle_.phase_start_time = congestion_event.event_time; + + // Pick probe wait time. + cycle_.rounds_since_probe = + sender_->RandomUint64(Params().probe_bw_max_probe_rand_rounds); + cycle_.probe_wait_time = + Params().probe_bw_probe_base_duration + + QuicTime::Delta::FromMicroseconds(sender_->RandomUint64( + Params().probe_bw_probe_max_rand_duration.ToMicroseconds())); + + cycle_.probe_up_bytes = std::numeric_limits<QuicByteCount>::max(); + cycle_.has_advanced_max_bw = false; + model_->RestartRound(); +} + +void Bbr2ProbeBwMode::EnterProbeCruise( + const Bbr2CongestionEvent& congestion_event) { + if (cycle_.phase == CyclePhase::PROBE_DOWN) { + ExitProbeDown(congestion_event); + } + QUIC_DVLOG(2) << sender_ << " Phase change: " << cycle_.phase << " ==> " + << CyclePhase::PROBE_CRUISE << " after " + << congestion_event.event_time - cycle_.phase_start_time + << ", or " << cycle_.rounds_in_phase << " rounds. @ " + << congestion_event.event_time; + cycle_.phase = CyclePhase::PROBE_CRUISE; + cycle_.rounds_in_phase = 0; + cycle_.phase_start_time = congestion_event.event_time; + cycle_.is_sample_from_probing = false; +} + +void Bbr2ProbeBwMode::EnterProbeRefill( + uint64_t probe_up_rounds, + const Bbr2CongestionEvent& congestion_event) { + if (cycle_.phase == CyclePhase::PROBE_DOWN) { + ExitProbeDown(congestion_event); + } + QUIC_DVLOG(2) << sender_ << " Phase change: " << cycle_.phase << " ==> " + << CyclePhase::PROBE_REFILL << " after " + << congestion_event.event_time - cycle_.phase_start_time + << ", or " << cycle_.rounds_in_phase + << " rounds. probe_up_rounds:" << probe_up_rounds << " @ " + << congestion_event.event_time; + cycle_.phase = CyclePhase::PROBE_REFILL; + cycle_.rounds_in_phase = 0; + cycle_.phase_start_time = congestion_event.event_time; + cycle_.is_sample_from_probing = false; + last_cycle_stopped_risky_probe_ = false; + + model_->clear_bandwidth_lo(); + model_->clear_inflight_lo(); + cycle_.probe_up_rounds = probe_up_rounds; + cycle_.probe_up_acked = 0; + model_->RestartRound(); +} + +void Bbr2ProbeBwMode::EnterProbeUp( + const Bbr2CongestionEvent& congestion_event) { + DCHECK_EQ(cycle_.phase, CyclePhase::PROBE_REFILL); + QUIC_DVLOG(2) << sender_ << " Phase change: " << cycle_.phase << " ==> " + << CyclePhase::PROBE_UP << " after " + << congestion_event.event_time - cycle_.phase_start_time + << ", or " << cycle_.rounds_in_phase << " rounds. @ " + << congestion_event.event_time; + cycle_.phase = CyclePhase::PROBE_UP; + cycle_.rounds_in_phase = 0; + cycle_.phase_start_time = congestion_event.event_time; + cycle_.is_sample_from_probing = true; + RaiseInflightHighSlope(); + + model_->RestartRound(); +} + +void Bbr2ProbeBwMode::ExitProbeDown( + const Bbr2CongestionEvent& /*congestion_event*/) { + DCHECK_EQ(cycle_.phase, CyclePhase::PROBE_DOWN); + if (!cycle_.has_advanced_max_bw) { + QUIC_DVLOG(2) << sender_ << " Advancing max bw filter at end of cycle."; + model_->AdvanceMaxBandwidthFilter(); + cycle_.has_advanced_max_bw = true; + } +} + +// static +const char* Bbr2ProbeBwMode::CyclePhaseToString(CyclePhase phase) { + switch (phase) { + case CyclePhase::PROBE_NOT_STARTED: + return "PROBE_NOT_STARTED"; + case CyclePhase::PROBE_UP: + return "PROBE_UP"; + case CyclePhase::PROBE_DOWN: + return "PROBE_DOWN"; + case CyclePhase::PROBE_CRUISE: + return "PROBE_CRUISE"; + case CyclePhase::PROBE_REFILL: + return "PROBE_REFILL"; + default: + break; + } + return "<Invalid CyclePhase>"; +} + +std::ostream& operator<<(std::ostream& os, + const Bbr2ProbeBwMode::CyclePhase phase) { + return os << Bbr2ProbeBwMode::CyclePhaseToString(phase); +} + +Bbr2ProbeBwMode::DebugState Bbr2ProbeBwMode::ExportDebugState() const { + DebugState s; + s.phase = cycle_.phase; + s.cycle_start_time = cycle_.cycle_start_time; + s.phase_start_time = cycle_.phase_start_time; + return s; +} + +std::ostream& operator<<(std::ostream& os, + const Bbr2ProbeBwMode::DebugState& state) { + os << "[PROBE_BW] phase: " << state.phase << "\n"; + os << "[PROBE_BW] cycle_start_time: " << state.cycle_start_time << "\n"; + os << "[PROBE_BW] phase_start_time: " << state.phase_start_time << "\n"; + return os; +} + +const Bbr2Params& Bbr2ProbeBwMode::Params() const { + return sender_->Params(); +} + +float Bbr2ProbeBwMode::PacingGainForPhase( + Bbr2ProbeBwMode::CyclePhase phase) const { + if (phase == Bbr2ProbeBwMode::CyclePhase::PROBE_UP) { + return Params().probe_bw_probe_up_pacing_gain; + } + if (phase == Bbr2ProbeBwMode::CyclePhase::PROBE_DOWN) { + return Params().probe_bw_probe_down_pacing_gain; + } + return Params().probe_bw_default_pacing_gain; +} + +} // namespace quic
diff --git a/quic/core/congestion_control/bbr2_probe_bw.h b/quic/core/congestion_control/bbr2_probe_bw.h new file mode 100644 index 0000000..407056b --- /dev/null +++ b/quic/core/congestion_control/bbr2_probe_bw.h
@@ -0,0 +1,135 @@ +// Copyright 2019 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. + +#ifndef QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_PROBE_BW_H_ +#define QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_PROBE_BW_H_ + +#include <cstdint> + +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_misc.h" +#include "net/third_party/quiche/src/quic/core/quic_time.h" +#include "net/third_party/quiche/src/quic/core/quic_types.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_export.h" + +namespace quic { + +class Bbr2Sender; +class QUIC_EXPORT_PRIVATE Bbr2ProbeBwMode final : public Bbr2ModeBase { + public: + using Bbr2ModeBase::Bbr2ModeBase; + + void Enter(const Bbr2CongestionEvent& congestion_event) override; + + Bbr2Mode OnCongestionEvent( + QuicByteCount prior_in_flight, + QuicTime event_time, + const AckedPacketVector& acked_packets, + const LostPacketVector& lost_packets, + const Bbr2CongestionEvent& congestion_event) override; + + Limits<QuicByteCount> GetCwndLimits() const override; + + bool IsProbingForBandwidth() const override; + + enum class CyclePhase : uint8_t { + PROBE_NOT_STARTED, + PROBE_UP, + PROBE_DOWN, + PROBE_CRUISE, + PROBE_REFILL, + }; + + static const char* CyclePhaseToString(CyclePhase phase); + + struct DebugState { + CyclePhase phase; + QuicTime cycle_start_time = QuicTime::Zero(); + QuicTime phase_start_time = QuicTime::Zero(); + }; + + DebugState ExportDebugState() const; + + private: + const Bbr2Params& Params() const; + float PacingGainForPhase(CyclePhase phase) const; + + void UpdateProbeUp(QuicByteCount prior_in_flight, + const Bbr2CongestionEvent& congestion_event); + void UpdateProbeDown(QuicByteCount prior_in_flight, + const Bbr2CongestionEvent& congestion_event); + void UpdateProbeCruise(const Bbr2CongestionEvent& congestion_event); + void UpdateProbeRefill(const Bbr2CongestionEvent& congestion_event); + + enum AdaptUpperBoundsResult : uint8_t { + ADAPTED_OK, + ADAPTED_PROBED_TOO_HIGH, + NOT_ADAPTED_INFLIGHT_HIGH_NOT_SET, + NOT_ADAPTED_INVALID_SAMPLE, + }; + + // Return whether adapted inflight_hi. If inflight is too high, this function + // will not adapt inflight_hi and will return false. + AdaptUpperBoundsResult MaybeAdaptUpperBounds( + const Bbr2CongestionEvent& congestion_event); + + void EnterProbeDown(bool probed_too_high, + bool stopped_risky_probe, + const Bbr2CongestionEvent& congestion_event); + void EnterProbeCruise(const Bbr2CongestionEvent& congestion_event); + void EnterProbeRefill(uint64_t probe_up_rounds, + const Bbr2CongestionEvent& congestion_event); + void EnterProbeUp(const Bbr2CongestionEvent& congestion_event); + + // Call right before the exit of PROBE_DOWN. + void ExitProbeDown(const Bbr2CongestionEvent& congestion_event); + + float PercentTimeElapsedToProbeBandwidth( + const Bbr2CongestionEvent& congestion_event) const; + + bool IsTimeToProbeBandwidth( + const Bbr2CongestionEvent& congestion_event) const; + bool HasStayedLongEnoughInProbeDown( + const Bbr2CongestionEvent& congestion_event) const; + bool HasCycleLasted(QuicTime::Delta duration, + const Bbr2CongestionEvent& congestion_event) const; + bool HasPhaseLasted(QuicTime::Delta duration, + const Bbr2CongestionEvent& congestion_event) const; + bool IsTimeToProbeForRenoCoexistence( + double probe_wait_fraction, + const Bbr2CongestionEvent& congestion_event) const; + + void RaiseInflightHighSlope(); + void ProbeInflightHighUpward(const Bbr2CongestionEvent& congestion_event); + + struct Cycle { + QuicTime cycle_start_time = QuicTime::Zero(); + CyclePhase phase = CyclePhase::PROBE_NOT_STARTED; + uint64_t rounds_in_phase = 0; + QuicTime phase_start_time = QuicTime::Zero(); + QuicRoundTripCount rounds_since_probe = 0; + QuicTime::Delta probe_wait_time = QuicTime::Delta::Zero(); + uint64_t probe_up_rounds = 0; + QuicByteCount probe_up_bytes = std::numeric_limits<QuicByteCount>::max(); + QuicByteCount probe_up_acked = 0; + // Whether max bandwidth filter window has advanced in this cycle. It is + // advanced once per cycle. + bool has_advanced_max_bw = false; + bool is_sample_from_probing = false; + } cycle_; + + bool last_cycle_probed_too_high_; + bool last_cycle_stopped_risky_probe_; +}; + +QUIC_EXPORT_PRIVATE std::ostream& operator<<( + std::ostream& os, + const Bbr2ProbeBwMode::DebugState& state); + +QUIC_EXPORT_PRIVATE std::ostream& operator<<( + std::ostream& os, + const Bbr2ProbeBwMode::CyclePhase phase); + +} // namespace quic + +#endif // QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_PROBE_BW_H_
diff --git a/quic/core/congestion_control/bbr2_probe_rtt.cc b/quic/core/congestion_control/bbr2_probe_rtt.cc new file mode 100644 index 0000000..fe4506b --- /dev/null +++ b/quic/core/congestion_control/bbr2_probe_rtt.cc
@@ -0,0 +1,66 @@ +// Copyright 2019 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. + +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_probe_rtt.h" + +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_sender.h" +#include "net/third_party/quiche/src/quic/core/quic_time.h" + +namespace quic { + +void Bbr2ProbeRttMode::Enter(const Bbr2CongestionEvent& /*congestion_event*/) { + model_->set_pacing_gain(1.0); + model_->set_cwnd_gain(1.0); + exit_time_ = QuicTime::Zero(); +} + +Bbr2Mode Bbr2ProbeRttMode::OnCongestionEvent( + QuicByteCount /*prior_in_flight*/, + QuicTime /*event_time*/, + const AckedPacketVector& /*acked_packets*/, + const LostPacketVector& /*lost_packets*/, + const Bbr2CongestionEvent& congestion_event) { + if (exit_time_ == QuicTime::Zero()) { + if (congestion_event.bytes_in_flight <= InflightTarget() || + congestion_event.bytes_in_flight <= + sender_->GetMinimumCongestionWindow()) { + exit_time_ = congestion_event.event_time + Params().probe_rtt_duration; + } + return Bbr2Mode::PROBE_RTT; + } + + return congestion_event.event_time > exit_time_ ? Bbr2Mode::PROBE_BW + : Bbr2Mode::PROBE_RTT; +} + +QuicByteCount Bbr2ProbeRttMode::InflightTarget() const { + return model_->BDP(model_->MaxBandwidth(), + Params().probe_rtt_inflight_target_bdp_fraction); +} + +Limits<QuicByteCount> Bbr2ProbeRttMode::GetCwndLimits() const { + QuicByteCount inflight_upper_bound = + std::min(model_->inflight_lo(), model_->inflight_hi_with_headroom()); + return NoGreaterThan(std::min(inflight_upper_bound, InflightTarget())); +} + +Bbr2ProbeRttMode::DebugState Bbr2ProbeRttMode::ExportDebugState() const { + DebugState s; + s.inflight_target = InflightTarget(); + s.exit_time = exit_time_; + return s; +} + +std::ostream& operator<<(std::ostream& os, + const Bbr2ProbeRttMode::DebugState& state) { + os << "[PROBE_RTT] inflight_target: " << state.inflight_target << "\n"; + os << "[PROBE_RTT] exit_time: " << state.exit_time << "\n"; + return os; +} + +const Bbr2Params& Bbr2ProbeRttMode::Params() const { + return sender_->Params(); +} + +} // namespace quic
diff --git a/quic/core/congestion_control/bbr2_probe_rtt.h b/quic/core/congestion_control/bbr2_probe_rtt.h new file mode 100644 index 0000000..811c646 --- /dev/null +++ b/quic/core/congestion_control/bbr2_probe_rtt.h
@@ -0,0 +1,54 @@ +// Copyright 2019 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. + +#ifndef QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_PROBE_RTT_H_ +#define QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_PROBE_RTT_H_ + +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_misc.h" +#include "net/third_party/quiche/src/quic/core/quic_time.h" +#include "net/third_party/quiche/src/quic/core/quic_types.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_export.h" + +namespace quic { + +class Bbr2Sender; +class QUIC_EXPORT_PRIVATE Bbr2ProbeRttMode final : public Bbr2ModeBase { + public: + using Bbr2ModeBase::Bbr2ModeBase; + + void Enter(const Bbr2CongestionEvent& congestion_event) override; + + Bbr2Mode OnCongestionEvent( + QuicByteCount prior_in_flight, + QuicTime event_time, + const AckedPacketVector& acked_packets, + const LostPacketVector& lost_packets, + const Bbr2CongestionEvent& congestion_event) override; + + Limits<QuicByteCount> GetCwndLimits() const override; + + bool IsProbingForBandwidth() const override { return false; } + + struct DebugState { + QuicByteCount inflight_target; + QuicTime exit_time = QuicTime::Zero(); + }; + + DebugState ExportDebugState() const; + + private: + const Bbr2Params& Params() const; + + QuicByteCount InflightTarget() const; + + QuicTime exit_time_ = QuicTime::Zero(); +}; + +QUIC_EXPORT_PRIVATE std::ostream& operator<<( + std::ostream& os, + const Bbr2ProbeRttMode::DebugState& state); + +} // namespace quic + +#endif // QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_PROBE_RTT_H_
diff --git a/quic/core/congestion_control/bbr2_sender.cc b/quic/core/congestion_control/bbr2_sender.cc new file mode 100644 index 0000000..66aa123 --- /dev/null +++ b/quic/core/congestion_control/bbr2_sender.cc
@@ -0,0 +1,410 @@ +// Copyright 2019 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. + +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_sender.h" + +#include <cstddef> + +#include "net/third_party/quiche/src/quic/core/congestion_control/bandwidth_sampler.h" +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_drain.h" +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_misc.h" +#include "net/third_party/quiche/src/quic/core/crypto/crypto_protocol.h" +#include "net/third_party/quiche/src/quic/core/quic_bandwidth.h" +#include "net/third_party/quiche/src/quic/core/quic_types.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_logging.h" + +namespace quic { + +namespace { +// Constants based on TCP defaults. +// The minimum CWND to ensure delayed acks don't reduce bandwidth measurements. +// Does not inflate the pacing rate. +const QuicByteCount kDefaultMinimumCongestionWindow = 4 * kMaxSegmentSize; + +const float kInitialPacingGain = 2.885f; + +const int kMaxModeChangesPerCongestionEvent = 4; +} // namespace + +// Call |member_function_call| based on the current Bbr2Mode we are in. e.g. +// +// auto result = BBR2_MODE_DISPATCH(Foo()); +// +// is equivalent to: +// +// Bbr2ModeBase& Bbr2Sender::GetCurrentMode() { +// if (mode_ == Bbr2Mode::STARTUP) { return startup_; } +// if (mode_ == Bbr2Mode::DRAIN) { return drain_; } +// ... +// } +// auto result = GetCurrentMode().Foo(); +// +// Except that BBR2_MODE_DISPATCH guarantees the call to Foo() is non-virtual. +// +#define BBR2_MODE_DISPATCH(member_function_call) \ + (mode_ == Bbr2Mode::STARTUP \ + ? (startup_.member_function_call) \ + : (mode_ == Bbr2Mode::PROBE_BW \ + ? (probe_bw_.member_function_call) \ + : (mode_ == Bbr2Mode::DRAIN \ + ? (drain_.member_function_call) \ + : (probe_rtt_or_die().member_function_call)))) + +Bbr2Sender::Bbr2Sender(QuicTime now, + const RttStats* rtt_stats, + const QuicUnackedPacketMap* unacked_packets, + QuicPacketCount initial_cwnd_in_packets, + QuicPacketCount max_cwnd_in_packets, + QuicRandom* random, + QuicConnectionStats* /*stats*/) + : mode_(Bbr2Mode::STARTUP), + rtt_stats_(rtt_stats), + unacked_packets_(unacked_packets), + random_(random), + params_(kDefaultMinimumCongestionWindow, + max_cwnd_in_packets * kDefaultTCPMSS), + model_(¶ms_, + rtt_stats->SmoothedOrInitialRtt(), + rtt_stats->last_update_time(), + /*cwnd_gain=*/1.0, + /*pacing_gain=*/kInitialPacingGain), + cwnd_( + cwnd_limits().ApplyLimits(initial_cwnd_in_packets * kDefaultTCPMSS)), + pacing_rate_(kInitialPacingGain * QuicBandwidth::FromBytesAndTimeDelta( + cwnd_, + rtt_stats->SmoothedOrInitialRtt())), + startup_(this, &model_), + drain_(this, &model_), + probe_bw_(this, &model_), + probe_rtt_(this, &model_), + flexible_app_limited_(false), + last_sample_is_app_limited_(false) { + QUIC_DVLOG(2) << this << " Initializing Bbr2Sender. mode:" << mode_ + << ", PacingRate:" << pacing_rate_ << ", Cwnd:" << cwnd_ + << ", CwndLimits:" << cwnd_limits() << " @ " << now; + DCHECK_EQ(mode_, Bbr2Mode::STARTUP); +} + +void Bbr2Sender::SetFromConfig(const QuicConfig& config, + Perspective perspective) { + if (config.HasClientRequestedIndependentOption(kBBR9, perspective)) { + flexible_app_limited_ = true; + } +} + +Limits<QuicByteCount> Bbr2Sender::GetCwndLimitsByMode() const { + switch (mode_) { + case Bbr2Mode::STARTUP: + return startup_.GetCwndLimits(); + case Bbr2Mode::PROBE_BW: + return probe_bw_.GetCwndLimits(); + case Bbr2Mode::DRAIN: + return drain_.GetCwndLimits(); + case Bbr2Mode::PROBE_RTT: + return probe_rtt_.GetCwndLimits(); + default: + QUIC_NOTREACHED(); + return Unlimited<QuicByteCount>(); + } +} + +const Limits<QuicByteCount>& Bbr2Sender::cwnd_limits() const { + return params_.cwnd_limits; +} + +void Bbr2Sender::AdjustNetworkParameters(QuicBandwidth bandwidth, + QuicTime::Delta rtt, + bool allow_cwnd_to_decrease) { + model_.UpdateNetworkParameters(bandwidth, rtt); + + if (mode_ == Bbr2Mode::STARTUP) { + const QuicByteCount prior_cwnd = cwnd_; + + // Normally UpdateCongestionWindow updates |cwnd_| towards the target by a + // small step per congestion event, by changing |cwnd_| to the bdp at here + // we are reducing the number of updates needed to arrive at the target. + cwnd_ = model_.BDP(model_.BandwidthEstimate()); + UpdateCongestionWindow(0); + if (!allow_cwnd_to_decrease) { + cwnd_ = std::max(cwnd_, prior_cwnd); + } + } +} + +void Bbr2Sender::SetInitialCongestionWindowInPackets( + QuicPacketCount congestion_window) { + if (mode_ == Bbr2Mode::STARTUP) { + // The cwnd limits is unchanged and still applies to the new cwnd. + cwnd_ = cwnd_limits().ApplyLimits(congestion_window * kDefaultTCPMSS); + } +} + +void Bbr2Sender::OnCongestionEvent(bool /*rtt_updated*/, + QuicByteCount prior_in_flight, + QuicTime event_time, + const AckedPacketVector& acked_packets, + const LostPacketVector& lost_packets) { + QUIC_DVLOG(3) << this + << " OnCongestionEvent. prior_in_flight:" << prior_in_flight + << " prior_cwnd:" << cwnd_ << " @ " << event_time; + Bbr2CongestionEvent congestion_event; + congestion_event.prior_cwnd = cwnd_; + congestion_event.is_probing_for_bandwidth = + BBR2_MODE_DISPATCH(IsProbingForBandwidth()); + + model_.OnCongestionEventStart(event_time, acked_packets, lost_packets, + &congestion_event); + + // Number of mode changes allowed for this congestion event. + int mode_changes_allowed = kMaxModeChangesPerCongestionEvent; + while (true) { + Bbr2Mode next_mode = BBR2_MODE_DISPATCH( + OnCongestionEvent(prior_in_flight, event_time, acked_packets, + lost_packets, congestion_event)); + + if (next_mode == mode_) { + break; + } + + QUIC_DVLOG(2) << this << " Mode change: " << mode_ << " ==> " << next_mode + << " @ " << event_time; + mode_ = next_mode; + BBR2_MODE_DISPATCH(Enter(congestion_event)); + --mode_changes_allowed; + if (mode_changes_allowed < 0) { + QUIC_BUG << "Exceeded max number of mode changes per congestion event."; + break; + } + } + + UpdatePacingRate(congestion_event.bytes_acked); + QUIC_BUG_IF(pacing_rate_.IsZero()) << "Pacing rate must not be zero!"; + + UpdateCongestionWindow(congestion_event.bytes_acked); + QUIC_BUG_IF(cwnd_ == 0u) << "Congestion window must not be zero!"; + + model_.OnCongestionEventFinish(unacked_packets_->GetLeastUnacked(), + congestion_event); + last_sample_is_app_limited_ = congestion_event.last_sample_is_app_limited; + + QUIC_DVLOG(3) + << this << " END CongestionEvent(acked:" << acked_packets + << ", lost:" << lost_packets.size() << ") " + << ", Mode:" << mode_ << ", RttCount:" << model_.RoundTripCount() + << ", BytesInFlight:" << model_.bytes_in_flight() + << ", PacingRate:" << PacingRate(0) << ", CWND:" << GetCongestionWindow() + << ", PacingGain:" << model_.pacing_gain() + << ", CwndGain:" << model_.cwnd_gain() + << ", BandwidthEstimate(kbps):" << BandwidthEstimate().ToKBitsPerSecond() + << ", MinRTT(us):" << model_.MinRtt().ToMicroseconds() + << ", BDP:" << model_.BDP(BandwidthEstimate()) + << ", BandwidthLatest(kbps):" + << model_.bandwidth_latest().ToKBitsPerSecond() + << ", BandwidthLow(kbps):" << model_.bandwidth_lo().ToKBitsPerSecond() + << ", BandwidthHigh(kbps):" << model_.MaxBandwidth().ToKBitsPerSecond() + << ", InflightLatest:" << model_.inflight_latest() + << ", InflightLow:" << model_.inflight_lo() + << ", InflightHigh:" << model_.inflight_hi() + << ", TotalAcked:" << model_.total_bytes_acked() + << ", TotalLost:" << model_.total_bytes_lost() + << ", TotalSent:" << model_.total_bytes_sent() << " @ " << event_time; +} + +void Bbr2Sender::UpdatePacingRate(QuicByteCount bytes_acked) { + if (BandwidthEstimate().IsZero()) { + return; + } + + if (model_.total_bytes_acked() == bytes_acked) { + // After the first ACK, cwnd_ is still the initial congestion window. + pacing_rate_ = QuicBandwidth::FromBytesAndTimeDelta(cwnd_, model_.MinRtt()); + return; + } + + QuicBandwidth target_rate = model_.pacing_gain() * model_.BandwidthEstimate(); + if (startup_.FullBandwidthReached()) { + pacing_rate_ = target_rate; + return; + } + + if (target_rate > pacing_rate_) { + pacing_rate_ = target_rate; + } +} + +void Bbr2Sender::UpdateCongestionWindow(QuicByteCount bytes_acked) { + QuicByteCount target_cwnd = GetTargetCongestionWindow(model_.cwnd_gain()); + + const QuicByteCount prior_cwnd = cwnd_; + if (startup_.FullBandwidthReached()) { + target_cwnd += model_.MaxAckHeight(); + cwnd_ = std::min(prior_cwnd + bytes_acked, target_cwnd); + } else if (prior_cwnd < target_cwnd || prior_cwnd < 2 * cwnd_limits().Min()) { + cwnd_ = prior_cwnd + bytes_acked; + } + const QuicByteCount desired_cwnd = cwnd_; + + cwnd_ = GetCwndLimitsByMode().ApplyLimits(cwnd_); + const QuicByteCount model_limited_cwnd = cwnd_; + + cwnd_ = cwnd_limits().ApplyLimits(cwnd_); + + QUIC_DVLOG(3) << this << " Updating CWND. target_cwnd:" << target_cwnd + << ", max_ack_height:" << model_.MaxAckHeight() + << ", full_bw:" << startup_.FullBandwidthReached() + << ", bytes_acked:" << bytes_acked + << ", inflight_lo:" << model_.inflight_lo() + << ", inflight_hi:" << model_.inflight_hi() << ". (prior_cwnd) " + << prior_cwnd << " => (desired_cwnd) " << desired_cwnd + << " => (model_limited_cwnd) " << model_limited_cwnd + << " => (final_cwnd) " << cwnd_; +} + +QuicByteCount Bbr2Sender::GetTargetCongestionWindow(float gain) const { + return std::max(model_.BDP(model_.BandwidthEstimate(), gain), + cwnd_limits().Min()); +} + +void Bbr2Sender::OnPacketSent(QuicTime sent_time, + QuicByteCount bytes_in_flight, + QuicPacketNumber packet_number, + QuicByteCount bytes, + HasRetransmittableData is_retransmittable) { + QUIC_DVLOG(3) << this << " OnPacketSent: pkn:" << packet_number + << ", bytes:" << bytes << ", cwnd:" << cwnd_ + << ", inflight:" << model_.bytes_in_flight() + bytes + << ", total_sent:" << model_.total_bytes_sent() + bytes + << ", total_acked:" << model_.total_bytes_acked() + << ", total_lost:" << model_.total_bytes_lost() << " @ " + << sent_time; + model_.OnPacketSent(sent_time, bytes_in_flight, packet_number, bytes, + is_retransmittable); +} + +bool Bbr2Sender::CanSend(QuicByteCount bytes_in_flight) { + const bool result = bytes_in_flight < GetCongestionWindow(); + return result; +} + +QuicByteCount Bbr2Sender::GetCongestionWindow() const { + // TODO(wub): Implement Recovery? + return cwnd_; +} + +QuicBandwidth Bbr2Sender::PacingRate(QuicByteCount /*bytes_in_flight*/) const { + return pacing_rate_; +} + +void Bbr2Sender::OnApplicationLimited(QuicByteCount bytes_in_flight) { + if (bytes_in_flight >= GetCongestionWindow()) { + return; + } + if (flexible_app_limited_ && IsPipeSufficientlyFull()) { + return; + } + + model_.OnApplicationLimited(); + QUIC_DVLOG(2) << this << " Becoming application limited. Last sent packet: " + << model_.last_sent_packet() + << ", CWND: " << GetCongestionWindow(); +} + +bool Bbr2Sender::ShouldSendProbingPacket() const { + // TODO(wub): Implement ShouldSendProbingPacket properly. + if (!BBR2_MODE_DISPATCH(IsProbingForBandwidth())) { + return false; + } + + // TODO(b/77975811): If the pipe is highly under-utilized, consider not + // sending a probing transmission, because the extra bandwidth is not needed. + // If flexible_app_limited is enabled, check if the pipe is sufficiently full. + if (flexible_app_limited_) { + const bool is_pipe_sufficiently_full = IsPipeSufficientlyFull(); + QUIC_DVLOG(3) << this << " CWND: " << GetCongestionWindow() + << ", inflight: " << model_.bytes_in_flight() + << ", pacing_rate: " << PacingRate(0) + << ", flexible_app_limited_: true, ShouldSendProbingPacket: " + << !is_pipe_sufficiently_full; + return !is_pipe_sufficiently_full; + } else { + return true; + } +} + +bool Bbr2Sender::IsPipeSufficientlyFull() const { + // See if we need more bytes in flight to see more bandwidth. + if (mode_ == Bbr2Mode::STARTUP) { + // STARTUP exits if it doesn't observe a 25% bandwidth increase, so the CWND + // must be more than 25% above the target. + return model_.bytes_in_flight() >= GetTargetCongestionWindow(1.5); + } + if (model_.pacing_gain() > 1) { + // Super-unity PROBE_BW doesn't exit until 1.25 * BDP is achieved. + return model_.bytes_in_flight() >= + GetTargetCongestionWindow(model_.pacing_gain()); + } + // If bytes_in_flight are above the target congestion window, it should be + // possible to observe the same or more bandwidth if it's available. + return model_.bytes_in_flight() >= GetTargetCongestionWindow(1.1); +} + +std::string Bbr2Sender::GetDebugState() const { + std::ostringstream stream; + stream << ExportDebugState(); + return stream.str(); +} + +Bbr2Sender::DebugState Bbr2Sender::ExportDebugState() const { + DebugState s; + s.mode = mode_; + s.round_trip_count = model_.RoundTripCount(); + s.bandwidth_hi = model_.MaxBandwidth(); + s.bandwidth_lo = model_.bandwidth_lo(); + s.bandwidth_est = BandwidthEstimate(); + s.min_rtt = model_.MinRtt(); + s.min_rtt_timestamp = model_.MinRttTimestamp(); + s.congestion_window = cwnd_; + s.pacing_rate = pacing_rate_; + s.last_sample_is_app_limited = last_sample_is_app_limited_; + s.end_of_app_limited_phase = model_.end_of_app_limited_phase(); + + s.startup = startup_.ExportDebugState(); + s.drain = drain_.ExportDebugState(); + s.probe_bw = probe_bw_.ExportDebugState(); + s.probe_rtt = probe_rtt_.ExportDebugState(); + + return s; +} + +std::ostream& operator<<(std::ostream& os, const Bbr2Sender::DebugState& s) { + os << "mode: " << s.mode << "\n"; + os << "round_trip_count: " << s.round_trip_count << "\n"; + os << "bandwidth_hi ~ lo ~ est: " << s.bandwidth_hi << " ~ " << s.bandwidth_lo + << " ~ " << s.bandwidth_est << "\n"; + os << "min_rtt: " << s.min_rtt << "\n"; + os << "min_rtt_timestamp: " << s.min_rtt_timestamp << "\n"; + os << "congestion_window: " << s.congestion_window << "\n"; + os << "pacing_rate: " << s.pacing_rate << "\n"; + os << "last_sample_is_app_limited: " << s.last_sample_is_app_limited << "\n"; + + if (s.mode == Bbr2Mode::STARTUP) { + os << s.startup; + } + + if (s.mode == Bbr2Mode::DRAIN) { + os << s.drain; + } + + if (s.mode == Bbr2Mode::PROBE_BW) { + os << s.probe_bw; + } + + if (s.mode == Bbr2Mode::PROBE_RTT) { + os << s.probe_rtt; + } + + return os; +} + +} // namespace quic
diff --git a/quic/core/congestion_control/bbr2_sender.h b/quic/core/congestion_control/bbr2_sender.h new file mode 100644 index 0000000..64f6347 --- /dev/null +++ b/quic/core/congestion_control/bbr2_sender.h
@@ -0,0 +1,192 @@ +// Copyright 2019 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. + +#ifndef QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_SENDER_H_ +#define QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_SENDER_H_ + +#include <cstdint> + +#include "net/third_party/quiche/src/quic/core/congestion_control/bandwidth_sampler.h" +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_drain.h" +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_misc.h" +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_probe_bw.h" +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_probe_rtt.h" +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_startup.h" +#include "net/third_party/quiche/src/quic/core/congestion_control/rtt_stats.h" +#include "net/third_party/quiche/src/quic/core/congestion_control/send_algorithm_interface.h" +#include "net/third_party/quiche/src/quic/core/congestion_control/windowed_filter.h" +#include "net/third_party/quiche/src/quic/core/quic_bandwidth.h" +#include "net/third_party/quiche/src/quic/core/quic_types.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_export.h" + +namespace quic { + +class QUIC_EXPORT_PRIVATE Bbr2Sender final : public SendAlgorithmInterface { + public: + Bbr2Sender(QuicTime now, + const RttStats* rtt_stats, + const QuicUnackedPacketMap* unacked_packets, + QuicPacketCount initial_cwnd_in_packets, + QuicPacketCount max_cwnd_in_packets, + QuicRandom* random, + QuicConnectionStats* /*stats*/); + + ~Bbr2Sender() override = default; + + // Start implementation of SendAlgorithmInterface. + bool InSlowStart() const override { return mode_ == Bbr2Mode::STARTUP; } + + bool InRecovery() const override { + // TODO(wub): Implement Recovery. + return false; + } + + bool ShouldSendProbingPacket() const override; + + void SetFromConfig(const QuicConfig& config, + Perspective perspective) override; + + void AdjustNetworkParameters(QuicBandwidth bandwidth, + QuicTime::Delta rtt, + bool allow_cwnd_to_decrease) 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 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 { + return model_.BandwidthEstimate(); + } + + QuicByteCount GetCongestionWindow() const override; + + QuicByteCount GetSlowStartThreshold() const override { return 0; } + + CongestionControlType GetCongestionControlType() const override { + return kBBRv2; + } + + std::string GetDebugState() const override; + + void OnApplicationLimited(QuicByteCount bytes_in_flight) override; + // End implementation of SendAlgorithmInterface. + + const Bbr2Params& Params() const { return params_; } + + QuicByteCount GetMinimumCongestionWindow() const { + return cwnd_limits().Min(); + } + + struct DebugState { + Bbr2Mode mode; + + // Shared states. + QuicRoundTripCount round_trip_count; + QuicBandwidth bandwidth_hi = QuicBandwidth::Zero(); + QuicBandwidth bandwidth_lo = QuicBandwidth::Zero(); + QuicBandwidth bandwidth_est = QuicBandwidth::Zero(); + QuicTime::Delta min_rtt = QuicTime::Delta::Zero(); + QuicTime min_rtt_timestamp = QuicTime::Zero(); + QuicByteCount congestion_window; + QuicBandwidth pacing_rate = QuicBandwidth::Zero(); + bool last_sample_is_app_limited; + QuicPacketNumber end_of_app_limited_phase; + + // Mode-specific debug states. + Bbr2StartupMode::DebugState startup; + Bbr2DrainMode::DebugState drain; + Bbr2ProbeBwMode::DebugState probe_bw; + Bbr2ProbeRttMode::DebugState probe_rtt; + }; + + DebugState ExportDebugState() const; + + private: + void UpdatePacingRate(QuicByteCount bytes_acked); + void UpdateCongestionWindow(QuicByteCount bytes_acked); + QuicByteCount GetTargetCongestionWindow(float gain) const; + + // Helper function for BBR2_MODE_DISPATCH. + Bbr2ProbeRttMode& probe_rtt_or_die() { + DCHECK_EQ(mode_, Bbr2Mode::PROBE_RTT); + return probe_rtt_; + } + + const Bbr2ProbeRttMode& probe_rtt_or_die() const { + DCHECK_EQ(mode_, Bbr2Mode::PROBE_RTT); + return probe_rtt_; + } + + uint64_t RandomUint64(uint64_t max) const { + return random_->RandUint64() % max; + } + + // Returns true if there are enough bytes in flight to ensure more bandwidth + // will be observed if present. + bool IsPipeSufficientlyFull() const; + + // Cwnd limits imposed by the current Bbr2 mode. + Limits<QuicByteCount> GetCwndLimitsByMode() const; + + // Cwnd limits imposed by caller. + const Limits<QuicByteCount>& cwnd_limits() const; + + Bbr2Mode mode_; + + const RttStats* const rtt_stats_; + const QuicUnackedPacketMap* const unacked_packets_; + QuicRandom* random_; + + const Bbr2Params params_; + + Bbr2NetworkModel model_; + + // Current cwnd and pacing rate. + QuicByteCount cwnd_; + QuicBandwidth pacing_rate_; + + Bbr2StartupMode startup_; + Bbr2DrainMode drain_; + Bbr2ProbeBwMode probe_bw_; + Bbr2ProbeRttMode probe_rtt_; + + // Indicates app-limited calls should be ignored as long as there's + // enough data inflight to see more bandwidth when necessary. + bool flexible_app_limited_; + + // Debug only. + bool last_sample_is_app_limited_; + + friend class Bbr2StartupMode; + friend class Bbr2DrainMode; + friend class Bbr2ProbeBwMode; + friend class Bbr2ProbeRttMode; +}; + +QUIC_EXPORT_PRIVATE std::ostream& operator<<( + std::ostream& os, + const Bbr2Sender::DebugState& state); + +} // namespace quic + +#endif // QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_SENDER_H_
diff --git a/quic/core/congestion_control/bbr2_simulator_test.cc b/quic/core/congestion_control/bbr2_simulator_test.cc new file mode 100644 index 0000000..736327f --- /dev/null +++ b/quic/core/congestion_control/bbr2_simulator_test.cc
@@ -0,0 +1,1014 @@ +// Copyright 2019 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. + +#include <sstream> + +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_misc.h" +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_sender.h" +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr_sender.h" +#include "net/third_party/quiche/src/quic/core/congestion_control/tcp_cubic_sender_bytes.h" +#include "net/third_party/quiche/src/quic/core/quic_bandwidth.h" +#include "net/third_party/quiche/src/quic/core/quic_types.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_logging.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_ptr_util.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_test.h" +#include "net/third_party/quiche/src/quic/test_tools/quic_connection_peer.h" +#include "net/third_party/quiche/src/quic/test_tools/quic_sent_packet_manager_peer.h" +#include "net/third_party/quiche/src/quic/test_tools/quic_test_utils.h" +#include "net/third_party/quiche/src/quic/test_tools/simulator/link.h" +#include "net/third_party/quiche/src/quic/test_tools/simulator/quic_endpoint.h" +#include "net/third_party/quiche/src/quic/test_tools/simulator/simulator.h" +#include "net/third_party/quiche/src/quic/test_tools/simulator/switch.h" + +namespace quic { + +using CyclePhase = Bbr2ProbeBwMode::CyclePhase; + +namespace test { + +// Use the initial CWND of 10, as 32 is too much for the test network. +const uint32_t kDefaultInitialCwndPackets = 10; +const uint32_t kDefaultInitialCwndBytes = + kDefaultInitialCwndPackets * kDefaultTCPMSS; + +struct LinkParams { + public: + LinkParams(int64_t kilo_bits_per_sec, int64_t delay_us) + : bandwidth(QuicBandwidth::FromKBitsPerSecond(kilo_bits_per_sec)), + delay(QuicTime::Delta::FromMicroseconds(delay_us)) {} + QuicBandwidth bandwidth; + QuicTime::Delta delay; +}; + +// All Bbr2DefaultTopologyTests uses the default network topology: +// +// Sender +// | +// | <-- local_link +// | +// Network switch +// * <-- the bottleneck queue in the direction +// | of the receiver +// | +// | <-- test_link +// | +// | +// Receiver +class DefaultTopologyParams { + public: + LinkParams local_link = {10000, 2000}; + LinkParams test_link = {4000, 30000}; + + const simulator::SwitchPortNumber switch_port_count = 2; + // Network switch queue capacity, in number of BDPs. + float switch_queue_capacity_in_bdp = 2; + + QuicBandwidth BottleneckBandwidth() const { + return std::min(local_link.bandwidth, test_link.bandwidth); + } + + // Round trip time of a single full size packet. + QuicTime::Delta RTT() const { + return 2 * (local_link.delay + test_link.delay + + local_link.bandwidth.TransferTime(kMaxOutgoingPacketSize) + + test_link.bandwidth.TransferTime(kMaxOutgoingPacketSize)); + } + + QuicByteCount BDP() const { return BottleneckBandwidth() * RTT(); } + + QuicByteCount SwitchQueueCapacity() const { + return switch_queue_capacity_in_bdp * BDP(); + } + + std::string ToString() const { + std::ostringstream os; + os << "{ BottleneckBandwidth: " << BottleneckBandwidth() + << " RTT: " << RTT() << " BDP: " << BDP() + << " BottleneckQueueSize: " << SwitchQueueCapacity() << "}"; + return os.str(); + } +}; + +class Bbr2SimulatorTest : public QuicTest { + protected: + Bbr2SimulatorTest() { + // Disable Ack Decimation by default, because it can significantly increase + // srtt. Individual test can enable it via QuicConnectionPeer::SetAckMode(). + SetQuicReloadableFlag(quic_enable_ack_decimation, false); + } +}; + +class Bbr2DefaultTopologyTest : public Bbr2SimulatorTest { + protected: + Bbr2DefaultTopologyTest() + : sender_endpoint_(&simulator_, + "Sender", + "Receiver", + Perspective::IS_CLIENT, + TestConnectionId(42)), + receiver_endpoint_(&simulator_, + "Receiver", + "Sender", + Perspective::IS_SERVER, + TestConnectionId(42)) { + sender_ = SetupBbr2Sender(&sender_endpoint_); + + uint64_t seed = QuicRandom::GetInstance()->RandUint64(); + random_.set_seed(seed); + QUIC_LOG(INFO) << "Bbr2DefaultTopologyTest set up. Seed: " << seed; + + simulator_.set_random_generator(&random_); + } + + ~Bbr2DefaultTopologyTest() { + const auto* test_info = + ::testing::UnitTest::GetInstance()->current_test_info(); + QUIC_LOG(INFO) << "Bbr2DefaultTopologyTest." << test_info->name() + << " completed at simulated time: " + << SimulatedNow().ToDebuggingValue() / 1e6 << " sec."; + } + + Bbr2Sender* SetupBbr2Sender(simulator::QuicEndpoint* endpoint) { + // Ownership of the sender will be overtaken by the endpoint. + Bbr2Sender* sender = new Bbr2Sender( + endpoint->connection()->clock()->Now(), + endpoint->connection()->sent_packet_manager().GetRttStats(), + QuicSentPacketManagerPeer::GetUnackedPacketMap( + QuicConnectionPeer::GetSentPacketManager(endpoint->connection())), + kDefaultInitialCwndPackets, kDefaultMaxCongestionWindowPackets, + &random_, QuicConnectionPeer::GetStats(endpoint->connection())); + QuicConnectionPeer::SetSendAlgorithm(endpoint->connection(), sender); + endpoint->RecordTrace(); + return sender; + } + + void CreateNetwork(const DefaultTopologyParams& params) { + QUIC_LOG(INFO) << "CreateNetwork with parameters: " << params.ToString(); + switch_ = QuicMakeUnique<simulator::Switch>(&simulator_, "Switch", + params.switch_port_count, + params.SwitchQueueCapacity()); + + // WARNING: The order to add links to network_links_ matters, because some + // tests adjusts the link bandwidth on the fly. + + // Local link connects sender and port 1. + network_links_.push_back(QuicMakeUnique<simulator::SymmetricLink>( + &sender_endpoint_, switch_->port(1), params.local_link.bandwidth, + params.local_link.delay)); + + // Test link connects receiver and port 2. + network_links_.push_back(QuicMakeUnique<simulator::SymmetricLink>( + &receiver_endpoint_, switch_->port(2), params.test_link.bandwidth, + params.test_link.delay)); + } + + simulator::SymmetricLink* TestLink() { return network_links_[1].get(); } + + void DoSimpleTransfer(QuicByteCount transfer_size, QuicTime::Delta timeout) { + sender_endpoint_.AddBytesToTransfer(transfer_size); + // TODO(wub): consider rewriting this to run until the receiver actually + // receives the intended amount of bytes. + bool simulator_result = simulator_.RunUntilOrTimeout( + [this]() { return sender_endpoint_.bytes_to_transfer() == 0; }, + timeout); + EXPECT_TRUE(simulator_result) + << "Simple transfer failed. Bytes remaining: " + << sender_endpoint_.bytes_to_transfer(); + QUIC_LOG(INFO) << "Simple transfer state: " << sender_->ExportDebugState(); + } + + // Drive the simulator by sending enough data to enter PROBE_BW. + void DriveOutOfStartup(const DefaultTopologyParams& params) { + ASSERT_FALSE(sender_->ExportDebugState().startup.full_bandwidth_reached); + DoSimpleTransfer(1024 * 1024, QuicTime::Delta::FromSeconds(15)); + EXPECT_EQ(Bbr2Mode::PROBE_BW, sender_->ExportDebugState().mode); + EXPECT_APPROX_EQ(params.BottleneckBandwidth(), + sender_->ExportDebugState().bandwidth_hi, 0.02f); + } + + // Send |bytes|-sized bursts of data |number_of_bursts| times, waiting for + // |wait_time| between each burst. + void SendBursts(const DefaultTopologyParams& params, + size_t number_of_bursts, + QuicByteCount bytes, + QuicTime::Delta wait_time) { + ASSERT_EQ(0u, sender_endpoint_.bytes_to_transfer()); + for (size_t i = 0; i < number_of_bursts; i++) { + sender_endpoint_.AddBytesToTransfer(bytes); + + // Transfer data and wait for three seconds between each transfer. + simulator_.RunFor(wait_time); + + // Ensure the connection did not time out. + ASSERT_TRUE(sender_endpoint_.connection()->connected()); + ASSERT_TRUE(receiver_endpoint_.connection()->connected()); + } + + simulator_.RunFor(wait_time + params.RTT()); + ASSERT_EQ(0u, sender_endpoint_.bytes_to_transfer()); + } + + template <class TerminationPredicate> + bool SendUntilOrTimeout(TerminationPredicate termination_predicate, + QuicTime::Delta timeout) { + EXPECT_EQ(0u, sender_endpoint_.bytes_to_transfer()); + const QuicTime deadline = SimulatedNow() + timeout; + do { + sender_endpoint_.AddBytesToTransfer(4 * kDefaultTCPMSS); + if (simulator_.RunUntilOrTimeout( + [this]() { return sender_endpoint_.bytes_to_transfer() == 0; }, + deadline - SimulatedNow()) && + termination_predicate()) { + return true; + } + } while (SimulatedNow() < deadline); + return false; + } + + void EnableAggregation(QuicByteCount aggregation_bytes, + QuicTime::Delta aggregation_timeout) { + switch_->port_queue(1)->EnableAggregation(aggregation_bytes, + aggregation_timeout); + } + + bool Bbr2ModeIsOneOf(const std::vector<Bbr2Mode>& expected_modes) const { + const Bbr2Mode mode = sender_->ExportDebugState().mode; + for (Bbr2Mode expected_mode : expected_modes) { + if (mode == expected_mode) { + return true; + } + } + return false; + } + + QuicTime SimulatedNow() const { return simulator_.GetClock()->Now(); } + + const RttStats* rtt_stats() { + return sender_endpoint_.connection()->sent_packet_manager().GetRttStats(); + } + + QuicConnection* sender_connection() { return sender_endpoint_.connection(); } + + const QuicConnectionStats& sender_connection_stats() { + return sender_connection()->GetStats(); + } + + float sender_loss_rate_in_packets() { + return static_cast<float>(sender_connection_stats().packets_lost) / + sender_connection_stats().packets_sent; + } + + simulator::Simulator simulator_; + simulator::QuicEndpoint sender_endpoint_; + simulator::QuicEndpoint receiver_endpoint_; + Bbr2Sender* sender_; + SimpleRandom random_; + + std::unique_ptr<simulator::Switch> switch_; + std::vector<std::unique_ptr<simulator::SymmetricLink>> network_links_; +}; + +TEST_F(Bbr2DefaultTopologyTest, NormalStartup) { + DefaultTopologyParams params; + CreateNetwork(params); + + // Run until the full bandwidth is reached and check how many rounds it was. + sender_endpoint_.AddBytesToTransfer(12 * 1024 * 1024); + QuicRoundTripCount max_bw_round = 0; + QuicBandwidth max_bw(QuicBandwidth::Zero()); + bool simulator_result = simulator_.RunUntilOrTimeout( + [this, &max_bw, &max_bw_round]() { + if (max_bw < sender_->ExportDebugState().bandwidth_hi) { + max_bw = sender_->ExportDebugState().bandwidth_hi; + max_bw_round = sender_->ExportDebugState().round_trip_count; + } + return sender_->ExportDebugState().startup.full_bandwidth_reached; + }, + QuicTime::Delta::FromSeconds(5)); + ASSERT_TRUE(simulator_result); + EXPECT_EQ(Bbr2Mode::DRAIN, sender_->ExportDebugState().mode); + EXPECT_EQ(3u, sender_->ExportDebugState().round_trip_count - max_bw_round); + EXPECT_EQ( + 3u, + sender_->ExportDebugState().startup.round_trips_without_bandwidth_growth); + EXPECT_EQ(0u, sender_connection_stats().packets_lost); + EXPECT_FALSE(sender_->ExportDebugState().last_sample_is_app_limited); +} + +// Test a simple long data transfer in the default setup. +TEST_F(Bbr2DefaultTopologyTest, SimpleTransfer) { + DefaultTopologyParams params; + CreateNetwork(params); + + // At startup make sure we are at the default. + EXPECT_EQ(kDefaultInitialCwndBytes, sender_->GetCongestionWindow()); + // At startup make sure we can send. + EXPECT_TRUE(sender_->CanSend(0)); + // And that window is un-affected. + EXPECT_EQ(kDefaultInitialCwndBytes, sender_->GetCongestionWindow()); + + // Verify that Sender is in slow start. + EXPECT_TRUE(sender_->InSlowStart()); + + // Verify that pacing rate is based on the initial RTT. + QuicBandwidth expected_pacing_rate = QuicBandwidth::FromBytesAndTimeDelta( + 2.885 * kDefaultInitialCwndBytes, rtt_stats()->initial_rtt()); + EXPECT_APPROX_EQ(expected_pacing_rate.ToBitsPerSecond(), + sender_->PacingRate(0).ToBitsPerSecond(), 0.01f); + + ASSERT_GE(params.BDP(), kDefaultInitialCwndBytes + kDefaultTCPMSS); + + DoSimpleTransfer(12 * 1024 * 1024, QuicTime::Delta::FromSeconds(30)); + EXPECT_TRUE(Bbr2ModeIsOneOf({Bbr2Mode::PROBE_BW, Bbr2Mode::PROBE_RTT})); + EXPECT_EQ(0u, sender_connection_stats().packets_lost); + EXPECT_FALSE(sender_->ExportDebugState().last_sample_is_app_limited); + + // The margin here is quite high, since there exists a possibility that the + // connection just exited high gain cycle. + EXPECT_APPROX_EQ(params.RTT(), rtt_stats()->smoothed_rtt(), 0.2f); +} + +TEST_F(Bbr2DefaultTopologyTest, SimpleTransferSmallBuffer) { + DefaultTopologyParams params; + params.switch_queue_capacity_in_bdp = 0.5; + CreateNetwork(params); + + DoSimpleTransfer(12 * 1024 * 1024, QuicTime::Delta::FromSeconds(30)); + EXPECT_TRUE(Bbr2ModeIsOneOf({Bbr2Mode::PROBE_BW, Bbr2Mode::PROBE_RTT})); + EXPECT_APPROX_EQ(params.BottleneckBandwidth(), + sender_->ExportDebugState().bandwidth_hi, 0.01f); + EXPECT_GE(sender_connection_stats().packets_lost, 0u); + EXPECT_FALSE(sender_->ExportDebugState().last_sample_is_app_limited); +} + +TEST_F(Bbr2DefaultTopologyTest, SimpleTransfer2RTTAggregationBytes) { + DefaultTopologyParams params; + CreateNetwork(params); + // 2 RTTs of aggregation, with a max of 10kb. + EnableAggregation(10 * 1024, 2 * params.RTT()); + + // Transfer 12MB. + DoSimpleTransfer(12 * 1024 * 1024, QuicTime::Delta::FromSeconds(35)); + EXPECT_TRUE(Bbr2ModeIsOneOf({Bbr2Mode::PROBE_BW, Bbr2Mode::PROBE_RTT})); + + EXPECT_LE(params.BottleneckBandwidth() * 0.99f, + sender_->ExportDebugState().bandwidth_hi); + // TODO(b/36022633): Bandwidth sampler overestimates with aggregation. + EXPECT_GE(params.BottleneckBandwidth() * 1.5f, + sender_->ExportDebugState().bandwidth_hi); + EXPECT_LE(sender_loss_rate_in_packets(), 0.05); + // The margin here is high, because the aggregation greatly increases + // smoothed rtt. + EXPECT_GE(params.RTT() * 4, rtt_stats()->smoothed_rtt()); + EXPECT_APPROX_EQ(params.RTT(), rtt_stats()->min_rtt(), 0.2f); +} + +TEST_F(Bbr2DefaultTopologyTest, SimpleTransferAckDecimation) { + // Enable Ack Decimation on the receiver. + QuicConnectionPeer::SetAckMode(receiver_endpoint_.connection(), + AckMode::ACK_DECIMATION); + DefaultTopologyParams params; + CreateNetwork(params); + + // Transfer 12MB. + DoSimpleTransfer(12 * 1024 * 1024, QuicTime::Delta::FromSeconds(35)); + EXPECT_TRUE(Bbr2ModeIsOneOf({Bbr2Mode::PROBE_BW, Bbr2Mode::PROBE_RTT})); + + EXPECT_LE(params.BottleneckBandwidth() * 0.99f, + sender_->ExportDebugState().bandwidth_hi); + // TODO(b/36022633): Bandwidth sampler overestimates with aggregation. + EXPECT_GE(params.BottleneckBandwidth() * 1.1f, + sender_->ExportDebugState().bandwidth_hi); + EXPECT_LE(sender_loss_rate_in_packets(), 0.001); + EXPECT_FALSE(sender_->ExportDebugState().last_sample_is_app_limited); + // The margin here is high, because the aggregation greatly increases + // smoothed rtt. + EXPECT_GE(params.RTT() * 2, rtt_stats()->smoothed_rtt()); + EXPECT_APPROX_EQ(params.RTT(), rtt_stats()->min_rtt(), 0.1f); +} + +// Test Bbr2's reaction to a 100x bandwidth decrease during a transfer. +TEST_F(Bbr2DefaultTopologyTest, BandwidthDecrease) { + DefaultTopologyParams params; + params.local_link.bandwidth = QuicBandwidth::FromKBitsPerSecond(15000); + params.test_link.bandwidth = QuicBandwidth::FromKBitsPerSecond(10000); + CreateNetwork(params); + + sender_endpoint_.AddBytesToTransfer(20 * 1024 * 1024); + + // We can transfer ~12MB in the first 10 seconds. The rest ~8MB needs about + // 640 seconds. + simulator_.RunFor(QuicTime::Delta::FromSeconds(10)); + EXPECT_TRUE(Bbr2ModeIsOneOf({Bbr2Mode::PROBE_BW, Bbr2Mode::PROBE_RTT})); + QUIC_LOG(INFO) << "Bandwidth decreasing at time " << SimulatedNow(); + + EXPECT_APPROX_EQ(params.test_link.bandwidth, + sender_->ExportDebugState().bandwidth_est, 0.1f); + EXPECT_EQ(0u, sender_connection_stats().packets_lost); + + // Now decrease the bottleneck bandwidth from 10Mbps to 100Kbps. + params.test_link.bandwidth = QuicBandwidth::FromKBitsPerSecond(100); + TestLink()->set_bandwidth(params.test_link.bandwidth); + + bool simulator_result = simulator_.RunUntilOrTimeout( + [this]() { return sender_endpoint_.bytes_to_transfer() == 0; }, + QuicTime::Delta::FromSeconds(800)); + EXPECT_TRUE(simulator_result); +} + +// Test Bbr2's reaction to a 100x bandwidth increase during a transfer. +TEST_F(Bbr2DefaultTopologyTest, BandwidthIncrease) { + DefaultTopologyParams params; + params.local_link.bandwidth = QuicBandwidth::FromKBitsPerSecond(15000); + params.test_link.bandwidth = QuicBandwidth::FromKBitsPerSecond(100); + CreateNetwork(params); + + sender_endpoint_.AddBytesToTransfer(20 * 1024 * 1024); + + simulator_.RunFor(QuicTime::Delta::FromSeconds(10)); + EXPECT_TRUE(Bbr2ModeIsOneOf({Bbr2Mode::PROBE_BW, Bbr2Mode::PROBE_RTT})); + QUIC_LOG(INFO) << "Bandwidth increasing at time " << SimulatedNow(); + + EXPECT_APPROX_EQ(params.test_link.bandwidth, + sender_->ExportDebugState().bandwidth_est, 0.1f); + EXPECT_LE(sender_loss_rate_in_packets(), 0.20); + + // Now increase the bottleneck bandwidth from 100Kbps to 10Mbps. + params.test_link.bandwidth = QuicBandwidth::FromKBitsPerSecond(10000); + TestLink()->set_bandwidth(params.test_link.bandwidth); + + bool simulator_result = simulator_.RunUntilOrTimeout( + [this]() { return sender_endpoint_.bytes_to_transfer() == 0; }, + QuicTime::Delta::FromSeconds(50)); + EXPECT_TRUE(simulator_result); +} + +// Test the number of losses incurred by the startup phase in a situation when +// the buffer is less than BDP. +TEST_F(Bbr2DefaultTopologyTest, PacketLossOnSmallBufferStartup) { + DefaultTopologyParams params; + params.switch_queue_capacity_in_bdp = 0.5; + CreateNetwork(params); + + DriveOutOfStartup(params); + EXPECT_LE(sender_loss_rate_in_packets(), 0.20); +} + +// Verify the behavior of the algorithm in the case when the connection sends +// small bursts of data after sending continuously for a while. +TEST_F(Bbr2DefaultTopologyTest, ApplicationLimitedBursts) { + DefaultTopologyParams params; + CreateNetwork(params); + + DriveOutOfStartup(params); + EXPECT_FALSE(sender_->ExportDebugState().last_sample_is_app_limited); + + SendBursts(params, 20, 512, QuicTime::Delta::FromSeconds(3)); + EXPECT_TRUE(sender_->ExportDebugState().last_sample_is_app_limited); + EXPECT_APPROX_EQ(params.BottleneckBandwidth(), + sender_->ExportDebugState().bandwidth_hi, 0.01f); +} + +// Verify the behavior of the algorithm in the case when the connection sends +// small bursts of data and then starts sending continuously. +TEST_F(Bbr2DefaultTopologyTest, ApplicationLimitedBurstsWithoutPrior) { + DefaultTopologyParams params; + CreateNetwork(params); + + SendBursts(params, 40, 512, QuicTime::Delta::FromSeconds(3)); + EXPECT_TRUE(sender_->ExportDebugState().last_sample_is_app_limited); + + DriveOutOfStartup(params); + EXPECT_APPROX_EQ(params.BottleneckBandwidth(), + sender_->ExportDebugState().bandwidth_hi, 0.01f); + EXPECT_FALSE(sender_->ExportDebugState().last_sample_is_app_limited); +} + +// Verify that the DRAIN phase works correctly. +TEST_F(Bbr2DefaultTopologyTest, Drain) { + DefaultTopologyParams params; + CreateNetwork(params); + + const QuicTime::Delta timeout = QuicTime::Delta::FromSeconds(10); + // Get the queue at the bottleneck, which is the outgoing queue at the port to + // which the receiver is connected. + const simulator::Queue* queue = switch_->port_queue(2); + bool simulator_result; + + // We have no intention of ever finishing this transfer. + sender_endpoint_.AddBytesToTransfer(100 * 1024 * 1024); + + // Run the startup, and verify that it fills up the queue. + ASSERT_EQ(Bbr2Mode::STARTUP, sender_->ExportDebugState().mode); + simulator_result = simulator_.RunUntilOrTimeout( + [this]() { + return sender_->ExportDebugState().mode != Bbr2Mode::STARTUP; + }, + timeout); + ASSERT_TRUE(simulator_result); + ASSERT_EQ(Bbr2Mode::DRAIN, sender_->ExportDebugState().mode); + EXPECT_APPROX_EQ(sender_->BandwidthEstimate() * (1 / 2.885f), + sender_->PacingRate(0), 0.01f); + // BBR uses CWND gain of 2.88 during STARTUP, hence it will fill the buffer + // with approximately 1.88 BDPs. Here, we use 1.5 to give some margin for + // error. + EXPECT_GE(queue->bytes_queued(), 1.5 * params.BDP()); + + // Observe increased RTT due to bufferbloat. + const QuicTime::Delta queueing_delay = + params.test_link.bandwidth.TransferTime(queue->bytes_queued()); + EXPECT_APPROX_EQ(params.RTT() + queueing_delay, rtt_stats()->latest_rtt(), + 0.1f); + + // Transition to the drain phase and verify that it makes the queue + // have at most a BDP worth of packets. + simulator_result = simulator_.RunUntilOrTimeout( + [this]() { return sender_->ExportDebugState().mode != Bbr2Mode::DRAIN; }, + timeout); + ASSERT_TRUE(simulator_result); + ASSERT_EQ(Bbr2Mode::PROBE_BW, sender_->ExportDebugState().mode); + EXPECT_LE(queue->bytes_queued(), params.BDP()); + + // Wait for a few round trips and ensure we're in appropriate phase of gain + // cycling before taking an RTT measurement. + const QuicRoundTripCount start_round_trip = + sender_->ExportDebugState().round_trip_count; + simulator_result = simulator_.RunUntilOrTimeout( + [this, start_round_trip]() { + const auto& debug_state = sender_->ExportDebugState(); + QuicRoundTripCount rounds_passed = + debug_state.round_trip_count - start_round_trip; + return rounds_passed >= 4 && debug_state.mode == Bbr2Mode::PROBE_BW && + debug_state.probe_bw.phase == CyclePhase::PROBE_REFILL; + }, + timeout); + ASSERT_TRUE(simulator_result); + + // Observe the bufferbloat go away. + EXPECT_APPROX_EQ(params.RTT(), rtt_stats()->smoothed_rtt(), 0.1f); +} + +// Ensure that a connection that is app-limited and is at sufficiently low +// bandwidth will not exit high gain phase, and similarly ensure that the +// connection will exit low gain early if the number of bytes in flight is low. +TEST_F(Bbr2DefaultTopologyTest, InFlightAwareGainCycling) { + DefaultTopologyParams params; + CreateNetwork(params); + DriveOutOfStartup(params); + + const QuicTime::Delta timeout = QuicTime::Delta::FromSeconds(5); + bool simulator_result; + + // Start a few cycles prior to the high gain one. + simulator_result = SendUntilOrTimeout( + [this]() { + return sender_->ExportDebugState().probe_bw.phase == + CyclePhase::PROBE_REFILL; + }, + timeout); + ASSERT_TRUE(simulator_result); + + // Send at 10% of available rate. Run for 3 seconds, checking in the middle + // and at the end. The pacing gain should be high throughout. + QuicBandwidth target_bandwidth = 0.1f * params.BottleneckBandwidth(); + QuicTime::Delta burst_interval = QuicTime::Delta::FromMilliseconds(300); + for (int i = 0; i < 2; i++) { + SendBursts(params, 5, target_bandwidth * burst_interval, burst_interval); + EXPECT_EQ(Bbr2Mode::PROBE_BW, sender_->ExportDebugState().mode); + EXPECT_EQ(CyclePhase::PROBE_UP, sender_->ExportDebugState().probe_bw.phase); + EXPECT_APPROX_EQ(params.BottleneckBandwidth(), + sender_->ExportDebugState().bandwidth_hi, 0.01f); + } + + // Now that in-flight is almost zero and the pacing gain is still above 1, + // send approximately 1.25 BDPs worth of data. This should cause the + // PROBE_BW mode to enter low gain cycle(PROBE_DOWN), and exit it earlier than + // one min_rtt due to running out of data to send. + sender_endpoint_.AddBytesToTransfer(1.3 * params.BDP()); + simulator_result = simulator_.RunUntilOrTimeout( + [this]() { + return sender_->ExportDebugState().probe_bw.phase == + CyclePhase::PROBE_DOWN; + }, + timeout); + ASSERT_TRUE(simulator_result); + simulator_.RunFor(0.75 * sender_->ExportDebugState().min_rtt); + EXPECT_EQ(Bbr2Mode::PROBE_BW, sender_->ExportDebugState().mode); + EXPECT_EQ(CyclePhase::PROBE_CRUISE, + sender_->ExportDebugState().probe_bw.phase); +} + +// Test exiting STARTUP earlier upon loss due to loss. +TEST_F(Bbr2DefaultTopologyTest, ExitStartupDueToLoss) { + DefaultTopologyParams params; + params.switch_queue_capacity_in_bdp = 0.5; + CreateNetwork(params); + + // Run until the full bandwidth is reached and check how many rounds it was. + sender_endpoint_.AddBytesToTransfer(12 * 1024 * 1024); + QuicRoundTripCount max_bw_round = 0; + QuicBandwidth max_bw(QuicBandwidth::Zero()); + bool simulator_result = simulator_.RunUntilOrTimeout( + [this, &max_bw, &max_bw_round]() { + if (max_bw < sender_->ExportDebugState().bandwidth_hi) { + max_bw = sender_->ExportDebugState().bandwidth_hi; + max_bw_round = sender_->ExportDebugState().round_trip_count; + } + return sender_->ExportDebugState().startup.full_bandwidth_reached; + }, + QuicTime::Delta::FromSeconds(5)); + ASSERT_TRUE(simulator_result); + EXPECT_EQ(Bbr2Mode::DRAIN, sender_->ExportDebugState().mode); + EXPECT_GE(2u, sender_->ExportDebugState().round_trip_count - max_bw_round); + EXPECT_EQ( + 1u, + sender_->ExportDebugState().startup.round_trips_without_bandwidth_growth); + EXPECT_NE(0u, sender_connection_stats().packets_lost); + EXPECT_FALSE(sender_->ExportDebugState().last_sample_is_app_limited); +} + +// All Bbr2MultiSenderTests uses the following network topology: +// +// Sender 0 (A Bbr2Sender) +// | +// | <-- local_links[0] +// | +// | Sender N (1 <= N < kNumLocalLinks) (May or may not be a Bbr2Sender) +// | | +// | | <-- local_links[N] +// | | +// Network switch +// * <-- the bottleneck queue in the direction +// | of the receiver +// | +// | <-- test_link +// | +// | +// Receiver +class MultiSenderTopologyParams { + public: + static const size_t kNumLocalLinks = 8; + std::array<LinkParams, kNumLocalLinks> local_links = { + LinkParams(10000, 1987), LinkParams(10000, 1993), LinkParams(10000, 1997), + LinkParams(10000, 1999), LinkParams(10000, 2003), LinkParams(10000, 2011), + LinkParams(10000, 2017), LinkParams(10000, 2027), + }; + + LinkParams test_link = LinkParams(4000, 30000); + + const simulator::SwitchPortNumber switch_port_count = kNumLocalLinks + 1; + + // Network switch queue capacity, in number of BDPs. + float switch_queue_capacity_in_bdp = 2; + + QuicBandwidth BottleneckBandwidth() const { + // Make sure all local links have a higher bandwidth than the test link. + for (size_t i = 0; i < local_links.size(); ++i) { + CHECK_GT(local_links[i].bandwidth, test_link.bandwidth); + } + return test_link.bandwidth; + } + + // Sender n's round trip time of a single full size packet. + QuicTime::Delta Rtt(size_t n) const { + return 2 * (local_links[n].delay + test_link.delay + + local_links[n].bandwidth.TransferTime(kMaxOutgoingPacketSize) + + test_link.bandwidth.TransferTime(kMaxOutgoingPacketSize)); + } + + QuicByteCount Bdp(size_t n) const { return BottleneckBandwidth() * Rtt(n); } + + QuicByteCount SwitchQueueCapacity() const { + return switch_queue_capacity_in_bdp * Bdp(1); + } + + std::string ToString() const { + std::ostringstream os; + os << "{ BottleneckBandwidth: " << BottleneckBandwidth(); + for (size_t i = 0; i < local_links.size(); ++i) { + os << " RTT_" << i << ": " << Rtt(i) << " BDP_" << i << ": " << Bdp(i); + } + os << " BottleneckQueueSize: " << SwitchQueueCapacity() << "}"; + return os.str(); + } +}; + +class Bbr2MultiSenderTest : public Bbr2SimulatorTest { + protected: + Bbr2MultiSenderTest() { + uint64_t first_connection_id = 42; + std::vector<simulator::QuicEndpoint*> receiver_endpoint_pointers; + for (size_t i = 0; i < MultiSenderTopologyParams::kNumLocalLinks; ++i) { + std::string sender_name = QuicStrCat("Sender", i + 1); + std::string receiver_name = QuicStrCat("Receiver", i + 1); + sender_endpoints_.push_back(QuicMakeUnique<simulator::QuicEndpoint>( + &simulator_, sender_name, receiver_name, Perspective::IS_CLIENT, + TestConnectionId(first_connection_id + i))); + receiver_endpoints_.push_back(QuicMakeUnique<simulator::QuicEndpoint>( + &simulator_, receiver_name, sender_name, Perspective::IS_SERVER, + TestConnectionId(first_connection_id + i))); + receiver_endpoint_pointers.push_back(receiver_endpoints_.back().get()); + } + receiver_multiplexer_ = QuicMakeUnique<simulator::QuicEndpointMultiplexer>( + "Receiver multiplexer", receiver_endpoint_pointers); + sender_1_ = SetupBbr2Sender(sender_endpoints_[0].get()); + + uint64_t seed = QuicRandom::GetInstance()->RandUint64(); + random_.set_seed(seed); + QUIC_LOG(INFO) << "Bbr2MultiSenderTest set up. Seed: " << seed; + + simulator_.set_random_generator(&random_); + } + + ~Bbr2MultiSenderTest() { + const auto* test_info = + ::testing::UnitTest::GetInstance()->current_test_info(); + QUIC_LOG(INFO) << "Bbr2MultiSenderTest." << test_info->name() + << " completed at simulated time: " + << SimulatedNow().ToDebuggingValue() / 1e6 << " sec."; + } + + Bbr2Sender* SetupBbr2Sender(simulator::QuicEndpoint* endpoint) { + // Ownership of the sender will be overtaken by the endpoint. + Bbr2Sender* sender = new Bbr2Sender( + endpoint->connection()->clock()->Now(), + endpoint->connection()->sent_packet_manager().GetRttStats(), + QuicSentPacketManagerPeer::GetUnackedPacketMap( + QuicConnectionPeer::GetSentPacketManager(endpoint->connection())), + kDefaultInitialCwndPackets, kDefaultMaxCongestionWindowPackets, + &random_, QuicConnectionPeer::GetStats(endpoint->connection())); + QuicConnectionPeer::SetSendAlgorithm(endpoint->connection(), sender); + endpoint->RecordTrace(); + return sender; + } + + BbrSender* SetupBbrSender(simulator::QuicEndpoint* endpoint) { + // Ownership of the sender will be overtaken by the endpoint. + BbrSender* sender = new BbrSender( + endpoint->connection()->clock()->Now(), + endpoint->connection()->sent_packet_manager().GetRttStats(), + QuicSentPacketManagerPeer::GetUnackedPacketMap( + QuicConnectionPeer::GetSentPacketManager(endpoint->connection())), + kDefaultInitialCwndPackets, kDefaultMaxCongestionWindowPackets, + &random_, QuicConnectionPeer::GetStats(endpoint->connection())); + QuicConnectionPeer::SetSendAlgorithm(endpoint->connection(), sender); + endpoint->RecordTrace(); + return sender; + } + + // reno => Reno. !reno => Cubic. + TcpCubicSenderBytes* SetupTcpSender(simulator::QuicEndpoint* endpoint, + bool reno) { + // Ownership of the sender will be overtaken by the endpoint. + TcpCubicSenderBytes* sender = new TcpCubicSenderBytes( + endpoint->connection()->clock(), + endpoint->connection()->sent_packet_manager().GetRttStats(), reno, + kDefaultInitialCwndPackets, kDefaultMaxCongestionWindowPackets, + QuicConnectionPeer::GetStats(endpoint->connection())); + QuicConnectionPeer::SetSendAlgorithm(endpoint->connection(), sender); + endpoint->RecordTrace(); + return sender; + } + + void CreateNetwork(const MultiSenderTopologyParams& params) { + QUIC_LOG(INFO) << "CreateNetwork with parameters: " << params.ToString(); + switch_ = QuicMakeUnique<simulator::Switch>(&simulator_, "Switch", + params.switch_port_count, + params.SwitchQueueCapacity()); + + network_links_.push_back(QuicMakeUnique<simulator::SymmetricLink>( + receiver_multiplexer_.get(), switch_->port(1), + params.test_link.bandwidth, params.test_link.delay)); + for (size_t i = 0; i < MultiSenderTopologyParams::kNumLocalLinks; ++i) { + simulator::SwitchPortNumber port_number = i + 2; + network_links_.push_back(QuicMakeUnique<simulator::SymmetricLink>( + sender_endpoints_[i].get(), switch_->port(port_number), + params.local_links[i].bandwidth, params.local_links[i].delay)); + } + } + + QuicTime SimulatedNow() const { return simulator_.GetClock()->Now(); } + + simulator::Simulator simulator_; + std::vector<std::unique_ptr<simulator::QuicEndpoint>> sender_endpoints_; + std::vector<std::unique_ptr<simulator::QuicEndpoint>> receiver_endpoints_; + std::unique_ptr<simulator::QuicEndpointMultiplexer> receiver_multiplexer_; + Bbr2Sender* sender_1_; + SimpleRandom random_; + + std::unique_ptr<simulator::Switch> switch_; + std::vector<std::unique_ptr<simulator::SymmetricLink>> network_links_; +}; + +TEST_F(Bbr2MultiSenderTest, Bbr2VsBbr2) { + SetupBbr2Sender(sender_endpoints_[1].get()); + + MultiSenderTopologyParams params; + CreateNetwork(params); + + const QuicByteCount transfer_size = 10 * 1024 * 1024; + const QuicTime::Delta transfer_time = + params.BottleneckBandwidth().TransferTime(transfer_size); + QUIC_LOG(INFO) << "Single flow transfer time: " << transfer_time; + + // Transfer 10% of data in first transfer. + sender_endpoints_[0]->AddBytesToTransfer(transfer_size); + bool simulator_result = simulator_.RunUntilOrTimeout( + [this]() { + return receiver_endpoints_[0]->bytes_received() >= 0.1 * transfer_size; + }, + transfer_time); + ASSERT_TRUE(simulator_result); + + // Start the second transfer and wait until both finish. + sender_endpoints_[1]->AddBytesToTransfer(transfer_size); + simulator_result = simulator_.RunUntilOrTimeout( + [this]() { + return receiver_endpoints_[0]->bytes_received() == transfer_size && + receiver_endpoints_[1]->bytes_received() == transfer_size; + }, + 3 * transfer_time); + ASSERT_TRUE(simulator_result); +} + +TEST_F(Bbr2MultiSenderTest, MultipleBbr2s) { + const int kTotalNumSenders = 6; + for (int i = 1; i < kTotalNumSenders; ++i) { + SetupBbr2Sender(sender_endpoints_[i].get()); + } + + MultiSenderTopologyParams params; + CreateNetwork(params); + + const QuicByteCount transfer_size = 10 * 1024 * 1024; + const QuicTime::Delta transfer_time = + params.BottleneckBandwidth().TransferTime(transfer_size); + QUIC_LOG(INFO) << "Single flow transfer time: " << transfer_time + << ". Now: " << SimulatedNow(); + + // Start all transfers. + for (int i = 0; i < kTotalNumSenders; ++i) { + if (i != 0) { + const QuicTime sender_start_time = + SimulatedNow() + QuicTime::Delta::FromSeconds(2); + bool simulator_result = simulator_.RunUntilOrTimeout( + [&]() { return SimulatedNow() >= sender_start_time; }, transfer_time); + ASSERT_TRUE(simulator_result); + } + + sender_endpoints_[i]->AddBytesToTransfer(transfer_size); + } + + // Wait for all transfers to finish. + QuicTime::Delta expected_total_transfer_time_upper_bound = + QuicTime::Delta::FromMicroseconds(kTotalNumSenders * + transfer_time.ToMicroseconds() * 1.1); + bool simulator_result = simulator_.RunUntilOrTimeout( + [this]() { + for (int i = 0; i < kTotalNumSenders; ++i) { + if (receiver_endpoints_[i]->bytes_received() < transfer_size) { + return false; + } + } + return true; + }, + expected_total_transfer_time_upper_bound); + ASSERT_TRUE(simulator_result) + << "Expected upper bound: " << expected_total_transfer_time_upper_bound; +} + +/* The first 11 packets are sent at the same time, but the duration between the + * acks of the 1st and the 11th packet is 49 milliseconds, causing very low bw + * samples. This happens for both large and small buffers. + */ +/* +TEST_F(Bbr2MultiSenderTest, Bbr2VsBbr2LargeRttTinyBuffer) { + SetupBbr2Sender(sender_endpoints_[1].get()); + + MultiSenderTopologyParams params; + params.switch_queue_capacity_in_bdp = 0.05; + params.test_link.delay = QuicTime::Delta::FromSeconds(1); + CreateNetwork(params); + + const QuicByteCount transfer_size = 10 * 1024 * 1024; + const QuicTime::Delta transfer_time = + params.BottleneckBandwidth().TransferTime(transfer_size); + QUIC_LOG(INFO) << "Single flow transfer time: " << transfer_time; + + // Transfer 10% of data in first transfer. + sender_endpoints_[0]->AddBytesToTransfer(transfer_size); + bool simulator_result = simulator_.RunUntilOrTimeout( + [this]() { + return receiver_endpoints_[0]->bytes_received() >= 0.1 * transfer_size; + }, + transfer_time); + ASSERT_TRUE(simulator_result); + + // Start the second transfer and wait until both finish. + sender_endpoints_[1]->AddBytesToTransfer(transfer_size); + simulator_result = simulator_.RunUntilOrTimeout( + [this]() { + return receiver_endpoints_[0]->bytes_received() == transfer_size && + receiver_endpoints_[1]->bytes_received() == transfer_size; + }, + 3 * transfer_time); + ASSERT_TRUE(simulator_result); +} +*/ + +TEST_F(Bbr2MultiSenderTest, Bbr2VsBbr1) { + SetupBbrSender(sender_endpoints_[1].get()); + + MultiSenderTopologyParams params; + CreateNetwork(params); + + const QuicByteCount transfer_size = 10 * 1024 * 1024; + const QuicTime::Delta transfer_time = + params.BottleneckBandwidth().TransferTime(transfer_size); + QUIC_LOG(INFO) << "Single flow transfer time: " << transfer_time; + + // Transfer 10% of data in first transfer. + sender_endpoints_[0]->AddBytesToTransfer(transfer_size); + bool simulator_result = simulator_.RunUntilOrTimeout( + [this]() { + return receiver_endpoints_[0]->bytes_received() >= 0.1 * transfer_size; + }, + transfer_time); + ASSERT_TRUE(simulator_result); + + // Start the second transfer and wait until both finish. + sender_endpoints_[1]->AddBytesToTransfer(transfer_size); + simulator_result = simulator_.RunUntilOrTimeout( + [this]() { + return receiver_endpoints_[0]->bytes_received() == transfer_size && + receiver_endpoints_[1]->bytes_received() == transfer_size; + }, + 3 * transfer_time); + ASSERT_TRUE(simulator_result); +} + +TEST_F(Bbr2MultiSenderTest, Bbr2VsReno) { + SetupTcpSender(sender_endpoints_[1].get(), /*reno=*/true); + + MultiSenderTopologyParams params; + CreateNetwork(params); + + const QuicByteCount transfer_size = 50 * 1024 * 1024; + const QuicTime::Delta transfer_time = + params.BottleneckBandwidth().TransferTime(transfer_size); + QUIC_LOG(INFO) << "Single flow transfer time: " << transfer_time; + + // Transfer 10% of data in first transfer. + sender_endpoints_[0]->AddBytesToTransfer(transfer_size); + bool simulator_result = simulator_.RunUntilOrTimeout( + [this]() { + return receiver_endpoints_[0]->bytes_received() >= 0.1 * transfer_size; + }, + transfer_time); + ASSERT_TRUE(simulator_result); + + // Start the second transfer and wait until both finish. + sender_endpoints_[1]->AddBytesToTransfer(transfer_size); + simulator_result = simulator_.RunUntilOrTimeout( + [this]() { + return receiver_endpoints_[0]->bytes_received() == transfer_size && + receiver_endpoints_[1]->bytes_received() == transfer_size; + }, + 3 * transfer_time); + ASSERT_TRUE(simulator_result); +} + +TEST_F(Bbr2MultiSenderTest, Bbr2VsCubic) { + SetupTcpSender(sender_endpoints_[1].get(), /*reno=*/false); + + MultiSenderTopologyParams params; + CreateNetwork(params); + + const QuicByteCount transfer_size = 50 * 1024 * 1024; + const QuicTime::Delta transfer_time = + params.BottleneckBandwidth().TransferTime(transfer_size); + QUIC_LOG(INFO) << "Single flow transfer time: " << transfer_time; + + // Transfer 10% of data in first transfer. + sender_endpoints_[0]->AddBytesToTransfer(transfer_size); + bool simulator_result = simulator_.RunUntilOrTimeout( + [this]() { + return receiver_endpoints_[0]->bytes_received() >= 0.1 * transfer_size; + }, + transfer_time); + ASSERT_TRUE(simulator_result); + + // Start the second transfer and wait until both finish. + sender_endpoints_[1]->AddBytesToTransfer(transfer_size); + simulator_result = simulator_.RunUntilOrTimeout( + [this]() { + return receiver_endpoints_[0]->bytes_received() == transfer_size && + receiver_endpoints_[1]->bytes_received() == transfer_size; + }, + 3 * transfer_time); + ASSERT_TRUE(simulator_result); +} + +} // namespace test +} // namespace quic
diff --git a/quic/core/congestion_control/bbr2_startup.cc b/quic/core/congestion_control/bbr2_startup.cc new file mode 100644 index 0000000..5ff1050 --- /dev/null +++ b/quic/core/congestion_control/bbr2_startup.cc
@@ -0,0 +1,138 @@ +// Copyright 2019 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. + +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_startup.h" + +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_misc.h" +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_sender.h" +#include "net/third_party/quiche/src/quic/core/quic_bandwidth.h" +#include "net/third_party/quiche/src/quic/core/quic_types.h" + +namespace quic { + +Bbr2StartupMode::Bbr2StartupMode(const Bbr2Sender* sender, + Bbr2NetworkModel* model) + : Bbr2ModeBase(sender, model), + full_bandwidth_reached_(false), + full_bandwidth_baseline_(QuicBandwidth::Zero()), + rounds_without_bandwidth_growth_(0), + loss_events_in_round_(0) {} + +void Bbr2StartupMode::Enter(const Bbr2CongestionEvent& /*congestion_event*/) { + QUIC_BUG << "Bbr2StartupMode::Enter should not be called"; +} + +Bbr2Mode Bbr2StartupMode::OnCongestionEvent( + QuicByteCount /*prior_in_flight*/, + QuicTime /*event_time*/, + const AckedPacketVector& /*acked_packets*/, + const LostPacketVector& lost_packets, + const Bbr2CongestionEvent& congestion_event) { + CheckFullBandwidthReached(congestion_event); + + CheckExcessiveLosses(lost_packets, congestion_event); + + model_->set_pacing_gain(Params().startup_gain); + model_->set_cwnd_gain(Params().startup_gain); + + // TODO(wub): Maybe implement STARTUP => PROBE_RTT. + return full_bandwidth_reached_ ? Bbr2Mode::DRAIN : Bbr2Mode::STARTUP; +} + +void Bbr2StartupMode::CheckFullBandwidthReached( + const Bbr2CongestionEvent& congestion_event) { + DCHECK(!full_bandwidth_reached_); + if (full_bandwidth_reached_ || !congestion_event.end_of_round_trip || + congestion_event.last_sample_is_app_limited) { + return; + } + + QuicBandwidth threshold = + full_bandwidth_baseline_ * Params().startup_full_bw_threshold; + + if (model_->MaxBandwidth() >= threshold) { + QUIC_DVLOG(3) + << sender_ + << " CheckFullBandwidthReached at end of round. max_bandwidth:" + << model_->MaxBandwidth() << ", threshold:" << threshold + << " (Still growing) @ " << congestion_event.event_time; + full_bandwidth_baseline_ = model_->MaxBandwidth(); + rounds_without_bandwidth_growth_ = 0; + return; + } + + ++rounds_without_bandwidth_growth_; + full_bandwidth_reached_ = + rounds_without_bandwidth_growth_ >= Params().startup_full_bw_rounds; + QUIC_DVLOG(3) << sender_ + << " CheckFullBandwidthReached at end of round. max_bandwidth:" + << model_->MaxBandwidth() << ", threshold:" << threshold + << " rounds_without_growth:" << rounds_without_bandwidth_growth_ + << " full_bw_reached:" << full_bandwidth_reached_ << " @ " + << congestion_event.event_time; +} + +void Bbr2StartupMode::CheckExcessiveLosses( + const LostPacketVector& lost_packets, + const Bbr2CongestionEvent& congestion_event) { + if (full_bandwidth_reached_) { + return; + } + + if (!lost_packets.empty()) { + ++loss_events_in_round_; + } + + // TODO(wub): In TCP, loss based exit only happens at end of a loss round, in + // QUIC we use the end of the normal round here. It is possible to exit after + // any congestion event, using information of the "rolling round". + if (!congestion_event.end_of_round_trip) { + return; + } + + QUIC_DVLOG(3) + << sender_ + << " CheckExcessiveLosses at end of round. loss_events_in_round_:" + << loss_events_in_round_ + << ", threshold:" << Params().startup_full_loss_count << " @ " + << congestion_event.event_time; + + // At the end of a round trip. Check if loss is too high in this round. + if (loss_events_in_round_ >= Params().startup_full_loss_count && + model_->IsInflightTooHigh(congestion_event)) { + const QuicByteCount bdp = model_->BDP(model_->MaxBandwidth()); + QUIC_DVLOG(3) << sender_ + << " Exiting STARTUP due to loss. inflight_hi:" << bdp; + model_->set_inflight_hi(bdp); + + full_bandwidth_reached_ = true; + } + + loss_events_in_round_ = 0; +} + +Bbr2StartupMode::DebugState Bbr2StartupMode::ExportDebugState() const { + DebugState s; + s.full_bandwidth_reached = full_bandwidth_reached_; + s.full_bandwidth_baseline = full_bandwidth_baseline_; + s.round_trips_without_bandwidth_growth = rounds_without_bandwidth_growth_; + return s; +} + +std::ostream& operator<<(std::ostream& os, + const Bbr2StartupMode::DebugState& state) { + os << "[STARTUP] full_bandwidth_reached: " << state.full_bandwidth_reached + << "\n"; + os << "[STARTUP] full_bandwidth_baseline: " << state.full_bandwidth_baseline + << "\n"; + os << "[STARTUP] round_trips_without_bandwidth_growth: " + << state.round_trips_without_bandwidth_growth << "\n"; + return os; +} + +const Bbr2Params& Bbr2StartupMode::Params() const { + return sender_->Params(); +} + +} // namespace quic
diff --git a/quic/core/congestion_control/bbr2_startup.h b/quic/core/congestion_control/bbr2_startup.h new file mode 100644 index 0000000..df3f9a7 --- /dev/null +++ b/quic/core/congestion_control/bbr2_startup.h
@@ -0,0 +1,68 @@ +// Copyright 2019 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. + +#ifndef QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_STARTUP_H_ +#define QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_STARTUP_H_ + +#include "net/third_party/quiche/src/quic/core/congestion_control/bbr2_misc.h" +#include "net/third_party/quiche/src/quic/core/quic_bandwidth.h" +#include "net/third_party/quiche/src/quic/core/quic_time.h" +#include "net/third_party/quiche/src/quic/core/quic_types.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_export.h" + +namespace quic { + +class Bbr2Sender; +class QUIC_EXPORT_PRIVATE Bbr2StartupMode final : public Bbr2ModeBase { + public: + Bbr2StartupMode(const Bbr2Sender* sender, Bbr2NetworkModel* model); + + void Enter(const Bbr2CongestionEvent& congestion_event) override; + + Bbr2Mode OnCongestionEvent( + QuicByteCount prior_in_flight, + QuicTime event_time, + const AckedPacketVector& acked_packets, + const LostPacketVector& lost_packets, + const Bbr2CongestionEvent& congestion_event) override; + + Limits<QuicByteCount> GetCwndLimits() const override { + return NoGreaterThan(model_->inflight_lo()); + } + + bool IsProbingForBandwidth() const override { return true; } + + bool FullBandwidthReached() const { return full_bandwidth_reached_; } + + struct DebugState { + bool full_bandwidth_reached; + QuicBandwidth full_bandwidth_baseline = QuicBandwidth::Zero(); + QuicRoundTripCount round_trips_without_bandwidth_growth; + }; + + DebugState ExportDebugState() const; + + private: + const Bbr2Params& Params() const; + + void CheckFullBandwidthReached(const Bbr2CongestionEvent& congestion_event); + + void CheckExcessiveLosses(const LostPacketVector& lost_packets, + const Bbr2CongestionEvent& congestion_event); + + bool full_bandwidth_reached_; + QuicBandwidth full_bandwidth_baseline_; + QuicRoundTripCount rounds_without_bandwidth_growth_; + + // Number of loss events in the current round trip. + int64_t loss_events_in_round_; +}; + +QUIC_EXPORT_PRIVATE std::ostream& operator<<( + std::ostream& os, + const Bbr2StartupMode::DebugState& state); + +} // namespace quic + +#endif // QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_STARTUP_H_