1 // Copyright 2013 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 #include <map>
7 #include <memory>
8 #include <string>
9 #include <utility>
10
11 #include "absl/strings/str_cat.h"
12 #include "quiche/quic/core/congestion_control/rtt_stats.h"
13 #include "quiche/quic/core/congestion_control/send_algorithm_interface.h"
14 #include "quiche/quic/core/quic_types.h"
15 #include "quiche/quic/core/quic_utils.h"
16 #include "quiche/quic/platform/api/quic_logging.h"
17 #include "quiche/quic/platform/api/quic_test.h"
18 #include "quiche/quic/test_tools/mock_clock.h"
19 #include "quiche/quic/test_tools/quic_config_peer.h"
20 #include "quiche/quic/test_tools/quic_connection_peer.h"
21 #include "quiche/quic/test_tools/quic_sent_packet_manager_peer.h"
22 #include "quiche/quic/test_tools/quic_test_utils.h"
23 #include "quiche/quic/test_tools/simulator/quic_endpoint.h"
24 #include "quiche/quic/test_tools/simulator/simulator.h"
25 #include "quiche/quic/test_tools/simulator/switch.h"
26
27 namespace quic {
28 namespace test {
29 namespace {
30
31 // Use the initial CWND of 10, as 32 is too much for the test network.
32 const uint32_t kInitialCongestionWindowPackets = 10;
33
34 // Test network parameters. Here, the topology of the network is:
35 //
36 // QUIC Sender
37 // |
38 // | <-- local link
39 // |
40 // Network switch
41 // * <-- the bottleneck queue in the direction
42 // | of the receiver
43 // |
44 // | <-- test link
45 // |
46 // |
47 // Receiver
48 //
49 // When setting the bandwidth of the local link and test link, choose
50 // a bandwidth lower than 20Mbps, as the clock-granularity of the
51 // simulator can only handle a granularity of 1us.
52
53 // Default settings between the switch and the sender.
54 const QuicBandwidth kLocalLinkBandwidth =
55 QuicBandwidth::FromKBitsPerSecond(10000);
56 const QuicTime::Delta kLocalPropagationDelay =
57 QuicTime::Delta::FromMilliseconds(2);
58
59 // Wired network settings. A typical desktop network setup, a
60 // high-bandwidth, 30ms test link to the receiver.
61 const QuicBandwidth kTestLinkWiredBandwidth =
62 QuicBandwidth::FromKBitsPerSecond(4000);
63 const QuicTime::Delta kTestLinkWiredPropagationDelay =
64 QuicTime::Delta::FromMilliseconds(50);
65 const QuicTime::Delta kTestWiredTransferTime =
66 kTestLinkWiredBandwidth.TransferTime(kMaxOutgoingPacketSize) +
67 kLocalLinkBandwidth.TransferTime(kMaxOutgoingPacketSize);
68 const QuicTime::Delta kTestWiredRtt =
69 (kTestLinkWiredPropagationDelay + kLocalPropagationDelay +
70 kTestWiredTransferTime) *
71 2;
72 const QuicByteCount kTestWiredBdp = kTestWiredRtt * kTestLinkWiredBandwidth;
73
74 // Small BDP, Bandwidth-policed network settings. In this scenario,
75 // the receiver has a low-bandwidth, short propagation-delay link,
76 // resulting in a small BDP. We model the policer by setting the
77 // queue size to only one packet.
78 const QuicBandwidth kTestLinkLowBdpBandwidth =
79 QuicBandwidth::FromKBitsPerSecond(200);
80 const QuicTime::Delta kTestLinkLowBdpPropagationDelay =
81 QuicTime::Delta::FromMilliseconds(50);
82 const QuicByteCount kTestPolicerQueue = kMaxOutgoingPacketSize;
83
84 // Satellite network settings. In a satellite network, the bottleneck
85 // buffer is typically sized for non-satellite links , but the
86 // propagation delay of the test link to the receiver is as much as a
87 // quarter second.
88 const QuicTime::Delta kTestSatellitePropagationDelay =
89 QuicTime::Delta::FromMilliseconds(250);
90
91 // Cellular scenarios. In a cellular network, the bottleneck queue at
92 // the edge of the network can be as great as 3MB.
93 const QuicBandwidth kTestLink2GBandwidth =
94 QuicBandwidth::FromKBitsPerSecond(100);
95 const QuicBandwidth kTestLink3GBandwidth =
96 QuicBandwidth::FromKBitsPerSecond(1500);
97 const QuicByteCount kCellularQueue = 3 * 1024 * 1024;
98 const QuicTime::Delta kTestCellularPropagationDelay =
99 QuicTime::Delta::FromMilliseconds(40);
100
101 // Small RTT scenario, below the per-ack-update threshold of 30ms.
102 const QuicTime::Delta kTestLinkSmallRTTDelay =
103 QuicTime::Delta::FromMilliseconds(10);
104
105 struct TestParams {
TestParamsquic::test::__anon587abfa70111::TestParams106 explicit TestParams(CongestionControlType congestion_control_type)
107 : congestion_control_type(congestion_control_type) {}
108
operator <<(std::ostream & os,const TestParams & p)109 friend std::ostream& operator<<(std::ostream& os, const TestParams& p) {
110 os << "{ congestion_control_type: "
111 << CongestionControlTypeToString(p.congestion_control_type);
112 os << " }";
113 return os;
114 }
115
116 const CongestionControlType congestion_control_type;
117 };
118
TestParamToString(const testing::TestParamInfo<TestParams> & params)119 std::string TestParamToString(
120 const testing::TestParamInfo<TestParams>& params) {
121 return absl::StrCat(
122 CongestionControlTypeToString(params.param.congestion_control_type), "_");
123 }
124
125 // Constructs various test permutations.
GetTestParams()126 std::vector<TestParams> GetTestParams() {
127 std::vector<TestParams> params;
128 for (const CongestionControlType congestion_control_type :
129 {kBBR, kCubicBytes, kRenoBytes, kPCC}) {
130 params.push_back(TestParams(congestion_control_type));
131 }
132 return params;
133 }
134
135 } // namespace
136
137 class SendAlgorithmTest : public QuicTestWithParam<TestParams> {
138 protected:
SendAlgorithmTest()139 SendAlgorithmTest()
140 : simulator_(),
141 quic_sender_(&simulator_, "QUIC sender", "Receiver",
142 Perspective::IS_CLIENT, TestConnectionId()),
143 receiver_(&simulator_, "Receiver", "QUIC sender",
144 Perspective::IS_SERVER, TestConnectionId()) {
145 rtt_stats_ = quic_sender_.connection()->sent_packet_manager().GetRttStats();
146 sender_ = SendAlgorithmInterface::Create(
147 simulator_.GetClock(), rtt_stats_,
148 QuicSentPacketManagerPeer::GetUnackedPacketMap(
149 QuicConnectionPeer::GetSentPacketManager(
150 quic_sender_.connection())),
151 GetParam().congestion_control_type, &random_, &stats_,
152 kInitialCongestionWindowPackets, nullptr);
153 quic_sender_.RecordTrace();
154
155 QuicConnectionPeer::SetSendAlgorithm(quic_sender_.connection(), sender_);
156 const int kTestMaxPacketSize = 1350;
157 quic_sender_.connection()->SetMaxPacketLength(kTestMaxPacketSize);
158 clock_ = simulator_.GetClock();
159 simulator_.set_random_generator(&random_);
160
161 uint64_t seed = QuicRandom::GetInstance()->RandUint64();
162 random_.set_seed(seed);
163 QUIC_LOG(INFO) << "SendAlgorithmTest simulator set up. Seed: " << seed;
164 }
165
166 // Creates a simulated network, with default settings between the
167 // sender and the switch and the given settings from the switch to
168 // the receiver.
CreateSetup(const QuicBandwidth & test_bandwidth,const QuicTime::Delta & test_link_delay,QuicByteCount bottleneck_queue_length)169 void CreateSetup(const QuicBandwidth& test_bandwidth,
170 const QuicTime::Delta& test_link_delay,
171 QuicByteCount bottleneck_queue_length) {
172 switch_ = std::make_unique<simulator::Switch>(&simulator_, "Switch", 8,
173 bottleneck_queue_length);
174 quic_sender_link_ = std::make_unique<simulator::SymmetricLink>(
175 &quic_sender_, switch_->port(1), kLocalLinkBandwidth,
176 kLocalPropagationDelay);
177 receiver_link_ = std::make_unique<simulator::SymmetricLink>(
178 &receiver_, switch_->port(2), test_bandwidth, test_link_delay);
179 }
180
DoSimpleTransfer(QuicByteCount transfer_size,QuicTime::Delta deadline)181 void DoSimpleTransfer(QuicByteCount transfer_size, QuicTime::Delta deadline) {
182 quic_sender_.AddBytesToTransfer(transfer_size);
183 bool simulator_result = simulator_.RunUntilOrTimeout(
184 [this]() { return quic_sender_.bytes_to_transfer() == 0; }, deadline);
185 EXPECT_TRUE(simulator_result)
186 << "Simple transfer failed. Bytes remaining: "
187 << quic_sender_.bytes_to_transfer();
188 }
189
SendBursts(size_t number_of_bursts,QuicByteCount bytes,QuicTime::Delta rtt,QuicTime::Delta wait_time)190 void SendBursts(size_t number_of_bursts, QuicByteCount bytes,
191 QuicTime::Delta rtt, QuicTime::Delta wait_time) {
192 ASSERT_EQ(0u, quic_sender_.bytes_to_transfer());
193 for (size_t i = 0; i < number_of_bursts; i++) {
194 quic_sender_.AddBytesToTransfer(bytes);
195
196 // Transfer data and wait for three seconds between each transfer.
197 simulator_.RunFor(wait_time);
198
199 // Ensure the connection did not time out.
200 ASSERT_TRUE(quic_sender_.connection()->connected());
201 ASSERT_TRUE(receiver_.connection()->connected());
202 }
203
204 simulator_.RunFor(wait_time + rtt);
205 EXPECT_EQ(0u, quic_sender_.bytes_to_transfer());
206 }
207
208 // Estimates the elapsed time for a given transfer size, given the
209 // bottleneck bandwidth and link propagation delay.
EstimatedElapsedTime(QuicByteCount transfer_size_bytes,QuicBandwidth test_link_bandwidth,const QuicTime::Delta & test_link_delay) const210 QuicTime::Delta EstimatedElapsedTime(
211 QuicByteCount transfer_size_bytes, QuicBandwidth test_link_bandwidth,
212 const QuicTime::Delta& test_link_delay) const {
213 return test_link_bandwidth.TransferTime(transfer_size_bytes) +
214 2 * test_link_delay;
215 }
216
QuicSenderStartTime()217 QuicTime QuicSenderStartTime() {
218 return quic_sender_.connection()->GetStats().connection_creation_time;
219 }
220
PrintTransferStats()221 void PrintTransferStats() {
222 const QuicConnectionStats& stats = quic_sender_.connection()->GetStats();
223 QUIC_LOG(INFO) << "Summary for scenario " << GetParam();
224 QUIC_LOG(INFO) << "Sender stats is " << stats;
225 const double rtx_rate =
226 static_cast<double>(stats.bytes_retransmitted) / stats.bytes_sent;
227 QUIC_LOG(INFO) << "Retransmit rate (num_rtx/num_total_sent): " << rtx_rate;
228 QUIC_LOG(INFO) << "Connection elapsed time: "
229 << (clock_->Now() - QuicSenderStartTime()).ToMilliseconds()
230 << " (ms)";
231 }
232
233 simulator::Simulator simulator_;
234 simulator::QuicEndpoint quic_sender_;
235 simulator::QuicEndpoint receiver_;
236 std::unique_ptr<simulator::Switch> switch_;
237 std::unique_ptr<simulator::SymmetricLink> quic_sender_link_;
238 std::unique_ptr<simulator::SymmetricLink> receiver_link_;
239 QuicConnectionStats stats_;
240
241 SimpleRandom random_;
242
243 // Owned by different components of the connection.
244 const QuicClock* clock_;
245 const RttStats* rtt_stats_;
246 SendAlgorithmInterface* sender_;
247 };
248
249 INSTANTIATE_TEST_SUITE_P(SendAlgorithmTests, SendAlgorithmTest,
250 ::testing::ValuesIn(GetTestParams()),
251 TestParamToString);
252
253 // Test a simple long data transfer in the default setup.
TEST_P(SendAlgorithmTest,SimpleWiredNetworkTransfer)254 TEST_P(SendAlgorithmTest, SimpleWiredNetworkTransfer) {
255 CreateSetup(kTestLinkWiredBandwidth, kTestLinkWiredPropagationDelay,
256 kTestWiredBdp);
257 const QuicByteCount kTransferSizeBytes = 12 * 1024 * 1024;
258 const QuicTime::Delta maximum_elapsed_time =
259 EstimatedElapsedTime(kTransferSizeBytes, kTestLinkWiredBandwidth,
260 kTestLinkWiredPropagationDelay) *
261 1.2;
262 DoSimpleTransfer(kTransferSizeBytes, maximum_elapsed_time);
263 PrintTransferStats();
264 }
265
TEST_P(SendAlgorithmTest,LowBdpPolicedNetworkTransfer)266 TEST_P(SendAlgorithmTest, LowBdpPolicedNetworkTransfer) {
267 CreateSetup(kTestLinkLowBdpBandwidth, kTestLinkLowBdpPropagationDelay,
268 kTestPolicerQueue);
269 const QuicByteCount kTransferSizeBytes = 5 * 1024 * 1024;
270 const QuicTime::Delta maximum_elapsed_time =
271 EstimatedElapsedTime(kTransferSizeBytes, kTestLinkLowBdpBandwidth,
272 kTestLinkLowBdpPropagationDelay) *
273 1.2;
274 DoSimpleTransfer(kTransferSizeBytes, maximum_elapsed_time);
275 PrintTransferStats();
276 }
277
TEST_P(SendAlgorithmTest,AppLimitedBurstsOverWiredNetwork)278 TEST_P(SendAlgorithmTest, AppLimitedBurstsOverWiredNetwork) {
279 CreateSetup(kTestLinkWiredBandwidth, kTestLinkWiredPropagationDelay,
280 kTestWiredBdp);
281 const QuicByteCount kBurstSizeBytes = 512;
282 const int kNumBursts = 20;
283 const QuicTime::Delta kWaitTime = QuicTime::Delta::FromSeconds(3);
284 SendBursts(kNumBursts, kBurstSizeBytes, kTestWiredRtt, kWaitTime);
285 PrintTransferStats();
286
287 const QuicTime::Delta estimated_burst_time =
288 EstimatedElapsedTime(kBurstSizeBytes, kTestLinkWiredBandwidth,
289 kTestLinkWiredPropagationDelay) +
290 kWaitTime;
291 const QuicTime::Delta max_elapsed_time =
292 kNumBursts * estimated_burst_time + kWaitTime;
293 const QuicTime::Delta actual_elapsed_time =
294 clock_->Now() - QuicSenderStartTime();
295 EXPECT_GE(max_elapsed_time, actual_elapsed_time);
296 }
297
TEST_P(SendAlgorithmTest,SatelliteNetworkTransfer)298 TEST_P(SendAlgorithmTest, SatelliteNetworkTransfer) {
299 CreateSetup(kTestLinkWiredBandwidth, kTestSatellitePropagationDelay,
300 kTestWiredBdp);
301 const QuicByteCount kTransferSizeBytes = 12 * 1024 * 1024;
302 const QuicTime::Delta maximum_elapsed_time =
303 EstimatedElapsedTime(kTransferSizeBytes, kTestLinkWiredBandwidth,
304 kTestSatellitePropagationDelay) *
305 1.25;
306 DoSimpleTransfer(kTransferSizeBytes, maximum_elapsed_time);
307 PrintTransferStats();
308 }
309
310 TEST_P(SendAlgorithmTest, 2GNetworkTransfer) {
311 CreateSetup(kTestLink2GBandwidth, kTestCellularPropagationDelay,
312 kCellularQueue);
313 const QuicByteCount kTransferSizeBytes = 1024 * 1024;
314 const QuicTime::Delta maximum_elapsed_time =
315 EstimatedElapsedTime(kTransferSizeBytes, kTestLink2GBandwidth,
316 kTestCellularPropagationDelay) *
317 1.2;
318 DoSimpleTransfer(kTransferSizeBytes, maximum_elapsed_time);
319 PrintTransferStats();
320 }
321
322 TEST_P(SendAlgorithmTest, 3GNetworkTransfer) {
323 CreateSetup(kTestLink3GBandwidth, kTestCellularPropagationDelay,
324 kCellularQueue);
325 const QuicByteCount kTransferSizeBytes = 5 * 1024 * 1024;
326 const QuicTime::Delta maximum_elapsed_time =
327 EstimatedElapsedTime(kTransferSizeBytes, kTestLink3GBandwidth,
328 kTestCellularPropagationDelay) *
329 1.2;
330 DoSimpleTransfer(kTransferSizeBytes, maximum_elapsed_time);
331 PrintTransferStats();
332 }
333
TEST_P(SendAlgorithmTest,LowRTTTransfer)334 TEST_P(SendAlgorithmTest, LowRTTTransfer) {
335 CreateSetup(kTestLinkWiredBandwidth, kTestLinkSmallRTTDelay, kCellularQueue);
336
337 const QuicByteCount kTransferSizeBytes = 12 * 1024 * 1024;
338 const QuicTime::Delta maximum_elapsed_time =
339 EstimatedElapsedTime(kTransferSizeBytes, kTestLinkWiredBandwidth,
340 kTestLinkSmallRTTDelay) *
341 1.2;
342 DoSimpleTransfer(kTransferSizeBytes, maximum_elapsed_time);
343 PrintTransferStats();
344 }
345
346 } // namespace test
347 } // namespace quic
348