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/prr_sender.h"
  11 #include "net/quic/congestion_control/rtt_stats.h"
  12 #include "net/quic/crypto/crypto_protocol.h"
  13
  14 using std::max;
  15 using std::min;
  16
  17 namespace net {
  18
  19 namespace {
  20 // Constants based on TCP defaults.
  21 // The minimum cwnd based on RFC 3782 (TCP NewReno) for cwnd reductions on a
  22 // fast retransmission.  The cwnd after a timeout is still 1.
  23 const QuicPacketCount kMinimumCongestionWindow = 2;
  24 const QuicByteCount kMaxSegmentSize = kDefaultTCPMSS;
  25 const int kMaxBurstLength = 3;
  26 const float kRenoBeta = 0.7f;  // Reno backoff factor.
  27 const uint32 kDefaultNumConnections = 2;  // N-connection emulation.
  28 }  // namespace
  29
  30 TcpCubicSender::TcpCubicSender(const QuicClock* clock,
  31                                const RttStats* rtt_stats,
  32                                bool reno,
  33                                QuicPacketCount initial_tcp_congestion_window,
  34                                QuicPacketCount max_tcp_congestion_window,
  35                                QuicConnectionStats* stats)
  36     : hybrid_slow_start_(clock),
  37       cubic_(clock, stats),
  38       rtt_stats_(rtt_stats),
  39       stats_(stats),
  40       reno_(reno),
  41       num_connections_(kDefaultNumConnections),
  42       congestion_window_count_(0),
  43       largest_sent_sequence_number_(0),
  44       largest_acked_sequence_number_(0),
  45       largest_sent_at_last_cutback_(0),
  46       congestion_window_(initial_tcp_congestion_window),
  47       previous_congestion_window_(0),
  48       slowstart_threshold_(max_tcp_congestion_window),
  49       previous_slowstart_threshold_(0),
  50       last_cutback_exited_slowstart_(false),
  51       max_tcp_congestion_window_(max_tcp_congestion_window),
  52       clock_(clock) {}
  53
  54 TcpCubicSender::~TcpCubicSender() {
  55   UMA_HISTOGRAM_COUNTS("Net.QuicSession.FinalTcpCwnd", congestion_window_);
  56 }
  57
  58 void TcpCubicSender::SetFromConfig(const QuicConfig& config,
  59                                    bool is_server,
  60                                    bool using_pacing) {
  61   if (is_server) {
  62     if (config.HasReceivedConnectionOptions() &&
  63         ContainsQuicTag(config.ReceivedConnectionOptions(), kIW10)) {
  64       // Initial window experiment.
  65       congestion_window_ = 10;
  66     }
  67     if (using_pacing) {
  68       // Disable the ack train mode in hystart when pacing is enabled, since it
  69       // may be falsely triggered.
  70       hybrid_slow_start_.set_ack_train_detection(false);
  71     }
  72   }
  73 }
  74
  75 bool TcpCubicSender::ResumeConnectionState(
  76     const CachedNetworkParameters& cached_network_params) {
  77   // If the previous bandwidth estimate is less than an hour old, store in
  78   // preparation for doing bandwidth resumption.
  79   int64 seconds_since_estimate =
  80       clock_->WallNow().ToUNIXSeconds() - cached_network_params.timestamp();
  81   if (seconds_since_estimate > kNumSecondsPerHour) {
  82     return false;
  83   }
  84
  85   QuicBandwidth bandwidth = QuicBandwidth::FromBytesPerSecond(
  86       cached_network_params.bandwidth_estimate_bytes_per_second());
  87   QuicTime::Delta rtt_ms =
  88       QuicTime::Delta::FromMilliseconds(cached_network_params.min_rtt_ms());
  89
  90   // Make sure CWND is in appropriate range (in case of bad data).
  91   QuicPacketCount new_congestion_window =
  92       bandwidth.ToBytesPerPeriod(rtt_ms) / kMaxPacketSize;
  93   congestion_window_ = max(min(new_congestion_window, kMaxTcpCongestionWindow),
  94                            kMinCongestionWindowForBandwidthResumption);
  95
  96   // TODO(rjshade): Set appropriate CWND when previous connection was in slow
  97   // start at time of estimate.
  98   return true;
  99 }
 100
 101 void TcpCubicSender::SetNumEmulatedConnections(int num_connections) {
 102   num_connections_ = max(1, num_connections);
 103   cubic_.SetNumConnections(num_connections_);
 104 }
 105
 106 float TcpCubicSender::RenoBeta() const {
 107   // kNConnectionBeta is the backoff factor after loss for our N-connection
 108   // emulation, which emulates the effective backoff of an ensemble of N
 109   // TCP-Reno connections on a single loss event. The effective multiplier is
 110   // computed as:
 111   return (num_connections_ - 1 + kRenoBeta) / num_connections_;
 112 }
 113
 114 void TcpCubicSender::OnCongestionEvent(
 115     bool rtt_updated,
 116     QuicByteCount bytes_in_flight,
 117     const CongestionVector& acked_packets,
 118     const CongestionVector& lost_packets) {
 119   if (rtt_updated && InSlowStart() &&
 120       hybrid_slow_start_.ShouldExitSlowStart(rtt_stats_->latest_rtt(),
 121                                              rtt_stats_->min_rtt(),
 122                                              congestion_window_)) {
 123     slowstart_threshold_ = congestion_window_;
 124   }
 125   for (CongestionVector::const_iterator it = lost_packets.begin();
 126        it != lost_packets.end(); ++it) {
 127     OnPacketLost(it->first, bytes_in_flight);
 128   }
 129   for (CongestionVector::const_iterator it = acked_packets.begin();
 130        it != acked_packets.end(); ++it) {
 131     OnPacketAcked(it->first, it->second.bytes_sent, bytes_in_flight);
 132   }
 133 }
 134
 135 void TcpCubicSender::OnPacketAcked(
 136     QuicPacketSequenceNumber acked_sequence_number,
 137     QuicByteCount acked_bytes,
 138     QuicByteCount bytes_in_flight) {
 139   largest_acked_sequence_number_ = max(acked_sequence_number,
 140                                        largest_acked_sequence_number_);
 141   // As soon as a packet is acked, ensure we're no longer in RTO mode.
 142   previous_congestion_window_ = 0;
 143   if (InRecovery()) {
 144     // PRR is used when in recovery.
 145     prr_.OnPacketAcked(acked_bytes);
 146     return;
 147   }
 148   MaybeIncreaseCwnd(acked_sequence_number, bytes_in_flight);
 149   // TODO(ianswett): Should this even be called when not in slow start?
 150   hybrid_slow_start_.OnPacketAcked(acked_sequence_number, InSlowStart());
 151 }
 152
 153 void TcpCubicSender::OnPacketLost(QuicPacketSequenceNumber sequence_number,
 154                                   QuicByteCount bytes_in_flight) {
 155   // TCP NewReno (RFC6582) says that once a loss occurs, any losses in packets
 156   // already sent should be treated as a single loss event, since it's expected.
 157   if (sequence_number <= largest_sent_at_last_cutback_) {
 158     if (last_cutback_exited_slowstart_) {
 159       ++stats_->slowstart_packets_lost;
 160     }
 161     DVLOG(1) << "Ignoring loss for largest_missing:" << sequence_number
 162              << " because it was sent prior to the last CWND cutback.";
 163     return;
 164   }
 165   ++stats_->tcp_loss_events;
 166   last_cutback_exited_slowstart_ = InSlowStart();
 167   if (InSlowStart()) {
 168     ++stats_->slowstart_packets_lost;
 169   }
 170
 171   prr_.OnPacketLost(bytes_in_flight);
 172
 173   if (reno_) {
 174     congestion_window_ = congestion_window_ * RenoBeta();
 175   } else {
 176     congestion_window_ =
 177         cubic_.CongestionWindowAfterPacketLoss(congestion_window_);
 178   }
 179   slowstart_threshold_ = congestion_window_;
 180   // Enforce TCP's minimum congestion window of 2*MSS.
 181   if (congestion_window_ < kMinimumCongestionWindow) {
 182     congestion_window_ = kMinimumCongestionWindow;
 183   }
 184   largest_sent_at_last_cutback_ = largest_sent_sequence_number_;
 185   // reset packet count from congestion avoidance mode. We start
 186   // counting again when we're out of recovery.
 187   congestion_window_count_ = 0;
 188   DVLOG(1) << "Incoming loss; congestion window: " << congestion_window_
 189            << " slowstart threshold: " << slowstart_threshold_;
 190 }
 191
 192 bool TcpCubicSender::OnPacketSent(QuicTime /*sent_time*/,
 193                                   QuicByteCount /*bytes_in_flight*/,
 194                                   QuicPacketSequenceNumber sequence_number,
 195                                   QuicByteCount bytes,
 196                                   HasRetransmittableData is_retransmittable) {
 197   // Only update bytes_in_flight_ for data packets.
 198   if (is_retransmittable != HAS_RETRANSMITTABLE_DATA) {
 199     return false;
 200   }
 201   if (InRecovery()) {
 202     // PRR is used when in recovery.
 203     prr_.OnPacketSent(bytes);
 204   }
 205   DCHECK_LT(largest_sent_sequence_number_, sequence_number);
 206   largest_sent_sequence_number_ = sequence_number;
 207   hybrid_slow_start_.OnPacketSent(sequence_number);
 208   return true;
 209 }
 210
 211 QuicTime::Delta TcpCubicSender::TimeUntilSend(
 212     QuicTime /* now */,
 213     QuicByteCount bytes_in_flight,
 214     HasRetransmittableData has_retransmittable_data) const {
 215   if (has_retransmittable_data == NO_RETRANSMITTABLE_DATA) {
 216     // For TCP we can always send an ACK immediately.
 217     return QuicTime::Delta::Zero();
 218   }
 219   if (InRecovery()) {
 220     // PRR is used when in recovery.
 221     return prr_.TimeUntilSend(GetCongestionWindow(), bytes_in_flight,
 222                               slowstart_threshold_);
 223   }
 224   if (GetCongestionWindow() > bytes_in_flight) {
 225     return QuicTime::Delta::Zero();
 226   }
 227   return QuicTime::Delta::Infinite();
 228 }
 229
 230 QuicBandwidth TcpCubicSender::PacingRate() const {
 231   // We pace at twice the rate of the underlying sender's bandwidth estimate
 232   // during slow start and 1.25x during congestion avoidance to ensure pacing
 233   // doesn't prevent us from filling the window.
 234   QuicTime::Delta srtt = rtt_stats_->smoothed_rtt();
 235   if (srtt.IsZero()) {
 236     srtt = QuicTime::Delta::FromMicroseconds(rtt_stats_->initial_rtt_us());
 237   }
 238   const QuicBandwidth bandwidth =
 239       QuicBandwidth::FromBytesAndTimeDelta(GetCongestionWindow(), srtt);
 240   return bandwidth.Scale(InSlowStart() ? 2 : 1.25);
 241 }
 242
 243 QuicBandwidth TcpCubicSender::BandwidthEstimate() const {
 244   QuicTime::Delta srtt = rtt_stats_->smoothed_rtt();
 245   if (srtt.IsZero()) {
 246     // If we haven't measured an rtt, the bandwidth estimate is unknown.
 247     return QuicBandwidth::Zero();
 248   }
 249   return QuicBandwidth::FromBytesAndTimeDelta(GetCongestionWindow(), srtt);
 250 }
 251
 252 bool TcpCubicSender::HasReliableBandwidthEstimate() const {
 253   return !InSlowStart() && !InRecovery() &&
 254       !rtt_stats_->smoothed_rtt().IsZero();;
 255 }
 256
 257 QuicTime::Delta TcpCubicSender::RetransmissionDelay() const {
 258   if (rtt_stats_->smoothed_rtt().IsZero()) {
 259     return QuicTime::Delta::Zero();
 260   }
 261   return rtt_stats_->smoothed_rtt().Add(
 262       rtt_stats_->mean_deviation().Multiply(4));
 263 }
 264
 265 QuicByteCount TcpCubicSender::GetCongestionWindow() const {
 266   return congestion_window_ * kMaxSegmentSize;
 267 }
 268
 269 bool TcpCubicSender::InSlowStart() const {
 270   return congestion_window_ < slowstart_threshold_;
 271 }
 272
 273 QuicByteCount TcpCubicSender::GetSlowStartThreshold() const {
 274   return slowstart_threshold_ * kMaxSegmentSize;
 275 }
 276
 277 bool TcpCubicSender::IsCwndLimited(QuicByteCount bytes_in_flight) const {
 278   const QuicByteCount congestion_window_bytes = congestion_window_ *
 279       kMaxSegmentSize;
 280   if (bytes_in_flight >= congestion_window_bytes) {
 281     return true;
 282   }
 283   const QuicByteCount max_burst = kMaxBurstLength * kMaxSegmentSize;
 284   const QuicByteCount available_bytes =
 285       congestion_window_bytes - bytes_in_flight;
 286   const bool slow_start_limited = InSlowStart() &&
 287       bytes_in_flight >  congestion_window_bytes / 2;
 288   return slow_start_limited || available_bytes <= max_burst;
 289 }
 290
 291 bool TcpCubicSender::InRecovery() const {
 292   return largest_acked_sequence_number_ <= largest_sent_at_last_cutback_ &&
 293       largest_acked_sequence_number_ != 0;
 294 }
 295
 296 // Called when we receive an ack. Normal TCP tracks how many packets one ack
 297 // represents, but quic has a separate ack for each packet.
 298 void TcpCubicSender::MaybeIncreaseCwnd(
 299     QuicPacketSequenceNumber acked_sequence_number,
 300     QuicByteCount bytes_in_flight) {
 301   LOG_IF(DFATAL, InRecovery()) << "Never increase the CWND during recovery.";
 302   if (!IsCwndLimited(bytes_in_flight)) {
 303     // We don't update the congestion window unless we are close to using the
 304     // window we have available.
 305     return;
 306   }
 307   if (InSlowStart()) {
 308     // congestion_window_cnt is the number of acks since last change of snd_cwnd
 309     if (congestion_window_ < max_tcp_congestion_window_) {
 310       // TCP slow start, exponential growth, increase by one for each ACK.
 311       ++congestion_window_;
 312     }
 313     DVLOG(1) << "Slow start; congestion window: " << congestion_window_
 314              << " slowstart threshold: " << slowstart_threshold_;
 315     return;
 316   }
 317   if (congestion_window_ >= max_tcp_congestion_window_) {
 318     return;
 319   }
 320   // Congestion avoidance
 321   if (reno_) {
 322     // Classic Reno congestion avoidance.
 323     ++congestion_window_count_;
 324     // Divide by num_connections to smoothly increase the CWND at a faster
 325     // rate than conventional Reno.
 326     if (congestion_window_count_ * num_connections_ >= congestion_window_) {
 327       ++congestion_window_;
 328       congestion_window_count_ = 0;
 329     }
 330
 331     DVLOG(1) << "Reno; congestion window: " << congestion_window_
 332              << " slowstart threshold: " << slowstart_threshold_
 333              << " congestion window count: " << congestion_window_count_;
 334   } else {
 335     congestion_window_ = min(max_tcp_congestion_window_,
 336                              cubic_.CongestionWindowAfterAck(
 337                                  congestion_window_, rtt_stats_->min_rtt()));
 338     DVLOG(1) << "Cubic; congestion window: " << congestion_window_
 339              << " slowstart threshold: " << slowstart_threshold_;
 340   }
 341 }
 342
 343 void TcpCubicSender::OnRetransmissionTimeout(bool packets_retransmitted) {
 344   largest_sent_at_last_cutback_ = 0;
 345   if (!packets_retransmitted) {
 346     return;
 347   }
 348   cubic_.Reset();
 349   hybrid_slow_start_.Restart();
 350   // Only reduce ssthresh once over multiple retransmissions.
 351   if (previous_congestion_window_ != 0) {
 352     return;
 353   }
 354   previous_slowstart_threshold_ = slowstart_threshold_;
 355   slowstart_threshold_ = congestion_window_ / 2;
 356   previous_congestion_window_ = congestion_window_;
 357   congestion_window_ = kMinimumCongestionWindow;
 358 }
 359
 360 void TcpCubicSender::RevertRetransmissionTimeout() {
 361   if (previous_congestion_window_ == 0) {
 362     LOG(DFATAL) << "No previous congestion window to revert to.";
 363     return;
 364   }
 365   congestion_window_ = previous_congestion_window_;
 366   slowstart_threshold_ = previous_slowstart_threshold_;
 367   previous_congestion_window_ = 0;
 368 }
 369
 370 CongestionControlType TcpCubicSender::GetCongestionControlType() const {
 371   return reno_ ? kReno : kCubic;
 372 }
 373
 374 }  // namespace net