net/quic/congestion_control/tcp_cubic_sender_test.cc

   1 // Copyright (c) 2012 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/memory/scoped_ptr.h"
   9 #include "net/quic/congestion_control/tcp_cubic_sender.h"
  10 #include "net/quic/congestion_control/tcp_receiver.h"
  11 #include "net/quic/test_tools/mock_clock.h"
  12 #include "testing/gtest/include/gtest/gtest.h"
  13
  14 using std::min;
  15
  16 namespace net {
  17 namespace test {
  18
  19 const uint32 kDefaultWindowTCP = 10 * kDefaultTCPMSS;
  20
  21 // TODO(ianswett): Remove 10000 once b/10075719 is fixed.
  22 const QuicTcpCongestionWindow kDefaultMaxCongestionWindowTCP = 10000;
  23
  24 class TcpCubicSenderPeer : public TcpCubicSender {
  25  public:
  26   TcpCubicSenderPeer(const QuicClock* clock,
  27                      bool reno,
  28                      QuicTcpCongestionWindow max_tcp_congestion_window)
  29       : TcpCubicSender(clock, reno, max_tcp_congestion_window) {
  30   }
  31
  32   QuicTcpCongestionWindow congestion_window() {
  33     return congestion_window_;
  34   }
  35
  36   using TcpCubicSender::AvailableSendWindow;
  37   using TcpCubicSender::SendWindow;
  38 };
  39
  40 class TcpCubicSenderTest : public ::testing::Test {
  41  protected:
  42   TcpCubicSenderTest()
  43       : one_ms_(QuicTime::Delta::FromMilliseconds(1)),
  44         sender_(new TcpCubicSenderPeer(&clock_, true,
  45                                        kDefaultMaxCongestionWindowTCP)),
  46         receiver_(new TcpReceiver()),
  47         sequence_number_(1),
  48         acked_sequence_number_(0) {
  49   }
  50
  51   void SendAvailableSendWindow() {
  52     QuicByteCount bytes_to_send = sender_->AvailableSendWindow();
  53     while (bytes_to_send > 0) {
  54       QuicByteCount bytes_in_packet = min(kDefaultTCPMSS, bytes_to_send);
  55       sender_->OnPacketSent(clock_.Now(), sequence_number_++, bytes_in_packet,
  56                             NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA);
  57       bytes_to_send -= bytes_in_packet;
  58       if (bytes_to_send > 0) {
  59         EXPECT_TRUE(sender_->TimeUntilSend(clock_.Now(), NOT_RETRANSMISSION,
  60                         HAS_RETRANSMITTABLE_DATA, NOT_HANDSHAKE).IsZero());
  61       }
  62     }
  63   }
  64   // Normal is that TCP acks every other segment.
  65   void AckNPackets(int n) {
  66     for (int i = 0; i < n; ++i) {
  67       acked_sequence_number_++;
  68       sender_->UpdateRtt(QuicTime::Delta::FromMilliseconds(60));
  69       sender_->OnPacketAcked(acked_sequence_number_, kDefaultTCPMSS);
  70     }
  71     clock_.AdvanceTime(one_ms_);  // 1 millisecond.
  72   }
  73
  74   const QuicTime::Delta one_ms_;
  75   MockClock clock_;
  76   SendAlgorithmInterface::SentPacketsMap not_used_;
  77   scoped_ptr<TcpCubicSenderPeer> sender_;
  78   scoped_ptr<TcpReceiver> receiver_;
  79   QuicPacketSequenceNumber sequence_number_;
  80   QuicPacketSequenceNumber acked_sequence_number_;
  81 };
  82
  83 TEST_F(TcpCubicSenderTest, SimpleSender) {
  84   QuicCongestionFeedbackFrame feedback;
  85   // At startup make sure we are at the default.
  86   EXPECT_EQ(kDefaultWindowTCP, sender_->AvailableSendWindow());
  87   EXPECT_EQ(kDefaultWindowTCP, sender_->GetCongestionWindow());
  88   // At startup make sure we can send.
  89   EXPECT_TRUE(sender_->TimeUntilSend(clock_.Now(),
  90       NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA, NOT_HANDSHAKE).IsZero());
  91   // Get default QuicCongestionFeedbackFrame from receiver.
  92   ASSERT_TRUE(receiver_->GenerateCongestionFeedback(&feedback));
  93   sender_->OnIncomingQuicCongestionFeedbackFrame(feedback, clock_.Now(),
  94                                                  not_used_);
  95   // Make sure we can send.
  96   EXPECT_TRUE(sender_->TimeUntilSend(clock_.Now(),
  97       NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA, NOT_HANDSHAKE).IsZero());
  98   // And that window is un-affected.
  99   EXPECT_EQ(kDefaultWindowTCP, sender_->AvailableSendWindow());
 100   EXPECT_EQ(kDefaultWindowTCP, sender_->GetCongestionWindow());
 101
 102   // A retransmit should always return 0.
 103   EXPECT_TRUE(sender_->TimeUntilSend(clock_.Now(),
 104       NACK_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA, NOT_HANDSHAKE).IsZero());
 105 }
 106
 107 TEST_F(TcpCubicSenderTest, ExponentialSlowStart) {
 108   const int kNumberOfAck = 20;
 109   QuicCongestionFeedbackFrame feedback;
 110   // At startup make sure we can send.
 111   EXPECT_TRUE(sender_->TimeUntilSend(clock_.Now(),
 112       NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA, NOT_HANDSHAKE).IsZero());
 113   // Get default QuicCongestionFeedbackFrame from receiver.
 114   ASSERT_TRUE(receiver_->GenerateCongestionFeedback(&feedback));
 115   sender_->OnIncomingQuicCongestionFeedbackFrame(feedback, clock_.Now(),
 116                                                  not_used_);
 117   // Make sure we can send.
 118   EXPECT_TRUE(sender_->TimeUntilSend(clock_.Now(),
 119       NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA, NOT_HANDSHAKE).IsZero());
 120
 121   for (int n = 0; n < kNumberOfAck; ++n) {
 122     // Send our full send window.
 123     SendAvailableSendWindow();
 124     AckNPackets(2);
 125   }
 126   QuicByteCount bytes_to_send = sender_->SendWindow();
 127   EXPECT_EQ(kDefaultWindowTCP + kDefaultTCPMSS * 2 * kNumberOfAck,
 128             bytes_to_send);
 129 }
 130
 131 TEST_F(TcpCubicSenderTest, SlowStartAckTrain) {
 132   // Make sure that we fall out of slow start when we send ACK train longer
 133   // than half the RTT, in this test case 30ms, which is more than 30 calls to
 134   // Ack2Packets in one round.
 135   // Since we start at 10 packet first round will be 5 second round 10 etc
 136   // Hence we should pass 30 at 65 = 5 + 10 + 20 + 30
 137   const int kNumberOfAck = 65;
 138   QuicCongestionFeedbackFrame feedback;
 139   // At startup make sure we can send.
 140   EXPECT_TRUE(sender_->TimeUntilSend(clock_.Now(),
 141       NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA, NOT_HANDSHAKE).IsZero());
 142   // Get default QuicCongestionFeedbackFrame from receiver.
 143   ASSERT_TRUE(receiver_->GenerateCongestionFeedback(&feedback));
 144   sender_->OnIncomingQuicCongestionFeedbackFrame(feedback, clock_.Now(),
 145                                                  not_used_);
 146   // Make sure we can send.
 147   EXPECT_TRUE(sender_->TimeUntilSend(clock_.Now(),
 148       NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA, NOT_HANDSHAKE).IsZero());
 149
 150   for (int n = 0; n < kNumberOfAck; ++n) {
 151     // Send our full send window.
 152     SendAvailableSendWindow();
 153     AckNPackets(2);
 154   }
 155   QuicByteCount expected_send_window =
 156       kDefaultWindowTCP + (kDefaultTCPMSS * 2 * kNumberOfAck);
 157   EXPECT_EQ(expected_send_window, sender_->SendWindow());
 158   EXPECT_EQ(expected_send_window, sender_->GetCongestionWindow());
 159
 160   // We should now have fallen out of slow start.
 161   // Testing Reno phase.
 162   // We should need 141(65*2+1+10) ACK:ed packets before increasing window by
 163   // one.
 164   for (int m = 0; m < 70; ++m) {
 165     SendAvailableSendWindow();
 166     AckNPackets(2);
 167     EXPECT_EQ(expected_send_window, sender_->SendWindow());
 168   }
 169   SendAvailableSendWindow();
 170   AckNPackets(2);
 171   expected_send_window += kDefaultTCPMSS;
 172   EXPECT_EQ(expected_send_window, sender_->SendWindow());
 173 }
 174
 175 TEST_F(TcpCubicSenderTest, SlowStartPacketLoss) {
 176   // Make sure that we fall out of slow start when we encounter a packet loss.
 177   const int kNumberOfAck = 10;
 178   QuicCongestionFeedbackFrame feedback;
 179   // At startup make sure we can send.
 180   EXPECT_TRUE(sender_->TimeUntilSend(clock_.Now(),
 181       NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA, NOT_HANDSHAKE).IsZero());
 182   // Get default QuicCongestionFeedbackFrame from receiver.
 183   ASSERT_TRUE(receiver_->GenerateCongestionFeedback(&feedback));
 184   sender_->OnIncomingQuicCongestionFeedbackFrame(feedback, clock_.Now(),
 185                                                  not_used_);
 186   // Make sure we can send.
 187   EXPECT_TRUE(sender_->TimeUntilSend(clock_.Now(),
 188       NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA, NOT_HANDSHAKE).IsZero());
 189
 190   for (int i = 0; i < kNumberOfAck; ++i) {
 191     // Send our full send window.
 192     SendAvailableSendWindow();
 193     AckNPackets(2);
 194   }
 195   SendAvailableSendWindow();
 196   QuicByteCount expected_send_window = kDefaultWindowTCP +
 197       (kDefaultTCPMSS * 2 * kNumberOfAck);
 198   EXPECT_EQ(expected_send_window, sender_->SendWindow());
 199
 200   sender_->OnPacketLost(acked_sequence_number_ + 1, clock_.Now());
 201
 202   // Make sure that we should not send right now.
 203   EXPECT_TRUE(sender_->TimeUntilSend(clock_.Now(), NOT_RETRANSMISSION,
 204       HAS_RETRANSMITTABLE_DATA, NOT_HANDSHAKE).IsInfinite());
 205
 206   // We should now have fallen out of slow start.
 207   // We expect window to be cut in half.
 208   expected_send_window /= 2;
 209   EXPECT_EQ(expected_send_window, sender_->SendWindow());
 210
 211   // Testing Reno phase.
 212   // We need to ack half of the pending packet before we can send again.
 213   int number_of_packets_in_window = expected_send_window / kDefaultTCPMSS;
 214   AckNPackets(number_of_packets_in_window);
 215   EXPECT_EQ(expected_send_window, sender_->SendWindow());
 216   EXPECT_EQ(0u, sender_->AvailableSendWindow());
 217
 218   AckNPackets(1);
 219   expected_send_window += kDefaultTCPMSS;
 220   number_of_packets_in_window++;
 221   EXPECT_EQ(expected_send_window, sender_->SendWindow());
 222
 223   // We should need number_of_packets_in_window ACK:ed packets before
 224   // increasing window by one.
 225   for (int k = 0; k < number_of_packets_in_window; ++k) {
 226     SendAvailableSendWindow();
 227     AckNPackets(1);
 228     EXPECT_EQ(expected_send_window, sender_->SendWindow());
 229   }
 230   SendAvailableSendWindow();
 231   AckNPackets(1);
 232   expected_send_window += kDefaultTCPMSS;
 233   EXPECT_EQ(expected_send_window, sender_->SendWindow());
 234 }
 235
 236 TEST_F(TcpCubicSenderTest, RTOCongestionWindow) {
 237   EXPECT_EQ(kDefaultWindowTCP, sender_->SendWindow());
 238
 239   // Expect the window to decrease to the minimum once the RTO fires.
 240   sender_->OnRetransmissionTimeout(true);
 241   EXPECT_EQ(2 * kDefaultTCPMSS, sender_->SendWindow());
 242 }
 243
 244 TEST_F(TcpCubicSenderTest, RTOCongestionWindowNoRetransmission) {
 245   EXPECT_EQ(kDefaultWindowTCP, sender_->SendWindow());
 246
 247   // Expect the window to remain unchanged if the RTO fires but no
 248   // packets are retransmitted.
 249   sender_->OnRetransmissionTimeout(false);
 250   EXPECT_EQ(kDefaultWindowTCP, sender_->SendWindow());
 251 }
 252
 253 TEST_F(TcpCubicSenderTest, RetransmissionDelay) {
 254   const int64 kRttMs = 10;
 255   const int64 kDeviationMs = 3;
 256   EXPECT_EQ(QuicTime::Delta::Zero(), sender_->RetransmissionDelay());
 257
 258   sender_->UpdateRtt(QuicTime::Delta::FromMilliseconds(kRttMs));
 259
 260   // Initial value is to set the median deviation to half of the initial
 261   // rtt, the median in then multiplied by a factor of 4 and finally the
 262   // smoothed rtt is added which is the initial rtt.
 263   QuicTime::Delta expected_delay =
 264       QuicTime::Delta::FromMilliseconds(kRttMs + kRttMs / 2 * 4);
 265   EXPECT_EQ(expected_delay, sender_->RetransmissionDelay());
 266
 267   for (int i = 0; i < 100; ++i) {
 268     // Run to make sure that we converge.
 269     sender_->UpdateRtt(
 270         QuicTime::Delta::FromMilliseconds(kRttMs + kDeviationMs));
 271     sender_->UpdateRtt(
 272         QuicTime::Delta::FromMilliseconds(kRttMs - kDeviationMs));
 273   }
 274   expected_delay = QuicTime::Delta::FromMilliseconds(kRttMs + kDeviationMs * 4);
 275
 276   EXPECT_NEAR(kRttMs, sender_->SmoothedRtt().ToMilliseconds(), 1);
 277   EXPECT_NEAR(expected_delay.ToMilliseconds(),
 278               sender_->RetransmissionDelay().ToMilliseconds(),
 279               1);
 280   EXPECT_EQ(static_cast<int64>(
 281                 sender_->GetCongestionWindow() * kNumMicrosPerSecond /
 282                 sender_->SmoothedRtt().ToMicroseconds()),
 283             sender_->BandwidthEstimate().ToBytesPerSecond());
 284 }
 285
 286 TEST_F(TcpCubicSenderTest, SlowStartMaxSendWindow) {
 287   const QuicTcpCongestionWindow kMaxCongestionWindowTCP = 50;
 288   const int kNumberOfAck = 100;
 289   sender_.reset(
 290       new TcpCubicSenderPeer(&clock_, false, kMaxCongestionWindowTCP));
 291
 292   QuicCongestionFeedbackFrame feedback;
 293   // At startup make sure we can send.
 294   EXPECT_TRUE(sender_->TimeUntilSend(clock_.Now(),
 295       NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA, NOT_HANDSHAKE).IsZero());
 296   // Get default QuicCongestionFeedbackFrame from receiver.
 297   ASSERT_TRUE(receiver_->GenerateCongestionFeedback(&feedback));
 298   sender_->OnIncomingQuicCongestionFeedbackFrame(feedback, clock_.Now(),
 299                                                  not_used_);
 300   // Make sure we can send.
 301   EXPECT_TRUE(sender_->TimeUntilSend(clock_.Now(),
 302       NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA, NOT_HANDSHAKE).IsZero());
 303
 304   for (int i = 0; i < kNumberOfAck; ++i) {
 305     // Send our full send window.
 306     SendAvailableSendWindow();
 307     AckNPackets(2);
 308   }
 309   QuicByteCount expected_send_window =
 310       kMaxCongestionWindowTCP * kDefaultTCPMSS;
 311   EXPECT_EQ(expected_send_window, sender_->SendWindow());
 312 }
 313
 314 TEST_F(TcpCubicSenderTest, TcpRenoMaxCongestionWindow) {
 315   const QuicTcpCongestionWindow kMaxCongestionWindowTCP = 50;
 316   const int kNumberOfAck = 1000;
 317   sender_.reset(
 318       new TcpCubicSenderPeer(&clock_, true, kMaxCongestionWindowTCP));
 319
 320   QuicCongestionFeedbackFrame feedback;
 321   // At startup make sure we can send.
 322   EXPECT_TRUE(sender_->TimeUntilSend(clock_.Now(),
 323       NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA, NOT_HANDSHAKE).IsZero());
 324   // Get default QuicCongestionFeedbackFrame from receiver.
 325   ASSERT_TRUE(receiver_->GenerateCongestionFeedback(&feedback));
 326   sender_->OnIncomingQuicCongestionFeedbackFrame(feedback, clock_.Now(),
 327                                                  not_used_);
 328   // Make sure we can send.
 329   EXPECT_TRUE(sender_->TimeUntilSend(clock_.Now(),
 330       NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA, NOT_HANDSHAKE).IsZero());
 331
 332   SendAvailableSendWindow();
 333   AckNPackets(2);
 334   // Make sure we fall out of slow start.
 335   sender_->OnPacketLost(acked_sequence_number_ + 1, clock_.Now());
 336
 337   for (int i = 0; i < kNumberOfAck; ++i) {
 338     // Send our full send window.
 339     SendAvailableSendWindow();
 340     AckNPackets(2);
 341   }
 342
 343   QuicByteCount expected_send_window =
 344       kMaxCongestionWindowTCP * kDefaultTCPMSS;
 345   EXPECT_EQ(expected_send_window, sender_->SendWindow());
 346 }
 347
 348 TEST_F(TcpCubicSenderTest, TcpCubicMaxCongestionWindow) {
 349   const QuicTcpCongestionWindow kMaxCongestionWindowTCP = 50;
 350   const int kNumberOfAck = 1000;
 351   sender_.reset(
 352       new TcpCubicSenderPeer(&clock_, false, kMaxCongestionWindowTCP));
 353
 354   QuicCongestionFeedbackFrame feedback;
 355   // At startup make sure we can send.
 356   EXPECT_TRUE(sender_->TimeUntilSend(clock_.Now(),
 357       NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA, NOT_HANDSHAKE).IsZero());
 358   // Get default QuicCongestionFeedbackFrame from receiver.
 359   ASSERT_TRUE(receiver_->GenerateCongestionFeedback(&feedback));
 360   sender_->OnIncomingQuicCongestionFeedbackFrame(feedback, clock_.Now(),
 361                                                  not_used_);
 362   // Make sure we can send.
 363   EXPECT_TRUE(sender_->TimeUntilSend(clock_.Now(),
 364       NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA, NOT_HANDSHAKE).IsZero());
 365
 366   SendAvailableSendWindow();
 367   AckNPackets(2);
 368   // Make sure we fall out of slow start.
 369   sender_->OnPacketLost(acked_sequence_number_ + 1, clock_.Now());
 370
 371   for (int i = 0; i < kNumberOfAck; ++i) {
 372     // Send our full send window.
 373     SendAvailableSendWindow();
 374     AckNPackets(2);
 375   }
 376
 377   QuicByteCount expected_send_window =
 378       kMaxCongestionWindowTCP * kDefaultTCPMSS;
 379   EXPECT_EQ(expected_send_window, sender_->SendWindow());
 380 }
 381
 382 TEST_F(TcpCubicSenderTest, MultipleLossesInOneWindow) {
 383   SendAvailableSendWindow();
 384   const QuicByteCount initial_window = sender_->GetCongestionWindow();
 385   sender_->OnPacketLost(acked_sequence_number_ + 1, clock_.Now());
 386   const QuicByteCount post_loss_window = sender_->GetCongestionWindow();
 387   EXPECT_GT(initial_window, post_loss_window);
 388   sender_->OnPacketLost(acked_sequence_number_ + 3, clock_.Now());
 389   EXPECT_EQ(post_loss_window, sender_->GetCongestionWindow());
 390   sender_->OnPacketLost(sequence_number_ - 1, clock_.Now());
 391   EXPECT_EQ(post_loss_window, sender_->GetCongestionWindow());
 392
 393   // Lose a later packet and ensure the window decreases.
 394   sender_->OnPacketLost(sequence_number_, clock_.Now());
 395   EXPECT_GT(post_loss_window, sender_->GetCongestionWindow());
 396 }
 397
 398 TEST_F(TcpCubicSenderTest, SendWindowNotAffectedByAcks) {
 399   QuicByteCount send_window = sender_->AvailableSendWindow();
 400
 401   // Send a packet with no retransmittable data, and ensure that the congestion
 402   // window doesn't change.
 403   QuicByteCount bytes_in_packet = min(kDefaultTCPMSS, send_window);
 404   sender_->OnPacketSent(clock_.Now(), sequence_number_++, bytes_in_packet,
 405                         NOT_RETRANSMISSION, NO_RETRANSMITTABLE_DATA);
 406   EXPECT_EQ(send_window, sender_->AvailableSendWindow());
 407
 408   // Send a data packet with retransmittable data, and ensure that the
 409   // congestion window has shrunk.
 410   sender_->OnPacketSent(clock_.Now(), sequence_number_++, bytes_in_packet,
 411                         NOT_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA);
 412   EXPECT_GT(send_window, sender_->AvailableSendWindow());
 413 }
 414
 415 TEST_F(TcpCubicSenderTest, ConfigureMaxInitialWindow) {
 416   QuicTcpCongestionWindow congestion_window = sender_->congestion_window();
 417   QuicConfig config;
 418   config.set_server_initial_congestion_window(2 * congestion_window,
 419                                        2 * congestion_window);
 420   EXPECT_EQ(2 * congestion_window, config.server_initial_congestion_window());
 421
 422   sender_->SetFromConfig(config, true);
 423   EXPECT_EQ(2 * congestion_window, sender_->congestion_window());
 424 }
 425
 426 }  // namespace test
 427 }  // namespace net