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