net/quic/congestion_control/tcp_cubic_bytes_sender.cc

   1 // Copyright (c) 2015 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_bytes_sender.h"
   6
   7 #include <algorithm>
   8
   9 #include "net/quic/congestion_control/prr_sender.h"
  10 #include "net/quic/congestion_control/rtt_stats.h"
  11 #include "net/quic/crypto/crypto_protocol.h"
  12 #include "net/quic/proto/cached_network_parameters.pb.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.
  23 const QuicByteCount kDefaultMinimumCongestionWindow = 2 * kDefaultTCPMSS;
  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 TcpCubicBytesSender::TcpCubicBytesSender(
  31     const QuicClock* clock,
  32     const RttStats* rtt_stats,
  33     bool reno,
  34     QuicPacketCount initial_tcp_congestion_window,
  35     QuicPacketCount max_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       num_acked_packets_(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 * kMaxSegmentSize),
  48       min_congestion_window_(kDefaultMinimumCongestionWindow),
  49       max_congestion_window_(max_congestion_window * kMaxSegmentSize),
  50       slowstart_threshold_(std::numeric_limits<uint64>::max()),
  51       last_cutback_exited_slowstart_(false),
  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 TcpCubicBytesSender::~TcpCubicBytesSender() {
  59 }
  60
  61 void TcpCubicBytesSender::SetFromConfig(const QuicConfig& config,
  62                                         Perspective perspective) {
  63   if (perspective == Perspective::IS_SERVER) {
  64     if (config.HasReceivedConnectionOptions() &&
  65         ContainsQuicTag(config.ReceivedConnectionOptions(), kIW10)) {
  66       // Initial window experiment.
  67       congestion_window_ = 10 * kMaxSegmentSize;
  68     }
  69     if (config.HasReceivedConnectionOptions() &&
  70         ContainsQuicTag(config.ReceivedConnectionOptions(), kMIN1)) {
  71       // Min CWND experiment.
  72       min_congestion_window_ = kMaxSegmentSize;
  73     }
  74   }
  75 }
  76
  77 bool TcpCubicBytesSender::ResumeConnectionState(
  78     const CachedNetworkParameters& cached_network_params,
  79     bool max_bandwidth_resumption) {
  80   // If the previous bandwidth estimate is less than an hour old, store in
  81   // preparation for doing bandwidth resumption.
  82   int64 seconds_since_estimate =
  83       clock_->WallNow().ToUNIXSeconds() - cached_network_params.timestamp();
  84   if (seconds_since_estimate > kNumSecondsPerHour) {
  85     return false;
  86   }
  87
  88   QuicBandwidth bandwidth = QuicBandwidth::FromBytesPerSecond(
  89       max_bandwidth_resumption
  90           ? cached_network_params.max_bandwidth_estimate_bytes_per_second()
  91           : cached_network_params.bandwidth_estimate_bytes_per_second());
  92   QuicTime::Delta rtt_ms =
  93       QuicTime::Delta::FromMilliseconds(cached_network_params.min_rtt_ms());
  94
  95   // Make sure CWND is in appropriate range (in case of bad data).
  96   QuicByteCount new_congestion_window = bandwidth.ToBytesPerPeriod(rtt_ms);
  97   congestion_window_ =
  98       max(min(new_congestion_window, kMaxTcpCongestionWindow * kMaxSegmentSize),
  99           kMinCongestionWindowForBandwidthResumption * kMaxSegmentSize);
 100
 101   // TODO(rjshade): Set appropriate CWND when previous connection was in slow
 102   // start at time of estimate.
 103   return true;
 104 }
 105
 106 void TcpCubicBytesSender::SetNumEmulatedConnections(int num_connections) {
 107   num_connections_ = max(1, num_connections);
 108   cubic_.SetNumConnections(num_connections_);
 109 }
 110
 111 void TcpCubicBytesSender::SetMaxCongestionWindow(
 112     QuicByteCount max_congestion_window) {
 113   max_congestion_window_ = max_congestion_window;
 114 }
 115
 116 float TcpCubicBytesSender::RenoBeta() const {
 117   // kNConnectionBeta is the backoff factor after loss for our N-connection
 118   // emulation, which emulates the effective backoff of an ensemble of N
 119   // TCP-Reno connections on a single loss event. The effective multiplier is
 120   // computed as:
 121   return (num_connections_ - 1 + kRenoBeta) / num_connections_;
 122 }
 123
 124 void TcpCubicBytesSender::OnCongestionEvent(
 125     bool rtt_updated,
 126     QuicByteCount bytes_in_flight,
 127     const CongestionVector& acked_packets,
 128     const CongestionVector& lost_packets) {
 129   if (rtt_updated && InSlowStart() &&
 130       hybrid_slow_start_.ShouldExitSlowStart(
 131           rtt_stats_->latest_rtt(), rtt_stats_->min_rtt(),
 132           congestion_window_ / kMaxSegmentSize)) {
 133     slowstart_threshold_ = congestion_window_;
 134   }
 135   for (CongestionVector::const_iterator it = lost_packets.begin();
 136        it != lost_packets.end(); ++it) {
 137     OnPacketLost(it->first, bytes_in_flight);
 138   }
 139   for (CongestionVector::const_iterator it = acked_packets.begin();
 140        it != acked_packets.end(); ++it) {
 141     OnPacketAcked(it->first, it->second.bytes_sent, bytes_in_flight);
 142   }
 143 }
 144
 145 void TcpCubicBytesSender::OnPacketAcked(
 146     QuicPacketSequenceNumber acked_sequence_number,
 147     QuicByteCount acked_bytes,
 148     QuicByteCount bytes_in_flight) {
 149   largest_acked_sequence_number_ =
 150       max(acked_sequence_number, largest_acked_sequence_number_);
 151   if (InRecovery()) {
 152     // PRR is used when in recovery.
 153     prr_.OnPacketAcked(acked_bytes);
 154     return;
 155   }
 156   MaybeIncreaseCwnd(acked_sequence_number, acked_bytes, bytes_in_flight);
 157   // TODO(ianswett): Should this even be called when not in slow start?
 158   hybrid_slow_start_.OnPacketAcked(acked_sequence_number, InSlowStart());
 159 }
 160
 161 void TcpCubicBytesSender::OnPacketLost(QuicPacketSequenceNumber sequence_number,
 162                                        QuicByteCount bytes_in_flight) {
 163   // TCP NewReno (RFC6582) says that once a loss occurs, any losses in packets
 164   // already sent should be treated as a single loss event, since it's expected.
 165   if (sequence_number <= largest_sent_at_last_cutback_) {
 166     if (last_cutback_exited_slowstart_) {
 167       ++stats_->slowstart_packets_lost;
 168     }
 169     DVLOG(1) << "Ignoring loss for largest_missing:" << sequence_number
 170              << " because it was sent prior to the last CWND cutback.";
 171     return;
 172   }
 173   ++stats_->tcp_loss_events;
 174   last_cutback_exited_slowstart_ = InSlowStart();
 175   if (InSlowStart()) {
 176     ++stats_->slowstart_packets_lost;
 177   }
 178
 179   prr_.OnPacketLost(bytes_in_flight);
 180
 181   if (reno_) {
 182     congestion_window_ = congestion_window_ * RenoBeta();
 183   } else {
 184     congestion_window_ =
 185         cubic_.CongestionWindowAfterPacketLoss(congestion_window_);
 186   }
 187   slowstart_threshold_ = congestion_window_;
 188   // Enforce TCP's minimum congestion window of 2*MSS.
 189   if (congestion_window_ < min_congestion_window_) {
 190     congestion_window_ = min_congestion_window_;
 191   }
 192   largest_sent_at_last_cutback_ = largest_sent_sequence_number_;
 193   // Reset packet count from congestion avoidance mode. We start counting again
 194   // when we're out of recovery.
 195   num_acked_packets_ = 0;
 196   DVLOG(1) << "Incoming loss; congestion window: " << congestion_window_
 197            << " slowstart threshold: " << slowstart_threshold_;
 198 }
 199
 200 bool TcpCubicBytesSender::OnPacketSent(
 201     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 TcpCubicBytesSender::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_);
 236   }
 237   if (GetCongestionWindow() > bytes_in_flight) {
 238     return QuicTime::Delta::Zero();
 239   }
 240   return QuicTime::Delta::Infinite();
 241 }
 242
 243 QuicBandwidth TcpCubicBytesSender::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 TcpCubicBytesSender::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 TcpCubicBytesSender::HasReliableBandwidthEstimate() const {
 266   return !InSlowStart() && !InRecovery() &&
 267          !rtt_stats_->smoothed_rtt().IsZero();
 268 }
 269
 270 QuicTime::Delta TcpCubicBytesSender::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 TcpCubicBytesSender::GetCongestionWindow() const {
 279   return congestion_window_;
 280 }
 281
 282 bool TcpCubicBytesSender::InSlowStart() const {
 283   return congestion_window_ < slowstart_threshold_;
 284 }
 285
 286 QuicByteCount TcpCubicBytesSender::GetSlowStartThreshold() const {
 287   return slowstart_threshold_;
 288 }
 289
 290 bool TcpCubicBytesSender::IsCwndLimited(QuicByteCount bytes_in_flight) const {
 291   if (bytes_in_flight >= congestion_window_) {
 292     return true;
 293   }
 294   const QuicByteCount max_burst = kMaxBurstLength * kMaxSegmentSize;
 295   const QuicByteCount available_bytes = congestion_window_ - bytes_in_flight;
 296   const bool slow_start_limited =
 297       InSlowStart() && bytes_in_flight > congestion_window_ / 2;
 298   return slow_start_limited || available_bytes <= max_burst;
 299 }
 300
 301 bool TcpCubicBytesSender::InRecovery() const {
 302   return largest_acked_sequence_number_ <= largest_sent_at_last_cutback_ &&
 303          largest_acked_sequence_number_ != 0;
 304 }
 305
 306 // Called when we receive an ack. Normal TCP tracks how many packets one ack
 307 // represents, but quic has a separate ack for each packet.
 308 void TcpCubicBytesSender::MaybeIncreaseCwnd(
 309     QuicPacketSequenceNumber acked_sequence_number,
 310     QuicByteCount acked_bytes,
 311     QuicByteCount bytes_in_flight) {
 312   LOG_IF(DFATAL, InRecovery()) << "Never increase the CWND during recovery.";
 313   if (!IsCwndLimited(bytes_in_flight)) {
 314     // We don't update the congestion window unless we are close to using the
 315     // window we have available.
 316     return;
 317   }
 318   if (congestion_window_ >= max_congestion_window_) {
 319     return;
 320   }
 321   if (InSlowStart()) {
 322     // TCP slow start, exponential growth, increase by one for each ACK.
 323     congestion_window_ += kMaxSegmentSize;
 324     DVLOG(1) << "Slow start; congestion window: " << congestion_window_
 325              << " slowstart threshold: " << slowstart_threshold_;
 326     return;
 327   }
 328   // Congestion avoidance.
 329   if (reno_) {
 330     // Classic Reno congestion avoidance.
 331     ++num_acked_packets_;
 332     // Divide by num_connections to smoothly increase the CWND at a faster rate
 333     // than conventional Reno.
 334     if (num_acked_packets_ * num_connections_ >=
 335         congestion_window_ / kMaxSegmentSize) {
 336       congestion_window_ += kMaxSegmentSize;
 337       num_acked_packets_ = 0;
 338     }
 339
 340     DVLOG(1) << "Reno; congestion window: " << congestion_window_
 341              << " slowstart threshold: " << slowstart_threshold_
 342              << " congestion window count: " << num_acked_packets_;
 343   } else {
 344     congestion_window_ = cubic_.CongestionWindowAfterAck(
 345         acked_bytes, congestion_window_, rtt_stats_->min_rtt());
 346     DVLOG(1) << "Cubic; congestion window: " << congestion_window_
 347              << " slowstart threshold: " << slowstart_threshold_;
 348   }
 349 }
 350
 351 void TcpCubicBytesSender::OnRetransmissionTimeout(bool packets_retransmitted) {
 352   largest_sent_at_last_cutback_ = 0;
 353   if (!packets_retransmitted) {
 354     return;
 355   }
 356   cubic_.Reset();
 357   hybrid_slow_start_.Restart();
 358   slowstart_threshold_ = congestion_window_ / 2;
 359   congestion_window_ = min_congestion_window_;
 360 }
 361
 362 CongestionControlType TcpCubicBytesSender::GetCongestionControlType() const {
 363   return reno_ ? kRenoBytes : kCubicBytes;
 364 }
 365
 366 }  // namespace net