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.
4
5#include "net/quic/congestion_control/tcp_cubic_sender.h"
6
7#include <algorithm>
8
9#include "base/metrics/histogram.h"
10#include "net/quic/congestion_control/rtt_stats.h"
11#include "net/quic/crypto/crypto_protocol.h"
12
13using std::max;
14using std::min;
15
16namespace net {
17
18namespace {
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.
22const QuicTcpCongestionWindow kMinimumCongestionWindow = 2;
23const QuicByteCount kMaxSegmentSize = kDefaultTCPMSS;
24const int64 kInitialCongestionWindow = 10;
25const int kMaxBurstLength = 3;
26};  // namespace
27
28TcpCubicSender::TcpCubicSender(
29    const QuicClock* clock,
30    const RttStats* rtt_stats,
31    bool reno,
32    QuicTcpCongestionWindow 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      congestion_window_count_(0),
40      receive_window_(kDefaultSocketReceiveBuffer),
41      prr_out_(0),
42      prr_delivered_(0),
43      ack_count_since_loss_(0),
44      bytes_in_flight_before_loss_(0),
45      largest_sent_sequence_number_(0),
46      largest_acked_sequence_number_(0),
47      largest_sent_at_last_cutback_(0),
48      congestion_window_(kInitialCongestionWindow),
49      previous_congestion_window_(0),
50      slowstart_threshold_(max_tcp_congestion_window),
51      previous_slowstart_threshold_(0),
52      last_cutback_exited_slowstart_(false),
53      max_tcp_congestion_window_(max_tcp_congestion_window) {
54}
55
56TcpCubicSender::~TcpCubicSender() {
57  UMA_HISTOGRAM_COUNTS("Net.QuicSession.FinalTcpCwnd", congestion_window_);
58}
59
60void TcpCubicSender::SetFromConfig(const QuicConfig& config, bool is_server) {
61  if (is_server) {
62    if (config.HasReceivedConnectionOptions() &&
63        ContainsQuicTag(config.ReceivedConnectionOptions(), kIW10)) {
64      // Initial window experiment.  Ignore the initial congestion
65      // window suggested by the client and use the default ICWND of
66      // 10 instead.
67      congestion_window_ = kInitialCongestionWindow;
68    } else if (config.HasReceivedInitialCongestionWindow()) {
69      // Set the initial window size.
70      congestion_window_ = min(kMaxInitialWindow,
71                               config.ReceivedInitialCongestionWindow());
72    }
73  }
74  if (config.HasReceivedSocketReceiveBuffer()) {
75    // Set the initial socket receive buffer size in bytes.
76    receive_window_ = config.ReceivedSocketReceiveBuffer();
77  }
78}
79
80void TcpCubicSender::OnIncomingQuicCongestionFeedbackFrame(
81    const QuicCongestionFeedbackFrame& feedback,
82    QuicTime feedback_receive_time) {
83  if (feedback.type == kTCP) {
84    receive_window_ = feedback.tcp.receive_window;
85  }
86}
87
88void TcpCubicSender::OnCongestionEvent(
89    bool rtt_updated,
90    QuicByteCount bytes_in_flight,
91    const CongestionVector& acked_packets,
92    const CongestionVector& lost_packets) {
93  if (rtt_updated && InSlowStart() &&
94      hybrid_slow_start_.ShouldExitSlowStart(rtt_stats_->latest_rtt(),
95                                             rtt_stats_->min_rtt(),
96                                             congestion_window_)) {
97    slowstart_threshold_ = congestion_window_;
98  }
99  for (CongestionVector::const_iterator it = lost_packets.begin();
100       it != lost_packets.end(); ++it) {
101    OnPacketLost(it->first, bytes_in_flight);
102  }
103  for (CongestionVector::const_iterator it = acked_packets.begin();
104       it != acked_packets.end(); ++it) {
105    OnPacketAcked(it->first, it->second.bytes_sent, bytes_in_flight);
106  }
107}
108
109void TcpCubicSender::OnPacketAcked(
110    QuicPacketSequenceNumber acked_sequence_number,
111    QuicByteCount acked_bytes,
112    QuicByteCount bytes_in_flight) {
113  largest_acked_sequence_number_ = max(acked_sequence_number,
114                                       largest_acked_sequence_number_);
115  if (InRecovery()) {
116    PrrOnPacketAcked(acked_bytes);
117    return;
118  }
119  MaybeIncreaseCwnd(acked_sequence_number, bytes_in_flight);
120  // TODO(ianswett): Should this even be called when not in slow start?
121  hybrid_slow_start_.OnPacketAcked(acked_sequence_number, InSlowStart());
122}
123
124void TcpCubicSender::OnPacketLost(QuicPacketSequenceNumber sequence_number,
125                                  QuicByteCount bytes_in_flight) {
126  // TCP NewReno (RFC6582) says that once a loss occurs, any losses in packets
127  // already sent should be treated as a single loss event, since it's expected.
128  if (sequence_number <= largest_sent_at_last_cutback_) {
129    if (last_cutback_exited_slowstart_) {
130      ++stats_->slowstart_packets_lost;
131    }
132    DVLOG(1) << "Ignoring loss for largest_missing:" << sequence_number
133             << " because it was sent prior to the last CWND cutback.";
134    return;
135  }
136  ++stats_->tcp_loss_events;
137  last_cutback_exited_slowstart_ = InSlowStart();
138  if (InSlowStart()) {
139    ++stats_->slowstart_packets_lost;
140  }
141  PrrOnPacketLost(bytes_in_flight);
142
143  if (reno_) {
144    congestion_window_ = congestion_window_ >> 1;
145  } else {
146    congestion_window_ =
147        cubic_.CongestionWindowAfterPacketLoss(congestion_window_);
148  }
149  slowstart_threshold_ = congestion_window_;
150  // Enforce TCP's minimum congestion window of 2*MSS.
151  if (congestion_window_ < kMinimumCongestionWindow) {
152    congestion_window_ = kMinimumCongestionWindow;
153  }
154  largest_sent_at_last_cutback_ = largest_sent_sequence_number_;
155  // reset packet count from congestion avoidance mode. We start
156  // counting again when we're out of recovery.
157  congestion_window_count_ = 0;
158  DVLOG(1) << "Incoming loss; congestion window: " << congestion_window_
159           << " slowstart threshold: " << slowstart_threshold_;
160}
161
162bool TcpCubicSender::OnPacketSent(QuicTime /*sent_time*/,
163                                  QuicByteCount /*bytes_in_flight*/,
164                                  QuicPacketSequenceNumber sequence_number,
165                                  QuicByteCount bytes,
166                                  HasRetransmittableData is_retransmittable) {
167  // Only update bytes_in_flight_ for data packets.
168  if (is_retransmittable != HAS_RETRANSMITTABLE_DATA) {
169    return false;
170  }
171
172  prr_out_ += bytes;
173  DCHECK_LT(largest_sent_sequence_number_, sequence_number);
174  largest_sent_sequence_number_ = sequence_number;
175  hybrid_slow_start_.OnPacketSent(sequence_number);
176  return true;
177}
178
179QuicTime::Delta TcpCubicSender::TimeUntilSend(
180    QuicTime /* now */,
181    QuicByteCount bytes_in_flight,
182    HasRetransmittableData has_retransmittable_data) const {
183  if (has_retransmittable_data == NO_RETRANSMITTABLE_DATA) {
184    // For TCP we can always send an ACK immediately.
185    return QuicTime::Delta::Zero();
186  }
187  if (InRecovery()) {
188    return PrrTimeUntilSend(bytes_in_flight);
189  }
190  if (SendWindow() > bytes_in_flight) {
191    return QuicTime::Delta::Zero();
192  }
193  return QuicTime::Delta::Infinite();
194}
195
196QuicByteCount TcpCubicSender::SendWindow() const {
197  // What's the current send window in bytes.
198  return min(receive_window_, GetCongestionWindow());
199}
200
201QuicBandwidth TcpCubicSender::BandwidthEstimate() const {
202  return QuicBandwidth::FromBytesAndTimeDelta(GetCongestionWindow(),
203                                              rtt_stats_->SmoothedRtt());
204}
205
206bool TcpCubicSender::HasReliableBandwidthEstimate() const {
207  return !InSlowStart() && !InRecovery();
208}
209
210QuicTime::Delta TcpCubicSender::RetransmissionDelay() const {
211  if (!rtt_stats_->HasUpdates()) {
212    return QuicTime::Delta::Zero();
213  }
214  return QuicTime::Delta::FromMicroseconds(
215      rtt_stats_->SmoothedRtt().ToMicroseconds() +
216      4 * rtt_stats_->mean_deviation().ToMicroseconds());
217}
218
219QuicByteCount TcpCubicSender::GetCongestionWindow() const {
220  return congestion_window_ * kMaxSegmentSize;
221}
222
223bool TcpCubicSender::InSlowStart() const {
224  return congestion_window_ < slowstart_threshold_;
225}
226
227QuicByteCount TcpCubicSender::GetSlowStartThreshold() const {
228  return slowstart_threshold_ * kMaxSegmentSize;
229}
230
231bool TcpCubicSender::IsCwndLimited(QuicByteCount bytes_in_flight) const {
232  const QuicByteCount congestion_window_bytes = congestion_window_ *
233      kMaxSegmentSize;
234  if (bytes_in_flight >= congestion_window_bytes) {
235    return true;
236  }
237  const QuicByteCount max_burst = kMaxBurstLength * kMaxSegmentSize;
238  const QuicByteCount available_bytes =
239      congestion_window_bytes - bytes_in_flight;
240  const bool slow_start_limited = InSlowStart() &&
241      bytes_in_flight >  congestion_window_bytes / 2;
242  return slow_start_limited || available_bytes <= max_burst;
243}
244
245bool TcpCubicSender::InRecovery() const {
246  return largest_acked_sequence_number_ <= largest_sent_at_last_cutback_ &&
247      largest_acked_sequence_number_ != 0;
248}
249
250// Called when we receive an ack. Normal TCP tracks how many packets one ack
251// represents, but quic has a separate ack for each packet.
252void TcpCubicSender::MaybeIncreaseCwnd(
253    QuicPacketSequenceNumber acked_sequence_number,
254    QuicByteCount bytes_in_flight) {
255  LOG_IF(DFATAL, InRecovery()) << "Never increase the CWND during recovery.";
256  if (!IsCwndLimited(bytes_in_flight)) {
257    // We don't update the congestion window unless we are close to using the
258    // window we have available.
259    return;
260  }
261  if (InSlowStart()) {
262    // congestion_window_cnt is the number of acks since last change of snd_cwnd
263    if (congestion_window_ < max_tcp_congestion_window_) {
264      // TCP slow start, exponential growth, increase by one for each ACK.
265      ++congestion_window_;
266    }
267    DVLOG(1) << "Slow start; congestion window: " << congestion_window_
268             << " slowstart threshold: " << slowstart_threshold_;
269    return;
270  }
271  if (congestion_window_ >= max_tcp_congestion_window_) {
272    return;
273  }
274  // Congestion avoidance
275  if (reno_) {
276    // Classic Reno congestion avoidance provided for testing.
277
278    ++congestion_window_count_;
279    if (congestion_window_count_ >= congestion_window_) {
280      ++congestion_window_;
281      congestion_window_count_ = 0;
282    }
283
284    DVLOG(1) << "Reno; congestion window: " << congestion_window_
285             << " slowstart threshold: " << slowstart_threshold_
286             << " congestion window count: " << congestion_window_count_;
287  } else {
288    congestion_window_ = min(max_tcp_congestion_window_,
289                             cubic_.CongestionWindowAfterAck(
290                                 congestion_window_, rtt_stats_->min_rtt()));
291    DVLOG(1) << "Cubic; congestion window: " << congestion_window_
292             << " slowstart threshold: " << slowstart_threshold_;
293  }
294}
295
296void TcpCubicSender::OnRetransmissionTimeout(bool packets_retransmitted) {
297  largest_sent_at_last_cutback_ = 0;
298  if (!packets_retransmitted) {
299    return;
300  }
301  cubic_.Reset();
302  hybrid_slow_start_.Restart();
303  previous_slowstart_threshold_ = slowstart_threshold_;
304  slowstart_threshold_ = congestion_window_ / 2;
305  previous_congestion_window_ = congestion_window_;
306  congestion_window_ = kMinimumCongestionWindow;
307}
308
309void TcpCubicSender::RevertRetransmissionTimeout() {
310  if (previous_congestion_window_ == 0) {
311    LOG(DFATAL) << "No previous congestion window to revert to.";
312    return;
313  }
314  congestion_window_ = previous_congestion_window_;
315  slowstart_threshold_ = previous_slowstart_threshold_;
316  previous_congestion_window_ = 0;
317}
318
319void TcpCubicSender::PrrOnPacketLost(QuicByteCount bytes_in_flight) {
320  prr_out_ = 0;
321  bytes_in_flight_before_loss_ = bytes_in_flight;
322  prr_delivered_ = 0;
323  ack_count_since_loss_ = 0;
324}
325
326void TcpCubicSender::PrrOnPacketAcked(QuicByteCount acked_bytes) {
327  prr_delivered_ += acked_bytes;
328  ++ack_count_since_loss_;
329}
330
331QuicTime::Delta TcpCubicSender::PrrTimeUntilSend(
332    QuicByteCount bytes_in_flight) const {
333  DCHECK(InRecovery());
334  // Return QuicTime::Zero In order to ensure limited transmit always works.
335  if (prr_out_ == 0 || bytes_in_flight < kMaxSegmentSize) {
336    return QuicTime::Delta::Zero();
337  }
338  if (SendWindow() > bytes_in_flight) {
339    // During PRR-SSRB, limit outgoing packets to 1 extra MSS per ack, instead
340    // of sending the entire available window. This prevents burst retransmits
341    // when more packets are lost than the CWND reduction.
342    //   limit = MAX(prr_delivered - prr_out, DeliveredData) + MSS
343    if (prr_delivered_ + ack_count_since_loss_ * kMaxSegmentSize <= prr_out_) {
344      return QuicTime::Delta::Infinite();
345    }
346    return QuicTime::Delta::Zero();
347  }
348  // Implement Proportional Rate Reduction (RFC6937)
349  // Checks a simplified version of the PRR formula that doesn't use division:
350  // AvailableSendWindow =
351  //   CEIL(prr_delivered * ssthresh / BytesInFlightAtLoss) - prr_sent
352  if (prr_delivered_ * slowstart_threshold_ * kMaxSegmentSize >
353          prr_out_ * bytes_in_flight_before_loss_) {
354    return QuicTime::Delta::Zero();
355  }
356  return QuicTime::Delta::Infinite();
357}
358
359CongestionControlType TcpCubicSender::GetCongestionControlType() const {
360  return reno_ ? kReno : kCubic;
361}
362
363}  // namespace net
364