gfe-relnote: In QUIC, add adaptive reordering thresholds. Deprecate SpuriousRetransmitDetected and call SpuriousLossDetected instead. Protected by gfe2_reloadable_flag_quic_detect_spurious_loss. PiperOrigin-RevId: 268541613 Change-Id: I861b74d6cd261c30affc3e4bc1874fee4c4f3ab4
diff --git a/quic/core/congestion_control/general_loss_algorithm.cc b/quic/core/congestion_control/general_loss_algorithm.cc index 02b2129..805ee83 100644 --- a/quic/core/congestion_control/general_loss_algorithm.cc +++ b/quic/core/congestion_control/general_loss_algorithm.cc
@@ -31,6 +31,8 @@ GeneralLossAlgorithm::GeneralLossAlgorithm(LossDetectionType loss_type) : loss_detection_timeout_(QuicTime::Zero()), + reordering_threshold_(kNumberOfNacksBeforeRetransmission), + use_adaptive_reordering_threshold_(false), least_in_flight_(1), packet_number_space_(NUM_PACKET_NUMBER_SPACES) { SetLossDetectionType(loss_type); @@ -113,8 +115,7 @@ if (loss_type_ == kNack) { // FACK based loss detection. - if (largest_newly_acked - packet_number >= - kNumberOfNacksBeforeRetransmission) { + if (largest_newly_acked - packet_number >= reordering_threshold_) { packets_lost->push_back(LostPacket(packet_number, it->bytes_sent)); continue; } @@ -207,6 +208,35 @@ } while (proposed_extra_time < extra_time_needed && reordering_shift_ > 0); } +void GeneralLossAlgorithm::SpuriousLossDetected( + const QuicUnackedPacketMap& unacked_packets, + const RttStats& rtt_stats, + QuicTime ack_receive_time, + QuicPacketNumber packet_number, + QuicPacketNumber previous_largest_acked) { + if (loss_type_ == kAdaptiveTime && reordering_shift_ > 0) { + // Increase reordering fraction such that the packet would not have been + // declared lost. + QuicTime::Delta time_needed = + ack_receive_time - + unacked_packets.GetTransmissionInfo(packet_number).sent_time; + QuicTime::Delta max_rtt = + std::max(rtt_stats.previous_srtt(), rtt_stats.latest_rtt()); + while (max_rtt + (max_rtt >> reordering_shift_) < time_needed && + reordering_shift_ > 0) { + --reordering_shift_; + } + } + + if (use_adaptive_reordering_threshold_) { + DCHECK_LT(packet_number, previous_largest_acked); + // Increase reordering_threshold_ such that packet_number would not have + // been declared lost. + reordering_threshold_ = std::max( + reordering_threshold_, previous_largest_acked - packet_number + 1); + } +} + void GeneralLossAlgorithm::SetPacketNumberSpace( PacketNumberSpace packet_number_space) { if (packet_number_space_ < NUM_PACKET_NUMBER_SPACES) {
diff --git a/quic/core/congestion_control/general_loss_algorithm.h b/quic/core/congestion_control/general_loss_algorithm.h index 089387f..3bde91b 100644 --- a/quic/core/congestion_control/general_loss_algorithm.h +++ b/quic/core/congestion_control/general_loss_algorithm.h
@@ -54,10 +54,21 @@ const RttStats& rtt_stats, QuicPacketNumber spurious_retransmission) override; + // Called to increases time and/or packet threshold. + void SpuriousLossDetected(const QuicUnackedPacketMap& unacked_packets, + const RttStats& rtt_stats, + QuicTime ack_receive_time, + QuicPacketNumber packet_number, + QuicPacketNumber previous_largest_acked) override; + void SetPacketNumberSpace(PacketNumberSpace packet_number_space); int reordering_shift() const { return reordering_shift_; } + void enable_adaptive_reordering_threshold() { + use_adaptive_reordering_threshold_ = true; + } + private: QuicTime loss_detection_timeout_; // Largest sent packet when a spurious retransmit is detected. @@ -68,6 +79,10 @@ // loss. Fraction calculated by shifting max(SRTT, latest_rtt) to the right // by reordering_shift. int reordering_shift_; + // Reordering threshold for loss detection. + QuicPacketCount reordering_threshold_; + // If true, uses adaptive reordering threshold for loss detection. + bool use_adaptive_reordering_threshold_; // The largest newly acked from the previous call to DetectLosses. QuicPacketNumber largest_previously_acked_; // The least in flight packet. Loss detection should start from this. Please
diff --git a/quic/core/congestion_control/general_loss_algorithm_test.cc b/quic/core/congestion_control/general_loss_algorithm_test.cc index c03ad90..8c200cc 100644 --- a/quic/core/congestion_control/general_loss_algorithm_test.cc +++ b/quic/core/congestion_control/general_loss_algorithm_test.cc
@@ -514,6 +514,13 @@ // Advance the time 1/4 RTT and indicate the loss was spurious. // The new threshold should be 1/2 RTT. clock_.AdvanceTime(rtt_stats_.smoothed_rtt() * (1.0f / 4)); + if (GetQuicReloadableFlag(quic_detect_spurious_loss)) { + loss_algorithm_.SpuriousLossDetected(unacked_packets_, rtt_stats_, + clock_.Now(), QuicPacketNumber(1), + QuicPacketNumber(2)); + EXPECT_EQ(1, loss_algorithm_.reordering_shift()); + return; + } loss_algorithm_.SpuriousRetransmitDetected(unacked_packets_, clock_.Now(), rtt_stats_, QuicPacketNumber(11)); EXPECT_EQ(1, loss_algorithm_.reordering_shift()); @@ -525,6 +532,69 @@ EXPECT_EQ(1, loss_algorithm_.reordering_shift()); } +TEST_F(GeneralLossAlgorithmTest, IncreaseReorderingThresholdUponSpuriousLoss) { + loss_algorithm_.enable_adaptive_reordering_threshold(); + for (size_t i = 1; i <= 4; ++i) { + SendDataPacket(i); + } + // Acking 4 causes 1 detected lost. + AckedPacketVector packets_acked; + unacked_packets_.RemoveFromInFlight(QuicPacketNumber(4)); + packets_acked.push_back(AckedPacket( + QuicPacketNumber(4), kMaxOutgoingPacketSize, QuicTime::Zero())); + VerifyLosses(4, packets_acked, std::vector<uint64_t>{1}); + packets_acked.clear(); + + // Retransmit 1 as 5. + SendDataPacket(5); + + // Acking 1 such that it was detected lost spuriously. + unacked_packets_.RemoveFromInFlight(QuicPacketNumber(1)); + packets_acked.push_back(AckedPacket( + QuicPacketNumber(1), kMaxOutgoingPacketSize, QuicTime::Zero())); + loss_algorithm_.SpuriousLossDetected(unacked_packets_, rtt_stats_, + clock_.Now(), QuicPacketNumber(1), + QuicPacketNumber(4)); + VerifyLosses(4, packets_acked, std::vector<uint64_t>{}); + packets_acked.clear(); + + // Verify acking 5 does not cause 2 detected lost. + unacked_packets_.RemoveFromInFlight(QuicPacketNumber(5)); + packets_acked.push_back(AckedPacket( + QuicPacketNumber(5), kMaxOutgoingPacketSize, QuicTime::Zero())); + VerifyLosses(5, packets_acked, std::vector<uint64_t>{}); + packets_acked.clear(); + + SendDataPacket(6); + + // Acking 6 will causes 2 detected lost. + unacked_packets_.RemoveFromInFlight(QuicPacketNumber(6)); + packets_acked.push_back(AckedPacket( + QuicPacketNumber(6), kMaxOutgoingPacketSize, QuicTime::Zero())); + VerifyLosses(6, packets_acked, std::vector<uint64_t>{2}); + packets_acked.clear(); + + // Retransmit 2 as 7. + SendDataPacket(7); + + // Acking 2 such that it was detected lost spuriously. + unacked_packets_.RemoveFromInFlight(QuicPacketNumber(2)); + packets_acked.push_back(AckedPacket( + QuicPacketNumber(2), kMaxOutgoingPacketSize, QuicTime::Zero())); + loss_algorithm_.SpuriousLossDetected(unacked_packets_, rtt_stats_, + clock_.Now(), QuicPacketNumber(2), + QuicPacketNumber(6)); + VerifyLosses(6, packets_acked, std::vector<uint64_t>{}); + packets_acked.clear(); + + // Acking 7 will not cause 3 as detected lost. + unacked_packets_.RemoveFromInFlight(QuicPacketNumber(7)); + packets_acked.push_back(AckedPacket( + QuicPacketNumber(7), kMaxOutgoingPacketSize, QuicTime::Zero())); + VerifyLosses(7, packets_acked, std::vector<uint64_t>{}); + packets_acked.clear(); +} + } // namespace } // namespace test } // namespace quic
diff --git a/quic/core/congestion_control/loss_detection_interface.h b/quic/core/congestion_control/loss_detection_interface.h index 7439d3f..f686785 100644 --- a/quic/core/congestion_control/loss_detection_interface.h +++ b/quic/core/congestion_control/loss_detection_interface.h
@@ -37,11 +37,21 @@ // Called when a |spurious_retransmission| is detected. The original // transmission must have been caused by DetectLosses. + // TODO(fayang): Remove this method when deprecating + // quic_detect_spurious_loss. virtual void SpuriousRetransmitDetected( const QuicUnackedPacketMap& unacked_packets, QuicTime time, const RttStats& rtt_stats, QuicPacketNumber spurious_retransmission) = 0; + + // Called when |packet_number| was detected lost but gets acked later. + virtual void SpuriousLossDetected( + const QuicUnackedPacketMap& unacked_packets, + const RttStats& rtt_stats, + QuicTime ack_receive_time, + QuicPacketNumber packet_number, + QuicPacketNumber previous_largest_acked) = 0; }; } // namespace quic
diff --git a/quic/core/congestion_control/uber_loss_algorithm.cc b/quic/core/congestion_control/uber_loss_algorithm.cc index e0dff98..e3b526a 100644 --- a/quic/core/congestion_control/uber_loss_algorithm.cc +++ b/quic/core/congestion_control/uber_loss_algorithm.cc
@@ -81,4 +81,15 @@ spurious_retransmission); } +void UberLossAlgorithm::SpuriousLossDetected( + const QuicUnackedPacketMap& unacked_packets, + const RttStats& rtt_stats, + QuicTime ack_receive_time, + QuicPacketNumber packet_number, + QuicPacketNumber previous_largest_acked) { + general_loss_algorithms_[unacked_packets.GetPacketNumberSpace(packet_number)] + .SpuriousLossDetected(unacked_packets, rtt_stats, ack_receive_time, + packet_number, previous_largest_acked); +} + } // namespace quic
diff --git a/quic/core/congestion_control/uber_loss_algorithm.h b/quic/core/congestion_control/uber_loss_algorithm.h index dddbcb3..558aaea 100644 --- a/quic/core/congestion_control/uber_loss_algorithm.h +++ b/quic/core/congestion_control/uber_loss_algorithm.h
@@ -42,6 +42,13 @@ const RttStats& rtt_stats, QuicPacketNumber spurious_retransmission) override; + // Called to increases time or packet threshold. + void SpuriousLossDetected(const QuicUnackedPacketMap& unacked_packets, + const RttStats& rtt_stats, + QuicTime ack_receive_time, + QuicPacketNumber packet_number, + QuicPacketNumber previous_largest_acked) override; + private: LossDetectionType loss_type_; // One loss algorithm per packet number space.
diff --git a/quic/core/quic_sent_packet_manager.cc b/quic/core/quic_sent_packet_manager.cc index e167c09..7a413d0 100644 --- a/quic/core/quic_sent_packet_manager.cc +++ b/quic/core/quic_sent_packet_manager.cc
@@ -109,7 +109,9 @@ max_probe_packets_per_pto_(2), consecutive_pto_count_(0), fix_rto_retransmission_(false), - handshake_mode_disabled_(false) { + handshake_mode_disabled_(false), + detect_spurious_losses_( + GetQuicReloadableFlag(quic_detect_spurious_loss)) { SetSendAlgorithm(congestion_control_type); } @@ -535,7 +537,8 @@ QuicPacketNumber acked_packet_number) { if (session_decides_what_to_write()) { RecordOneSpuriousRetransmission(info); - if (info.transmission_type == LOSS_RETRANSMISSION) { + if (!detect_spurious_losses_ && + info.transmission_type == LOSS_RETRANSMISSION) { // Only inform the loss detection of spurious retransmits it caused. loss_algorithm_->SpuriousRetransmitDetected( unacked_packets_, clock_->Now(), rtt_stats_, acked_packet_number); @@ -603,6 +606,7 @@ void QuicSentPacketManager::MarkPacketHandled(QuicPacketNumber packet_number, QuicTransmissionInfo* info, + QuicTime ack_receive_time, QuicTime::Delta ack_delay_time, QuicTime receive_timestamp) { QuicPacketNumber newest_transmission = @@ -635,6 +639,26 @@ RecordSpuriousRetransmissions(*info, packet_number); } } + if (detect_spurious_losses_ && session_decides_what_to_write() && + info->state == LOST) { + // Record as a spurious loss as a packet previously declared lost gets + // acked. + QUIC_RELOADABLE_FLAG_COUNT(quic_detect_spurious_loss); + const PacketNumberSpace packet_number_space = + unacked_packets_.GetPacketNumberSpace(info->encryption_level); + const QuicPacketNumber previous_largest_acked = + supports_multiple_packet_number_spaces() + ? unacked_packets_.GetLargestAckedOfPacketNumberSpace( + packet_number_space) + : unacked_packets_.largest_acked(); + QUIC_DVLOG(1) << "Packet " << packet_number + << " was detected lost spuriously, " + "previous_largest_acked: " + << previous_largest_acked; + loss_algorithm_->SpuriousLossDetected(unacked_packets_, rtt_stats_, + ack_receive_time, packet_number, + previous_largest_acked); + } } else { DCHECK(!session_decides_what_to_write()); RecordSpuriousRetransmissions(*info, packet_number); @@ -1306,7 +1330,9 @@ } QUIC_DVLOG(1) << ENDPOINT << "Got an " << QuicUtils::EncryptionLevelToString(ack_decrypted_level) - << " ack for packet " << acked_packet.packet_number; + << " ack for packet " << acked_packet.packet_number + << " , state: " + << QuicUtils::SentPacketStateToString(info->state); const PacketNumberSpace packet_number_space = unacked_packets_.GetPacketNumberSpace(info->encryption_level); if (supports_multiple_packet_number_spaces() && @@ -1330,7 +1356,7 @@ } unacked_packets_.MaybeUpdateLargestAckedOfPacketNumberSpace( packet_number_space, acked_packet.packet_number); - MarkPacketHandled(acked_packet.packet_number, info, + MarkPacketHandled(acked_packet.packet_number, info, ack_receive_time, last_ack_frame_.ack_delay_time, acked_packet.receive_timestamp); }
diff --git a/quic/core/quic_sent_packet_manager.h b/quic/core/quic_sent_packet_manager.h index e50a181..cbb00a9 100644 --- a/quic/core/quic_sent_packet_manager.h +++ b/quic/core/quic_sent_packet_manager.h
@@ -491,6 +491,7 @@ // |info| due to receipt by the peer. void MarkPacketHandled(QuicPacketNumber packet_number, QuicTransmissionInfo* info, + QuicTime ack_receive_time, QuicTime::Delta ack_delay_time, QuicTime receive_timestamp); @@ -656,6 +657,9 @@ // True if HANDSHAKE mode has been disabled. bool handshake_mode_disabled_; + + // Latched value of quic_detect_spurious_loss. + const bool detect_spurious_losses_; }; } // namespace quic
diff --git a/quic/core/quic_sent_packet_manager_test.cc b/quic/core/quic_sent_packet_manager_test.cc index be22dee..b0806e5 100644 --- a/quic/core/quic_sent_packet_manager_test.cc +++ b/quic/core/quic_sent_packet_manager_test.cc
@@ -774,8 +774,15 @@ uint64_t acked[] = {3}; ExpectAcksAndLosses(false, acked, QUIC_ARRAYSIZE(acked), nullptr, 0); EXPECT_CALL(*loss_algorithm, DetectLosses(_, _, _, _, _, _)); - EXPECT_CALL(*loss_algorithm, - SpuriousRetransmitDetected(_, _, _, QuicPacketNumber(5))); + if (GetQuicReloadableFlag(quic_detect_spurious_loss) && + manager_.session_decides_what_to_write()) { + EXPECT_CALL(*loss_algorithm, + SpuriousLossDetected(_, _, _, QuicPacketNumber(3), + QuicPacketNumber(4))); + } else { + EXPECT_CALL(*loss_algorithm, + SpuriousRetransmitDetected(_, _, _, QuicPacketNumber(5))); + } manager_.OnAckFrameStart(QuicPacketNumber(4), QuicTime::Delta::Infinite(), clock_.Now()); manager_.OnAckRange(QuicPacketNumber(3), QuicPacketNumber(5));
diff --git a/quic/test_tools/quic_test_utils.h b/quic/test_tools/quic_test_utils.h index 90fa9b1..da04f42 100644 --- a/quic/test_tools/quic_test_utils.h +++ b/quic/test_tools/quic_test_utils.h
@@ -951,6 +951,12 @@ QuicTime, const RttStats&, QuicPacketNumber)); + MOCK_METHOD5(SpuriousLossDetected, + void(const QuicUnackedPacketMap&, + const RttStats&, + QuicTime, + QuicPacketNumber, + QuicPacketNumber)); }; class MockAckListener : public QuicAckListenerInterface {