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 "base/basictypes.h" | 7 #include "base/basictypes.h" |
8 #include "base/logging.h" | 8 #include "base/logging.h" |
9 #include "base/time.h" | 9 #include "base/time.h" |
10 | 10 |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
63 const uint32 cube_root_table[] = { | 63 const uint32 cube_root_table[] = { |
64 0, 54, 54, 54, 118, 118, 118, 118, 123, 129, 134, 138, 143, 147, 151, | 64 0, 54, 54, 54, 118, 118, 118, 118, 123, 129, 134, 138, 143, 147, 151, |
65 156, 157, 161, 164, 168, 170, 173, 176, 179, 181, 185, 187, 190, 192, 194, | 65 156, 157, 161, 164, 168, 170, 173, 176, 179, 181, 185, 187, 190, 192, 194, |
66 197, 199, 200, 202, 204, 206, 209, 211, 213, 215, 217, 219, 221, 222, 224, | 66 197, 199, 200, 202, 204, 206, 209, 211, 213, 215, 217, 219, 221, 222, 224, |
67 225, 227, 229, 231, 232, 234, 236, 237, 239, 240, 242, 244, 245, 246, 248, | 67 225, 227, 229, 231, 232, 234, 236, 237, 239, 240, 242, 244, 245, 246, 248, |
68 250, 251, 252, 254 | 68 250, 251, 252, 254 |
69 }; | 69 }; |
70 } // namespace | 70 } // namespace |
71 | 71 |
72 Cubic::Cubic(const QuicClock* clock) | 72 Cubic::Cubic(const QuicClock* clock) |
73 : clock_(clock) { | 73 : clock_(clock), |
| 74 epoch_(QuicTime::Zero()), |
| 75 last_update_time_(QuicTime::Zero()) { |
74 Reset(); | 76 Reset(); |
75 } | 77 } |
76 | 78 |
77 // Calculate the cube root using a table lookup followed by one Newton-Raphson | 79 // Calculate the cube root using a table lookup followed by one Newton-Raphson |
78 // iteration. | 80 // iteration. |
79 uint32 Cubic::CubeRoot(uint64 a) { | 81 uint32 Cubic::CubeRoot(uint64 a) { |
80 uint32 msb = FindMostSignificantBit(a); | 82 uint32 msb = FindMostSignificantBit(a); |
81 DCHECK_LE(msb, 64u); | 83 DCHECK_LE(msb, 64u); |
82 | 84 |
83 if (msb < 7) { | 85 if (msb < 7) { |
(...skipping 12 matching lines...) Expand all Loading... |
96 | 98 |
97 // Make one Newton-Raphson iteration. | 99 // Make one Newton-Raphson iteration. |
98 // Since x has an error (inaccuracy due to the use of fix point) we get a | 100 // Since x has an error (inaccuracy due to the use of fix point) we get a |
99 // more accurate result by doing x * (x - 1) instead of x * x. | 101 // more accurate result by doing x * (x - 1) instead of x * x. |
100 root = 2 * root + (a / (root * (root - 1))); | 102 root = 2 * root + (a / (root * (root - 1))); |
101 root = ((root * 341) >> 10); // Div by 3, biased low. | 103 root = ((root * 341) >> 10); // Div by 3, biased low. |
102 return static_cast<uint32>(root); | 104 return static_cast<uint32>(root); |
103 } | 105 } |
104 | 106 |
105 void Cubic::Reset() { | 107 void Cubic::Reset() { |
106 epoch_ = QuicTime(); // Reset time. | 108 epoch_ = QuicTime::Zero(); // Reset time. |
107 last_update_time_ = QuicTime(); // Reset time. | 109 last_update_time_ = QuicTime::Zero(); // Reset time. |
108 last_congestion_window_ = 0; | 110 last_congestion_window_ = 0; |
109 last_max_congestion_window_ = 0; | 111 last_max_congestion_window_ = 0; |
110 acked_packets_count_ = 0; | 112 acked_packets_count_ = 0; |
111 estimated_tcp_congestion_window_ = 0; | 113 estimated_tcp_congestion_window_ = 0; |
112 origin_point_congestion_window_ = 0; | 114 origin_point_congestion_window_ = 0; |
113 time_to_origin_point_ = 0; | 115 time_to_origin_point_ = 0; |
114 last_target_congestion_window_ = 0; | 116 last_target_congestion_window_ = 0; |
115 } | 117 } |
116 | 118 |
117 QuicTcpCongestionWindow Cubic::CongestionWindowAfterPacketLoss( | 119 QuicTcpCongestionWindow Cubic::CongestionWindowAfterPacketLoss( |
118 QuicTcpCongestionWindow current_congestion_window) { | 120 QuicTcpCongestionWindow current_congestion_window) { |
119 if (current_congestion_window < last_max_congestion_window_) { | 121 if (current_congestion_window < last_max_congestion_window_) { |
120 // We never reached the old max, so assume we are competing with another | 122 // We never reached the old max, so assume we are competing with another |
121 // flow. Use our extra back off factor to allow the other flow to go up. | 123 // flow. Use our extra back off factor to allow the other flow to go up. |
122 last_max_congestion_window_ = | 124 last_max_congestion_window_ = |
123 (kBetaLastMax * current_congestion_window) >> 10; | 125 (kBetaLastMax * current_congestion_window) >> 10; |
124 } else { | 126 } else { |
125 last_max_congestion_window_ = current_congestion_window; | 127 last_max_congestion_window_ = current_congestion_window; |
126 } | 128 } |
127 epoch_ = QuicTime(); // Reset time. | 129 epoch_ = QuicTime::Zero(); // Reset time. |
128 return (current_congestion_window * kBeta) >> 10; | 130 return (current_congestion_window * kBeta) >> 10; |
129 } | 131 } |
130 | 132 |
131 QuicTcpCongestionWindow Cubic::CongestionWindowAfterAck( | 133 QuicTcpCongestionWindow Cubic::CongestionWindowAfterAck( |
132 QuicTcpCongestionWindow current_congestion_window, | 134 QuicTcpCongestionWindow current_congestion_window, |
133 QuicTime::Delta delay_min) { | 135 QuicTime::Delta delay_min) { |
134 acked_packets_count_ += 1; // Packets acked. | 136 acked_packets_count_ += 1; // Packets acked. |
135 QuicTime current_time = clock_->Now(); | 137 QuicTime current_time = clock_->Now(); |
136 | 138 |
137 // Cubic is "independent" of RTT, the update is limited by the time elapsed. | 139 // Cubic is "independent" of RTT, the update is limited by the time elapsed. |
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
188 // Compute target congestion_window based on cubic target and estimated TCP | 190 // Compute target congestion_window based on cubic target and estimated TCP |
189 // congestion_window, use highest (fastest). | 191 // congestion_window, use highest (fastest). |
190 if (target_congestion_window < estimated_tcp_congestion_window_) { | 192 if (target_congestion_window < estimated_tcp_congestion_window_) { |
191 target_congestion_window = estimated_tcp_congestion_window_; | 193 target_congestion_window = estimated_tcp_congestion_window_; |
192 } | 194 } |
193 DLOG(INFO) << "Target congestion_window:" << target_congestion_window; | 195 DLOG(INFO) << "Target congestion_window:" << target_congestion_window; |
194 return target_congestion_window; | 196 return target_congestion_window; |
195 } | 197 } |
196 | 198 |
197 } // namespace net | 199 } // namespace net |
OLD | NEW |