1 // Copyright 2019 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/third_party/quiche/src/quic/core/congestion_control/bbr2_misc.h"
6
7 #include "net/third_party/quiche/src/quic/core/congestion_control/bandwidth_sampler.h"
8 #include "net/third_party/quiche/src/quic/core/quic_bandwidth.h"
9 #include "net/third_party/quiche/src/quic/core/quic_time.h"
10 #include "net/third_party/quiche/src/quic/core/quic_types.h"
11 #include "net/third_party/quiche/src/quic/platform/api/quic_logging.h"
12
13 namespace quic {
14
RoundTripCounter()15 RoundTripCounter::RoundTripCounter() : round_trip_count_(0) {}
16
OnPacketSent(QuicPacketNumber packet_number)17 void RoundTripCounter::OnPacketSent(QuicPacketNumber packet_number) {
18 DCHECK(!last_sent_packet_.IsInitialized() ||
19 last_sent_packet_ < packet_number);
20 last_sent_packet_ = packet_number;
21 }
22
OnPacketsAcked(QuicPacketNumber last_acked_packet)23 bool RoundTripCounter::OnPacketsAcked(QuicPacketNumber last_acked_packet) {
24 if (!end_of_round_trip_.IsInitialized() ||
25 last_acked_packet > end_of_round_trip_) {
26 round_trip_count_++;
27 end_of_round_trip_ = last_sent_packet_;
28 return true;
29 }
30 return false;
31 }
32
RestartRound()33 void RoundTripCounter::RestartRound() {
34 end_of_round_trip_ = last_sent_packet_;
35 }
36
MinRttFilter(QuicTime::Delta initial_min_rtt,QuicTime initial_min_rtt_timestamp)37 MinRttFilter::MinRttFilter(QuicTime::Delta initial_min_rtt,
38 QuicTime initial_min_rtt_timestamp)
39 : min_rtt_(initial_min_rtt),
40 min_rtt_timestamp_(initial_min_rtt_timestamp) {}
41
Update(QuicTime::Delta sample_rtt,QuicTime now)42 void MinRttFilter::Update(QuicTime::Delta sample_rtt, QuicTime now) {
43 if (sample_rtt < min_rtt_ || min_rtt_timestamp_ == QuicTime::Zero()) {
44 min_rtt_ = sample_rtt;
45 min_rtt_timestamp_ = now;
46 }
47 }
48
ForceUpdate(QuicTime::Delta sample_rtt,QuicTime now)49 void MinRttFilter::ForceUpdate(QuicTime::Delta sample_rtt, QuicTime now) {
50 min_rtt_ = sample_rtt;
51 min_rtt_timestamp_ = now;
52 }
53
Bbr2NetworkModel(const Bbr2Params * params,QuicTime::Delta initial_rtt,QuicTime initial_rtt_timestamp,float cwnd_gain,float pacing_gain,const BandwidthSampler * old_sampler)54 Bbr2NetworkModel::Bbr2NetworkModel(const Bbr2Params* params,
55 QuicTime::Delta initial_rtt,
56 QuicTime initial_rtt_timestamp,
57 float cwnd_gain,
58 float pacing_gain,
59 const BandwidthSampler* old_sampler)
60 : params_(params),
61 bandwidth_sampler_([](QuicRoundTripCount max_height_tracker_window_length,
62 const BandwidthSampler* old_sampler) {
63 if (GetQuicReloadableFlag(quic_bbr_copy_sampler_state_from_v1_to_v2) &&
64 old_sampler != nullptr) {
65 QUIC_RELOADABLE_FLAG_COUNT(quic_bbr_copy_sampler_state_from_v1_to_v2);
66 return BandwidthSampler(*old_sampler);
67 }
68 return BandwidthSampler(/*unacked_packet_map=*/nullptr,
69 max_height_tracker_window_length);
70 }(params->initial_max_ack_height_filter_window, old_sampler)),
71 min_rtt_filter_(initial_rtt, initial_rtt_timestamp),
72 cwnd_gain_(cwnd_gain),
73 pacing_gain_(pacing_gain) {}
74
OnPacketSent(QuicTime sent_time,QuicByteCount bytes_in_flight,QuicPacketNumber packet_number,QuicByteCount bytes,HasRetransmittableData is_retransmittable)75 void Bbr2NetworkModel::OnPacketSent(QuicTime sent_time,
76 QuicByteCount bytes_in_flight,
77 QuicPacketNumber packet_number,
78 QuicByteCount bytes,
79 HasRetransmittableData is_retransmittable) {
80 round_trip_counter_.OnPacketSent(packet_number);
81
82 bandwidth_sampler_.OnPacketSent(sent_time, packet_number, bytes,
83 bytes_in_flight, is_retransmittable);
84 }
85
OnCongestionEventStart(QuicTime event_time,const AckedPacketVector & acked_packets,const LostPacketVector & lost_packets,Bbr2CongestionEvent * congestion_event)86 void Bbr2NetworkModel::OnCongestionEventStart(
87 QuicTime event_time,
88 const AckedPacketVector& acked_packets,
89 const LostPacketVector& lost_packets,
90 Bbr2CongestionEvent* congestion_event) {
91 const QuicByteCount prior_bytes_acked = total_bytes_acked();
92 const QuicByteCount prior_bytes_lost = total_bytes_lost();
93
94 congestion_event->event_time = event_time;
95 congestion_event->end_of_round_trip =
96 acked_packets.empty() ? false
97 : round_trip_counter_.OnPacketsAcked(
98 acked_packets.rbegin()->packet_number);
99
100 BandwidthSamplerInterface::CongestionEventSample sample =
101 bandwidth_sampler_.OnCongestionEvent(event_time, acked_packets,
102 lost_packets, MaxBandwidth(),
103 bandwidth_lo(), RoundTripCount());
104
105 if (sample.last_packet_send_state.is_valid) {
106 congestion_event->last_packet_send_state = sample.last_packet_send_state;
107 congestion_event->last_sample_is_app_limited =
108 sample.last_packet_send_state.is_app_limited;
109 }
110
111 // Avoid updating |max_bandwidth_filter_| if a) this is a loss-only event, or
112 // b) all packets in |acked_packets| did not generate valid samples. (e.g. ack
113 // of ack-only packets). In both cases, total_bytes_acked() will not change.
114 if (!fix_zero_bw_on_loss_only_event_ ||
115 (prior_bytes_acked != total_bytes_acked())) {
116 QUIC_BUG_IF((prior_bytes_acked != total_bytes_acked()) &&
117 sample.sample_max_bandwidth.IsZero())
118 << total_bytes_acked() - prior_bytes_acked << " bytes from "
119 << acked_packets.size()
120 << " packets have been acked, but sample_max_bandwidth is zero.";
121 if (!sample.sample_is_app_limited ||
122 sample.sample_max_bandwidth > MaxBandwidth()) {
123 congestion_event->sample_max_bandwidth = sample.sample_max_bandwidth;
124 max_bandwidth_filter_.Update(congestion_event->sample_max_bandwidth);
125 }
126 } else {
127 if (acked_packets.empty()) {
128 QUIC_RELOADABLE_FLAG_COUNT_N(quic_bbr_fix_zero_bw_on_loss_only_event, 3,
129 4);
130 } else {
131 QUIC_RELOADABLE_FLAG_COUNT_N(quic_bbr_fix_zero_bw_on_loss_only_event, 4,
132 4);
133 }
134 }
135
136 if (!sample.sample_rtt.IsInfinite()) {
137 congestion_event->sample_min_rtt = sample.sample_rtt;
138 min_rtt_filter_.Update(congestion_event->sample_min_rtt, event_time);
139 }
140
141 congestion_event->bytes_acked = total_bytes_acked() - prior_bytes_acked;
142 congestion_event->bytes_lost = total_bytes_lost() - prior_bytes_lost;
143
144 if (congestion_event->prior_bytes_in_flight >=
145 congestion_event->bytes_acked + congestion_event->bytes_lost) {
146 congestion_event->bytes_in_flight =
147 congestion_event->prior_bytes_in_flight -
148 congestion_event->bytes_acked - congestion_event->bytes_lost;
149 } else {
150 QUIC_LOG_FIRST_N(ERROR, 1)
151 << "prior_bytes_in_flight:" << congestion_event->prior_bytes_in_flight
152 << " is smaller than the sum of bytes_acked:"
153 << congestion_event->bytes_acked
154 << " and bytes_lost:" << congestion_event->bytes_lost;
155 congestion_event->bytes_in_flight = 0;
156 }
157
158 if (congestion_event->bytes_lost > 0) {
159 bytes_lost_in_round_ += congestion_event->bytes_lost;
160 loss_events_in_round_++;
161 }
162
163 // |bandwidth_latest_| and |inflight_latest_| only increased within a round.
164 if (sample.sample_max_bandwidth > bandwidth_latest_) {
165 bandwidth_latest_ = sample.sample_max_bandwidth;
166 }
167
168 if (sample.sample_max_inflight > inflight_latest_) {
169 inflight_latest_ = sample.sample_max_inflight;
170 }
171
172 if (!congestion_event->end_of_round_trip) {
173 return;
174 }
175
176 // Per round-trip updates.
177 AdaptLowerBounds(*congestion_event);
178
179 if (!sample.sample_max_bandwidth.IsZero()) {
180 bandwidth_latest_ = sample.sample_max_bandwidth;
181 }
182
183 if (sample.sample_max_inflight > 0) {
184 inflight_latest_ = sample.sample_max_inflight;
185 }
186 }
187
AdaptLowerBounds(const Bbr2CongestionEvent & congestion_event)188 void Bbr2NetworkModel::AdaptLowerBounds(
189 const Bbr2CongestionEvent& congestion_event) {
190 if (!congestion_event.end_of_round_trip ||
191 congestion_event.is_probing_for_bandwidth) {
192 return;
193 }
194
195 if (bytes_lost_in_round_ > 0) {
196 if (bandwidth_lo_.IsInfinite()) {
197 bandwidth_lo_ = MaxBandwidth();
198 }
199 if (inflight_lo_ == inflight_lo_default()) {
200 inflight_lo_ = congestion_event.prior_cwnd;
201 }
202
203 bandwidth_lo_ =
204 std::max(bandwidth_latest_, bandwidth_lo_ * (1.0 - Params().beta));
205 QUIC_DVLOG(3) << "bandwidth_lo_ updated to " << bandwidth_lo_
206 << ", bandwidth_latest_ is " << bandwidth_latest_;
207
208 inflight_lo_ = std::max<QuicByteCount>(
209 inflight_latest_, inflight_lo_ * (1.0 - Params().beta));
210 }
211 }
212
OnCongestionEventFinish(QuicPacketNumber least_unacked_packet,const Bbr2CongestionEvent & congestion_event)213 void Bbr2NetworkModel::OnCongestionEventFinish(
214 QuicPacketNumber least_unacked_packet,
215 const Bbr2CongestionEvent& congestion_event) {
216 if (congestion_event.end_of_round_trip) {
217 bytes_lost_in_round_ = 0;
218 loss_events_in_round_ = 0;
219 }
220
221 bandwidth_sampler_.RemoveObsoletePackets(least_unacked_packet);
222 }
223
UpdateNetworkParameters(QuicBandwidth bandwidth,QuicTime::Delta rtt)224 void Bbr2NetworkModel::UpdateNetworkParameters(QuicBandwidth bandwidth,
225 QuicTime::Delta rtt) {
226 if (!bandwidth.IsInfinite() && bandwidth > MaxBandwidth()) {
227 max_bandwidth_filter_.Update(bandwidth);
228 }
229
230 if (!rtt.IsZero()) {
231 min_rtt_filter_.Update(rtt, MinRttTimestamp());
232 }
233 }
234
MaybeExpireMinRtt(const Bbr2CongestionEvent & congestion_event)235 bool Bbr2NetworkModel::MaybeExpireMinRtt(
236 const Bbr2CongestionEvent& congestion_event) {
237 if (congestion_event.event_time <
238 (MinRttTimestamp() + Params().probe_rtt_period)) {
239 return false;
240 }
241 if (congestion_event.sample_min_rtt.IsInfinite()) {
242 return false;
243 }
244 QUIC_DVLOG(3) << "Replacing expired min rtt of " << min_rtt_filter_.Get()
245 << " by " << congestion_event.sample_min_rtt << " @ "
246 << congestion_event.event_time;
247 min_rtt_filter_.ForceUpdate(congestion_event.sample_min_rtt,
248 congestion_event.event_time);
249 return true;
250 }
251
IsCongestionWindowLimited(const Bbr2CongestionEvent & congestion_event) const252 bool Bbr2NetworkModel::IsCongestionWindowLimited(
253 const Bbr2CongestionEvent& congestion_event) const {
254 QuicByteCount prior_bytes_in_flight = congestion_event.bytes_in_flight +
255 congestion_event.bytes_acked +
256 congestion_event.bytes_lost;
257 return prior_bytes_in_flight >= congestion_event.prior_cwnd;
258 }
259
IsInflightTooHigh(const Bbr2CongestionEvent & congestion_event) const260 bool Bbr2NetworkModel::IsInflightTooHigh(
261 const Bbr2CongestionEvent& congestion_event) const {
262 const SendTimeState& send_state = congestion_event.last_packet_send_state;
263 if (!send_state.is_valid) {
264 // Not enough information.
265 return false;
266 }
267
268 const QuicByteCount inflight_at_send = BytesInFlight(send_state);
269 // TODO(wub): Consider total_bytes_lost() - send_state.total_bytes_lost, which
270 // is the total bytes lost when the largest numbered packet was inflight.
271 // bytes_lost_in_round_, OTOH, is the total bytes lost in the "current" round.
272 const QuicByteCount bytes_lost_in_round = bytes_lost_in_round_;
273
274 QUIC_DVLOG(3) << "IsInflightTooHigh: bytes_lost_in_round:"
275 << bytes_lost_in_round << ", lost_in_round_threshold:"
276 << inflight_at_send * Params().loss_threshold;
277
278 if (inflight_at_send > 0 && bytes_lost_in_round > 0) {
279 QuicByteCount lost_in_round_threshold =
280 inflight_at_send * Params().loss_threshold;
281 if (bytes_lost_in_round > lost_in_round_threshold) {
282 return true;
283 }
284 }
285
286 return false;
287 }
288
RestartRound()289 void Bbr2NetworkModel::RestartRound() {
290 bytes_lost_in_round_ = 0;
291 loss_events_in_round_ = 0;
292 round_trip_counter_.RestartRound();
293 }
294
inflight_hi_with_headroom() const295 QuicByteCount Bbr2NetworkModel::inflight_hi_with_headroom() const {
296 QuicByteCount headroom = inflight_hi_ * Params().inflight_hi_headroom;
297
298 return inflight_hi_ > headroom ? inflight_hi_ - headroom : 0;
299 }
300
301 } // namespace quic
302