net/quic/congestion_control/tcp_cubic_sender.cc

   1 // Copyright (c) 2012 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_sender.h"
   6
   7 #include <algorithm>
   8
   9 #include "base/metrics/histogram_macros.h"
  10 #include "net/quic/congestion_control/prr_sender.h"
  11 #include "net/quic/congestion_control/rtt_stats.h"
  12 #include "net/quic/crypto/crypto_protocol.h"
  13 #include "net/quic/proto/cached_network_parameters.pb.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.  The cwnd after a timeout is still 1.
  24 const QuicPacketCount kDefaultMinimumCongestionWindow = 2;
  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 TcpCubicSender::TcpCubicSender(const QuicClock* clock,
  32                                const RttStats* rtt_stats,
  33                                bool reno,
  34                                QuicPacketCount initial_tcp_congestion_window,
  35                                QuicPacketCount max_tcp_congestion_window,
  36                                QuicConnectionStats* stats)
  37     : cubic_(clock),
  38       rtt_stats_(rtt_stats),
  39       stats_(stats),
  40       reno_(reno),
  41       num_connections_(kDefaultNumConnections),
  42       congestion_window_count_(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),
  47       min_congestion_window_(kDefaultMinimumCongestionWindow),
  48       min4_mode_(false),
  49       slowstart_threshold_(max_tcp_congestion_window),
  50       last_cutback_exited_slowstart_(false),
  51       max_tcp_congestion_window_(max_tcp_congestion_window),
  52       clock_(clock) {}
  53
  54 TcpCubicSender::~TcpCubicSender() {
  55   UMA_HISTOGRAM_COUNTS("Net.QuicSession.FinalTcpCwnd", congestion_window_);
  56 }
  57
  58 void TcpCubicSender::SetFromConfig(const QuicConfig& config,
  59                                    Perspective perspective) {
  60   if (perspective == Perspective::IS_SERVER) {
  61     if (config.HasReceivedConnectionOptions() &&
  62         ContainsQuicTag(config.ReceivedConnectionOptions(), kIW03)) {
  63       // Initial window experiment.
  64       congestion_window_ = 3;
  65     }
  66     if (config.HasReceivedConnectionOptions() &&
  67         ContainsQuicTag(config.ReceivedConnectionOptions(), kIW10)) {
  68       // Initial window experiment.
  69       congestion_window_ = 10;
  70     }
  71     if (config.HasReceivedConnectionOptions() &&
  72         ContainsQuicTag(config.ReceivedConnectionOptions(), kIW20)) {
  73       // Initial window experiment.
  74       congestion_window_ = 20;
  75     }
  76     if (config.HasReceivedConnectionOptions() &&
  77         ContainsQuicTag(config.ReceivedConnectionOptions(), kIW50)) {
  78       // Initial window experiment.
  79       congestion_window_ = 50;
  80     }
  81     if (config.HasReceivedConnectionOptions() &&
  82         ContainsQuicTag(config.ReceivedConnectionOptions(), kMIN1)) {
  83       // Min CWND experiment.
  84       min_congestion_window_ = 1;
  85     }
  86     if (config.HasReceivedConnectionOptions() &&
  87         ContainsQuicTag(config.ReceivedConnectionOptions(), kMIN4)) {
  88       // Min CWND of 4 experiment.
  89       min4_mode_ = true;
  90       min_congestion_window_ = 1;
  91     }
  92   }
  93 }
  94
  95 void TcpCubicSender::ResumeConnectionState(
  96     const CachedNetworkParameters& cached_network_params,
  97     bool max_bandwidth_resumption) {
  98   QuicBandwidth bandwidth = QuicBandwidth::FromBytesPerSecond(
  99       max_bandwidth_resumption
 100           ? cached_network_params.max_bandwidth_estimate_bytes_per_second()
 101           : cached_network_params.bandwidth_estimate_bytes_per_second());
 102   QuicTime::Delta rtt_ms =
 103       QuicTime::Delta::FromMilliseconds(cached_network_params.min_rtt_ms());
 104
 105   // Make sure CWND is in appropriate range (in case of bad data).
 106   QuicPacketCount new_congestion_window =
 107       bandwidth.ToBytesPerPeriod(rtt_ms) / kMaxPacketSize;
 108   congestion_window_ = max(min(new_congestion_window, kMaxCongestionWindow),
 109                            kMinCongestionWindowForBandwidthResumption);
 110 }
 111
 112 void TcpCubicSender::SetNumEmulatedConnections(int num_connections) {
 113   num_connections_ = max(1, num_connections);
 114   cubic_.SetNumConnections(num_connections_);
 115 }
 116
 117 void TcpCubicSender::SetMaxCongestionWindow(
 118     QuicByteCount max_congestion_window) {
 119   max_tcp_congestion_window_ = max_congestion_window / kMaxPacketSize;
 120 }
 121
 122 float TcpCubicSender::RenoBeta() const {
 123   // kNConnectionBeta is the backoff factor after loss for our N-connection
 124   // emulation, which emulates the effective backoff of an ensemble of N
 125   // TCP-Reno connections on a single loss event. The effective multiplier is
 126   // computed as:
 127   return (num_connections_ - 1 + kRenoBeta) / num_connections_;
 128 }
 129
 130 void TcpCubicSender::OnCongestionEvent(
 131     bool rtt_updated,
 132     QuicByteCount bytes_in_flight,
 133     const CongestionVector& acked_packets,
 134     const CongestionVector& lost_packets) {
 135   if (rtt_updated && InSlowStart() &&
 136       hybrid_slow_start_.ShouldExitSlowStart(rtt_stats_->latest_rtt(),
 137                                              rtt_stats_->min_rtt(),
 138                                              congestion_window_)) {
 139     slowstart_threshold_ = congestion_window_;
 140   }
 141   for (CongestionVector::const_iterator it = lost_packets.begin();
 142        it != lost_packets.end(); ++it) {
 143     OnPacketLost(it->first, bytes_in_flight);
 144   }
 145   for (CongestionVector::const_iterator it = acked_packets.begin();
 146        it != acked_packets.end(); ++it) {
 147     OnPacketAcked(it->first, it->second.bytes_sent, bytes_in_flight);
 148   }
 149 }
 150
 151 void TcpCubicSender::OnPacketAcked(QuicPacketNumber acked_packet_number,
 152                                    QuicByteCount acked_bytes,
 153                                    QuicByteCount bytes_in_flight) {
 154   largest_acked_packet_number_ =
 155       max(acked_packet_number, largest_acked_packet_number_);
 156   if (InRecovery()) {
 157     // PRR is used when in recovery.
 158     prr_.OnPacketAcked(acked_bytes);
 159     return;
 160   }
 161   MaybeIncreaseCwnd(acked_packet_number, bytes_in_flight);
 162   // TODO(ianswett): Should this even be called when not in slow start?
 163   hybrid_slow_start_.OnPacketAcked(acked_packet_number, InSlowStart());
 164 }
 165
 166 void TcpCubicSender::OnPacketLost(QuicPacketNumber packet_number,
 167                                   QuicByteCount bytes_in_flight) {
 168   // TCP NewReno (RFC6582) says that once a loss occurs, any losses in packets
 169   // already sent should be treated as a single loss event, since it's expected.
 170   if (packet_number <= largest_sent_at_last_cutback_) {
 171     if (last_cutback_exited_slowstart_) {
 172       ++stats_->slowstart_packets_lost;
 173     }
 174     DVLOG(1) << "Ignoring loss for largest_missing:" << packet_number
 175              << " because it was sent prior to the last CWND cutback.";
 176     return;
 177   }
 178   ++stats_->tcp_loss_events;
 179   last_cutback_exited_slowstart_ = InSlowStart();
 180   if (InSlowStart()) {
 181     ++stats_->slowstart_packets_lost;
 182   }
 183
 184   prr_.OnPacketLost(bytes_in_flight);
 185
 186   if (reno_) {
 187     congestion_window_ = congestion_window_ * RenoBeta();
 188   } else {
 189     congestion_window_ =
 190         cubic_.CongestionWindowAfterPacketLoss(congestion_window_);
 191   }
 192   slowstart_threshold_ = congestion_window_;
 193   // Enforce a minimum congestion window.
 194   if (congestion_window_ < min_congestion_window_) {
 195     congestion_window_ = min_congestion_window_;
 196   }
 197   largest_sent_at_last_cutback_ = largest_sent_packet_number_;
 198   // reset packet count from congestion avoidance mode. We start
 199   // counting again when we're out of recovery.
 200   congestion_window_count_ = 0;
 201   DVLOG(1) << "Incoming loss; congestion window: " << congestion_window_
 202            << " slowstart threshold: " << slowstart_threshold_;
 203 }
 204
 205 bool TcpCubicSender::OnPacketSent(QuicTime /*sent_time*/,
 206                                   QuicByteCount /*bytes_in_flight*/,
 207                                   QuicPacketNumber packet_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_packet_number_, packet_number);
 223   largest_sent_packet_number_ = packet_number;
 224   hybrid_slow_start_.OnPacketSent(packet_number);
 225   return true;
 226 }
 227
 228 QuicTime::Delta TcpCubicSender::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_ * kMaxSegmentSize);
 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 TcpCubicSender::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 TcpCubicSender::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 QuicTime::Delta TcpCubicSender::RetransmissionDelay() const {
 273   if (rtt_stats_->smoothed_rtt().IsZero()) {
 274     return QuicTime::Delta::Zero();
 275   }
 276   return rtt_stats_->smoothed_rtt().Add(
 277       rtt_stats_->mean_deviation().Multiply(4));
 278 }
 279
 280 QuicByteCount TcpCubicSender::GetCongestionWindow() const {
 281   return congestion_window_ * kMaxSegmentSize;
 282 }
 283
 284 bool TcpCubicSender::InSlowStart() const {
 285   return congestion_window_ < slowstart_threshold_;
 286 }
 287
 288 QuicByteCount TcpCubicSender::GetSlowStartThreshold() const {
 289   return slowstart_threshold_ * kMaxSegmentSize;
 290 }
 291
 292 bool TcpCubicSender::IsCwndLimited(QuicByteCount bytes_in_flight) const {
 293   const QuicByteCount congestion_window_bytes = GetCongestionWindow();
 294   if (bytes_in_flight >= congestion_window_bytes) {
 295     return true;
 296   }
 297   const QuicByteCount available_bytes =
 298       congestion_window_bytes - bytes_in_flight;
 299   const bool slow_start_limited = InSlowStart() &&
 300       bytes_in_flight >  congestion_window_bytes / 2;
 301   return slow_start_limited || available_bytes <= kMaxBurstBytes;
 302 }
 303
 304 bool TcpCubicSender::InRecovery() const {
 305   return largest_acked_packet_number_ <= largest_sent_at_last_cutback_ &&
 306          largest_acked_packet_number_ != 0;
 307 }
 308
 309 // Called when we receive an ack. Normal TCP tracks how many packets one ack
 310 // represents, but quic has a separate ack for each packet.
 311 void TcpCubicSender::MaybeIncreaseCwnd(QuicPacketNumber acked_packet_number,
 312                                        QuicByteCount bytes_in_flight) {
 313   LOG_IF(DFATAL, InRecovery()) << "Never increase the CWND during recovery.";
 314   if (!IsCwndLimited(bytes_in_flight)) {
 315     // We don't update the congestion window unless we are close to using the
 316     // window we have available.
 317     return;
 318   }
 319   if (congestion_window_ >= max_tcp_congestion_window_) {
 320     return;
 321   }
 322   if (InSlowStart()) {
 323     // TCP slow start, exponential growth, increase by one for each ACK.
 324     ++congestion_window_;
 325     DVLOG(1) << "Slow start; congestion window: " << congestion_window_
 326              << " slowstart threshold: " << slowstart_threshold_;
 327     return;
 328   }
 329   // Congestion avoidance
 330   if (reno_) {
 331     // Classic Reno congestion avoidance.
 332     ++congestion_window_count_;
 333     // Divide by num_connections to smoothly increase the CWND at a faster
 334     // rate than conventional Reno.
 335     if (congestion_window_count_ * num_connections_ >= congestion_window_) {
 336       ++congestion_window_;
 337       congestion_window_count_ = 0;
 338     }
 339
 340     DVLOG(1) << "Reno; congestion window: " << congestion_window_
 341              << " slowstart threshold: " << slowstart_threshold_
 342              << " congestion window count: " << congestion_window_count_;
 343   } else {
 344     congestion_window_ = min(max_tcp_congestion_window_,
 345                              cubic_.CongestionWindowAfterAck(
 346                                  congestion_window_, rtt_stats_->min_rtt()));
 347     DVLOG(1) << "Cubic; congestion window: " << congestion_window_
 348              << " slowstart threshold: " << slowstart_threshold_;
 349   }
 350 }
 351
 352 void TcpCubicSender::OnRetransmissionTimeout(bool packets_retransmitted) {
 353   largest_sent_at_last_cutback_ = 0;
 354   if (!packets_retransmitted) {
 355     return;
 356   }
 357   cubic_.Reset();
 358   hybrid_slow_start_.Restart();
 359   slowstart_threshold_ = congestion_window_ / 2;
 360   congestion_window_ = min_congestion_window_;
 361 }
 362
 363 CongestionControlType TcpCubicSender::GetCongestionControlType() const {
 364   return reno_ ? kReno : kCubic;
 365 }
 366
 367 }  // namespace net