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
13using std::vector;
14using testing::_;
15using testing::Return;
16using testing::StrictMock;
17
18namespace net {
19namespace test {
20namespace {
21
22class MockHelper : public QuicSentPacketManager::HelperInterface {
23 public:
24  MOCK_METHOD0(GetNextPacketSequenceNumber, QuicPacketSequenceNumber());
25};
26
27class 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
148TEST_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
161TEST_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
174TEST_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
191TEST_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
212TEST_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
236TEST_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
261TEST_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
284TEST_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
408TEST_F(QuicSentPacketManagerTest, GetLeastUnackedSentPacket) {
409  EXPECT_CALL(helper_, GetNextPacketSequenceNumber()).WillOnce(Return(1u));
410  EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket());
411}
412
413TEST_F(QuicSentPacketManagerTest, GetLeastUnackedSentPacketUnacked) {
414  SerializedPacket serialized_packet(CreatePacket(1));
415
416  manager_.OnSerializedPacket(serialized_packet);
417  EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket());
418}
419
420TEST_F(QuicSentPacketManagerTest, GetLeastUnackedSentPacketUnackedFec) {
421  SerializedPacket serialized_packet(CreateFecPacket(1));
422
423  manager_.OnSerializedPacket(serialized_packet);
424  EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket());
425}
426
427TEST_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
436TEST_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
470TEST_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
497TEST_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.
528TEST_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.
554TEST_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
581TEST_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
606TEST_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
634TEST_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
665TEST_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
706TEST_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
736TEST_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
757TEST_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
781TEST_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
803TEST_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
825TEST_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
840TEST_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
848TEST_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
856TEST_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
873TEST_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