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       started_(false),
  28       hystart_found_(NOT_FOUND),
  29       last_sent_sequence_number_(0),
  30       end_sequence_number_(0),
  31       rtt_sample_count_(0),
  32       current_min_rtt_(QuicTime::Delta::Zero()) {
  33 }
  34
  35 void HybridSlowStart::OnPacketAcked(
  36     QuicPacketSequenceNumber acked_sequence_number, bool in_slow_start) {
  37   // OnPacketAcked gets invoked after ShouldExitSlowStart, so it's best to end
  38   // the round when the final packet of the burst is received and start it on
  39   // the next incoming ack.
  40   if (in_slow_start && IsEndOfRound(acked_sequence_number)) {
  41     started_ = false;
  42   }
  43 }
  44
  45 void HybridSlowStart::OnPacketSent(QuicPacketSequenceNumber sequence_number) {
  46   last_sent_sequence_number_ = sequence_number;
  47 }
  48
  49 void HybridSlowStart::Restart() {
  50   started_ = false;
  51   hystart_found_ = NOT_FOUND;
  52 }
  53
  54 void HybridSlowStart::StartReceiveRound(QuicPacketSequenceNumber last_sent) {
  55   DVLOG(1) << "Reset hybrid slow start @" << last_sent;
  56   end_sequence_number_ = last_sent;
  57   current_min_rtt_ = QuicTime::Delta::Zero();
  58   rtt_sample_count_ = 0;
  59   started_ = true;
  60 }
  61
  62 bool HybridSlowStart::IsEndOfRound(QuicPacketSequenceNumber ack) const {
  63   return end_sequence_number_ <= ack;
  64 }
  65
  66 bool HybridSlowStart::ShouldExitSlowStart(QuicTime::Delta latest_rtt,
  67                                           QuicTime::Delta min_rtt,
  68                                           int64 congestion_window) {
  69   if (!started_) {
  70     // Time to start the hybrid slow start.
  71     StartReceiveRound(last_sent_sequence_number_);
  72   }
  73   if (hystart_found_ != NOT_FOUND) {
  74     return true;
  75   }
  76   // Second detection parameter - delay increase detection.
  77   // Compare the minimum delay (current_min_rtt_) of the current
  78   // burst of packets relative to the minimum delay during the session.
  79   // Note: we only look at the first few(8) packets in each burst, since we
  80   // only want to compare the lowest RTT of the burst relative to previous
  81   // bursts.
  82   rtt_sample_count_++;
  83   if (rtt_sample_count_ <= kHybridStartMinSamples) {
  84     if (current_min_rtt_.IsZero() || current_min_rtt_ > latest_rtt) {
  85       current_min_rtt_ = latest_rtt;
  86     }
  87   }
  88   // We only need to check this once per round.
  89   if (rtt_sample_count_ == kHybridStartMinSamples) {
  90     // Divide min_rtt by 16 to get a rtt increase threshold for exiting.
  91     int64 min_rtt_increase_threshold_us = min_rtt.ToMicroseconds() >>
  92         kHybridStartDelayFactorExp;
  93     // Ensure the rtt threshold is never less than 2ms or more than 16ms.
  94     min_rtt_increase_threshold_us = min(min_rtt_increase_threshold_us,
  95                                         kHybridStartDelayMaxThresholdUs);
  96     QuicTime::Delta min_rtt_increase_threshold =
  97         QuicTime::Delta::FromMicroseconds(max(min_rtt_increase_threshold_us,
  98                                               kHybridStartDelayMinThresholdUs));
  99
 100     if (current_min_rtt_ > min_rtt.Add(min_rtt_increase_threshold)) {
 101       hystart_found_= DELAY;
 102     }
 103   }
 104   // Exit from slow start if the cwnd is greater than 16 and
 105   // increasing delay is found.
 106   return congestion_window >= kHybridStartLowWindow &&
 107       hystart_found_ != NOT_FOUND;
 108 }
 109
 110 }  // namespace net