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