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 "net/quic/congestion_control/cubic.h"
6
7 #include <algorithm>
8
9 #include "base/basictypes.h"
10 #include "base/logging.h"
11 #include "base/time/time.h"
12 #include "net/quic/congestion_control/cube_root.h"
13 #include "net/quic/quic_protocol.h"
14
15 using std::max;
16
17 namespace net {
18
19 namespace {
20
21 // Constants based on TCP defaults.
22 // The following constants are in 2^10 fractions of a second instead of ms to
23 // allow a 10 shift right to divide.
24 const int kCubeScale = 40; // 1024*1024^3 (first 1024 is from 0.100^3)
25 // where 0.100 is 100 ms which is the scaling
26 // round trip time.
27 const int kCubeCongestionWindowScale = 410;
28 const uint64 kCubeFactor = (GG_UINT64_C(1) << kCubeScale) /
29 kCubeCongestionWindowScale;
30
31 const uint32 kNumConnections = 2;
32 const float kBeta = 0.7f; // Default Cubic backoff factor.
33 // Additional backoff factor when loss occurs in the concave part of the Cubic
34 // curve. This additional backoff factor is expected to give up bandwidth to
35 // new concurrent flows and speed up convergence.
36 const float kBetaLastMax = 0.85f;
37
38 // kNConnectionBeta is the backoff factor after loss for our N-connection
39 // emulation, which emulates the effective backoff of an ensemble of N TCP-Reno
40 // connections on a single loss event. The effective multiplier is computed as:
41 const float kNConnectionBeta = (kNumConnections - 1 + kBeta) / kNumConnections;
42
43 // TCPFriendly alpha is described in Section 3.3 of the CUBIC paper. Note that
44 // kBeta here is a cwnd multiplier, and is equal to 1-beta from the CUBIC paper.
45 // We derive the equivalent kNConnectionAlpha for an N-connection emulation as:
46 const float kNConnectionAlpha = 3 * kNumConnections * kNumConnections *
47 (1 - kNConnectionBeta) / (1 + kNConnectionBeta);
48 // TODO(jri): Compute kNConnectionBeta and kNConnectionAlpha from
49 // number of active streams.
50
51 } // namespace
52
Cubic(const QuicClock * clock,QuicConnectionStats * stats)53 Cubic::Cubic(const QuicClock* clock, QuicConnectionStats* stats)
54 : clock_(clock),
55 epoch_(QuicTime::Zero()),
56 last_update_time_(QuicTime::Zero()),
57 stats_(stats) {
58 Reset();
59 }
60
Reset()61 void Cubic::Reset() {
62 epoch_ = QuicTime::Zero(); // Reset time.
63 last_update_time_ = QuicTime::Zero(); // Reset time.
64 last_congestion_window_ = 0;
65 last_max_congestion_window_ = 0;
66 acked_packets_count_ = 0;
67 estimated_tcp_congestion_window_ = 0;
68 origin_point_congestion_window_ = 0;
69 time_to_origin_point_ = 0;
70 last_target_congestion_window_ = 0;
71 }
72
UpdateCongestionControlStats(QuicTcpCongestionWindow new_cubic_mode_cwnd,QuicTcpCongestionWindow new_reno_mode_cwnd)73 void Cubic::UpdateCongestionControlStats(
74 QuicTcpCongestionWindow new_cubic_mode_cwnd,
75 QuicTcpCongestionWindow new_reno_mode_cwnd) {
76
77 QuicTcpCongestionWindow highest_new_cwnd = std::max(new_cubic_mode_cwnd,
78 new_reno_mode_cwnd);
79 if (last_congestion_window_ < highest_new_cwnd) {
80 // cwnd will increase to highest_new_cwnd.
81 stats_->cwnd_increase_congestion_avoidance +=
82 highest_new_cwnd - last_congestion_window_;
83 if (new_cubic_mode_cwnd > new_reno_mode_cwnd) {
84 // This cwnd increase is due to cubic mode.
85 stats_->cwnd_increase_cubic_mode +=
86 new_cubic_mode_cwnd - last_congestion_window_;
87 }
88 }
89 }
90
CongestionWindowAfterPacketLoss(QuicTcpCongestionWindow current_congestion_window)91 QuicTcpCongestionWindow Cubic::CongestionWindowAfterPacketLoss(
92 QuicTcpCongestionWindow current_congestion_window) {
93 if (current_congestion_window < last_max_congestion_window_) {
94 // We never reached the old max, so assume we are competing with another
95 // flow. Use our extra back off factor to allow the other flow to go up.
96 last_max_congestion_window_ =
97 static_cast<int>(kBetaLastMax * current_congestion_window);
98 } else {
99 last_max_congestion_window_ = current_congestion_window;
100 }
101 epoch_ = QuicTime::Zero(); // Reset time.
102 return static_cast<int>(current_congestion_window * kNConnectionBeta);
103 }
104
CongestionWindowAfterAck(QuicTcpCongestionWindow current_congestion_window,QuicTime::Delta delay_min)105 QuicTcpCongestionWindow Cubic::CongestionWindowAfterAck(
106 QuicTcpCongestionWindow current_congestion_window,
107 QuicTime::Delta delay_min) {
108 acked_packets_count_ += 1; // Packets acked.
109 QuicTime current_time = clock_->ApproximateNow();
110
111 // Cubic is "independent" of RTT, the update is limited by the time elapsed.
112 if (last_congestion_window_ == current_congestion_window &&
113 (current_time.Subtract(last_update_time_) <= MaxCubicTimeInterval())) {
114 return max(last_target_congestion_window_,
115 estimated_tcp_congestion_window_);
116 }
117 last_congestion_window_ = current_congestion_window;
118 last_update_time_ = current_time;
119
120 if (!epoch_.IsInitialized()) {
121 // First ACK after a loss event.
122 DVLOG(1) << "Start of epoch";
123 epoch_ = current_time; // Start of epoch.
124 acked_packets_count_ = 1; // Reset count.
125 // Reset estimated_tcp_congestion_window_ to be in sync with cubic.
126 estimated_tcp_congestion_window_ = current_congestion_window;
127 if (last_max_congestion_window_ <= current_congestion_window) {
128 time_to_origin_point_ = 0;
129 origin_point_congestion_window_ = current_congestion_window;
130 } else {
131 time_to_origin_point_ = CubeRoot::Root(kCubeFactor *
132 (last_max_congestion_window_ - current_congestion_window));
133 origin_point_congestion_window_ =
134 last_max_congestion_window_;
135 }
136 }
137 // Change the time unit from microseconds to 2^10 fractions per second. Take
138 // the round trip time in account. This is done to allow us to use shift as a
139 // divide operator.
140 int64 elapsed_time =
141 (current_time.Add(delay_min).Subtract(epoch_).ToMicroseconds() << 10) /
142 base::Time::kMicrosecondsPerSecond;
143
144 int64 offset = time_to_origin_point_ - elapsed_time;
145 QuicTcpCongestionWindow delta_congestion_window = (kCubeCongestionWindowScale
146 * offset * offset * offset) >> kCubeScale;
147
148 QuicTcpCongestionWindow target_congestion_window =
149 origin_point_congestion_window_ - delta_congestion_window;
150
151 DCHECK_LT(0u, estimated_tcp_congestion_window_);
152 // With dynamic beta/alpha based on number of active streams, it is possible
153 // for the required_ack_count to become much lower than acked_packets_count_
154 // suddenly, leading to more than one iteration through the following loop.
155 while (true) {
156 // Update estimated TCP congestion_window.
157 uint32 required_ack_count =
158 estimated_tcp_congestion_window_ / kNConnectionAlpha;
159 if (acked_packets_count_ < required_ack_count) {
160 break;
161 }
162 acked_packets_count_ -= required_ack_count;
163 estimated_tcp_congestion_window_++;
164 }
165
166 // Update cubic mode and reno mode stats in QuicConnectionStats.
167 UpdateCongestionControlStats(target_congestion_window,
168 estimated_tcp_congestion_window_);
169
170 // We have a new cubic congestion window.
171 last_target_congestion_window_ = target_congestion_window;
172
173 // Compute target congestion_window based on cubic target and estimated TCP
174 // congestion_window, use highest (fastest).
175 if (target_congestion_window < estimated_tcp_congestion_window_) {
176 target_congestion_window = estimated_tcp_congestion_window_;
177 }
178
179 DVLOG(1) << "Target congestion_window: " << target_congestion_window;
180 return target_congestion_window;
181 }
182
183 } // namespace net
184