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