| OLD | NEW |
| 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 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 | 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 "net/quic/core/congestion_control/cubic.h" | 5 #include "net/quic/core/congestion_control/cubic.h" |
| 6 | 6 |
| 7 #include <cstdint> | 7 #include <cstdint> |
| 8 | 8 |
| 9 #include "net/quic/core/quic_flags.h" | 9 #include "net/quic/core/quic_flags.h" |
| 10 #include "net/quic/platform/api/quic_str_cat.h" |
| 10 #include "net/quic/test_tools/mock_clock.h" | 11 #include "net/quic/test_tools/mock_clock.h" |
| 11 #include "testing/gtest/include/gtest/gtest.h" | 12 #include "testing/gtest/include/gtest/gtest.h" |
| 12 | 13 |
| 14 using std::string; |
| 15 |
| 13 namespace net { | 16 namespace net { |
| 14 namespace test { | 17 namespace test { |
| 18 namespace { |
| 15 | 19 |
| 16 const float kBeta = 0.7f; // Default Cubic backoff factor. | 20 const float kBeta = 0.7f; // Default Cubic backoff factor. |
| 17 const float kBetaLastMax = 0.85f; // Default Cubic backoff factor. | 21 const float kBetaLastMax = 0.85f; // Default Cubic backoff factor. |
| 18 const uint32_t kNumConnections = 2; | 22 const uint32_t kNumConnections = 2; |
| 19 const float kNConnectionBeta = (kNumConnections - 1 + kBeta) / kNumConnections; | 23 const float kNConnectionBeta = (kNumConnections - 1 + kBeta) / kNumConnections; |
| 20 const float kNConnectionBetaLastMax = | 24 const float kNConnectionBetaLastMax = |
| 21 (kNumConnections - 1 + kBetaLastMax) / kNumConnections; | 25 (kNumConnections - 1 + kBetaLastMax) / kNumConnections; |
| 22 const float kNConnectionAlpha = 3 * kNumConnections * kNumConnections * | 26 const float kNConnectionAlpha = 3 * kNumConnections * kNumConnections * |
| 23 (1 - kNConnectionBeta) / (1 + kNConnectionBeta); | 27 (1 - kNConnectionBeta) / (1 + kNConnectionBeta); |
| 24 | 28 |
| 29 struct TestParams { |
| 30 TestParams(bool fix_convex_mode, bool fix_beta_last_max) |
| 31 : fix_convex_mode(fix_convex_mode), |
| 32 fix_beta_last_max(fix_beta_last_max) {} |
| 33 |
| 34 friend std::ostream& operator<<(std::ostream& os, const TestParams& p) { |
| 35 os << "{ fix_convex_mode: " << p.fix_convex_mode |
| 36 << " fix_beta_last_max: " << p.fix_beta_last_max; |
| 37 os << " }"; |
| 38 return os; |
| 39 } |
| 40 |
| 41 bool fix_convex_mode; |
| 42 bool fix_beta_last_max; |
| 43 }; |
| 44 |
| 45 string TestParamToString(const testing::TestParamInfo<TestParams>& params) { |
| 46 return QuicStrCat("convex_mode_", params.param.fix_convex_mode, "_", |
| 47 "beta_last_max_", params.param.fix_beta_last_max); |
| 48 } |
| 49 |
| 50 std::vector<TestParams> GetTestParams() { |
| 51 std::vector<TestParams> params; |
| 52 for (bool fix_convex_mode : {true, false}) { |
| 53 for (bool fix_beta_last_max : {true, false}) { |
| 54 if (!FLAGS_quic_reloadable_flag_quic_fix_cubic_convex_mode && |
| 55 fix_convex_mode) { |
| 56 continue; |
| 57 } |
| 58 if (!FLAGS_quic_reloadable_flag_quic_fix_beta_last_max && |
| 59 fix_beta_last_max) { |
| 60 continue; |
| 61 } |
| 62 TestParams param(fix_convex_mode, fix_beta_last_max); |
| 63 params.push_back(param); |
| 64 } |
| 65 } |
| 66 return params; |
| 67 } |
| 68 |
| 69 } // namespace |
| 70 |
| 25 // TODO(jokulik): Once we've rolled out the cubic convex fix, we will | 71 // TODO(jokulik): Once we've rolled out the cubic convex fix, we will |
| 26 // no longer need a parameterized test. | 72 // no longer need a parameterized test. |
| 27 class CubicTest : public ::testing::TestWithParam<bool> { | 73 class CubicTest : public ::testing::TestWithParam<TestParams> { |
| 28 protected: | 74 protected: |
| 29 CubicTest() | 75 CubicTest() |
| 30 : one_ms_(QuicTime::Delta::FromMilliseconds(1)), | 76 : one_ms_(QuicTime::Delta::FromMilliseconds(1)), |
| 31 hundred_ms_(QuicTime::Delta::FromMilliseconds(100)), | 77 hundred_ms_(QuicTime::Delta::FromMilliseconds(100)), |
| 32 cubic_(&clock_) { | 78 cubic_(&clock_) { |
| 33 fix_convex_mode_ = GetParam(); | 79 cubic_.SetFixConvexMode(GetParam().fix_convex_mode); |
| 34 cubic_.SetFixConvexMode(fix_convex_mode_); | 80 cubic_.SetFixBetaLastMax(GetParam().fix_beta_last_max); |
| 35 cubic_.SetFixBetaLastMax(FLAGS_quic_reloadable_flag_quic_fix_beta_last_max); | |
| 36 } | 81 } |
| 37 | 82 |
| 38 QuicByteCount LastMaxCongestionWindow() { | 83 QuicByteCount LastMaxCongestionWindow() { |
| 39 return cubic_.last_max_congestion_window(); | 84 return cubic_.last_max_congestion_window(); |
| 40 } | 85 } |
| 41 | 86 |
| 42 const QuicTime::Delta one_ms_; | 87 const QuicTime::Delta one_ms_; |
| 43 const QuicTime::Delta hundred_ms_; | 88 const QuicTime::Delta hundred_ms_; |
| 44 MockClock clock_; | 89 MockClock clock_; |
| 45 Cubic cubic_; | 90 Cubic cubic_; |
| 46 bool fix_convex_mode_; | |
| 47 }; | 91 }; |
| 48 | 92 |
| 49 INSTANTIATE_TEST_CASE_P(CubicTests, CubicTest, testing::Bool()); | 93 INSTANTIATE_TEST_CASE_P(CubicTests, |
| 94 CubicTest, |
| 95 ::testing::ValuesIn(GetTestParams()), |
| 96 TestParamToString); |
| 50 | 97 |
| 51 TEST_P(CubicTest, AboveOrigin) { | 98 TEST_P(CubicTest, AboveOrigin) { |
| 52 // Convex growth. | 99 // Convex growth. |
| 53 const QuicTime::Delta rtt_min = hundred_ms_; | 100 const QuicTime::Delta rtt_min = hundred_ms_; |
| 54 const float rtt_min_s = rtt_min.ToMilliseconds() / 1000.0; | 101 const float rtt_min_s = rtt_min.ToMilliseconds() / 1000.0; |
| 55 QuicPacketCount current_cwnd = 10; | 102 QuicPacketCount current_cwnd = 10; |
| 56 // Without the signed-integer, cubic-convex fix, we mistakenly | 103 // Without the signed-integer, cubic-convex fix, we mistakenly |
| 57 // increment cwnd after only one_ms_ and a single ack. | 104 // increment cwnd after only one_ms_ and a single ack. |
| 58 QuicPacketCount expected_cwnd = | 105 QuicPacketCount expected_cwnd = |
| 59 fix_convex_mode_ ? current_cwnd : current_cwnd + 1; | 106 GetParam().fix_convex_mode ? current_cwnd : current_cwnd + 1; |
| 60 // Initialize the state. | 107 // Initialize the state. |
| 61 clock_.AdvanceTime(one_ms_); | 108 clock_.AdvanceTime(one_ms_); |
| 62 const QuicTime initial_time = clock_.ApproximateNow(); | 109 const QuicTime initial_time = clock_.ApproximateNow(); |
| 63 current_cwnd = | 110 current_cwnd = |
| 64 cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min, initial_time); | 111 cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min, initial_time); |
| 65 ASSERT_EQ(expected_cwnd, current_cwnd); | 112 ASSERT_EQ(expected_cwnd, current_cwnd); |
| 66 const QuicPacketCount initial_cwnd = current_cwnd; | 113 const QuicPacketCount initial_cwnd = current_cwnd; |
| 67 // Normal TCP phase. | 114 // Normal TCP phase. |
| 68 // The maximum number of expected reno RTTs can be calculated by | 115 // The maximum number of expected reno RTTs can be calculated by |
| 69 // finding the point where the cubic curve and the reno curve meet. | 116 // finding the point where the cubic curve and the reno curve meet. |
| 70 const int max_reno_rtts = | 117 const int max_reno_rtts = |
| 71 std::sqrt(kNConnectionAlpha / (.4 * rtt_min_s * rtt_min_s * rtt_min_s)) - | 118 std::sqrt(kNConnectionAlpha / (.4 * rtt_min_s * rtt_min_s * rtt_min_s)) - |
| 72 1; | 119 1; |
| 73 for (int i = 0; i < max_reno_rtts; ++i) { | 120 for (int i = 0; i < max_reno_rtts; ++i) { |
| 74 const QuicByteCount max_per_ack_cwnd = current_cwnd; | 121 const QuicByteCount max_per_ack_cwnd = current_cwnd; |
| 75 for (QuicPacketCount n = 1; n < max_per_ack_cwnd / kNConnectionAlpha; ++n) { | 122 for (QuicPacketCount n = 1; n < max_per_ack_cwnd / kNConnectionAlpha; ++n) { |
| 76 // Call once per ACK. | 123 // Call once per ACK. |
| 77 const QuicByteCount next_cwnd = cubic_.CongestionWindowAfterAck( | 124 const QuicByteCount next_cwnd = cubic_.CongestionWindowAfterAck( |
| 78 current_cwnd, rtt_min, clock_.ApproximateNow()); | 125 current_cwnd, rtt_min, clock_.ApproximateNow()); |
| 79 ASSERT_EQ(current_cwnd, next_cwnd); | 126 ASSERT_EQ(current_cwnd, next_cwnd); |
| 80 } | 127 } |
| 81 clock_.AdvanceTime(hundred_ms_); | 128 clock_.AdvanceTime(hundred_ms_); |
| 82 current_cwnd = cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min, | 129 current_cwnd = cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min, |
| 83 clock_.ApproximateNow()); | 130 clock_.ApproximateNow()); |
| 84 if (fix_convex_mode_) { | 131 if (GetParam().fix_convex_mode) { |
| 85 // When we fix convex mode and the uint64 arithmetic, we | 132 // When we fix convex mode and the uint64 arithmetic, we |
| 86 // increase the expected_cwnd only after after the first 100ms, | 133 // increase the expected_cwnd only after after the first 100ms, |
| 87 // rather than after the initial 1ms. | 134 // rather than after the initial 1ms. |
| 88 expected_cwnd++; | 135 expected_cwnd++; |
| 89 ASSERT_EQ(expected_cwnd, current_cwnd); | 136 ASSERT_EQ(expected_cwnd, current_cwnd); |
| 90 } else { | 137 } else { |
| 91 ASSERT_EQ(expected_cwnd, current_cwnd); | 138 ASSERT_EQ(expected_cwnd, current_cwnd); |
| 92 expected_cwnd++; | 139 expected_cwnd++; |
| 93 } | 140 } |
| 94 } | 141 } |
| (...skipping 20 matching lines...) Expand all Loading... |
| 115 (elapsed_time_s * elapsed_time_s * elapsed_time_s * 410) / 1024; | 162 (elapsed_time_s * elapsed_time_s * elapsed_time_s * 410) / 1024; |
| 116 EXPECT_EQ(expected_cwnd, current_cwnd); | 163 EXPECT_EQ(expected_cwnd, current_cwnd); |
| 117 } | 164 } |
| 118 | 165 |
| 119 TEST_P(CubicTest, LossEvents) { | 166 TEST_P(CubicTest, LossEvents) { |
| 120 const QuicTime::Delta rtt_min = hundred_ms_; | 167 const QuicTime::Delta rtt_min = hundred_ms_; |
| 121 QuicPacketCount current_cwnd = 422; | 168 QuicPacketCount current_cwnd = 422; |
| 122 // Without the signed-integer, cubic-convex fix, we mistakenly | 169 // Without the signed-integer, cubic-convex fix, we mistakenly |
| 123 // increment cwnd after only one_ms_ and a single ack. | 170 // increment cwnd after only one_ms_ and a single ack. |
| 124 QuicPacketCount expected_cwnd = | 171 QuicPacketCount expected_cwnd = |
| 125 fix_convex_mode_ ? current_cwnd : current_cwnd + 1; | 172 GetParam().fix_convex_mode ? current_cwnd : current_cwnd + 1; |
| 126 // Initialize the state. | 173 // Initialize the state. |
| 127 clock_.AdvanceTime(one_ms_); | 174 clock_.AdvanceTime(one_ms_); |
| 128 EXPECT_EQ(expected_cwnd, cubic_.CongestionWindowAfterAck( | 175 EXPECT_EQ(expected_cwnd, cubic_.CongestionWindowAfterAck( |
| 129 current_cwnd, rtt_min, clock_.ApproximateNow())); | 176 current_cwnd, rtt_min, clock_.ApproximateNow())); |
| 130 | 177 |
| 131 // On the first loss, the last max congestion window is set to the | 178 // On the first loss, the last max congestion window is set to the |
| 132 // congestion window before the loss. | 179 // congestion window before the loss. |
| 133 QuicByteCount pre_loss_cwnd = current_cwnd; | 180 QuicByteCount pre_loss_cwnd = current_cwnd; |
| 134 expected_cwnd = static_cast<QuicPacketCount>(current_cwnd * kNConnectionBeta); | 181 expected_cwnd = static_cast<QuicPacketCount>(current_cwnd * kNConnectionBeta); |
| 135 ASSERT_EQ(0u, LastMaxCongestionWindow()); | 182 ASSERT_EQ(0u, LastMaxCongestionWindow()); |
| 136 EXPECT_EQ(expected_cwnd, | 183 EXPECT_EQ(expected_cwnd, |
| 137 cubic_.CongestionWindowAfterPacketLoss(current_cwnd)); | 184 cubic_.CongestionWindowAfterPacketLoss(current_cwnd)); |
| 138 ASSERT_EQ(pre_loss_cwnd, LastMaxCongestionWindow()); | 185 ASSERT_EQ(pre_loss_cwnd, LastMaxCongestionWindow()); |
| 139 current_cwnd = expected_cwnd; | 186 current_cwnd = expected_cwnd; |
| 140 | 187 |
| 141 // On the second loss, the current congestion window is | 188 // On the second loss, the current congestion window is |
| 142 // significantly lower than the last max congestion window. The | 189 // significantly lower than the last max congestion window. The |
| 143 // last max congestion window will be reduced by an additional | 190 // last max congestion window will be reduced by an additional |
| 144 // backoff factor to allow for competition. | 191 // backoff factor to allow for competition. |
| 145 pre_loss_cwnd = current_cwnd; | 192 pre_loss_cwnd = current_cwnd; |
| 146 expected_cwnd = static_cast<QuicPacketCount>(current_cwnd * kNConnectionBeta); | 193 expected_cwnd = static_cast<QuicPacketCount>(current_cwnd * kNConnectionBeta); |
| 147 ASSERT_EQ(expected_cwnd, | 194 ASSERT_EQ(expected_cwnd, |
| 148 cubic_.CongestionWindowAfterPacketLoss(current_cwnd)); | 195 cubic_.CongestionWindowAfterPacketLoss(current_cwnd)); |
| 149 current_cwnd = expected_cwnd; | 196 current_cwnd = expected_cwnd; |
| 150 EXPECT_GT(pre_loss_cwnd, LastMaxCongestionWindow()); | 197 EXPECT_GT(pre_loss_cwnd, LastMaxCongestionWindow()); |
| 151 QuicByteCount expected_last_max = | 198 QuicByteCount expected_last_max = |
| 152 FLAGS_quic_reloadable_flag_quic_fix_beta_last_max | 199 GetParam().fix_beta_last_max |
| 153 ? static_cast<QuicPacketCount>(pre_loss_cwnd * | 200 ? static_cast<QuicPacketCount>(pre_loss_cwnd * |
| 154 kNConnectionBetaLastMax) | 201 kNConnectionBetaLastMax) |
| 155 : static_cast<QuicPacketCount>(pre_loss_cwnd * kBetaLastMax); | 202 : static_cast<QuicPacketCount>(pre_loss_cwnd * kBetaLastMax); |
| 156 EXPECT_EQ(expected_last_max, LastMaxCongestionWindow()); | 203 EXPECT_EQ(expected_last_max, LastMaxCongestionWindow()); |
| 157 if (FLAGS_quic_reloadable_flag_quic_fix_beta_last_max) { | 204 if (GetParam().fix_beta_last_max) { |
| 158 EXPECT_LT(expected_cwnd, LastMaxCongestionWindow()); | 205 EXPECT_LT(expected_cwnd, LastMaxCongestionWindow()); |
| 159 } else { | 206 } else { |
| 160 // If we don't scale kLastBetaMax, the current window is exactly | 207 // If we don't scale kLastBetaMax, the current window is exactly |
| 161 // equal to the last max congestion window, which would cause us | 208 // equal to the last max congestion window, which would cause us |
| 162 // to land above the origin on the next increase. | 209 // to land above the origin on the next increase. |
| 163 EXPECT_EQ(expected_cwnd, LastMaxCongestionWindow()); | 210 EXPECT_EQ(expected_cwnd, LastMaxCongestionWindow()); |
| 164 } | 211 } |
| 165 // Simulate an increase, and check that we are below the origin. | 212 // Simulate an increase, and check that we are below the origin. |
| 166 current_cwnd = cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min, | 213 current_cwnd = cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min, |
| 167 clock_.ApproximateNow()); | 214 clock_.ApproximateNow()); |
| 168 if (FLAGS_quic_reloadable_flag_quic_fix_beta_last_max) { | 215 if (GetParam().fix_beta_last_max) { |
| 169 EXPECT_GT(LastMaxCongestionWindow(), current_cwnd); | 216 EXPECT_GT(LastMaxCongestionWindow(), current_cwnd); |
| 170 } else { | 217 } else { |
| 171 // Without the bug fix, we will be at or above the origin. | 218 // Without the bug fix, we will be at or above the origin. |
| 172 EXPECT_LE(LastMaxCongestionWindow(), current_cwnd); | 219 EXPECT_LE(LastMaxCongestionWindow(), current_cwnd); |
| 173 } | 220 } |
| 174 | 221 |
| 175 // On the final loss, simulate the condition where the congestion | 222 // On the final loss, simulate the condition where the congestion |
| 176 // window had a chance to grow back to the last congestion window. | 223 // window had a chance to grow back to the last congestion window. |
| 177 current_cwnd = LastMaxCongestionWindow(); | 224 current_cwnd = LastMaxCongestionWindow(); |
| 178 pre_loss_cwnd = current_cwnd; | 225 pre_loss_cwnd = current_cwnd; |
| 179 expected_cwnd = static_cast<QuicPacketCount>(current_cwnd * kNConnectionBeta); | 226 expected_cwnd = static_cast<QuicPacketCount>(current_cwnd * kNConnectionBeta); |
| 180 EXPECT_EQ(expected_cwnd, | 227 EXPECT_EQ(expected_cwnd, |
| 181 cubic_.CongestionWindowAfterPacketLoss(current_cwnd)); | 228 cubic_.CongestionWindowAfterPacketLoss(current_cwnd)); |
| 182 ASSERT_EQ(pre_loss_cwnd, LastMaxCongestionWindow()); | 229 ASSERT_EQ(pre_loss_cwnd, LastMaxCongestionWindow()); |
| 183 } | 230 } |
| 184 | 231 |
| 185 TEST_P(CubicTest, BelowOrigin) { | 232 TEST_P(CubicTest, BelowOrigin) { |
| 186 // Concave growth. | 233 // Concave growth. |
| 187 const QuicTime::Delta rtt_min = hundred_ms_; | 234 const QuicTime::Delta rtt_min = hundred_ms_; |
| 188 QuicPacketCount current_cwnd = 422; | 235 QuicPacketCount current_cwnd = 422; |
| 189 // Without the signed-integer, cubic-convex fix, we mistakenly | 236 // Without the signed-integer, cubic-convex fix, we mistakenly |
| 190 // increment cwnd after only one_ms_ and a single ack. | 237 // increment cwnd after only one_ms_ and a single ack. |
| 191 QuicPacketCount expected_cwnd = | 238 QuicPacketCount expected_cwnd = |
| 192 fix_convex_mode_ ? current_cwnd : current_cwnd + 1; | 239 GetParam().fix_convex_mode ? current_cwnd : current_cwnd + 1; |
| 193 // Initialize the state. | 240 // Initialize the state. |
| 194 clock_.AdvanceTime(one_ms_); | 241 clock_.AdvanceTime(one_ms_); |
| 195 EXPECT_EQ(expected_cwnd, cubic_.CongestionWindowAfterAck( | 242 EXPECT_EQ(expected_cwnd, cubic_.CongestionWindowAfterAck( |
| 196 current_cwnd, rtt_min, clock_.ApproximateNow())); | 243 current_cwnd, rtt_min, clock_.ApproximateNow())); |
| 197 expected_cwnd = static_cast<QuicPacketCount>(current_cwnd * kNConnectionBeta); | 244 expected_cwnd = static_cast<QuicPacketCount>(current_cwnd * kNConnectionBeta); |
| 198 EXPECT_EQ(expected_cwnd, | 245 EXPECT_EQ(expected_cwnd, |
| 199 cubic_.CongestionWindowAfterPacketLoss(current_cwnd)); | 246 cubic_.CongestionWindowAfterPacketLoss(current_cwnd)); |
| 200 current_cwnd = expected_cwnd; | 247 current_cwnd = expected_cwnd; |
| 201 // First update after loss to initialize the epoch. | 248 // First update after loss to initialize the epoch. |
| 202 current_cwnd = cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min, | 249 current_cwnd = cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min, |
| 203 clock_.ApproximateNow()); | 250 clock_.ApproximateNow()); |
| 204 // Cubic phase. | 251 // Cubic phase. |
| 205 for (int i = 0; i < 40; ++i) { | 252 for (int i = 0; i < 40; ++i) { |
| 206 clock_.AdvanceTime(hundred_ms_); | 253 clock_.AdvanceTime(hundred_ms_); |
| 207 current_cwnd = cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min, | 254 current_cwnd = cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min, |
| 208 clock_.ApproximateNow()); | 255 clock_.ApproximateNow()); |
| 209 } | 256 } |
| 210 expected_cwnd = 399; | 257 expected_cwnd = 399; |
| 211 EXPECT_EQ(expected_cwnd, current_cwnd); | 258 EXPECT_EQ(expected_cwnd, current_cwnd); |
| 212 } | 259 } |
| 213 | 260 |
| 214 } // namespace test | 261 } // namespace test |
| 215 } // namespace net | 262 } // namespace net |
| OLD | NEW |