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