1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "net/quic/congestion_control/time_loss_algorithm.h"
#include <algorithm>
#include "base/logging.h"
#include "base/stl_util.h"
#include "net/quic/congestion_control/rtt_stats.h"
#include "net/quic/quic_unacked_packet_map.h"
#include "net/quic/test_tools/mock_clock.h"
#include "testing/gtest/include/gtest/gtest.h"
using std::vector;
namespace net {
namespace test {
namespace {
// Default packet length.
const uint32 kDefaultLength = 1000;
class TimeLossAlgorithmTest : public ::testing::Test {
protected:
TimeLossAlgorithmTest() {
rtt_stats_.UpdateRtt(QuicTime::Delta::FromMilliseconds(100),
QuicTime::Delta::Zero(),
clock_.Now());
}
~TimeLossAlgorithmTest() override {
STLDeleteElements(&packets_);
}
void SendDataPacket(QuicPacketNumber packet_number) {
packets_.push_back(new QuicEncryptedPacket(nullptr, kDefaultLength));
SerializedPacket packet(
packet_number, PACKET_1BYTE_PACKET_NUMBER, packets_.back(), 0,
new RetransmittableFrames(ENCRYPTION_NONE), false, false);
unacked_packets_.AddSentPacket(&packet, 0, NOT_RETRANSMISSION, clock_.Now(),
1000, true);
}
void VerifyLosses(QuicPacketNumber largest_observed,
QuicPacketNumber* losses_expected,
size_t num_losses) {
PacketNumberSet lost_packets = loss_algorithm_.DetectLostPackets(
unacked_packets_, clock_.Now(), largest_observed, rtt_stats_);
EXPECT_EQ(num_losses, lost_packets.size());
for (size_t i = 0; i < num_losses; ++i) {
EXPECT_TRUE(ContainsKey(lost_packets, losses_expected[i]));
}
}
vector<QuicEncryptedPacket*> packets_;
QuicUnackedPacketMap unacked_packets_;
TimeLossAlgorithm loss_algorithm_;
RttStats rtt_stats_;
MockClock clock_;
};
TEST_F(TimeLossAlgorithmTest, NoLossFor500Nacks) {
const size_t kNumSentPackets = 5;
// Transmit 5 packets.
for (size_t i = 1; i <= kNumSentPackets; ++i) {
SendDataPacket(i);
}
unacked_packets_.RemoveFromInFlight(2);
for (size_t i = 1; i < 500; ++i) {
unacked_packets_.NackPacket(1, i);
VerifyLosses(2, nullptr, 0);
}
EXPECT_EQ(rtt_stats_.smoothed_rtt().Multiply(1.25),
loss_algorithm_.GetLossTimeout().Subtract(clock_.Now()));
}
TEST_F(TimeLossAlgorithmTest, NoLossUntilTimeout) {
const size_t kNumSentPackets = 10;
// Transmit 10 packets at 1/10th an RTT interval.
for (size_t i = 1; i <= kNumSentPackets; ++i) {
SendDataPacket(i);
clock_.AdvanceTime(rtt_stats_.smoothed_rtt().Multiply(0.1));
}
// Expect the timer to not be set.
EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
// The packet should not be lost until 1.25 RTTs pass.
unacked_packets_.NackPacket(1, 1);
unacked_packets_.RemoveFromInFlight(2);
VerifyLosses(2, nullptr, 0);
// Expect the timer to be set to 0.25 RTT's in the future.
EXPECT_EQ(rtt_stats_.smoothed_rtt().Multiply(0.25),
loss_algorithm_.GetLossTimeout().Subtract(clock_.Now()));
unacked_packets_.NackPacket(1, 5);
VerifyLosses(2, nullptr, 0);
clock_.AdvanceTime(rtt_stats_.smoothed_rtt().Multiply(0.25));
QuicPacketNumber lost[] = {1};
VerifyLosses(2, lost, arraysize(lost));
EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
}
TEST_F(TimeLossAlgorithmTest, NoLossWithoutNack) {
const size_t kNumSentPackets = 10;
// Transmit 10 packets at 1/10th an RTT interval.
for (size_t i = 1; i <= kNumSentPackets; ++i) {
SendDataPacket(i);
clock_.AdvanceTime(rtt_stats_.smoothed_rtt().Multiply(0.1));
}
// Expect the timer to not be set.
EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
// The packet should not be lost without a nack.
unacked_packets_.RemoveFromInFlight(1);
VerifyLosses(1, nullptr, 0);
// The timer should still not be set.
EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
clock_.AdvanceTime(rtt_stats_.smoothed_rtt().Multiply(0.25));
VerifyLosses(1, nullptr, 0);
clock_.AdvanceTime(rtt_stats_.smoothed_rtt());
VerifyLosses(1, nullptr, 0);
EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
}
TEST_F(TimeLossAlgorithmTest, MultipleLossesAtOnce) {
const size_t kNumSentPackets = 10;
// Transmit 10 packets at once and then go forward an RTT.
for (size_t i = 1; i <= kNumSentPackets; ++i) {
SendDataPacket(i);
}
clock_.AdvanceTime(rtt_stats_.smoothed_rtt());
// Expect the timer to not be set.
EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
// The packet should not be lost until 1.25 RTTs pass.
for (size_t i = 1; i < kNumSentPackets; ++i) {
unacked_packets_.NackPacket(i, 1);
}
unacked_packets_.RemoveFromInFlight(10);
VerifyLosses(10, nullptr, 0);
// Expect the timer to be set to 0.25 RTT's in the future.
EXPECT_EQ(rtt_stats_.smoothed_rtt().Multiply(0.25),
loss_algorithm_.GetLossTimeout().Subtract(clock_.Now()));
clock_.AdvanceTime(rtt_stats_.smoothed_rtt().Multiply(0.25));
QuicPacketNumber lost[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
VerifyLosses(10, lost, arraysize(lost));
EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
}
} // namespace
} // namespace test
} // namespace net
|
