| 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 |