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 "quiche/quic/core/congestion_control/hybrid_slow_start.h"
6
7 #include <algorithm>
8
9 #include "quiche/quic/platform/api/quic_logging.h"
10
11 namespace quic {
12
13 // Note(pwestin): the magic clamping numbers come from the original code in
14 // tcp_cubic.c.
15 const int64_t kHybridStartLowWindow = 16;
16 // Number of delay samples for detecting the increase of delay.
17 const uint32_t kHybridStartMinSamples = 8;
18 // Exit slow start if the min rtt has increased by more than 1/8th.
19 const int kHybridStartDelayFactorExp = 3; // 2^3 = 8
20 // The original paper specifies 2 and 8ms, but those have changed over time.
21 const int64_t kHybridStartDelayMinThresholdUs = 4000;
22 const int64_t kHybridStartDelayMaxThresholdUs = 16000;
23
HybridSlowStart()24 HybridSlowStart::HybridSlowStart()
25 : started_(false),
26 hystart_found_(NOT_FOUND),
27 rtt_sample_count_(0),
28 current_min_rtt_(QuicTime::Delta::Zero()) {}
29
OnPacketAcked(QuicPacketNumber acked_packet_number)30 void HybridSlowStart::OnPacketAcked(QuicPacketNumber acked_packet_number) {
31 // OnPacketAcked gets invoked after ShouldExitSlowStart, so it's best to end
32 // the round when the final packet of the burst is received and start it on
33 // the next incoming ack.
34 if (IsEndOfRound(acked_packet_number)) {
35 started_ = false;
36 }
37 }
38
OnPacketSent(QuicPacketNumber packet_number)39 void HybridSlowStart::OnPacketSent(QuicPacketNumber packet_number) {
40 last_sent_packet_number_ = packet_number;
41 }
42
Restart()43 void HybridSlowStart::Restart() {
44 started_ = false;
45 hystart_found_ = NOT_FOUND;
46 }
47
StartReceiveRound(QuicPacketNumber last_sent)48 void HybridSlowStart::StartReceiveRound(QuicPacketNumber last_sent) {
49 QUIC_DVLOG(1) << "Reset hybrid slow start @" << last_sent;
50 end_packet_number_ = last_sent;
51 current_min_rtt_ = QuicTime::Delta::Zero();
52 rtt_sample_count_ = 0;
53 started_ = true;
54 }
55
IsEndOfRound(QuicPacketNumber ack) const56 bool HybridSlowStart::IsEndOfRound(QuicPacketNumber ack) const {
57 return !end_packet_number_.IsInitialized() || end_packet_number_ <= ack;
58 }
59
ShouldExitSlowStart(QuicTime::Delta latest_rtt,QuicTime::Delta min_rtt,QuicPacketCount congestion_window)60 bool HybridSlowStart::ShouldExitSlowStart(QuicTime::Delta latest_rtt,
61 QuicTime::Delta min_rtt,
62 QuicPacketCount congestion_window) {
63 if (!started_) {
64 // Time to start the hybrid slow start.
65 StartReceiveRound(last_sent_packet_number_);
66 }
67 if (hystart_found_ != NOT_FOUND) {
68 return true;
69 }
70 // Second detection parameter - delay increase detection.
71 // Compare the minimum delay (current_min_rtt_) of the current
72 // burst of packets relative to the minimum delay during the session.
73 // Note: we only look at the first few(8) packets in each burst, since we
74 // only want to compare the lowest RTT of the burst relative to previous
75 // bursts.
76 rtt_sample_count_++;
77 if (rtt_sample_count_ <= kHybridStartMinSamples) {
78 if (current_min_rtt_.IsZero() || current_min_rtt_ > latest_rtt) {
79 current_min_rtt_ = latest_rtt;
80 }
81 }
82 // We only need to check this once per round.
83 if (rtt_sample_count_ == kHybridStartMinSamples) {
84 // Divide min_rtt by 8 to get a rtt increase threshold for exiting.
85 int64_t min_rtt_increase_threshold_us =
86 min_rtt.ToMicroseconds() >> kHybridStartDelayFactorExp;
87 // Ensure the rtt threshold is never less than 2ms or more than 16ms.
88 min_rtt_increase_threshold_us = std::min(min_rtt_increase_threshold_us,
89 kHybridStartDelayMaxThresholdUs);
90 QuicTime::Delta min_rtt_increase_threshold =
91 QuicTime::Delta::FromMicroseconds(std::max(
92 min_rtt_increase_threshold_us, kHybridStartDelayMinThresholdUs));
93
94 if (current_min_rtt_ > min_rtt + min_rtt_increase_threshold) {
95 hystart_found_ = DELAY;
96 }
97 }
98 // Exit from slow start if the cwnd is greater than 16 and
99 // increasing delay is found.
100 return congestion_window >= kHybridStartLowWindow &&
101 hystart_found_ != NOT_FOUND;
102 }
103
104 } // namespace quic
105