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