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