OLD | NEW |
1 // Copyright 2014 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include <algorithm> | 5 #include <algorithm> |
6 | 6 |
7 #include "base/logging.h" | 7 #include "base/logging.h" |
8 #include "base/stl_util.h" | 8 #include "base/stl_util.h" |
9 #include "net/quic/congestion_control/rtt_stats.h" | 9 #include "net/quic/congestion_control/rtt_stats.h" |
10 #include "net/quic/congestion_control/tcp_loss_algorithm.h" | 10 #include "net/quic/congestion_control/tcp_loss_algorithm.h" |
11 #include "net/quic/quic_unacked_packet_map.h" | 11 #include "net/quic/quic_unacked_packet_map.h" |
12 #include "net/quic/test_tools/mock_clock.h" | 12 #include "net/quic/test_tools/mock_clock.h" |
13 #include "testing/gtest/include/gtest/gtest.h" | 13 #include "testing/gtest/include/gtest/gtest.h" |
14 | 14 |
15 namespace net { | 15 namespace net { |
16 namespace test { | 16 namespace test { |
17 | 17 |
18 class TcpLossAlgorithmTest : public ::testing::Test { | 18 class TcpLossAlgorithmTest : public ::testing::Test { |
19 protected: | 19 protected: |
20 TcpLossAlgorithmTest() | 20 TcpLossAlgorithmTest() : unacked_packets_() { |
21 : unacked_packets_() { | |
22 rtt_stats_.UpdateRtt(QuicTime::Delta::FromMilliseconds(100), | 21 rtt_stats_.UpdateRtt(QuicTime::Delta::FromMilliseconds(100), |
23 QuicTime::Delta::Zero(), | 22 QuicTime::Delta::Zero(), |
24 clock_.Now()); | 23 clock_.Now()); |
25 } | 24 } |
26 | 25 |
27 void SendDataPacket(QuicPacketSequenceNumber sequence_number) { | 26 void SendDataPacket(QuicPacketSequenceNumber sequence_number) { |
28 SerializedPacket packet(sequence_number, PACKET_1BYTE_SEQUENCE_NUMBER, | 27 SerializedPacket packet(sequence_number, |
29 NULL, 0, new RetransmittableFrames()); | 28 PACKET_1BYTE_SEQUENCE_NUMBER, |
| 29 NULL, |
| 30 0, |
| 31 new RetransmittableFrames()); |
30 unacked_packets_.AddPacket(packet); | 32 unacked_packets_.AddPacket(packet); |
31 unacked_packets_.SetSent(sequence_number, clock_.Now(), 1000, true); | 33 unacked_packets_.SetSent(sequence_number, clock_.Now(), 1000, true); |
32 } | 34 } |
33 | 35 |
34 void VerifyLosses(QuicPacketSequenceNumber largest_observed, | 36 void VerifyLosses(QuicPacketSequenceNumber largest_observed, |
35 QuicPacketSequenceNumber* losses_expected, | 37 QuicPacketSequenceNumber* losses_expected, |
36 size_t num_losses) { | 38 size_t num_losses) { |
37 SequenceNumberSet lost_packets = | 39 SequenceNumberSet lost_packets = loss_algorithm_.DetectLostPackets( |
38 loss_algorithm_.DetectLostPackets( | 40 unacked_packets_, clock_.Now(), largest_observed, rtt_stats_); |
39 unacked_packets_, clock_.Now(), largest_observed, rtt_stats_); | |
40 EXPECT_EQ(num_losses, lost_packets.size()); | 41 EXPECT_EQ(num_losses, lost_packets.size()); |
41 for (size_t i = 0; i < num_losses; ++i) { | 42 for (size_t i = 0; i < num_losses; ++i) { |
42 EXPECT_TRUE(ContainsKey(lost_packets, losses_expected[i])); | 43 EXPECT_TRUE(ContainsKey(lost_packets, losses_expected[i])); |
43 } | 44 } |
44 } | 45 } |
45 | 46 |
46 QuicUnackedPacketMap unacked_packets_; | 47 QuicUnackedPacketMap unacked_packets_; |
47 TCPLossAlgorithm loss_algorithm_; | 48 TCPLossAlgorithm loss_algorithm_; |
48 RttStats rtt_stats_; | 49 RttStats rtt_stats_; |
49 MockClock clock_; | 50 MockClock clock_; |
50 }; | 51 }; |
51 | 52 |
52 TEST_F(TcpLossAlgorithmTest, NackRetransmit1Packet) { | 53 TEST_F(TcpLossAlgorithmTest, NackRetransmit1Packet) { |
53 const size_t kNumSentPackets = 5; | 54 const size_t kNumSentPackets = 5; |
54 // Transmit 5 packets. | 55 // Transmit 5 packets. |
55 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 56 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
56 SendDataPacket(i); | 57 SendDataPacket(i); |
57 } | 58 } |
58 // No loss on one ack. | 59 // No loss on one ack. |
59 unacked_packets_.SetNotPending(2); | 60 unacked_packets_.SetNotPending(2); |
60 unacked_packets_.NackPacket(1, 1); | 61 unacked_packets_.NackPacket(1, 1); |
61 VerifyLosses(2, NULL, 0); | 62 VerifyLosses(2, NULL, 0); |
62 // No loss on two acks. | 63 // No loss on two acks. |
63 unacked_packets_.SetNotPending(3); | 64 unacked_packets_.SetNotPending(3); |
64 unacked_packets_.NackPacket(1, 2); | 65 unacked_packets_.NackPacket(1, 2); |
65 VerifyLosses(3, NULL, 0); | 66 VerifyLosses(3, NULL, 0); |
66 // Loss on three acks. | 67 // Loss on three acks. |
67 unacked_packets_.SetNotPending(4); | 68 unacked_packets_.SetNotPending(4); |
68 unacked_packets_.NackPacket(1, 3); | 69 unacked_packets_.NackPacket(1, 3); |
69 QuicPacketSequenceNumber lost[] = { 1 }; | 70 QuicPacketSequenceNumber lost[] = {1}; |
70 VerifyLosses(4, lost, arraysize(lost)); | 71 VerifyLosses(4, lost, arraysize(lost)); |
71 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 72 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
72 } | 73 } |
73 | 74 |
74 // A stretch ack is an ack that covers more than 1 packet of previously | 75 // A stretch ack is an ack that covers more than 1 packet of previously |
75 // unacknowledged data. | 76 // unacknowledged data. |
76 TEST_F(TcpLossAlgorithmTest, NackRetransmit1PacketWith1StretchAck) { | 77 TEST_F(TcpLossAlgorithmTest, NackRetransmit1PacketWith1StretchAck) { |
77 const size_t kNumSentPackets = 10; | 78 const size_t kNumSentPackets = 10; |
78 // Transmit 10 packets. | 79 // Transmit 10 packets. |
79 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 80 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
80 SendDataPacket(i); | 81 SendDataPacket(i); |
81 } | 82 } |
82 | 83 |
83 // Nack the first packet 3 times in a single StretchAck. | 84 // Nack the first packet 3 times in a single StretchAck. |
84 unacked_packets_.NackPacket(1, 3); | 85 unacked_packets_.NackPacket(1, 3); |
85 unacked_packets_.SetNotPending(2); | 86 unacked_packets_.SetNotPending(2); |
86 unacked_packets_.SetNotPending(3); | 87 unacked_packets_.SetNotPending(3); |
87 unacked_packets_.SetNotPending(4); | 88 unacked_packets_.SetNotPending(4); |
88 QuicPacketSequenceNumber lost[] = { 1 }; | 89 QuicPacketSequenceNumber lost[] = {1}; |
89 VerifyLosses(4, lost, arraysize(lost)); | 90 VerifyLosses(4, lost, arraysize(lost)); |
90 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 91 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
91 } | 92 } |
92 | 93 |
93 // Ack a packet 3 packets ahead, causing a retransmit. | 94 // Ack a packet 3 packets ahead, causing a retransmit. |
94 TEST_F(TcpLossAlgorithmTest, NackRetransmit1PacketSingleAck) { | 95 TEST_F(TcpLossAlgorithmTest, NackRetransmit1PacketSingleAck) { |
95 const size_t kNumSentPackets = 10; | 96 const size_t kNumSentPackets = 10; |
96 // Transmit 10 packets. | 97 // Transmit 10 packets. |
97 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 98 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
98 SendDataPacket(i); | 99 SendDataPacket(i); |
99 } | 100 } |
100 | 101 |
101 // Nack the first packet 3 times in an AckFrame with three missing packets. | 102 // Nack the first packet 3 times in an AckFrame with three missing packets. |
102 unacked_packets_.NackPacket(1, 3); | 103 unacked_packets_.NackPacket(1, 3); |
103 unacked_packets_.NackPacket(2, 2); | 104 unacked_packets_.NackPacket(2, 2); |
104 unacked_packets_.NackPacket(3, 1); | 105 unacked_packets_.NackPacket(3, 1); |
105 unacked_packets_.SetNotPending(4); | 106 unacked_packets_.SetNotPending(4); |
106 QuicPacketSequenceNumber lost[] = { 1 }; | 107 QuicPacketSequenceNumber lost[] = {1}; |
107 VerifyLosses(4, lost, arraysize(lost)); | 108 VerifyLosses(4, lost, arraysize(lost)); |
108 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 109 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
109 } | 110 } |
110 | 111 |
111 TEST_F(TcpLossAlgorithmTest, EarlyRetransmit1Packet) { | 112 TEST_F(TcpLossAlgorithmTest, EarlyRetransmit1Packet) { |
112 const size_t kNumSentPackets = 2; | 113 const size_t kNumSentPackets = 2; |
113 // Transmit 2 packets. | 114 // Transmit 2 packets. |
114 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 115 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
115 SendDataPacket(i); | 116 SendDataPacket(i); |
116 } | 117 } |
117 // Early retransmit when the final packet gets acked and the first is nacked. | 118 // Early retransmit when the final packet gets acked and the first is nacked. |
118 unacked_packets_.SetNotPending(2); | 119 unacked_packets_.SetNotPending(2); |
119 unacked_packets_.NackPacket(1, 1); | 120 unacked_packets_.NackPacket(1, 1); |
120 VerifyLosses(2, NULL, 0); | 121 VerifyLosses(2, NULL, 0); |
121 EXPECT_EQ(clock_.Now().Add(rtt_stats_.SmoothedRtt().Multiply(1.25)), | 122 EXPECT_EQ(clock_.Now().Add(rtt_stats_.SmoothedRtt().Multiply(1.25)), |
122 loss_algorithm_.GetLossTimeout()); | 123 loss_algorithm_.GetLossTimeout()); |
123 | 124 |
124 clock_.AdvanceTime(rtt_stats_.latest_rtt().Multiply(1.25)); | 125 clock_.AdvanceTime(rtt_stats_.latest_rtt().Multiply(1.25)); |
125 QuicPacketSequenceNumber lost[] = { 1 }; | 126 QuicPacketSequenceNumber lost[] = {1}; |
126 VerifyLosses(2, lost, arraysize(lost)); | 127 VerifyLosses(2, lost, arraysize(lost)); |
127 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 128 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
128 } | 129 } |
129 | 130 |
130 TEST_F(TcpLossAlgorithmTest, EarlyRetransmitAllPackets) { | 131 TEST_F(TcpLossAlgorithmTest, EarlyRetransmitAllPackets) { |
131 const size_t kNumSentPackets = 5; | 132 const size_t kNumSentPackets = 5; |
132 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 133 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
133 SendDataPacket(i); | 134 SendDataPacket(i); |
134 // Advance the time 1/4 RTT between 3 and 4. | 135 // Advance the time 1/4 RTT between 3 and 4. |
135 if (i == 3) { | 136 if (i == 3) { |
136 clock_.AdvanceTime(rtt_stats_.SmoothedRtt().Multiply(0.25)); | 137 clock_.AdvanceTime(rtt_stats_.SmoothedRtt().Multiply(0.25)); |
137 } | 138 } |
138 } | 139 } |
139 | 140 |
140 // Early retransmit when the final packet gets acked and 1.25 RTTs have | 141 // Early retransmit when the final packet gets acked and 1.25 RTTs have |
141 // elapsed since the packets were sent. | 142 // elapsed since the packets were sent. |
142 unacked_packets_.SetNotPending(kNumSentPackets); | 143 unacked_packets_.SetNotPending(kNumSentPackets); |
143 // This simulates a single ack following multiple missing packets with FACK. | 144 // This simulates a single ack following multiple missing packets with FACK. |
144 for (size_t i = 1; i < kNumSentPackets; ++i) { | 145 for (size_t i = 1; i < kNumSentPackets; ++i) { |
145 unacked_packets_.NackPacket(i, kNumSentPackets - i); | 146 unacked_packets_.NackPacket(i, kNumSentPackets - i); |
146 } | 147 } |
147 QuicPacketSequenceNumber lost[] = { 1, 2 }; | 148 QuicPacketSequenceNumber lost[] = {1, 2}; |
148 VerifyLosses(kNumSentPackets, lost, arraysize(lost)); | 149 VerifyLosses(kNumSentPackets, lost, arraysize(lost)); |
149 // The time has already advanced 1/4 an RTT, so ensure the timeout is set | 150 // The time has already advanced 1/4 an RTT, so ensure the timeout is set |
150 // 1.25 RTTs after the earliest pending packet(3), not the last(4). | 151 // 1.25 RTTs after the earliest pending packet(3), not the last(4). |
151 EXPECT_EQ(clock_.Now().Add(rtt_stats_.SmoothedRtt()), | 152 EXPECT_EQ(clock_.Now().Add(rtt_stats_.SmoothedRtt()), |
152 loss_algorithm_.GetLossTimeout()); | 153 loss_algorithm_.GetLossTimeout()); |
153 | 154 |
154 clock_.AdvanceTime(rtt_stats_.SmoothedRtt()); | 155 clock_.AdvanceTime(rtt_stats_.SmoothedRtt()); |
155 QuicPacketSequenceNumber lost2[] = { 1, 2, 3 }; | 156 QuicPacketSequenceNumber lost2[] = {1, 2, 3}; |
156 VerifyLosses(kNumSentPackets, lost2, arraysize(lost2)); | 157 VerifyLosses(kNumSentPackets, lost2, arraysize(lost2)); |
157 EXPECT_EQ(clock_.Now().Add(rtt_stats_.SmoothedRtt().Multiply(0.25)), | 158 EXPECT_EQ(clock_.Now().Add(rtt_stats_.SmoothedRtt().Multiply(0.25)), |
158 loss_algorithm_.GetLossTimeout()); | 159 loss_algorithm_.GetLossTimeout()); |
159 clock_.AdvanceTime(rtt_stats_.SmoothedRtt().Multiply(0.25)); | 160 clock_.AdvanceTime(rtt_stats_.SmoothedRtt().Multiply(0.25)); |
160 QuicPacketSequenceNumber lost3[] = { 1, 2, 3, 4 }; | 161 QuicPacketSequenceNumber lost3[] = {1, 2, 3, 4}; |
161 VerifyLosses(kNumSentPackets, lost3, arraysize(lost3)); | 162 VerifyLosses(kNumSentPackets, lost3, arraysize(lost3)); |
162 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 163 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
163 } | 164 } |
164 | 165 |
165 TEST_F(TcpLossAlgorithmTest, DontEarlyRetransmitNeuteredPacket) { | 166 TEST_F(TcpLossAlgorithmTest, DontEarlyRetransmitNeuteredPacket) { |
166 const size_t kNumSentPackets = 2; | 167 const size_t kNumSentPackets = 2; |
167 // Transmit 2 packets. | 168 // Transmit 2 packets. |
168 for (size_t i = 1; i <= kNumSentPackets; ++i) { | 169 for (size_t i = 1; i <= kNumSentPackets; ++i) { |
169 SendDataPacket(i); | 170 SendDataPacket(i); |
170 } | 171 } |
171 // Early retransmit when the final packet gets acked and the first is nacked. | 172 // Early retransmit when the final packet gets acked and the first is nacked. |
172 unacked_packets_.SetNotPending(2); | 173 unacked_packets_.SetNotPending(2); |
173 unacked_packets_.NackPacket(1, 1); | 174 unacked_packets_.NackPacket(1, 1); |
174 unacked_packets_.NeuterPacket(1); | 175 unacked_packets_.NeuterPacket(1); |
175 VerifyLosses(2, NULL, 0); | 176 VerifyLosses(2, NULL, 0); |
176 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); | 177 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
177 } | 178 } |
178 | 179 |
179 } // namespace test | 180 } // namespace test |
180 } // namespace net | 181 } // namespace net |
OLD | NEW |