Implement L4S version of Cubic congestion control for QUIC. See go/prague-cubic for details. PiperOrigin-RevId: 675316348
diff --git a/build/source_list.bzl b/build/source_list.bzl index 4f1c45f..e32fc09 100644 --- a/build/source_list.bzl +++ b/build/source_list.bzl
@@ -154,6 +154,7 @@ "quic/core/congestion_control/hybrid_slow_start.h", "quic/core/congestion_control/loss_detection_interface.h", "quic/core/congestion_control/pacing_sender.h", + "quic/core/congestion_control/prague_sender.h", "quic/core/congestion_control/prr_sender.h", "quic/core/congestion_control/rtt_stats.h", "quic/core/congestion_control/send_algorithm_interface.h", @@ -510,6 +511,7 @@ "quic/core/congestion_control/general_loss_algorithm.cc", "quic/core/congestion_control/hybrid_slow_start.cc", "quic/core/congestion_control/pacing_sender.cc", + "quic/core/congestion_control/prague_sender.cc", "quic/core/congestion_control/prr_sender.cc", "quic/core/congestion_control/rtt_stats.cc", "quic/core/congestion_control/send_algorithm_interface.cc", @@ -1186,6 +1188,7 @@ "quic/core/congestion_control/general_loss_algorithm_test.cc", "quic/core/congestion_control/hybrid_slow_start_test.cc", "quic/core/congestion_control/pacing_sender_test.cc", + "quic/core/congestion_control/prague_sender_test.cc", "quic/core/congestion_control/prr_sender_test.cc", "quic/core/congestion_control/rtt_stats_test.cc", "quic/core/congestion_control/send_algorithm_test.cc",
diff --git a/build/source_list.gni b/build/source_list.gni index e5285c3..98d1fc3 100644 --- a/build/source_list.gni +++ b/build/source_list.gni
@@ -154,6 +154,7 @@ "src/quiche/quic/core/congestion_control/hybrid_slow_start.h", "src/quiche/quic/core/congestion_control/loss_detection_interface.h", "src/quiche/quic/core/congestion_control/pacing_sender.h", + "src/quiche/quic/core/congestion_control/prague_sender.h", "src/quiche/quic/core/congestion_control/prr_sender.h", "src/quiche/quic/core/congestion_control/rtt_stats.h", "src/quiche/quic/core/congestion_control/send_algorithm_interface.h", @@ -510,6 +511,7 @@ "src/quiche/quic/core/congestion_control/general_loss_algorithm.cc", "src/quiche/quic/core/congestion_control/hybrid_slow_start.cc", "src/quiche/quic/core/congestion_control/pacing_sender.cc", + "src/quiche/quic/core/congestion_control/prague_sender.cc", "src/quiche/quic/core/congestion_control/prr_sender.cc", "src/quiche/quic/core/congestion_control/rtt_stats.cc", "src/quiche/quic/core/congestion_control/send_algorithm_interface.cc", @@ -1187,6 +1189,7 @@ "src/quiche/quic/core/congestion_control/general_loss_algorithm_test.cc", "src/quiche/quic/core/congestion_control/hybrid_slow_start_test.cc", "src/quiche/quic/core/congestion_control/pacing_sender_test.cc", + "src/quiche/quic/core/congestion_control/prague_sender_test.cc", "src/quiche/quic/core/congestion_control/prr_sender_test.cc", "src/quiche/quic/core/congestion_control/rtt_stats_test.cc", "src/quiche/quic/core/congestion_control/send_algorithm_test.cc",
diff --git a/build/source_list.json b/build/source_list.json index b1daa01..e1ed864 100644 --- a/build/source_list.json +++ b/build/source_list.json
@@ -153,6 +153,7 @@ "quiche/quic/core/congestion_control/hybrid_slow_start.h", "quiche/quic/core/congestion_control/loss_detection_interface.h", "quiche/quic/core/congestion_control/pacing_sender.h", + "quiche/quic/core/congestion_control/prague_sender.h", "quiche/quic/core/congestion_control/prr_sender.h", "quiche/quic/core/congestion_control/rtt_stats.h", "quiche/quic/core/congestion_control/send_algorithm_interface.h", @@ -509,6 +510,7 @@ "quiche/quic/core/congestion_control/general_loss_algorithm.cc", "quiche/quic/core/congestion_control/hybrid_slow_start.cc", "quiche/quic/core/congestion_control/pacing_sender.cc", + "quiche/quic/core/congestion_control/prague_sender.cc", "quiche/quic/core/congestion_control/prr_sender.cc", "quiche/quic/core/congestion_control/rtt_stats.cc", "quiche/quic/core/congestion_control/send_algorithm_interface.cc", @@ -1186,6 +1188,7 @@ "quiche/quic/core/congestion_control/general_loss_algorithm_test.cc", "quiche/quic/core/congestion_control/hybrid_slow_start_test.cc", "quiche/quic/core/congestion_control/pacing_sender_test.cc", + "quiche/quic/core/congestion_control/prague_sender_test.cc", "quiche/quic/core/congestion_control/prr_sender_test.cc", "quiche/quic/core/congestion_control/rtt_stats_test.cc", "quiche/quic/core/congestion_control/send_algorithm_test.cc",
diff --git a/quiche/quic/core/congestion_control/prague_sender.cc b/quiche/quic/core/congestion_control/prague_sender.cc new file mode 100644 index 0000000..b707efa --- /dev/null +++ b/quiche/quic/core/congestion_control/prague_sender.cc
@@ -0,0 +1,158 @@ +// Copyright (c) 2024 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 "quiche/quic/core/congestion_control/prague_sender.h" + +#include <algorithm> + +#include "quiche/quic/core/congestion_control/rtt_stats.h" +#include "quiche/quic/core/congestion_control/tcp_cubic_sender_bytes.h" +#include "quiche/quic/core/quic_clock.h" +#include "quiche/quic/core/quic_connection_stats.h" +#include "quiche/quic/core/quic_time.h" +#include "quiche/quic/core/quic_types.h" + +namespace quic { + +PragueSender::PragueSender(const QuicClock* clock, const RttStats* rtt_stats, + QuicPacketCount initial_tcp_congestion_window, + QuicPacketCount max_congestion_window, + QuicConnectionStats* stats) + : TcpCubicSenderBytes(clock, rtt_stats, false, + initial_tcp_congestion_window, max_congestion_window, + stats), + connection_start_time_(clock->Now()), + last_alpha_update_(connection_start_time_) {} + +void PragueSender::OnCongestionEvent(bool rtt_updated, + QuicByteCount prior_in_flight, + QuicTime event_time, + const AckedPacketVector& acked_packets, + const LostPacketVector& lost_packets, + QuicPacketCount num_ect, + QuicPacketCount num_ce) { + if (!ect1_enabled_) { + TcpCubicSenderBytes::OnCongestionEvent(rtt_updated, prior_in_flight, + event_time, acked_packets, + lost_packets, num_ect, num_ce); + return; + } + // Update Prague-specific variables. + if (rtt_updated) { + rtt_virt_ = std::max(rtt_stats()->smoothed_rtt(), kPragueRttVirtMin); + } + if (prague_alpha_.has_value()) { + ect_count_ += num_ect; + ce_count_ += num_ce; + if (event_time - last_alpha_update_ > rtt_virt_) { + // Update alpha once per virtual RTT. + float frac = static_cast<float>(ce_count_) / + static_cast<float>(ect_count_ + ce_count_); + prague_alpha_ = + (1 - kPragueEwmaGain) * *prague_alpha_ + kPragueEwmaGain * frac; + last_alpha_update_ = event_time; + ect_count_ = 0; + ce_count_ = 0; + } + } else if (num_ce > 0) { + last_alpha_update_ = event_time; + prague_alpha_ = 1.0; + ect_count_ = num_ect; + ce_count_ = num_ce; + } + if (!lost_packets.empty() && last_congestion_response_time_.has_value() && + (event_time - *last_congestion_response_time_ < rtt_virt_)) { + // Give credit for recent ECN cwnd reductions if there is a packet loss. + QuicByteCount previous_reduction = last_congestion_response_size_; + last_congestion_response_time_.reset(); + set_congestion_window(GetCongestionWindow() + previous_reduction); + } + // Due to shorter RTTs with L4S, and the longer virtual RTT, after 500 RTTs + // congestion avoidance should grow slower than in Cubic. + if (!reduce_rtt_dependence_) { + reduce_rtt_dependence_ = + !InSlowStart() && lost_packets.empty() && + (event_time - connection_start_time_) > + kRoundsBeforeReducedRttDependence * rtt_stats()->smoothed_rtt(); + } + float congestion_avoidance_deflator; + if (reduce_rtt_dependence_) { + congestion_avoidance_deflator = + static_cast<float>(rtt_stats()->smoothed_rtt().ToMicroseconds()) / + static_cast<float>(rtt_virt_.ToMicroseconds()); + congestion_avoidance_deflator *= congestion_avoidance_deflator; + } else { + congestion_avoidance_deflator = 1.0f; + } + QuicByteCount original_cwnd = GetCongestionWindow(); + if (num_ce == 0 || !lost_packets.empty()) { + // Fast path. No ECN specific logic except updating stats, adjusting for + // previous CE responses, and reduced RTT dependence. + TcpCubicSenderBytes::OnCongestionEvent(rtt_updated, prior_in_flight, + event_time, acked_packets, + lost_packets, num_ect, num_ce); + if (lost_packets.empty() && reduce_rtt_dependence_ && + original_cwnd < GetCongestionWindow()) { + QuicByteCount cwnd_increase = GetCongestionWindow() - original_cwnd; + set_congestion_window(original_cwnd + + cwnd_increase * congestion_avoidance_deflator); + } + return; + } + // num_ce > 0 and lost_packets is empty. + if (InSlowStart()) { + ExitSlowstart(); + } + // Estimate bytes that were CE marked + QuicByteCount bytes_acked = 0; + for (auto packet : acked_packets) { + bytes_acked += packet.bytes_acked; + } + float ce_fraction = + static_cast<float>(num_ce) / static_cast<float>(num_ect + num_ce); + QuicByteCount bytes_ce = bytes_acked * ce_fraction; + QuicPacketCount ce_packets_remaining = num_ce; + bytes_acked -= bytes_ce; + if (!last_congestion_response_time_.has_value() || + event_time - *last_congestion_response_time_ > rtt_virt_) { + last_congestion_response_time_ = event_time; + // Create a synthetic loss to trigger a loss response. The packet number + // needs to be large enough to not be before the last loss response, which + // should be easy since acked packet numbers should be higher than lost + // packet numbers, due to the delay in detecting loss. + while (ce_packets_remaining > 0) { + OnPacketLost(acked_packets.back().packet_number, bytes_ce, + prior_in_flight); + bytes_ce = 0; + ce_packets_remaining--; + } + QuicByteCount cwnd_reduction = original_cwnd - GetCongestionWindow(); + last_congestion_response_size_ = cwnd_reduction * *prague_alpha_; + set_congestion_window(original_cwnd - last_congestion_response_size_); + set_slowstart_threshold(GetCongestionWindow()); + ExitRecovery(); + } + if (num_ect == 0) { + return; + } + for (const AckedPacket& acked : acked_packets) { + // Timing matters so report all of the packets faithfully, but reduce the + // size to reflect that some bytes were marked CE. + OnPacketAcked( + acked.packet_number, + acked.bytes_acked * (1 - ce_fraction) * congestion_avoidance_deflator, + prior_in_flight, event_time); + } +} + +CongestionControlType PragueSender::GetCongestionControlType() const { + return kPragueCubic; +} + +bool PragueSender::EnableECT1() { + ect1_enabled_ = true; + return true; +} + +} // namespace quic
diff --git a/quiche/quic/core/congestion_control/prague_sender.h b/quiche/quic/core/congestion_control/prague_sender.h new file mode 100644 index 0000000..a13ebae --- /dev/null +++ b/quiche/quic/core/congestion_control/prague_sender.h
@@ -0,0 +1,82 @@ +// Copyright (c) 2024 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. + +// A modification of Cubic to match Prague congestion control, as described in +// draft-briscoe-iccrg-prague-congestion-control-04. + +#ifndef QUICHE_QUIC_CORE_CONGESTION_CONTROL_PRAGUE_SENDER_H_ +#define QUICHE_QUIC_CORE_CONGESTION_CONTROL_PRAGUE_SENDER_H_ + +#include <optional> + +#include "quiche/quic/core/congestion_control/rtt_stats.h" +#include "quiche/quic/core/congestion_control/send_algorithm_interface.h" +#include "quiche/quic/core/congestion_control/tcp_cubic_sender_bytes.h" +#include "quiche/quic/core/quic_connection_stats.h" +#include "quiche/quic/core/quic_time.h" +#include "quiche/quic/core/quic_types.h" +#include "quiche/common/platform/api/quiche_export.h" + +namespace quic { + +class RttStats; + +constexpr float kPragueEwmaGain = 1 / 16.0; +constexpr QuicTime::Delta kPragueRttVirtMin = + QuicTime::Delta::FromMilliseconds(25); +constexpr int kRoundsBeforeReducedRttDependence = 500; + +namespace test { +class PragueSenderPeer; +} // namespace test + +class QUICHE_EXPORT PragueSender : public TcpCubicSenderBytes { + public: + PragueSender(const QuicClock* clock, const RttStats* rtt_stats, + QuicPacketCount initial_tcp_congestion_window, + QuicPacketCount max_congestion_window, + QuicConnectionStats* stats); + PragueSender(const PragueSender&) = delete; + PragueSender& operator=(const PragueSender&) = delete; + ~PragueSender() override {} + + // Start implementation of SendAlgorithmInterface overrides. + void OnCongestionEvent(bool rtt_updated, QuicByteCount prior_in_flight, + QuicTime event_time, + const AckedPacketVector& acked_packets, + const LostPacketVector& lost_packets, + QuicPacketCount num_ect, + QuicPacketCount num_ce) override; + CongestionControlType GetCongestionControlType() const override; + bool EnableECT1() override; + // End implementation of SendAlgorithmInterface overrides. + + private: + friend class test::PragueSenderPeer; + + bool ect1_enabled_ = false; + + // Tracks the life of the connection to begin reducing RTT dependence of + // congestion avoidance after 500 RTTs. + QuicTime connection_start_time_; + bool reduce_rtt_dependence_ = false; + + // Alpha-related variables + std::optional<float> prague_alpha_; + QuicPacketCount ect_count_ = 0; + QuicPacketCount ce_count_ = 0; + + // Virtual RTT related variables + QuicTime::Delta rtt_virt_ = kPragueRttVirtMin; + QuicTime last_alpha_update_; + + // Accounting for recent CE-based cwnd reductions that are "credit" for future + // loss responses. + std::optional<QuicTime> last_congestion_response_time_; + QuicByteCount last_congestion_response_size_; +}; + +} // namespace quic + +#endif // QUICHE_QUIC_CORE_CONGESTION_CONTROL_PRAGUE_SENDER_H_
diff --git a/quiche/quic/core/congestion_control/prague_sender_test.cc b/quiche/quic/core/congestion_control/prague_sender_test.cc new file mode 100644 index 0000000..3b38eec --- /dev/null +++ b/quiche/quic/core/congestion_control/prague_sender_test.cc
@@ -0,0 +1,273 @@ +// Copyright (c) 2015 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 "quiche/quic/core/congestion_control/prague_sender.h" + +#include <cstdint> +#include <optional> + +#include "quiche/quic/core/congestion_control/cubic_bytes.h" +#include "quiche/quic/core/congestion_control/rtt_stats.h" +#include "quiche/quic/core/congestion_control/send_algorithm_interface.h" +#include "quiche/quic/core/quic_clock.h" +#include "quiche/quic/core/quic_connection_stats.h" +#include "quiche/quic/core/quic_constants.h" +#include "quiche/quic/core/quic_packet_number.h" +#include "quiche/quic/core/quic_time.h" +#include "quiche/quic/core/quic_types.h" +#include "quiche/quic/platform/api/quic_test.h" +#include "quiche/quic/test_tools/mock_clock.h" + +namespace quic::test { + +// TODO(ianswett): A number of theses tests were written with the assumption of +// an initial CWND of 10. They have carefully calculated values which should be +// updated to be based on kInitialCongestionWindow. +const uint32_t kInitialCongestionWindowPackets = 10; +const uint32_t kMaxCongestionWindowPackets = 200; +const QuicTime::Delta kRtt = QuicTime::Delta::FromMilliseconds(10); + +class PragueSenderPeer : public PragueSender { + public: + explicit PragueSenderPeer(const QuicClock* clock) + : PragueSender(clock, &rtt_stats_, kInitialCongestionWindowPackets, + kMaxCongestionWindowPackets, &stats_) {} + + QuicTimeDelta rtt_virt() const { return rtt_virt_; } + bool InReducedRttDependenceMode() const { return reduce_rtt_dependence_; } + float alpha() const { return *prague_alpha_; } + + RttStats rtt_stats_; + QuicConnectionStats stats_; +}; + +class PragueSenderTest : public QuicTest { + protected: + PragueSenderTest() + : one_ms_(QuicTime::Delta::FromMilliseconds(1)), + sender_(&clock_), + packet_number_(1), + acked_packet_number_(0), + bytes_in_flight_(0), + cubic_(&clock_) { + EXPECT_TRUE(sender_.EnableECT1()); + } + + int SendAvailableSendWindow() { + return SendAvailableSendWindow(kDefaultTCPMSS); + } + + int SendAvailableSendWindow(QuicPacketLength /*packet_length*/) { + // Send as long as TimeUntilSend returns Zero. + int packets_sent = 0; + bool can_send = sender_.CanSend(bytes_in_flight_); + while (can_send) { + sender_.OnPacketSent(clock_.Now(), bytes_in_flight_, + QuicPacketNumber(packet_number_++), kDefaultTCPMSS, + HAS_RETRANSMITTABLE_DATA); + ++packets_sent; + bytes_in_flight_ += kDefaultTCPMSS; + can_send = sender_.CanSend(bytes_in_flight_); + } + return packets_sent; + } + + // Normal is that TCP acks every other segment. + void AckNPackets(int n, int ce) { + EXPECT_LE(ce, n); + sender_.rtt_stats_.UpdateRtt(kRtt, QuicTime::Delta::Zero(), clock_.Now()); + AckedPacketVector acked_packets; + LostPacketVector lost_packets; + for (int i = 0; i < n; ++i) { + ++acked_packet_number_; + acked_packets.push_back( + AckedPacket(QuicPacketNumber(acked_packet_number_), kDefaultTCPMSS, + QuicTime::Zero())); + } + sender_.OnCongestionEvent(true, bytes_in_flight_, clock_.Now(), + acked_packets, lost_packets, n - ce, ce); + bytes_in_flight_ -= n * kDefaultTCPMSS; + clock_.AdvanceTime(one_ms_); + } + + void LoseNPackets(int n) { LoseNPackets(n, kDefaultTCPMSS); } + + void LoseNPackets(int n, QuicPacketLength packet_length) { + AckedPacketVector acked_packets; + LostPacketVector lost_packets; + for (int i = 0; i < n; ++i) { + ++acked_packet_number_; + lost_packets.push_back( + LostPacket(QuicPacketNumber(acked_packet_number_), packet_length)); + } + sender_.OnCongestionEvent(false, bytes_in_flight_, clock_.Now(), + acked_packets, lost_packets, 0, 0); + bytes_in_flight_ -= n * packet_length; + } + + // Does not increment acked_packet_number_. + void LosePacket(uint64_t packet_number) { + AckedPacketVector acked_packets; + LostPacketVector lost_packets; + lost_packets.push_back( + LostPacket(QuicPacketNumber(packet_number), kDefaultTCPMSS)); + sender_.OnCongestionEvent(false, bytes_in_flight_, clock_.Now(), + acked_packets, lost_packets, 0, 0); + bytes_in_flight_ -= kDefaultTCPMSS; + } + + void MaybeUpdateAlpha(float& alpha, QuicTime& last_update, uint64_t& ect, + uint64_t& ce) { + if (clock_.Now() - last_update > kPragueRttVirtMin) { + float frac = static_cast<float>(ce) / static_cast<float>(ect + ce); + alpha = (1 - kPragueEwmaGain) * alpha + kPragueEwmaGain * frac; + last_update = clock_.Now(); + ect = 0; + ce = 0; + } + } + + const QuicTime::Delta one_ms_; + MockClock clock_; + PragueSenderPeer sender_; + uint64_t packet_number_; + uint64_t acked_packet_number_; + QuicByteCount bytes_in_flight_; + // Since CubicBytes is not mockable, this copy will verify that PragueSender + // is getting results equivalent to the expected calls to CubicBytes. + CubicBytes cubic_; +}; + +TEST_F(PragueSenderTest, EcnResponseInCongestionAvoidance) { + int num_sent = SendAvailableSendWindow(); + + // Make sure we fall out of slow start. + QuicByteCount expected_cwnd = sender_.GetCongestionWindow(); + LoseNPackets(1); + expected_cwnd = cubic_.CongestionWindowAfterPacketLoss(expected_cwnd); + EXPECT_EQ(expected_cwnd, sender_.GetCongestionWindow()); + + // Ack the rest of the outstanding packets to get out of recovery. + for (int i = 1; i < num_sent; ++i) { + AckNPackets(1, 0); + } + // Exiting recovery; cwnd should not have increased. + EXPECT_EQ(expected_cwnd, sender_.GetCongestionWindow()); + EXPECT_EQ(0u, bytes_in_flight_); + // Send a new window of data and ack all; cubic growth should occur. + num_sent = SendAvailableSendWindow(); + + // Ack packets until the CWND increases. + QuicByteCount original_cwnd = sender_.GetCongestionWindow(); + while (sender_.GetCongestionWindow() == original_cwnd) { + AckNPackets(1, 0); + expected_cwnd = cubic_.CongestionWindowAfterAck( + kDefaultTCPMSS, expected_cwnd, kRtt, clock_.Now()); + EXPECT_EQ(expected_cwnd, sender_.GetCongestionWindow()); + SendAvailableSendWindow(); + } + // Bytes in flight may be larger than the CWND if the CWND isn't an exact + // multiple of the packet sizes being sent. + EXPECT_GE(bytes_in_flight_, sender_.GetCongestionWindow()); + + // Advance time 2 seconds waiting for an ack. + clock_.AdvanceTime(kRtt); + + // First CE mark. Should be treated as a loss. Alpha = 1 so it is the full + // Cubic loss response. + original_cwnd = sender_.GetCongestionWindow(); + AckNPackets(2, 1); + // Process the "loss", then the ack. + expected_cwnd = cubic_.CongestionWindowAfterPacketLoss(expected_cwnd); + QuicByteCount expected_ssthresh = expected_cwnd; + QuicByteCount loss_reduction = original_cwnd - expected_cwnd; + expected_cwnd = cubic_.CongestionWindowAfterAck( + kDefaultTCPMSS / 2, expected_cwnd, kRtt, clock_.Now()); + expected_cwnd = cubic_.CongestionWindowAfterAck( + kDefaultTCPMSS / 2, expected_cwnd, kRtt, clock_.Now()); + EXPECT_EQ(expected_cwnd, sender_.GetCongestionWindow()); + EXPECT_EQ(expected_ssthresh, sender_.GetSlowStartThreshold()); + + // Second CE mark is ignored. + AckNPackets(1, 1); + EXPECT_EQ(expected_cwnd, sender_.GetCongestionWindow()); + + // Since there was a full loss response, a subsequent loss should incorporate + // that. + LoseNPackets(1); + expected_cwnd = + cubic_.CongestionWindowAfterPacketLoss(expected_cwnd + loss_reduction); + EXPECT_EQ(expected_cwnd, sender_.GetCongestionWindow()); + EXPECT_EQ(expected_cwnd, sender_.GetSlowStartThreshold()); + + // With 10ms inputs, rtt_virt_ should be at the minimum value. + EXPECT_EQ(sender_.rtt_virt().ToMilliseconds(), 25); +} + +TEST_F(PragueSenderTest, EcnResponseInSlowStart) { + SendAvailableSendWindow(); + AckNPackets(1, 1); + EXPECT_FALSE(sender_.InSlowStart()); +} + +TEST_F(PragueSenderTest, ReducedRttDependence) { + float expected_alpha; + uint64_t num_ect = 0; + uint64_t num_ce = 0; + std::optional<QuicTime> last_alpha_update; + std::optional<QuicTime> last_decrease; + // While trying to get to 50 RTTs, check that alpha is being updated properly, + // and is applied to CE response. + while (!sender_.InReducedRttDependenceMode()) { + int num_sent = SendAvailableSendWindow(); + clock_.AdvanceTime(kRtt); + for (int i = 0; (i < num_sent - 1); ++i) { + if (last_alpha_update.has_value()) { + ++num_ect; + MaybeUpdateAlpha(expected_alpha, last_alpha_update.value(), num_ect, + num_ce); + } + AckNPackets(1, 0); + } + QuicByteCount cwnd = sender_.GetCongestionWindow(); + num_ce++; + if (last_alpha_update.has_value()) { + MaybeUpdateAlpha(expected_alpha, last_alpha_update.value(), num_ect, + num_ce); + } else { + // First CE mark starts the update + expected_alpha = 1.0; + last_alpha_update = clock_.Now(); + } + AckNPackets(1, 1); + bool simulated_loss = false; + if (!last_decrease.has_value() || + (clock_.Now() - last_decrease.value() > sender_.rtt_virt())) { + QuicByteCount new_cwnd = cubic_.CongestionWindowAfterPacketLoss(cwnd); + // Add one byte to fix a rounding error. + QuicByteCount reduction = (cwnd - new_cwnd) * expected_alpha; + cwnd -= reduction; + last_decrease = clock_.Now(); + simulated_loss = true; + } + EXPECT_EQ(expected_alpha, sender_.alpha()); + EXPECT_EQ(cwnd, sender_.GetCongestionWindow()); + // This is the one spot where PragueSender has to manually update ssthresh. + if (simulated_loss) { + EXPECT_EQ(cwnd, sender_.GetSlowStartThreshold()); + } + } + SendAvailableSendWindow(); + // Next ack should be scaled by 1/M^2 = 1/2.5^2 + QuicByteCount expected_cwnd = sender_.GetCongestionWindow(); + QuicByteCount expected_increase = + cubic_.CongestionWindowAfterAck(kDefaultTCPMSS, expected_cwnd, kRtt, + clock_.Now()) - + expected_cwnd; + expected_increase = static_cast<float>(expected_increase) / (2.5 * 2.5); + AckNPackets(1, 0); + EXPECT_EQ(expected_cwnd + expected_increase, sender_.GetCongestionWindow()); +} + +} // namespace quic::test
diff --git a/quiche/quic/core/congestion_control/send_algorithm_interface.cc b/quiche/quic/core/congestion_control/send_algorithm_interface.cc index 89b1ce9..64b4c0d 100644 --- a/quiche/quic/core/congestion_control/send_algorithm_interface.cc +++ b/quiche/quic/core/congestion_control/send_algorithm_interface.cc
@@ -7,6 +7,7 @@ #include "absl/base/attributes.h" #include "quiche/quic/core/congestion_control/bbr2_sender.h" #include "quiche/quic/core/congestion_control/bbr_sender.h" +#include "quiche/quic/core/congestion_control/prague_sender.h" #include "quiche/quic/core/congestion_control/tcp_cubic_sender_bytes.h" #include "quiche/quic/core/quic_packets.h" #include "quiche/quic/platform/api/quic_bug_tracker.h" @@ -51,6 +52,9 @@ return new TcpCubicSenderBytes(clock, rtt_stats, true /* use Reno */, initial_congestion_window, max_congestion_window, stats); + case kPragueCubic: + return new PragueSender(clock, rtt_stats, initial_congestion_window, + max_congestion_window, stats); } return nullptr; }
diff --git a/quiche/quic/core/congestion_control/tcp_cubic_sender_bytes.h b/quiche/quic/core/congestion_control/tcp_cubic_sender_bytes.h index 9162f62..de003f7 100644 --- a/quiche/quic/core/congestion_control/tcp_cubic_sender_bytes.h +++ b/quiche/quic/core/congestion_control/tcp_cubic_sender_bytes.h
@@ -86,7 +86,6 @@ bool IsCwndLimited(QuicByteCount bytes_in_flight) const; - // TODO(ianswett): Remove these and migrate to OnCongestionEvent. void OnPacketAcked(QuicPacketNumber acked_packet_number, QuicByteCount acked_bytes, QuicByteCount prior_in_flight, QuicTime event_time); @@ -100,6 +99,13 @@ QuicByteCount acked_bytes, QuicByteCount prior_in_flight, QuicTime event_time); void HandleRetransmissionTimeout(); + const RttStats* rtt_stats() const { return rtt_stats_; } + + void set_congestion_window(QuicByteCount cwnd) { congestion_window_ = cwnd; } + void set_slowstart_threshold(QuicByteCount ssthresh) { + slowstart_threshold_ = ssthresh; + } + void ExitRecovery() { largest_sent_at_last_cutback_.Clear(); } private: friend class test::TcpCubicSenderBytesPeer;
diff --git a/quiche/quic/core/quic_types.cc b/quiche/quic/core/quic_types.cc index 31314cb..fff80a9 100644 --- a/quiche/quic/core/quic_types.cc +++ b/quiche/quic/core/quic_types.cc
@@ -325,6 +325,8 @@ return "PCC"; case kGoogCC: return "GoogCC"; + case kPragueCubic: + return "PRAGUE_CUBIC"; } return absl::StrCat("Unknown(", static_cast<int>(cc_type), ")"); }
diff --git a/quiche/quic/core/quic_types.h b/quiche/quic/core/quic_types.h index af3380b..2ffd824 100644 --- a/quiche/quic/core/quic_types.h +++ b/quiche/quic/core/quic_types.h
@@ -453,6 +453,7 @@ kGoogCC, kBBRv2, // TODO(rch): This is effectively BBRv3. We should finish the // implementation and rename this enum. + kPragueCubic, }; QUICHE_EXPORT std::string CongestionControlTypeToString(