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 namespace net {
  12
  13 namespace {
  14 // Constants based on TCP defaults.
  15 //TODO(rch): set to 2.
  16 const QuicTcpCongestionWindow kMinimumCongestionWindow = 1;
  17 const int64 kHybridStartLowWindow = 16;
  18 const QuicByteCount kMaxSegmentSize = kDefaultTCPMSS;
  19 const QuicByteCount kDefaultReceiveWindow = 64000;
  20 const int64 kInitialCongestionWindow = 10;
  21 const int kMaxBurstLength = 3;
  22 const int kInitialRttMs = 60;  // At a typical RTT 60 ms.
  23 const float kAlpha = 0.125f;
  24 const float kOneMinusAlpha = (1 - kAlpha);
  25 const float kBeta = 0.25f;
  26 const float kOneMinusBeta = (1 - kBeta);
  27 };  // namespace
  28
  29 TcpCubicSender::TcpCubicSender(
  30     const QuicClock* clock,
  31     bool reno,
  32     QuicTcpCongestionWindow max_tcp_congestion_window)
  33     : hybrid_slow_start_(clock),
  34       cubic_(clock),
  35       reno_(reno),
  36       congestion_window_count_(0),
  37       receive_window_(kDefaultReceiveWindow),
  38       last_received_accumulated_number_of_lost_packets_(0),
  39       bytes_in_flight_(0),
  40       update_end_sequence_number_(true),
  41       end_sequence_number_(0),
  42       congestion_window_(kInitialCongestionWindow),
  43       slowstart_threshold_(max_tcp_congestion_window),
  44       max_tcp_congestion_window_(max_tcp_congestion_window),
  45       delay_min_(QuicTime::Delta::Zero()),
  46       smoothed_rtt_(QuicTime::Delta::Zero()),
  47       mean_deviation_(QuicTime::Delta::Zero()) {
  48 }
  49
  50 TcpCubicSender::~TcpCubicSender() {
  51   UMA_HISTOGRAM_COUNTS("Net.QuicSession.FinalTcpCwnd", congestion_window_);
  52 }
  53
  54 void TcpCubicSender::SetFromConfig(const QuicConfig& config, bool is_server) {
  55   if (is_server) {
  56     // Set the initial window size.
  57     // Ignoring the max packet size and always using TCP's default MSS.
  58     congestion_window_ = config.server_initial_congestion_window();
  59   }
  60 }
  61
  62 void TcpCubicSender::OnIncomingQuicCongestionFeedbackFrame(
  63     const QuicCongestionFeedbackFrame& feedback,
  64     QuicTime feedback_receive_time,
  65     const SentPacketsMap& /*sent_packets*/) {
  66   if (last_received_accumulated_number_of_lost_packets_ !=
  67       feedback.tcp.accumulated_number_of_lost_packets) {
  68     int recovered_lost_packets =
  69         last_received_accumulated_number_of_lost_packets_ -
  70         feedback.tcp.accumulated_number_of_lost_packets;
  71     last_received_accumulated_number_of_lost_packets_ =
  72         feedback.tcp.accumulated_number_of_lost_packets;
  73     if (recovered_lost_packets > 0) {
  74       OnIncomingLoss(feedback_receive_time);
  75     }
  76   }
  77   receive_window_ = feedback.tcp.receive_window;
  78 }
  79
  80 void TcpCubicSender::OnIncomingAck(
  81     QuicPacketSequenceNumber acked_sequence_number, QuicByteCount acked_bytes,
  82     QuicTime::Delta rtt) {
  83   DCHECK_GE(bytes_in_flight_, acked_bytes);
  84   bytes_in_flight_ -= acked_bytes;
  85   CongestionAvoidance(acked_sequence_number);
  86   AckAccounting(rtt);
  87   if (end_sequence_number_ == acked_sequence_number) {
  88     DLOG(INFO) << "Start update end sequence number @" << acked_sequence_number;
  89     update_end_sequence_number_ = true;
  90   }
  91 }
  92
  93 void TcpCubicSender::OnIncomingLoss(QuicTime /*ack_receive_time*/) {
  94   // In a normal TCP we would need to know the lowest missing packet to detect
  95   // if we receive 3 missing packets. Here we get a missing packet for which we
  96   // enter TCP Fast Retransmit immediately.
  97   if (reno_) {
  98     congestion_window_ = congestion_window_ >> 1;
  99     slowstart_threshold_ = congestion_window_;
 100   } else {
 101     congestion_window_ =
 102         cubic_.CongestionWindowAfterPacketLoss(congestion_window_);
 103     slowstart_threshold_ = congestion_window_;
 104   }
 105   // Sanity, make sure that we don't end up with an empty window.
 106   if (congestion_window_ == 0) {
 107     congestion_window_ = kMinimumCongestionWindow;
 108   }
 109   DLOG(INFO) << "Incoming loss; congestion window:" << congestion_window_;
 110 }
 111
 112 bool TcpCubicSender::OnPacketSent(QuicTime /*sent_time*/,
 113                                   QuicPacketSequenceNumber sequence_number,
 114                                   QuicByteCount bytes,
 115                                   TransmissionType transmission_type,
 116                                   HasRetransmittableData is_retransmittable) {
 117   // Only update bytes_in_flight_ for data packets.
 118   if (is_retransmittable != HAS_RETRANSMITTABLE_DATA) {
 119     return false;
 120   }
 121
 122   bytes_in_flight_ += bytes;
 123   if (transmission_type == NOT_RETRANSMISSION && update_end_sequence_number_) {
 124     end_sequence_number_ = sequence_number;
 125     if (AvailableSendWindow() == 0) {
 126       update_end_sequence_number_ = false;
 127       DLOG(INFO) << "Stop update end sequence number @" << sequence_number;
 128     }
 129   }
 130   return true;
 131 }
 132
 133 void TcpCubicSender::OnPacketAbandoned(QuicPacketSequenceNumber sequence_number,
 134                                       QuicByteCount abandoned_bytes) {
 135   DCHECK_GE(bytes_in_flight_, abandoned_bytes);
 136   bytes_in_flight_ -= abandoned_bytes;
 137 }
 138
 139 QuicTime::Delta TcpCubicSender::TimeUntilSend(
 140     QuicTime /* now */,
 141     TransmissionType transmission_type,
 142     HasRetransmittableData has_retransmittable_data,
 143     IsHandshake handshake) {
 144   if (transmission_type == NACK_RETRANSMISSION ||
 145       has_retransmittable_data == NO_RETRANSMITTABLE_DATA ||
 146       handshake == IS_HANDSHAKE) {
 147     // For TCP we can always send an ACK immediately.
 148     // We also immediately send any handshake packet (CHLO, etc.).  We provide
 149     // this special dispensation for handshake messages in QUIC, although the
 150     // concept is not present in TCP.
 151     return QuicTime::Delta::Zero();
 152   }
 153   if (AvailableSendWindow() == 0) {
 154     return QuicTime::Delta::Infinite();
 155   }
 156   return QuicTime::Delta::Zero();
 157 }
 158
 159 QuicByteCount TcpCubicSender::AvailableSendWindow() {
 160   if (bytes_in_flight_ > SendWindow()) {
 161     return 0;
 162   }
 163   return SendWindow() - bytes_in_flight_;
 164 }
 165
 166 QuicByteCount TcpCubicSender::SendWindow() {
 167   // What's the current send window in bytes.
 168   return std::min(receive_window_, GetCongestionWindow());
 169 }
 170
 171 QuicBandwidth TcpCubicSender::BandwidthEstimate() {
 172   // TODO(pwestin): make a long term estimate, based on RTT and loss rate? or
 173   // instantaneous estimate?
 174   // Throughput ~= (1/RTT)*sqrt(3/2p)
 175   return QuicBandwidth::Zero();
 176 }
 177
 178 QuicTime::Delta TcpCubicSender::SmoothedRtt() {
 179   if (smoothed_rtt_.IsZero()) {
 180     return QuicTime::Delta::FromMilliseconds(kInitialRttMs);
 181   }
 182   return smoothed_rtt_;
 183 }
 184
 185 QuicTime::Delta TcpCubicSender::RetransmissionDelay() {
 186   return QuicTime::Delta::FromMicroseconds(
 187       smoothed_rtt_.ToMicroseconds() + 4 * mean_deviation_.ToMicroseconds());
 188 }
 189
 190 QuicByteCount TcpCubicSender::GetCongestionWindow() {
 191   return congestion_window_ * kMaxSegmentSize;
 192 }
 193
 194 void TcpCubicSender::SetCongestionWindow(QuicByteCount window) {
 195   congestion_window_ = window / kMaxSegmentSize;
 196   if (congestion_window_ < kMinimumCongestionWindow) {
 197     congestion_window_ = kMinimumCongestionWindow;
 198   }
 199 }
 200
 201 void TcpCubicSender::Reset() {
 202   delay_min_ = QuicTime::Delta::Zero();
 203   hybrid_slow_start_.Restart();
 204 }
 205
 206 bool TcpCubicSender::IsCwndLimited() const {
 207   const QuicByteCount congestion_window_bytes = congestion_window_ *
 208       kMaxSegmentSize;
 209   if (bytes_in_flight_ >= congestion_window_bytes) {
 210     return true;
 211   }
 212   const QuicByteCount tcp_max_burst = kMaxBurstLength * kMaxSegmentSize;
 213   const QuicByteCount left = congestion_window_bytes - bytes_in_flight_;
 214   return left <= tcp_max_burst;
 215 }
 216
 217 // Called when we receive an ack. Normal TCP tracks how many packets one ack
 218 // represents, but quic has a separate ack for each packet.
 219 void TcpCubicSender::CongestionAvoidance(QuicPacketSequenceNumber ack) {
 220   if (!IsCwndLimited()) {
 221     // We don't update the congestion window unless we are close to using the
 222     // window we have available.
 223     return;
 224   }
 225   if (congestion_window_ < slowstart_threshold_) {
 226     // Slow start.
 227     if (hybrid_slow_start_.EndOfRound(ack)) {
 228       hybrid_slow_start_.Reset(end_sequence_number_);
 229     }
 230     // congestion_window_cnt is the number of acks since last change of snd_cwnd
 231     if (congestion_window_ < max_tcp_congestion_window_) {
 232       // TCP slow start, exponential growth, increase by one for each ACK.
 233       congestion_window_++;
 234     }
 235     DLOG(INFO) << "Slow start; congestion window:" << congestion_window_;
 236   } else {
 237     if (congestion_window_ < max_tcp_congestion_window_) {
 238       if (reno_) {
 239         // Classic Reno congestion avoidance provided for testing.
 240         if (congestion_window_count_ >= congestion_window_) {
 241           congestion_window_++;
 242           congestion_window_count_ = 0;
 243         } else {
 244           congestion_window_count_++;
 245         }
 246         DLOG(INFO) << "Reno; congestion window:" << congestion_window_;
 247       } else {
 248         congestion_window_ = std::min(
 249             max_tcp_congestion_window_,
 250             cubic_.CongestionWindowAfterAck(congestion_window_, delay_min_));
 251         DLOG(INFO) << "Cubic; congestion window:" << congestion_window_;
 252       }
 253     }
 254   }
 255 }
 256
 257 // TODO(pwestin): what is the timout value?
 258 void TcpCubicSender::OnTimeOut() {
 259   cubic_.Reset();
 260   congestion_window_ = 1;
 261 }
 262
 263 void TcpCubicSender::AckAccounting(QuicTime::Delta rtt) {
 264   if (rtt.IsInfinite() || rtt.IsZero()) {
 265     DLOG(INFO) << "Ignoring rtt, because it's "
 266                << (rtt.IsZero() ? "Zero" : "Infinite");
 267     return;
 268   }
 269   // RTT can't be negative.
 270   DCHECK_LT(0, rtt.ToMicroseconds());
 271
 272   // TODO(pwestin): Discard delay samples right after fast recovery,
 273   // during 1 second?.
 274
 275   // First time call or link delay decreases.
 276   if (delay_min_.IsZero() || delay_min_ > rtt) {
 277     delay_min_ = rtt;
 278   }
 279   // First time call.
 280   if (smoothed_rtt_.IsZero()) {
 281     smoothed_rtt_ = rtt;
 282     mean_deviation_ = QuicTime::Delta::FromMicroseconds(
 283         rtt.ToMicroseconds() / 2);
 284   } else {
 285     mean_deviation_ = QuicTime::Delta::FromMicroseconds(
 286         kOneMinusBeta * mean_deviation_.ToMicroseconds() +
 287         kBeta * abs(smoothed_rtt_.ToMicroseconds() - rtt.ToMicroseconds()));
 288     smoothed_rtt_ = QuicTime::Delta::FromMicroseconds(
 289         kOneMinusAlpha * smoothed_rtt_.ToMicroseconds() +
 290         kAlpha * rtt.ToMicroseconds());
 291     DLOG(INFO) << "Cubic; smoothed_rtt_:" << smoothed_rtt_.ToMicroseconds()
 292                << " mean_deviation_:" << mean_deviation_.ToMicroseconds();
 293   }
 294
 295   // Hybrid start triggers when cwnd is larger than some threshold.
 296   if (congestion_window_ <= slowstart_threshold_ &&
 297       congestion_window_ >= kHybridStartLowWindow) {
 298     if (!hybrid_slow_start_.started()) {
 299       // Time to start the hybrid slow start.
 300       hybrid_slow_start_.Reset(end_sequence_number_);
 301     }
 302     hybrid_slow_start_.Update(rtt, delay_min_);
 303     if (hybrid_slow_start_.Exit()) {
 304       slowstart_threshold_ = congestion_window_;
 305     }
 306   }
 307 }
 308
 309 }  // namespace net