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
3 // found in the LICENSE file.
4
5 #include "net/third_party/quiche/src/quic/core/congestion_control/bandwidth_sampler.h"
6
7 #include <algorithm>
8
9 #include "net/third_party/quiche/src/quic/core/quic_types.h"
10 #include "net/third_party/quiche/src/quic/platform/api/quic_bug_tracker.h"
11 #include "net/third_party/quiche/src/quic/platform/api/quic_flag_utils.h"
12 #include "net/third_party/quiche/src/quic/platform/api/quic_flags.h"
13 #include "net/third_party/quiche/src/quic/platform/api/quic_logging.h"
14
15 namespace quic {
16
operator <<(std::ostream & os,const SendTimeState & s)17 std::ostream& operator<<(std::ostream& os, const SendTimeState& s) {
18 os << "{valid:" << s.is_valid << ", app_limited:" << s.is_app_limited
19 << ", total_sent:" << s.total_bytes_sent
20 << ", total_acked:" << s.total_bytes_acked
21 << ", total_lost:" << s.total_bytes_lost
22 << ", inflight:" << s.bytes_in_flight << "}";
23 return os;
24 }
25
Update(QuicBandwidth bandwidth_estimate,QuicRoundTripCount round_trip_count,QuicTime ack_time,QuicByteCount bytes_acked)26 QuicByteCount MaxAckHeightTracker::Update(QuicBandwidth bandwidth_estimate,
27 QuicRoundTripCount round_trip_count,
28 QuicTime ack_time,
29 QuicByteCount bytes_acked) {
30 if (aggregation_epoch_start_time_ == QuicTime::Zero()) {
31 aggregation_epoch_bytes_ = bytes_acked;
32 aggregation_epoch_start_time_ = ack_time;
33 ++num_ack_aggregation_epochs_;
34 return 0;
35 }
36
37 // Compute how many bytes are expected to be delivered, assuming max bandwidth
38 // is correct.
39 QuicByteCount expected_bytes_acked =
40 bandwidth_estimate * (ack_time - aggregation_epoch_start_time_);
41 // Reset the current aggregation epoch as soon as the ack arrival rate is less
42 // than or equal to the max bandwidth.
43 if (aggregation_epoch_bytes_ <=
44 ack_aggregation_bandwidth_threshold_ * expected_bytes_acked) {
45 QUIC_DVLOG(3) << "Starting a new aggregation epoch because "
46 "aggregation_epoch_bytes_ "
47 << aggregation_epoch_bytes_
48 << " is smaller than expected. "
49 "ack_aggregation_bandwidth_threshold_:"
50 << ack_aggregation_bandwidth_threshold_
51 << ", expected_bytes_acked:" << expected_bytes_acked
52 << ", bandwidth_estimate:" << bandwidth_estimate
53 << ", aggregation_duration:"
54 << (ack_time - aggregation_epoch_start_time_)
55 << ", new_aggregation_epoch:" << ack_time
56 << ", new_aggregation_bytes_acked:" << bytes_acked;
57 // Reset to start measuring a new aggregation epoch.
58 aggregation_epoch_bytes_ = bytes_acked;
59 aggregation_epoch_start_time_ = ack_time;
60 ++num_ack_aggregation_epochs_;
61 return 0;
62 }
63
64 aggregation_epoch_bytes_ += bytes_acked;
65
66 // Compute how many extra bytes were delivered vs max bandwidth.
67 QuicByteCount extra_bytes_acked =
68 aggregation_epoch_bytes_ - expected_bytes_acked;
69 QUIC_DVLOG(3) << "Updating MaxAckHeight. ack_time:" << ack_time
70 << ", round trip count:" << round_trip_count
71 << ", bandwidth_estimate:" << bandwidth_estimate
72 << ", bytes_acked:" << bytes_acked
73 << ", expected_bytes_acked:" << expected_bytes_acked
74 << ", aggregation_epoch_bytes_:" << aggregation_epoch_bytes_
75 << ", extra_bytes_acked:" << extra_bytes_acked;
76 max_ack_height_filter_.Update(extra_bytes_acked, round_trip_count);
77 return extra_bytes_acked;
78 }
79
BandwidthSampler(const QuicUnackedPacketMap * unacked_packet_map,QuicRoundTripCount max_height_tracker_window_length)80 BandwidthSampler::BandwidthSampler(
81 const QuicUnackedPacketMap* unacked_packet_map,
82 QuicRoundTripCount max_height_tracker_window_length)
83 : total_bytes_sent_(0),
84 total_bytes_acked_(0),
85 total_bytes_lost_(0),
86 total_bytes_neutered_(0),
87 total_bytes_sent_at_last_acked_packet_(0),
88 last_acked_packet_sent_time_(QuicTime::Zero()),
89 last_acked_packet_ack_time_(QuicTime::Zero()),
90 is_app_limited_(true),
91 connection_state_map_(),
92 max_tracked_packets_(GetQuicFlag(FLAGS_quic_max_tracked_packet_count)),
93 unacked_packet_map_(unacked_packet_map),
94 max_ack_height_tracker_(max_height_tracker_window_length),
95 total_bytes_acked_after_last_ack_event_(0),
96 overestimate_avoidance_(false) {}
97
BandwidthSampler(const BandwidthSampler & other)98 BandwidthSampler::BandwidthSampler(const BandwidthSampler& other)
99 : total_bytes_sent_(other.total_bytes_sent_),
100 total_bytes_acked_(other.total_bytes_acked_),
101 total_bytes_lost_(other.total_bytes_lost_),
102 total_bytes_neutered_(other.total_bytes_neutered_),
103 total_bytes_sent_at_last_acked_packet_(
104 other.total_bytes_sent_at_last_acked_packet_),
105 last_acked_packet_sent_time_(other.last_acked_packet_sent_time_),
106 last_acked_packet_ack_time_(other.last_acked_packet_ack_time_),
107 last_sent_packet_(other.last_sent_packet_),
108 is_app_limited_(other.is_app_limited_),
109 end_of_app_limited_phase_(other.end_of_app_limited_phase_),
110 connection_state_map_(other.connection_state_map_),
111 recent_ack_points_(other.recent_ack_points_),
112 a0_candidates_(other.a0_candidates_),
113 max_tracked_packets_(other.max_tracked_packets_),
114 unacked_packet_map_(other.unacked_packet_map_),
115 max_ack_height_tracker_(other.max_ack_height_tracker_),
116 total_bytes_acked_after_last_ack_event_(
117 other.total_bytes_acked_after_last_ack_event_),
118 overestimate_avoidance_(other.overestimate_avoidance_) {}
119
EnableOverestimateAvoidance()120 void BandwidthSampler::EnableOverestimateAvoidance() {
121 if (overestimate_avoidance_) {
122 return;
123 }
124
125 overestimate_avoidance_ = true;
126 // TODO(wub): Change the default value of
127 // --quic_ack_aggregation_bandwidth_threshold to 2.0.
128 max_ack_height_tracker_.SetAckAggregationBandwidthThreshold(2.0);
129 }
130
~BandwidthSampler()131 BandwidthSampler::~BandwidthSampler() {}
132
OnPacketSent(QuicTime sent_time,QuicPacketNumber packet_number,QuicByteCount bytes,QuicByteCount bytes_in_flight,HasRetransmittableData has_retransmittable_data)133 void BandwidthSampler::OnPacketSent(
134 QuicTime sent_time,
135 QuicPacketNumber packet_number,
136 QuicByteCount bytes,
137 QuicByteCount bytes_in_flight,
138 HasRetransmittableData has_retransmittable_data) {
139 last_sent_packet_ = packet_number;
140
141 if (has_retransmittable_data != HAS_RETRANSMITTABLE_DATA) {
142 return;
143 }
144
145 total_bytes_sent_ += bytes;
146
147 // If there are no packets in flight, the time at which the new transmission
148 // opens can be treated as the A_0 point for the purpose of bandwidth
149 // sampling. This underestimates bandwidth to some extent, and produces some
150 // artificially low samples for most packets in flight, but it provides with
151 // samples at important points where we would not have them otherwise, most
152 // importantly at the beginning of the connection.
153 if (bytes_in_flight == 0) {
154 last_acked_packet_ack_time_ = sent_time;
155 if (overestimate_avoidance_) {
156 recent_ack_points_.Clear();
157 recent_ack_points_.Update(sent_time, total_bytes_acked_);
158 a0_candidates_.clear();
159 a0_candidates_.push_back(recent_ack_points_.MostRecentPoint());
160 }
161 total_bytes_sent_at_last_acked_packet_ = total_bytes_sent_;
162
163 // In this situation ack compression is not a concern, set send rate to
164 // effectively infinite.
165 last_acked_packet_sent_time_ = sent_time;
166 }
167
168 if (!connection_state_map_.IsEmpty() &&
169 packet_number >
170 connection_state_map_.last_packet() + max_tracked_packets_) {
171 if (unacked_packet_map_ != nullptr) {
172 QUIC_BUG << "BandwidthSampler in-flight packet map has exceeded maximum "
173 "number of tracked packets("
174 << max_tracked_packets_
175 << "). First tracked: " << connection_state_map_.first_packet()
176 << "; last tracked: " << connection_state_map_.last_packet()
177 << "; least unacked: " << unacked_packet_map_->GetLeastUnacked()
178 << "; packet number: " << packet_number << "; largest observed: "
179 << unacked_packet_map_->largest_acked();
180 } else {
181 QUIC_BUG << "BandwidthSampler in-flight packet map has exceeded maximum "
182 "number of tracked packets.";
183 }
184 }
185
186 bool success = connection_state_map_.Emplace(packet_number, sent_time, bytes,
187 bytes_in_flight + bytes, *this);
188 QUIC_BUG_IF(!success) << "BandwidthSampler failed to insert the packet "
189 "into the map, most likely because it's already "
190 "in it.";
191 }
192
OnPacketNeutered(QuicPacketNumber packet_number)193 void BandwidthSampler::OnPacketNeutered(QuicPacketNumber packet_number) {
194 connection_state_map_.Remove(
195 packet_number, [&](const ConnectionStateOnSentPacket& sent_packet) {
196 QUIC_CODE_COUNT(quic_bandwidth_sampler_packet_neutered);
197 total_bytes_neutered_ += sent_packet.size;
198 });
199 }
200
201 BandwidthSamplerInterface::CongestionEventSample
OnCongestionEvent(QuicTime ack_time,const AckedPacketVector & acked_packets,const LostPacketVector & lost_packets,QuicBandwidth max_bandwidth,QuicBandwidth est_bandwidth_upper_bound,QuicRoundTripCount round_trip_count)202 BandwidthSampler::OnCongestionEvent(QuicTime ack_time,
203 const AckedPacketVector& acked_packets,
204 const LostPacketVector& lost_packets,
205 QuicBandwidth max_bandwidth,
206 QuicBandwidth est_bandwidth_upper_bound,
207 QuicRoundTripCount round_trip_count) {
208 CongestionEventSample event_sample;
209
210 SendTimeState last_lost_packet_send_state;
211
212 for (const LostPacket& packet : lost_packets) {
213 SendTimeState send_state =
214 OnPacketLost(packet.packet_number, packet.bytes_lost);
215 if (send_state.is_valid) {
216 last_lost_packet_send_state = send_state;
217 }
218 }
219
220 if (acked_packets.empty()) {
221 // Only populate send state for a loss-only event.
222 event_sample.last_packet_send_state = last_lost_packet_send_state;
223 return event_sample;
224 }
225
226 SendTimeState last_acked_packet_send_state;
227 for (const auto& packet : acked_packets) {
228 BandwidthSample sample =
229 OnPacketAcknowledged(ack_time, packet.packet_number);
230 if (!sample.state_at_send.is_valid) {
231 continue;
232 }
233
234 last_acked_packet_send_state = sample.state_at_send;
235
236 if (!sample.rtt.IsZero()) {
237 event_sample.sample_rtt = std::min(event_sample.sample_rtt, sample.rtt);
238 }
239 if (sample.bandwidth > event_sample.sample_max_bandwidth) {
240 event_sample.sample_max_bandwidth = sample.bandwidth;
241 event_sample.sample_is_app_limited = sample.state_at_send.is_app_limited;
242 }
243 const QuicByteCount inflight_sample =
244 total_bytes_acked() - last_acked_packet_send_state.total_bytes_acked;
245 if (inflight_sample > event_sample.sample_max_inflight) {
246 event_sample.sample_max_inflight = inflight_sample;
247 }
248 }
249
250 if (!last_lost_packet_send_state.is_valid) {
251 event_sample.last_packet_send_state = last_acked_packet_send_state;
252 } else if (!last_acked_packet_send_state.is_valid) {
253 event_sample.last_packet_send_state = last_lost_packet_send_state;
254 } else {
255 // If two packets are inflight and an alarm is armed to lose a packet and it
256 // wakes up late, then the first of two in flight packets could have been
257 // acknowledged before the wakeup, which re-evaluates loss detection, and
258 // could declare the later of the two lost.
259 event_sample.last_packet_send_state =
260 lost_packets.back().packet_number > acked_packets.back().packet_number
261 ? last_lost_packet_send_state
262 : last_acked_packet_send_state;
263 }
264
265 max_bandwidth = std::max(max_bandwidth, event_sample.sample_max_bandwidth);
266 event_sample.extra_acked = OnAckEventEnd(
267 std::min(est_bandwidth_upper_bound, max_bandwidth), round_trip_count);
268
269 return event_sample;
270 }
271
OnAckEventEnd(QuicBandwidth bandwidth_estimate,QuicRoundTripCount round_trip_count)272 QuicByteCount BandwidthSampler::OnAckEventEnd(
273 QuicBandwidth bandwidth_estimate,
274 QuicRoundTripCount round_trip_count) {
275 const QuicByteCount newly_acked_bytes =
276 total_bytes_acked_ - total_bytes_acked_after_last_ack_event_;
277
278 if (newly_acked_bytes == 0) {
279 return 0;
280 }
281 total_bytes_acked_after_last_ack_event_ = total_bytes_acked_;
282
283 QuicByteCount extra_acked = max_ack_height_tracker_.Update(
284 bandwidth_estimate, round_trip_count, last_acked_packet_ack_time_,
285 newly_acked_bytes);
286 // If |extra_acked| is zero, i.e. this ack event marks the start of a new ack
287 // aggregation epoch, save LessRecentPoint, which is the last ack point of the
288 // previous epoch, as a A0 candidate.
289 if (overestimate_avoidance_ && extra_acked == 0) {
290 a0_candidates_.push_back(recent_ack_points_.LessRecentPoint());
291 QUIC_DVLOG(1) << "New a0_candidate:" << a0_candidates_.back();
292 }
293 return extra_acked;
294 }
295
OnPacketAcknowledged(QuicTime ack_time,QuicPacketNumber packet_number)296 BandwidthSample BandwidthSampler::OnPacketAcknowledged(
297 QuicTime ack_time,
298 QuicPacketNumber packet_number) {
299 ConnectionStateOnSentPacket* sent_packet_pointer =
300 connection_state_map_.GetEntry(packet_number);
301 if (sent_packet_pointer == nullptr) {
302 // See the TODO below.
303 return BandwidthSample();
304 }
305 BandwidthSample sample =
306 OnPacketAcknowledgedInner(ack_time, packet_number, *sent_packet_pointer);
307 return sample;
308 }
309
OnPacketAcknowledgedInner(QuicTime ack_time,QuicPacketNumber packet_number,const ConnectionStateOnSentPacket & sent_packet)310 BandwidthSample BandwidthSampler::OnPacketAcknowledgedInner(
311 QuicTime ack_time,
312 QuicPacketNumber packet_number,
313 const ConnectionStateOnSentPacket& sent_packet) {
314 total_bytes_acked_ += sent_packet.size;
315 total_bytes_sent_at_last_acked_packet_ =
316 sent_packet.send_time_state.total_bytes_sent;
317 last_acked_packet_sent_time_ = sent_packet.sent_time;
318 last_acked_packet_ack_time_ = ack_time;
319 if (overestimate_avoidance_) {
320 recent_ack_points_.Update(ack_time, total_bytes_acked_);
321 }
322
323 if (is_app_limited_) {
324 // Exit app-limited phase in two cases:
325 // (1) end_of_app_limited_phase_ is not initialized, i.e., so far all
326 // packets are sent while there are buffered packets or pending data.
327 // (2) The current acked packet is after the sent packet marked as the end
328 // of the app limit phase.
329 if (!end_of_app_limited_phase_.IsInitialized() ||
330 packet_number > end_of_app_limited_phase_) {
331 is_app_limited_ = false;
332 }
333 }
334
335 // There might have been no packets acknowledged at the moment when the
336 // current packet was sent. In that case, there is no bandwidth sample to
337 // make.
338 if (sent_packet.last_acked_packet_sent_time == QuicTime::Zero()) {
339 QUIC_BUG << "sent_packet.last_acked_packet_sent_time is zero";
340 return BandwidthSample();
341 }
342
343 // Infinite rate indicates that the sampler is supposed to discard the
344 // current send rate sample and use only the ack rate.
345 QuicBandwidth send_rate = QuicBandwidth::Infinite();
346 if (sent_packet.sent_time > sent_packet.last_acked_packet_sent_time) {
347 send_rate = QuicBandwidth::FromBytesAndTimeDelta(
348 sent_packet.send_time_state.total_bytes_sent -
349 sent_packet.total_bytes_sent_at_last_acked_packet,
350 sent_packet.sent_time - sent_packet.last_acked_packet_sent_time);
351 }
352
353 AckPoint a0;
354 if (overestimate_avoidance_ &&
355 ChooseA0Point(sent_packet.send_time_state.total_bytes_acked, &a0)) {
356 QUIC_DVLOG(2) << "Using a0 point: " << a0;
357 } else {
358 a0.ack_time = sent_packet.last_acked_packet_ack_time,
359 a0.total_bytes_acked = sent_packet.send_time_state.total_bytes_acked;
360 }
361
362 // During the slope calculation, ensure that ack time of the current packet is
363 // always larger than the time of the previous packet, otherwise division by
364 // zero or integer underflow can occur.
365 if (ack_time <= a0.ack_time) {
366 // TODO(wub): Compare this code count before and after fixing clock jitter
367 // issue.
368 if (a0.ack_time == sent_packet.sent_time) {
369 // This is the 1st packet after quiescense.
370 QUIC_CODE_COUNT_N(quic_prev_ack_time_larger_than_current_ack_time, 1, 2);
371 } else {
372 QUIC_CODE_COUNT_N(quic_prev_ack_time_larger_than_current_ack_time, 2, 2);
373 }
374 QUIC_LOG_EVERY_N_SEC(ERROR, 60)
375 << "Time of the previously acked packet:"
376 << a0.ack_time.ToDebuggingValue()
377 << " is larger than the ack time of the current packet:"
378 << ack_time.ToDebuggingValue()
379 << ". acked packet number:" << packet_number
380 << ", total_bytes_acked_:" << total_bytes_acked_
381 << ", overestimate_avoidance_:" << overestimate_avoidance_
382 << ", sent_packet:" << sent_packet;
383 return BandwidthSample();
384 }
385 QuicBandwidth ack_rate = QuicBandwidth::FromBytesAndTimeDelta(
386 total_bytes_acked_ - a0.total_bytes_acked, ack_time - a0.ack_time);
387
388 BandwidthSample sample;
389 sample.bandwidth = std::min(send_rate, ack_rate);
390 // Note: this sample does not account for delayed acknowledgement time. This
391 // means that the RTT measurements here can be artificially high, especially
392 // on low bandwidth connections.
393 sample.rtt = ack_time - sent_packet.sent_time;
394 SentPacketToSendTimeState(sent_packet, &sample.state_at_send);
395
396 if (sample.bandwidth.IsZero()) {
397 QUIC_LOG_EVERY_N_SEC(ERROR, 60)
398 << "ack_rate: " << ack_rate << ", send_rate: " << send_rate
399 << ". acked packet number:" << packet_number
400 << ", overestimate_avoidance_:" << overestimate_avoidance_ << "a1:{"
401 << total_bytes_acked_ << "@" << ack_time << "}, a0:{"
402 << a0.total_bytes_acked << "@" << a0.ack_time
403 << "}, sent_packet:" << sent_packet;
404 }
405 return sample;
406 }
407
ChooseA0Point(QuicByteCount total_bytes_acked,AckPoint * a0)408 bool BandwidthSampler::ChooseA0Point(QuicByteCount total_bytes_acked,
409 AckPoint* a0) {
410 if (a0_candidates_.empty()) {
411 QUIC_BUG << "No A0 point candicates. total_bytes_acked:"
412 << total_bytes_acked;
413 return false;
414 }
415
416 if (a0_candidates_.size() == 1) {
417 *a0 = a0_candidates_.front();
418 return true;
419 }
420
421 for (size_t i = 1; i < a0_candidates_.size(); ++i) {
422 if (a0_candidates_[i].total_bytes_acked > total_bytes_acked) {
423 *a0 = a0_candidates_[i - 1];
424 if (i > 1) {
425 a0_candidates_.pop_front_n(i - 1);
426 }
427 return true;
428 }
429 }
430
431 // All candidates' total_bytes_acked is <= |total_bytes_acked|.
432 *a0 = a0_candidates_.back();
433 a0_candidates_.pop_front_n(a0_candidates_.size() - 1);
434 return true;
435 }
436
OnPacketLost(QuicPacketNumber packet_number,QuicPacketLength bytes_lost)437 SendTimeState BandwidthSampler::OnPacketLost(QuicPacketNumber packet_number,
438 QuicPacketLength bytes_lost) {
439 // TODO(vasilvv): see the comment for the case of missing packets in
440 // BandwidthSampler::OnPacketAcknowledged on why this does not raise a
441 // QUIC_BUG when removal fails.
442 SendTimeState send_time_state;
443
444 total_bytes_lost_ += bytes_lost;
445 ConnectionStateOnSentPacket* sent_packet_pointer =
446 connection_state_map_.GetEntry(packet_number);
447 if (sent_packet_pointer != nullptr) {
448 SentPacketToSendTimeState(*sent_packet_pointer, &send_time_state);
449 }
450
451 return send_time_state;
452 }
453
SentPacketToSendTimeState(const ConnectionStateOnSentPacket & sent_packet,SendTimeState * send_time_state) const454 void BandwidthSampler::SentPacketToSendTimeState(
455 const ConnectionStateOnSentPacket& sent_packet,
456 SendTimeState* send_time_state) const {
457 *send_time_state = sent_packet.send_time_state;
458 send_time_state->is_valid = true;
459 }
460
OnAppLimited()461 void BandwidthSampler::OnAppLimited() {
462 is_app_limited_ = true;
463 end_of_app_limited_phase_ = last_sent_packet_;
464 }
465
RemoveObsoletePackets(QuicPacketNumber least_unacked)466 void BandwidthSampler::RemoveObsoletePackets(QuicPacketNumber least_unacked) {
467 // A packet can become obsolete when it is removed from QuicUnackedPacketMap's
468 // view of inflight before it is acked or marked as lost. For example, when
469 // QuicSentPacketManager::RetransmitCryptoPackets retransmits a crypto packet,
470 // the packet is removed from QuicUnackedPacketMap's inflight, but is not
471 // marked as acked or lost in the BandwidthSampler.
472 connection_state_map_.RemoveUpTo(least_unacked);
473 }
474
total_bytes_sent() const475 QuicByteCount BandwidthSampler::total_bytes_sent() const {
476 return total_bytes_sent_;
477 }
478
total_bytes_acked() const479 QuicByteCount BandwidthSampler::total_bytes_acked() const {
480 return total_bytes_acked_;
481 }
482
total_bytes_lost() const483 QuicByteCount BandwidthSampler::total_bytes_lost() const {
484 return total_bytes_lost_;
485 }
486
total_bytes_neutered() const487 QuicByteCount BandwidthSampler::total_bytes_neutered() const {
488 return total_bytes_neutered_;
489 }
490
is_app_limited() const491 bool BandwidthSampler::is_app_limited() const {
492 return is_app_limited_;
493 }
494
end_of_app_limited_phase() const495 QuicPacketNumber BandwidthSampler::end_of_app_limited_phase() const {
496 return end_of_app_limited_phase_;
497 }
498
499 } // namespace quic
500