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