net/quic/congestion_control/tcp_loss_algorithm_test.cc

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