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
3 // found in the LICENSE file.
5 #include "net/quic/congestion_control/tcp_cubic_sender.h"
9 #include "base/metrics/histogram.h"
10 #include "net/quic/congestion_control/rtt_stats.h"
11 #include "net/quic/crypto/crypto_protocol.h"
19 // Constants based on TCP defaults.
20 // The minimum cwnd based on RFC 3782 (TCP NewReno) for cwnd reductions on a
21 // fast retransmission. The cwnd after a timeout is still 1.
22 const QuicPacketCount kMinimumCongestionWindow
= 2;
23 const QuicByteCount kMaxSegmentSize
= kDefaultTCPMSS
;
24 const int64 kInitialCongestionWindow
= 10;
25 const int kMaxBurstLength
= 3;
28 TcpCubicSender::TcpCubicSender(
29 const QuicClock
* clock
,
30 const RttStats
* rtt_stats
,
32 QuicPacketCount max_tcp_congestion_window
,
33 QuicConnectionStats
* stats
)
34 : hybrid_slow_start_(clock
),
36 rtt_stats_(rtt_stats
),
40 congestion_window_count_(0),
41 receive_window_(kDefaultSocketReceiveBuffer
),
44 ack_count_since_loss_(0),
45 bytes_in_flight_before_loss_(0),
46 largest_sent_sequence_number_(0),
47 largest_acked_sequence_number_(0),
48 largest_sent_at_last_cutback_(0),
49 congestion_window_(kInitialCongestionWindow
),
50 previous_congestion_window_(0),
51 slowstart_threshold_(max_tcp_congestion_window
),
52 previous_slowstart_threshold_(0),
53 last_cutback_exited_slowstart_(false),
54 max_tcp_congestion_window_(max_tcp_congestion_window
) {
57 TcpCubicSender::~TcpCubicSender() {
58 UMA_HISTOGRAM_COUNTS("Net.QuicSession.FinalTcpCwnd", congestion_window_
);
61 void TcpCubicSender::SetFromConfig(const QuicConfig
& config
, bool is_server
) {
63 if (config
.HasReceivedConnectionOptions() &&
64 ContainsQuicTag(config
.ReceivedConnectionOptions(), kIW10
)) {
65 // Initial window experiment. Ignore the initial congestion
66 // window suggested by the client and use the default ICWND of
68 congestion_window_
= kInitialCongestionWindow
;
69 } else if (config
.HasReceivedInitialCongestionWindow()) {
70 // Set the initial window size.
71 congestion_window_
= min(kMaxInitialWindow
,
72 config
.ReceivedInitialCongestionWindow());
75 if (config
.HasReceivedSocketReceiveBuffer()) {
76 // Set the initial socket receive buffer size in bytes.
77 receive_window_
= config
.ReceivedSocketReceiveBuffer();
81 void TcpCubicSender::SetNumEmulatedConnections(int num_connections
) {
82 num_connections_
= max(1, num_connections
);
83 cubic_
.SetNumConnections(num_connections_
);
86 void TcpCubicSender::OnIncomingQuicCongestionFeedbackFrame(
87 const QuicCongestionFeedbackFrame
& feedback
,
88 QuicTime feedback_receive_time
) {
89 if (feedback
.type
== kTCP
) {
90 receive_window_
= feedback
.tcp
.receive_window
;
94 void TcpCubicSender::OnCongestionEvent(
96 QuicByteCount bytes_in_flight
,
97 const CongestionVector
& acked_packets
,
98 const CongestionVector
& lost_packets
) {
99 if (rtt_updated
&& InSlowStart() &&
100 hybrid_slow_start_
.ShouldExitSlowStart(rtt_stats_
->latest_rtt(),
101 rtt_stats_
->MinRtt(),
102 congestion_window_
)) {
103 slowstart_threshold_
= congestion_window_
;
105 for (CongestionVector::const_iterator it
= lost_packets
.begin();
106 it
!= lost_packets
.end(); ++it
) {
107 OnPacketLost(it
->first
, bytes_in_flight
);
109 for (CongestionVector::const_iterator it
= acked_packets
.begin();
110 it
!= acked_packets
.end(); ++it
) {
111 OnPacketAcked(it
->first
, it
->second
.bytes_sent
, bytes_in_flight
);
115 void TcpCubicSender::OnPacketAcked(
116 QuicPacketSequenceNumber acked_sequence_number
,
117 QuicByteCount acked_bytes
,
118 QuicByteCount bytes_in_flight
) {
119 largest_acked_sequence_number_
= max(acked_sequence_number
,
120 largest_acked_sequence_number_
);
122 PrrOnPacketAcked(acked_bytes
);
125 MaybeIncreaseCwnd(acked_sequence_number
, bytes_in_flight
);
126 // TODO(ianswett): Should this even be called when not in slow start?
127 hybrid_slow_start_
.OnPacketAcked(acked_sequence_number
, InSlowStart());
130 void TcpCubicSender::OnPacketLost(QuicPacketSequenceNumber sequence_number
,
131 QuicByteCount bytes_in_flight
) {
132 // TCP NewReno (RFC6582) says that once a loss occurs, any losses in packets
133 // already sent should be treated as a single loss event, since it's expected.
134 if (sequence_number
<= largest_sent_at_last_cutback_
) {
135 if (last_cutback_exited_slowstart_
) {
136 ++stats_
->slowstart_packets_lost
;
138 DVLOG(1) << "Ignoring loss for largest_missing:" << sequence_number
139 << " because it was sent prior to the last CWND cutback.";
142 ++stats_
->tcp_loss_events
;
143 last_cutback_exited_slowstart_
= InSlowStart();
145 ++stats_
->slowstart_packets_lost
;
147 PrrOnPacketLost(bytes_in_flight
);
150 congestion_window_
= congestion_window_
>> 1;
153 cubic_
.CongestionWindowAfterPacketLoss(congestion_window_
);
155 slowstart_threshold_
= congestion_window_
;
156 // Enforce TCP's minimum congestion window of 2*MSS.
157 if (congestion_window_
< kMinimumCongestionWindow
) {
158 congestion_window_
= kMinimumCongestionWindow
;
160 largest_sent_at_last_cutback_
= largest_sent_sequence_number_
;
161 // reset packet count from congestion avoidance mode. We start
162 // counting again when we're out of recovery.
163 congestion_window_count_
= 0;
164 DVLOG(1) << "Incoming loss; congestion window: " << congestion_window_
165 << " slowstart threshold: " << slowstart_threshold_
;
168 bool TcpCubicSender::OnPacketSent(QuicTime
/*sent_time*/,
169 QuicByteCount
/*bytes_in_flight*/,
170 QuicPacketSequenceNumber sequence_number
,
172 HasRetransmittableData is_retransmittable
) {
173 // Only update bytes_in_flight_ for data packets.
174 if (is_retransmittable
!= HAS_RETRANSMITTABLE_DATA
) {
179 DCHECK_LT(largest_sent_sequence_number_
, sequence_number
);
180 largest_sent_sequence_number_
= sequence_number
;
181 hybrid_slow_start_
.OnPacketSent(sequence_number
);
185 QuicTime::Delta
TcpCubicSender::TimeUntilSend(
187 QuicByteCount bytes_in_flight
,
188 HasRetransmittableData has_retransmittable_data
) const {
189 if (has_retransmittable_data
== NO_RETRANSMITTABLE_DATA
) {
190 // For TCP we can always send an ACK immediately.
191 return QuicTime::Delta::Zero();
194 return PrrTimeUntilSend(bytes_in_flight
);
196 if (SendWindow() > bytes_in_flight
) {
197 return QuicTime::Delta::Zero();
199 return QuicTime::Delta::Infinite();
202 QuicByteCount
TcpCubicSender::SendWindow() const {
203 // What's the current send window in bytes.
204 return min(receive_window_
, GetCongestionWindow());
207 QuicBandwidth
TcpCubicSender::PacingRate() const {
208 // We pace at twice the rate of the underlying sender's bandwidth estimate
209 // during slow start and 1.25x during congestion avoidance to ensure pacing
210 // doesn't prevent us from filling the window.
211 return BandwidthEstimate().Scale(InSlowStart() ? 2 : 1.25);
214 QuicBandwidth
TcpCubicSender::BandwidthEstimate() const {
215 if (rtt_stats_
->SmoothedRtt().IsZero()) {
216 LOG(DFATAL
) << "In BandwidthEstimate(), smoothed RTT is zero!";
217 return QuicBandwidth::Zero();
219 return QuicBandwidth::FromBytesAndTimeDelta(GetCongestionWindow(),
220 rtt_stats_
->SmoothedRtt());
223 bool TcpCubicSender::HasReliableBandwidthEstimate() const {
224 return !InSlowStart() && !InRecovery();
227 QuicTime::Delta
TcpCubicSender::RetransmissionDelay() const {
228 if (!rtt_stats_
->HasUpdates()) {
229 return QuicTime::Delta::Zero();
231 return rtt_stats_
->SmoothedRtt().Add(
232 rtt_stats_
->mean_deviation().Multiply(4));
235 QuicByteCount
TcpCubicSender::GetCongestionWindow() const {
236 return congestion_window_
* kMaxSegmentSize
;
239 bool TcpCubicSender::InSlowStart() const {
240 return congestion_window_
< slowstart_threshold_
;
243 QuicByteCount
TcpCubicSender::GetSlowStartThreshold() const {
244 return slowstart_threshold_
* kMaxSegmentSize
;
247 bool TcpCubicSender::IsCwndLimited(QuicByteCount bytes_in_flight
) const {
248 const QuicByteCount congestion_window_bytes
= congestion_window_
*
250 if (bytes_in_flight
>= congestion_window_bytes
) {
253 const QuicByteCount max_burst
= kMaxBurstLength
* kMaxSegmentSize
;
254 const QuicByteCount available_bytes
=
255 congestion_window_bytes
- bytes_in_flight
;
256 const bool slow_start_limited
= InSlowStart() &&
257 bytes_in_flight
> congestion_window_bytes
/ 2;
258 return slow_start_limited
|| available_bytes
<= max_burst
;
261 bool TcpCubicSender::InRecovery() const {
262 return largest_acked_sequence_number_
<= largest_sent_at_last_cutback_
&&
263 largest_acked_sequence_number_
!= 0;
266 // Called when we receive an ack. Normal TCP tracks how many packets one ack
267 // represents, but quic has a separate ack for each packet.
268 void TcpCubicSender::MaybeIncreaseCwnd(
269 QuicPacketSequenceNumber acked_sequence_number
,
270 QuicByteCount bytes_in_flight
) {
271 LOG_IF(DFATAL
, InRecovery()) << "Never increase the CWND during recovery.";
272 if (!IsCwndLimited(bytes_in_flight
)) {
273 // We don't update the congestion window unless we are close to using the
274 // window we have available.
278 // congestion_window_cnt is the number of acks since last change of snd_cwnd
279 if (congestion_window_
< max_tcp_congestion_window_
) {
280 // TCP slow start, exponential growth, increase by one for each ACK.
281 ++congestion_window_
;
283 DVLOG(1) << "Slow start; congestion window: " << congestion_window_
284 << " slowstart threshold: " << slowstart_threshold_
;
287 if (congestion_window_
>= max_tcp_congestion_window_
) {
290 // Congestion avoidance
292 // Classic Reno congestion avoidance.
293 ++congestion_window_count_
;
294 // Divide by num_connections to smoothly increase the CWND at a faster
295 // rate than conventional Reno.
296 if (congestion_window_count_
* num_connections_
>= congestion_window_
) {
297 ++congestion_window_
;
298 congestion_window_count_
= 0;
301 DVLOG(1) << "Reno; congestion window: " << congestion_window_
302 << " slowstart threshold: " << slowstart_threshold_
303 << " congestion window count: " << congestion_window_count_
;
305 congestion_window_
= min(max_tcp_congestion_window_
,
306 cubic_
.CongestionWindowAfterAck(
307 congestion_window_
, rtt_stats_
->MinRtt()));
308 DVLOG(1) << "Cubic; congestion window: " << congestion_window_
309 << " slowstart threshold: " << slowstart_threshold_
;
313 void TcpCubicSender::OnRetransmissionTimeout(bool packets_retransmitted
) {
314 largest_sent_at_last_cutback_
= 0;
315 if (!packets_retransmitted
) {
319 hybrid_slow_start_
.Restart();
320 previous_slowstart_threshold_
= slowstart_threshold_
;
321 slowstart_threshold_
= congestion_window_
/ 2;
322 previous_congestion_window_
= congestion_window_
;
323 congestion_window_
= kMinimumCongestionWindow
;
326 void TcpCubicSender::RevertRetransmissionTimeout() {
327 if (previous_congestion_window_
== 0) {
328 LOG(DFATAL
) << "No previous congestion window to revert to.";
331 congestion_window_
= previous_congestion_window_
;
332 slowstart_threshold_
= previous_slowstart_threshold_
;
333 previous_congestion_window_
= 0;
336 void TcpCubicSender::PrrOnPacketLost(QuicByteCount bytes_in_flight
) {
338 bytes_in_flight_before_loss_
= bytes_in_flight
;
340 ack_count_since_loss_
= 0;
343 void TcpCubicSender::PrrOnPacketAcked(QuicByteCount acked_bytes
) {
344 prr_delivered_
+= acked_bytes
;
345 ++ack_count_since_loss_
;
348 QuicTime::Delta
TcpCubicSender::PrrTimeUntilSend(
349 QuicByteCount bytes_in_flight
) const {
350 DCHECK(InRecovery());
351 // Return QuicTime::Zero In order to ensure limited transmit always works.
352 if (prr_out_
== 0 || bytes_in_flight
< kMaxSegmentSize
) {
353 return QuicTime::Delta::Zero();
355 if (SendWindow() > bytes_in_flight
) {
356 // During PRR-SSRB, limit outgoing packets to 1 extra MSS per ack, instead
357 // of sending the entire available window. This prevents burst retransmits
358 // when more packets are lost than the CWND reduction.
359 // limit = MAX(prr_delivered - prr_out, DeliveredData) + MSS
360 if (prr_delivered_
+ ack_count_since_loss_
* kMaxSegmentSize
<= prr_out_
) {
361 return QuicTime::Delta::Infinite();
363 return QuicTime::Delta::Zero();
365 // Implement Proportional Rate Reduction (RFC6937)
366 // Checks a simplified version of the PRR formula that doesn't use division:
367 // AvailableSendWindow =
368 // CEIL(prr_delivered * ssthresh / BytesInFlightAtLoss) - prr_sent
369 if (prr_delivered_
* slowstart_threshold_
* kMaxSegmentSize
>
370 prr_out_
* bytes_in_flight_before_loss_
) {
371 return QuicTime::Delta::Zero();
373 return QuicTime::Delta::Infinite();
376 CongestionControlType
TcpCubicSender::GetCongestionControlType() const {
377 return reno_
? kReno
: kCubic
;