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 "quiche/quic/core/congestion_control/bbr2_misc.h"
6
7 #include "quiche/quic/core/congestion_control/bandwidth_sampler.h"
8 #include "quiche/quic/core/quic_bandwidth.h"
9 #include "quiche/quic/core/quic_time.h"
10 #include "quiche/quic/core/quic_types.h"
11 #include "quiche/quic/platform/api/quic_bug_tracker.h"
12 #include "quiche/quic/platform/api/quic_flag_utils.h"
13 #include "quiche/quic/platform/api/quic_flags.h"
14 #include "quiche/quic/platform/api/quic_logging.h"
15
16 namespace quic {
17
RoundTripCounter()18 RoundTripCounter::RoundTripCounter() : round_trip_count_(0) {}
19
OnPacketSent(QuicPacketNumber packet_number)20 void RoundTripCounter::OnPacketSent(QuicPacketNumber packet_number) {
21 QUICHE_DCHECK(!last_sent_packet_.IsInitialized() ||
22 last_sent_packet_ < packet_number);
23 last_sent_packet_ = packet_number;
24 }
25
OnPacketsAcked(QuicPacketNumber last_acked_packet)26 bool RoundTripCounter::OnPacketsAcked(QuicPacketNumber last_acked_packet) {
27 if (!end_of_round_trip_.IsInitialized() ||
28 last_acked_packet > end_of_round_trip_) {
29 round_trip_count_++;
30 end_of_round_trip_ = last_sent_packet_;
31 return true;
32 }
33 return false;
34 }
35
RestartRound()36 void RoundTripCounter::RestartRound() {
37 end_of_round_trip_ = last_sent_packet_;
38 }
39
MinRttFilter(QuicTime::Delta initial_min_rtt,QuicTime initial_min_rtt_timestamp)40 MinRttFilter::MinRttFilter(QuicTime::Delta initial_min_rtt,
41 QuicTime initial_min_rtt_timestamp)
42 : min_rtt_(initial_min_rtt),
43 min_rtt_timestamp_(initial_min_rtt_timestamp) {}
44
Update(QuicTime::Delta sample_rtt,QuicTime now)45 void MinRttFilter::Update(QuicTime::Delta sample_rtt, QuicTime now) {
46 if (sample_rtt <= QuicTime::Delta::Zero()) {
47 return;
48 }
49 if (sample_rtt < min_rtt_ || min_rtt_timestamp_ == QuicTime::Zero()) {
50 min_rtt_ = sample_rtt;
51 min_rtt_timestamp_ = now;
52 }
53 }
54
ForceUpdate(QuicTime::Delta sample_rtt,QuicTime now)55 void MinRttFilter::ForceUpdate(QuicTime::Delta sample_rtt, QuicTime now) {
56 if (sample_rtt <= QuicTime::Delta::Zero()) {
57 return;
58 }
59 min_rtt_ = sample_rtt;
60 min_rtt_timestamp_ = now;
61 }
62
Bbr2NetworkModel(const Bbr2Params * params,QuicTime::Delta initial_rtt,QuicTime initial_rtt_timestamp,float cwnd_gain,float pacing_gain,const BandwidthSampler * old_sampler)63 Bbr2NetworkModel::Bbr2NetworkModel(const Bbr2Params* params,
64 QuicTime::Delta initial_rtt,
65 QuicTime initial_rtt_timestamp,
66 float cwnd_gain, float pacing_gain,
67 const BandwidthSampler* old_sampler)
68 : params_(params),
69 bandwidth_sampler_([](QuicRoundTripCount max_height_tracker_window_length,
70 const BandwidthSampler* old_sampler) {
71 if (old_sampler != nullptr) {
72 return BandwidthSampler(*old_sampler);
73 }
74 return BandwidthSampler(/*unacked_packet_map=*/nullptr,
75 max_height_tracker_window_length);
76 }(params->initial_max_ack_height_filter_window, old_sampler)),
77 min_rtt_filter_(initial_rtt, initial_rtt_timestamp),
78 cwnd_gain_(cwnd_gain),
79 pacing_gain_(pacing_gain) {}
80
OnPacketSent(QuicTime sent_time,QuicByteCount bytes_in_flight,QuicPacketNumber packet_number,QuicByteCount bytes,HasRetransmittableData is_retransmittable)81 void Bbr2NetworkModel::OnPacketSent(QuicTime sent_time,
82 QuicByteCount bytes_in_flight,
83 QuicPacketNumber packet_number,
84 QuicByteCount bytes,
85 HasRetransmittableData is_retransmittable) {
86 // Updating the min here ensures a more realistic (0) value when flows exit
87 // quiescence.
88 if (bytes_in_flight < min_bytes_in_flight_in_round_) {
89 min_bytes_in_flight_in_round_ = bytes_in_flight;
90 }
91 if (bytes_in_flight + bytes >= inflight_hi_) {
92 inflight_hi_limited_in_round_ = true;
93 }
94 round_trip_counter_.OnPacketSent(packet_number);
95
96 bandwidth_sampler_.OnPacketSent(sent_time, packet_number, bytes,
97 bytes_in_flight, is_retransmittable);
98 }
99
OnCongestionEventStart(QuicTime event_time,const AckedPacketVector & acked_packets,const LostPacketVector & lost_packets,Bbr2CongestionEvent * congestion_event)100 void Bbr2NetworkModel::OnCongestionEventStart(
101 QuicTime event_time, const AckedPacketVector& acked_packets,
102 const LostPacketVector& lost_packets,
103 Bbr2CongestionEvent* congestion_event) {
104 const QuicByteCount prior_bytes_acked = total_bytes_acked();
105 const QuicByteCount prior_bytes_lost = total_bytes_lost();
106
107 congestion_event->event_time = event_time;
108 congestion_event->end_of_round_trip =
109 acked_packets.empty() ? false
110 : round_trip_counter_.OnPacketsAcked(
111 acked_packets.rbegin()->packet_number);
112
113 BandwidthSamplerInterface::CongestionEventSample sample =
114 bandwidth_sampler_.OnCongestionEvent(event_time, acked_packets,
115 lost_packets, MaxBandwidth(),
116 bandwidth_lo(), RoundTripCount());
117
118 if (sample.extra_acked == 0) {
119 cwnd_limited_before_aggregation_epoch_ =
120 congestion_event->prior_bytes_in_flight >= congestion_event->prior_cwnd;
121 }
122
123 if (sample.last_packet_send_state.is_valid) {
124 congestion_event->last_packet_send_state = sample.last_packet_send_state;
125 }
126
127 // Avoid updating |max_bandwidth_filter_| if a) this is a loss-only event, or
128 // b) all packets in |acked_packets| did not generate valid samples. (e.g. ack
129 // of ack-only packets). In both cases, total_bytes_acked() will not change.
130 if (prior_bytes_acked != total_bytes_acked()) {
131 QUIC_LOG_IF(WARNING, sample.sample_max_bandwidth.IsZero())
132 << total_bytes_acked() - prior_bytes_acked << " bytes from "
133 << acked_packets.size()
134 << " packets have been acked, but sample_max_bandwidth is zero.";
135 congestion_event->sample_max_bandwidth = sample.sample_max_bandwidth;
136 if (!sample.sample_is_app_limited ||
137 sample.sample_max_bandwidth > MaxBandwidth()) {
138 max_bandwidth_filter_.Update(congestion_event->sample_max_bandwidth);
139 }
140 }
141
142 if (!sample.sample_rtt.IsInfinite()) {
143 congestion_event->sample_min_rtt = sample.sample_rtt;
144 min_rtt_filter_.Update(congestion_event->sample_min_rtt, event_time);
145 }
146
147 congestion_event->bytes_acked = total_bytes_acked() - prior_bytes_acked;
148 congestion_event->bytes_lost = total_bytes_lost() - prior_bytes_lost;
149
150 if (congestion_event->prior_bytes_in_flight >=
151 congestion_event->bytes_acked + congestion_event->bytes_lost) {
152 congestion_event->bytes_in_flight =
153 congestion_event->prior_bytes_in_flight -
154 congestion_event->bytes_acked - congestion_event->bytes_lost;
155 } else {
156 QUIC_BUG(quic_bbr2_prior_in_flight_too_small)
157 << "prior_bytes_in_flight:" << congestion_event->prior_bytes_in_flight
158 << " is smaller than the sum of bytes_acked:"
159 << congestion_event->bytes_acked
160 << " and bytes_lost:" << congestion_event->bytes_lost;
161 congestion_event->bytes_in_flight = 0;
162 }
163
164 if (congestion_event->bytes_lost > 0) {
165 bytes_lost_in_round_ += congestion_event->bytes_lost;
166 loss_events_in_round_++;
167 }
168
169 if (congestion_event->bytes_acked > 0 &&
170 congestion_event->last_packet_send_state.is_valid &&
171 total_bytes_acked() >
172 congestion_event->last_packet_send_state.total_bytes_acked) {
173 QuicByteCount bytes_delivered =
174 total_bytes_acked() -
175 congestion_event->last_packet_send_state.total_bytes_acked;
176 max_bytes_delivered_in_round_ =
177 std::max(max_bytes_delivered_in_round_, bytes_delivered);
178 }
179 // TODO(ianswett) Consider treating any bytes lost as decreasing inflight,
180 // because it's a sign of overutilization, not underutilization.
181 if (congestion_event->bytes_in_flight < min_bytes_in_flight_in_round_) {
182 min_bytes_in_flight_in_round_ = congestion_event->bytes_in_flight;
183 }
184
185 // |bandwidth_latest_| and |inflight_latest_| only increased within a round.
186 if (sample.sample_max_bandwidth > bandwidth_latest_) {
187 bandwidth_latest_ = sample.sample_max_bandwidth;
188 }
189
190 if (sample.sample_max_inflight > inflight_latest_) {
191 inflight_latest_ = sample.sample_max_inflight;
192 }
193
194 // Adapt lower bounds(bandwidth_lo and inflight_lo).
195 AdaptLowerBounds(*congestion_event);
196
197 if (!congestion_event->end_of_round_trip) {
198 return;
199 }
200
201 if (!sample.sample_max_bandwidth.IsZero()) {
202 bandwidth_latest_ = sample.sample_max_bandwidth;
203 }
204
205 if (sample.sample_max_inflight > 0) {
206 inflight_latest_ = sample.sample_max_inflight;
207 }
208 }
209
AdaptLowerBounds(const Bbr2CongestionEvent & congestion_event)210 void Bbr2NetworkModel::AdaptLowerBounds(
211 const Bbr2CongestionEvent& congestion_event) {
212 if (Params().bw_lo_mode_ == Bbr2Params::DEFAULT) {
213 if (!congestion_event.end_of_round_trip ||
214 congestion_event.is_probing_for_bandwidth) {
215 return;
216 }
217
218 if (bytes_lost_in_round_ > 0) {
219 if (bandwidth_lo_.IsInfinite()) {
220 bandwidth_lo_ = MaxBandwidth();
221 }
222 bandwidth_lo_ =
223 std::max(bandwidth_latest_, bandwidth_lo_ * (1.0 - Params().beta));
224 QUIC_DVLOG(3) << "bandwidth_lo_ updated to " << bandwidth_lo_
225 << ", bandwidth_latest_ is " << bandwidth_latest_;
226
227 if (Params().ignore_inflight_lo) {
228 return;
229 }
230 if (inflight_lo_ == inflight_lo_default()) {
231 inflight_lo_ = congestion_event.prior_cwnd;
232 }
233 inflight_lo_ = std::max<QuicByteCount>(
234 inflight_latest_, inflight_lo_ * (1.0 - Params().beta));
235 }
236 return;
237 }
238
239 // Params().bw_lo_mode_ != Bbr2Params::DEFAULT
240 if (congestion_event.bytes_lost == 0) {
241 return;
242 }
243 // Ignore losses from packets sent when probing for more bandwidth in
244 // STARTUP or PROBE_UP when they're lost in DRAIN or PROBE_DOWN.
245 if (pacing_gain_ < 1) {
246 return;
247 }
248 // Decrease bandwidth_lo whenever there is loss.
249 // Set bandwidth_lo_ if it is not yet set.
250 if (bandwidth_lo_.IsInfinite()) {
251 bandwidth_lo_ = MaxBandwidth();
252 }
253 // Save bandwidth_lo_ if it hasn't already been saved.
254 if (prior_bandwidth_lo_.IsZero()) {
255 prior_bandwidth_lo_ = bandwidth_lo_;
256 }
257 switch (Params().bw_lo_mode_) {
258 case Bbr2Params::MIN_RTT_REDUCTION:
259 bandwidth_lo_ =
260 bandwidth_lo_ - QuicBandwidth::FromBytesAndTimeDelta(
261 congestion_event.bytes_lost, MinRtt());
262 break;
263 case Bbr2Params::INFLIGHT_REDUCTION: {
264 // Use a max of BDP and inflight to avoid starving app-limited flows.
265 const QuicByteCount effective_inflight =
266 std::max(BDP(), congestion_event.prior_bytes_in_flight);
267 // This could use bytes_lost_in_round if the bandwidth_lo_ was saved
268 // when entering 'recovery', but this BBRv2 implementation doesn't have
269 // recovery defined.
270 bandwidth_lo_ =
271 bandwidth_lo_ * ((effective_inflight - congestion_event.bytes_lost) /
272 static_cast<double>(effective_inflight));
273 break;
274 }
275 case Bbr2Params::CWND_REDUCTION:
276 bandwidth_lo_ =
277 bandwidth_lo_ *
278 ((congestion_event.prior_cwnd - congestion_event.bytes_lost) /
279 static_cast<double>(congestion_event.prior_cwnd));
280 break;
281 case Bbr2Params::DEFAULT:
282 QUIC_BUG(quic_bug_10466_1) << "Unreachable case DEFAULT.";
283 }
284 QuicBandwidth last_bandwidth = bandwidth_latest_;
285 // sample_max_bandwidth will be Zero() if the loss is triggered by a timer
286 // expiring. Ideally we'd use the most recent bandwidth sample,
287 // but bandwidth_latest is safer than Zero().
288 if (!congestion_event.sample_max_bandwidth.IsZero()) {
289 // bandwidth_latest_ is the max bandwidth for the round, but to allow
290 // fast, conservation style response to loss, use the last sample.
291 last_bandwidth = congestion_event.sample_max_bandwidth;
292 }
293 if (pacing_gain_ > Params().full_bw_threshold) {
294 // In STARTUP, pacing_gain_ is applied to bandwidth_lo_ in
295 // UpdatePacingRate, so this backs that multiplication out to allow the
296 // pacing rate to decrease, but not below
297 // last_bandwidth * full_bw_threshold.
298 // TODO(ianswett): Consider altering pacing_gain_ when in STARTUP instead.
299 bandwidth_lo_ =
300 std::max(bandwidth_lo_,
301 last_bandwidth * (Params().full_bw_threshold / pacing_gain_));
302 } else {
303 // Ensure bandwidth_lo isn't lower than last_bandwidth.
304 bandwidth_lo_ = std::max(bandwidth_lo_, last_bandwidth);
305 }
306 // If it's the end of the round, ensure bandwidth_lo doesn't decrease more
307 // than beta.
308 if (congestion_event.end_of_round_trip) {
309 bandwidth_lo_ =
310 std::max(bandwidth_lo_, prior_bandwidth_lo_ * (1.0 - Params().beta));
311 prior_bandwidth_lo_ = QuicBandwidth::Zero();
312 }
313 // These modes ignore inflight_lo as well.
314 }
315
OnCongestionEventFinish(QuicPacketNumber least_unacked_packet,const Bbr2CongestionEvent & congestion_event)316 void Bbr2NetworkModel::OnCongestionEventFinish(
317 QuicPacketNumber least_unacked_packet,
318 const Bbr2CongestionEvent& congestion_event) {
319 if (congestion_event.end_of_round_trip) {
320 OnNewRound();
321 }
322
323 bandwidth_sampler_.RemoveObsoletePackets(least_unacked_packet);
324 }
325
UpdateNetworkParameters(QuicTime::Delta rtt)326 void Bbr2NetworkModel::UpdateNetworkParameters(QuicTime::Delta rtt) {
327 if (!rtt.IsZero()) {
328 min_rtt_filter_.Update(rtt, MinRttTimestamp());
329 }
330 }
331
MaybeExpireMinRtt(const Bbr2CongestionEvent & congestion_event)332 bool Bbr2NetworkModel::MaybeExpireMinRtt(
333 const Bbr2CongestionEvent& congestion_event) {
334 if (congestion_event.event_time <
335 (MinRttTimestamp() + Params().probe_rtt_period)) {
336 return false;
337 }
338 if (congestion_event.sample_min_rtt.IsInfinite()) {
339 return false;
340 }
341 QUIC_DVLOG(3) << "Replacing expired min rtt of " << min_rtt_filter_.Get()
342 << " by " << congestion_event.sample_min_rtt << " @ "
343 << congestion_event.event_time;
344 min_rtt_filter_.ForceUpdate(congestion_event.sample_min_rtt,
345 congestion_event.event_time);
346 return true;
347 }
348
IsInflightTooHigh(const Bbr2CongestionEvent & congestion_event,int64_t max_loss_events) const349 bool Bbr2NetworkModel::IsInflightTooHigh(
350 const Bbr2CongestionEvent& congestion_event,
351 int64_t max_loss_events) const {
352 const SendTimeState& send_state = congestion_event.last_packet_send_state;
353 if (!send_state.is_valid) {
354 // Not enough information.
355 return false;
356 }
357
358 if (loss_events_in_round() < max_loss_events) {
359 return false;
360 }
361
362 const QuicByteCount inflight_at_send = BytesInFlight(send_state);
363 // TODO(wub): Consider total_bytes_lost() - send_state.total_bytes_lost, which
364 // is the total bytes lost when the largest numbered packet was inflight.
365 // bytes_lost_in_round_, OTOH, is the total bytes lost in the "current" round.
366 const QuicByteCount bytes_lost_in_round = bytes_lost_in_round_;
367
368 QUIC_DVLOG(3) << "IsInflightTooHigh: loss_events_in_round:"
369 << loss_events_in_round()
370
371 << " bytes_lost_in_round:" << bytes_lost_in_round
372 << ", lost_in_round_threshold:"
373 << inflight_at_send * Params().loss_threshold;
374
375 if (inflight_at_send > 0 && bytes_lost_in_round > 0) {
376 QuicByteCount lost_in_round_threshold =
377 inflight_at_send * Params().loss_threshold;
378 if (bytes_lost_in_round > lost_in_round_threshold) {
379 return true;
380 }
381 }
382
383 return false;
384 }
385
RestartRoundEarly()386 void Bbr2NetworkModel::RestartRoundEarly() {
387 OnNewRound();
388 round_trip_counter_.RestartRound();
389 rounds_with_queueing_ = 0;
390 }
391
OnNewRound()392 void Bbr2NetworkModel::OnNewRound() {
393 bytes_lost_in_round_ = 0;
394 loss_events_in_round_ = 0;
395 max_bytes_delivered_in_round_ = 0;
396 min_bytes_in_flight_in_round_ = std::numeric_limits<uint64_t>::max();
397 inflight_hi_limited_in_round_ = false;
398 }
399
cap_inflight_lo(QuicByteCount cap)400 void Bbr2NetworkModel::cap_inflight_lo(QuicByteCount cap) {
401 if (Params().ignore_inflight_lo) {
402 return;
403 }
404 if (inflight_lo_ != inflight_lo_default() && inflight_lo_ > cap) {
405 inflight_lo_ = cap;
406 }
407 }
408
inflight_hi_with_headroom() const409 QuicByteCount Bbr2NetworkModel::inflight_hi_with_headroom() const {
410 QuicByteCount headroom = inflight_hi_ * Params().inflight_hi_headroom;
411
412 return inflight_hi_ > headroom ? inflight_hi_ - headroom : 0;
413 }
414
HasBandwidthGrowth(const Bbr2CongestionEvent & congestion_event)415 bool Bbr2NetworkModel::HasBandwidthGrowth(
416 const Bbr2CongestionEvent& congestion_event) {
417 QUICHE_DCHECK(!full_bandwidth_reached_);
418 QUICHE_DCHECK(congestion_event.end_of_round_trip);
419
420 QuicBandwidth threshold =
421 full_bandwidth_baseline_ * Params().full_bw_threshold;
422
423 if (MaxBandwidth() >= threshold) {
424 QUIC_DVLOG(3) << " CheckBandwidthGrowth at end of round. max_bandwidth:"
425 << MaxBandwidth() << ", threshold:" << threshold
426 << " (Still growing) @ " << congestion_event.event_time;
427 full_bandwidth_baseline_ = MaxBandwidth();
428 rounds_without_bandwidth_growth_ = 0;
429 return true;
430 }
431 ++rounds_without_bandwidth_growth_;
432
433 // full_bandwidth_reached is only set to true when not app-limited, except
434 // when exit_startup_on_persistent_queue is true.
435 if (rounds_without_bandwidth_growth_ >= Params().startup_full_bw_rounds &&
436 !congestion_event.last_packet_send_state.is_app_limited) {
437 full_bandwidth_reached_ = true;
438 }
439 QUIC_DVLOG(3) << " CheckBandwidthGrowth at end of round. max_bandwidth:"
440 << MaxBandwidth() << ", threshold:" << threshold
441 << " rounds_without_growth:" << rounds_without_bandwidth_growth_
442 << " full_bw_reached:" << full_bandwidth_reached_ << " @ "
443 << congestion_event.event_time;
444
445 return false;
446 }
447
CheckPersistentQueue(const Bbr2CongestionEvent & congestion_event,float target_gain)448 void Bbr2NetworkModel::CheckPersistentQueue(
449 const Bbr2CongestionEvent& congestion_event, float target_gain) {
450 QUICHE_DCHECK(congestion_event.end_of_round_trip);
451 QUICHE_DCHECK_NE(min_bytes_in_flight_in_round_,
452 std::numeric_limits<uint64_t>::max());
453 QUICHE_DCHECK_GE(target_gain, Params().full_bw_threshold);
454 QuicByteCount target =
455 std::max(static_cast<QuicByteCount>(target_gain * BDP()),
456 BDP() + QueueingThresholdExtraBytes());
457 if (min_bytes_in_flight_in_round_ < target) {
458 rounds_with_queueing_ = 0;
459 return;
460 }
461 rounds_with_queueing_++;
462 if (rounds_with_queueing_ >= Params().max_startup_queue_rounds) {
463 full_bandwidth_reached_ = true;
464 }
465 }
466
467 } // namespace quic
468