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