| 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" | 12 #include "net/quic/congestion_control/cube_root.h" |
| 13 #include "net/quic/quic_protocol.h" | 13 #include "net/quic/quic_protocol.h" |
| 14 | 14 |
| 15 using std::max; | 15 using std::max; |
| 16 | 16 |
| 17 namespace net { | 17 namespace net { |
| 18 | 18 |
| 19 namespace { | 19 namespace { |
| 20 | 20 |
| 21 // Constants based on TCP defaults. | 21 // Constants based on TCP defaults. |
| 22 // The following constants are in 2^10 fractions of a second instead of ms to | 22 // The following constants are in 2^10 fractions of a second instead of ms to |
| 23 // allow a 10 shift right to divide. | 23 // allow a 10 shift right to divide. |
| 24 const int kCubeScale = 40; // 1024*1024^3 (first 1024 is from 0.100^3) | 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 | 25 // where 0.100 is 100 ms which is the scaling |
| 26 // round trip time. | 26 // round trip time. |
| 27 const int kCubeCongestionWindowScale = 410; | 27 const int kCubeCongestionWindowScale = 410; |
| 28 const uint64 kCubeFactor = (GG_UINT64_C(1) << kCubeScale) / | 28 const uint64 kCubeFactor = |
| 29 kCubeCongestionWindowScale; | 29 (GG_UINT64_C(1) << kCubeScale) / kCubeCongestionWindowScale; |
| 30 | 30 |
| 31 const uint32 kNumConnections = 2; | 31 const uint32 kNumConnections = 2; |
| 32 const float kBeta = 0.7f; // Default Cubic backoff factor. | 32 const float kBeta = 0.7f; // Default Cubic backoff factor. |
| 33 // Additional backoff factor when loss occurs in the concave part of the Cubic | 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 | 34 // curve. This additional backoff factor is expected to give up bandwidth to |
| 35 // new concurrent flows and speed up convergence. | 35 // new concurrent flows and speed up convergence. |
| 36 const float kBetaLastMax = 0.85f; | 36 const float kBetaLastMax = 0.85f; |
| 37 | 37 |
| 38 // kNConnectionBeta is the backoff factor after loss for our N-connection | 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 | 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: | 40 // connections on a single loss event. The effective multiplier is computed as: |
| 41 const float kNConnectionBeta = (kNumConnections - 1 + kBeta) / kNumConnections; | 41 const float kNConnectionBeta = (kNumConnections - 1 + kBeta) / kNumConnections; |
| 42 | 42 |
| 43 // TCPFriendly alpha is described in Section 3.3 of the CUBIC paper. Note that | 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. | 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: | 45 // We derive the equivalent kNConnectionAlpha for an N-connection emulation as: |
| 46 const float kNConnectionAlpha = 3 * kNumConnections * kNumConnections * | 46 const float kNConnectionAlpha = 3 * kNumConnections * kNumConnections * |
| 47 (1 - kNConnectionBeta) / (1 + kNConnectionBeta); | 47 (1 - kNConnectionBeta) / (1 + kNConnectionBeta); |
| 48 // TODO(jri): Compute kNConnectionBeta and kNConnectionAlpha from | 48 // TODO(jri): Compute kNConnectionBeta and kNConnectionAlpha from |
| 49 // number of active streams. | 49 // number of active streams. |
| 50 | 50 |
| 51 } // namespace | 51 } // namespace |
| 52 | 52 |
| 53 Cubic::Cubic(const QuicClock* clock, QuicConnectionStats* stats) | 53 Cubic::Cubic(const QuicClock* clock, QuicConnectionStats* stats) |
| 54 : clock_(clock), | 54 : clock_(clock), |
| 55 epoch_(QuicTime::Zero()), | 55 epoch_(QuicTime::Zero()), |
| 56 last_update_time_(QuicTime::Zero()), | 56 last_update_time_(QuicTime::Zero()), |
| 57 stats_(stats) { | 57 stats_(stats) { |
| 58 Reset(); | 58 Reset(); |
| 59 } | 59 } |
| 60 | 60 |
| 61 void Cubic::Reset() { | 61 void Cubic::Reset() { |
| 62 epoch_ = QuicTime::Zero(); // Reset time. | 62 epoch_ = QuicTime::Zero(); // Reset time. |
| 63 last_update_time_ = QuicTime::Zero(); // Reset time. | 63 last_update_time_ = QuicTime::Zero(); // Reset time. |
| 64 last_congestion_window_ = 0; | 64 last_congestion_window_ = 0; |
| 65 last_max_congestion_window_ = 0; | 65 last_max_congestion_window_ = 0; |
| 66 acked_packets_count_ = 0; | 66 acked_packets_count_ = 0; |
| 67 estimated_tcp_congestion_window_ = 0; | 67 estimated_tcp_congestion_window_ = 0; |
| 68 origin_point_congestion_window_ = 0; | 68 origin_point_congestion_window_ = 0; |
| 69 time_to_origin_point_ = 0; | 69 time_to_origin_point_ = 0; |
| 70 last_target_congestion_window_ = 0; | 70 last_target_congestion_window_ = 0; |
| 71 } | 71 } |
| 72 | 72 |
| 73 void Cubic::UpdateCongestionControlStats( | 73 void Cubic::UpdateCongestionControlStats( |
| 74 QuicTcpCongestionWindow new_cubic_mode_cwnd, | 74 QuicTcpCongestionWindow new_cubic_mode_cwnd, |
| 75 QuicTcpCongestionWindow new_reno_mode_cwnd) { | 75 QuicTcpCongestionWindow new_reno_mode_cwnd) { |
| 76 | 76 QuicTcpCongestionWindow highest_new_cwnd = |
| 77 QuicTcpCongestionWindow highest_new_cwnd = std::max(new_cubic_mode_cwnd, | 77 std::max(new_cubic_mode_cwnd, new_reno_mode_cwnd); |
| 78 new_reno_mode_cwnd); | |
| 79 if (last_congestion_window_ < highest_new_cwnd) { | 78 if (last_congestion_window_ < highest_new_cwnd) { |
| 80 // cwnd will increase to highest_new_cwnd. | 79 // cwnd will increase to highest_new_cwnd. |
| 81 stats_->cwnd_increase_congestion_avoidance += | 80 stats_->cwnd_increase_congestion_avoidance += |
| 82 highest_new_cwnd - last_congestion_window_; | 81 highest_new_cwnd - last_congestion_window_; |
| 83 if (new_cubic_mode_cwnd > new_reno_mode_cwnd) { | 82 if (new_cubic_mode_cwnd > new_reno_mode_cwnd) { |
| 84 // This cwnd increase is due to cubic mode. | 83 // This cwnd increase is due to cubic mode. |
| 85 stats_->cwnd_increase_cubic_mode += | 84 stats_->cwnd_increase_cubic_mode += |
| 86 new_cubic_mode_cwnd - last_congestion_window_; | 85 new_cubic_mode_cwnd - last_congestion_window_; |
| 87 } | 86 } |
| 88 } | 87 } |
| (...skipping 24 matching lines...) Expand all Loading... |
| 113 (current_time.Subtract(last_update_time_) <= MaxCubicTimeInterval())) { | 112 (current_time.Subtract(last_update_time_) <= MaxCubicTimeInterval())) { |
| 114 return max(last_target_congestion_window_, | 113 return max(last_target_congestion_window_, |
| 115 estimated_tcp_congestion_window_); | 114 estimated_tcp_congestion_window_); |
| 116 } | 115 } |
| 117 last_congestion_window_ = current_congestion_window; | 116 last_congestion_window_ = current_congestion_window; |
| 118 last_update_time_ = current_time; | 117 last_update_time_ = current_time; |
| 119 | 118 |
| 120 if (!epoch_.IsInitialized()) { | 119 if (!epoch_.IsInitialized()) { |
| 121 // First ACK after a loss event. | 120 // First ACK after a loss event. |
| 122 DVLOG(1) << "Start of epoch"; | 121 DVLOG(1) << "Start of epoch"; |
| 123 epoch_ = current_time; // Start of epoch. | 122 epoch_ = current_time; // Start of epoch. |
| 124 acked_packets_count_ = 1; // Reset count. | 123 acked_packets_count_ = 1; // Reset count. |
| 125 // Reset estimated_tcp_congestion_window_ to be in sync with cubic. | 124 // Reset estimated_tcp_congestion_window_ to be in sync with cubic. |
| 126 estimated_tcp_congestion_window_ = current_congestion_window; | 125 estimated_tcp_congestion_window_ = current_congestion_window; |
| 127 if (last_max_congestion_window_ <= current_congestion_window) { | 126 if (last_max_congestion_window_ <= current_congestion_window) { |
| 128 time_to_origin_point_ = 0; | 127 time_to_origin_point_ = 0; |
| 129 origin_point_congestion_window_ = current_congestion_window; | 128 origin_point_congestion_window_ = current_congestion_window; |
| 130 } else { | 129 } else { |
| 131 time_to_origin_point_ = CubeRoot::Root(kCubeFactor * | 130 time_to_origin_point_ = |
| 132 (last_max_congestion_window_ - current_congestion_window)); | 131 CubeRoot::Root(kCubeFactor * (last_max_congestion_window_ - |
| 133 origin_point_congestion_window_ = | 132 current_congestion_window)); |
| 134 last_max_congestion_window_; | 133 origin_point_congestion_window_ = last_max_congestion_window_; |
| 135 } | 134 } |
| 136 } | 135 } |
| 137 // Change the time unit from microseconds to 2^10 fractions per second. Take | 136 // 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 | 137 // the round trip time in account. This is done to allow us to use shift as a |
| 139 // divide operator. | 138 // divide operator. |
| 140 int64 elapsed_time = | 139 int64 elapsed_time = |
| 141 (current_time.Add(delay_min).Subtract(epoch_).ToMicroseconds() << 10) / | 140 (current_time.Add(delay_min).Subtract(epoch_).ToMicroseconds() << 10) / |
| 142 base::Time::kMicrosecondsPerSecond; | 141 base::Time::kMicrosecondsPerSecond; |
| 143 | 142 |
| 144 int64 offset = time_to_origin_point_ - elapsed_time; | 143 int64 offset = time_to_origin_point_ - elapsed_time; |
| 145 QuicTcpCongestionWindow delta_congestion_window = (kCubeCongestionWindowScale | 144 QuicTcpCongestionWindow delta_congestion_window = |
| 146 * offset * offset * offset) >> kCubeScale; | 145 (kCubeCongestionWindowScale * offset * offset * offset) >> kCubeScale; |
| 147 | 146 |
| 148 QuicTcpCongestionWindow target_congestion_window = | 147 QuicTcpCongestionWindow target_congestion_window = |
| 149 origin_point_congestion_window_ - delta_congestion_window; | 148 origin_point_congestion_window_ - delta_congestion_window; |
| 150 | 149 |
| 151 DCHECK_LT(0u, estimated_tcp_congestion_window_); | 150 DCHECK_LT(0u, estimated_tcp_congestion_window_); |
| 152 // With dynamic beta/alpha based on number of active streams, it is possible | 151 // 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_ | 152 // 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. | 153 // suddenly, leading to more than one iteration through the following loop. |
| 155 while (true) { | 154 while (true) { |
| 156 // Update estimated TCP congestion_window. | 155 // Update estimated TCP congestion_window. |
| (...skipping 17 matching lines...) Expand all Loading... |
| 174 // congestion_window, use highest (fastest). | 173 // congestion_window, use highest (fastest). |
| 175 if (target_congestion_window < estimated_tcp_congestion_window_) { | 174 if (target_congestion_window < estimated_tcp_congestion_window_) { |
| 176 target_congestion_window = estimated_tcp_congestion_window_; | 175 target_congestion_window = estimated_tcp_congestion_window_; |
| 177 } | 176 } |
| 178 | 177 |
| 179 DVLOG(1) << "Target congestion_window: " << target_congestion_window; | 178 DVLOG(1) << "Target congestion_window: " << target_congestion_window; |
| 180 return target_congestion_window; | 179 return target_congestion_window; |
| 181 } | 180 } |
| 182 | 181 |
| 183 } // namespace net | 182 } // namespace net |
| OLD | NEW |