net/quic/congestion_control/hybrid_slow_start.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/hybrid_slow_start.h"
   6
   7 #include <algorithm>
   8
   9 using std::max;
  10 using std::min;
  11
  12 namespace net {
  13
  14 // Note(pwestin): the magic clamping numbers come from the original code in
  15 // tcp_cubic.c.
  16 const int64 kHybridStartLowWindow = 16;
  17 // Number of delay samples for detecting the increase of delay.
  18 const uint32 kHybridStartMinSamples = 8;
  19 // Exit slow start if the min rtt has increased by more than 1/8th.
  20 const int kHybridStartDelayFactorExp = 3;  // 2^3 = 8
  21 // The original paper specifies 2 and 8ms, but those have changed over time.
  22 const int64 kHybridStartDelayMinThresholdUs = 4000;
  23 const int64 kHybridStartDelayMaxThresholdUs = 16000;
  24
  25 HybridSlowStart::HybridSlowStart(const QuicClock* clock)
  26     : clock_(clock),
  27       ack_train_detection_(true),
  28       started_(false),
  29       hystart_found_(NOT_FOUND),
  30       last_sent_sequence_number_(0),
  31       round_start_(QuicTime::Zero()),
  32       end_sequence_number_(0),
  33       last_close_ack_pair_time_(QuicTime::Zero()),
  34       rtt_sample_count_(0),
  35       current_min_rtt_(QuicTime::Delta::Zero()) {
  36 }
  37
  38 void HybridSlowStart::OnPacketAcked(
  39     QuicPacketSequenceNumber acked_sequence_number, bool in_slow_start) {
  40   // OnPacketAcked gets invoked after ShouldExitSlowStart, so it's best to end
  41   // the round when the final packet of the burst is received and start it on
  42   // the next incoming ack.
  43   if (in_slow_start && IsEndOfRound(acked_sequence_number)) {
  44     started_ = false;
  45   }
  46 }
  47
  48 void HybridSlowStart::OnPacketSent(QuicPacketSequenceNumber sequence_number) {
  49   last_sent_sequence_number_ = sequence_number;
  50 }
  51
  52 void HybridSlowStart::Restart() {
  53   started_ = false;
  54   hystart_found_ = NOT_FOUND;
  55 }
  56
  57 void HybridSlowStart::StartReceiveRound(QuicPacketSequenceNumber last_sent) {
  58   DVLOG(1) << "Reset hybrid slow start @" << last_sent;
  59   round_start_ = last_close_ack_pair_time_ = clock_->ApproximateNow();
  60   end_sequence_number_ = last_sent;
  61   current_min_rtt_ = QuicTime::Delta::Zero();
  62   rtt_sample_count_ = 0;
  63   started_ = true;
  64 }
  65
  66 bool HybridSlowStart::IsEndOfRound(QuicPacketSequenceNumber ack) const {
  67   return end_sequence_number_ <= ack;
  68 }
  69
  70 bool HybridSlowStart::ShouldExitSlowStart(QuicTime::Delta latest_rtt,
  71                                           QuicTime::Delta min_rtt,
  72                                           int64 congestion_window) {
  73   if (!started_) {
  74     // Time to start the hybrid slow start.
  75     StartReceiveRound(last_sent_sequence_number_);
  76   }
  77   if (hystart_found_ != NOT_FOUND) {
  78     return true;
  79   }
  80   QuicTime current_time = clock_->ApproximateNow();
  81
  82   // First detection parameter - ack-train detection.
  83   // Since slow start burst out packets we can indirectly estimate the inter-
  84   // arrival time by looking at the arrival time of the ACKs if the ACKs are
  85   // spread out more then half the minimum RTT packets are being spread out
  86   // more than the capacity.
  87   // This first trigger will not come into play until we hit roughly 9.6 Mbps
  88   // with delayed acks (or 4.8Mbps without delayed acks)
  89   if (ack_train_detection_ &&
  90       current_time.Subtract(last_close_ack_pair_time_).ToMicroseconds() <=
  91           kHybridStartDelayMinThresholdUs) {
  92     last_close_ack_pair_time_ = current_time;
  93     if (current_time.Subtract(round_start_).ToMicroseconds() >=
  94             min_rtt.ToMicroseconds() >> 1) {
  95       hystart_found_ = ACK_TRAIN;
  96     }
  97   } else if (last_close_ack_pair_time_ == round_start_) {
  98     // If the previous ack wasn't close, then move forward the round start time
  99     // to the incoming ack.
 100     last_close_ack_pair_time_ = round_start_ = current_time;
 101   }
 102   // Second detection parameter - delay increase detection.
 103   // Compare the minimum delay (current_min_rtt_) of the current
 104   // burst of packets relative to the minimum delay during the session.
 105   // Note: we only look at the first few(8) packets in each burst, since we
 106   // only want to compare the lowest RTT of the burst relative to previous
 107   // bursts.
 108   rtt_sample_count_++;
 109   if (rtt_sample_count_ <= kHybridStartMinSamples) {
 110     if (current_min_rtt_.IsZero() || current_min_rtt_ > latest_rtt) {
 111       current_min_rtt_ = latest_rtt;
 112     }
 113   }
 114   // We only need to check this once per round.
 115   if (rtt_sample_count_ == kHybridStartMinSamples) {
 116     // Divide min_rtt by 16 to get a rtt increase threshold for exiting.
 117     int64 min_rtt_increase_threshold_us = min_rtt.ToMicroseconds() >>
 118         kHybridStartDelayFactorExp;
 119     // Ensure the rtt threshold is never less than 2ms or more than 16ms.
 120     min_rtt_increase_threshold_us = min(min_rtt_increase_threshold_us,
 121                                         kHybridStartDelayMaxThresholdUs);
 122     QuicTime::Delta min_rtt_increase_threshold =
 123         QuicTime::Delta::FromMicroseconds(max(min_rtt_increase_threshold_us,
 124                                               kHybridStartDelayMinThresholdUs));
 125
 126     if (current_min_rtt_ > min_rtt.Add(min_rtt_increase_threshold)) {
 127       hystart_found_= DELAY;
 128     }
 129   }
 130   // Exit from slow start if the cwnd is greater than 16 and an ack train or
 131   // increasing delay are found.
 132   return congestion_window >= kHybridStartLowWindow &&
 133       hystart_found_ != NOT_FOUND;
 134 }
 135
 136 }  // namespace net