1 files changed, 388 insertions, 0 deletions
diff --git a/chromium/net/third_party/quiche/src/quic/core/congestion_control/cubic_bytes_test.cc b/chromium/net/third_party/quiche/src/quic/core/congestion_control/cubic_bytes_test.cc
new file mode 100644
index 00000000000..4f3e9b1044a
--- /dev/null
+++ b/chromium/net/third_party/quiche/src/quic/core/congestion_control/cubic_bytes_test.cc
@@ -0,0 +1,388 @@
+// Copyright (c) 2015 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/third_party/quiche/src/quic/core/congestion_control/cubic_bytes.h"
+
+#include <cstdint>
+
+#include "net/third_party/quiche/src/quic/platform/api/quic_flags.h"
+#include "net/third_party/quiche/src/quic/platform/api/quic_str_cat.h"
+#include "net/third_party/quiche/src/quic/platform/api/quic_test.h"
+#include "net/third_party/quiche/src/quic/test_tools/mock_clock.h"
+
+namespace quic {
+namespace test {
+namespace {
+
+const float kBeta = 0.7f;          // Default Cubic backoff factor.
+const float kBetaLastMax = 0.85f;  // Default Cubic backoff factor.
+const uint32_t kNumConnections = 2;
+const float kNConnectionBeta = (kNumConnections - 1 + kBeta) / kNumConnections;
+const float kNConnectionBetaLastMax =
+    (kNumConnections - 1 + kBetaLastMax) / kNumConnections;
+const float kNConnectionAlpha = 3 * kNumConnections * kNumConnections *
+                                (1 - kNConnectionBeta) / (1 + kNConnectionBeta);
+
+}  // namespace
+
+class CubicBytesTest : public QuicTest {
+ protected:
+  CubicBytesTest()
+      : one_ms_(QuicTime::Delta::FromMilliseconds(1)),
+        hundred_ms_(QuicTime::Delta::FromMilliseconds(100)),
+        cubic_(&clock_) {}
+
+  QuicByteCount RenoCwndInBytes(QuicByteCount current_cwnd) {
+    QuicByteCount reno_estimated_cwnd =
+        current_cwnd +
+        kDefaultTCPMSS * (kNConnectionAlpha * kDefaultTCPMSS) / current_cwnd;
+    return reno_estimated_cwnd;
+  }
+
+  QuicByteCount ConservativeCwndInBytes(QuicByteCount current_cwnd) {
+    QuicByteCount conservative_cwnd = current_cwnd + kDefaultTCPMSS / 2;
+    return conservative_cwnd;
+  }
+
+  QuicByteCount CubicConvexCwndInBytes(QuicByteCount initial_cwnd,
+                                       QuicTime::Delta rtt,
+                                       QuicTime::Delta elapsed_time) {
+    const int64_t offset =
+        ((elapsed_time + rtt).ToMicroseconds() << 10) / 1000000;
+    const QuicByteCount delta_congestion_window =
+        ((410 * offset * offset * offset) * kDefaultTCPMSS >> 40);
+    const QuicByteCount cubic_cwnd = initial_cwnd + delta_congestion_window;
+    return cubic_cwnd;
+  }
+
+  QuicByteCount LastMaxCongestionWindow() {
+    return cubic_.last_max_congestion_window();
+  }
+
+  QuicTime::Delta MaxCubicTimeInterval() {
+    return cubic_.MaxCubicTimeInterval();
+  }
+
+  const QuicTime::Delta one_ms_;
+  const QuicTime::Delta hundred_ms_;
+  MockClock clock_;
+  CubicBytes cubic_;
+};
+
+// TODO(jokulik): The original "AboveOrigin" test, below, is very
+// loose.  It's nearly impossible to make the test tighter without
+// deploying the fix for convex mode.  Once cubic convex is deployed,
+// replace "AboveOrigin" with this test.
+TEST_F(CubicBytesTest, AboveOriginWithTighterBounds) {
+  // Convex growth.
+  const QuicTime::Delta rtt_min = hundred_ms_;
+  int64_t rtt_min_ms = rtt_min.ToMilliseconds();
+  float rtt_min_s = rtt_min_ms / 1000.0;
+  QuicByteCount current_cwnd = 10 * kDefaultTCPMSS;
+  const QuicByteCount initial_cwnd = current_cwnd;
+
+  clock_.AdvanceTime(one_ms_);
+  const QuicTime initial_time = clock_.ApproximateNow();
+  const QuicByteCount expected_first_cwnd = RenoCwndInBytes(current_cwnd);
+  current_cwnd = cubic_.CongestionWindowAfterAck(kDefaultTCPMSS, current_cwnd,
+                                                 rtt_min, initial_time);
+  ASSERT_EQ(expected_first_cwnd, current_cwnd);
+
+  // Normal TCP phase.
+  // The maximum number of expected Reno RTTs is calculated by
+  // finding the point where the cubic curve and the reno curve meet.
+  const int max_reno_rtts =
+      std::sqrt(kNConnectionAlpha / (.4 * rtt_min_s * rtt_min_s * rtt_min_s)) -
+      2;
+  for (int i = 0; i < max_reno_rtts; ++i) {
+    // Alternatively, we expect it to increase by one, every time we
+    // receive current_cwnd/Alpha acks back.  (This is another way of
+    // saying we expect cwnd to increase by approximately Alpha once
+    // we receive current_cwnd number ofacks back).
+    const uint64_t num_acks_this_epoch =
+        current_cwnd / kDefaultTCPMSS / kNConnectionAlpha;
+    const QuicByteCount initial_cwnd_this_epoch = current_cwnd;
+    for (QuicPacketCount n = 0; n < num_acks_this_epoch; ++n) {
+      // Call once per ACK.
+      const QuicByteCount expected_next_cwnd = RenoCwndInBytes(current_cwnd);
+      current_cwnd = cubic_.CongestionWindowAfterAck(
+          kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
+      ASSERT_EQ(expected_next_cwnd, current_cwnd);
+    }
+    // Our byte-wise Reno implementation is an estimate.  We expect
+    // the cwnd to increase by approximately one MSS every
+    // cwnd/kDefaultTCPMSS/Alpha acks, but it may be off by as much as
+    // half a packet for smaller values of current_cwnd.
+    const QuicByteCount cwnd_change_this_epoch =
+        current_cwnd - initial_cwnd_this_epoch;
+    ASSERT_NEAR(kDefaultTCPMSS, cwnd_change_this_epoch, kDefaultTCPMSS / 2);
+    clock_.AdvanceTime(hundred_ms_);
+  }
+
+  for (int i = 0; i < 54; ++i) {
+    const uint64_t max_acks_this_epoch = current_cwnd / kDefaultTCPMSS;
+    const QuicTime::Delta interval = QuicTime::Delta::FromMicroseconds(
+        hundred_ms_.ToMicroseconds() / max_acks_this_epoch);
+    for (QuicPacketCount n = 0; n < max_acks_this_epoch; ++n) {
+      clock_.AdvanceTime(interval);
+      current_cwnd = cubic_.CongestionWindowAfterAck(
+          kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
+      const QuicByteCount expected_cwnd = CubicConvexCwndInBytes(
+          initial_cwnd, rtt_min, (clock_.ApproximateNow() - initial_time));
+      // If we allow per-ack updates, every update is a small cubic update.
+      ASSERT_EQ(expected_cwnd, current_cwnd);
+    }
+  }
+  const QuicByteCount expected_cwnd = CubicConvexCwndInBytes(
+      initial_cwnd, rtt_min, (clock_.ApproximateNow() - initial_time));
+  current_cwnd = cubic_.CongestionWindowAfterAck(
+      kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
+  ASSERT_EQ(expected_cwnd, current_cwnd);
+}
+
+// TODO(ianswett): This test was disabled when all fixes were enabled, but it
+// may be worth fixing.
+TEST_F(CubicBytesTest, DISABLED_AboveOrigin) {
+  // Convex growth.
+  const QuicTime::Delta rtt_min = hundred_ms_;
+  QuicByteCount current_cwnd = 10 * kDefaultTCPMSS;
+  // Without the signed-integer, cubic-convex fix, we start out in the
+  // wrong mode.
+  QuicPacketCount expected_cwnd = RenoCwndInBytes(current_cwnd);
+  // Initialize the state.
+  clock_.AdvanceTime(one_ms_);
+  ASSERT_EQ(expected_cwnd,
+            cubic_.CongestionWindowAfterAck(kDefaultTCPMSS, current_cwnd,
+                                            rtt_min, clock_.ApproximateNow()));
+  current_cwnd = expected_cwnd;
+  const QuicPacketCount initial_cwnd = expected_cwnd;
+  // Normal TCP phase.
+  for (int i = 0; i < 48; ++i) {
+    for (QuicPacketCount n = 1;
+         n < current_cwnd / kDefaultTCPMSS / kNConnectionAlpha; ++n) {
+      // Call once per ACK.
+      ASSERT_NEAR(
+          current_cwnd,
+          cubic_.CongestionWindowAfterAck(kDefaultTCPMSS, current_cwnd, rtt_min,
+                                          clock_.ApproximateNow()),
+          kDefaultTCPMSS);
+    }
+    clock_.AdvanceTime(hundred_ms_);
+    current_cwnd = cubic_.CongestionWindowAfterAck(
+        kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
+    // When we fix convex mode and the uint64 arithmetic, we
+    // increase the expected_cwnd only after after the first 100ms,
+    // rather than after the initial 1ms.
+    expected_cwnd += kDefaultTCPMSS;
+    ASSERT_NEAR(expected_cwnd, current_cwnd, kDefaultTCPMSS);
+  }
+  // Cubic phase.
+  for (int i = 0; i < 52; ++i) {
+    for (QuicPacketCount n = 1; n < current_cwnd / kDefaultTCPMSS; ++n) {
+      // Call once per ACK.
+      ASSERT_NEAR(
+          current_cwnd,
+          cubic_.CongestionWindowAfterAck(kDefaultTCPMSS, current_cwnd, rtt_min,
+                                          clock_.ApproximateNow()),
+          kDefaultTCPMSS);
+    }
+    clock_.AdvanceTime(hundred_ms_);
+    current_cwnd = cubic_.CongestionWindowAfterAck(
+        kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
+  }
+  // Total time elapsed so far; add min_rtt (0.1s) here as well.
+  float elapsed_time_s = 10.0f + 0.1f;
+  // |expected_cwnd| is initial value of cwnd + K * t^3, where K = 0.4.
+  expected_cwnd =
+      initial_cwnd / kDefaultTCPMSS +
+      (elapsed_time_s * elapsed_time_s * elapsed_time_s * 410) / 1024;
+  EXPECT_EQ(expected_cwnd, current_cwnd / kDefaultTCPMSS);
+}
+
+// Constructs an artificial scenario to ensure that cubic-convex
+// increases are truly fine-grained:
+//
+// - After starting the epoch, this test advances the elapsed time
+// sufficiently far that cubic will do small increases at less than
+// MaxCubicTimeInterval() intervals.
+//
+// - Sets an artificially large initial cwnd to prevent Reno from the
+// convex increases on every ack.
+TEST_F(CubicBytesTest, AboveOriginFineGrainedCubing) {
+  // Start the test with an artificially large cwnd to prevent Reno
+  // from over-taking cubic.
+  QuicByteCount current_cwnd = 1000 * kDefaultTCPMSS;
+  const QuicByteCount initial_cwnd = current_cwnd;
+  const QuicTime::Delta rtt_min = hundred_ms_;
+  clock_.AdvanceTime(one_ms_);
+  QuicTime initial_time = clock_.ApproximateNow();
+
+  // Start the epoch and then artificially advance the time.
+  current_cwnd = cubic_.CongestionWindowAfterAck(
+      kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
+  clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(600));
+  current_cwnd = cubic_.CongestionWindowAfterAck(
+      kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
+
+  // We expect the algorithm to perform only non-zero, fine-grained cubic
+  // increases on every ack in this case.
+  for (int i = 0; i < 100; ++i) {
+    clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(10));
+    const QuicByteCount expected_cwnd = CubicConvexCwndInBytes(
+        initial_cwnd, rtt_min, (clock_.ApproximateNow() - initial_time));
+    const QuicByteCount next_cwnd = cubic_.CongestionWindowAfterAck(
+        kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
+    // Make sure we are performing cubic increases.
+    ASSERT_EQ(expected_cwnd, next_cwnd);
+    // Make sure that these are non-zero, less-than-packet sized
+    // increases.
+    ASSERT_GT(next_cwnd, current_cwnd);
+    const QuicByteCount cwnd_delta = next_cwnd - current_cwnd;
+    ASSERT_GT(kDefaultTCPMSS * .1, cwnd_delta);
+
+    current_cwnd = next_cwnd;
+  }
+}
+
+// Constructs an artificial scenario to show what happens when we
+// allow per-ack updates, rather than limititing update freqency.  In
+// this scenario, the first two acks of the epoch produce the same
+// cwnd.  When we limit per-ack updates, this would cause the
+// cessation of cubic updates for 30ms.  When we allow per-ack
+// updates, the window continues to grow on every ack.
+TEST_F(CubicBytesTest, PerAckUpdates) {
+  // Start the test with a large cwnd and RTT, to force the first
+  // increase to be a cubic increase.
+  QuicPacketCount initial_cwnd_packets = 150;
+  QuicByteCount current_cwnd = initial_cwnd_packets * kDefaultTCPMSS;
+  const QuicTime::Delta rtt_min = 350 * one_ms_;
+
+  // Initialize the epoch
+  clock_.AdvanceTime(one_ms_);
+  // Keep track of the growth of the reno-equivalent cwnd.
+  QuicByteCount reno_cwnd = RenoCwndInBytes(current_cwnd);
+  current_cwnd = cubic_.CongestionWindowAfterAck(
+      kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
+  const QuicByteCount initial_cwnd = current_cwnd;
+
+  // Simulate the return of cwnd packets in less than
+  // MaxCubicInterval() time.
+  const QuicPacketCount max_acks = initial_cwnd_packets / kNConnectionAlpha;
+  const QuicTime::Delta interval = QuicTime::Delta::FromMicroseconds(
+      MaxCubicTimeInterval().ToMicroseconds() / (max_acks + 1));
+
+  // In this scenario, the first increase is dictated by the cubic
+  // equation, but it is less than one byte, so the cwnd doesn't
+  // change.  Normally, without per-ack increases, any cwnd plateau
+  // will cause the cwnd to be pinned for MaxCubicTimeInterval().  If
+  // we enable per-ack updates, the cwnd will continue to grow,
+  // regardless of the temporary plateau.
+  clock_.AdvanceTime(interval);
+  reno_cwnd = RenoCwndInBytes(reno_cwnd);
+  ASSERT_EQ(current_cwnd,
+            cubic_.CongestionWindowAfterAck(kDefaultTCPMSS, current_cwnd,
+                                            rtt_min, clock_.ApproximateNow()));
+  for (QuicPacketCount i = 1; i < max_acks; ++i) {
+    clock_.AdvanceTime(interval);
+    const QuicByteCount next_cwnd = cubic_.CongestionWindowAfterAck(
+        kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
+    reno_cwnd = RenoCwndInBytes(reno_cwnd);
+    // The window shoud increase on every ack.
+    ASSERT_LT(current_cwnd, next_cwnd);
+    ASSERT_EQ(reno_cwnd, next_cwnd);
+    current_cwnd = next_cwnd;
+  }
+
+  // After all the acks are returned from the epoch, we expect the
+  // cwnd to have increased by nearly one packet.  (Not exactly one
+  // packet, because our byte-wise Reno algorithm is always a slight
+  // under-estimation).  Without per-ack updates, the current_cwnd
+  // would otherwise be unchanged.
+  const QuicByteCount minimum_expected_increase = kDefaultTCPMSS * .9;
+  EXPECT_LT(minimum_expected_increase + initial_cwnd, current_cwnd);
+}
+
+TEST_F(CubicBytesTest, LossEvents) {
+  const QuicTime::Delta rtt_min = hundred_ms_;
+  QuicByteCount current_cwnd = 422 * kDefaultTCPMSS;
+  // Without the signed-integer, cubic-convex fix, we mistakenly
+  // increment cwnd after only one_ms_ and a single ack.
+  QuicPacketCount expected_cwnd = RenoCwndInBytes(current_cwnd);
+  // Initialize the state.
+  clock_.AdvanceTime(one_ms_);
+  EXPECT_EQ(expected_cwnd,
+            cubic_.CongestionWindowAfterAck(kDefaultTCPMSS, current_cwnd,
+                                            rtt_min, clock_.ApproximateNow()));
+
+  // On the first loss, the last max congestion window is set to the
+  // congestion window before the loss.
+  QuicByteCount pre_loss_cwnd = current_cwnd;
+  ASSERT_EQ(0u, LastMaxCongestionWindow());
+  expected_cwnd = static_cast<QuicByteCount>(current_cwnd * kNConnectionBeta);
+  EXPECT_EQ(expected_cwnd,
+            cubic_.CongestionWindowAfterPacketLoss(current_cwnd));
+  ASSERT_EQ(pre_loss_cwnd, LastMaxCongestionWindow());
+  current_cwnd = expected_cwnd;
+
+  // On the second loss, the current congestion window has not yet
+  // reached the last max congestion window.  The last max congestion
+  // window will be reduced by an additional backoff factor to allow
+  // for competition.
+  pre_loss_cwnd = current_cwnd;
+  expected_cwnd = static_cast<QuicByteCount>(current_cwnd * kNConnectionBeta);
+  ASSERT_EQ(expected_cwnd,
+            cubic_.CongestionWindowAfterPacketLoss(current_cwnd));
+  current_cwnd = expected_cwnd;
+  EXPECT_GT(pre_loss_cwnd, LastMaxCongestionWindow());
+  QuicByteCount expected_last_max =
+      static_cast<QuicByteCount>(pre_loss_cwnd * kNConnectionBetaLastMax);
+  EXPECT_EQ(expected_last_max, LastMaxCongestionWindow());
+  EXPECT_LT(expected_cwnd, LastMaxCongestionWindow());
+  // Simulate an increase, and check that we are below the origin.
+  current_cwnd = cubic_.CongestionWindowAfterAck(
+      kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
+  EXPECT_GT(LastMaxCongestionWindow(), current_cwnd);
+
+  // On the final loss, simulate the condition where the congestion
+  // window had a chance to grow nearly to the last congestion window.
+  current_cwnd = LastMaxCongestionWindow() - 1;
+  pre_loss_cwnd = current_cwnd;
+  expected_cwnd = static_cast<QuicByteCount>(current_cwnd * kNConnectionBeta);
+  EXPECT_EQ(expected_cwnd,
+            cubic_.CongestionWindowAfterPacketLoss(current_cwnd));
+  expected_last_max = pre_loss_cwnd;
+  ASSERT_EQ(expected_last_max, LastMaxCongestionWindow());
+}
+
+TEST_F(CubicBytesTest, BelowOrigin) {
+  // Concave growth.
+  const QuicTime::Delta rtt_min = hundred_ms_;
+  QuicByteCount current_cwnd = 422 * kDefaultTCPMSS;
+  // Without the signed-integer, cubic-convex fix, we mistakenly
+  // increment cwnd after only one_ms_ and a single ack.
+  QuicPacketCount expected_cwnd = RenoCwndInBytes(current_cwnd);
+  // Initialize the state.
+  clock_.AdvanceTime(one_ms_);
+  EXPECT_EQ(expected_cwnd,
+            cubic_.CongestionWindowAfterAck(kDefaultTCPMSS, current_cwnd,
+                                            rtt_min, clock_.ApproximateNow()));
+  expected_cwnd = static_cast<QuicPacketCount>(current_cwnd * kNConnectionBeta);
+  EXPECT_EQ(expected_cwnd,
+            cubic_.CongestionWindowAfterPacketLoss(current_cwnd));
+  current_cwnd = expected_cwnd;
+  // First update after loss to initialize the epoch.
+  current_cwnd = cubic_.CongestionWindowAfterAck(
+      kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
+  // Cubic phase.
+  for (int i = 0; i < 40; ++i) {
+    clock_.AdvanceTime(hundred_ms_);
+    current_cwnd = cubic_.CongestionWindowAfterAck(
+        kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
+  }
+  expected_cwnd = 553632;
+  EXPECT_EQ(expected_cwnd, current_cwnd);
+}
+
+}  // namespace test
+}  // namespace quic