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