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
9namespace net {
10
11// Note(pwestin): the magic clamping numbers come from the original code in
12// tcp_cubic.c.
13// Number of delay samples for detecting the increase of delay.
14const int kHybridStartMinSamples = 8;
15const int kHybridStartDelayFactorExp = 4;  // 2^4 = 16
16const int kHybridStartDelayMinThresholdUs = 2000;
17const int kHybridStartDelayMaxThresholdUs = 16000;
18
19HybridSlowStart::HybridSlowStart(const QuicClock* clock)
20    : clock_(clock),
21      started_(false),
22      found_ack_train_(false),
23      found_delay_(false),
24      round_start_(QuicTime::Zero()),
25      end_sequence_number_(0),
26      last_time_(QuicTime::Zero()),
27      sample_count_(0),
28      current_rtt_(QuicTime::Delta::Zero()) {
29}
30
31void HybridSlowStart::Restart() {
32  found_ack_train_ = false;
33  found_delay_  = false;
34}
35
36void HybridSlowStart::Reset(QuicPacketSequenceNumber end_sequence_number) {
37  DVLOG(1) << "Reset hybrid slow start @" << end_sequence_number;
38  round_start_ = last_time_ = clock_->ApproximateNow();
39  end_sequence_number_ = end_sequence_number;
40  current_rtt_ = QuicTime::Delta::Zero();
41  sample_count_ = 0;
42  started_ = true;
43}
44
45bool HybridSlowStart::EndOfRound(QuicPacketSequenceNumber ack) {
46  return end_sequence_number_ <= ack;
47}
48
49void HybridSlowStart::Update(QuicTime::Delta rtt, QuicTime::Delta delay_min) {
50  // The original code doesn't invoke this until we hit 16 packet per burst.
51  // Since the code handles lower than 16 grecefully and I removed that
52  // limit.
53  if (found_ack_train_ || found_delay_) {
54    return;
55  }
56  QuicTime current_time = clock_->ApproximateNow();
57
58  // First detection parameter - ack-train detection.
59  // Since slow start burst out packets we can indirectly estimate the inter-
60  // arrival time by looking at the arrival time of the ACKs if the ACKs are
61  // spread out more then half the minimum RTT packets are beeing spread out
62  // more than the capacity.
63  // This first trigger will not come into play until we hit roughly 4.8 Mbit/s.
64  // TODO(pwestin): we need to make sure our pacing don't trigger this detector.
65  if (current_time.Subtract(last_time_).ToMicroseconds() <=
66      kHybridStartDelayMinThresholdUs) {
67    last_time_ = current_time;
68    if (current_time.Subtract(round_start_).ToMicroseconds() >=
69        (delay_min.ToMicroseconds() >> 1)) {
70      found_ack_train_ = true;
71    }
72  }
73  // Second detection parameter - delay increase detection.
74  // Compare the minimum delay (current_rtt_) of the current
75  // burst of packets relative to the minimum delay during the session.
76  // Note: we only look at the first few(8) packets in each burst, since we
77  // only want to compare the lowest RTT of the burst relative to previous
78  // bursts.
79  sample_count_++;
80  if (sample_count_ <= kHybridStartMinSamples) {
81    if (current_rtt_.IsZero() || current_rtt_ > rtt) {
82      current_rtt_ = rtt;
83    }
84  }
85  // We only need to check this once.
86  if (sample_count_ == kHybridStartMinSamples) {
87    int accepted_variance_us = delay_min.ToMicroseconds() >>
88        kHybridStartDelayFactorExp;
89    accepted_variance_us = std::min(accepted_variance_us,
90                                    kHybridStartDelayMaxThresholdUs);
91    QuicTime::Delta accepted_variance = QuicTime::Delta::FromMicroseconds(
92        std::max(accepted_variance_us, kHybridStartDelayMinThresholdUs));
93
94    if (current_rtt_ > delay_min.Add(accepted_variance)) {
95      found_delay_ = true;
96    }
97  }
98}
99
100bool HybridSlowStart::Exit() {
101  // If either one of the two conditions are met we exit from slow start
102  // immediately.
103  if (found_ack_train_ || found_delay_) {
104    return true;
105  }
106  return false;
107}
108
109}  // namespace net
110