Land Recent QUIC Changes.
[chromium-blink-merge.git] / net / quic / congestion_control / tcp_cubic_sender.cc
blob9c438d45251e535c454dc358035ba276a9a9f73a
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"
7 #include <algorithm>
9 #include "base/metrics/histogram.h"
10 #include "net/quic/congestion_control/rtt_stats.h"
11 #include "net/quic/crypto/crypto_protocol.h"
13 using std::max;
14 using std::min;
16 namespace net {
18 namespace {
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;
26 }; // namespace
28 TcpCubicSender::TcpCubicSender(
29 const QuicClock* clock,
30 const RttStats* rtt_stats,
31 bool reno,
32 QuicPacketCount max_tcp_congestion_window,
33 QuicConnectionStats* stats)
34 : hybrid_slow_start_(clock),
35 cubic_(clock, stats),
36 rtt_stats_(rtt_stats),
37 stats_(stats),
38 reno_(reno),
39 num_connections_(2),
40 congestion_window_count_(0),
41 receive_window_(kDefaultSocketReceiveBuffer),
42 prr_out_(0),
43 prr_delivered_(0),
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) {
62 if (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
67 // 10 instead.
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(
95 bool rtt_updated,
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_);
121 if (InRecovery()) {
122 PrrOnPacketAcked(acked_bytes);
123 return;
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.";
140 return;
142 ++stats_->tcp_loss_events;
143 last_cutback_exited_slowstart_ = InSlowStart();
144 if (InSlowStart()) {
145 ++stats_->slowstart_packets_lost;
147 PrrOnPacketLost(bytes_in_flight);
149 if (reno_) {
150 congestion_window_ = congestion_window_ >> 1;
151 } else {
152 congestion_window_ =
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,
171 QuicByteCount bytes,
172 HasRetransmittableData is_retransmittable) {
173 // Only update bytes_in_flight_ for data packets.
174 if (is_retransmittable != HAS_RETRANSMITTABLE_DATA) {
175 return false;
178 prr_out_ += bytes;
179 DCHECK_LT(largest_sent_sequence_number_, sequence_number);
180 largest_sent_sequence_number_ = sequence_number;
181 hybrid_slow_start_.OnPacketSent(sequence_number);
182 return true;
185 QuicTime::Delta TcpCubicSender::TimeUntilSend(
186 QuicTime /* now */,
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();
193 if (InRecovery()) {
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_ *
249 kMaxSegmentSize;
250 if (bytes_in_flight >= congestion_window_bytes) {
251 return true;
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.
275 return;
277 if (InSlowStart()) {
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_;
285 return;
287 if (congestion_window_ >= max_tcp_congestion_window_) {
288 return;
290 // Congestion avoidance
291 if (reno_) {
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_;
304 } else {
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) {
316 return;
318 cubic_.Reset();
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.";
329 return;
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) {
337 prr_out_ = 0;
338 bytes_in_flight_before_loss_ = bytes_in_flight;
339 prr_delivered_ = 0;
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;
380 } // namespace net