net/quic/congestion_control/tcp_cubic_sender.cc

   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
  13 using std::max;
  14 using std::min;
  15
  16 namespace net {
  17
  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 QuicTcpCongestionWindow kMinimumCongestionWindow = 2;
  23 const QuicByteCount kMaxSegmentSize = kDefaultTCPMSS;
  24 const int64 kInitialCongestionWindow = 10;
  25 const int kMaxBurstLength = 3;
  26 };  // namespace
  27
  28 TcpCubicSender::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
  56 TcpCubicSender::~TcpCubicSender() {
  57   UMA_HISTOGRAM_COUNTS("Net.QuicSession.FinalTcpCwnd", congestion_window_);
  58 }
  59
  60 void 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
  80 void 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
  88 void TcpCubicSender::OnCongestionEvent(
  89     bool rtt_updated,
  90     QuicByteCount bytes_in_flight,
  91     const CongestionMap& acked_packets,
  92     const CongestionMap& 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 (CongestionMap::const_iterator it = lost_packets.begin();
 100        it != lost_packets.end(); ++it) {
 101     OnPacketLost(it->first, bytes_in_flight);
 102   }
 103   for (CongestionMap::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
 109 void 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
 124 void 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
 162 bool 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
 179 QuicTime::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
 196 QuicByteCount TcpCubicSender::SendWindow() const {
 197   // What's the current send window in bytes.
 198   return min(receive_window_, GetCongestionWindow());
 199 }
 200
 201 QuicBandwidth TcpCubicSender::BandwidthEstimate() const {
 202   return QuicBandwidth::FromBytesAndTimeDelta(GetCongestionWindow(),
 203                                               rtt_stats_->SmoothedRtt());
 204 }
 205
 206 bool TcpCubicSender::HasReliableBandwidthEstimate() const {
 207   return !InSlowStart() && !InRecovery();
 208 }
 209
 210 QuicTime::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
 219 QuicByteCount TcpCubicSender::GetCongestionWindow() const {
 220   return congestion_window_ * kMaxSegmentSize;
 221 }
 222
 223 bool TcpCubicSender::InSlowStart() const {
 224   return congestion_window_ < slowstart_threshold_;
 225 }
 226
 227 QuicByteCount TcpCubicSender::GetSlowStartThreshold() const {
 228   return slowstart_threshold_ * kMaxSegmentSize;
 229 }
 230
 231 bool 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
 245 bool 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.
 252 void 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
 296 void 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
 309 void 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
 319 void 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
 326 void TcpCubicSender::PrrOnPacketAcked(QuicByteCount acked_bytes) {
 327   prr_delivered_ += acked_bytes;
 328   ++ack_count_since_loss_;
 329 }
 330
 331 QuicTime::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
 359 CongestionControlType TcpCubicSender::GetCongestionControlType() const {
 360   return reno_ ? kReno : kCubic;
 361 }
 362
 363 }  // namespace net