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 (old_sampler != nullptr) {
64 return BandwidthSampler(*old_sampler);
65 }
66 return BandwidthSampler(/*unacked_packet_map=*/nullptr,
67 max_height_tracker_window_length);
68 }(params->initial_max_ack_height_filter_window, old_sampler)),
69 min_rtt_filter_(initial_rtt, initial_rtt_timestamp),
70 cwnd_gain_(cwnd_gain),
71 pacing_gain_(pacing_gain) {}
72
OnPacketSent(QuicTime sent_time,QuicByteCount bytes_in_flight,QuicPacketNumber packet_number,QuicByteCount bytes,HasRetransmittableData is_retransmittable)73 void Bbr2NetworkModel::OnPacketSent(QuicTime sent_time,
74 QuicByteCount bytes_in_flight,
75 QuicPacketNumber packet_number,
76 QuicByteCount bytes,
77 HasRetransmittableData is_retransmittable) {
78 round_trip_counter_.OnPacketSent(packet_number);
79
80 bandwidth_sampler_.OnPacketSent(sent_time, packet_number, bytes,
81 bytes_in_flight, is_retransmittable);
82 }
83
OnCongestionEventStart(QuicTime event_time,const AckedPacketVector & acked_packets,const LostPacketVector & lost_packets,Bbr2CongestionEvent * congestion_event)84 void Bbr2NetworkModel::OnCongestionEventStart(
85 QuicTime event_time,
86 const AckedPacketVector& acked_packets,
87 const LostPacketVector& lost_packets,
88 Bbr2CongestionEvent* congestion_event) {
89 const QuicByteCount prior_bytes_acked = total_bytes_acked();
90 const QuicByteCount prior_bytes_lost = total_bytes_lost();
91
92 congestion_event->event_time = event_time;
93 congestion_event->end_of_round_trip =
94 acked_packets.empty() ? false
95 : round_trip_counter_.OnPacketsAcked(
96 acked_packets.rbegin()->packet_number);
97
98 BandwidthSamplerInterface::CongestionEventSample sample =
99 bandwidth_sampler_.OnCongestionEvent(event_time, acked_packets,
100 lost_packets, MaxBandwidth(),
101 bandwidth_lo(), RoundTripCount());
102
103 if (sample.last_packet_send_state.is_valid) {
104 congestion_event->last_packet_send_state = sample.last_packet_send_state;
105 congestion_event->last_sample_is_app_limited =
106 sample.last_packet_send_state.is_app_limited;
107 }
108
109 // Avoid updating |max_bandwidth_filter_| if a) this is a loss-only event, or
110 // b) all packets in |acked_packets| did not generate valid samples. (e.g. ack
111 // of ack-only packets). In both cases, total_bytes_acked() will not change.
112 if (prior_bytes_acked != total_bytes_acked()) {
113 QUIC_LOG_IF(WARNING, sample.sample_max_bandwidth.IsZero())
114 << total_bytes_acked() - prior_bytes_acked << " bytes from "
115 << acked_packets.size()
116 << " packets have been acked, but sample_max_bandwidth is zero.";
117 if (!sample.sample_is_app_limited ||
118 sample.sample_max_bandwidth > MaxBandwidth()) {
119 congestion_event->sample_max_bandwidth = sample.sample_max_bandwidth;
120 max_bandwidth_filter_.Update(congestion_event->sample_max_bandwidth);
121 }
122 }
123
124 if (!sample.sample_rtt.IsInfinite()) {
125 congestion_event->sample_min_rtt = sample.sample_rtt;
126 min_rtt_filter_.Update(congestion_event->sample_min_rtt, event_time);
127 }
128
129 congestion_event->bytes_acked = total_bytes_acked() - prior_bytes_acked;
130 congestion_event->bytes_lost = total_bytes_lost() - prior_bytes_lost;
131
132 if (congestion_event->prior_bytes_in_flight >=
133 congestion_event->bytes_acked + congestion_event->bytes_lost) {
134 congestion_event->bytes_in_flight =
135 congestion_event->prior_bytes_in_flight -
136 congestion_event->bytes_acked - congestion_event->bytes_lost;
137 } else {
138 QUIC_LOG_FIRST_N(ERROR, 1)
139 << "prior_bytes_in_flight:" << congestion_event->prior_bytes_in_flight
140 << " is smaller than the sum of bytes_acked:"
141 << congestion_event->bytes_acked
142 << " and bytes_lost:" << congestion_event->bytes_lost;
143 congestion_event->bytes_in_flight = 0;
144 }
145
146 if (congestion_event->bytes_lost > 0) {
147 bytes_lost_in_round_ += congestion_event->bytes_lost;
148 loss_events_in_round_++;
149 }
150
151 if (GetQuicReloadableFlag(quic_bbr2_startup_loss_exit_use_max_delivered) &&
152 congestion_event->bytes_acked > 0 &&
153 congestion_event->last_packet_send_state.is_valid &&
154 total_bytes_acked() >
155 congestion_event->last_packet_send_state.total_bytes_acked) {
156 QuicByteCount bytes_delivered =
157 total_bytes_acked() -
158 congestion_event->last_packet_send_state.total_bytes_acked;
159 max_bytes_delivered_in_round_ =
160 std::max(max_bytes_delivered_in_round_, bytes_delivered);
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 bandwidth_lo_ =
200 std::max(bandwidth_latest_, bandwidth_lo_ * (1.0 - Params().beta));
201 QUIC_DVLOG(3) << "bandwidth_lo_ updated to " << bandwidth_lo_
202 << ", bandwidth_latest_ is " << bandwidth_latest_;
203
204 if (Params().ignore_inflight_lo) {
205 return;
206 }
207 if (inflight_lo_ == inflight_lo_default()) {
208 inflight_lo_ = congestion_event.prior_cwnd;
209 }
210 inflight_lo_ = std::max<QuicByteCount>(
211 inflight_latest_, inflight_lo_ * (1.0 - Params().beta));
212 }
213 }
214
OnCongestionEventFinish(QuicPacketNumber least_unacked_packet,const Bbr2CongestionEvent & congestion_event)215 void Bbr2NetworkModel::OnCongestionEventFinish(
216 QuicPacketNumber least_unacked_packet,
217 const Bbr2CongestionEvent& congestion_event) {
218 if (congestion_event.end_of_round_trip) {
219 bytes_lost_in_round_ = 0;
220 loss_events_in_round_ = 0;
221 }
222
223 bandwidth_sampler_.RemoveObsoletePackets(least_unacked_packet);
224 }
225
UpdateNetworkParameters(QuicTime::Delta rtt)226 void Bbr2NetworkModel::UpdateNetworkParameters(QuicTime::Delta rtt) {
227 if (!rtt.IsZero()) {
228 min_rtt_filter_.Update(rtt, MinRttTimestamp());
229 }
230 }
231
MaybeExpireMinRtt(const Bbr2CongestionEvent & congestion_event)232 bool Bbr2NetworkModel::MaybeExpireMinRtt(
233 const Bbr2CongestionEvent& congestion_event) {
234 if (congestion_event.event_time <
235 (MinRttTimestamp() + Params().probe_rtt_period)) {
236 return false;
237 }
238 if (congestion_event.sample_min_rtt.IsInfinite()) {
239 return false;
240 }
241 QUIC_DVLOG(3) << "Replacing expired min rtt of " << min_rtt_filter_.Get()
242 << " by " << congestion_event.sample_min_rtt << " @ "
243 << congestion_event.event_time;
244 min_rtt_filter_.ForceUpdate(congestion_event.sample_min_rtt,
245 congestion_event.event_time);
246 return true;
247 }
248
IsCongestionWindowLimited(const Bbr2CongestionEvent & congestion_event) const249 bool Bbr2NetworkModel::IsCongestionWindowLimited(
250 const Bbr2CongestionEvent& congestion_event) const {
251 QuicByteCount prior_bytes_in_flight = congestion_event.bytes_in_flight +
252 congestion_event.bytes_acked +
253 congestion_event.bytes_lost;
254 return prior_bytes_in_flight >= congestion_event.prior_cwnd;
255 }
256
IsInflightTooHigh(const Bbr2CongestionEvent & congestion_event,int64_t max_loss_events) const257 bool Bbr2NetworkModel::IsInflightTooHigh(
258 const Bbr2CongestionEvent& congestion_event,
259 int64_t max_loss_events) const {
260 const SendTimeState& send_state = congestion_event.last_packet_send_state;
261 if (!send_state.is_valid) {
262 // Not enough information.
263 return false;
264 }
265
266 if (loss_events_in_round() < max_loss_events) {
267 return false;
268 }
269
270 const QuicByteCount inflight_at_send = BytesInFlight(send_state);
271 // TODO(wub): Consider total_bytes_lost() - send_state.total_bytes_lost, which
272 // is the total bytes lost when the largest numbered packet was inflight.
273 // bytes_lost_in_round_, OTOH, is the total bytes lost in the "current" round.
274 const QuicByteCount bytes_lost_in_round = bytes_lost_in_round_;
275
276 QUIC_DVLOG(3) << "IsInflightTooHigh: loss_events_in_round:"
277 << loss_events_in_round()
278
279 << " bytes_lost_in_round:" << bytes_lost_in_round
280 << ", lost_in_round_threshold:"
281 << inflight_at_send * Params().loss_threshold;
282
283 if (inflight_at_send > 0 && bytes_lost_in_round > 0) {
284 QuicByteCount lost_in_round_threshold =
285 inflight_at_send * Params().loss_threshold;
286 if (bytes_lost_in_round > lost_in_round_threshold) {
287 return true;
288 }
289 }
290
291 return false;
292 }
293
RestartRound()294 void Bbr2NetworkModel::RestartRound() {
295 bytes_lost_in_round_ = 0;
296 loss_events_in_round_ = 0;
297 if (GetQuicReloadableFlag(quic_bbr2_startup_loss_exit_use_max_delivered)) {
298 max_bytes_delivered_in_round_ = 0;
299 }
300 round_trip_counter_.RestartRound();
301 }
302
cap_inflight_lo(QuicByteCount cap)303 void Bbr2NetworkModel::cap_inflight_lo(QuicByteCount cap) {
304 if (Params().ignore_inflight_lo) {
305 return;
306 }
307 if (inflight_lo_ != inflight_lo_default() && inflight_lo_ > cap) {
308 inflight_lo_ = cap;
309 }
310 }
311
inflight_hi_with_headroom() const312 QuicByteCount Bbr2NetworkModel::inflight_hi_with_headroom() const {
313 QuicByteCount headroom = inflight_hi_ * Params().inflight_hi_headroom;
314
315 return inflight_hi_ > headroom ? inflight_hi_ - headroom : 0;
316 }
317
318 } // namespace quic
319