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 namespace net {
  16 namespace test {
  17
  18 class 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
  52 TEST_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.
  76 TEST_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.
  94 TEST_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
 111 TEST_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
 130 TEST_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
 165 TEST_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