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
13 namespace net {
14
15 // Constants based on TCP defaults.
16 // The following constants are in 2^10 fractions of a second instead of ms to
17 // allow a 10 shift right to divide.
18 const int kCubeScale = 40; // 1024*1024^3 (first 1024 is from 0.100^3)
19 // where 0.100 is 100 ms which is the scaling
20 // round trip time.
21 const int kCubeCongestionWindowScale = 410;
22 const uint64 kCubeFactor = (GG_UINT64_C(1) << kCubeScale) /
23 kCubeCongestionWindowScale;
24 const uint32 kBetaSPDY = 939; // Back off factor after loss for SPDY, reduces
25 // the CWND by 1/12th.
26 const uint32 kBetaLastMax = 871; // Additional back off factor after loss for
27 // the stored max value.
28
29 namespace {
30 // Find last bit in a 64-bit word.
FindMostSignificantBit(uint64 x)31 int FindMostSignificantBit(uint64 x) {
32 if (!x) {
33 return 0;
34 }
35 int r = 0;
36 if (x & 0xffffffff00000000ull) {
37 x >>= 32;
38 r += 32;
39 }
40 if (x & 0xffff0000u) {
41 x >>= 16;
42 r += 16;
43 }
44 if (x & 0xff00u) {
45 x >>= 8;
46 r += 8;
47 }
48 if (x & 0xf0u) {
49 x >>= 4;
50 r += 4;
51 }
52 if (x & 0xcu) {
53 x >>= 2;
54 r += 2;
55 }
56 if (x & 0x02u) {
57 x >>= 1;
58 r++;
59 }
60 if (x & 0x01u) {
61 r++;
62 }
63 return r;
64 }
65
66 // 6 bits table [0..63]
67 const uint32 cube_root_table[] = {
68 0, 54, 54, 54, 118, 118, 118, 118, 123, 129, 134, 138, 143, 147, 151,
69 156, 157, 161, 164, 168, 170, 173, 176, 179, 181, 185, 187, 190, 192, 194,
70 197, 199, 200, 202, 204, 206, 209, 211, 213, 215, 217, 219, 221, 222, 224,
71 225, 227, 229, 231, 232, 234, 236, 237, 239, 240, 242, 244, 245, 246, 248,
72 250, 251, 252, 254
73 };
74 } // namespace
75
Cubic(const QuicClock * clock)76 Cubic::Cubic(const QuicClock* clock)
77 : clock_(clock),
78 epoch_(QuicTime::Zero()),
79 last_update_time_(QuicTime::Zero()) {
80 Reset();
81 }
82
83 // Calculate the cube root using a table lookup followed by one Newton-Raphson
84 // iteration.
CubeRoot(uint64 a)85 uint32 Cubic::CubeRoot(uint64 a) {
86 uint32 msb = FindMostSignificantBit(a);
87 DCHECK_LE(msb, 64u);
88
89 if (msb < 7) {
90 // MSB in our table.
91 return ((cube_root_table[static_cast<uint32>(a)]) + 31) >> 6;
92 }
93 // MSB 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ...
94 // cubic_shift 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ...
95 uint32 cubic_shift = (msb - 4);
96 cubic_shift = ((cubic_shift * 342) >> 10); // Div by 3, biased high.
97
98 // 4 to 6 bits accuracy depending on MSB.
99 uint32 down_shifted_to_6bit = (a >> (cubic_shift * 3));
100 uint64 root = ((cube_root_table[down_shifted_to_6bit] + 10) << cubic_shift)
101 >> 6;
102
103 // Make one Newton-Raphson iteration.
104 // Since x has an error (inaccuracy due to the use of fix point) we get a
105 // more accurate result by doing x * (x - 1) instead of x * x.
106 root = 2 * root + (a / (root * (root - 1)));
107 root = ((root * 341) >> 10); // Div by 3, biased low.
108 return static_cast<uint32>(root);
109 }
110
Reset()111 void Cubic::Reset() {
112 epoch_ = QuicTime::Zero(); // Reset time.
113 last_update_time_ = QuicTime::Zero(); // Reset time.
114 last_congestion_window_ = 0;
115 last_max_congestion_window_ = 0;
116 acked_packets_count_ = 0;
117 estimated_tcp_congestion_window_ = 0;
118 origin_point_congestion_window_ = 0;
119 time_to_origin_point_ = 0;
120 last_target_congestion_window_ = 0;
121 }
122
CongestionWindowAfterPacketLoss(QuicTcpCongestionWindow current_congestion_window)123 QuicTcpCongestionWindow Cubic::CongestionWindowAfterPacketLoss(
124 QuicTcpCongestionWindow current_congestion_window) {
125 if (current_congestion_window < last_max_congestion_window_) {
126 // We never reached the old max, so assume we are competing with another
127 // flow. Use our extra back off factor to allow the other flow to go up.
128 last_max_congestion_window_ =
129 (kBetaLastMax * current_congestion_window) >> 10;
130 } else {
131 last_max_congestion_window_ = current_congestion_window;
132 }
133 epoch_ = QuicTime::Zero(); // Reset time.
134 return (current_congestion_window * kBetaSPDY) >> 10;
135 }
136
CongestionWindowAfterAck(QuicTcpCongestionWindow current_congestion_window,QuicTime::Delta delay_min)137 QuicTcpCongestionWindow Cubic::CongestionWindowAfterAck(
138 QuicTcpCongestionWindow current_congestion_window,
139 QuicTime::Delta delay_min) {
140 acked_packets_count_ += 1; // Packets acked.
141 QuicTime current_time = clock_->ApproximateNow();
142
143 // Cubic is "independent" of RTT, the update is limited by the time elapsed.
144 if (last_congestion_window_ == current_congestion_window &&
145 (current_time.Subtract(last_update_time_) <= MaxCubicTimeInterval())) {
146 return std::max(last_target_congestion_window_,
147 estimated_tcp_congestion_window_);
148 }
149 last_congestion_window_ = current_congestion_window;
150 last_update_time_ = current_time;
151
152 if (!epoch_.IsInitialized()) {
153 // First ACK after a loss event.
154 DVLOG(1) << "Start of epoch";
155 epoch_ = current_time; // Start of epoch.
156 acked_packets_count_ = 1; // Reset count.
157 // Reset estimated_tcp_congestion_window_ to be in sync with cubic.
158 estimated_tcp_congestion_window_ = current_congestion_window;
159 if (last_max_congestion_window_ <= current_congestion_window) {
160 time_to_origin_point_ = 0;
161 origin_point_congestion_window_ = current_congestion_window;
162 } else {
163 time_to_origin_point_ = CubeRoot(kCubeFactor *
164 (last_max_congestion_window_ - current_congestion_window));
165 origin_point_congestion_window_ =
166 last_max_congestion_window_;
167 }
168 }
169 // Change the time unit from microseconds to 2^10 fractions per second. Take
170 // the round trip time in account. This is done to allow us to use shift as a
171 // divide operator.
172 int64 elapsed_time =
173 (current_time.Add(delay_min).Subtract(epoch_).ToMicroseconds() << 10) /
174 base::Time::kMicrosecondsPerSecond;
175
176 int64 offset = time_to_origin_point_ - elapsed_time;
177 QuicTcpCongestionWindow delta_congestion_window = (kCubeCongestionWindowScale
178 * offset * offset * offset) >> kCubeScale;
179
180 QuicTcpCongestionWindow target_congestion_window =
181 origin_point_congestion_window_ - delta_congestion_window;
182
183 // We have a new cubic congestion window.
184 last_target_congestion_window_ = target_congestion_window;
185
186 // Update estimated TCP congestion_window.
187 // Note: we do a normal Reno congestion avoidance calculation not the
188 // calculation described in section 3.3 TCP-friendly region of the document.
189 while (acked_packets_count_ >= estimated_tcp_congestion_window_) {
190 acked_packets_count_ -= estimated_tcp_congestion_window_;
191 estimated_tcp_congestion_window_++;
192 }
193 // Compute target congestion_window based on cubic target and estimated TCP
194 // congestion_window, use highest (fastest).
195 if (target_congestion_window < estimated_tcp_congestion_window_) {
196 target_congestion_window = estimated_tcp_congestion_window_;
197 }
198 DVLOG(1) << "Target congestion_window:" << target_congestion_window;
199 return target_congestion_window;
200 }
201
202 } // namespace net
203