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));
