OLD | NEW |
1 // Copyright 2015 The Chromium Authors. All rights reserved. | 1 // Copyright 2015 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "net/quic/core/congestion_control/general_loss_algorithm.h" | 5 #include "net/quic/core/congestion_control/general_loss_algorithm.h" |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
8 #include <cstdint> | 8 #include <cstdint> |
9 | 9 |
10 #include "base/stl_util.h" | 10 #include "base/stl_util.h" |
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
43 } | 43 } |
44 | 44 |
45 void SendAckPacket(QuicPacketNumber packet_number) { | 45 void SendAckPacket(QuicPacketNumber packet_number) { |
46 SerializedPacket packet(packet_number, PACKET_1BYTE_PACKET_NUMBER, nullptr, | 46 SerializedPacket packet(packet_number, PACKET_1BYTE_PACKET_NUMBER, nullptr, |
47 kDefaultLength, true, false); | 47 kDefaultLength, true, false); |
48 unacked_packets_.AddSentPacket(&packet, 0, NOT_RETRANSMISSION, clock_.Now(), | 48 unacked_packets_.AddSentPacket(&packet, 0, NOT_RETRANSMISSION, clock_.Now(), |
49 false); | 49 false); |
50 } | 50 } |
51 | 51 |
52 void VerifyLosses(QuicPacketNumber largest_newly_acked, | 52 void VerifyLosses(QuicPacketNumber largest_newly_acked, |
53 QuicPacketNumber* losses_expected, | 53 const std::vector<QuicPacketNumber>& losses_expected) { |
54 size_t num_losses) { | |
55 if (largest_newly_acked > unacked_packets_.largest_observed()) { | 54 if (largest_newly_acked > unacked_packets_.largest_observed()) { |
56 unacked_packets_.IncreaseLargestObserved(largest_newly_acked); | 55 unacked_packets_.IncreaseLargestObserved(largest_newly_acked); |
57 } | 56 } |
58 SendAlgorithmInterface::CongestionVector lost_packets; | 57 SendAlgorithmInterface::CongestionVector lost_packets; |
59 loss_algorithm_.DetectLosses(unacked_packets_, clock_.Now(), rtt_stats_, | 58 loss_algorithm_.DetectLosses(unacked_packets_, clock_.Now(), rtt_stats_, |
60 largest_newly_acked, &lost_packets); | 59 largest_newly_acked, &lost_packets); |
61 EXPECT_EQ(num_losses, lost_packets.size()); | 60 ASSERT_EQ(losses_expected.size(), lost_packets.size()); |
62 for (size_t i = 0; i < num_losses; ++i) { | 61 for (size_t i = 0; i < losses_expected.size(); ++i) { |
63 EXPECT_EQ(lost_packets[i].first, losses_expected[i]); | 62 EXPECT_EQ(lost_packets[i].first, losses_expected[i]); |
64 } | 63 } |
65 } | 64 } |
66 | 65 |
67 QuicFlagSaver flags_; // Save/restore all QUIC flag values. | 66 QuicFlagSaver flags_; // Save/restore all QUIC flag values. |
68 QuicUnackedPacketMap unacked_packets_; | 67 QuicUnackedPacketMap unacked_packets_; |
69 GeneralLossAlgorithm loss_algorithm_; | 68 GeneralLossAlgorithm loss_algorithm_; |
70 RttStats rtt_stats_; | 69 RttStats rtt_stats_; |
71 MockClock clock_; | 70 MockClock clock_; |
72 }; | 71 }; |
73 | 72 |
74 TEST_F(GeneralLossAlgorithmTest, NackRetransmit1Packet) { | 73 TEST_F(GeneralLossAlgorithmTest, NackRetransmit1Packet) { |
75 const size_t kNumSentPackets = 5; | 74 const size_t kNumSentPackets = 5; |
76 // Transmit 5 packets. | 75 // Transmit 5 packets. |
77 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 76 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
78 SendDataPacket(i); | 77 SendDataPacket(i); |
79 } | 78 } |
80 // No loss on one ack. | 79 // No loss on one ack. |
81 unacked_packets_.RemoveFromInFlight(2); | 80 unacked_packets_.RemoveFromInFlight(2); |
82 VerifyLosses(2, nullptr, 0); | 81 VerifyLosses(2, std::vector<QuicPacketNumber>{}); |
83 // No loss on two acks. | 82 // No loss on two acks. |
84 unacked_packets_.RemoveFromInFlight(3); | 83 unacked_packets_.RemoveFromInFlight(3); |
85 VerifyLosses(3, nullptr, 0); | 84 VerifyLosses(3, std::vector<QuicPacketNumber>{}); |
86 // Loss on three acks. | 85 // Loss on three acks. |
87 unacked_packets_.RemoveFromInFlight(4); | 86 unacked_packets_.RemoveFromInFlight(4); |
88 QuicPacketNumber lost[] = {1}; | 87 VerifyLosses(4, {1}); |
89 VerifyLosses(4, lost, arraysize(lost)); | |
90 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 88 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
91 } | 89 } |
92 | 90 |
93 // A stretch ack is an ack that covers more than 1 packet of previously | 91 // A stretch ack is an ack that covers more than 1 packet of previously |
94 // unacknowledged data. | 92 // unacknowledged data. |
95 TEST_F(GeneralLossAlgorithmTest, NackRetransmit1PacketWith1StretchAck) { | 93 TEST_F(GeneralLossAlgorithmTest, NackRetransmit1PacketWith1StretchAck) { |
96 const size_t kNumSentPackets = 10; | 94 const size_t kNumSentPackets = 10; |
97 // Transmit 10 packets. | 95 // Transmit 10 packets. |
98 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 96 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
99 SendDataPacket(i); | 97 SendDataPacket(i); |
100 } | 98 } |
101 | 99 |
102 // Nack the first packet 3 times in a single StretchAck. | 100 // Nack the first packet 3 times in a single StretchAck. |
103 unacked_packets_.RemoveFromInFlight(2); | 101 unacked_packets_.RemoveFromInFlight(2); |
104 unacked_packets_.RemoveFromInFlight(3); | 102 unacked_packets_.RemoveFromInFlight(3); |
105 unacked_packets_.RemoveFromInFlight(4); | 103 unacked_packets_.RemoveFromInFlight(4); |
106 QuicPacketNumber lost[] = {1}; | 104 VerifyLosses(4, {1}); |
107 VerifyLosses(4, lost, arraysize(lost)); | |
108 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 105 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
109 } | 106 } |
110 | 107 |
111 // Ack a packet 3 packets ahead, causing a retransmit. | 108 // Ack a packet 3 packets ahead, causing a retransmit. |
112 TEST_F(GeneralLossAlgorithmTest, NackRetransmit1PacketSingleAck) { | 109 TEST_F(GeneralLossAlgorithmTest, NackRetransmit1PacketSingleAck) { |
113 const size_t kNumSentPackets = 10; | 110 const size_t kNumSentPackets = 10; |
114 // Transmit 10 packets. | 111 // Transmit 10 packets. |
115 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 112 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
116 SendDataPacket(i); | 113 SendDataPacket(i); |
117 } | 114 } |
118 | 115 |
119 // Nack the first packet 3 times in an AckFrame with three missing packets. | 116 // Nack the first packet 3 times in an AckFrame with three missing packets. |
120 unacked_packets_.RemoveFromInFlight(4); | 117 unacked_packets_.RemoveFromInFlight(4); |
121 QuicPacketNumber lost[] = {1}; | 118 VerifyLosses(4, {1}); |
122 VerifyLosses(4, lost, arraysize(lost)); | |
123 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 119 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
124 } | 120 } |
125 | 121 |
126 TEST_F(GeneralLossAlgorithmTest, EarlyRetransmit1Packet) { | 122 TEST_F(GeneralLossAlgorithmTest, EarlyRetransmit1Packet) { |
127 const size_t kNumSentPackets = 2; | 123 const size_t kNumSentPackets = 2; |
128 // Transmit 2 packets. | 124 // Transmit 2 packets. |
129 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 125 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
130 SendDataPacket(i); | 126 SendDataPacket(i); |
131 } | 127 } |
132 // Early retransmit when the final packet gets acked and the first is nacked. | 128 // Early retransmit when the final packet gets acked and the first is nacked. |
133 unacked_packets_.RemoveFromInFlight(2); | 129 unacked_packets_.RemoveFromInFlight(2); |
134 VerifyLosses(2, nullptr, 0); | 130 VerifyLosses(2, std::vector<QuicPacketNumber>{}); |
135 EXPECT_EQ(clock_.Now() + 1.25 * rtt_stats_.smoothed_rtt(), | 131 EXPECT_EQ(clock_.Now() + 1.25 * rtt_stats_.smoothed_rtt(), |
136 loss_algorithm_.GetLossTimeout()); | 132 loss_algorithm_.GetLossTimeout()); |
137 | 133 |
138 clock_.AdvanceTime(1.25 * rtt_stats_.latest_rtt()); | 134 clock_.AdvanceTime(1.25 * rtt_stats_.latest_rtt()); |
139 QuicPacketNumber lost[] = {1}; | 135 VerifyLosses(2, {1}); |
140 VerifyLosses(2, lost, arraysize(lost)); | |
141 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 136 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
142 } | 137 } |
143 | 138 |
144 TEST_F(GeneralLossAlgorithmTest, EarlyRetransmitAllPackets) { | 139 TEST_F(GeneralLossAlgorithmTest, EarlyRetransmitAllPackets) { |
145 const size_t kNumSentPackets = 5; | 140 const size_t kNumSentPackets = 5; |
146 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 141 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
147 SendDataPacket(i); | 142 SendDataPacket(i); |
148 // Advance the time 1/4 RTT between 3 and 4. | 143 // Advance the time 1/4 RTT between 3 and 4. |
149 if (i == 3) { | 144 if (i == 3) { |
150 clock_.AdvanceTime(0.25 * rtt_stats_.smoothed_rtt()); | 145 clock_.AdvanceTime(0.25 * rtt_stats_.smoothed_rtt()); |
151 } | 146 } |
152 } | 147 } |
153 | 148 |
154 // Early retransmit when the final packet gets acked and 1.25 RTTs have | 149 // Early retransmit when the final packet gets acked and 1.25 RTTs have |
155 // elapsed since the packets were sent. | 150 // elapsed since the packets were sent. |
156 unacked_packets_.RemoveFromInFlight(kNumSentPackets); | 151 unacked_packets_.RemoveFromInFlight(kNumSentPackets); |
157 // This simulates a single ack following multiple missing packets with FACK. | 152 // This simulates a single ack following multiple missing packets with FACK. |
158 QuicPacketNumber lost[] = {1, 2}; | 153 VerifyLosses(kNumSentPackets, {1, 2}); |
159 VerifyLosses(kNumSentPackets, lost, arraysize(lost)); | |
160 // The time has already advanced 1/4 an RTT, so ensure the timeout is set | 154 // The time has already advanced 1/4 an RTT, so ensure the timeout is set |
161 // 1.25 RTTs after the earliest pending packet(3), not the last(4). | 155 // 1.25 RTTs after the earliest pending packet(3), not the last(4). |
162 EXPECT_EQ(clock_.Now() + rtt_stats_.smoothed_rtt(), | 156 EXPECT_EQ(clock_.Now() + rtt_stats_.smoothed_rtt(), |
163 loss_algorithm_.GetLossTimeout()); | 157 loss_algorithm_.GetLossTimeout()); |
164 | 158 |
165 clock_.AdvanceTime(rtt_stats_.smoothed_rtt()); | 159 clock_.AdvanceTime(rtt_stats_.smoothed_rtt()); |
166 QuicPacketNumber lost2[] = {1, 2, 3}; | 160 VerifyLosses(kNumSentPackets, {1, 2, 3}); |
167 VerifyLosses(kNumSentPackets, lost2, arraysize(lost2)); | |
168 EXPECT_EQ(clock_.Now() + 0.25 * rtt_stats_.smoothed_rtt(), | 161 EXPECT_EQ(clock_.Now() + 0.25 * rtt_stats_.smoothed_rtt(), |
169 loss_algorithm_.GetLossTimeout()); | 162 loss_algorithm_.GetLossTimeout()); |
170 clock_.AdvanceTime(0.25 * rtt_stats_.smoothed_rtt()); | 163 clock_.AdvanceTime(0.25 * rtt_stats_.smoothed_rtt()); |
171 QuicPacketNumber lost3[] = {1, 2, 3, 4}; | 164 VerifyLosses(kNumSentPackets, {1, 2, 3, 4}); |
172 VerifyLosses(kNumSentPackets, lost3, arraysize(lost3)); | |
173 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 165 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
174 } | 166 } |
175 | 167 |
176 TEST_F(GeneralLossAlgorithmTest, DontEarlyRetransmitNeuteredPacket) { | 168 TEST_F(GeneralLossAlgorithmTest, DontEarlyRetransmitNeuteredPacket) { |
177 const size_t kNumSentPackets = 2; | 169 const size_t kNumSentPackets = 2; |
178 // Transmit 2 packets. | 170 // Transmit 2 packets. |
179 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 171 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
180 SendDataPacket(i); | 172 SendDataPacket(i); |
181 } | 173 } |
182 // Neuter packet 1. | 174 // Neuter packet 1. |
183 unacked_packets_.RemoveRetransmittability(1); | 175 unacked_packets_.RemoveRetransmittability(1); |
184 | 176 |
185 // Early retransmit when the final packet gets acked and the first is nacked. | 177 // Early retransmit when the final packet gets acked and the first is nacked. |
186 unacked_packets_.IncreaseLargestObserved(2); | 178 unacked_packets_.IncreaseLargestObserved(2); |
187 unacked_packets_.RemoveFromInFlight(2); | 179 unacked_packets_.RemoveFromInFlight(2); |
188 VerifyLosses(2, nullptr, 0); | 180 VerifyLosses(2, std::vector<QuicPacketNumber>{}); |
189 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 181 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
190 } | 182 } |
191 | 183 |
192 TEST_F(GeneralLossAlgorithmTest, EarlyRetransmitWithLargerUnackablePackets) { | 184 TEST_F(GeneralLossAlgorithmTest, EarlyRetransmitWithLargerUnackablePackets) { |
193 // Transmit 2 data packets and one ack. | 185 // Transmit 2 data packets and one ack. |
194 SendDataPacket(1); | 186 SendDataPacket(1); |
195 SendDataPacket(2); | 187 SendDataPacket(2); |
196 SendAckPacket(3); | 188 SendAckPacket(3); |
197 clock_.AdvanceTime(rtt_stats_.smoothed_rtt()); | 189 clock_.AdvanceTime(rtt_stats_.smoothed_rtt()); |
198 | 190 |
199 // Early retransmit when the final packet gets acked and the first is nacked. | 191 // Early retransmit when the final packet gets acked and the first is nacked. |
200 unacked_packets_.IncreaseLargestObserved(2); | 192 unacked_packets_.IncreaseLargestObserved(2); |
201 unacked_packets_.RemoveFromInFlight(2); | 193 unacked_packets_.RemoveFromInFlight(2); |
202 VerifyLosses(2, nullptr, 0); | 194 VerifyLosses(2, std::vector<QuicPacketNumber>{}); |
203 EXPECT_EQ(clock_.Now() + 0.25 * rtt_stats_.smoothed_rtt(), | 195 EXPECT_EQ(clock_.Now() + 0.25 * rtt_stats_.smoothed_rtt(), |
204 loss_algorithm_.GetLossTimeout()); | 196 loss_algorithm_.GetLossTimeout()); |
205 | 197 |
206 // The packet should be lost once the loss timeout is reached. | 198 // The packet should be lost once the loss timeout is reached. |
207 clock_.AdvanceTime(0.25 * rtt_stats_.latest_rtt()); | 199 clock_.AdvanceTime(0.25 * rtt_stats_.latest_rtt()); |
208 QuicPacketNumber lost[] = {1}; | 200 VerifyLosses(2, {1}); |
209 VerifyLosses(2, lost, arraysize(lost)); | |
210 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 201 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
211 } | 202 } |
212 | 203 |
213 TEST_F(GeneralLossAlgorithmTest, AlwaysLosePacketSent1RTTEarlier) { | 204 TEST_F(GeneralLossAlgorithmTest, AlwaysLosePacketSent1RTTEarlier) { |
214 // Transmit 1 packet and then wait an rtt plus 1ms. | 205 // Transmit 1 packet and then wait an rtt plus 1ms. |
215 SendDataPacket(1); | 206 SendDataPacket(1); |
216 clock_.AdvanceTime(rtt_stats_.smoothed_rtt() + | 207 clock_.AdvanceTime(rtt_stats_.smoothed_rtt() + |
217 QuicTime::Delta::FromMilliseconds(1)); | 208 QuicTime::Delta::FromMilliseconds(1)); |
218 | 209 |
219 // Transmit 2 packets. | 210 // Transmit 2 packets. |
220 SendDataPacket(2); | 211 SendDataPacket(2); |
221 SendDataPacket(3); | 212 SendDataPacket(3); |
222 | 213 |
223 // Wait another RTT and ack 2. | 214 // Wait another RTT and ack 2. |
224 clock_.AdvanceTime(rtt_stats_.smoothed_rtt()); | 215 clock_.AdvanceTime(rtt_stats_.smoothed_rtt()); |
225 unacked_packets_.IncreaseLargestObserved(2); | 216 unacked_packets_.IncreaseLargestObserved(2); |
226 unacked_packets_.RemoveFromInFlight(2); | 217 unacked_packets_.RemoveFromInFlight(2); |
227 QuicPacketNumber lost[] = {1}; | 218 VerifyLosses(2, {1}); |
228 VerifyLosses(2, lost, arraysize(lost)); | |
229 } | 219 } |
230 | 220 |
231 // NoFack loss detection tests. | 221 // NoFack loss detection tests. |
232 TEST_F(GeneralLossAlgorithmTest, LazyFackNackRetransmit1Packet) { | 222 TEST_F(GeneralLossAlgorithmTest, LazyFackNackRetransmit1Packet) { |
233 loss_algorithm_.SetLossDetectionType(kLazyFack); | 223 loss_algorithm_.SetLossDetectionType(kLazyFack); |
234 const size_t kNumSentPackets = 5; | 224 const size_t kNumSentPackets = 5; |
235 // Transmit 5 packets. | 225 // Transmit 5 packets. |
236 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 226 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
237 SendDataPacket(i); | 227 SendDataPacket(i); |
238 } | 228 } |
239 // No loss on one ack. | 229 // No loss on one ack. |
240 unacked_packets_.RemoveFromInFlight(2); | 230 unacked_packets_.RemoveFromInFlight(2); |
241 VerifyLosses(2, nullptr, 0); | 231 VerifyLosses(2, std::vector<QuicPacketNumber>{}); |
242 // No loss on two acks. | 232 // No loss on two acks. |
243 unacked_packets_.RemoveFromInFlight(3); | 233 unacked_packets_.RemoveFromInFlight(3); |
244 VerifyLosses(3, nullptr, 0); | 234 VerifyLosses(3, std::vector<QuicPacketNumber>{}); |
245 // Loss on three acks. | 235 // Loss on three acks. |
246 unacked_packets_.RemoveFromInFlight(4); | 236 unacked_packets_.RemoveFromInFlight(4); |
247 QuicPacketNumber lost[] = {1}; | 237 VerifyLosses(4, {1}); |
248 VerifyLosses(4, lost, arraysize(lost)); | |
249 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 238 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
250 } | 239 } |
251 | 240 |
252 // A stretch ack is an ack that covers more than 1 packet of previously | 241 // A stretch ack is an ack that covers more than 1 packet of previously |
253 // unacknowledged data. | 242 // unacknowledged data. |
254 TEST_F(GeneralLossAlgorithmTest, | 243 TEST_F(GeneralLossAlgorithmTest, |
255 LazyFackNoNackRetransmit1PacketWith1StretchAck) { | 244 LazyFackNoNackRetransmit1PacketWith1StretchAck) { |
256 loss_algorithm_.SetLossDetectionType(kLazyFack); | 245 loss_algorithm_.SetLossDetectionType(kLazyFack); |
257 const size_t kNumSentPackets = 10; | 246 const size_t kNumSentPackets = 10; |
258 // Transmit 10 packets. | 247 // Transmit 10 packets. |
259 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 248 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
260 SendDataPacket(i); | 249 SendDataPacket(i); |
261 } | 250 } |
262 | 251 |
263 // Nack the first packet 3 times in a single StretchAck. | 252 // Nack the first packet 3 times in a single StretchAck. |
264 unacked_packets_.RemoveFromInFlight(2); | 253 unacked_packets_.RemoveFromInFlight(2); |
265 unacked_packets_.RemoveFromInFlight(3); | 254 unacked_packets_.RemoveFromInFlight(3); |
266 unacked_packets_.RemoveFromInFlight(4); | 255 unacked_packets_.RemoveFromInFlight(4); |
267 VerifyLosses(4, nullptr, 0); | 256 VerifyLosses(4, std::vector<QuicPacketNumber>{}); |
268 // The timer isn't set because we expect more acks. | 257 // The timer isn't set because we expect more acks. |
269 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 258 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
270 // Process another ack and then packet 1 will be lost. | 259 // Process another ack and then packet 1 will be lost. |
271 unacked_packets_.RemoveFromInFlight(5); | 260 unacked_packets_.RemoveFromInFlight(5); |
272 QuicPacketNumber lost[] = {1}; | 261 VerifyLosses(5, {1}); |
273 VerifyLosses(5, lost, arraysize(lost)); | |
274 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 262 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
275 } | 263 } |
276 | 264 |
277 // Ack a packet 3 packets ahead does not cause a retransmit. | 265 // Ack a packet 3 packets ahead does not cause a retransmit. |
278 TEST_F(GeneralLossAlgorithmTest, LazyFackNackRetransmit1PacketSingleAck) { | 266 TEST_F(GeneralLossAlgorithmTest, LazyFackNackRetransmit1PacketSingleAck) { |
279 loss_algorithm_.SetLossDetectionType(kLazyFack); | 267 loss_algorithm_.SetLossDetectionType(kLazyFack); |
280 const size_t kNumSentPackets = 10; | 268 const size_t kNumSentPackets = 10; |
281 // Transmit 10 packets. | 269 // Transmit 10 packets. |
282 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 270 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
283 SendDataPacket(i); | 271 SendDataPacket(i); |
284 } | 272 } |
285 | 273 |
286 // Nack the first packet 3 times in an AckFrame with three missing packets. | 274 // Nack the first packet 3 times in an AckFrame with three missing packets. |
287 unacked_packets_.RemoveFromInFlight(4); | 275 unacked_packets_.RemoveFromInFlight(4); |
288 VerifyLosses(4, nullptr, 0); | 276 VerifyLosses(4, std::vector<QuicPacketNumber>{}); |
289 // The timer isn't set because we expect more acks. | 277 // The timer isn't set because we expect more acks. |
290 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 278 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
291 // Process another ack and then packet 1 and 2 will be lost. | 279 // Process another ack and then packet 1 and 2 will be lost. |
292 unacked_packets_.RemoveFromInFlight(5); | 280 unacked_packets_.RemoveFromInFlight(5); |
293 QuicPacketNumber lost[] = {1, 2}; | 281 VerifyLosses(5, {1, 2}); |
294 VerifyLosses(5, lost, arraysize(lost)); | |
295 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 282 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
296 } | 283 } |
297 | 284 |
298 // Time-based loss detection tests. | 285 // Time-based loss detection tests. |
299 TEST_F(GeneralLossAlgorithmTest, NoLossFor500Nacks) { | 286 TEST_F(GeneralLossAlgorithmTest, NoLossFor500Nacks) { |
300 loss_algorithm_.SetLossDetectionType(kTime); | 287 loss_algorithm_.SetLossDetectionType(kTime); |
301 const size_t kNumSentPackets = 5; | 288 const size_t kNumSentPackets = 5; |
302 // Transmit 5 packets. | 289 // Transmit 5 packets. |
303 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 290 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
304 SendDataPacket(i); | 291 SendDataPacket(i); |
305 } | 292 } |
306 unacked_packets_.RemoveFromInFlight(2); | 293 unacked_packets_.RemoveFromInFlight(2); |
307 for (size_t i = 1; i < 500; ++i) { | 294 for (size_t i = 1; i < 500; ++i) { |
308 VerifyLosses(2, nullptr, 0); | 295 VerifyLosses(2, std::vector<QuicPacketNumber>{}); |
309 } | 296 } |
310 EXPECT_EQ(1.25 * rtt_stats_.smoothed_rtt(), | 297 EXPECT_EQ(1.25 * rtt_stats_.smoothed_rtt(), |
311 loss_algorithm_.GetLossTimeout() - clock_.Now()); | 298 loss_algorithm_.GetLossTimeout() - clock_.Now()); |
312 } | 299 } |
313 | 300 |
314 TEST_F(GeneralLossAlgorithmTest, NoLossUntilTimeout) { | 301 TEST_F(GeneralLossAlgorithmTest, NoLossUntilTimeout) { |
315 loss_algorithm_.SetLossDetectionType(kTime); | 302 loss_algorithm_.SetLossDetectionType(kTime); |
316 const size_t kNumSentPackets = 10; | 303 const size_t kNumSentPackets = 10; |
317 // Transmit 10 packets at 1/10th an RTT interval. | 304 // Transmit 10 packets at 1/10th an RTT interval. |
318 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 305 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
319 SendDataPacket(i); | 306 SendDataPacket(i); |
320 clock_.AdvanceTime(0.1 * rtt_stats_.smoothed_rtt()); | 307 clock_.AdvanceTime(0.1 * rtt_stats_.smoothed_rtt()); |
321 } | 308 } |
322 // Expect the timer to not be set. | 309 // Expect the timer to not be set. |
323 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 310 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
324 // The packet should not be lost until 1.25 RTTs pass. | 311 // The packet should not be lost until 1.25 RTTs pass. |
325 unacked_packets_.RemoveFromInFlight(2); | 312 unacked_packets_.RemoveFromInFlight(2); |
326 VerifyLosses(2, nullptr, 0); | 313 VerifyLosses(2, std::vector<QuicPacketNumber>{}); |
327 // Expect the timer to be set to 0.25 RTT's in the future. | 314 // Expect the timer to be set to 0.25 RTT's in the future. |
328 EXPECT_EQ(0.25 * rtt_stats_.smoothed_rtt(), | 315 EXPECT_EQ(0.25 * rtt_stats_.smoothed_rtt(), |
329 loss_algorithm_.GetLossTimeout() - clock_.Now()); | 316 loss_algorithm_.GetLossTimeout() - clock_.Now()); |
330 VerifyLosses(2, nullptr, 0); | 317 VerifyLosses(2, std::vector<QuicPacketNumber>{}); |
331 clock_.AdvanceTime(0.25 * rtt_stats_.smoothed_rtt()); | 318 clock_.AdvanceTime(0.25 * rtt_stats_.smoothed_rtt()); |
332 QuicPacketNumber lost[] = {1}; | 319 VerifyLosses(2, {1}); |
333 VerifyLosses(2, lost, arraysize(lost)); | |
334 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 320 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
335 } | 321 } |
336 | 322 |
337 TEST_F(GeneralLossAlgorithmTest, NoLossWithoutNack) { | 323 TEST_F(GeneralLossAlgorithmTest, NoLossWithoutNack) { |
338 loss_algorithm_.SetLossDetectionType(kTime); | 324 loss_algorithm_.SetLossDetectionType(kTime); |
339 const size_t kNumSentPackets = 10; | 325 const size_t kNumSentPackets = 10; |
340 // Transmit 10 packets at 1/10th an RTT interval. | 326 // Transmit 10 packets at 1/10th an RTT interval. |
341 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 327 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
342 SendDataPacket(i); | 328 SendDataPacket(i); |
343 clock_.AdvanceTime(0.1 * rtt_stats_.smoothed_rtt()); | 329 clock_.AdvanceTime(0.1 * rtt_stats_.smoothed_rtt()); |
344 } | 330 } |
345 // Expect the timer to not be set. | 331 // Expect the timer to not be set. |
346 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 332 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
347 // The packet should not be lost without a nack. | 333 // The packet should not be lost without a nack. |
348 unacked_packets_.RemoveFromInFlight(1); | 334 unacked_packets_.RemoveFromInFlight(1); |
349 VerifyLosses(1, nullptr, 0); | 335 VerifyLosses(1, std::vector<QuicPacketNumber>{}); |
350 // The timer should still not be set. | 336 // The timer should still not be set. |
351 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 337 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
352 clock_.AdvanceTime(0.25 * rtt_stats_.smoothed_rtt()); | 338 clock_.AdvanceTime(0.25 * rtt_stats_.smoothed_rtt()); |
353 VerifyLosses(1, nullptr, 0); | 339 VerifyLosses(1, std::vector<QuicPacketNumber>{}); |
354 clock_.AdvanceTime(rtt_stats_.smoothed_rtt()); | 340 clock_.AdvanceTime(rtt_stats_.smoothed_rtt()); |
355 VerifyLosses(1, nullptr, 0); | 341 VerifyLosses(1, std::vector<QuicPacketNumber>{}); |
356 | 342 |
357 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 343 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
358 } | 344 } |
359 | 345 |
360 TEST_F(GeneralLossAlgorithmTest, MultipleLossesAtOnce) { | 346 TEST_F(GeneralLossAlgorithmTest, MultipleLossesAtOnce) { |
361 loss_algorithm_.SetLossDetectionType(kTime); | 347 loss_algorithm_.SetLossDetectionType(kTime); |
362 const size_t kNumSentPackets = 10; | 348 const size_t kNumSentPackets = 10; |
363 // Transmit 10 packets at once and then go forward an RTT. | 349 // Transmit 10 packets at once and then go forward an RTT. |
364 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 350 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
365 SendDataPacket(i); | 351 SendDataPacket(i); |
366 } | 352 } |
367 clock_.AdvanceTime(rtt_stats_.smoothed_rtt()); | 353 clock_.AdvanceTime(rtt_stats_.smoothed_rtt()); |
368 // Expect the timer to not be set. | 354 // Expect the timer to not be set. |
369 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 355 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
370 // The packet should not be lost until 1.25 RTTs pass. | 356 // The packet should not be lost until 1.25 RTTs pass. |
371 unacked_packets_.RemoveFromInFlight(10); | 357 unacked_packets_.RemoveFromInFlight(10); |
372 VerifyLosses(10, nullptr, 0); | 358 VerifyLosses(10, std::vector<QuicPacketNumber>{}); |
373 // Expect the timer to be set to 0.25 RTT's in the future. | 359 // Expect the timer to be set to 0.25 RTT's in the future. |
374 EXPECT_EQ(0.25 * rtt_stats_.smoothed_rtt(), | 360 EXPECT_EQ(0.25 * rtt_stats_.smoothed_rtt(), |
375 loss_algorithm_.GetLossTimeout() - clock_.Now()); | 361 loss_algorithm_.GetLossTimeout() - clock_.Now()); |
376 clock_.AdvanceTime(0.25 * rtt_stats_.smoothed_rtt()); | 362 clock_.AdvanceTime(0.25 * rtt_stats_.smoothed_rtt()); |
377 QuicPacketNumber lost[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; | 363 VerifyLosses(10, {1, 2, 3, 4, 5, 6, 7, 8, 9}); |
378 VerifyLosses(10, lost, arraysize(lost)); | |
379 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 364 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
380 } | 365 } |
381 | 366 |
382 TEST_F(GeneralLossAlgorithmTest, NoSpuriousLossesFromLargeReordering) { | 367 TEST_F(GeneralLossAlgorithmTest, NoSpuriousLossesFromLargeReordering) { |
383 loss_algorithm_.SetLossDetectionType(kTime); | 368 loss_algorithm_.SetLossDetectionType(kTime); |
384 const size_t kNumSentPackets = 10; | 369 const size_t kNumSentPackets = 10; |
385 // Transmit 10 packets at once and then go forward an RTT. | 370 // Transmit 10 packets at once and then go forward an RTT. |
386 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 371 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
387 SendDataPacket(i); | 372 SendDataPacket(i); |
388 } | 373 } |
389 clock_.AdvanceTime(rtt_stats_.smoothed_rtt()); | 374 clock_.AdvanceTime(rtt_stats_.smoothed_rtt()); |
390 // Expect the timer to not be set. | 375 // Expect the timer to not be set. |
391 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 376 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
392 // The packet should not be lost until 1.25 RTTs pass. | 377 // The packet should not be lost until 1.25 RTTs pass. |
393 | 378 |
394 unacked_packets_.RemoveFromInFlight(10); | 379 unacked_packets_.RemoveFromInFlight(10); |
395 VerifyLosses(10, nullptr, 0); | 380 VerifyLosses(10, std::vector<QuicPacketNumber>{}); |
396 // Expect the timer to be set to 0.25 RTT's in the future. | 381 // Expect the timer to be set to 0.25 RTT's in the future. |
397 EXPECT_EQ(0.25 * rtt_stats_.smoothed_rtt(), | 382 EXPECT_EQ(0.25 * rtt_stats_.smoothed_rtt(), |
398 loss_algorithm_.GetLossTimeout() - clock_.Now()); | 383 loss_algorithm_.GetLossTimeout() - clock_.Now()); |
399 clock_.AdvanceTime(0.25 * rtt_stats_.smoothed_rtt()); | 384 clock_.AdvanceTime(0.25 * rtt_stats_.smoothed_rtt()); |
400 // Now ack packets 1 to 9 and ensure the timer is no longer set and no packets | 385 // Now ack packets 1 to 9 and ensure the timer is no longer set and no packets |
401 // are lost. | 386 // are lost. |
402 for (QuicPacketNumber i = 1; i <= 9; ++i) { | 387 for (QuicPacketNumber i = 1; i <= 9; ++i) { |
403 unacked_packets_.RemoveFromInFlight(i); | 388 unacked_packets_.RemoveFromInFlight(i); |
404 VerifyLosses(i, nullptr, 0); | 389 VerifyLosses(i, std::vector<QuicPacketNumber>{}); |
405 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 390 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
406 } | 391 } |
407 } | 392 } |
408 | 393 |
409 TEST_F(GeneralLossAlgorithmTest, IncreaseThresholdUponSpuriousLoss) { | 394 TEST_F(GeneralLossAlgorithmTest, IncreaseThresholdUponSpuriousLoss) { |
410 loss_algorithm_.SetLossDetectionType(kAdaptiveTime); | 395 loss_algorithm_.SetLossDetectionType(kAdaptiveTime); |
411 EXPECT_EQ(4, loss_algorithm_.reordering_shift()); | 396 EXPECT_EQ(4, loss_algorithm_.reordering_shift()); |
412 const size_t kNumSentPackets = 10; | 397 const size_t kNumSentPackets = 10; |
413 // Transmit 2 packets at 1/10th an RTT interval. | 398 // Transmit 2 packets at 1/10th an RTT interval. |
414 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 399 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
415 SendDataPacket(i); | 400 SendDataPacket(i); |
416 clock_.AdvanceTime(0.1 * rtt_stats_.smoothed_rtt()); | 401 clock_.AdvanceTime(0.1 * rtt_stats_.smoothed_rtt()); |
417 } | 402 } |
418 EXPECT_EQ(QuicTime::Zero() + rtt_stats_.smoothed_rtt(), clock_.Now()); | 403 EXPECT_EQ(QuicTime::Zero() + rtt_stats_.smoothed_rtt(), clock_.Now()); |
419 | 404 |
420 // Expect the timer to not be set. | 405 // Expect the timer to not be set. |
421 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 406 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
422 // Packet 1 should not be lost until 1/16 RTTs pass. | 407 // Packet 1 should not be lost until 1/16 RTTs pass. |
423 unacked_packets_.RemoveFromInFlight(2); | 408 unacked_packets_.RemoveFromInFlight(2); |
424 VerifyLosses(2, nullptr, 0); | 409 VerifyLosses(2, std::vector<QuicPacketNumber>{}); |
425 // Expect the timer to be set to 1/16 RTT's in the future. | 410 // Expect the timer to be set to 1/16 RTT's in the future. |
426 EXPECT_EQ(rtt_stats_.smoothed_rtt() * (1.0f / 16), | 411 EXPECT_EQ(rtt_stats_.smoothed_rtt() * (1.0f / 16), |
427 loss_algorithm_.GetLossTimeout() - clock_.Now()); | 412 loss_algorithm_.GetLossTimeout() - clock_.Now()); |
428 VerifyLosses(2, nullptr, 0); | 413 VerifyLosses(2, std::vector<QuicPacketNumber>{}); |
429 clock_.AdvanceTime(rtt_stats_.smoothed_rtt() * (1.0f / 16)); | 414 clock_.AdvanceTime(rtt_stats_.smoothed_rtt() * (1.0f / 16)); |
430 QuicPacketNumber lost[] = {1}; | 415 VerifyLosses(2, {1}); |
431 VerifyLosses(2, lost, arraysize(lost)); | |
432 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 416 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
433 // Retransmit packet 1 as 11 and 2 as 12. | 417 // Retransmit packet 1 as 11 and 2 as 12. |
434 SendDataPacket(11); | 418 SendDataPacket(11); |
435 SendDataPacket(12); | 419 SendDataPacket(12); |
436 | 420 |
437 // Advance the time 1/4 RTT and indicate the loss was spurious. | 421 // Advance the time 1/4 RTT and indicate the loss was spurious. |
438 // The new threshold should be 1/2 RTT. | 422 // The new threshold should be 1/2 RTT. |
439 clock_.AdvanceTime(rtt_stats_.smoothed_rtt() * (1.0f / 4)); | 423 clock_.AdvanceTime(rtt_stats_.smoothed_rtt() * (1.0f / 4)); |
| 424 if (FLAGS_quic_reloadable_flag_quic_fix_adaptive_time_loss) { |
| 425 // The flag fixes an issue where adaptive time loss would increase the |
| 426 // reordering threshold by an extra factor of two. |
| 427 clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(1)); |
| 428 } |
440 loss_algorithm_.SpuriousRetransmitDetected(unacked_packets_, clock_.Now(), | 429 loss_algorithm_.SpuriousRetransmitDetected(unacked_packets_, clock_.Now(), |
441 rtt_stats_, 11); | 430 rtt_stats_, 11); |
442 EXPECT_EQ(1, loss_algorithm_.reordering_shift()); | 431 EXPECT_EQ(1, loss_algorithm_.reordering_shift()); |
443 | 432 |
444 // Detect another spurious retransmit and ensure the threshold doesn't | 433 // Detect another spurious retransmit and ensure the threshold doesn't |
445 // increase again. | 434 // increase again. |
446 loss_algorithm_.SpuriousRetransmitDetected(unacked_packets_, clock_.Now(), | 435 loss_algorithm_.SpuriousRetransmitDetected(unacked_packets_, clock_.Now(), |
447 rtt_stats_, 12); | 436 rtt_stats_, 12); |
448 EXPECT_EQ(1, loss_algorithm_.reordering_shift()); | 437 EXPECT_EQ(1, loss_algorithm_.reordering_shift()); |
449 } | 438 } |
450 | 439 |
451 } // namespace | 440 } // namespace |
452 } // namespace test | 441 } // namespace test |
453 } // namespace net | 442 } // namespace net |
OLD | NEW |