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 "base/basictypes.h"
6#include "base/logging.h"
7#include "net/quic/congestion_control/cubic.h"
8#include "net/quic/quic_connection_stats.h"
9#include "net/quic/test_tools/mock_clock.h"
10#include "testing/gtest/include/gtest/gtest.h"
11
12namespace net {
13namespace test {
14
15const float kBeta = 0.7f;  // Default Cubic backoff factor.
16const uint32 kNumConnections = 2;
17const float kNConnectionBeta = (kNumConnections - 1 + kBeta) / kNumConnections;
18const float kNConnectionAlpha = 3 * kNumConnections * kNumConnections *
19      (1 - kNConnectionBeta) / (1 + kNConnectionBeta);
20
21class CubicTest : public ::testing::Test {
22 protected:
23  CubicTest()
24      : one_ms_(QuicTime::Delta::FromMilliseconds(1)),
25        hundred_ms_(QuicTime::Delta::FromMilliseconds(100)),
26        cubic_(&clock_, &stats_) {
27  }
28  const QuicTime::Delta one_ms_;
29  const QuicTime::Delta hundred_ms_;
30  MockClock clock_;
31  QuicConnectionStats stats_;
32  Cubic cubic_;
33};
34
35TEST_F(CubicTest, AboveOrigin) {
36  // Convex growth.
37  const QuicTime::Delta rtt_min = hundred_ms_;
38  uint32 current_cwnd = 10;
39  uint32 expected_cwnd = current_cwnd + 1;
40  // Initialize the state.
41  clock_.AdvanceTime(one_ms_);
42  EXPECT_EQ(expected_cwnd,
43            cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min));
44  current_cwnd = expected_cwnd;
45  // Normal TCP phase.
46  for (int i = 0; i < 48; ++i) {
47    for (uint32 n = 1; n < current_cwnd / kNConnectionAlpha; ++n) {
48      // Call once per ACK.
49      EXPECT_NEAR(current_cwnd,
50                  cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min), 1);
51    }
52    clock_.AdvanceTime(hundred_ms_);
53    current_cwnd = cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min);
54    EXPECT_NEAR(expected_cwnd, current_cwnd, 1);
55    expected_cwnd++;
56  }
57  // Cubic phase.
58  for (int i = 0; i < 52; ++i) {
59    for (uint32 n = 1; n < current_cwnd; ++n) {
60      // Call once per ACK.
61      EXPECT_EQ(current_cwnd,
62                cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min));
63    }
64    clock_.AdvanceTime(hundred_ms_);
65    current_cwnd = cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min);
66  }
67  // Total time elapsed so far; add min_rtt (0.1s) here as well.
68  float elapsed_time_s = 10.0f + 0.1f;
69  // |expected_cwnd| is initial value of cwnd + K * t^3, where K = 0.4.
70  expected_cwnd = 11 + (elapsed_time_s * elapsed_time_s * elapsed_time_s * 410)
71      / 1024;
72  EXPECT_EQ(expected_cwnd, current_cwnd);
73}
74
75TEST_F(CubicTest, CwndIncreaseStatsDuringConvexRegion) {
76  const QuicTime::Delta rtt_min = hundred_ms_;
77  uint32 current_cwnd = 10;
78  uint32 expected_cwnd = current_cwnd + 1;
79  // Initialize controller state.
80  clock_.AdvanceTime(one_ms_);
81  expected_cwnd = cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min);
82  current_cwnd = expected_cwnd;
83  // Testing Reno mode increase.
84  for (int i = 0; i < 48; ++i) {
85    for (uint32 n = 1; n < current_cwnd / kNConnectionAlpha; ++n) {
86      // Call once per ACK, causing cwnd growth in Reno mode.
87      cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min);
88    }
89    // Advance current time so that cwnd update is allowed to happen by Cubic.
90    clock_.AdvanceTime(hundred_ms_);
91    current_cwnd = cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min);
92    EXPECT_NEAR(expected_cwnd - 10, stats_.cwnd_increase_congestion_avoidance,
93                1);
94    EXPECT_NEAR(1u, stats_.cwnd_increase_cubic_mode, 1);
95    expected_cwnd++;
96  }
97  uint32 old_cwnd = current_cwnd;
98  stats_.cwnd_increase_cubic_mode = 0;
99  stats_.cwnd_increase_congestion_avoidance = 0;
100
101  // Testing Cubic mode increase.
102  for (int i = 0; i < 52; ++i) {
103    for (uint32 n = 1; n < current_cwnd; ++n) {
104      // Call once per ACK.
105      cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min);
106    }
107    clock_.AdvanceTime(hundred_ms_);
108    current_cwnd = cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min);
109  }
110  // Total time elapsed so far; add min_rtt (0.1s) here as well.
111  float elapsed_time_s = 10.0f + 0.1f;
112  // |expected_cwnd| is initial value of cwnd + K * t^3, where K = 0.4.
113  expected_cwnd = 11 + (elapsed_time_s * elapsed_time_s * elapsed_time_s * 410)
114      / 1024;
115  EXPECT_EQ(expected_cwnd - old_cwnd, stats_.cwnd_increase_cubic_mode);
116  EXPECT_EQ(expected_cwnd - old_cwnd,
117            stats_.cwnd_increase_congestion_avoidance);
118}
119
120
121TEST_F(CubicTest, LossEvents) {
122  const QuicTime::Delta rtt_min = hundred_ms_;
123  uint32 current_cwnd = 422;
124  uint32 expected_cwnd = current_cwnd + 1;
125  // Initialize the state.
126  clock_.AdvanceTime(one_ms_);
127  EXPECT_EQ(expected_cwnd,
128            cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min));
129  expected_cwnd = static_cast<int>(current_cwnd * kNConnectionBeta);
130  EXPECT_EQ(expected_cwnd,
131            cubic_.CongestionWindowAfterPacketLoss(current_cwnd));
132  expected_cwnd = static_cast<int>(current_cwnd * kNConnectionBeta);
133  EXPECT_EQ(expected_cwnd,
134            cubic_.CongestionWindowAfterPacketLoss(current_cwnd));
135}
136
137TEST_F(CubicTest, BelowOrigin) {
138  // Concave growth.
139  const QuicTime::Delta rtt_min = hundred_ms_;
140  uint32 current_cwnd = 422;
141  uint32 expected_cwnd = current_cwnd + 1;
142  // Initialize the state.
143  clock_.AdvanceTime(one_ms_);
144  EXPECT_EQ(expected_cwnd,
145            cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min));
146  expected_cwnd = static_cast<int>(current_cwnd * kNConnectionBeta);
147  EXPECT_EQ(expected_cwnd,
148            cubic_.CongestionWindowAfterPacketLoss(current_cwnd));
149  current_cwnd = expected_cwnd;
150  // First update after loss to initialize the epoch.
151  current_cwnd = cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min);
152  uint32 old_cwnd =  current_cwnd;
153  // Cubic phase.
154  stats_.cwnd_increase_cubic_mode = 0;
155  stats_.cwnd_increase_congestion_avoidance = 0;
156  for (int i = 0; i < 40 ; ++i) {
157    clock_.AdvanceTime(hundred_ms_);
158    current_cwnd = cubic_.CongestionWindowAfterAck(current_cwnd, rtt_min);
159  }
160  expected_cwnd = 422;
161  EXPECT_EQ(expected_cwnd, current_cwnd);
162  EXPECT_EQ(expected_cwnd - old_cwnd, stats_.cwnd_increase_cubic_mode);
163  EXPECT_EQ(expected_cwnd - old_cwnd,
164            stats_.cwnd_increase_congestion_avoidance);
165}
166
167}  // namespace test
168}  // namespace net
169