OLD | NEW |
| (Empty) |
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 | |
15 using std::vector; | |
16 | |
17 namespace net { | |
18 namespace test { | |
19 namespace { | |
20 | |
21 // Default packet length. | |
22 const uint32 kDefaultLength = 1000; | |
23 | |
24 class TcpLossAlgorithmTest : public ::testing::Test { | |
25 protected: | |
26 TcpLossAlgorithmTest() | |
27 : unacked_packets_() { | |
28 rtt_stats_.UpdateRtt(QuicTime::Delta::FromMilliseconds(100), | |
29 QuicTime::Delta::Zero(), | |
30 clock_.Now()); | |
31 } | |
32 | |
33 ~TcpLossAlgorithmTest() override { | |
34 STLDeleteElements(&packets_); | |
35 } | |
36 | |
37 void SendDataPacket(QuicPacketSequenceNumber sequence_number) { | |
38 packets_.push_back(new QuicEncryptedPacket(nullptr, kDefaultLength)); | |
39 SerializedPacket packet(sequence_number, PACKET_1BYTE_SEQUENCE_NUMBER, | |
40 packets_.back(), 0, new RetransmittableFrames()); | |
41 unacked_packets_.AddSentPacket(packet, 0, NOT_RETRANSMISSION, clock_.Now(), | |
42 1000, true); | |
43 } | |
44 | |
45 void VerifyLosses(QuicPacketSequenceNumber largest_observed, | |
46 QuicPacketSequenceNumber* losses_expected, | |
47 size_t num_losses) { | |
48 SequenceNumberSet lost_packets = | |
49 loss_algorithm_.DetectLostPackets( | |
50 unacked_packets_, clock_.Now(), largest_observed, rtt_stats_); | |
51 EXPECT_EQ(num_losses, lost_packets.size()); | |
52 for (size_t i = 0; i < num_losses; ++i) { | |
53 EXPECT_TRUE(ContainsKey(lost_packets, losses_expected[i])); | |
54 } | |
55 } | |
56 | |
57 vector<QuicEncryptedPacket*> packets_; | |
58 QuicUnackedPacketMap unacked_packets_; | |
59 TCPLossAlgorithm loss_algorithm_; | |
60 RttStats rtt_stats_; | |
61 MockClock clock_; | |
62 }; | |
63 | |
64 TEST_F(TcpLossAlgorithmTest, NackRetransmit1Packet) { | |
65 const size_t kNumSentPackets = 5; | |
66 // Transmit 5 packets. | |
67 for (size_t i = 1; i <= kNumSentPackets; ++i) { | |
68 SendDataPacket(i); | |
69 } | |
70 // No loss on one ack. | |
71 unacked_packets_.RemoveFromInFlight(2); | |
72 unacked_packets_.NackPacket(1, 1); | |
73 VerifyLosses(2, nullptr, 0); | |
74 // No loss on two acks. | |
75 unacked_packets_.RemoveFromInFlight(3); | |
76 unacked_packets_.NackPacket(1, 2); | |
77 VerifyLosses(3, nullptr, 0); | |
78 // Loss on three acks. | |
79 unacked_packets_.RemoveFromInFlight(4); | |
80 unacked_packets_.NackPacket(1, 3); | |
81 QuicPacketSequenceNumber lost[] = {1}; | |
82 VerifyLosses(4, lost, arraysize(lost)); | |
83 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | |
84 } | |
85 | |
86 // A stretch ack is an ack that covers more than 1 packet of previously | |
87 // unacknowledged data. | |
88 TEST_F(TcpLossAlgorithmTest, NackRetransmit1PacketWith1StretchAck) { | |
89 const size_t kNumSentPackets = 10; | |
90 // Transmit 10 packets. | |
91 for (size_t i = 1; i <= kNumSentPackets; ++i) { | |
92 SendDataPacket(i); | |
93 } | |
94 | |
95 // Nack the first packet 3 times in a single StretchAck. | |
96 unacked_packets_.NackPacket(1, 3); | |
97 unacked_packets_.RemoveFromInFlight(2); | |
98 unacked_packets_.RemoveFromInFlight(3); | |
99 unacked_packets_.RemoveFromInFlight(4); | |
100 QuicPacketSequenceNumber lost[] = { 1 }; | |
101 VerifyLosses(4, lost, arraysize(lost)); | |
102 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | |
103 } | |
104 | |
105 // Ack a packet 3 packets ahead, causing a retransmit. | |
106 TEST_F(TcpLossAlgorithmTest, NackRetransmit1PacketSingleAck) { | |
107 const size_t kNumSentPackets = 10; | |
108 // Transmit 10 packets. | |
109 for (size_t i = 1; i <= kNumSentPackets; ++i) { | |
110 SendDataPacket(i); | |
111 } | |
112 | |
113 // Nack the first packet 3 times in an AckFrame with three missing packets. | |
114 unacked_packets_.NackPacket(1, 3); | |
115 unacked_packets_.NackPacket(2, 2); | |
116 unacked_packets_.NackPacket(3, 1); | |
117 unacked_packets_.RemoveFromInFlight(4); | |
118 QuicPacketSequenceNumber lost[] = { 1 }; | |
119 VerifyLosses(4, lost, arraysize(lost)); | |
120 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | |
121 } | |
122 | |
123 TEST_F(TcpLossAlgorithmTest, EarlyRetransmit1Packet) { | |
124 const size_t kNumSentPackets = 2; | |
125 // Transmit 2 packets. | |
126 for (size_t i = 1; i <= kNumSentPackets; ++i) { | |
127 SendDataPacket(i); | |
128 } | |
129 // Early retransmit when the final packet gets acked and the first is nacked. | |
130 unacked_packets_.RemoveFromInFlight(2); | |
131 unacked_packets_.NackPacket(1, 1); | |
132 VerifyLosses(2, nullptr, 0); | |
133 EXPECT_EQ(clock_.Now().Add(rtt_stats_.smoothed_rtt().Multiply(1.25)), | |
134 loss_algorithm_.GetLossTimeout()); | |
135 | |
136 clock_.AdvanceTime(rtt_stats_.latest_rtt().Multiply(1.25)); | |
137 QuicPacketSequenceNumber lost[] = { 1 }; | |
138 VerifyLosses(2, lost, arraysize(lost)); | |
139 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | |
140 } | |
141 | |
142 TEST_F(TcpLossAlgorithmTest, EarlyRetransmitAllPackets) { | |
143 const size_t kNumSentPackets = 5; | |
144 for (size_t i = 1; i <= kNumSentPackets; ++i) { | |
145 SendDataPacket(i); | |
146 // Advance the time 1/4 RTT between 3 and 4. | |
147 if (i == 3) { | |
148 clock_.AdvanceTime(rtt_stats_.smoothed_rtt().Multiply(0.25)); | |
149 } | |
150 } | |
151 | |
152 // Early retransmit when the final packet gets acked and 1.25 RTTs have | |
153 // elapsed since the packets were sent. | |
154 unacked_packets_.RemoveFromInFlight(kNumSentPackets); | |
155 // This simulates a single ack following multiple missing packets with FACK. | |
156 for (size_t i = 1; i < kNumSentPackets; ++i) { | |
157 unacked_packets_.NackPacket(i, kNumSentPackets - i); | |
158 } | |
159 QuicPacketSequenceNumber lost[] = { 1, 2 }; | |
160 VerifyLosses(kNumSentPackets, lost, arraysize(lost)); | |
161 // The time has already advanced 1/4 an RTT, so ensure the timeout is set | |
162 // 1.25 RTTs after the earliest pending packet(3), not the last(4). | |
163 EXPECT_EQ(clock_.Now().Add(rtt_stats_.smoothed_rtt()), | |
164 loss_algorithm_.GetLossTimeout()); | |
165 | |
166 clock_.AdvanceTime(rtt_stats_.smoothed_rtt()); | |
167 QuicPacketSequenceNumber lost2[] = { 1, 2, 3 }; | |
168 VerifyLosses(kNumSentPackets, lost2, arraysize(lost2)); | |
169 EXPECT_EQ(clock_.Now().Add(rtt_stats_.smoothed_rtt().Multiply(0.25)), | |
170 loss_algorithm_.GetLossTimeout()); | |
171 clock_.AdvanceTime(rtt_stats_.smoothed_rtt().Multiply(0.25)); | |
172 QuicPacketSequenceNumber lost3[] = { 1, 2, 3, 4 }; | |
173 VerifyLosses(kNumSentPackets, lost3, arraysize(lost3)); | |
174 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | |
175 } | |
176 | |
177 TEST_F(TcpLossAlgorithmTest, DontEarlyRetransmitNeuteredPacket) { | |
178 const size_t kNumSentPackets = 2; | |
179 // Transmit 2 packets. | |
180 for (size_t i = 1; i <= kNumSentPackets; ++i) { | |
181 SendDataPacket(i); | |
182 } | |
183 // Neuter packet 1. | |
184 unacked_packets_.RemoveRetransmittability(1); | |
185 | |
186 // Early retransmit when the final packet gets acked and the first is nacked. | |
187 unacked_packets_.IncreaseLargestObserved(2); | |
188 unacked_packets_.RemoveFromInFlight(2); | |
189 unacked_packets_.NackPacket(1, 1); | |
190 VerifyLosses(2, nullptr, 0); | |
191 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | |
192 } | |
193 | |
194 TEST_F(TcpLossAlgorithmTest, AlwaysLosePacketSent1RTTEarlier) { | |
195 // Transmit 1 packet and then wait an rtt plus 1ms. | |
196 SendDataPacket(1); | |
197 clock_.AdvanceTime( | |
198 rtt_stats_.smoothed_rtt().Add(QuicTime::Delta::FromMilliseconds(1))); | |
199 | |
200 // Transmit 2 packets. | |
201 SendDataPacket(2); | |
202 SendDataPacket(3); | |
203 | |
204 // Wait another RTT and ack 2. | |
205 clock_.AdvanceTime(rtt_stats_.smoothed_rtt()); | |
206 unacked_packets_.IncreaseLargestObserved(2); | |
207 unacked_packets_.RemoveFromInFlight(2); | |
208 unacked_packets_.NackPacket(1, 1); | |
209 QuicPacketSequenceNumber lost[] = {1}; | |
210 VerifyLosses(2, lost, arraysize(lost)); | |
211 } | |
212 | |
213 } // namespace | |
214 } // namespace test | |
215 } // namespace net | |
OLD | NEW |