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