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_sequence_number_(0),
  44       largest_acked_sequence_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
  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(
 137     QuicPacketSequenceNumber acked_sequence_number,
 138     QuicByteCount acked_bytes,
 139     QuicByteCount bytes_in_flight) {
 140   largest_acked_sequence_number_ =
 141       max(acked_sequence_number, largest_acked_sequence_number_);
 142   if (InRecovery()) {
 143     // PRR is used when in recovery.
 144     prr_.OnPacketAcked(acked_bytes);
 145     return;
 146   }
 147   MaybeIncreaseCwnd(acked_sequence_number, acked_bytes, bytes_in_flight);
 148   // TODO(ianswett): Should this even be called when not in slow start?
 149   hybrid_slow_start_.OnPacketAcked(acked_sequence_number, InSlowStart());
 150 }
 151
 152 void TcpCubicBytesSender::OnPacketLost(QuicPacketSequenceNumber sequence_number,
 153                                        QuicByteCount bytes_in_flight) {
 154   // TCP NewReno (RFC6582) says that once a loss occurs, any losses in packets
 155   // already sent should be treated as a single loss event, since it's expected.
 156   if (sequence_number <= largest_sent_at_last_cutback_) {
 157     if (last_cutback_exited_slowstart_) {
 158       ++stats_->slowstart_packets_lost;
 159     }
 160     DVLOG(1) << "Ignoring loss for largest_missing:" << sequence_number
 161              << " because it was sent prior to the last CWND cutback.";
 162     return;
 163   }
 164   ++stats_->tcp_loss_events;
 165   last_cutback_exited_slowstart_ = InSlowStart();
 166   if (InSlowStart()) {
 167     ++stats_->slowstart_packets_lost;
 168   }
 169
 170   prr_.OnPacketLost(bytes_in_flight);
 171
 172   if (reno_) {
 173     congestion_window_ = congestion_window_ * RenoBeta();
 174   } else {
 175     congestion_window_ =
 176         cubic_.CongestionWindowAfterPacketLoss(congestion_window_);
 177   }
 178   slowstart_threshold_ = congestion_window_;
 179   // Enforce TCP's minimum congestion window of 2*MSS.
 180   if (congestion_window_ < min_congestion_window_) {
 181     congestion_window_ = min_congestion_window_;
 182   }
 183   largest_sent_at_last_cutback_ = largest_sent_sequence_number_;
 184   // Reset packet count from congestion avoidance mode. We start counting again
 185   // when we're out of recovery.
 186   num_acked_packets_ = 0;
 187   DVLOG(1) << "Incoming loss; congestion window: " << congestion_window_
 188            << " slowstart threshold: " << slowstart_threshold_;
 189 }
 190
 191 bool TcpCubicBytesSender::OnPacketSent(
 192     QuicTime /*sent_time*/,
 193     QuicByteCount /*bytes_in_flight*/,
 194     QuicPacketSequenceNumber sequence_number,
 195     QuicByteCount bytes,
 196     HasRetransmittableData is_retransmittable) {
 197   if (InSlowStart()) {
 198     ++(stats_->slowstart_packets_sent);
 199   }
 200
 201   // Only update bytes_in_flight_ for data packets.
 202   if (is_retransmittable != HAS_RETRANSMITTABLE_DATA) {
 203     return false;
 204   }
 205   if (InRecovery()) {
 206     // PRR is used when in recovery.
 207     prr_.OnPacketSent(bytes);
 208   }
 209   DCHECK_LT(largest_sent_sequence_number_, sequence_number);
 210   largest_sent_sequence_number_ = sequence_number;
 211   hybrid_slow_start_.OnPacketSent(sequence_number);
 212   return true;
 213 }
 214
 215 QuicTime::Delta TcpCubicBytesSender::TimeUntilSend(
 216     QuicTime /* now */,
 217     QuicByteCount bytes_in_flight,
 218     HasRetransmittableData has_retransmittable_data) const {
 219   if (has_retransmittable_data == NO_RETRANSMITTABLE_DATA) {
 220     // For TCP we can always send an ACK immediately.
 221     return QuicTime::Delta::Zero();
 222   }
 223   if (InRecovery()) {
 224     // PRR is used when in recovery.
 225     return prr_.TimeUntilSend(GetCongestionWindow(), bytes_in_flight,
 226                               slowstart_threshold_);
 227   }
 228   if (GetCongestionWindow() > bytes_in_flight) {
 229     return QuicTime::Delta::Zero();
 230   }
 231   if (min4_mode_ && bytes_in_flight < 4 * kMaxSegmentSize) {
 232     return QuicTime::Delta::Zero();
 233   }
 234   return QuicTime::Delta::Infinite();
 235 }
 236
 237 QuicBandwidth TcpCubicBytesSender::PacingRate() const {
 238   // We pace at twice the rate of the underlying sender's bandwidth estimate
 239   // during slow start and 1.25x during congestion avoidance to ensure pacing
 240   // doesn't prevent us from filling the window.
 241   QuicTime::Delta srtt = rtt_stats_->smoothed_rtt();
 242   if (srtt.IsZero()) {
 243     srtt = QuicTime::Delta::FromMicroseconds(rtt_stats_->initial_rtt_us());
 244   }
 245   const QuicBandwidth bandwidth =
 246       QuicBandwidth::FromBytesAndTimeDelta(GetCongestionWindow(), srtt);
 247   return bandwidth.Scale(InSlowStart() ? 2 : 1.25);
 248 }
 249
 250 QuicBandwidth TcpCubicBytesSender::BandwidthEstimate() const {
 251   QuicTime::Delta srtt = rtt_stats_->smoothed_rtt();
 252   if (srtt.IsZero()) {
 253     // If we haven't measured an rtt, the bandwidth estimate is unknown.
 254     return QuicBandwidth::Zero();
 255   }
 256   return QuicBandwidth::FromBytesAndTimeDelta(GetCongestionWindow(), srtt);
 257 }
 258
 259 QuicTime::Delta TcpCubicBytesSender::RetransmissionDelay() const {
 260   if (rtt_stats_->smoothed_rtt().IsZero()) {
 261     return QuicTime::Delta::Zero();
 262   }
 263   return rtt_stats_->smoothed_rtt().Add(
 264       rtt_stats_->mean_deviation().Multiply(4));
 265 }
 266
 267 QuicByteCount TcpCubicBytesSender::GetCongestionWindow() const {
 268   return congestion_window_;
 269 }
 270
 271 bool TcpCubicBytesSender::InSlowStart() const {
 272   return congestion_window_ < slowstart_threshold_;
 273 }
 274
 275 QuicByteCount TcpCubicBytesSender::GetSlowStartThreshold() const {
 276   return slowstart_threshold_;
 277 }
 278
 279 bool TcpCubicBytesSender::IsCwndLimited(QuicByteCount bytes_in_flight) const {
 280   if (bytes_in_flight >= congestion_window_) {
 281     return true;
 282   }
 283   const QuicByteCount available_bytes = congestion_window_ - bytes_in_flight;
 284   const bool slow_start_limited =
 285       InSlowStart() && bytes_in_flight > congestion_window_ / 2;
 286   return slow_start_limited || available_bytes <= kMaxBurstBytes;
 287 }
 288
 289 bool TcpCubicBytesSender::InRecovery() const {
 290   return largest_acked_sequence_number_ <= largest_sent_at_last_cutback_ &&
 291          largest_acked_sequence_number_ != 0;
 292 }
 293
 294 // Called when we receive an ack. Normal TCP tracks how many packets one ack
 295 // represents, but quic has a separate ack for each packet.
 296 void TcpCubicBytesSender::MaybeIncreaseCwnd(
 297     QuicPacketSequenceNumber acked_sequence_number,
 298     QuicByteCount acked_bytes,
 299     QuicByteCount bytes_in_flight) {
 300   LOG_IF(DFATAL, InRecovery()) << "Never increase the CWND during recovery.";
 301   if (!IsCwndLimited(bytes_in_flight)) {
 302     // We don't update the congestion window unless we are close to using the
 303     // window we have available.
 304     return;
 305   }
 306   if (congestion_window_ >= max_congestion_window_) {
 307     return;
 308   }
 309   if (InSlowStart()) {
 310     // TCP slow start, exponential growth, increase by one for each ACK.
 311     congestion_window_ += kMaxSegmentSize;
 312     DVLOG(1) << "Slow start; congestion window: " << congestion_window_
 313              << " slowstart threshold: " << slowstart_threshold_;
 314     return;
 315   }
 316   // Congestion avoidance.
 317   if (reno_) {
 318     // Classic Reno congestion avoidance.
 319     ++num_acked_packets_;
 320     // Divide by num_connections to smoothly increase the CWND at a faster rate
 321     // than conventional Reno.
 322     if (num_acked_packets_ * num_connections_ >=
 323         congestion_window_ / kMaxSegmentSize) {
 324       congestion_window_ += kMaxSegmentSize;
 325       num_acked_packets_ = 0;
 326     }
 327
 328     DVLOG(1) << "Reno; congestion window: " << congestion_window_
 329              << " slowstart threshold: " << slowstart_threshold_
 330              << " congestion window count: " << num_acked_packets_;
 331   } else {
 332     congestion_window_ =
 333         min(max_congestion_window_,
 334             cubic_.CongestionWindowAfterAck(acked_bytes, congestion_window_,
 335                                             rtt_stats_->min_rtt()));
 336     DVLOG(1) << "Cubic; congestion window: " << congestion_window_
 337              << " slowstart threshold: " << slowstart_threshold_;
 338   }
 339 }
 340
 341 void TcpCubicBytesSender::OnRetransmissionTimeout(bool packets_retransmitted) {
 342   largest_sent_at_last_cutback_ = 0;
 343   if (!packets_retransmitted) {
 344     return;
 345   }
 346   cubic_.Reset();
 347   hybrid_slow_start_.Restart();
 348   slowstart_threshold_ = congestion_window_ / 2;
 349   congestion_window_ = min_congestion_window_;
 350 }
 351
 352 CongestionControlType TcpCubicBytesSender::GetCongestionControlType() const {
 353   return reno_ ? kRenoBytes : kCubicBytes;
 354 }
 355
 356 }  // namespace net