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
  11 using std::max;
  12 using std::min;
  13
  14 namespace net {
  15
  16 namespace {
  17 // Constants based on TCP defaults.
  18 // The minimum cwnd based on RFC 3782 (TCP NewReno) for cwnd reductions on a
  19 // fast retransmission.  The cwnd after a timeout is still 1.
  20 const QuicTcpCongestionWindow kMinimumCongestionWindow = 2;
  21 const int64 kHybridStartLowWindow = 16;
  22 const QuicByteCount kMaxSegmentSize = kDefaultTCPMSS;
  23 const QuicByteCount kDefaultReceiveWindow = 64000;
  24 const int64 kInitialCongestionWindow = 10;
  25 const int kMaxBurstLength = 3;
  26 // Constants used for RTT calculation.
  27 const int kInitialRttMs = 60;  // At a typical RTT 60 ms.
  28 const float kAlpha = 0.125f;
  29 const float kOneMinusAlpha = (1 - kAlpha);
  30 const float kBeta = 0.25f;
  31 const float kOneMinusBeta = (1 - kBeta);
  32 };  // namespace
  33
  34 TcpCubicSender::TcpCubicSender(
  35     const QuicClock* clock,
  36     bool reno,
  37     QuicTcpCongestionWindow max_tcp_congestion_window)
  38     : hybrid_slow_start_(clock),
  39       cubic_(clock),
  40       reno_(reno),
  41       congestion_window_count_(0),
  42       receive_window_(kDefaultReceiveWindow),
  43       last_received_accumulated_number_of_lost_packets_(0),
  44       bytes_in_flight_(0),
  45       prr_out_(0),
  46       prr_delivered_(0),
  47       ack_count_since_loss_(0),
  48       bytes_in_flight_before_loss_(0),
  49       update_end_sequence_number_(true),
  50       end_sequence_number_(0),
  51       largest_sent_sequence_number_(0),
  52       largest_acked_sequence_number_(0),
  53       largest_sent_at_last_cutback_(0),
  54       congestion_window_(kInitialCongestionWindow),
  55       slowstart_threshold_(max_tcp_congestion_window),
  56       max_tcp_congestion_window_(max_tcp_congestion_window),
  57       delay_min_(QuicTime::Delta::Zero()),
  58       smoothed_rtt_(QuicTime::Delta::Zero()),
  59       mean_deviation_(QuicTime::Delta::Zero()) {
  60 }
  61
  62 TcpCubicSender::~TcpCubicSender() {
  63   UMA_HISTOGRAM_COUNTS("Net.QuicSession.FinalTcpCwnd", congestion_window_);
  64 }
  65
  66 void TcpCubicSender::SetMaxPacketSize(QuicByteCount /*max_packet_size*/) {
  67 }
  68
  69 void TcpCubicSender::SetFromConfig(const QuicConfig& config, bool is_server) {
  70   if (is_server) {
  71     // Set the initial window size.
  72     congestion_window_ = config.server_initial_congestion_window();
  73   }
  74 }
  75
  76 void TcpCubicSender::OnIncomingQuicCongestionFeedbackFrame(
  77     const QuicCongestionFeedbackFrame& feedback,
  78     QuicTime feedback_receive_time,
  79     const SentPacketsMap& /*sent_packets*/) {
  80   if (last_received_accumulated_number_of_lost_packets_ !=
  81       feedback.tcp.accumulated_number_of_lost_packets) {
  82     int recovered_lost_packets =
  83         last_received_accumulated_number_of_lost_packets_ -
  84         feedback.tcp.accumulated_number_of_lost_packets;
  85     last_received_accumulated_number_of_lost_packets_ =
  86         feedback.tcp.accumulated_number_of_lost_packets;
  87     if (recovered_lost_packets > 0) {
  88       // Assume the loss could be as late as the last acked packet.
  89       OnPacketLost(largest_acked_sequence_number_, feedback_receive_time);
  90     }
  91   }
  92   receive_window_ = feedback.tcp.receive_window;
  93 }
  94
  95 void TcpCubicSender::OnPacketAcked(
  96     QuicPacketSequenceNumber acked_sequence_number, QuicByteCount acked_bytes) {
  97   DCHECK_GE(bytes_in_flight_, acked_bytes);
  98   bytes_in_flight_ -= acked_bytes;
  99   prr_delivered_ += acked_bytes;
 100   ++ack_count_since_loss_;
 101   largest_acked_sequence_number_ = max(acked_sequence_number,
 102                                        largest_acked_sequence_number_);
 103   MaybeIncreaseCwnd(acked_sequence_number);
 104   if (end_sequence_number_ == acked_sequence_number) {
 105     DVLOG(1) << "Start update end sequence number @" << acked_sequence_number;
 106     update_end_sequence_number_ = true;
 107   }
 108 }
 109
 110 void TcpCubicSender::OnPacketLost(QuicPacketSequenceNumber sequence_number,
 111                                   QuicTime /*ack_receive_time*/) {
 112   // TCP NewReno (RFC6582) says that once a loss occurs, any losses in packets
 113   // already sent should be treated as a single loss event, since it's expected.
 114   if (sequence_number <= largest_sent_at_last_cutback_) {
 115     DVLOG(1) << "Ignoring loss for largest_missing:" << sequence_number
 116                << " because it was sent prior to the last CWND cutback.";
 117     return;
 118   }
 119
 120   // Initialize proportional rate reduction(RFC 6937) variables.
 121   prr_out_ = 0;
 122   bytes_in_flight_before_loss_ = bytes_in_flight_;
 123   // Since all losses are triggered by an incoming ack currently, and acks are
 124   // registered before losses by the SentPacketManager, initialize the variables
 125   // as though one ack was received directly after the loss.  This is too low
 126   // for stretch acks, but we expect missing packets to be immediately acked.
 127   // This ensures 1 or 2 packets are immediately able to be sent, depending upon
 128   // whether we're in PRR or PRR-SSRB mode.
 129   prr_delivered_ = kMaxPacketSize;
 130   ack_count_since_loss_ = 1;
 131
 132   // In a normal TCP we would need to know the lowest missing packet to detect
 133   // if we receive 3 missing packets. Here we get a missing packet for which we
 134   // enter TCP Fast Retransmit immediately.
 135   if (reno_) {
 136     congestion_window_ = congestion_window_ >> 1;
 137   } else {
 138     congestion_window_ =
 139         cubic_.CongestionWindowAfterPacketLoss(congestion_window_);
 140   }
 141   slowstart_threshold_ = congestion_window_;
 142   // Enforce TCP's minimimum congestion window of 2*MSS.
 143   if (congestion_window_ < kMinimumCongestionWindow) {
 144     congestion_window_ = kMinimumCongestionWindow;
 145   }
 146   largest_sent_at_last_cutback_ = largest_sent_sequence_number_;
 147   DVLOG(1) << "Incoming loss; congestion window:" << congestion_window_;
 148 }
 149
 150 bool TcpCubicSender::OnPacketSent(QuicTime /*sent_time*/,
 151                                   QuicPacketSequenceNumber sequence_number,
 152                                   QuicByteCount bytes,
 153                                   TransmissionType transmission_type,
 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   bytes_in_flight_ += bytes;
 161   prr_out_ += bytes;
 162   if (largest_sent_sequence_number_ < sequence_number) {
 163     // TODO(rch): Ensure that packets are really sent in order.
 164     // DCHECK_LT(largest_sent_sequence_number_, sequence_number);
 165     largest_sent_sequence_number_ = sequence_number;
 166   }
 167   if (transmission_type == NOT_RETRANSMISSION && update_end_sequence_number_) {
 168     end_sequence_number_ = sequence_number;
 169     if (AvailableSendWindow() == 0) {
 170       update_end_sequence_number_ = false;
 171       DVLOG(1) << "Stop update end sequence number @" << sequence_number;
 172     }
 173   }
 174   return true;
 175 }
 176
 177 void TcpCubicSender::OnPacketAbandoned(QuicPacketSequenceNumber sequence_number,
 178                                        QuicByteCount abandoned_bytes) {
 179   DCHECK_GE(bytes_in_flight_, abandoned_bytes);
 180   bytes_in_flight_ -= abandoned_bytes;
 181 }
 182
 183 QuicTime::Delta TcpCubicSender::TimeUntilSend(
 184     QuicTime /* now */,
 185     TransmissionType transmission_type,
 186     HasRetransmittableData has_retransmittable_data,
 187     IsHandshake handshake) {
 188   if (transmission_type == TLP_RETRANSMISSION ||
 189       has_retransmittable_data == NO_RETRANSMITTABLE_DATA ||
 190       handshake == IS_HANDSHAKE) {
 191     // For TCP we can always send an ACK immediately.
 192     // We also immediately send any handshake packet (CHLO, etc.).  We provide
 193     // this special dispensation for handshake messages in QUIC, although the
 194     // concept is not present in TCP.
 195     // We also allow tail loss probes to be sent immediately, in keeping with
 196     // tail loss probe (draft-dukkipati-tcpm-tcp-loss-probe-01).
 197     return QuicTime::Delta::Zero();
 198   }
 199   if (AvailableSendWindow() > 0) {
 200     // During PRR-SSRB, limit outgoing packets to 1 extra MSS per ack, instead
 201     // of sending the entire available window. This prevents burst retransmits
 202     // when more packets are lost than the CWND reduction.
 203     //   limit = MAX(prr_delivered - prr_out, DeliveredData) + MSS
 204     if (InRecovery() &&
 205         prr_delivered_ + ack_count_since_loss_ * kMaxSegmentSize < prr_out_) {
 206       return QuicTime::Delta::Infinite();
 207     }
 208     return QuicTime::Delta::Zero();
 209   }
 210   // Implement Proportional Rate Reduction (RFC6937)
 211   // Checks a simplified version of the PRR formula that doesn't use division:
 212   // AvailableSendWindow =
 213   //   CEIL(prr_delivered * ssthresh / BytesInFlightAtLoss) - prr_sent
 214   if (InRecovery() &&
 215       prr_delivered_ * slowstart_threshold_ * kMaxSegmentSize >
 216           prr_out_ * bytes_in_flight_before_loss_) {
 217     return QuicTime::Delta::Zero();
 218   }
 219   return QuicTime::Delta::Infinite();
 220 }
 221
 222 QuicByteCount TcpCubicSender::AvailableSendWindow() {
 223   if (bytes_in_flight_ > SendWindow()) {
 224     return 0;
 225   }
 226   return SendWindow() - bytes_in_flight_;
 227 }
 228
 229 QuicByteCount TcpCubicSender::SendWindow() {
 230   // What's the current send window in bytes.
 231   return min(receive_window_, GetCongestionWindow());
 232 }
 233
 234 QuicBandwidth TcpCubicSender::BandwidthEstimate() const {
 235   return QuicBandwidth::FromBytesAndTimeDelta(GetCongestionWindow(),
 236                                               SmoothedRtt());
 237 }
 238
 239 QuicTime::Delta TcpCubicSender::SmoothedRtt() const {
 240   if (smoothed_rtt_.IsZero()) {
 241     return QuicTime::Delta::FromMilliseconds(kInitialRttMs);
 242   }
 243   return smoothed_rtt_;
 244 }
 245
 246 QuicTime::Delta TcpCubicSender::RetransmissionDelay() const {
 247   return QuicTime::Delta::FromMicroseconds(
 248       smoothed_rtt_.ToMicroseconds() + 4 * mean_deviation_.ToMicroseconds());
 249 }
 250
 251 QuicByteCount TcpCubicSender::GetCongestionWindow() const {
 252   return congestion_window_ * kMaxSegmentSize;
 253 }
 254
 255 void TcpCubicSender::Reset() {
 256   delay_min_ = QuicTime::Delta::Zero();
 257   hybrid_slow_start_.Restart();
 258 }
 259
 260 bool TcpCubicSender::IsCwndLimited() const {
 261   const QuicByteCount congestion_window_bytes = congestion_window_ *
 262       kMaxSegmentSize;
 263   if (bytes_in_flight_ >= congestion_window_bytes) {
 264     return true;
 265   }
 266   const QuicByteCount tcp_max_burst = kMaxBurstLength * kMaxSegmentSize;
 267   const QuicByteCount left = congestion_window_bytes - bytes_in_flight_;
 268   return left <= tcp_max_burst;
 269 }
 270
 271 bool TcpCubicSender::InRecovery() const {
 272   return largest_acked_sequence_number_ <= largest_sent_at_last_cutback_ &&
 273       largest_acked_sequence_number_ != 0;
 274 }
 275
 276 // Called when we receive an ack. Normal TCP tracks how many packets one ack
 277 // represents, but quic has a separate ack for each packet.
 278 void TcpCubicSender::MaybeIncreaseCwnd(
 279     QuicPacketSequenceNumber acked_sequence_number) {
 280   if (!IsCwndLimited()) {
 281     // We don't update the congestion window unless we are close to using the
 282     // window we have available.
 283     return;
 284   }
 285   if (acked_sequence_number <= largest_sent_at_last_cutback_) {
 286     // We don't increase the congestion window during recovery.
 287     return;
 288   }
 289   if (congestion_window_ < slowstart_threshold_) {
 290     // Slow start.
 291     if (hybrid_slow_start_.EndOfRound(acked_sequence_number)) {
 292       hybrid_slow_start_.Reset(end_sequence_number_);
 293     }
 294     // congestion_window_cnt is the number of acks since last change of snd_cwnd
 295     if (congestion_window_ < max_tcp_congestion_window_) {
 296       // TCP slow start, exponential growth, increase by one for each ACK.
 297       ++congestion_window_;
 298     }
 299     DVLOG(1) << "Slow start; congestion window:" << congestion_window_;
 300     return;
 301   }
 302   if (congestion_window_ >= max_tcp_congestion_window_) {
 303     return;
 304   }
 305   // Congestion avoidance
 306   if (reno_) {
 307     // Classic Reno congestion avoidance provided for testing.
 308     if (congestion_window_count_ >= congestion_window_) {
 309       ++congestion_window_;
 310       congestion_window_count_ = 0;
 311     } else {
 312       ++congestion_window_count_;
 313     }
 314     DVLOG(1) << "Reno; congestion window:" << congestion_window_;
 315   } else {
 316     congestion_window_ = min(
 317         max_tcp_congestion_window_,
 318         cubic_.CongestionWindowAfterAck(congestion_window_, delay_min_));
 319     DVLOG(1) << "Cubic; congestion window:" << congestion_window_;
 320   }
 321 }
 322
 323 void TcpCubicSender::OnRetransmissionTimeout(bool packets_retransmitted) {
 324   bytes_in_flight_ = 0;
 325   largest_sent_at_last_cutback_ = 0;
 326   if (packets_retransmitted) {
 327     cubic_.Reset();
 328     congestion_window_ = kMinimumCongestionWindow;
 329   }
 330 }
 331
 332 void TcpCubicSender::UpdateRtt(QuicTime::Delta rtt) {
 333   if (rtt.IsInfinite() || rtt.IsZero()) {
 334     DVLOG(1) << "Ignoring rtt, because it's "
 335                << (rtt.IsZero() ? "Zero" : "Infinite");
 336     return;
 337   }
 338   // RTT can't be negative.
 339   DCHECK_LT(0, rtt.ToMicroseconds());
 340
 341   // TODO(pwestin): Discard delay samples right after fast recovery,
 342   // during 1 second?.
 343
 344   // First time call or link delay decreases.
 345   if (delay_min_.IsZero() || delay_min_ > rtt) {
 346     delay_min_ = rtt;
 347   }
 348   // First time call.
 349   if (smoothed_rtt_.IsZero()) {
 350     smoothed_rtt_ = rtt;
 351     mean_deviation_ = QuicTime::Delta::FromMicroseconds(
 352         rtt.ToMicroseconds() / 2);
 353   } else {
 354     mean_deviation_ = QuicTime::Delta::FromMicroseconds(
 355         kOneMinusBeta * mean_deviation_.ToMicroseconds() +
 356         kBeta * abs(smoothed_rtt_.ToMicroseconds() - rtt.ToMicroseconds()));
 357     smoothed_rtt_ = QuicTime::Delta::FromMicroseconds(
 358         kOneMinusAlpha * smoothed_rtt_.ToMicroseconds() +
 359         kAlpha * rtt.ToMicroseconds());
 360     DVLOG(1) << "Cubic; smoothed_rtt_:" << smoothed_rtt_.ToMicroseconds()
 361                << " mean_deviation_:" << mean_deviation_.ToMicroseconds();
 362   }
 363
 364   // Hybrid start triggers when cwnd is larger than some threshold.
 365   if (congestion_window_ <= slowstart_threshold_ &&
 366       congestion_window_ >= kHybridStartLowWindow) {
 367     if (!hybrid_slow_start_.started()) {
 368       // Time to start the hybrid slow start.
 369       hybrid_slow_start_.Reset(end_sequence_number_);
 370     }
 371     hybrid_slow_start_.Update(rtt, delay_min_);
 372     if (hybrid_slow_start_.Exit()) {
 373       slowstart_threshold_ = congestion_window_;
 374     }
 375   }
 376 }
 377
 378 }  // namespace net