Merge changes I01fea753,I3e67bf92,I8bdbdadd,I1a96285a,I1c67ed93
* changes:
Fix return type of QuicSpdyClientBase::latest_response_code
Change QuicSpdyStreamBodyBuffer API to decouple from QuicStreamSequencer.
gfe-relnote: Add IsStreamReady() interface to WriteScheduler and implement the interface in subclasses. No functional expected. Not protected.
Call MarkConsumed() only once in QuicSpdyStreamBodyBuffer::MarkBodyConsumed() with a combined byte count.
Add debugging logs for Priority frames.
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_
