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) {
  82     OnRttUpdated();
  83   }
  84   for (CongestionMap::const_iterator it = lost_packets.begin();
  85        it != lost_packets.end(); ++it) {
  86     OnPacketLost(it->first, bytes_in_flight);
  87   }
  88   for (CongestionMap::const_iterator it = acked_packets.begin();
  89        it != acked_packets.end(); ++it) {
  90     OnPacketAcked(it->first, it->second.bytes_sent, bytes_in_flight);
  91   }
  92 }
  93
  94 void TcpCubicSender::OnPacketAcked(
  95     QuicPacketSequenceNumber acked_sequence_number,
  96     QuicByteCount acked_bytes,
  97     QuicByteCount bytes_in_flight) {
  98   largest_acked_sequence_number_ = max(acked_sequence_number,
  99                                        largest_acked_sequence_number_);
 100   if (InRecovery()) {
 101     PrrOnPacketAcked(acked_bytes);
 102     return;
 103   }
 104   MaybeIncreaseCwnd(acked_sequence_number, bytes_in_flight);
 105   // TODO(ianswett): Should this even be called when not in slow start?
 106   hybrid_slow_start_.OnPacketAcked(acked_sequence_number, InSlowStart());
 107 }
 108
 109 void TcpCubicSender::OnPacketLost(QuicPacketSequenceNumber sequence_number,
 110                                   QuicByteCount bytes_in_flight) {
 111   // TCP NewReno (RFC6582) says that once a loss occurs, any losses in packets
 112   // already sent should be treated as a single loss event, since it's expected.
 113   if (sequence_number <= largest_sent_at_last_cutback_) {
 114     if (last_cutback_exited_slowstart_) {
 115       ++stats_->slowstart_packets_lost;
 116     }
 117     DVLOG(1) << "Ignoring loss for largest_missing:" << sequence_number
 118              << " because it was sent prior to the last CWND cutback.";
 119     return;
 120   }
 121   ++stats_->tcp_loss_events;
 122   last_cutback_exited_slowstart_ = InSlowStart();
 123   if (InSlowStart()) {
 124     ++stats_->slowstart_packets_lost;
 125   }
 126   PrrOnPacketLost(bytes_in_flight);
 127
 128   // In a normal TCP we would need to know the lowest missing packet to detect
 129   // if we receive 3 missing packets. Here we get a missing packet for which we
 130   // enter TCP Fast Retransmit immediately.
 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 minimimum 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                                   QuicPacketSequenceNumber sequence_number,
 152                                   QuicByteCount bytes,
 153                                   HasRetransmittableData is_retransmittable) {
 154   // Only update bytes_in_flight_ for data packets.
 155   if (is_retransmittable != HAS_RETRANSMITTABLE_DATA) {
 156     return false;
 157   }
 158
 159   prr_out_ += bytes;
 160   if (largest_sent_sequence_number_ < sequence_number) {
 161     // TODO(rch): Ensure that packets are really sent in order.
 162     // DCHECK_LT(largest_sent_sequence_number_, sequence_number);
 163     largest_sent_sequence_number_ = sequence_number;
 164   }
 165   hybrid_slow_start_.OnPacketSent(sequence_number);
 166   return true;
 167 }
 168
 169 QuicTime::Delta TcpCubicSender::TimeUntilSend(
 170     QuicTime /* now */,
 171     QuicByteCount bytes_in_flight,
 172     HasRetransmittableData has_retransmittable_data) {
 173   if (has_retransmittable_data == NO_RETRANSMITTABLE_DATA) {
 174     // For TCP we can always send an ACK immediately.
 175     // We also allow tail loss probes to be sent immediately, in keeping with
 176     // tail loss probe (draft-dukkipati-tcpm-tcp-loss-probe-01).
 177     return QuicTime::Delta::Zero();
 178   }
 179   if (InRecovery()) {
 180     return PrrTimeUntilSend(bytes_in_flight);
 181   }
 182   if (AvailableSendWindow(bytes_in_flight) > 0) {
 183     return QuicTime::Delta::Zero();
 184   }
 185   return QuicTime::Delta::Infinite();
 186 }
 187
 188 QuicByteCount TcpCubicSender::AvailableSendWindow(
 189     QuicByteCount bytes_in_flight) {
 190   if (bytes_in_flight > SendWindow()) {
 191     return 0;
 192   }
 193   return SendWindow() - bytes_in_flight;
 194 }
 195
 196 QuicByteCount TcpCubicSender::SendWindow() {
 197   // What's the current send window in bytes.
 198   return min(receive_window_, GetCongestionWindow());
 199 }
 200
 201 QuicBandwidth TcpCubicSender::BandwidthEstimate() const {
 202   return QuicBandwidth::FromBytesAndTimeDelta(GetCongestionWindow(),
 203                                               rtt_stats_->SmoothedRtt());
 204 }
 205
 206 QuicTime::Delta TcpCubicSender::RetransmissionDelay() const {
 207   if (!rtt_stats_->HasUpdates()) {
 208     return QuicTime::Delta::Zero();
 209   }
 210   return QuicTime::Delta::FromMicroseconds(
 211       rtt_stats_->SmoothedRtt().ToMicroseconds() +
 212       4 * rtt_stats_->mean_deviation().ToMicroseconds());
 213 }
 214
 215 QuicByteCount TcpCubicSender::GetCongestionWindow() const {
 216   return congestion_window_ * kMaxSegmentSize;
 217 }
 218
 219 bool TcpCubicSender::IsCwndLimited(QuicByteCount bytes_in_flight) const {
 220   const QuicByteCount congestion_window_bytes = congestion_window_ *
 221       kMaxSegmentSize;
 222   if (bytes_in_flight >= congestion_window_bytes) {
 223     return true;
 224   }
 225   const QuicByteCount tcp_max_burst = kMaxBurstLength * kMaxSegmentSize;
 226   const QuicByteCount left = congestion_window_bytes - bytes_in_flight;
 227   return left <= tcp_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     cubic_.Reset();
 285     hybrid_slow_start_.Restart();
 286     congestion_window_ = kMinimumCongestionWindow;
 287   }
 288 }
 289
 290 void TcpCubicSender::OnRttUpdated() {
 291   if (InSlowStart() &&
 292       hybrid_slow_start_.ShouldExitSlowStart(rtt_stats_->latest_rtt(),
 293                                              rtt_stats_->min_rtt(),
 294                                              congestion_window_)) {
 295      slowstart_threshold_ = congestion_window_;
 296   }
 297 }
 298
 299 void TcpCubicSender::PrrOnPacketLost(QuicByteCount bytes_in_flight) {
 300   prr_out_ = 0;
 301   bytes_in_flight_before_loss_ = bytes_in_flight;
 302   prr_delivered_ = 0;
 303   ack_count_since_loss_ = 0;
 304 }
 305
 306 void TcpCubicSender::PrrOnPacketAcked(QuicByteCount acked_bytes) {
 307   prr_delivered_ += acked_bytes;
 308   ++ack_count_since_loss_;
 309 }
 310
 311 QuicTime::Delta TcpCubicSender::PrrTimeUntilSend(
 312     QuicByteCount bytes_in_flight) {
 313   DCHECK(InRecovery());
 314   // Return QuicTime::Zero In order to ensure limited transmit always works.
 315   if (prr_out_ == 0) {
 316     return QuicTime::Delta::Zero();
 317   }
 318   if (AvailableSendWindow(bytes_in_flight) > 0) {
 319     // During PRR-SSRB, limit outgoing packets to 1 extra MSS per ack, instead
 320     // of sending the entire available window. This prevents burst retransmits
 321     // when more packets are lost than the CWND reduction.
 322     //   limit = MAX(prr_delivered - prr_out, DeliveredData) + MSS
 323     if (prr_delivered_ + ack_count_since_loss_ * kMaxSegmentSize <= prr_out_) {
 324       return QuicTime::Delta::Infinite();
 325     }
 326     return QuicTime::Delta::Zero();
 327   }
 328   // Implement Proportional Rate Reduction (RFC6937)
 329   // Checks a simplified version of the PRR formula that doesn't use division:
 330   // AvailableSendWindow =
 331   //   CEIL(prr_delivered * ssthresh / BytesInFlightAtLoss) - prr_sent
 332   if (prr_delivered_ * slowstart_threshold_ * kMaxSegmentSize >
 333           prr_out_ * bytes_in_flight_before_loss_) {
 334     return QuicTime::Delta::Zero();
 335   }
 336   return QuicTime::Delta::Infinite();
 337 }
 338
 339 }  // namespace net