src/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.h"
  10 #include "net/quic/congestion_control/rtt_stats.h"
  11
  12 using std::max;
  13 using std::min;
  14
  15 namespace net {
  16
  17 namespace {
  18 // Constants based on TCP defaults.
  19 // The minimum cwnd based on RFC 3782 (TCP NewReno) for cwnd reductions on a
  20 // fast retransmission.  The cwnd after a timeout is still 1.
  21 const QuicTcpCongestionWindow kMinimumCongestionWindow = 2;
  22 const QuicByteCount kMaxSegmentSize = kDefaultTCPMSS;
  23 const QuicByteCount kDefaultReceiveWindow = 64000;
  24 const int64 kInitialCongestionWindow = 10;
  25 const int kMaxBurstLength = 3;
  26 };  // namespace
  27
  28 TcpCubicSender::TcpCubicSender(
  29     const QuicClock* clock,
  30     const RttStats* rtt_stats,
  31     bool reno,
  32     QuicTcpCongestionWindow max_tcp_congestion_window,
  33     QuicConnectionStats* stats)
  34     : hybrid_slow_start_(clock),
  35       cubic_(clock, stats),
  36       rtt_stats_(rtt_stats),
  37       stats_(stats),
  38       reno_(reno),
  39       congestion_window_count_(0),
  40       receive_window_(kDefaultReceiveWindow),
  41       prr_out_(0),
  42       prr_delivered_(0),
  43       ack_count_since_loss_(0),
  44       bytes_in_flight_before_loss_(0),
  45       largest_sent_sequence_number_(0),
  46       largest_acked_sequence_number_(0),
  47       largest_sent_at_last_cutback_(0),
  48       congestion_window_(kInitialCongestionWindow),
  49       slowstart_threshold_(max_tcp_congestion_window),
  50       last_cutback_exited_slowstart_(false),
  51       max_tcp_congestion_window_(max_tcp_congestion_window) {
  52 }
  53
  54 TcpCubicSender::~TcpCubicSender() {
  55   UMA_HISTOGRAM_COUNTS("Net.QuicSession.FinalTcpCwnd", congestion_window_);
  56 }
  57
  58 bool TcpCubicSender::InSlowStart() const {
  59   return congestion_window_ < slowstart_threshold_;
  60 }
  61
  62 void TcpCubicSender::SetFromConfig(const QuicConfig& config, bool is_server) {
  63   if (is_server && config.HasReceivedInitialCongestionWindow()) {
  64     // Set the initial window size.
  65     congestion_window_ = min(kMaxInitialWindow,
  66                              config.ReceivedInitialCongestionWindow());
  67   }
  68 }
  69
  70 void TcpCubicSender::OnIncomingQuicCongestionFeedbackFrame(
  71     const QuicCongestionFeedbackFrame& feedback,
  72     QuicTime feedback_receive_time) {
  73   receive_window_ = feedback.tcp.receive_window;
  74 }
  75
  76 void TcpCubicSender::OnCongestionEvent(
  77     bool rtt_updated,
  78     QuicByteCount bytes_in_flight,
  79     const CongestionMap& acked_packets,
  80     const CongestionMap& lost_packets) {
  81   if (rtt_updated && InSlowStart() &&
  82       hybrid_slow_start_.ShouldExitSlowStart(rtt_stats_->latest_rtt(),
  83                                              rtt_stats_->min_rtt(),
  84                                              congestion_window_)) {
  85     slowstart_threshold_ = congestion_window_;
  86   }
  87   for (CongestionMap::const_iterator it = lost_packets.begin();
  88        it != lost_packets.end(); ++it) {
  89     OnPacketLost(it->first, bytes_in_flight);
  90   }
  91   for (CongestionMap::const_iterator it = acked_packets.begin();
  92        it != acked_packets.end(); ++it) {
  93     OnPacketAcked(it->first, it->second.bytes_sent, bytes_in_flight);
  94   }
  95 }
  96
  97 void TcpCubicSender::OnPacketAcked(
  98     QuicPacketSequenceNumber acked_sequence_number,
  99     QuicByteCount acked_bytes,
 100     QuicByteCount bytes_in_flight) {
 101   largest_acked_sequence_number_ = max(acked_sequence_number,
 102                                        largest_acked_sequence_number_);
 103   if (InRecovery()) {
 104     PrrOnPacketAcked(acked_bytes);
 105     return;
 106   }
 107   MaybeIncreaseCwnd(acked_sequence_number, bytes_in_flight);
 108   // TODO(ianswett): Should this even be called when not in slow start?
 109   hybrid_slow_start_.OnPacketAcked(acked_sequence_number, InSlowStart());
 110 }
 111
 112 void TcpCubicSender::OnPacketLost(QuicPacketSequenceNumber sequence_number,
 113                                   QuicByteCount bytes_in_flight) {
 114   // TCP NewReno (RFC6582) says that once a loss occurs, any losses in packets
 115   // already sent should be treated as a single loss event, since it's expected.
 116   if (sequence_number <= largest_sent_at_last_cutback_) {
 117     if (last_cutback_exited_slowstart_) {
 118       ++stats_->slowstart_packets_lost;
 119     }
 120     DVLOG(1) << "Ignoring loss for largest_missing:" << sequence_number
 121              << " because it was sent prior to the last CWND cutback.";
 122     return;
 123   }
 124   ++stats_->tcp_loss_events;
 125   last_cutback_exited_slowstart_ = InSlowStart();
 126   if (InSlowStart()) {
 127     ++stats_->slowstart_packets_lost;
 128   }
 129   PrrOnPacketLost(bytes_in_flight);
 130
 131   if (reno_) {
 132     congestion_window_ = congestion_window_ >> 1;
 133   } else {
 134     congestion_window_ =
 135         cubic_.CongestionWindowAfterPacketLoss(congestion_window_);
 136   }
 137   slowstart_threshold_ = congestion_window_;
 138   // Enforce TCP's minimum congestion window of 2*MSS.
 139   if (congestion_window_ < kMinimumCongestionWindow) {
 140     congestion_window_ = kMinimumCongestionWindow;
 141   }
 142   largest_sent_at_last_cutback_ = largest_sent_sequence_number_;
 143   // reset packet count from congestion avoidance mode. We start
 144   // counting again when we're out of recovery.
 145   congestion_window_count_ = 0;
 146   DVLOG(1) << "Incoming loss; congestion window: " << congestion_window_
 147            << " slowstart threshold: " << slowstart_threshold_;
 148 }
 149
 150 bool TcpCubicSender::OnPacketSent(QuicTime /*sent_time*/,
 151                                   QuicByteCount /*bytes_in_flight*/,
 152                                   QuicPacketSequenceNumber sequence_number,
 153                                   QuicByteCount bytes,
 154                                   HasRetransmittableData is_retransmittable) {
 155   // Only update bytes_in_flight_ for data packets.
 156   if (is_retransmittable != HAS_RETRANSMITTABLE_DATA) {
 157     return false;
 158   }
 159
 160   prr_out_ += bytes;
 161   if (largest_sent_sequence_number_ < sequence_number) {
 162     // TODO(rch): Ensure that packets are really sent in order.
 163     // DCHECK_LT(largest_sent_sequence_number_, sequence_number);
 164     largest_sent_sequence_number_ = sequence_number;
 165   }
 166   hybrid_slow_start_.OnPacketSent(sequence_number);
 167   return true;
 168 }
 169
 170 QuicTime::Delta TcpCubicSender::TimeUntilSend(
 171     QuicTime /* now */,
 172     QuicByteCount bytes_in_flight,
 173     HasRetransmittableData has_retransmittable_data) {
 174   if (has_retransmittable_data == NO_RETRANSMITTABLE_DATA) {
 175     // For TCP we can always send an ACK immediately.
 176     return QuicTime::Delta::Zero();
 177   }
 178   if (InRecovery()) {
 179     return PrrTimeUntilSend(bytes_in_flight);
 180   }
 181   if (SendWindow() > bytes_in_flight) {
 182     return QuicTime::Delta::Zero();
 183   }
 184   return QuicTime::Delta::Infinite();
 185 }
 186
 187 QuicByteCount TcpCubicSender::SendWindow() {
 188   // What's the current send window in bytes.
 189   return min(receive_window_, GetCongestionWindow());
 190 }
 191
 192 QuicBandwidth TcpCubicSender::BandwidthEstimate() const {
 193   return QuicBandwidth::FromBytesAndTimeDelta(GetCongestionWindow(),
 194                                               rtt_stats_->SmoothedRtt());
 195 }
 196
 197 QuicTime::Delta TcpCubicSender::RetransmissionDelay() const {
 198   if (!rtt_stats_->HasUpdates()) {
 199     return QuicTime::Delta::Zero();
 200   }
 201   return QuicTime::Delta::FromMicroseconds(
 202       rtt_stats_->SmoothedRtt().ToMicroseconds() +
 203       4 * rtt_stats_->mean_deviation().ToMicroseconds());
 204 }
 205
 206 QuicByteCount TcpCubicSender::GetCongestionWindow() const {
 207   return congestion_window_ * kMaxSegmentSize;
 208 }
 209
 210 bool TcpCubicSender::IsCwndLimited(QuicByteCount bytes_in_flight) const {
 211   const QuicByteCount congestion_window_bytes = congestion_window_ *
 212       kMaxSegmentSize;
 213   if (bytes_in_flight >= congestion_window_bytes) {
 214     return true;
 215   }
 216   const QuicByteCount max_burst = kMaxBurstLength * kMaxSegmentSize;
 217   const QuicByteCount available_bytes =
 218       congestion_window_bytes - bytes_in_flight;
 219   const bool slow_start_limited = InSlowStart() &&
 220       bytes_in_flight >  congestion_window_bytes / 2;
 221   return slow_start_limited || available_bytes <= max_burst;
 222 }
 223
 224 bool TcpCubicSender::InRecovery() const {
 225   return largest_acked_sequence_number_ <= largest_sent_at_last_cutback_ &&
 226       largest_acked_sequence_number_ != 0;
 227 }
 228
 229 // Called when we receive an ack. Normal TCP tracks how many packets one ack
 230 // represents, but quic has a separate ack for each packet.
 231 void TcpCubicSender::MaybeIncreaseCwnd(
 232     QuicPacketSequenceNumber acked_sequence_number,
 233     QuicByteCount bytes_in_flight) {
 234   LOG_IF(DFATAL, InRecovery()) << "Never increase the CWND during recovery.";
 235   if (!IsCwndLimited(bytes_in_flight)) {
 236     // We don't update the congestion window unless we are close to using the
 237     // window we have available.
 238     return;
 239   }
 240   if (InSlowStart()) {
 241     // congestion_window_cnt is the number of acks since last change of snd_cwnd
 242     if (congestion_window_ < max_tcp_congestion_window_) {
 243       // TCP slow start, exponential growth, increase by one for each ACK.
 244       ++congestion_window_;
 245     }
 246     DVLOG(1) << "Slow start; congestion window: " << congestion_window_
 247              << " slowstart threshold: " << slowstart_threshold_;
 248     return;
 249   }
 250   if (congestion_window_ >= max_tcp_congestion_window_) {
 251     return;
 252   }
 253   // Congestion avoidance
 254   if (reno_) {
 255     // Classic Reno congestion avoidance provided for testing.
 256
 257     ++congestion_window_count_;
 258     if (congestion_window_count_ >= congestion_window_) {
 259       ++congestion_window_;
 260       congestion_window_count_ = 0;
 261     }
 262
 263     DVLOG(1) << "Reno; congestion window: " << congestion_window_
 264              << " slowstart threshold: " << slowstart_threshold_
 265              << " congestion window count: " << congestion_window_count_;
 266   } else {
 267     congestion_window_ = min(max_tcp_congestion_window_,
 268                              cubic_.CongestionWindowAfterAck(
 269                                  congestion_window_, rtt_stats_->min_rtt()));
 270     DVLOG(1) << "Cubic; congestion window: " << congestion_window_
 271              << " slowstart threshold: " << slowstart_threshold_;
 272   }
 273 }
 274
 275 void TcpCubicSender::OnRetransmissionTimeout(bool packets_retransmitted) {
 276   largest_sent_at_last_cutback_ = 0;
 277   if (packets_retransmitted) {
 278     cubic_.Reset();
 279     hybrid_slow_start_.Restart();
 280     congestion_window_ = kMinimumCongestionWindow;
 281   }
 282 }
 283
 284 void TcpCubicSender::PrrOnPacketLost(QuicByteCount bytes_in_flight) {
 285   prr_out_ = 0;
 286   bytes_in_flight_before_loss_ = bytes_in_flight;
 287   prr_delivered_ = 0;
 288   ack_count_since_loss_ = 0;
 289 }
 290
 291 void TcpCubicSender::PrrOnPacketAcked(QuicByteCount acked_bytes) {
 292   prr_delivered_ += acked_bytes;
 293   ++ack_count_since_loss_;
 294 }
 295
 296 QuicTime::Delta TcpCubicSender::PrrTimeUntilSend(
 297     QuicByteCount bytes_in_flight) {
 298   DCHECK(InRecovery());
 299   // Return QuicTime::Zero In order to ensure limited transmit always works.
 300   if (prr_out_ == 0) {
 301     return QuicTime::Delta::Zero();
 302   }
 303   if (SendWindow() > bytes_in_flight) {
 304     // During PRR-SSRB, limit outgoing packets to 1 extra MSS per ack, instead
 305     // of sending the entire available window. This prevents burst retransmits
 306     // when more packets are lost than the CWND reduction.
 307     //   limit = MAX(prr_delivered - prr_out, DeliveredData) + MSS
 308     if (prr_delivered_ + ack_count_since_loss_ * kMaxSegmentSize <= prr_out_) {
 309       return QuicTime::Delta::Infinite();
 310     }
 311     return QuicTime::Delta::Zero();
 312   }
 313   // Implement Proportional Rate Reduction (RFC6937)
 314   // Checks a simplified version of the PRR formula that doesn't use division:
 315   // AvailableSendWindow =
 316   //   CEIL(prr_delivered * ssthresh / BytesInFlightAtLoss) - prr_sent
 317   if (prr_delivered_ * slowstart_threshold_ * kMaxSegmentSize >
 318           prr_out_ * bytes_in_flight_before_loss_) {
 319     return QuicTime::Delta::Zero();
 320   }
 321   return QuicTime::Delta::Infinite();
 322 }
 323
 324 }  // namespace net