Initial export of QUIC BBRv2.
PiperOrigin-RevId: 259531121
Change-Id: Idbca8ab50bac5e098bda4ec0a752b1d68a4a3cd2
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
