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