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 |