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/congestion_control/cubic.h" | 5 #include "net/quic/congestion_control/cubic.h" |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
8 | 8 |
9 #include "base/basictypes.h" | 9 #include "base/basictypes.h" |
10 #include "base/logging.h" | 10 #include "base/logging.h" |
11 #include "base/time/time.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; |
12 | 16 |
13 namespace net { | 17 namespace net { |
14 | 18 |
| 19 namespace { |
15 // Constants based on TCP defaults. | 20 // Constants based on TCP defaults. |
16 // The following constants are in 2^10 fractions of a second instead of ms to | 21 // The following constants are in 2^10 fractions of a second instead of ms to |
17 // allow a 10 shift right to divide. | 22 // allow a 10 shift right to divide. |
18 const int kCubeScale = 40; // 1024*1024^3 (first 1024 is from 0.100^3) | 23 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 | 24 // where 0.100 is 100 ms which is the scaling |
20 // round trip time. | 25 // round trip time. |
21 const int kCubeCongestionWindowScale = 410; | 26 const int kCubeCongestionWindowScale = 410; |
22 const uint64 kCubeFactor = (GG_UINT64_C(1) << kCubeScale) / | 27 const uint64 kCubeFactor = (GG_UINT64_C(1) << kCubeScale) / |
23 kCubeCongestionWindowScale; | 28 kCubeCongestionWindowScale; |
24 const uint32 kBetaSPDY = 939; // Back off factor after loss for SPDY, reduces | 29 const uint32 kBetaSPDY = 939; // Back off factor after loss for SPDY, reduces |
25 // the CWND by 1/12th. | 30 // the CWND by 1/12th. |
26 const uint32 kBetaLastMax = 871; // Additional back off factor after loss for | 31 const uint32 kBetaLastMax = 871; // Additional back off factor after loss for |
27 // the stored max value. | 32 // the stored max value. |
28 | |
29 namespace { | |
30 // Find last bit in a 64-bit word. | |
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 | 33 } // namespace |
75 | 34 |
76 Cubic::Cubic(const QuicClock* clock) | 35 Cubic::Cubic(const QuicClock* clock) |
77 : clock_(clock), | 36 : clock_(clock), |
78 epoch_(QuicTime::Zero()), | 37 epoch_(QuicTime::Zero()), |
79 last_update_time_(QuicTime::Zero()) { | 38 last_update_time_(QuicTime::Zero()) { |
80 Reset(); | 39 Reset(); |
81 } | 40 } |
82 | 41 |
83 // Calculate the cube root using a table lookup followed by one Newton-Raphson | |
84 // iteration. | |
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 | |
111 void Cubic::Reset() { | 42 void Cubic::Reset() { |
112 epoch_ = QuicTime::Zero(); // Reset time. | 43 epoch_ = QuicTime::Zero(); // Reset time. |
113 last_update_time_ = QuicTime::Zero(); // Reset time. | 44 last_update_time_ = QuicTime::Zero(); // Reset time. |
114 last_congestion_window_ = 0; | 45 last_congestion_window_ = 0; |
115 last_max_congestion_window_ = 0; | 46 last_max_congestion_window_ = 0; |
116 acked_packets_count_ = 0; | 47 acked_packets_count_ = 0; |
117 estimated_tcp_congestion_window_ = 0; | 48 estimated_tcp_congestion_window_ = 0; |
118 origin_point_congestion_window_ = 0; | 49 origin_point_congestion_window_ = 0; |
119 time_to_origin_point_ = 0; | 50 time_to_origin_point_ = 0; |
120 last_target_congestion_window_ = 0; | 51 last_target_congestion_window_ = 0; |
(...skipping 15 matching lines...) Expand all Loading... |
136 | 67 |
137 QuicTcpCongestionWindow Cubic::CongestionWindowAfterAck( | 68 QuicTcpCongestionWindow Cubic::CongestionWindowAfterAck( |
138 QuicTcpCongestionWindow current_congestion_window, | 69 QuicTcpCongestionWindow current_congestion_window, |
139 QuicTime::Delta delay_min) { | 70 QuicTime::Delta delay_min) { |
140 acked_packets_count_ += 1; // Packets acked. | 71 acked_packets_count_ += 1; // Packets acked. |
141 QuicTime current_time = clock_->ApproximateNow(); | 72 QuicTime current_time = clock_->ApproximateNow(); |
142 | 73 |
143 // Cubic is "independent" of RTT, the update is limited by the time elapsed. | 74 // Cubic is "independent" of RTT, the update is limited by the time elapsed. |
144 if (last_congestion_window_ == current_congestion_window && | 75 if (last_congestion_window_ == current_congestion_window && |
145 (current_time.Subtract(last_update_time_) <= MaxCubicTimeInterval())) { | 76 (current_time.Subtract(last_update_time_) <= MaxCubicTimeInterval())) { |
146 return std::max(last_target_congestion_window_, | 77 return max(last_target_congestion_window_, |
147 estimated_tcp_congestion_window_); | 78 estimated_tcp_congestion_window_); |
148 } | 79 } |
149 last_congestion_window_ = current_congestion_window; | 80 last_congestion_window_ = current_congestion_window; |
150 last_update_time_ = current_time; | 81 last_update_time_ = current_time; |
151 | 82 |
152 if (!epoch_.IsInitialized()) { | 83 if (!epoch_.IsInitialized()) { |
153 // First ACK after a loss event. | 84 // First ACK after a loss event. |
154 DVLOG(1) << "Start of epoch"; | 85 DVLOG(1) << "Start of epoch"; |
155 epoch_ = current_time; // Start of epoch. | 86 epoch_ = current_time; // Start of epoch. |
156 acked_packets_count_ = 1; // Reset count. | 87 acked_packets_count_ = 1; // Reset count. |
157 // Reset estimated_tcp_congestion_window_ to be in sync with cubic. | 88 // Reset estimated_tcp_congestion_window_ to be in sync with cubic. |
158 estimated_tcp_congestion_window_ = current_congestion_window; | 89 estimated_tcp_congestion_window_ = current_congestion_window; |
159 if (last_max_congestion_window_ <= current_congestion_window) { | 90 if (last_max_congestion_window_ <= current_congestion_window) { |
160 time_to_origin_point_ = 0; | 91 time_to_origin_point_ = 0; |
161 origin_point_congestion_window_ = current_congestion_window; | 92 origin_point_congestion_window_ = current_congestion_window; |
162 } else { | 93 } else { |
163 time_to_origin_point_ = CubeRoot(kCubeFactor * | 94 time_to_origin_point_ = CubeRoot::Root(kCubeFactor * |
164 (last_max_congestion_window_ - current_congestion_window)); | 95 (last_max_congestion_window_ - current_congestion_window)); |
165 origin_point_congestion_window_ = | 96 origin_point_congestion_window_ = |
166 last_max_congestion_window_; | 97 last_max_congestion_window_; |
167 } | 98 } |
168 } | 99 } |
169 // Change the time unit from microseconds to 2^10 fractions per second. Take | 100 // 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 | 101 // the round trip time in account. This is done to allow us to use shift as a |
171 // divide operator. | 102 // divide operator. |
172 int64 elapsed_time = | 103 int64 elapsed_time = |
173 (current_time.Add(delay_min).Subtract(epoch_).ToMicroseconds() << 10) / | 104 (current_time.Add(delay_min).Subtract(epoch_).ToMicroseconds() << 10) / |
(...skipping 19 matching lines...) Expand all Loading... |
193 // Compute target congestion_window based on cubic target and estimated TCP | 124 // Compute target congestion_window based on cubic target and estimated TCP |
194 // congestion_window, use highest (fastest). | 125 // congestion_window, use highest (fastest). |
195 if (target_congestion_window < estimated_tcp_congestion_window_) { | 126 if (target_congestion_window < estimated_tcp_congestion_window_) { |
196 target_congestion_window = estimated_tcp_congestion_window_; | 127 target_congestion_window = estimated_tcp_congestion_window_; |
197 } | 128 } |
198 DVLOG(1) << "Target congestion_window:" << target_congestion_window; | 129 DVLOG(1) << "Target congestion_window:" << target_congestion_window; |
199 return target_congestion_window; | 130 return target_congestion_window; |
200 } | 131 } |
201 | 132 |
202 } // namespace net | 133 } // namespace net |
OLD | NEW |