1// Copyright 2014 The Chromium Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#include <algorithm> 6 7#include "base/logging.h" 8#include "base/stl_util.h" 9#include "net/quic/congestion_control/rtt_stats.h" 10#include "net/quic/congestion_control/tcp_loss_algorithm.h" 11#include "net/quic/quic_unacked_packet_map.h" 12#include "net/quic/test_tools/mock_clock.h" 13#include "testing/gtest/include/gtest/gtest.h" 14 15namespace net { 16namespace test { 17 18class TcpLossAlgorithmTest : public ::testing::Test { 19 protected: 20 TcpLossAlgorithmTest() 21 : unacked_packets_() { 22 rtt_stats_.UpdateRtt(QuicTime::Delta::FromMilliseconds(100), 23 QuicTime::Delta::Zero(), 24 clock_.Now()); 25 } 26 27 void SendDataPacket(QuicPacketSequenceNumber sequence_number) { 28 SerializedPacket packet(sequence_number, PACKET_1BYTE_SEQUENCE_NUMBER, 29 NULL, 0, new RetransmittableFrames()); 30 unacked_packets_.AddPacket(packet); 31 unacked_packets_.SetSent(sequence_number, clock_.Now(), 1000, true); 32 } 33 34 void VerifyLosses(QuicPacketSequenceNumber largest_observed, 35 QuicPacketSequenceNumber* losses_expected, 36 size_t num_losses) { 37 SequenceNumberSet lost_packets = 38 loss_algorithm_.DetectLostPackets( 39 unacked_packets_, clock_.Now(), largest_observed, rtt_stats_); 40 EXPECT_EQ(num_losses, lost_packets.size()); 41 for (size_t i = 0; i < num_losses; ++i) { 42 EXPECT_TRUE(ContainsKey(lost_packets, losses_expected[i])); 43 } 44 } 45 46 QuicUnackedPacketMap unacked_packets_; 47 TCPLossAlgorithm loss_algorithm_; 48 RttStats rtt_stats_; 49 MockClock clock_; 50}; 51 52TEST_F(TcpLossAlgorithmTest, NackRetransmit1Packet) { 53 const size_t kNumSentPackets = 5; 54 // Transmit 5 packets. 55 for (size_t i = 1; i <= kNumSentPackets; ++i) { 56 SendDataPacket(i); 57 } 58 // No loss on one ack. 59 unacked_packets_.RemoveFromInFlight(2); 60 unacked_packets_.NackPacket(1, 1); 61 VerifyLosses(2, NULL, 0); 62 // No loss on two acks. 63 unacked_packets_.RemoveFromInFlight(3); 64 unacked_packets_.NackPacket(1, 2); 65 VerifyLosses(3, NULL, 0); 66 // Loss on three acks. 67 unacked_packets_.RemoveFromInFlight(4); 68 unacked_packets_.NackPacket(1, 3); 69 QuicPacketSequenceNumber lost[] = { 1 }; 70 VerifyLosses(4, lost, arraysize(lost)); 71 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); 72} 73 74// A stretch ack is an ack that covers more than 1 packet of previously 75// unacknowledged data. 76TEST_F(TcpLossAlgorithmTest, NackRetransmit1PacketWith1StretchAck) { 77 const size_t kNumSentPackets = 10; 78 // Transmit 10 packets. 79 for (size_t i = 1; i <= kNumSentPackets; ++i) { 80 SendDataPacket(i); 81 } 82 83 // Nack the first packet 3 times in a single StretchAck. 84 unacked_packets_.NackPacket(1, 3); 85 unacked_packets_.RemoveFromInFlight(2); 86 unacked_packets_.RemoveFromInFlight(3); 87 unacked_packets_.RemoveFromInFlight(4); 88 QuicPacketSequenceNumber lost[] = { 1 }; 89 VerifyLosses(4, lost, arraysize(lost)); 90 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); 91} 92 93// Ack a packet 3 packets ahead, causing a retransmit. 94TEST_F(TcpLossAlgorithmTest, NackRetransmit1PacketSingleAck) { 95 const size_t kNumSentPackets = 10; 96 // Transmit 10 packets. 97 for (size_t i = 1; i <= kNumSentPackets; ++i) { 98 SendDataPacket(i); 99 } 100 101 // Nack the first packet 3 times in an AckFrame with three missing packets. 102 unacked_packets_.NackPacket(1, 3); 103 unacked_packets_.NackPacket(2, 2); 104 unacked_packets_.NackPacket(3, 1); 105 unacked_packets_.RemoveFromInFlight(4); 106 QuicPacketSequenceNumber lost[] = { 1 }; 107 VerifyLosses(4, lost, arraysize(lost)); 108 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); 109} 110 111TEST_F(TcpLossAlgorithmTest, EarlyRetransmit1Packet) { 112 const size_t kNumSentPackets = 2; 113 // Transmit 2 packets. 114 for (size_t i = 1; i <= kNumSentPackets; ++i) { 115 SendDataPacket(i); 116 } 117 // Early retransmit when the final packet gets acked and the first is nacked. 118 unacked_packets_.RemoveFromInFlight(2); 119 unacked_packets_.NackPacket(1, 1); 120 VerifyLosses(2, NULL, 0); 121 EXPECT_EQ(clock_.Now().Add(rtt_stats_.SmoothedRtt().Multiply(1.25)), 122 loss_algorithm_.GetLossTimeout()); 123 124 clock_.AdvanceTime(rtt_stats_.latest_rtt().Multiply(1.25)); 125 QuicPacketSequenceNumber lost[] = { 1 }; 126 VerifyLosses(2, lost, arraysize(lost)); 127 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); 128} 129 130TEST_F(TcpLossAlgorithmTest, EarlyRetransmitAllPackets) { 131 const size_t kNumSentPackets = 5; 132 for (size_t i = 1; i <= kNumSentPackets; ++i) { 133 SendDataPacket(i); 134 // Advance the time 1/4 RTT between 3 and 4. 135 if (i == 3) { 136 clock_.AdvanceTime(rtt_stats_.SmoothedRtt().Multiply(0.25)); 137 } 138 } 139 140 // Early retransmit when the final packet gets acked and 1.25 RTTs have 141 // elapsed since the packets were sent. 142 unacked_packets_.RemoveFromInFlight(kNumSentPackets); 143 // This simulates a single ack following multiple missing packets with FACK. 144 for (size_t i = 1; i < kNumSentPackets; ++i) { 145 unacked_packets_.NackPacket(i, kNumSentPackets - i); 146 } 147 QuicPacketSequenceNumber lost[] = { 1, 2 }; 148 VerifyLosses(kNumSentPackets, lost, arraysize(lost)); 149 // The time has already advanced 1/4 an RTT, so ensure the timeout is set 150 // 1.25 RTTs after the earliest pending packet(3), not the last(4). 151 EXPECT_EQ(clock_.Now().Add(rtt_stats_.SmoothedRtt()), 152 loss_algorithm_.GetLossTimeout()); 153 154 clock_.AdvanceTime(rtt_stats_.SmoothedRtt()); 155 QuicPacketSequenceNumber lost2[] = { 1, 2, 3 }; 156 VerifyLosses(kNumSentPackets, lost2, arraysize(lost2)); 157 EXPECT_EQ(clock_.Now().Add(rtt_stats_.SmoothedRtt().Multiply(0.25)), 158 loss_algorithm_.GetLossTimeout()); 159 clock_.AdvanceTime(rtt_stats_.SmoothedRtt().Multiply(0.25)); 160 QuicPacketSequenceNumber lost3[] = { 1, 2, 3, 4 }; 161 VerifyLosses(kNumSentPackets, lost3, arraysize(lost3)); 162 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); 163} 164 165TEST_F(TcpLossAlgorithmTest, DontEarlyRetransmitNeuteredPacket) { 166 const size_t kNumSentPackets = 2; 167 // Transmit 2 packets. 168 for (size_t i = 1; i <= kNumSentPackets; ++i) { 169 SendDataPacket(i); 170 } 171 // Neuter packet 1. 172 unacked_packets_.RemoveRetransmittability(1); 173 174 // Early retransmit when the final packet gets acked and the first is nacked. 175 unacked_packets_.IncreaseLargestObserved(2); 176 unacked_packets_.RemoveFromInFlight(2); 177 unacked_packets_.NackPacket(1, 1); 178 VerifyLosses(2, NULL, 0); 179 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); 180} 181 182} // namespace test 183} // namespace net 184