1 // Copyright 2013 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 "net/quic/quic_sent_packet_manager.h" 6 7 #include "base/stl_util.h" 8 #include "net/quic/test_tools/quic_sent_packet_manager_peer.h" 9 #include "net/quic/test_tools/quic_test_utils.h" 10 #include "testing/gmock/include/gmock/gmock.h" 11 #include "testing/gtest/include/gtest/gtest.h" 12 13 using std::vector; 14 using testing::_; 15 using testing::Return; 16 using testing::StrictMock; 17 18 namespace net { 19 namespace test { 20 namespace { 21 22 class MockHelper : public QuicSentPacketManager::HelperInterface { 23 public: 24 MOCK_METHOD0(GetNextPacketSequenceNumber, QuicPacketSequenceNumber()); 25 }; 26 27 class QuicSentPacketManagerTest : public ::testing::TestWithParam<bool> { 28 protected: 29 QuicSentPacketManagerTest() 30 : manager_(true, &helper_, &clock_, kFixRate), 31 send_algorithm_(new StrictMock<MockSendAlgorithm>) { 32 QuicSentPacketManagerPeer::SetSendAlgorithm(&manager_, send_algorithm_); 33 } 34 35 ~QuicSentPacketManagerTest() { 36 STLDeleteElements(&packets_); 37 } 38 39 void VerifyUnackedPackets(QuicPacketSequenceNumber* packets, 40 size_t num_packets) { 41 if (num_packets == 0) { 42 EXPECT_FALSE(manager_.HasUnackedPackets()); 43 EXPECT_EQ(0u, manager_.GetNumRetransmittablePackets()); 44 return; 45 } 46 47 EXPECT_TRUE(manager_.HasUnackedPackets()); 48 EXPECT_EQ(packets[0], manager_.GetLeastUnackedSentPacket()); 49 for (size_t i = 0; i < num_packets; ++i) { 50 EXPECT_TRUE(manager_.IsUnacked(packets[i])) << packets[i]; 51 } 52 } 53 54 void VerifyRetransmittablePackets(QuicPacketSequenceNumber* packets, 55 size_t num_packets) { 56 SequenceNumberSet unacked = manager_.GetUnackedPackets(); 57 for (size_t i = 0; i < num_packets; ++i) { 58 EXPECT_TRUE(ContainsKey(unacked, packets[i])) << packets[i]; 59 } 60 size_t num_retransmittable = 0; 61 for (SequenceNumberSet::const_iterator it = unacked.begin(); 62 it != unacked.end(); ++it) { 63 if (manager_.HasRetransmittableFrames(*it)) { 64 ++num_retransmittable; 65 } 66 } 67 EXPECT_EQ(num_packets, manager_.GetNumRetransmittablePackets()); 68 EXPECT_EQ(num_packets, num_retransmittable); 69 } 70 71 void VerifyAckedPackets(QuicPacketSequenceNumber* expected, 72 size_t num_expected, 73 const SequenceNumberSet& actual) { 74 if (num_expected == 0) { 75 EXPECT_TRUE(actual.empty()); 76 return; 77 } 78 79 EXPECT_EQ(num_expected, actual.size()); 80 for (size_t i = 0; i < num_expected; ++i) { 81 EXPECT_TRUE(ContainsKey(actual, expected[i])) << expected[i]; 82 } 83 } 84 85 void RetransmitPacket(QuicPacketSequenceNumber old_sequence_number, 86 QuicPacketSequenceNumber new_sequence_number) { 87 QuicSentPacketManagerPeer::MarkForRetransmission( 88 &manager_, old_sequence_number, NACK_RETRANSMISSION); 89 EXPECT_TRUE(manager_.HasPendingRetransmissions()); 90 QuicSentPacketManager::PendingRetransmission next_retransmission = 91 manager_.NextPendingRetransmission(); 92 EXPECT_EQ(old_sequence_number, next_retransmission.sequence_number); 93 EXPECT_EQ(NACK_RETRANSMISSION, next_retransmission.transmission_type); 94 manager_.OnRetransmittedPacket(old_sequence_number, new_sequence_number); 95 EXPECT_TRUE(QuicSentPacketManagerPeer::IsRetransmission( 96 &manager_, new_sequence_number)); 97 } 98 99 SerializedPacket CreatePacket(QuicPacketSequenceNumber sequence_number) { 100 packets_.push_back(QuicPacket::NewDataPacket( 101 NULL, 0, false, PACKET_8BYTE_GUID, false, 102 PACKET_6BYTE_SEQUENCE_NUMBER)); 103 return SerializedPacket(sequence_number, PACKET_6BYTE_SEQUENCE_NUMBER, 104 packets_.back(), 0u, new RetransmittableFrames()); 105 } 106 107 SerializedPacket CreateFecPacket(QuicPacketSequenceNumber sequence_number) { 108 packets_.push_back(QuicPacket::NewFecPacket( 109 NULL, 0, false, PACKET_8BYTE_GUID, false, 110 PACKET_6BYTE_SEQUENCE_NUMBER)); 111 return SerializedPacket(sequence_number, PACKET_6BYTE_SEQUENCE_NUMBER, 112 packets_.back(), 0u, NULL); 113 } 114 115 void SendDataPacket(QuicPacketSequenceNumber sequence_number) { 116 EXPECT_CALL(*send_algorithm_, OnPacketSent(_, sequence_number, _, _, _)) 117 .Times(1).WillOnce(Return(true)); 118 SerializedPacket packet(CreatePacket(sequence_number)); 119 manager_.OnSerializedPacket(packet); 120 manager_.OnPacketSent(sequence_number, clock_.ApproximateNow(), 121 packet.packet->length(), NOT_RETRANSMISSION, 122 HAS_RETRANSMITTABLE_DATA); 123 } 124 125 // Based on QuicConnection's WritePendingRetransmissions. 126 void RetransmitNextPacket( 127 QuicPacketSequenceNumber retransmission_sequence_number) { 128 EXPECT_TRUE(manager_.HasPendingRetransmissions()); 129 EXPECT_CALL(*send_algorithm_, 130 OnPacketSent(_, retransmission_sequence_number, _, _, _)) 131 .Times(1).WillOnce(Return(true)); 132 const QuicSentPacketManager::PendingRetransmission pending = 133 manager_.NextPendingRetransmission(); 134 manager_.OnRetransmittedPacket( 135 pending.sequence_number, retransmission_sequence_number); 136 manager_.OnPacketSent(retransmission_sequence_number, 137 clock_.ApproximateNow(), 1000, 138 pending.transmission_type, HAS_RETRANSMITTABLE_DATA); 139 } 140 141 testing::StrictMock<MockHelper> helper_; 142 QuicSentPacketManager manager_; 143 vector<QuicPacket*> packets_; 144 MockClock clock_; 145 MockSendAlgorithm* send_algorithm_; 146 }; 147 148 TEST_F(QuicSentPacketManagerTest, IsUnacked) { 149 VerifyUnackedPackets(NULL, 0); 150 151 SerializedPacket serialized_packet(CreatePacket(1)); 152 153 manager_.OnSerializedPacket(serialized_packet); 154 155 QuicPacketSequenceNumber unacked[] = { 1 }; 156 VerifyUnackedPackets(unacked, arraysize(unacked)); 157 QuicPacketSequenceNumber retransmittable[] = { 1 }; 158 VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable)); 159 } 160 161 TEST_F(QuicSentPacketManagerTest, IsUnAckedRetransmit) { 162 SerializedPacket serialized_packet(CreatePacket(1)); 163 164 manager_.OnSerializedPacket(serialized_packet); 165 RetransmitPacket(1, 2); 166 167 EXPECT_TRUE(QuicSentPacketManagerPeer::IsRetransmission(&manager_, 2)); 168 QuicPacketSequenceNumber unacked[] = { 1, 2 }; 169 VerifyUnackedPackets(unacked, arraysize(unacked)); 170 QuicPacketSequenceNumber retransmittable[] = { 2 }; 171 VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable)); 172 } 173 174 TEST_F(QuicSentPacketManagerTest, RetransmitThenAck) { 175 SerializedPacket serialized_packet(CreatePacket(1)); 176 177 manager_.OnSerializedPacket(serialized_packet); 178 RetransmitPacket(1, 2); 179 180 // Ack 2 but not 1. 181 ReceivedPacketInfo received_info; 182 received_info.largest_observed = 2; 183 received_info.missing_packets.insert(1); 184 manager_.OnIncomingAck(received_info, QuicTime::Zero()); 185 186 // No unacked packets remain. 187 VerifyUnackedPackets(NULL, 0); 188 VerifyRetransmittablePackets(NULL, 0); 189 } 190 191 TEST_F(QuicSentPacketManagerTest, RetransmitThenAckBeforeSend) { 192 SerializedPacket serialized_packet(CreatePacket(1)); 193 194 manager_.OnSerializedPacket(serialized_packet); 195 QuicSentPacketManagerPeer::MarkForRetransmission( 196 &manager_, 1, NACK_RETRANSMISSION); 197 EXPECT_TRUE(manager_.HasPendingRetransmissions()); 198 199 // Ack 1. 200 ReceivedPacketInfo received_info; 201 received_info.largest_observed = 1; 202 manager_.OnIncomingAck(received_info, QuicTime::Zero()); 203 204 // There should no longer be a pending retransmission. 205 EXPECT_FALSE(manager_.HasPendingRetransmissions()); 206 207 // No unacked packets remain. 208 VerifyUnackedPackets(NULL, 0); 209 VerifyRetransmittablePackets(NULL, 0); 210 } 211 212 TEST_F(QuicSentPacketManagerTest, RetransmitThenAckPrevious) { 213 SerializedPacket serialized_packet(CreatePacket(1)); 214 215 manager_.OnSerializedPacket(serialized_packet); 216 RetransmitPacket(1, 2); 217 218 // Ack 1 but not 2. 219 ReceivedPacketInfo received_info; 220 received_info.largest_observed = 1; 221 manager_.OnIncomingAck(received_info, QuicTime::Zero()); 222 223 // 2 remains unacked, but no packets have retransmittable data. 224 QuicPacketSequenceNumber unacked[] = { 2 }; 225 VerifyUnackedPackets(unacked, arraysize(unacked)); 226 VerifyRetransmittablePackets(NULL, 0); 227 228 // Verify that if the retransmission alarm does fire to abandon packet 2, 229 // the sent packet manager is not notified, since there is no retransmittable 230 // data outstanding. 231 EXPECT_CALL(*send_algorithm_, RetransmissionDelay()) 232 .WillOnce(Return(QuicTime::Delta::FromMilliseconds(1))); 233 manager_.OnRetransmissionTimeout(); 234 } 235 236 TEST_F(QuicSentPacketManagerTest, RetransmitTwiceThenAckFirst) { 237 SerializedPacket serialized_packet(CreatePacket(1)); 238 239 manager_.OnSerializedPacket(serialized_packet); 240 RetransmitPacket(1, 2); 241 RetransmitPacket(2, 3); 242 243 // Ack 1 but not 2 or 3. 244 ReceivedPacketInfo received_info; 245 received_info.largest_observed = 1; 246 manager_.OnIncomingAck(received_info, QuicTime::Zero()); 247 248 // 3 remains unacked, but no packets have retransmittable data. 249 QuicPacketSequenceNumber unacked[] = { 3 }; 250 VerifyUnackedPackets(unacked, arraysize(unacked)); 251 VerifyRetransmittablePackets(NULL, 0); 252 253 // Verify that if the retransmission alarm does fire to abandon packet 3, 254 // the sent packet manager is not notified, since there is no retransmittable 255 // data outstanding. 256 EXPECT_CALL(*send_algorithm_, RetransmissionDelay()) 257 .WillOnce(Return(QuicTime::Delta::FromMilliseconds(1))); 258 manager_.OnRetransmissionTimeout(); 259 } 260 261 TEST_F(QuicSentPacketManagerTest, TruncatedAck) { 262 SerializedPacket serialized_packet(CreatePacket(1)); 263 264 manager_.OnSerializedPacket(serialized_packet); 265 RetransmitPacket(1, 2); 266 RetransmitPacket(2, 3); 267 RetransmitPacket(3, 4); 268 269 // Truncated ack with 2 NACKs 270 ReceivedPacketInfo received_info; 271 received_info.largest_observed = 2; 272 received_info.missing_packets.insert(1); 273 received_info.missing_packets.insert(2); 274 received_info.is_truncated = true; 275 manager_.OnIncomingAck(received_info, QuicTime::Zero()); 276 277 // High water mark will be raised. 278 QuicPacketSequenceNumber unacked[] = { 2, 3, 4 }; 279 VerifyUnackedPackets(unacked, arraysize(unacked)); 280 QuicPacketSequenceNumber retransmittable[] = { 4 }; 281 VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable)); 282 } 283 284 TEST_F(QuicSentPacketManagerTest, SendDropAckRetransmitManyPackets) { 285 manager_.OnSerializedPacket(CreatePacket(1)); 286 manager_.OnSerializedPacket(CreatePacket(2)); 287 manager_.OnSerializedPacket(CreatePacket(3)); 288 289 { 290 // Ack packets 1 and 3. 291 ReceivedPacketInfo received_info; 292 received_info.largest_observed = 3; 293 received_info.missing_packets.insert(2); 294 manager_.OnIncomingAck(received_info, QuicTime::Zero()); 295 296 QuicPacketSequenceNumber unacked[] = { 2 }; 297 VerifyUnackedPackets(unacked, arraysize(unacked)); 298 QuicPacketSequenceNumber retransmittable[] = { 2 }; 299 VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable)); 300 } 301 302 manager_.OnSerializedPacket(CreatePacket(4)); 303 manager_.OnSerializedPacket(CreatePacket(5)); 304 305 { 306 // Ack packets 5. 307 ReceivedPacketInfo received_info; 308 received_info.largest_observed = 5; 309 received_info.missing_packets.insert(2); 310 received_info.missing_packets.insert(4); 311 manager_.OnIncomingAck(received_info, QuicTime::Zero()); 312 313 QuicPacketSequenceNumber unacked[] = { 2, 4 }; 314 VerifyUnackedPackets(unacked, arraysize(unacked)); 315 QuicPacketSequenceNumber retransmittable[] = { 2, 4 }; 316 VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable)); 317 } 318 319 manager_.OnSerializedPacket(CreatePacket(6)); 320 manager_.OnSerializedPacket(CreatePacket(7)); 321 322 { 323 // Ack packets 7. 324 ReceivedPacketInfo received_info; 325 received_info.largest_observed = 7; 326 received_info.missing_packets.insert(2); 327 received_info.missing_packets.insert(4); 328 received_info.missing_packets.insert(6); 329 manager_.OnIncomingAck(received_info, QuicTime::Zero()); 330 331 QuicPacketSequenceNumber unacked[] = { 2, 4, 6 }; 332 VerifyUnackedPackets(unacked, arraysize(unacked)); 333 QuicPacketSequenceNumber retransmittable[] = { 2, 4, 6 }; 334 VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable)); 335 } 336 337 RetransmitPacket(2, 8); 338 manager_.OnSerializedPacket(CreatePacket(9)); 339 manager_.OnSerializedPacket(CreatePacket(10)); 340 341 { 342 // Ack packet 10. 343 ReceivedPacketInfo received_info; 344 received_info.largest_observed = 10; 345 received_info.missing_packets.insert(2); 346 received_info.missing_packets.insert(4); 347 received_info.missing_packets.insert(6); 348 received_info.missing_packets.insert(8); 349 received_info.missing_packets.insert(9); 350 manager_.OnIncomingAck(received_info, QuicTime::Zero()); 351 352 QuicPacketSequenceNumber unacked[] = { 2, 4, 6, 8, 9 }; 353 VerifyUnackedPackets(unacked, arraysize(unacked)); 354 QuicPacketSequenceNumber retransmittable[] = { 4, 6, 8, 9 }; 355 VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable)); 356 } 357 358 359 RetransmitPacket(4, 11); 360 manager_.OnSerializedPacket(CreatePacket(12)); 361 manager_.OnSerializedPacket(CreatePacket(13)); 362 363 { 364 // Ack packet 13. 365 ReceivedPacketInfo received_info; 366 received_info.largest_observed = 13; 367 received_info.missing_packets.insert(2); 368 received_info.missing_packets.insert(4); 369 received_info.missing_packets.insert(6); 370 received_info.missing_packets.insert(8); 371 received_info.missing_packets.insert(9); 372 received_info.missing_packets.insert(11); 373 received_info.missing_packets.insert(12); 374 manager_.OnIncomingAck(received_info, QuicTime::Zero()); 375 376 QuicPacketSequenceNumber unacked[] = { 2, 4, 6, 8, 9, 11, 12 }; 377 VerifyUnackedPackets(unacked, arraysize(unacked)); 378 QuicPacketSequenceNumber retransmittable[] = { 6, 8, 9, 11, 12 }; 379 VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable)); 380 } 381 382 RetransmitPacket(6, 14); 383 manager_.OnSerializedPacket(CreatePacket(15)); 384 manager_.OnSerializedPacket(CreatePacket(16)); 385 386 { 387 // Ack packet 16. 388 ReceivedPacketInfo received_info; 389 received_info.largest_observed = 13; 390 received_info.missing_packets.insert(2); 391 received_info.missing_packets.insert(4); 392 received_info.missing_packets.insert(6); 393 received_info.missing_packets.insert(8); 394 received_info.missing_packets.insert(9); 395 received_info.missing_packets.insert(11); 396 received_info.missing_packets.insert(12); 397 received_info.is_truncated = true; 398 manager_.OnIncomingAck(received_info, QuicTime::Zero()); 399 400 // Truncated ack raises the high water mark by clearing out 2, 4, and 6. 401 QuicPacketSequenceNumber unacked[] = { 8, 9, 11, 12, 14, 15, 16 }; 402 VerifyUnackedPackets(unacked, arraysize(unacked)); 403 QuicPacketSequenceNumber retransmittable[] = { 8, 9, 11, 12, 14, 15, 16 }; 404 VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable)); 405 } 406 } 407 408 TEST_F(QuicSentPacketManagerTest, GetLeastUnackedSentPacket) { 409 EXPECT_CALL(helper_, GetNextPacketSequenceNumber()).WillOnce(Return(1u)); 410 EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket()); 411 } 412 413 TEST_F(QuicSentPacketManagerTest, GetLeastUnackedSentPacketUnacked) { 414 SerializedPacket serialized_packet(CreatePacket(1)); 415 416 manager_.OnSerializedPacket(serialized_packet); 417 EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket()); 418 } 419 420 TEST_F(QuicSentPacketManagerTest, GetLeastUnackedSentPacketUnackedFec) { 421 SerializedPacket serialized_packet(CreateFecPacket(1)); 422 423 manager_.OnSerializedPacket(serialized_packet); 424 EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket()); 425 } 426 427 TEST_F(QuicSentPacketManagerTest, GetLeastUnackedSentPacketDiscardUnacked) { 428 SerializedPacket serialized_packet(CreatePacket(1)); 429 430 manager_.OnSerializedPacket(serialized_packet); 431 manager_.DiscardUnackedPacket(1u); 432 EXPECT_CALL(helper_, GetNextPacketSequenceNumber()).WillOnce(Return(2u)); 433 EXPECT_EQ(2u, manager_.GetLeastUnackedSentPacket()); 434 } 435 436 TEST_F(QuicSentPacketManagerTest, GetLeastUnackedPacketAndDiscard) { 437 VerifyUnackedPackets(NULL, 0); 438 439 SerializedPacket serialized_packet(CreateFecPacket(1)); 440 manager_.OnSerializedPacket(serialized_packet); 441 EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket()); 442 443 SerializedPacket serialized_packet2(CreateFecPacket(2)); 444 manager_.OnSerializedPacket(serialized_packet2); 445 EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket()); 446 447 SerializedPacket serialized_packet3(CreateFecPacket(3)); 448 manager_.OnSerializedPacket(serialized_packet3); 449 EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket()); 450 451 QuicPacketSequenceNumber unacked[] = { 1, 2, 3 }; 452 VerifyUnackedPackets(unacked, arraysize(unacked)); 453 VerifyRetransmittablePackets(NULL, 0); 454 455 manager_.DiscardUnackedPacket(1); 456 EXPECT_EQ(2u, manager_.GetLeastUnackedSentPacket()); 457 458 // Ack 2. 459 ReceivedPacketInfo received_info; 460 received_info.largest_observed = 2; 461 manager_.OnIncomingAck(received_info, QuicTime::Zero()); 462 463 EXPECT_EQ(3u, manager_.GetLeastUnackedSentPacket()); 464 465 // Discard the 3rd packet and ensure there are no FEC packets. 466 manager_.DiscardUnackedPacket(3); 467 EXPECT_FALSE(manager_.HasUnackedPackets()); 468 } 469 470 TEST_F(QuicSentPacketManagerTest, GetSentTime) { 471 VerifyUnackedPackets(NULL, 0); 472 473 SerializedPacket serialized_packet(CreateFecPacket(1)); 474 manager_.OnSerializedPacket(serialized_packet); 475 EXPECT_CALL(*send_algorithm_, OnPacketSent(_, 1, _, _, _)) 476 .Times(1).WillOnce(Return(true)); 477 manager_.OnPacketSent( 478 1, QuicTime::Zero(), 0, NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA); 479 SerializedPacket serialized_packet2(CreateFecPacket(2)); 480 QuicTime sent_time = QuicTime::Zero().Add(QuicTime::Delta::FromSeconds(1)); 481 manager_.OnSerializedPacket(serialized_packet2); 482 EXPECT_CALL(*send_algorithm_, OnPacketSent(_, 2, _, _, _)) 483 .Times(1).WillOnce(Return(true)); 484 manager_.OnPacketSent( 485 2, sent_time, 0, NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA); 486 487 QuicPacketSequenceNumber unacked[] = { 1, 2 }; 488 VerifyUnackedPackets(unacked, arraysize(unacked)); 489 VerifyRetransmittablePackets(NULL, 0); 490 491 EXPECT_TRUE(manager_.HasUnackedPackets()); 492 EXPECT_EQ(QuicTime::Zero(), 493 QuicSentPacketManagerPeer::GetSentTime(&manager_, 1)); 494 EXPECT_EQ(sent_time, QuicSentPacketManagerPeer::GetSentTime(&manager_, 2)); 495 } 496 497 TEST_F(QuicSentPacketManagerTest, NackRetransmit1Packet) { 498 const size_t kNumSentPackets = 4; 499 // Transmit 4 packets. 500 for (size_t i = 1; i <= kNumSentPackets; ++i) { 501 EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, _, _, _)) 502 .Times(1).WillOnce(Return(true)); 503 manager_.OnPacketSent(i, clock_.Now(), 1000, 504 NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA); 505 } 506 507 // Nack the first packet 3 times with increasing largest observed. 508 ReceivedPacketInfo received_info; 509 received_info.delta_time_largest_observed = 510 QuicTime::Delta::FromMilliseconds(5); 511 received_info.missing_packets.insert(1); 512 for (QuicPacketSequenceNumber i = 1; i <= 3; ++i) { 513 received_info.largest_observed = i + 1; 514 EXPECT_CALL(*send_algorithm_, OnPacketAcked(i + 1, _, _)).Times(1); 515 if (i == 3) { 516 EXPECT_CALL(*send_algorithm_, OnPacketLost(1, _)).Times(1); 517 EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(1, _)).Times(1); 518 } 519 SequenceNumberSet retransmissions = 520 manager_.OnIncomingAckFrame(received_info, clock_.Now()); 521 EXPECT_EQ(i == 3 ? 1u : 0u, retransmissions.size()); 522 EXPECT_EQ(i, QuicSentPacketManagerPeer::GetNackCount(&manager_, 1)); 523 } 524 } 525 526 // A stretch ack is an ack that covers more than 1 packet of previously 527 // unacknowledged data. 528 TEST_F(QuicSentPacketManagerTest, NackRetransmit1PacketWith1StretchAck) { 529 const size_t kNumSentPackets = 4; 530 // Transmit 4 packets. 531 for (size_t i = 1; i <= kNumSentPackets; ++i) { 532 EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, _, _, _)) 533 .Times(1).WillOnce(Return(true)); 534 manager_.OnPacketSent(i, clock_.Now(), 1000, 535 NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA); 536 } 537 538 // Nack the first packet 3 times in a single StretchAck. 539 ReceivedPacketInfo received_info; 540 received_info.delta_time_largest_observed = 541 QuicTime::Delta::FromMilliseconds(5); 542 received_info.missing_packets.insert(1); 543 received_info.largest_observed = kNumSentPackets; 544 EXPECT_CALL(*send_algorithm_, OnPacketAcked(_, _, _)).Times(3); 545 EXPECT_CALL(*send_algorithm_, OnPacketLost(1, _)).Times(1); 546 EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(1, _)).Times(1); 547 SequenceNumberSet retransmissions = 548 manager_.OnIncomingAckFrame(received_info, clock_.Now()); 549 EXPECT_EQ(1u, retransmissions.size()); 550 EXPECT_EQ(3u, QuicSentPacketManagerPeer::GetNackCount(&manager_, 1)); 551 } 552 553 // Ack a packet 3 packets ahead, causing a retransmit. 554 TEST_F(QuicSentPacketManagerTest, NackRetransmit1PacketSingleAck) { 555 const size_t kNumSentPackets = 4; 556 // Transmit 4 packets. 557 for (size_t i = 1; i <= kNumSentPackets; ++i) { 558 EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, _, _, _)) 559 .Times(1).WillOnce(Return(true)); 560 manager_.OnPacketSent(i, clock_.Now(), 1000, 561 NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA); 562 } 563 564 // Nack the first packet 3 times in an AckFrame with three missing packets. 565 ReceivedPacketInfo received_info; 566 received_info.delta_time_largest_observed = 567 QuicTime::Delta::FromMilliseconds(5); 568 received_info.missing_packets.insert(1); 569 received_info.missing_packets.insert(2); 570 received_info.missing_packets.insert(3); 571 received_info.largest_observed = kNumSentPackets; 572 EXPECT_CALL(*send_algorithm_, OnPacketAcked(kNumSentPackets, _, _)).Times(1); 573 EXPECT_CALL(*send_algorithm_, OnPacketLost(1, _)).Times(1); 574 EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(1, _)).Times(1); 575 SequenceNumberSet retransmissions = 576 manager_.OnIncomingAckFrame(received_info, clock_.Now()); 577 EXPECT_EQ(1u, retransmissions.size()); 578 EXPECT_EQ(3u, QuicSentPacketManagerPeer::GetNackCount(&manager_, 1)); 579 } 580 581 TEST_F(QuicSentPacketManagerTest, EarlyRetransmit1Packet) { 582 const size_t kNumSentPackets = 2; 583 // Transmit 2 packets. 584 for (size_t i = 1; i <= kNumSentPackets; ++i) { 585 EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, _, _, _)) 586 .Times(1).WillOnce(Return(true)); 587 manager_.OnPacketSent(i, clock_.Now(), 1000, 588 NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA); 589 } 590 591 // Early retransmit when the final packet gets acked and the first is nacked. 592 ReceivedPacketInfo received_info; 593 received_info.delta_time_largest_observed = 594 QuicTime::Delta::FromMilliseconds(5); 595 received_info.missing_packets.insert(1); 596 received_info.largest_observed = kNumSentPackets; 597 EXPECT_CALL(*send_algorithm_, OnPacketAcked(kNumSentPackets, _, _)).Times(1); 598 EXPECT_CALL(*send_algorithm_, OnPacketLost(1, _)).Times(1); 599 EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(1, _)).Times(1); 600 SequenceNumberSet retransmissions = 601 manager_.OnIncomingAckFrame(received_info, clock_.Now()); 602 EXPECT_EQ(1u, retransmissions.size()); 603 EXPECT_EQ(1u, QuicSentPacketManagerPeer::GetNackCount(&manager_, 1)); 604 } 605 606 TEST_F(QuicSentPacketManagerTest, DontEarlyRetransmitPacket) { 607 const size_t kNumSentPackets = 4; 608 for (size_t i = 1; i <= kNumSentPackets; ++i) { 609 EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, _, _, _)) 610 .Times(1).WillOnce(Return(true)); 611 manager_.OnPacketSent(i, clock_.Now(), 1000, 612 NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA); 613 } 614 615 // Fast retransmit when the final packet gets acked, but don't early 616 // retransmit as well, because there are 4 packets outstanding when the ack 617 // arrives. 618 ReceivedPacketInfo received_info; 619 received_info.delta_time_largest_observed = 620 QuicTime::Delta::FromMilliseconds(5); 621 received_info.missing_packets.insert(1); 622 received_info.missing_packets.insert(2); 623 received_info.missing_packets.insert(3); 624 received_info.largest_observed = kNumSentPackets; 625 EXPECT_CALL(*send_algorithm_, OnPacketAcked(kNumSentPackets, _, _)).Times(1); 626 EXPECT_CALL(*send_algorithm_, OnPacketLost(1, _)).Times(1); 627 EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(1, _)).Times(1); 628 SequenceNumberSet retransmissions = 629 manager_.OnIncomingAckFrame(received_info, clock_.Now()); 630 EXPECT_EQ(1u, retransmissions.size()); 631 EXPECT_EQ(3u, QuicSentPacketManagerPeer::GetNackCount(&manager_, 1)); 632 } 633 634 TEST_F(QuicSentPacketManagerTest, NackRetransmit2Packets) { 635 const size_t kNumSentPackets = 20; 636 // Transmit 20 packets. 637 for (QuicPacketSequenceNumber i = 1; i <= kNumSentPackets; ++i) { 638 EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, _, _, _)) 639 .Times(1).WillOnce(Return(true)); 640 manager_.OnPacketSent(i, clock_.Now(), 1000, 641 NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA); 642 } 643 644 // Nack the first 19 packets 3 times. 645 ReceivedPacketInfo received_info; 646 received_info.largest_observed = kNumSentPackets; 647 received_info.delta_time_largest_observed = 648 QuicTime::Delta::FromMilliseconds(5); 649 for (size_t i = 1; i < kNumSentPackets; ++i) { 650 received_info.missing_packets.insert(i); 651 } 652 EXPECT_CALL(*send_algorithm_, 653 OnPacketAcked(kNumSentPackets, _, _)).Times(1); 654 EXPECT_CALL(*send_algorithm_, OnPacketLost(_, _)).Times(2); 655 EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(_, _)).Times(2); 656 SequenceNumberSet retransmissions = 657 manager_.OnIncomingAckFrame(received_info, clock_.Now()); 658 EXPECT_EQ(2u, retransmissions.size()); 659 for (size_t i = 1; i < kNumSentPackets; ++i) { 660 EXPECT_EQ(kNumSentPackets - i, 661 QuicSentPacketManagerPeer::GetNackCount(&manager_, i)); 662 } 663 } 664 665 TEST_F(QuicSentPacketManagerTest, NackRetransmit2PacketsAlternateAcks) { 666 const size_t kNumSentPackets = 30; 667 // Transmit 15 packets of data and 15 ack packets. The send algorithm will 668 // inform the congestion manager not to save the acks by returning false. 669 for (QuicPacketSequenceNumber i = 1; i <= kNumSentPackets; ++i) { 670 EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, _, _, _)) 671 .Times(1).WillOnce(Return(i % 2 == 0 ? false : true)); 672 manager_.OnPacketSent( 673 i, clock_.Now(), 1000, NOT_RETRANSMISSION, 674 i % 2 == 0 ? NO_RETRANSMITTABLE_DATA : HAS_RETRANSMITTABLE_DATA); 675 } 676 677 // Nack the first 29 packets 3 times. 678 ReceivedPacketInfo received_info; 679 received_info.largest_observed = kNumSentPackets; 680 received_info.delta_time_largest_observed = 681 QuicTime::Delta::FromMilliseconds(5); 682 for (size_t i = 1; i < kNumSentPackets; ++i) { 683 received_info.missing_packets.insert(i); 684 } 685 // We never actually get an ack call, since the kNumSentPackets packet was 686 // not saved. 687 EXPECT_CALL(*send_algorithm_, OnPacketLost(_, _)).Times(2); 688 EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(_, _)).Times(2); 689 SequenceNumberSet retransmissions = 690 manager_.OnIncomingAckFrame(received_info, clock_.Now()); 691 EXPECT_EQ(2u, retransmissions.size()); 692 // Only non-ack packets have a nack count. 693 for (size_t i = 1; i < kNumSentPackets; i += 2) { 694 EXPECT_EQ(kNumSentPackets - i, 695 QuicSentPacketManagerPeer::GetNackCount(&manager_, i)); 696 } 697 698 // Ensure only the odd packets were retransmitted, since the others were not 699 // retransmittable(ie: acks). 700 for (SequenceNumberSet::const_iterator it = retransmissions.begin(); 701 it != retransmissions.end(); ++it) { 702 EXPECT_EQ(1u, *it % 2); 703 } 704 } 705 706 TEST_F(QuicSentPacketManagerTest, NackTwiceThenAck) { 707 // Transmit 4 packets. 708 for (QuicPacketSequenceNumber i = 1; i <= 4; ++i) { 709 EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, _, _, _)) 710 .Times(1).WillOnce(Return(true)); 711 manager_.OnPacketSent(i, clock_.Now(), 1000, 712 NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA); 713 } 714 715 // Nack the first packet 2 times, then ack it. 716 ReceivedPacketInfo received_info; 717 received_info.missing_packets.insert(1); 718 for (size_t i = 1; i <= 3; ++i) { 719 if (i == 3) { 720 received_info.missing_packets.clear(); 721 } 722 received_info.largest_observed = i + 1; 723 received_info.delta_time_largest_observed = 724 QuicTime::Delta::FromMilliseconds(5); 725 EXPECT_CALL(*send_algorithm_, 726 OnPacketAcked(_, _, _)).Times(i == 3 ? 2 : 1); 727 SequenceNumberSet retransmissions = 728 manager_.OnIncomingAckFrame(received_info, clock_.Now()); 729 EXPECT_EQ(0u, retransmissions.size()); 730 // The nack count remains at 2 when the packet is acked. 731 EXPECT_EQ(i == 3 ? 2u : i, 732 QuicSentPacketManagerPeer::GetNackCount(&manager_, 1)); 733 } 734 } 735 736 TEST_F(QuicSentPacketManagerTest, Rtt) { 737 QuicPacketSequenceNumber sequence_number = 1; 738 QuicTime::Delta expected_rtt = QuicTime::Delta::FromMilliseconds(15); 739 740 EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, _, _, _)) 741 .Times(1).WillOnce(Return(true)); 742 EXPECT_CALL(*send_algorithm_, 743 OnPacketAcked(sequence_number, _, expected_rtt)).Times(1); 744 745 manager_.OnPacketSent(sequence_number, clock_.Now(), 1000, 746 NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA); 747 clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(20)); 748 749 ReceivedPacketInfo received_info; 750 received_info.largest_observed = sequence_number; 751 received_info.delta_time_largest_observed = 752 QuicTime::Delta::FromMilliseconds(5); 753 manager_.OnIncomingAckFrame(received_info, clock_.Now()); 754 EXPECT_EQ(expected_rtt, QuicSentPacketManagerPeer::rtt(&manager_)); 755 } 756 757 TEST_F(QuicSentPacketManagerTest, RttWithInvalidDelta) { 758 // Expect that the RTT is equal to the local time elapsed, since the 759 // delta_time_largest_observed is larger than the local time elapsed 760 // and is hence invalid. 761 QuicPacketSequenceNumber sequence_number = 1; 762 QuicTime::Delta expected_rtt = QuicTime::Delta::FromMilliseconds(10); 763 764 EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, _, _, _)) 765 .Times(1).WillOnce(Return(true)); 766 EXPECT_CALL(*send_algorithm_, 767 OnPacketAcked(sequence_number, _, expected_rtt)).Times(1); 768 769 manager_.OnPacketSent(sequence_number, clock_.Now(), 1000, 770 NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA); 771 clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(10)); 772 773 ReceivedPacketInfo received_info; 774 received_info.largest_observed = sequence_number; 775 received_info.delta_time_largest_observed = 776 QuicTime::Delta::FromMilliseconds(11); 777 manager_.OnIncomingAckFrame(received_info, clock_.Now()); 778 EXPECT_EQ(expected_rtt, QuicSentPacketManagerPeer::rtt(&manager_)); 779 } 780 781 TEST_F(QuicSentPacketManagerTest, RttWithInfiniteDelta) { 782 // Expect that the RTT is equal to the local time elapsed, since the 783 // delta_time_largest_observed is infinite, and is hence invalid. 784 QuicPacketSequenceNumber sequence_number = 1; 785 QuicTime::Delta expected_rtt = QuicTime::Delta::FromMilliseconds(10); 786 787 EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, _, _, _)) 788 .Times(1).WillOnce(Return(true)); 789 EXPECT_CALL(*send_algorithm_, 790 OnPacketAcked(sequence_number, _, expected_rtt)).Times(1); 791 792 manager_.OnPacketSent(sequence_number, clock_.Now(), 1000, 793 NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA); 794 clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(10)); 795 796 ReceivedPacketInfo received_info; 797 received_info.largest_observed = sequence_number; 798 received_info.delta_time_largest_observed = QuicTime::Delta::Infinite(); 799 manager_.OnIncomingAckFrame(received_info, clock_.Now()); 800 EXPECT_EQ(expected_rtt, QuicSentPacketManagerPeer::rtt(&manager_)); 801 } 802 803 TEST_F(QuicSentPacketManagerTest, RttZeroDelta) { 804 // Expect that the RTT is the time between send and receive since the 805 // delta_time_largest_observed is zero. 806 QuicPacketSequenceNumber sequence_number = 1; 807 QuicTime::Delta expected_rtt = QuicTime::Delta::FromMilliseconds(10); 808 809 EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, _, _, _)) 810 .Times(1).WillOnce(Return(true)); 811 EXPECT_CALL(*send_algorithm_, OnPacketAcked(sequence_number, _, expected_rtt)) 812 .Times(1); 813 814 manager_.OnPacketSent(sequence_number, clock_.Now(), 1000, 815 NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA); 816 clock_.AdvanceTime(expected_rtt); 817 818 ReceivedPacketInfo received_info; 819 received_info.largest_observed = sequence_number; 820 received_info.delta_time_largest_observed = QuicTime::Delta::Zero(); 821 manager_.OnIncomingAckFrame(received_info, clock_.Now()); 822 EXPECT_EQ(expected_rtt, QuicSentPacketManagerPeer::rtt(&manager_)); 823 } 824 825 TEST_F(QuicSentPacketManagerTest, RetransmissionTimeout) { 826 // Send 100 packets and then ensure all are abandoned when the RTO fires. 827 const size_t kNumSentPackets = 100; 828 for (size_t i = 1; i <= kNumSentPackets; ++i) { 829 SendDataPacket(i); 830 } 831 832 EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(_, _)).Times(kNumSentPackets); 833 834 EXPECT_CALL(*send_algorithm_, RetransmissionDelay()) 835 .WillOnce(Return(QuicTime::Delta::FromMilliseconds(1))); 836 EXPECT_CALL(*send_algorithm_, OnRetransmissionTimeout()); 837 manager_.OnRetransmissionTimeout(); 838 } 839 840 TEST_F(QuicSentPacketManagerTest, GetTransmissionDelayMin) { 841 EXPECT_CALL(*send_algorithm_, RetransmissionDelay()) 842 .WillOnce(Return(QuicTime::Delta::FromMilliseconds(1))); 843 844 EXPECT_EQ(QuicTime::Delta::FromMilliseconds(200), 845 manager_.GetRetransmissionDelay()); 846 } 847 848 TEST_F(QuicSentPacketManagerTest, GetTransmissionDelayMax) { 849 EXPECT_CALL(*send_algorithm_, RetransmissionDelay()) 850 .WillOnce(Return(QuicTime::Delta::FromSeconds(500))); 851 852 EXPECT_EQ(QuicTime::Delta::FromSeconds(60), 853 manager_.GetRetransmissionDelay()); 854 } 855 856 TEST_F(QuicSentPacketManagerTest, GetTransmissionDelay) { 857 SendDataPacket(1); 858 QuicTime::Delta delay = QuicTime::Delta::FromMilliseconds(500); 859 EXPECT_CALL(*send_algorithm_, RetransmissionDelay()) 860 .WillRepeatedly(Return(delay)); 861 862 // Delay should back off exponentially. 863 for (int i = 0; i < 5; ++i) { 864 EXPECT_EQ(delay, manager_.GetRetransmissionDelay()); 865 delay = delay.Add(delay); 866 EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(i + 1, _)); 867 EXPECT_CALL(*send_algorithm_, OnRetransmissionTimeout()); 868 manager_.OnRetransmissionTimeout(); 869 RetransmitNextPacket(i + 2); 870 } 871 } 872 873 TEST_F(QuicSentPacketManagerTest, GetTestTransmissionDelayTailDrop) { 874 FLAGS_limit_rto_increase_for_tests = true; 875 876 SendDataPacket(1); 877 QuicTime::Delta delay = QuicTime::Delta::FromMilliseconds(500); 878 EXPECT_CALL(*send_algorithm_, RetransmissionDelay()) 879 .WillRepeatedly(Return(delay)); 880 881 // No backoff for the first 5 retransmissions. 882 for (int i = 0; i < 5; ++i) { 883 EXPECT_EQ(delay, manager_.GetRetransmissionDelay()); 884 EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(i + 1, _)); 885 EXPECT_CALL(*send_algorithm_, OnRetransmissionTimeout()); 886 manager_.OnRetransmissionTimeout(); 887 RetransmitNextPacket(i + 2); 888 } 889 890 // Then backoff starts 891 EXPECT_EQ(delay.Add(delay), manager_.GetRetransmissionDelay()); 892 } 893 894 } // namespace 895 } // namespace test 896 } // namespace net 897
