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 #ifndef QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_MISC_H_
6 #define QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_MISC_H_
7
8 #include <algorithm>
9 #include <limits>
10
11 #include "net/third_party/quiche/src/quic/core/congestion_control/bandwidth_sampler.h"
12 #include "net/third_party/quiche/src/quic/core/congestion_control/windowed_filter.h"
13 #include "net/third_party/quiche/src/quic/core/quic_bandwidth.h"
14 #include "net/third_party/quiche/src/quic/core/quic_packet_number.h"
15 #include "net/third_party/quiche/src/quic/core/quic_time.h"
16 #include "net/third_party/quiche/src/quic/core/quic_types.h"
17 #include "net/third_party/quiche/src/quic/platform/api/quic_export.h"
18 #include "net/third_party/quiche/src/quic/platform/api/quic_flags.h"
19 #include "net/quic/platform/impl/quic_export_impl.h"
20
21 namespace quic {
22
23 template <typename T>
24 class QUIC_EXPORT_PRIVATE Limits {
25 public:
Limits(T min,T max)26 Limits(T min, T max) : min_(min), max_(max) {}
27
28 // If [min, max] is an empty range, i.e. min > max, this function returns max,
29 // because typically a value larger than max means "risky".
ApplyLimits(T raw_value)30 T ApplyLimits(T raw_value) const {
31 return std::min(max_, std::max(min_, raw_value));
32 }
33
Min()34 T Min() const { return min_; }
Max()35 T Max() const { return max_; }
36
37 private:
38 T min_;
39 T max_;
40 };
41
42 template <typename T>
MinMax(T min,T max)43 QUIC_EXPORT_PRIVATE inline Limits<T> MinMax(T min, T max) {
44 return Limits<T>(min, max);
45 }
46
47 template <typename T>
NoLessThan(T min)48 QUIC_EXPORT_PRIVATE inline Limits<T> NoLessThan(T min) {
49 return Limits<T>(min, std::numeric_limits<T>::max());
50 }
51
52 template <typename T>
NoGreaterThan(T max)53 QUIC_EXPORT_PRIVATE inline Limits<T> NoGreaterThan(T max) {
54 return Limits<T>(std::numeric_limits<T>::min(), max);
55 }
56
57 template <typename T>
Unlimited()58 QUIC_EXPORT_PRIVATE inline Limits<T> Unlimited() {
59 return Limits<T>(std::numeric_limits<T>::min(),
60 std::numeric_limits<T>::max());
61 }
62
63 template <typename T>
64 QUIC_EXPORT_PRIVATE inline std::ostream& operator<<(std::ostream& os,
65 const Limits<T>& limits) {
66 return os << "[" << limits.Min() << ", " << limits.Max() << "]";
67 }
68
69 // Bbr2Params contains all parameters of a Bbr2Sender.
70 struct QUIC_EXPORT_PRIVATE Bbr2Params {
Bbr2ParamsBbr2Params71 Bbr2Params(QuicByteCount cwnd_min, QuicByteCount cwnd_max)
72 : cwnd_limits(cwnd_min, cwnd_max) {}
73
74 /*
75 * STARTUP parameters.
76 */
77
78 // The gain for both CWND and PacingRate at startup.
79 // TODO(wub): Maybe change to the newly derived value of 2.773 (4 * ln(2)).
80 float startup_gain = 2.885;
81
82 // Full bandwidth is declared if the total bandwidth growth is less than
83 // |startup_full_bw_threshold| times in the last |startup_full_bw_rounds|
84 // round trips.
85 float startup_full_bw_threshold = 1.25;
86
87 QuicRoundTripCount startup_full_bw_rounds = 3;
88
89 // The minimum number of loss marking events to exit STARTUP.
90 int64_t startup_full_loss_count =
91 GetQuicFlag(FLAGS_quic_bbr2_default_startup_full_loss_count);
92
93 /*
94 * DRAIN parameters.
95 */
96 float drain_cwnd_gain = 2.885;
97 float drain_pacing_gain = 1.0 / 2.885;
98
99 /*
100 * PROBE_BW parameters.
101 */
102 // Max amount of randomness to inject in round counting for Reno-coexistence.
103 QuicRoundTripCount probe_bw_max_probe_rand_rounds = 2;
104
105 // Max number of rounds before probing for Reno-coexistence.
106 uint32_t probe_bw_probe_max_rounds = 63;
107
108 // Multiplier to get Reno-style probe epoch duration as: k * BDP round trips.
109 // If zero, disables Reno-style BDP-scaled coexistence mechanism.
110 float probe_bw_probe_reno_gain = 1.0;
111
112 // Minimum duration for BBR-native probes.
113 QuicTime::Delta probe_bw_probe_base_duration =
114 QuicTime::Delta::FromMilliseconds(
115 GetQuicFlag(FLAGS_quic_bbr2_default_probe_bw_base_duration_ms));
116
117 // The upper bound of the random amount of BBR-native probes.
118 QuicTime::Delta probe_bw_probe_max_rand_duration =
119 QuicTime::Delta::FromMilliseconds(
120 GetQuicFlag(FLAGS_quic_bbr2_default_probe_bw_max_rand_duration_ms));
121
122 // The minimum number of loss marking events to exit the PROBE_UP phase.
123 int64_t probe_bw_full_loss_count =
124 GetQuicFlag(FLAGS_quic_bbr2_default_probe_bw_full_loss_count);
125
126 // Multiplier to get target inflight (as multiple of BDP) for PROBE_UP phase.
127 float probe_bw_probe_inflight_gain = 1.25;
128
129 // Pacing gains.
130 float probe_bw_probe_up_pacing_gain = 1.25;
131 float probe_bw_probe_down_pacing_gain = 0.75;
132 float probe_bw_default_pacing_gain = 1.0;
133
134 float probe_bw_cwnd_gain = 2.0;
135
136 /*
137 * PROBE_RTT parameters.
138 */
139 float probe_rtt_inflight_target_bdp_fraction = 0.5;
140 QuicTime::Delta probe_rtt_period = QuicTime::Delta::FromMilliseconds(
141 GetQuicFlag(FLAGS_quic_bbr2_default_probe_rtt_period_ms));
142 QuicTime::Delta probe_rtt_duration = QuicTime::Delta::FromMilliseconds(200);
143
144 /*
145 * Parameters used by multiple modes.
146 */
147
148 // The initial value of the max ack height filter's window length.
149 QuicRoundTripCount initial_max_ack_height_filter_window =
150 GetQuicFlag(FLAGS_quic_bbr2_default_initial_ack_height_filter_window);
151
152 // Fraction of unutilized headroom to try to leave in path upon high loss.
153 float inflight_hi_headroom =
154 GetQuicFlag(FLAGS_quic_bbr2_default_inflight_hi_headroom);
155
156 // Estimate startup/bw probing has gone too far if loss rate exceeds this.
157 float loss_threshold = GetQuicFlag(FLAGS_quic_bbr2_default_loss_threshold);
158
159 // A common factor for multiplicative decreases. Used for adjusting
160 // bandwidth_lo, inflight_lo and inflight_hi upon losses.
161 float beta = 0.3;
162
163 Limits<QuicByteCount> cwnd_limits;
164
165 /*
166 * Experimental flags from QuicConfig.
167 */
168
169 // Indicates app-limited calls should be ignored as long as there's
170 // enough data inflight to see more bandwidth when necessary.
171 bool flexible_app_limited = false;
172
173 // Can be disabled by connection option 'B2NA'.
174 bool add_ack_height_to_queueing_threshold =
175 GetQuicReloadableFlag(quic_bbr2_add_ack_height_to_queueing_threshold);
176
177 // Can be disabled by connection option 'B2RP'.
178 bool avoid_unnecessary_probe_rtt =
179 GetQuicReloadableFlag(quic_bbr2_avoid_unnecessary_probe_rtt);
180 };
181
182 class QUIC_EXPORT_PRIVATE RoundTripCounter {
183 public:
184 RoundTripCounter();
185
Count()186 QuicRoundTripCount Count() const { return round_trip_count_; }
187
last_sent_packet()188 QuicPacketNumber last_sent_packet() const { return last_sent_packet_; }
189
190 // Must be called in ascending packet number order.
191 void OnPacketSent(QuicPacketNumber packet_number);
192
193 // Return whether a round trip has just completed.
194 bool OnPacketsAcked(QuicPacketNumber last_acked_packet);
195
196 void RestartRound();
197
198 private:
199 QuicRoundTripCount round_trip_count_;
200 QuicPacketNumber last_sent_packet_;
201 // The last sent packet number of the current round trip.
202 QuicPacketNumber end_of_round_trip_;
203 };
204
205 class QUIC_EXPORT_PRIVATE MinRttFilter {
206 public:
207 MinRttFilter(QuicTime::Delta initial_min_rtt,
208 QuicTime initial_min_rtt_timestamp);
209
210 void Update(QuicTime::Delta sample_rtt, QuicTime now);
211
212 void ForceUpdate(QuicTime::Delta sample_rtt, QuicTime now);
213
Get()214 QuicTime::Delta Get() const { return min_rtt_; }
215
GetTimestamp()216 QuicTime GetTimestamp() const { return min_rtt_timestamp_; }
217
218 private:
219 QuicTime::Delta min_rtt_;
220 // Time when the current value of |min_rtt_| was assigned.
221 QuicTime min_rtt_timestamp_;
222 };
223
224 class QUIC_EXPORT_PRIVATE Bbr2MaxBandwidthFilter {
225 public:
Update(QuicBandwidth sample)226 void Update(QuicBandwidth sample) {
227 max_bandwidth_[1] = std::max(sample, max_bandwidth_[1]);
228 }
229
Advance()230 void Advance() {
231 if (max_bandwidth_[1].IsZero()) {
232 return;
233 }
234
235 max_bandwidth_[0] = max_bandwidth_[1];
236 max_bandwidth_[1] = QuicBandwidth::Zero();
237 }
238
Get()239 QuicBandwidth Get() const {
240 return std::max(max_bandwidth_[0], max_bandwidth_[1]);
241 }
242
243 private:
244 QuicBandwidth max_bandwidth_[2] = {QuicBandwidth::Zero(),
245 QuicBandwidth::Zero()};
246 };
247
248 // Information that are meaningful only when Bbr2Sender::OnCongestionEvent is
249 // running.
250 struct QUIC_EXPORT_PRIVATE Bbr2CongestionEvent {
251 QuicTime event_time = QuicTime::Zero();
252
253 // The congestion window prior to the processing of the ack/loss events.
254 QuicByteCount prior_cwnd;
255
256 // Total bytes inflight before the processing of the ack/loss events.
257 QuicByteCount prior_bytes_in_flight = 0;
258
259 // Total bytes inflight after the processing of the ack/loss events.
260 QuicByteCount bytes_in_flight = 0;
261
262 // Total bytes acked from acks in this event.
263 QuicByteCount bytes_acked = 0;
264
265 // Total bytes lost from losses in this event.
266 QuicByteCount bytes_lost = 0;
267
268 // Whether acked_packets indicates the end of a round trip.
269 bool end_of_round_trip = false;
270
271 // TODO(wub): After deprecating --quic_one_bw_sample_per_ack_event, use
272 // last_packet_send_state.is_app_limited instead of this field.
273 // Whether the last bandwidth sample from acked_packets is app limited.
274 // false if acked_packets is empty.
275 bool last_sample_is_app_limited = false;
276
277 // When the event happened, whether the sender is probing for bandwidth.
278 bool is_probing_for_bandwidth = false;
279
280 // Minimum rtt of all bandwidth samples from acked_packets.
281 // QuicTime::Delta::Infinite() if acked_packets is empty.
282 QuicTime::Delta sample_min_rtt = QuicTime::Delta::Infinite();
283
284 // Maximum bandwidth of all bandwidth samples from acked_packets.
285 QuicBandwidth sample_max_bandwidth = QuicBandwidth::Zero();
286
287 // The send state of the largest packet in acked_packets, unless it is empty.
288 // If acked_packets is empty, it's the send state of the largest packet in
289 // lost_packets.
290 SendTimeState last_packet_send_state;
291 };
292
293 // Bbr2NetworkModel takes low level congestion signals(packets sent/acked/lost)
294 // as input and produces BBRv2 model parameters like inflight_(hi|lo),
295 // bandwidth_(hi|lo), bandwidth and rtt estimates, etc.
296 class QUIC_EXPORT_PRIVATE Bbr2NetworkModel {
297 public:
298 Bbr2NetworkModel(const Bbr2Params* params,
299 QuicTime::Delta initial_rtt,
300 QuicTime initial_rtt_timestamp,
301 float cwnd_gain,
302 float pacing_gain,
303 const BandwidthSampler* old_sampler);
304
305 void OnPacketSent(QuicTime sent_time,
306 QuicByteCount bytes_in_flight,
307 QuicPacketNumber packet_number,
308 QuicByteCount bytes,
309 HasRetransmittableData is_retransmittable);
310
311 void OnCongestionEventStart(QuicTime event_time,
312 const AckedPacketVector& acked_packets,
313 const LostPacketVector& lost_packets,
314 Bbr2CongestionEvent* congestion_event);
315
316 void OnCongestionEventFinish(QuicPacketNumber least_unacked_packet,
317 const Bbr2CongestionEvent& congestion_event);
318
319 // Update the model without a congestion event.
320 // Max bandwidth is updated if |bandwidth| is larger than existing max
321 // bandwidth. Min rtt is updated if |rtt| is non-zero and smaller than
322 // existing min rtt.
323 void UpdateNetworkParameters(QuicBandwidth bandwidth, QuicTime::Delta rtt);
324
325 // Update inflight/bandwidth short-term lower bounds.
326 void AdaptLowerBounds(const Bbr2CongestionEvent& congestion_event);
327
328 // Restart the current round trip as if it is starting now.
329 void RestartRound();
330
AdvanceMaxBandwidthFilter()331 void AdvanceMaxBandwidthFilter() { max_bandwidth_filter_.Advance(); }
332
OnApplicationLimited()333 void OnApplicationLimited() { bandwidth_sampler_.OnAppLimited(); }
334
BDP(QuicBandwidth bandwidth)335 QuicByteCount BDP(QuicBandwidth bandwidth) const {
336 return bandwidth * MinRtt();
337 }
338
BDP(QuicBandwidth bandwidth,float gain)339 QuicByteCount BDP(QuicBandwidth bandwidth, float gain) const {
340 return bandwidth * MinRtt() * gain;
341 }
342
MinRtt()343 QuicTime::Delta MinRtt() const { return min_rtt_filter_.Get(); }
344
MinRttTimestamp()345 QuicTime MinRttTimestamp() const { return min_rtt_filter_.GetTimestamp(); }
346
347 // TODO(wub): If we do this too frequently, we can potentailly postpone
348 // PROBE_RTT indefinitely. Observe how it works in production and improve it.
PostponeMinRttTimestamp(QuicTime::Delta duration)349 void PostponeMinRttTimestamp(QuicTime::Delta duration) {
350 min_rtt_filter_.ForceUpdate(MinRtt(), MinRttTimestamp() + duration);
351 }
352
MaxBandwidth()353 QuicBandwidth MaxBandwidth() const { return max_bandwidth_filter_.Get(); }
354
MaxAckHeight()355 QuicByteCount MaxAckHeight() const {
356 return bandwidth_sampler_.max_ack_height();
357 }
358
EnableOverestimateAvoidance()359 void EnableOverestimateAvoidance() {
360 bandwidth_sampler_.EnableOverestimateAvoidance();
361 }
362
OnPacketNeutered(QuicPacketNumber packet_number)363 void OnPacketNeutered(QuicPacketNumber packet_number) {
364 bandwidth_sampler_.OnPacketNeutered(packet_number);
365 }
366
num_ack_aggregation_epochs()367 uint64_t num_ack_aggregation_epochs() const {
368 return bandwidth_sampler_.num_ack_aggregation_epochs();
369 }
370
371 bool MaybeExpireMinRtt(const Bbr2CongestionEvent& congestion_event);
372
BandwidthEstimate()373 QuicBandwidth BandwidthEstimate() const {
374 return std::min(MaxBandwidth(), bandwidth_lo_);
375 }
376
RoundTripCount()377 QuicRoundTripCount RoundTripCount() const {
378 return round_trip_counter_.Count();
379 }
380
381 bool IsCongestionWindowLimited(
382 const Bbr2CongestionEvent& congestion_event) const;
383
384 // TODO(wub): Replace this by a new version which takes two thresholds, one
385 // is the number of loss events, the other is the percentage of bytes lost.
386 bool IsInflightTooHigh(const Bbr2CongestionEvent& congestion_event) const;
387
last_sent_packet()388 QuicPacketNumber last_sent_packet() const {
389 return round_trip_counter_.last_sent_packet();
390 }
391
total_bytes_acked()392 QuicByteCount total_bytes_acked() const {
393 return bandwidth_sampler_.total_bytes_acked();
394 }
395
total_bytes_lost()396 QuicByteCount total_bytes_lost() const {
397 return bandwidth_sampler_.total_bytes_lost();
398 }
399
total_bytes_sent()400 QuicByteCount total_bytes_sent() const {
401 return bandwidth_sampler_.total_bytes_sent();
402 }
403
loss_events_in_round()404 int64_t loss_events_in_round() const { return loss_events_in_round_; }
405
end_of_app_limited_phase()406 QuicPacketNumber end_of_app_limited_phase() const {
407 return bandwidth_sampler_.end_of_app_limited_phase();
408 }
409
bandwidth_latest()410 QuicBandwidth bandwidth_latest() const { return bandwidth_latest_; }
bandwidth_lo()411 QuicBandwidth bandwidth_lo() const { return bandwidth_lo_; }
bandwidth_lo_default()412 static QuicBandwidth bandwidth_lo_default() {
413 return QuicBandwidth::Infinite();
414 }
clear_bandwidth_lo()415 void clear_bandwidth_lo() { bandwidth_lo_ = bandwidth_lo_default(); }
416
inflight_latest()417 QuicByteCount inflight_latest() const { return inflight_latest_; }
inflight_lo()418 QuicByteCount inflight_lo() const { return inflight_lo_; }
inflight_lo_default()419 static QuicByteCount inflight_lo_default() {
420 return std::numeric_limits<QuicByteCount>::max();
421 }
clear_inflight_lo()422 void clear_inflight_lo() { inflight_lo_ = inflight_lo_default(); }
cap_inflight_lo(QuicByteCount cap)423 void cap_inflight_lo(QuicByteCount cap) {
424 if (inflight_lo_ != inflight_lo_default() && inflight_lo_ > cap) {
425 inflight_lo_ = cap;
426 }
427 }
428
429 QuicByteCount inflight_hi_with_headroom() const;
inflight_hi()430 QuicByteCount inflight_hi() const { return inflight_hi_; }
inflight_hi_default()431 static QuicByteCount inflight_hi_default() {
432 return std::numeric_limits<QuicByteCount>::max();
433 }
set_inflight_hi(QuicByteCount inflight_hi)434 void set_inflight_hi(QuicByteCount inflight_hi) {
435 inflight_hi_ = inflight_hi;
436 }
437
cwnd_gain()438 float cwnd_gain() const { return cwnd_gain_; }
set_cwnd_gain(float cwnd_gain)439 void set_cwnd_gain(float cwnd_gain) { cwnd_gain_ = cwnd_gain; }
440
pacing_gain()441 float pacing_gain() const { return pacing_gain_; }
set_pacing_gain(float pacing_gain)442 void set_pacing_gain(float pacing_gain) { pacing_gain_ = pacing_gain; }
443
444 private:
Params()445 const Bbr2Params& Params() const { return *params_; }
446 const Bbr2Params* const params_;
447 RoundTripCounter round_trip_counter_;
448
449 // Bandwidth sampler provides BBR with the bandwidth measurements at
450 // individual points.
451 BandwidthSampler bandwidth_sampler_;
452 // The filter that tracks the maximum bandwidth over multiple recent round
453 // trips.
454 Bbr2MaxBandwidthFilter max_bandwidth_filter_;
455 MinRttFilter min_rtt_filter_;
456
457 // Bytes lost in the current round. Updated once per congestion event.
458 QuicByteCount bytes_lost_in_round_ = 0;
459 // Number of loss marking events in the current round.
460 int64_t loss_events_in_round_ = 0;
461
462 // Max bandwidth in the current round. Updated once per congestion event.
463 QuicBandwidth bandwidth_latest_ = QuicBandwidth::Zero();
464 // Max bandwidth of recent rounds. Updated once per round.
465 QuicBandwidth bandwidth_lo_ = bandwidth_lo_default();
466
467 // Max inflight in the current round. Updated once per congestion event.
468 QuicByteCount inflight_latest_ = 0;
469 // Max inflight of recent rounds. Updated once per round.
470 QuicByteCount inflight_lo_ = inflight_lo_default();
471 QuicByteCount inflight_hi_ = inflight_hi_default();
472
473 float cwnd_gain_;
474 float pacing_gain_;
475
476 const bool fix_zero_bw_on_loss_only_event_ =
477 GetQuicReloadableFlag(quic_bbr_fix_zero_bw_on_loss_only_event);
478 };
479
480 enum class Bbr2Mode : uint8_t {
481 // Startup phase of the connection.
482 STARTUP,
483 // After achieving the highest possible bandwidth during the startup, lower
484 // the pacing rate in order to drain the queue.
485 DRAIN,
486 // Cruising mode.
487 PROBE_BW,
488 // Temporarily slow down sending in order to empty the buffer and measure
489 // the real minimum RTT.
490 PROBE_RTT,
491 };
492
493 QUIC_EXPORT_PRIVATE inline std::ostream& operator<<(std::ostream& os,
494 const Bbr2Mode& mode) {
495 switch (mode) {
496 case Bbr2Mode::STARTUP:
497 return os << "STARTUP";
498 case Bbr2Mode::DRAIN:
499 return os << "DRAIN";
500 case Bbr2Mode::PROBE_BW:
501 return os << "PROBE_BW";
502 case Bbr2Mode::PROBE_RTT:
503 return os << "PROBE_RTT";
504 }
505 return os << "<Invalid Mode>";
506 }
507
508 // The base class for all BBRv2 modes. A Bbr2Sender is in one mode at a time,
509 // this interface is used to implement mode-specific behaviors.
510 class Bbr2Sender;
511 class QUIC_EXPORT_PRIVATE Bbr2ModeBase {
512 public:
Bbr2ModeBase(const Bbr2Sender * sender,Bbr2NetworkModel * model)513 Bbr2ModeBase(const Bbr2Sender* sender, Bbr2NetworkModel* model)
514 : sender_(sender), model_(model) {}
515
516 virtual ~Bbr2ModeBase() = default;
517
518 // Called when entering/leaving this mode.
519 // congestion_event != nullptr means BBRv2 is switching modes in the context
520 // of a ack and/or loss.
521 virtual void Enter(QuicTime now,
522 const Bbr2CongestionEvent* congestion_event) = 0;
523 virtual void Leave(QuicTime now,
524 const Bbr2CongestionEvent* congestion_event) = 0;
525
526 virtual Bbr2Mode OnCongestionEvent(
527 QuicByteCount prior_in_flight,
528 QuicTime event_time,
529 const AckedPacketVector& acked_packets,
530 const LostPacketVector& lost_packets,
531 const Bbr2CongestionEvent& congestion_event) = 0;
532
533 virtual Limits<QuicByteCount> GetCwndLimits() const = 0;
534
535 virtual bool IsProbingForBandwidth() const = 0;
536
537 virtual Bbr2Mode OnExitQuiescence(QuicTime now,
538 QuicTime quiescence_start_time) = 0;
539
540 protected:
541 const Bbr2Sender* const sender_;
542 Bbr2NetworkModel* model_;
543 };
544
BytesInFlight(const SendTimeState & send_state)545 QUIC_EXPORT_PRIVATE inline QuicByteCount BytesInFlight(
546 const SendTimeState& send_state) {
547 DCHECK(send_state.is_valid);
548 if (send_state.bytes_in_flight != 0) {
549 return send_state.bytes_in_flight;
550 }
551 return send_state.total_bytes_sent - send_state.total_bytes_acked -
552 send_state.total_bytes_lost;
553 }
554
555 } // namespace quic
556
557 #endif // QUICHE_QUIC_CORE_CONGESTION_CONTROL_BBR2_MISC_H_
558