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
15namespace net {
16namespace test {
17
18class TimeLossAlgorithmTest : public ::testing::Test {
19 protected:
20  TimeLossAlgorithmTest()
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  TimeLossAlgorithm loss_algorithm_;
48  RttStats rtt_stats_;
49  MockClock clock_;
50};
51
52TEST_F(TimeLossAlgorithmTest, NoLossFor500Nacks) {
53  const size_t kNumSentPackets = 5;
54  // Transmit 5 packets.
55  for (size_t i = 1; i <= kNumSentPackets; ++i) {
56    SendDataPacket(i);
57  }
58  unacked_packets_.RemoveFromInFlight(2);
59  for (size_t i = 1; i < 500; ++i) {
60    unacked_packets_.NackPacket(1, i);
61    VerifyLosses(2, NULL, 0);
62  }
63  EXPECT_EQ(rtt_stats_.SmoothedRtt().Multiply(1.25),
64            loss_algorithm_.GetLossTimeout().Subtract(clock_.Now()));
65}
66
67TEST_F(TimeLossAlgorithmTest, NoLossUntilTimeout) {
68  const size_t kNumSentPackets = 10;
69  // Transmit 10 packets at 1/10th an RTT interval.
70  for (size_t i = 1; i <= kNumSentPackets; ++i) {
71    SendDataPacket(i);
72    clock_.AdvanceTime(rtt_stats_.SmoothedRtt().Multiply(0.1));
73  }
74  // Expect the timer to not be set.
75  EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
76  // The packet should not be lost until 1.25 RTTs pass.
77  unacked_packets_.NackPacket(1, 1);
78  unacked_packets_.RemoveFromInFlight(2);
79  VerifyLosses(2, NULL, 0);
80  // Expect the timer to be set to 0.25 RTT's in the future.
81  EXPECT_EQ(rtt_stats_.SmoothedRtt().Multiply(0.25),
82            loss_algorithm_.GetLossTimeout().Subtract(clock_.Now()));
83  unacked_packets_.NackPacket(1, 5);
84  VerifyLosses(2, NULL, 0);
85  clock_.AdvanceTime(rtt_stats_.SmoothedRtt().Multiply(0.25));
86  QuicPacketSequenceNumber lost[] = { 1 };
87  VerifyLosses(2, lost, arraysize(lost));
88  EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
89}
90
91TEST_F(TimeLossAlgorithmTest, NoLossWithoutNack) {
92  const size_t kNumSentPackets = 10;
93  // Transmit 10 packets at 1/10th an RTT interval.
94  for (size_t i = 1; i <= kNumSentPackets; ++i) {
95    SendDataPacket(i);
96    clock_.AdvanceTime(rtt_stats_.SmoothedRtt().Multiply(0.1));
97  }
98  // Expect the timer to not be set.
99  EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
100  // The packet should not be lost without a nack.
101  unacked_packets_.RemoveFromInFlight(1);
102  VerifyLosses(1, NULL, 0);
103  // The timer should still not be set.
104  EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
105  clock_.AdvanceTime(rtt_stats_.SmoothedRtt().Multiply(0.25));
106  VerifyLosses(1, NULL, 0);
107  clock_.AdvanceTime(rtt_stats_.SmoothedRtt());
108  VerifyLosses(1, NULL, 0);
109
110  EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
111}
112
113TEST_F(TimeLossAlgorithmTest, MultipleLossesAtOnce) {
114  const size_t kNumSentPackets = 10;
115  // Transmit 10 packets at once and then go forward an RTT.
116  for (size_t i = 1; i <= kNumSentPackets; ++i) {
117    SendDataPacket(i);
118  }
119  clock_.AdvanceTime(rtt_stats_.SmoothedRtt());
120  // Expect the timer to not be set.
121  EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
122  // The packet should not be lost until 1.25 RTTs pass.
123  for (size_t i = 1; i < kNumSentPackets; ++i) {
124    unacked_packets_.NackPacket(i, 1);
125  }
126  unacked_packets_.RemoveFromInFlight(10);
127  VerifyLosses(10, NULL, 0);
128  // Expect the timer to be set to 0.25 RTT's in the future.
129  EXPECT_EQ(rtt_stats_.SmoothedRtt().Multiply(0.25),
130            loss_algorithm_.GetLossTimeout().Subtract(clock_.Now()));
131  clock_.AdvanceTime(rtt_stats_.SmoothedRtt().Multiply(0.25));
132  QuicPacketSequenceNumber lost[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
133  VerifyLosses(10, lost, arraysize(lost));
134  EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
135}
136
137}  // namespace test
138}  // namespace net
139