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