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