OLD | NEW |
1 // Copyright 2016 The Chromium Authors. All rights reserved. | 1 // Copyright 2016 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "net/quic/core/congestion_control/bbr_sender.h" | 5 #include "net/quic/core/congestion_control/bbr_sender.h" |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
8 #include <sstream> | 8 #include <sstream> |
9 | 9 |
10 #include "net/quic/core/congestion_control/rtt_stats.h" | 10 #include "net/quic/core/congestion_control/rtt_stats.h" |
(...skipping 28 matching lines...) Expand all Loading... |
39 // The time after which the current min_rtt value expires. | 39 // The time after which the current min_rtt value expires. |
40 const QuicTime::Delta kMinRttExpiry = QuicTime::Delta::FromSeconds(10); | 40 const QuicTime::Delta kMinRttExpiry = QuicTime::Delta::FromSeconds(10); |
41 // The minimum time the connection can spend in PROBE_RTT mode. | 41 // The minimum time the connection can spend in PROBE_RTT mode. |
42 const QuicTime::Delta kProbeRttTime = QuicTime::Delta::FromMilliseconds(200); | 42 const QuicTime::Delta kProbeRttTime = QuicTime::Delta::FromMilliseconds(200); |
43 | 43 |
44 // If the bandwidth does not increase by the factor of |kStartupGrowthTarget| | 44 // If the bandwidth does not increase by the factor of |kStartupGrowthTarget| |
45 // within |kRoundTripsWithoutGrowthBeforeExitingStartup| rounds, the connection | 45 // within |kRoundTripsWithoutGrowthBeforeExitingStartup| rounds, the connection |
46 // will exit the STARTUP mode. | 46 // will exit the STARTUP mode. |
47 const float kStartupGrowthTarget = 1.25; | 47 const float kStartupGrowthTarget = 1.25; |
48 const QuicRoundTripCount kRoundTripsWithoutGrowthBeforeExitingStartup = 3; | 48 const QuicRoundTripCount kRoundTripsWithoutGrowthBeforeExitingStartup = 3; |
| 49 |
| 50 // Maintain ack history for this fraction of the smoothed RTT. |
| 51 const float kRecentlyAckedRttFraction = 0.5f; |
| 52 // Minimum period over which ack history will be maintained. |
| 53 const QuicTime::Delta kMinAckHistory = QuicTime::Delta::FromMilliseconds(5); |
| 54 |
49 } // namespace | 55 } // namespace |
50 | 56 |
51 BbrSender::DebugState::DebugState(const BbrSender& sender) | 57 BbrSender::DebugState::DebugState(const BbrSender& sender) |
52 : mode(sender.mode_), | 58 : mode(sender.mode_), |
53 max_bandwidth(sender.max_bandwidth_.GetBest()), | 59 max_bandwidth(sender.max_bandwidth_.GetBest()), |
54 round_trip_count(sender.round_trip_count_), | 60 round_trip_count(sender.round_trip_count_), |
55 gain_cycle_index(sender.cycle_current_offset_), | 61 gain_cycle_index(sender.cycle_current_offset_), |
56 congestion_window(sender.congestion_window_), | 62 congestion_window(sender.congestion_window_), |
57 is_at_full_bandwidth(sender.is_at_full_bandwidth_), | 63 is_at_full_bandwidth(sender.is_at_full_bandwidth_), |
58 bandwidth_at_last_round(sender.bandwidth_at_last_round_), | 64 bandwidth_at_last_round(sender.bandwidth_at_last_round_), |
(...skipping 27 matching lines...) Expand all Loading... |
86 min_rtt_(QuicTime::Delta::Zero()), | 92 min_rtt_(QuicTime::Delta::Zero()), |
87 min_rtt_timestamp_(QuicTime::Zero()), | 93 min_rtt_timestamp_(QuicTime::Zero()), |
88 congestion_window_(initial_tcp_congestion_window * kDefaultTCPMSS), | 94 congestion_window_(initial_tcp_congestion_window * kDefaultTCPMSS), |
89 initial_congestion_window_(initial_tcp_congestion_window * | 95 initial_congestion_window_(initial_tcp_congestion_window * |
90 kDefaultTCPMSS), | 96 kDefaultTCPMSS), |
91 max_congestion_window_(max_tcp_congestion_window * kDefaultTCPMSS), | 97 max_congestion_window_(max_tcp_congestion_window * kDefaultTCPMSS), |
92 pacing_rate_(QuicBandwidth::Zero()), | 98 pacing_rate_(QuicBandwidth::Zero()), |
93 pacing_gain_(1), | 99 pacing_gain_(1), |
94 congestion_window_gain_(1), | 100 congestion_window_gain_(1), |
95 congestion_window_gain_constant_( | 101 congestion_window_gain_constant_( |
96 static_cast<float>(GetQuicFlag(FLAGS_quic_bbr_cwnd_gain))), | 102 static_cast<float>(FLAGS_quic_bbr_cwnd_gain)), |
97 rtt_variance_weight_( | 103 rtt_variance_weight_( |
98 static_cast<float>(GetQuicFlag(FLAGS_quic_bbr_rtt_variation_weight))), | 104 static_cast<float>(FLAGS_quic_bbr_rtt_variation_weight)), |
99 num_startup_rtts_(kRoundTripsWithoutGrowthBeforeExitingStartup), | 105 num_startup_rtts_(kRoundTripsWithoutGrowthBeforeExitingStartup), |
| 106 congestion_window_gain_for_slow_delivery_( |
| 107 static_cast<float>(FLAGS_quic_bbr_slow_delivery_cwnd_gain)), |
| 108 threshold_multiplier_for_slow_delivery_(static_cast<float>( |
| 109 FLAGS_quic_bbr_slow_delivery_threshold_multiplier)), |
100 cycle_current_offset_(0), | 110 cycle_current_offset_(0), |
101 last_cycle_start_(QuicTime::Zero()), | 111 last_cycle_start_(QuicTime::Zero()), |
102 is_at_full_bandwidth_(false), | 112 is_at_full_bandwidth_(false), |
103 rounds_without_bandwidth_gain_(0), | 113 rounds_without_bandwidth_gain_(0), |
104 bandwidth_at_last_round_(QuicBandwidth::Zero()), | 114 bandwidth_at_last_round_(QuicBandwidth::Zero()), |
105 exiting_quiescence_(false), | 115 exiting_quiescence_(false), |
106 exit_probe_rtt_at_(QuicTime::Zero()), | 116 exit_probe_rtt_at_(QuicTime::Zero()), |
107 probe_rtt_round_passed_(false), | 117 probe_rtt_round_passed_(false), |
108 last_sample_is_app_limited_(false), | 118 last_sample_is_app_limited_(false), |
109 recovery_state_(NOT_IN_RECOVERY), | 119 recovery_state_(NOT_IN_RECOVERY), |
110 end_recovery_at_(0), | 120 end_recovery_at_(0), |
111 recovery_window_(max_congestion_window_) { | 121 recovery_window_(max_congestion_window_), |
| 122 bytes_recently_acked_(0) { |
112 EnterStartupMode(); | 123 EnterStartupMode(); |
113 } | 124 } |
114 | 125 |
115 BbrSender::~BbrSender() {} | 126 BbrSender::~BbrSender() {} |
116 | 127 |
117 bool BbrSender::InSlowStart() const { | 128 bool BbrSender::InSlowStart() const { |
118 return mode_ == STARTUP; | 129 return mode_ == STARTUP; |
119 } | 130 } |
120 | 131 |
121 bool BbrSender::OnPacketSent(QuicTime sent_time, | 132 bool BbrSender::OnPacketSent(QuicTime sent_time, |
122 QuicByteCount bytes_in_flight, | 133 QuicByteCount bytes_in_flight, |
123 QuicPacketNumber packet_number, | 134 QuicPacketNumber packet_number, |
124 QuicByteCount bytes, | 135 QuicByteCount bytes, |
125 HasRetransmittableData is_retransmittable) { | 136 HasRetransmittableData is_retransmittable) { |
126 last_sent_packet_ = packet_number; | 137 last_sent_packet_ = packet_number; |
127 | 138 |
128 if (bytes_in_flight == 0 && sampler_.is_app_limited()) { | 139 if (bytes_in_flight == 0 && sampler_.is_app_limited()) { |
129 exiting_quiescence_ = true; | 140 exiting_quiescence_ = true; |
130 } | 141 } |
131 | 142 |
132 sampler_.OnPacketSent(sent_time, packet_number, bytes, bytes_in_flight, | 143 sampler_.OnPacketSent(sent_time, packet_number, bytes, bytes_in_flight, |
133 is_retransmittable); | 144 is_retransmittable); |
134 return is_retransmittable == HAS_RETRANSMITTABLE_DATA; | 145 return is_retransmittable == HAS_RETRANSMITTABLE_DATA; |
135 } | 146 } |
136 | 147 |
137 QuicTime::Delta BbrSender::TimeUntilSend(QuicTime /* now */, | 148 bool BbrSender::SlowDeliveryAllowsSending(QuicTime now, |
138 QuicByteCount bytes_in_flight) const { | 149 QuicByteCount bytes_in_flight) { |
| 150 if (mode_ != BbrSender::PROBE_BW) { |
| 151 return false; |
| 152 } |
| 153 UpdateRecentlyAcked(now, 0u); |
| 154 // Set a (large) limit to how much we send into a blackhole. |
| 155 if (bytes_in_flight >= |
| 156 congestion_window_gain_for_slow_delivery_ * GetCongestionWindow()) { |
| 157 return false; |
| 158 } |
| 159 // If no acks were recorded in the recent past, continue sending. |
| 160 if (recently_acked_.empty()) { |
| 161 return true; |
| 162 } |
| 163 // Compute the time period over which acks should have been recorded. |
| 164 QuicTime::Delta ack_period = |
| 165 std::max(now - recently_acked_.front().ack_time, |
| 166 std::max(kMinAckHistory, kRecentlyAckedRttFraction * |
| 167 rtt_stats_->smoothed_rtt())); |
| 168 // If delivery rate is less than BW by a factor of threshold_multiplier_, |
| 169 // ack rate has suddenly decreased substantially. Continue sending. |
| 170 if (BandwidthEstimate() * ack_period > |
| 171 threshold_multiplier_for_slow_delivery_ * bytes_recently_acked_) { |
| 172 return true; |
| 173 } |
| 174 return false; |
| 175 } |
| 176 |
| 177 QuicTime::Delta BbrSender::TimeUntilSend(QuicTime now, |
| 178 QuicByteCount bytes_in_flight) { |
139 if (bytes_in_flight < GetCongestionWindow()) { | 179 if (bytes_in_flight < GetCongestionWindow()) { |
140 return QuicTime::Delta::Zero(); | 180 return QuicTime::Delta::Zero(); |
141 } | 181 } |
| 182 if (FLAGS_quic_reloadable_flag_quic_bbr_slow_recent_delivery && |
| 183 SlowDeliveryAllowsSending(now, bytes_in_flight)) { |
| 184 QUIC_FLAG_COUNT_N(quic_reloadable_flag_quic_bbr_slow_recent_delivery, 2, 2); |
| 185 return QuicTime::Delta::Zero(); |
| 186 } |
142 return QuicTime::Delta::Infinite(); | 187 return QuicTime::Delta::Infinite(); |
143 } | 188 } |
144 | 189 |
145 QuicBandwidth BbrSender::PacingRate(QuicByteCount bytes_in_flight) const { | 190 QuicBandwidth BbrSender::PacingRate(QuicByteCount bytes_in_flight) const { |
146 if (pacing_rate_.IsZero()) { | 191 if (pacing_rate_.IsZero()) { |
147 return kHighGain * QuicBandwidth::FromBytesAndTimeDelta( | 192 return kHighGain * QuicBandwidth::FromBytesAndTimeDelta( |
148 initial_congestion_window_, GetMinRtt()); | 193 initial_congestion_window_, GetMinRtt()); |
149 } | 194 } |
150 if (FLAGS_quic_reloadable_flag_quic_bbr_keep_sending_at_recent_rate && | 195 if (FLAGS_quic_reloadable_flag_quic_bbr_keep_sending_at_recent_rate && |
151 mode_ == PROBE_BW && bytes_in_flight > congestion_window_) { | 196 mode_ == PROBE_BW && bytes_in_flight > congestion_window_) { |
(...skipping 88 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
240 | 285 |
241 DiscardLostPackets(lost_packets); | 286 DiscardLostPackets(lost_packets); |
242 | 287 |
243 // Input the new data into the BBR model of the connection. | 288 // Input the new data into the BBR model of the connection. |
244 if (!acked_packets.empty()) { | 289 if (!acked_packets.empty()) { |
245 QuicPacketNumber last_acked_packet = acked_packets.rbegin()->first; | 290 QuicPacketNumber last_acked_packet = acked_packets.rbegin()->first; |
246 is_round_start = UpdateRoundTripCounter(last_acked_packet); | 291 is_round_start = UpdateRoundTripCounter(last_acked_packet); |
247 min_rtt_expired = UpdateBandwidthAndMinRtt(event_time, acked_packets); | 292 min_rtt_expired = UpdateBandwidthAndMinRtt(event_time, acked_packets); |
248 UpdateRecoveryState(last_acked_packet, !lost_packets.empty(), | 293 UpdateRecoveryState(last_acked_packet, !lost_packets.empty(), |
249 is_round_start); | 294 is_round_start); |
| 295 |
| 296 if (FLAGS_quic_reloadable_flag_quic_bbr_slow_recent_delivery) { |
| 297 QUIC_FLAG_COUNT_N(quic_reloadable_flag_quic_bbr_slow_recent_delivery, 1, |
| 298 2); |
| 299 UpdateRecentlyAcked( |
| 300 event_time, sampler_.total_bytes_acked() - total_bytes_acked_before); |
| 301 } |
| 302 |
250 if (FLAGS_quic_reloadable_flag_quic_bbr_ack_aggregation_bytes) { | 303 if (FLAGS_quic_reloadable_flag_quic_bbr_ack_aggregation_bytes) { |
251 QUIC_FLAG_COUNT_N(quic_reloadable_flag_quic_bbr_ack_aggregation_bytes, 1, | 304 QUIC_FLAG_COUNT_N(quic_reloadable_flag_quic_bbr_ack_aggregation_bytes, 1, |
252 2); | 305 2); |
253 UpdateAckAggregationBytes( | 306 UpdateAckAggregationBytes( |
254 event_time, sampler_.total_bytes_acked() - total_bytes_acked_before); | 307 event_time, sampler_.total_bytes_acked() - total_bytes_acked_before); |
255 } | 308 } |
256 } | 309 } |
257 | 310 |
258 // Handle logic specific to PROBE_BW mode. | 311 // Handle logic specific to PROBE_BW mode. |
259 if (mode_ == PROBE_BW) { | 312 if (mode_ == PROBE_BW) { |
(...skipping 248 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
508 | 561 |
509 case CONSERVATION: | 562 case CONSERVATION: |
510 if (is_round_start) { | 563 if (is_round_start) { |
511 recovery_state_ = GROWTH; | 564 recovery_state_ = GROWTH; |
512 } | 565 } |
513 | 566 |
514 case GROWTH: | 567 case GROWTH: |
515 // Exit recovery if appropriate. | 568 // Exit recovery if appropriate. |
516 if (!has_losses && last_acked_packet > end_recovery_at_) { | 569 if (!has_losses && last_acked_packet > end_recovery_at_) { |
517 recovery_state_ = NOT_IN_RECOVERY; | 570 recovery_state_ = NOT_IN_RECOVERY; |
| 571 return; |
| 572 } |
| 573 |
| 574 if (!FLAGS_quic_reloadable_flag_quic_bbr_extra_conservation) { |
| 575 return; |
| 576 } |
| 577 |
| 578 // Use "single round in conservation" approach outside of PROBE_BW. |
| 579 if (mode_ != PROBE_BW) { |
| 580 return; |
| 581 } |
| 582 |
| 583 // Switch between conservation and growth depending on position in the |
| 584 // gain cycle. |
| 585 if (cycle_current_offset_ == 0 || |
| 586 cycle_current_offset_ == kGainCycleLength - 1) { |
| 587 recovery_state_ = GROWTH; |
| 588 } else { |
| 589 recovery_state_ = CONSERVATION; |
518 } | 590 } |
519 break; | 591 break; |
520 } | 592 } |
521 } | 593 } |
522 | 594 |
| 595 void BbrSender::UpdateRecentlyAcked(QuicTime new_ack_time, |
| 596 QuicByteCount newly_acked_bytes) { |
| 597 // Discard information stored for acks received too far in the past. |
| 598 QuicTime::Delta recent_period = std::max( |
| 599 kMinAckHistory, kRecentlyAckedRttFraction * rtt_stats_->smoothed_rtt()); |
| 600 while (!recently_acked_.empty() && |
| 601 (recently_acked_.front().ack_time + recent_period < new_ack_time)) { |
| 602 DCHECK_GE(bytes_recently_acked_, recently_acked_.front().acked_bytes); |
| 603 bytes_recently_acked_ -= recently_acked_.front().acked_bytes; |
| 604 recently_acked_.pop_front(); |
| 605 } |
| 606 // Nothing to add to recently_acked_ if no new ack. |
| 607 if (newly_acked_bytes == 0) |
| 608 return; |
| 609 // Add information for new ack |
| 610 DataDelivered new_ack = {new_ack_time, newly_acked_bytes}; |
| 611 recently_acked_.push_back(new_ack); |
| 612 bytes_recently_acked_ += newly_acked_bytes; |
| 613 } |
| 614 |
| 615 // TODO(ianswett): Move this logic into BandwidthSampler. |
523 void BbrSender::UpdateAckAggregationBytes(QuicTime ack_time, | 616 void BbrSender::UpdateAckAggregationBytes(QuicTime ack_time, |
524 QuicByteCount newly_acked_bytes) { | 617 QuicByteCount newly_acked_bytes) { |
525 // Compute how many bytes are expected to be delivered, assuming max bandwidth | 618 // Compute how many bytes are expected to be delivered, assuming max bandwidth |
526 // is correct. | 619 // is correct. |
527 QuicByteCount expected_bytes_acked = | 620 QuicByteCount expected_bytes_acked = |
528 max_bandwidth_.GetBest() * (ack_time - aggregation_epoch_start_time_); | 621 max_bandwidth_.GetBest() * (ack_time - aggregation_epoch_start_time_); |
529 // Reset the current aggregation epoch as soon as the ack arrival rate is less | 622 // Reset the current aggregation epoch as soon as the ack arrival rate is less |
530 // than or equal to the max bandwidth. | 623 // than or equal to the max bandwidth. |
531 if (aggregation_epoch_bytes_ <= expected_bytes_acked) { | 624 if (aggregation_epoch_bytes_ <= expected_bytes_acked) { |
532 // Reset to start measuring a new aggregation epoch. | 625 // Reset to start measuring a new aggregation epoch. |
(...skipping 156 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
689 os << "Minimum RTT timestamp: " << state.min_rtt_timestamp.ToDebuggingValue() | 782 os << "Minimum RTT timestamp: " << state.min_rtt_timestamp.ToDebuggingValue() |
690 << std::endl; | 783 << std::endl; |
691 | 784 |
692 os << "Last sample is app-limited: " | 785 os << "Last sample is app-limited: " |
693 << (state.last_sample_is_app_limited ? "yes" : "no"); | 786 << (state.last_sample_is_app_limited ? "yes" : "no"); |
694 | 787 |
695 return os; | 788 return os; |
696 } | 789 } |
697 | 790 |
698 } // namespace net | 791 } // namespace net |
OLD | NEW |