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