net/quic/congestion_control/time_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/time_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 TimeLossAlgorithmTest : public ::testing::Test {
  25  protected:
  26   TimeLossAlgorithmTest()
  27       : unacked_packets_() {
  28     rtt_stats_.UpdateRtt(QuicTime::Delta::FromMilliseconds(100),
  29                          QuicTime::Delta::Zero(),
  30                          clock_.Now());
  31   }
  32
  33   ~TimeLossAlgorithmTest() 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   TimeLossAlgorithm loss_algorithm_;
  61   RttStats rtt_stats_;
  62   MockClock clock_;
  63 };
  64
  65 TEST_F(TimeLossAlgorithmTest, NoLossFor500Nacks) {
  66   const size_t kNumSentPackets = 5;
  67   // Transmit 5 packets.
  68   for (size_t i = 1; i <= kNumSentPackets; ++i) {
  69     SendDataPacket(i);
  70   }
  71   unacked_packets_.RemoveFromInFlight(2);
  72   for (size_t i = 1; i < 500; ++i) {
  73     unacked_packets_.NackPacket(1, i);
  74     VerifyLosses(2, nullptr, 0);
  75   }
  76   EXPECT_EQ(rtt_stats_.smoothed_rtt().Multiply(1.25),
  77             loss_algorithm_.GetLossTimeout().Subtract(clock_.Now()));
  78 }
  79
  80 TEST_F(TimeLossAlgorithmTest, NoLossUntilTimeout) {
  81   const size_t kNumSentPackets = 10;
  82   // Transmit 10 packets at 1/10th an RTT interval.
  83   for (size_t i = 1; i <= kNumSentPackets; ++i) {
  84     SendDataPacket(i);
  85     clock_.AdvanceTime(rtt_stats_.smoothed_rtt().Multiply(0.1));
  86   }
  87   // Expect the timer to not be set.
  88   EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
  89   // The packet should not be lost until 1.25 RTTs pass.
  90   unacked_packets_.NackPacket(1, 1);
  91   unacked_packets_.RemoveFromInFlight(2);
  92   VerifyLosses(2, nullptr, 0);
  93   // Expect the timer to be set to 0.25 RTT's in the future.
  94   EXPECT_EQ(rtt_stats_.smoothed_rtt().Multiply(0.25),
  95             loss_algorithm_.GetLossTimeout().Subtract(clock_.Now()));
  96   unacked_packets_.NackPacket(1, 5);
  97   VerifyLosses(2, nullptr, 0);
  98   clock_.AdvanceTime(rtt_stats_.smoothed_rtt().Multiply(0.25));
  99   QuicPacketSequenceNumber lost[] = { 1 };
 100   VerifyLosses(2, lost, arraysize(lost));
 101   EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
 102 }
 103
 104 TEST_F(TimeLossAlgorithmTest, NoLossWithoutNack) {
 105   const size_t kNumSentPackets = 10;
 106   // Transmit 10 packets at 1/10th an RTT interval.
 107   for (size_t i = 1; i <= kNumSentPackets; ++i) {
 108     SendDataPacket(i);
 109     clock_.AdvanceTime(rtt_stats_.smoothed_rtt().Multiply(0.1));
 110   }
 111   // Expect the timer to not be set.
 112   EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
 113   // The packet should not be lost without a nack.
 114   unacked_packets_.RemoveFromInFlight(1);
 115   VerifyLosses(1, nullptr, 0);
 116   // The timer should still not be set.
 117   EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
 118   clock_.AdvanceTime(rtt_stats_.smoothed_rtt().Multiply(0.25));
 119   VerifyLosses(1, nullptr, 0);
 120   clock_.AdvanceTime(rtt_stats_.smoothed_rtt());
 121   VerifyLosses(1, nullptr, 0);
 122
 123   EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
 124 }
 125
 126 TEST_F(TimeLossAlgorithmTest, MultipleLossesAtOnce) {
 127   const size_t kNumSentPackets = 10;
 128   // Transmit 10 packets at once and then go forward an RTT.
 129   for (size_t i = 1; i <= kNumSentPackets; ++i) {
 130     SendDataPacket(i);
 131   }
 132   clock_.AdvanceTime(rtt_stats_.smoothed_rtt());
 133   // Expect the timer to not be set.
 134   EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
 135   // The packet should not be lost until 1.25 RTTs pass.
 136   for (size_t i = 1; i < kNumSentPackets; ++i) {
 137     unacked_packets_.NackPacket(i, 1);
 138   }
 139   unacked_packets_.RemoveFromInFlight(10);
 140   VerifyLosses(10, nullptr, 0);
 141   // Expect the timer to be set to 0.25 RTT's in the future.
 142   EXPECT_EQ(rtt_stats_.smoothed_rtt().Multiply(0.25),
 143             loss_algorithm_.GetLossTimeout().Subtract(clock_.Now()));
 144   clock_.AdvanceTime(rtt_stats_.smoothed_rtt().Multiply(0.25));
 145   QuicPacketSequenceNumber lost[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 146   VerifyLosses(10, lost, arraysize(lost));
 147   EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
 148 }
 149
 150 }  // namespace
 151 }  // namespace test
 152 }  // namespace net