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