1 // Copyright (c) 2015 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 "quiche/quic/core/congestion_control/tcp_cubic_sender_bytes.h"
6 
7 #include <algorithm>
8 #include <cstdint>
9 #include <memory>
10 #include <utility>
11 
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/crypto/crypto_protocol.h"
15 #include "quiche/quic/core/quic_packets.h"
16 #include "quiche/quic/core/quic_utils.h"
17 #include "quiche/quic/platform/api/quic_logging.h"
18 #include "quiche/quic/platform/api/quic_test.h"
19 #include "quiche/quic/test_tools/mock_clock.h"
20 #include "quiche/quic/test_tools/quic_config_peer.h"
21 
22 namespace quic {
23 namespace test {
24 
25 // TODO(ianswett): A number of theses tests were written with the assumption of
26 // an initial CWND of 10. They have carefully calculated values which should be
27 // updated to be based on kInitialCongestionWindow.
28 const uint32_t kInitialCongestionWindowPackets = 10;
29 const uint32_t kMaxCongestionWindowPackets = 200;
30 const uint32_t kDefaultWindowTCP =
31     kInitialCongestionWindowPackets * kDefaultTCPMSS;
32 const float kRenoBeta = 0.7f;  // Reno backoff factor.
33 
34 class TcpCubicSenderBytesPeer : public TcpCubicSenderBytes {
35  public:
TcpCubicSenderBytesPeer(const QuicClock * clock,bool reno)36   TcpCubicSenderBytesPeer(const QuicClock* clock, bool reno)
37       : TcpCubicSenderBytes(clock, &rtt_stats_, reno,
38                             kInitialCongestionWindowPackets,
39                             kMaxCongestionWindowPackets, &stats_) {}
40 
hybrid_slow_start() const41   const HybridSlowStart& hybrid_slow_start() const {
42     return hybrid_slow_start_;
43   }
44 
GetRenoBeta() const45   float GetRenoBeta() const { return RenoBeta(); }
46 
47   RttStats rtt_stats_;
48   QuicConnectionStats stats_;
49 };
50 
51 class TcpCubicSenderBytesTest : public QuicTest {
52  protected:
TcpCubicSenderBytesTest()53   TcpCubicSenderBytesTest()
54       : one_ms_(QuicTime::Delta::FromMilliseconds(1)),
55         sender_(new TcpCubicSenderBytesPeer(&clock_, true)),
56         packet_number_(1),
57         acked_packet_number_(0),
58         bytes_in_flight_(0) {}
59 
SendAvailableSendWindow()60   int SendAvailableSendWindow() {
61     return SendAvailableSendWindow(kDefaultTCPMSS);
62   }
63 
SendAvailableSendWindow(QuicPacketLength)64   int SendAvailableSendWindow(QuicPacketLength /*packet_length*/) {
65     // Send as long as TimeUntilSend returns Zero.
66     int packets_sent = 0;
67     bool can_send = sender_->CanSend(bytes_in_flight_);
68     while (can_send) {
69       sender_->OnPacketSent(clock_.Now(), bytes_in_flight_,
70                             QuicPacketNumber(packet_number_++), kDefaultTCPMSS,
71                             HAS_RETRANSMITTABLE_DATA);
72       ++packets_sent;
73       bytes_in_flight_ += kDefaultTCPMSS;
74       can_send = sender_->CanSend(bytes_in_flight_);
75     }
76     return packets_sent;
77   }
78 
79   // Normal is that TCP acks every other segment.
AckNPackets(int n)80   void AckNPackets(int n) {
81     sender_->rtt_stats_.UpdateRtt(QuicTime::Delta::FromMilliseconds(60),
82                                   QuicTime::Delta::Zero(), clock_.Now());
83     AckedPacketVector acked_packets;
84     LostPacketVector lost_packets;
85     for (int i = 0; i < n; ++i) {
86       ++acked_packet_number_;
87       acked_packets.push_back(
88           AckedPacket(QuicPacketNumber(acked_packet_number_), kDefaultTCPMSS,
89                       QuicTime::Zero()));
90     }
91     sender_->OnCongestionEvent(true, bytes_in_flight_, clock_.Now(),
92                                acked_packets, lost_packets, 0, 0);
93     bytes_in_flight_ -= n * kDefaultTCPMSS;
94     clock_.AdvanceTime(one_ms_);
95   }
96 
LoseNPackets(int n)97   void LoseNPackets(int n) { LoseNPackets(n, kDefaultTCPMSS); }
98 
LoseNPackets(int n,QuicPacketLength packet_length)99   void LoseNPackets(int n, QuicPacketLength packet_length) {
100     AckedPacketVector acked_packets;
101     LostPacketVector lost_packets;
102     for (int i = 0; i < n; ++i) {
103       ++acked_packet_number_;
104       lost_packets.push_back(
105           LostPacket(QuicPacketNumber(acked_packet_number_), packet_length));
106     }
107     sender_->OnCongestionEvent(false, bytes_in_flight_, clock_.Now(),
108                                acked_packets, lost_packets, 0, 0);
109     bytes_in_flight_ -= n * packet_length;
110   }
111 
112   // Does not increment acked_packet_number_.
LosePacket(uint64_t packet_number)113   void LosePacket(uint64_t packet_number) {
114     AckedPacketVector acked_packets;
115     LostPacketVector lost_packets;
116     lost_packets.push_back(
117         LostPacket(QuicPacketNumber(packet_number), kDefaultTCPMSS));
118     sender_->OnCongestionEvent(false, bytes_in_flight_, clock_.Now(),
119                                acked_packets, lost_packets, 0, 0);
120     bytes_in_flight_ -= kDefaultTCPMSS;
121   }
122 
123   const QuicTime::Delta one_ms_;
124   MockClock clock_;
125   std::unique_ptr<TcpCubicSenderBytesPeer> sender_;
126   uint64_t packet_number_;
127   uint64_t acked_packet_number_;
128   QuicByteCount bytes_in_flight_;
129 };
130 
TEST_F(TcpCubicSenderBytesTest,SimpleSender)131 TEST_F(TcpCubicSenderBytesTest, SimpleSender) {
132   // At startup make sure we are at the default.
133   EXPECT_EQ(kDefaultWindowTCP, sender_->GetCongestionWindow());
134   // At startup make sure we can send.
135   EXPECT_TRUE(sender_->CanSend(0));
136   // Make sure we can send.
137   EXPECT_TRUE(sender_->CanSend(0));
138   // And that window is un-affected.
139   EXPECT_EQ(kDefaultWindowTCP, sender_->GetCongestionWindow());
140 
141   // Fill the send window with data, then verify that we can't send.
142   SendAvailableSendWindow();
143   EXPECT_FALSE(sender_->CanSend(sender_->GetCongestionWindow()));
144 }
145 
TEST_F(TcpCubicSenderBytesTest,ApplicationLimitedSlowStart)146 TEST_F(TcpCubicSenderBytesTest, ApplicationLimitedSlowStart) {
147   // Send exactly 10 packets and ensure the CWND ends at 14 packets.
148   const int kNumberOfAcks = 5;
149   // At startup make sure we can send.
150   EXPECT_TRUE(sender_->CanSend(0));
151   // Make sure we can send.
152   EXPECT_TRUE(sender_->CanSend(0));
153 
154   SendAvailableSendWindow();
155   for (int i = 0; i < kNumberOfAcks; ++i) {
156     AckNPackets(2);
157   }
158   QuicByteCount bytes_to_send = sender_->GetCongestionWindow();
159   // It's expected 2 acks will arrive when the bytes_in_flight are greater than
160   // half the CWND.
161   EXPECT_EQ(kDefaultWindowTCP + kDefaultTCPMSS * 2 * 2, bytes_to_send);
162 }
163 
TEST_F(TcpCubicSenderBytesTest,ExponentialSlowStart)164 TEST_F(TcpCubicSenderBytesTest, ExponentialSlowStart) {
165   const int kNumberOfAcks = 20;
166   // At startup make sure we can send.
167   EXPECT_TRUE(sender_->CanSend(0));
168   EXPECT_EQ(QuicBandwidth::Zero(), sender_->BandwidthEstimate());
169   // Make sure we can send.
170   EXPECT_TRUE(sender_->CanSend(0));
171 
172   for (int i = 0; i < kNumberOfAcks; ++i) {
173     // Send our full send window.
174     SendAvailableSendWindow();
175     AckNPackets(2);
176   }
177   const QuicByteCount cwnd = sender_->GetCongestionWindow();
178   EXPECT_EQ(kDefaultWindowTCP + kDefaultTCPMSS * 2 * kNumberOfAcks, cwnd);
179   EXPECT_EQ(QuicBandwidth::FromBytesAndTimeDelta(
180                 cwnd, sender_->rtt_stats_.smoothed_rtt()),
181             sender_->BandwidthEstimate());
182 }
183 
TEST_F(TcpCubicSenderBytesTest,SlowStartPacketLoss)184 TEST_F(TcpCubicSenderBytesTest, SlowStartPacketLoss) {
185   sender_->SetNumEmulatedConnections(1);
186   const int kNumberOfAcks = 10;
187   for (int i = 0; i < kNumberOfAcks; ++i) {
188     // Send our full send window.
189     SendAvailableSendWindow();
190     AckNPackets(2);
191   }
192   SendAvailableSendWindow();
193   QuicByteCount expected_send_window =
194       kDefaultWindowTCP + (kDefaultTCPMSS * 2 * kNumberOfAcks);
195   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
196 
197   // Lose a packet to exit slow start.
198   LoseNPackets(1);
199   size_t packets_in_recovery_window = expected_send_window / kDefaultTCPMSS;
200 
201   // We should now have fallen out of slow start with a reduced window.
202   expected_send_window *= kRenoBeta;
203   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
204 
205   // Recovery phase. We need to ack every packet in the recovery window before
206   // we exit recovery.
207   size_t number_of_packets_in_window = expected_send_window / kDefaultTCPMSS;
208   QUIC_DLOG(INFO) << "number_packets: " << number_of_packets_in_window;
209   AckNPackets(packets_in_recovery_window);
210   SendAvailableSendWindow();
211   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
212 
213   // We need to ack an entire window before we increase CWND by 1.
214   AckNPackets(number_of_packets_in_window - 2);
215   SendAvailableSendWindow();
216   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
217 
218   // Next ack should increase cwnd by 1.
219   AckNPackets(1);
220   expected_send_window += kDefaultTCPMSS;
221   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
222 
223   // Now RTO and ensure slow start gets reset.
224   EXPECT_TRUE(sender_->hybrid_slow_start().started());
225   sender_->OnRetransmissionTimeout(true);
226   EXPECT_FALSE(sender_->hybrid_slow_start().started());
227 }
228 
TEST_F(TcpCubicSenderBytesTest,SlowStartPacketLossWithLargeReduction)229 TEST_F(TcpCubicSenderBytesTest, SlowStartPacketLossWithLargeReduction) {
230   QuicConfig config;
231   QuicTagVector options;
232   options.push_back(kSSLR);
233   QuicConfigPeer::SetReceivedConnectionOptions(&config, options);
234   sender_->SetFromConfig(config, Perspective::IS_SERVER);
235 
236   sender_->SetNumEmulatedConnections(1);
237   const int kNumberOfAcks = (kDefaultWindowTCP / (2 * kDefaultTCPMSS)) - 1;
238   for (int i = 0; i < kNumberOfAcks; ++i) {
239     // Send our full send window.
240     SendAvailableSendWindow();
241     AckNPackets(2);
242   }
243   SendAvailableSendWindow();
244   QuicByteCount expected_send_window =
245       kDefaultWindowTCP + (kDefaultTCPMSS * 2 * kNumberOfAcks);
246   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
247 
248   // Lose a packet to exit slow start. We should now have fallen out of
249   // slow start with a window reduced by 1.
250   LoseNPackets(1);
251   expected_send_window -= kDefaultTCPMSS;
252   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
253 
254   // Lose 5 packets in recovery and verify that congestion window is reduced
255   // further.
256   LoseNPackets(5);
257   expected_send_window -= 5 * kDefaultTCPMSS;
258   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
259   // Lose another 10 packets and ensure it reduces below half the peak CWND,
260   // because we never acked the full IW.
261   LoseNPackets(10);
262   expected_send_window -= 10 * kDefaultTCPMSS;
263   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
264 
265   size_t packets_in_recovery_window = expected_send_window / kDefaultTCPMSS;
266 
267   // Recovery phase. We need to ack every packet in the recovery window before
268   // we exit recovery.
269   size_t number_of_packets_in_window = expected_send_window / kDefaultTCPMSS;
270   QUIC_DLOG(INFO) << "number_packets: " << number_of_packets_in_window;
271   AckNPackets(packets_in_recovery_window);
272   SendAvailableSendWindow();
273   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
274 
275   // We need to ack an entire window before we increase CWND by 1.
276   AckNPackets(number_of_packets_in_window - 1);
277   SendAvailableSendWindow();
278   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
279 
280   // Next ack should increase cwnd by 1.
281   AckNPackets(1);
282   expected_send_window += kDefaultTCPMSS;
283   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
284 
285   // Now RTO and ensure slow start gets reset.
286   EXPECT_TRUE(sender_->hybrid_slow_start().started());
287   sender_->OnRetransmissionTimeout(true);
288   EXPECT_FALSE(sender_->hybrid_slow_start().started());
289 }
290 
TEST_F(TcpCubicSenderBytesTest,SlowStartHalfPacketLossWithLargeReduction)291 TEST_F(TcpCubicSenderBytesTest, SlowStartHalfPacketLossWithLargeReduction) {
292   QuicConfig config;
293   QuicTagVector options;
294   options.push_back(kSSLR);
295   QuicConfigPeer::SetReceivedConnectionOptions(&config, options);
296   sender_->SetFromConfig(config, Perspective::IS_SERVER);
297 
298   sender_->SetNumEmulatedConnections(1);
299   const int kNumberOfAcks = 10;
300   for (int i = 0; i < kNumberOfAcks; ++i) {
301     // Send our full send window in half sized packets.
302     SendAvailableSendWindow(kDefaultTCPMSS / 2);
303     AckNPackets(2);
304   }
305   SendAvailableSendWindow(kDefaultTCPMSS / 2);
306   QuicByteCount expected_send_window =
307       kDefaultWindowTCP + (kDefaultTCPMSS * 2 * kNumberOfAcks);
308   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
309 
310   // Lose a packet to exit slow start. We should now have fallen out of
311   // slow start with a window reduced by 1.
312   LoseNPackets(1);
313   expected_send_window -= kDefaultTCPMSS;
314   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
315 
316   // Lose 10 packets in recovery and verify that congestion window is reduced
317   // by 5 packets.
318   LoseNPackets(10, kDefaultTCPMSS / 2);
319   expected_send_window -= 5 * kDefaultTCPMSS;
320   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
321 }
322 
TEST_F(TcpCubicSenderBytesTest,SlowStartPacketLossWithMaxHalfReduction)323 TEST_F(TcpCubicSenderBytesTest, SlowStartPacketLossWithMaxHalfReduction) {
324   QuicConfig config;
325   QuicTagVector options;
326   options.push_back(kSSLR);
327   QuicConfigPeer::SetReceivedConnectionOptions(&config, options);
328   sender_->SetFromConfig(config, Perspective::IS_SERVER);
329 
330   sender_->SetNumEmulatedConnections(1);
331   const int kNumberOfAcks = kInitialCongestionWindowPackets / 2;
332   for (int i = 0; i < kNumberOfAcks; ++i) {
333     // Send our full send window.
334     SendAvailableSendWindow();
335     AckNPackets(2);
336   }
337   SendAvailableSendWindow();
338   QuicByteCount expected_send_window =
339       kDefaultWindowTCP + (kDefaultTCPMSS * 2 * kNumberOfAcks);
340   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
341 
342   // Lose a packet to exit slow start. We should now have fallen out of
343   // slow start with a window reduced by 1.
344   LoseNPackets(1);
345   expected_send_window -= kDefaultTCPMSS;
346   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
347 
348   // Lose half the outstanding packets in recovery and verify the congestion
349   // window is only reduced by a max of half.
350   LoseNPackets(kNumberOfAcks * 2);
351   expected_send_window -= (kNumberOfAcks * 2 - 1) * kDefaultTCPMSS;
352   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
353   LoseNPackets(5);
354   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
355 }
356 
TEST_F(TcpCubicSenderBytesTest,NoPRRWhenLessThanOnePacketInFlight)357 TEST_F(TcpCubicSenderBytesTest, NoPRRWhenLessThanOnePacketInFlight) {
358   SendAvailableSendWindow();
359   LoseNPackets(kInitialCongestionWindowPackets - 1);
360   AckNPackets(1);
361   // PRR will allow 2 packets for every ack during recovery.
362   EXPECT_EQ(2, SendAvailableSendWindow());
363   // Simulate abandoning all packets by supplying a bytes_in_flight of 0.
364   // PRR should now allow a packet to be sent, even though prr's state variables
365   // believe it has sent enough packets.
366   EXPECT_TRUE(sender_->CanSend(0));
367 }
368 
TEST_F(TcpCubicSenderBytesTest,SlowStartPacketLossPRR)369 TEST_F(TcpCubicSenderBytesTest, SlowStartPacketLossPRR) {
370   sender_->SetNumEmulatedConnections(1);
371   // Test based on the first example in RFC6937.
372   // Ack 10 packets in 5 acks to raise the CWND to 20, as in the example.
373   const int kNumberOfAcks = 5;
374   for (int i = 0; i < kNumberOfAcks; ++i) {
375     // Send our full send window.
376     SendAvailableSendWindow();
377     AckNPackets(2);
378   }
379   SendAvailableSendWindow();
380   QuicByteCount expected_send_window =
381       kDefaultWindowTCP + (kDefaultTCPMSS * 2 * kNumberOfAcks);
382   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
383 
384   LoseNPackets(1);
385 
386   // We should now have fallen out of slow start with a reduced window.
387   size_t send_window_before_loss = expected_send_window;
388   expected_send_window *= kRenoBeta;
389   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
390 
391   // Testing TCP proportional rate reduction.
392   // We should send packets paced over the received acks for the remaining
393   // outstanding packets. The number of packets before we exit recovery is the
394   // original CWND minus the packet that has been lost and the one which
395   // triggered the loss.
396   size_t remaining_packets_in_recovery =
397       send_window_before_loss / kDefaultTCPMSS - 2;
398 
399   for (size_t i = 0; i < remaining_packets_in_recovery; ++i) {
400     AckNPackets(1);
401     SendAvailableSendWindow();
402     EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
403   }
404 
405   // We need to ack another window before we increase CWND by 1.
406   size_t number_of_packets_in_window = expected_send_window / kDefaultTCPMSS;
407   for (size_t i = 0; i < number_of_packets_in_window; ++i) {
408     AckNPackets(1);
409     EXPECT_EQ(1, SendAvailableSendWindow());
410     EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
411   }
412 
413   AckNPackets(1);
414   expected_send_window += kDefaultTCPMSS;
415   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
416 }
417 
TEST_F(TcpCubicSenderBytesTest,SlowStartBurstPacketLossPRR)418 TEST_F(TcpCubicSenderBytesTest, SlowStartBurstPacketLossPRR) {
419   sender_->SetNumEmulatedConnections(1);
420   // Test based on the second example in RFC6937, though we also implement
421   // forward acknowledgements, so the first two incoming acks will trigger
422   // PRR immediately.
423   // Ack 20 packets in 10 acks to raise the CWND to 30.
424   const int kNumberOfAcks = 10;
425   for (int i = 0; i < kNumberOfAcks; ++i) {
426     // Send our full send window.
427     SendAvailableSendWindow();
428     AckNPackets(2);
429   }
430   SendAvailableSendWindow();
431   QuicByteCount expected_send_window =
432       kDefaultWindowTCP + (kDefaultTCPMSS * 2 * kNumberOfAcks);
433   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
434 
435   // Lose one more than the congestion window reduction, so that after loss,
436   // bytes_in_flight is lesser than the congestion window.
437   size_t send_window_after_loss = kRenoBeta * expected_send_window;
438   size_t num_packets_to_lose =
439       (expected_send_window - send_window_after_loss) / kDefaultTCPMSS + 1;
440   LoseNPackets(num_packets_to_lose);
441   // Immediately after the loss, ensure at least one packet can be sent.
442   // Losses without subsequent acks can occur with timer based loss detection.
443   EXPECT_TRUE(sender_->CanSend(bytes_in_flight_));
444   AckNPackets(1);
445 
446   // We should now have fallen out of slow start with a reduced window.
447   expected_send_window *= kRenoBeta;
448   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
449 
450   // Only 2 packets should be allowed to be sent, per PRR-SSRB.
451   EXPECT_EQ(2, SendAvailableSendWindow());
452 
453   // Ack the next packet, which triggers another loss.
454   LoseNPackets(1);
455   AckNPackets(1);
456 
457   // Send 2 packets to simulate PRR-SSRB.
458   EXPECT_EQ(2, SendAvailableSendWindow());
459 
460   // Ack the next packet, which triggers another loss.
461   LoseNPackets(1);
462   AckNPackets(1);
463 
464   // Send 2 packets to simulate PRR-SSRB.
465   EXPECT_EQ(2, SendAvailableSendWindow());
466 
467   // Exit recovery and return to sending at the new rate.
468   for (int i = 0; i < kNumberOfAcks; ++i) {
469     AckNPackets(1);
470     EXPECT_EQ(1, SendAvailableSendWindow());
471   }
472 }
473 
TEST_F(TcpCubicSenderBytesTest,RTOCongestionWindow)474 TEST_F(TcpCubicSenderBytesTest, RTOCongestionWindow) {
475   EXPECT_EQ(kDefaultWindowTCP, sender_->GetCongestionWindow());
476   // Expect the window to decrease to the minimum once the RTO fires and slow
477   // start threshold to be set to 1/2 of the CWND.
478   sender_->OnRetransmissionTimeout(true);
479   EXPECT_EQ(2 * kDefaultTCPMSS, sender_->GetCongestionWindow());
480   EXPECT_EQ(5u * kDefaultTCPMSS, sender_->GetSlowStartThreshold());
481 }
482 
TEST_F(TcpCubicSenderBytesTest,RTOCongestionWindowNoRetransmission)483 TEST_F(TcpCubicSenderBytesTest, RTOCongestionWindowNoRetransmission) {
484   EXPECT_EQ(kDefaultWindowTCP, sender_->GetCongestionWindow());
485 
486   // Expect the window to remain unchanged if the RTO fires but no packets are
487   // retransmitted.
488   sender_->OnRetransmissionTimeout(false);
489   EXPECT_EQ(kDefaultWindowTCP, sender_->GetCongestionWindow());
490 }
491 
TEST_F(TcpCubicSenderBytesTest,TcpCubicResetEpochOnQuiescence)492 TEST_F(TcpCubicSenderBytesTest, TcpCubicResetEpochOnQuiescence) {
493   const int kMaxCongestionWindow = 50;
494   const QuicByteCount kMaxCongestionWindowBytes =
495       kMaxCongestionWindow * kDefaultTCPMSS;
496   int num_sent = SendAvailableSendWindow();
497 
498   // Make sure we fall out of slow start.
499   QuicByteCount saved_cwnd = sender_->GetCongestionWindow();
500   LoseNPackets(1);
501   EXPECT_GT(saved_cwnd, sender_->GetCongestionWindow());
502 
503   // Ack the rest of the outstanding packets to get out of recovery.
504   for (int i = 1; i < num_sent; ++i) {
505     AckNPackets(1);
506   }
507   EXPECT_EQ(0u, bytes_in_flight_);
508 
509   // Send a new window of data and ack all; cubic growth should occur.
510   saved_cwnd = sender_->GetCongestionWindow();
511   num_sent = SendAvailableSendWindow();
512   for (int i = 0; i < num_sent; ++i) {
513     AckNPackets(1);
514   }
515   EXPECT_LT(saved_cwnd, sender_->GetCongestionWindow());
516   EXPECT_GT(kMaxCongestionWindowBytes, sender_->GetCongestionWindow());
517   EXPECT_EQ(0u, bytes_in_flight_);
518 
519   // Quiescent time of 100 seconds
520   clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(100000));
521 
522   // Send new window of data and ack one packet. Cubic epoch should have
523   // been reset; ensure cwnd increase is not dramatic.
524   saved_cwnd = sender_->GetCongestionWindow();
525   SendAvailableSendWindow();
526   AckNPackets(1);
527   EXPECT_NEAR(saved_cwnd, sender_->GetCongestionWindow(), kDefaultTCPMSS);
528   EXPECT_GT(kMaxCongestionWindowBytes, sender_->GetCongestionWindow());
529 }
530 
TEST_F(TcpCubicSenderBytesTest,MultipleLossesInOneWindow)531 TEST_F(TcpCubicSenderBytesTest, MultipleLossesInOneWindow) {
532   SendAvailableSendWindow();
533   const QuicByteCount initial_window = sender_->GetCongestionWindow();
534   LosePacket(acked_packet_number_ + 1);
535   const QuicByteCount post_loss_window = sender_->GetCongestionWindow();
536   EXPECT_GT(initial_window, post_loss_window);
537   LosePacket(acked_packet_number_ + 3);
538   EXPECT_EQ(post_loss_window, sender_->GetCongestionWindow());
539   LosePacket(packet_number_ - 1);
540   EXPECT_EQ(post_loss_window, sender_->GetCongestionWindow());
541 
542   // Lose a later packet and ensure the window decreases.
543   LosePacket(packet_number_);
544   EXPECT_GT(post_loss_window, sender_->GetCongestionWindow());
545 }
546 
TEST_F(TcpCubicSenderBytesTest,ConfigureMaxInitialWindow)547 TEST_F(TcpCubicSenderBytesTest, ConfigureMaxInitialWindow) {
548   QuicConfig config;
549 
550   // Verify that kCOPT: kIW10 forces the congestion window to the default of 10.
551   QuicTagVector options;
552   options.push_back(kIW10);
553   QuicConfigPeer::SetReceivedConnectionOptions(&config, options);
554   sender_->SetFromConfig(config, Perspective::IS_SERVER);
555   EXPECT_EQ(10u * kDefaultTCPMSS, sender_->GetCongestionWindow());
556 }
557 
TEST_F(TcpCubicSenderBytesTest,SetInitialCongestionWindow)558 TEST_F(TcpCubicSenderBytesTest, SetInitialCongestionWindow) {
559   EXPECT_NE(3u * kDefaultTCPMSS, sender_->GetCongestionWindow());
560   sender_->SetInitialCongestionWindowInPackets(3);
561   EXPECT_EQ(3u * kDefaultTCPMSS, sender_->GetCongestionWindow());
562 }
563 
564 TEST_F(TcpCubicSenderBytesTest, 2ConnectionCongestionAvoidanceAtEndOfRecovery) {
565   sender_->SetNumEmulatedConnections(2);
566   // Ack 10 packets in 5 acks to raise the CWND to 20.
567   const int kNumberOfAcks = 5;
568   for (int i = 0; i < kNumberOfAcks; ++i) {
569     // Send our full send window.
570     SendAvailableSendWindow();
571     AckNPackets(2);
572   }
573   SendAvailableSendWindow();
574   QuicByteCount expected_send_window =
575       kDefaultWindowTCP + (kDefaultTCPMSS * 2 * kNumberOfAcks);
576   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
577 
578   LoseNPackets(1);
579 
580   // We should now have fallen out of slow start with a reduced window.
581   expected_send_window = expected_send_window * sender_->GetRenoBeta();
582   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
583 
584   // No congestion window growth should occur in recovery phase, i.e., until the
585   // currently outstanding 20 packets are acked.
586   for (int i = 0; i < 10; ++i) {
587     // Send our full send window.
588     SendAvailableSendWindow();
589     EXPECT_TRUE(sender_->InRecovery());
590     AckNPackets(2);
591     EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
592   }
593   EXPECT_FALSE(sender_->InRecovery());
594 
595   // Out of recovery now. Congestion window should not grow for half an RTT.
596   size_t packets_in_send_window = expected_send_window / kDefaultTCPMSS;
597   SendAvailableSendWindow();
598   AckNPackets(packets_in_send_window / 2 - 2);
599   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
600 
601   // Next ack should increase congestion window by 1MSS.
602   SendAvailableSendWindow();
603   AckNPackets(2);
604   expected_send_window += kDefaultTCPMSS;
605   packets_in_send_window += 1;
606   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
607 
608   // Congestion window should remain steady again for half an RTT.
609   SendAvailableSendWindow();
610   AckNPackets(packets_in_send_window / 2 - 1);
611   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
612 
613   // Next ack should cause congestion window to grow by 1MSS.
614   SendAvailableSendWindow();
615   AckNPackets(2);
616   expected_send_window += kDefaultTCPMSS;
617   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
618 }
619 
620 TEST_F(TcpCubicSenderBytesTest, 1ConnectionCongestionAvoidanceAtEndOfRecovery) {
621   sender_->SetNumEmulatedConnections(1);
622   // Ack 10 packets in 5 acks to raise the CWND to 20.
623   const int kNumberOfAcks = 5;
624   for (int i = 0; i < kNumberOfAcks; ++i) {
625     // Send our full send window.
626     SendAvailableSendWindow();
627     AckNPackets(2);
628   }
629   SendAvailableSendWindow();
630   QuicByteCount expected_send_window =
631       kDefaultWindowTCP + (kDefaultTCPMSS * 2 * kNumberOfAcks);
632   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
633 
634   LoseNPackets(1);
635 
636   // We should now have fallen out of slow start with a reduced window.
637   expected_send_window *= kRenoBeta;
638   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
639 
640   // No congestion window growth should occur in recovery phase, i.e., until the
641   // currently outstanding 20 packets are acked.
642   for (int i = 0; i < 10; ++i) {
643     // Send our full send window.
644     SendAvailableSendWindow();
645     EXPECT_TRUE(sender_->InRecovery());
646     AckNPackets(2);
647     EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
648   }
649   EXPECT_FALSE(sender_->InRecovery());
650 
651   // Out of recovery now. Congestion window should not grow during RTT.
652   for (uint64_t i = 0; i < expected_send_window / kDefaultTCPMSS - 2; i += 2) {
653     // Send our full send window.
654     SendAvailableSendWindow();
655     AckNPackets(2);
656     EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
657   }
658 
659   // Next ack should cause congestion window to grow by 1MSS.
660   SendAvailableSendWindow();
661   AckNPackets(2);
662   expected_send_window += kDefaultTCPMSS;
663   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
664 }
665 
TEST_F(TcpCubicSenderBytesTest,BandwidthResumption)666 TEST_F(TcpCubicSenderBytesTest, BandwidthResumption) {
667   // Test that when provided with CachedNetworkParameters and opted in to the
668   // bandwidth resumption experiment, that the TcpCubicSenderPackets sets
669   // initial CWND appropriately.
670 
671   // Set some common values.
672   const QuicPacketCount kNumberOfPackets = 123;
673   const QuicBandwidth kBandwidthEstimate =
674       QuicBandwidth::FromBytesPerSecond(kNumberOfPackets * kDefaultTCPMSS);
675   const QuicTime::Delta kRttEstimate = QuicTime::Delta::FromSeconds(1);
676 
677   SendAlgorithmInterface::NetworkParams network_param;
678   network_param.bandwidth = kBandwidthEstimate;
679   network_param.rtt = kRttEstimate;
680   sender_->AdjustNetworkParameters(network_param);
681   EXPECT_EQ(kNumberOfPackets * kDefaultTCPMSS, sender_->GetCongestionWindow());
682 
683   // Resume with an illegal value of 0 and verify the server ignores it.
684   SendAlgorithmInterface::NetworkParams network_param_no_bandwidth;
685   network_param_no_bandwidth.bandwidth = QuicBandwidth::Zero();
686   network_param_no_bandwidth.rtt = kRttEstimate;
687   sender_->AdjustNetworkParameters(network_param_no_bandwidth);
688   EXPECT_EQ(kNumberOfPackets * kDefaultTCPMSS, sender_->GetCongestionWindow());
689 
690   // Resumed CWND is limited to be in a sensible range.
691   const QuicBandwidth kUnreasonableBandwidth =
692       QuicBandwidth::FromBytesPerSecond((kMaxResumptionCongestionWindow + 1) *
693                                         kDefaultTCPMSS);
694   SendAlgorithmInterface::NetworkParams network_param_large_bandwidth;
695   network_param_large_bandwidth.bandwidth = kUnreasonableBandwidth;
696   network_param_large_bandwidth.rtt = QuicTime::Delta::FromSeconds(1);
697   sender_->AdjustNetworkParameters(network_param_large_bandwidth);
698   EXPECT_EQ(kMaxResumptionCongestionWindow * kDefaultTCPMSS,
699             sender_->GetCongestionWindow());
700 }
701 
TEST_F(TcpCubicSenderBytesTest,PaceBelowCWND)702 TEST_F(TcpCubicSenderBytesTest, PaceBelowCWND) {
703   QuicConfig config;
704 
705   // Verify that kCOPT: kMIN4 forces the min CWND to 1 packet, but allows up
706   // to 4 to be sent.
707   QuicTagVector options;
708   options.push_back(kMIN4);
709   QuicConfigPeer::SetReceivedConnectionOptions(&config, options);
710   sender_->SetFromConfig(config, Perspective::IS_SERVER);
711   sender_->OnRetransmissionTimeout(true);
712   EXPECT_EQ(kDefaultTCPMSS, sender_->GetCongestionWindow());
713   EXPECT_TRUE(sender_->CanSend(kDefaultTCPMSS));
714   EXPECT_TRUE(sender_->CanSend(2 * kDefaultTCPMSS));
715   EXPECT_TRUE(sender_->CanSend(3 * kDefaultTCPMSS));
716   EXPECT_FALSE(sender_->CanSend(4 * kDefaultTCPMSS));
717 }
718 
TEST_F(TcpCubicSenderBytesTest,NoPRR)719 TEST_F(TcpCubicSenderBytesTest, NoPRR) {
720   QuicTime::Delta rtt = QuicTime::Delta::FromMilliseconds(100);
721   sender_->rtt_stats_.UpdateRtt(rtt, QuicTime::Delta::Zero(), QuicTime::Zero());
722 
723   sender_->SetNumEmulatedConnections(1);
724   // Verify that kCOPT: kNPRR allows all packets to be sent, even if only one
725   // ack has been received.
726   QuicTagVector options;
727   options.push_back(kNPRR);
728   QuicConfig config;
729   QuicConfigPeer::SetReceivedConnectionOptions(&config, options);
730   sender_->SetFromConfig(config, Perspective::IS_SERVER);
731   SendAvailableSendWindow();
732   LoseNPackets(9);
733   AckNPackets(1);
734 
735   // We should now have fallen out of slow start with a reduced window.
736   EXPECT_EQ(kRenoBeta * kDefaultWindowTCP, sender_->GetCongestionWindow());
737   const QuicPacketCount window_in_packets =
738       kRenoBeta * kDefaultWindowTCP / kDefaultTCPMSS;
739   const QuicBandwidth expected_pacing_rate =
740       QuicBandwidth::FromBytesAndTimeDelta(kRenoBeta * kDefaultWindowTCP,
741                                            sender_->rtt_stats_.smoothed_rtt());
742   EXPECT_EQ(expected_pacing_rate, sender_->PacingRate(0));
743   EXPECT_EQ(window_in_packets,
744             static_cast<uint64_t>(SendAvailableSendWindow()));
745   EXPECT_EQ(expected_pacing_rate,
746             sender_->PacingRate(kRenoBeta * kDefaultWindowTCP));
747 }
748 
TEST_F(TcpCubicSenderBytesTest,ResetAfterConnectionMigration)749 TEST_F(TcpCubicSenderBytesTest, ResetAfterConnectionMigration) {
750   // Starts from slow start.
751   sender_->SetNumEmulatedConnections(1);
752   const int kNumberOfAcks = 10;
753   for (int i = 0; i < kNumberOfAcks; ++i) {
754     // Send our full send window.
755     SendAvailableSendWindow();
756     AckNPackets(2);
757   }
758   SendAvailableSendWindow();
759   QuicByteCount expected_send_window =
760       kDefaultWindowTCP + (kDefaultTCPMSS * 2 * kNumberOfAcks);
761   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
762 
763   // Loses a packet to exit slow start.
764   LoseNPackets(1);
765 
766   // We should now have fallen out of slow start with a reduced window. Slow
767   // start threshold is also updated.
768   expected_send_window *= kRenoBeta;
769   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
770   EXPECT_EQ(expected_send_window, sender_->GetSlowStartThreshold());
771 
772   // Resets cwnd and slow start threshold on connection migrations.
773   sender_->OnConnectionMigration();
774   EXPECT_EQ(kDefaultWindowTCP, sender_->GetCongestionWindow());
775   EXPECT_EQ(kMaxCongestionWindowPackets * kDefaultTCPMSS,
776             sender_->GetSlowStartThreshold());
777   EXPECT_FALSE(sender_->hybrid_slow_start().started());
778 }
779 
TEST_F(TcpCubicSenderBytesTest,DefaultMaxCwnd)780 TEST_F(TcpCubicSenderBytesTest, DefaultMaxCwnd) {
781   RttStats rtt_stats;
782   QuicConnectionStats stats;
783   std::unique_ptr<SendAlgorithmInterface> sender(SendAlgorithmInterface::Create(
784       &clock_, &rtt_stats, /*unacked_packets=*/nullptr, kCubicBytes,
785       QuicRandom::GetInstance(), &stats, kInitialCongestionWindow, nullptr));
786 
787   AckedPacketVector acked_packets;
788   LostPacketVector missing_packets;
789   QuicPacketCount max_congestion_window =
790       GetQuicFlag(quic_max_congestion_window);
791   for (uint64_t i = 1; i < max_congestion_window; ++i) {
792     acked_packets.clear();
793     acked_packets.push_back(
794         AckedPacket(QuicPacketNumber(i), 1350, QuicTime::Zero()));
795     sender->OnCongestionEvent(true, sender->GetCongestionWindow(), clock_.Now(),
796                               acked_packets, missing_packets, 0, 0);
797   }
798   EXPECT_EQ(max_congestion_window,
799             sender->GetCongestionWindow() / kDefaultTCPMSS);
800 }
801 
TEST_F(TcpCubicSenderBytesTest,LimitCwndIncreaseInCongestionAvoidance)802 TEST_F(TcpCubicSenderBytesTest, LimitCwndIncreaseInCongestionAvoidance) {
803   // Enable Cubic.
804   sender_ = std::make_unique<TcpCubicSenderBytesPeer>(&clock_, false);
805 
806   int num_sent = SendAvailableSendWindow();
807 
808   // Make sure we fall out of slow start.
809   QuicByteCount saved_cwnd = sender_->GetCongestionWindow();
810   LoseNPackets(1);
811   EXPECT_GT(saved_cwnd, sender_->GetCongestionWindow());
812 
813   // Ack the rest of the outstanding packets to get out of recovery.
814   for (int i = 1; i < num_sent; ++i) {
815     AckNPackets(1);
816   }
817   EXPECT_EQ(0u, bytes_in_flight_);
818   // Send a new window of data and ack all; cubic growth should occur.
819   saved_cwnd = sender_->GetCongestionWindow();
820   num_sent = SendAvailableSendWindow();
821 
822   // Ack packets until the CWND increases.
823   while (sender_->GetCongestionWindow() == saved_cwnd) {
824     AckNPackets(1);
825     SendAvailableSendWindow();
826   }
827   // Bytes in flight may be larger than the CWND if the CWND isn't an exact
828   // multiple of the packet sizes being sent.
829   EXPECT_GE(bytes_in_flight_, sender_->GetCongestionWindow());
830   saved_cwnd = sender_->GetCongestionWindow();
831 
832   // Advance time 2 seconds waiting for an ack.
833   clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(2000));
834 
835   // Ack two packets.  The CWND should increase by only one packet.
836   AckNPackets(2);
837   EXPECT_EQ(saved_cwnd + kDefaultTCPMSS, sender_->GetCongestionWindow());
838 }
839 
840 }  // namespace test
841 }  // namespace quic
842