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