blob: babb6e35f0a274feae89113f4410a6f7ce8d5b7a [file] [log] [blame]
// Copyright 2016 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "quic/core/congestion_control/bandwidth_sampler.h"
#include <algorithm>
#include "quic/core/quic_types.h"
#include "quic/platform/api/quic_bug_tracker.h"
#include "quic/platform/api/quic_flag_utils.h"
#include "quic/platform/api/quic_flags.h"
#include "quic/platform/api/quic_logging.h"
namespace quic {
std::ostream& operator<<(std::ostream& os, const SendTimeState& s) {
os << "{valid:" << s.is_valid << ", app_limited:" << s.is_app_limited
<< ", total_sent:" << s.total_bytes_sent
<< ", total_acked:" << s.total_bytes_acked
<< ", total_lost:" << s.total_bytes_lost
<< ", inflight:" << s.bytes_in_flight << "}";
return os;
}
QuicByteCount MaxAckHeightTracker::Update(QuicBandwidth bandwidth_estimate,
QuicRoundTripCount round_trip_count,
QuicTime ack_time,
QuicByteCount bytes_acked) {
if (aggregation_epoch_start_time_ == QuicTime::Zero()) {
aggregation_epoch_bytes_ = bytes_acked;
aggregation_epoch_start_time_ = ack_time;
++num_ack_aggregation_epochs_;
return 0;
}
// Compute how many bytes are expected to be delivered, assuming max bandwidth
// is correct.
QuicByteCount expected_bytes_acked =
bandwidth_estimate * (ack_time - aggregation_epoch_start_time_);
// Reset the current aggregation epoch as soon as the ack arrival rate is less
// than or equal to the max bandwidth.
if (aggregation_epoch_bytes_ <=
ack_aggregation_bandwidth_threshold_ * expected_bytes_acked) {
QUIC_DVLOG(3) << "Starting a new aggregation epoch because "
"aggregation_epoch_bytes_ "
<< aggregation_epoch_bytes_
<< " is smaller than expected. "
"ack_aggregation_bandwidth_threshold_:"
<< ack_aggregation_bandwidth_threshold_
<< ", expected_bytes_acked:" << expected_bytes_acked
<< ", bandwidth_estimate:" << bandwidth_estimate
<< ", aggregation_duration:"
<< (ack_time - aggregation_epoch_start_time_)
<< ", new_aggregation_epoch:" << ack_time
<< ", new_aggregation_bytes_acked:" << bytes_acked;
// Reset to start measuring a new aggregation epoch.
aggregation_epoch_bytes_ = bytes_acked;
aggregation_epoch_start_time_ = ack_time;
++num_ack_aggregation_epochs_;
return 0;
}
aggregation_epoch_bytes_ += bytes_acked;
// Compute how many extra bytes were delivered vs max bandwidth.
QuicByteCount extra_bytes_acked =
aggregation_epoch_bytes_ - expected_bytes_acked;
QUIC_DVLOG(3) << "Updating MaxAckHeight. ack_time:" << ack_time
<< ", round trip count:" << round_trip_count
<< ", bandwidth_estimate:" << bandwidth_estimate
<< ", bytes_acked:" << bytes_acked
<< ", expected_bytes_acked:" << expected_bytes_acked
<< ", aggregation_epoch_bytes_:" << aggregation_epoch_bytes_
<< ", extra_bytes_acked:" << extra_bytes_acked;
max_ack_height_filter_.Update(extra_bytes_acked, round_trip_count);
return extra_bytes_acked;
}
BandwidthSampler::BandwidthSampler(
const QuicUnackedPacketMap* unacked_packet_map,
QuicRoundTripCount max_height_tracker_window_length)
: total_bytes_sent_(0),
total_bytes_acked_(0),
total_bytes_lost_(0),
total_bytes_neutered_(0),
total_bytes_sent_at_last_acked_packet_(0),
last_acked_packet_sent_time_(QuicTime::Zero()),
last_acked_packet_ack_time_(QuicTime::Zero()),
is_app_limited_(true),
connection_state_map_(),
max_tracked_packets_(GetQuicFlag(FLAGS_quic_max_tracked_packet_count)),
unacked_packet_map_(unacked_packet_map),
max_ack_height_tracker_(max_height_tracker_window_length),
total_bytes_acked_after_last_ack_event_(0),
overestimate_avoidance_(false) {}
BandwidthSampler::BandwidthSampler(const BandwidthSampler& other)
: total_bytes_sent_(other.total_bytes_sent_),
total_bytes_acked_(other.total_bytes_acked_),
total_bytes_lost_(other.total_bytes_lost_),
total_bytes_neutered_(other.total_bytes_neutered_),
total_bytes_sent_at_last_acked_packet_(
other.total_bytes_sent_at_last_acked_packet_),
last_acked_packet_sent_time_(other.last_acked_packet_sent_time_),
last_acked_packet_ack_time_(other.last_acked_packet_ack_time_),
last_sent_packet_(other.last_sent_packet_),
is_app_limited_(other.is_app_limited_),
end_of_app_limited_phase_(other.end_of_app_limited_phase_),
connection_state_map_(other.connection_state_map_),
recent_ack_points_(other.recent_ack_points_),
a0_candidates_(other.a0_candidates_),
max_tracked_packets_(other.max_tracked_packets_),
unacked_packet_map_(other.unacked_packet_map_),
max_ack_height_tracker_(other.max_ack_height_tracker_),
total_bytes_acked_after_last_ack_event_(
other.total_bytes_acked_after_last_ack_event_),
overestimate_avoidance_(other.overestimate_avoidance_) {}
void BandwidthSampler::EnableOverestimateAvoidance() {
if (overestimate_avoidance_) {
return;
}
overestimate_avoidance_ = true;
// TODO(wub): Change the default value of
// --quic_ack_aggregation_bandwidth_threshold to 2.0.
max_ack_height_tracker_.SetAckAggregationBandwidthThreshold(2.0);
}
BandwidthSampler::~BandwidthSampler() {}
void BandwidthSampler::OnPacketSent(
QuicTime sent_time,
QuicPacketNumber packet_number,
QuicByteCount bytes,
QuicByteCount bytes_in_flight,
HasRetransmittableData has_retransmittable_data) {
last_sent_packet_ = packet_number;
if (has_retransmittable_data != HAS_RETRANSMITTABLE_DATA) {
return;
}
total_bytes_sent_ += bytes;
// If there are no packets in flight, the time at which the new transmission
// opens can be treated as the A_0 point for the purpose of bandwidth
// sampling. This underestimates bandwidth to some extent, and produces some
// artificially low samples for most packets in flight, but it provides with
// samples at important points where we would not have them otherwise, most
// importantly at the beginning of the connection.
if (bytes_in_flight == 0) {
last_acked_packet_ack_time_ = sent_time;
if (overestimate_avoidance_) {
recent_ack_points_.Clear();
recent_ack_points_.Update(sent_time, total_bytes_acked_);
a0_candidates_.clear();
a0_candidates_.push_back(recent_ack_points_.MostRecentPoint());
}
total_bytes_sent_at_last_acked_packet_ = total_bytes_sent_;
// In this situation ack compression is not a concern, set send rate to
// effectively infinite.
last_acked_packet_sent_time_ = sent_time;
}
if (!connection_state_map_.IsEmpty() &&
packet_number >
connection_state_map_.last_packet() + max_tracked_packets_) {
if (unacked_packet_map_ != nullptr && !unacked_packet_map_->empty()) {
QuicPacketNumber maybe_least_unacked =
unacked_packet_map_->GetLeastUnacked();
QUIC_BUG << "BandwidthSampler in-flight packet map has exceeded maximum "
"number of tracked packets("
<< max_tracked_packets_
<< "). First tracked: " << connection_state_map_.first_packet()
<< "; last tracked: " << connection_state_map_.last_packet()
<< "; entry_slots_used: "
<< connection_state_map_.entry_slots_used()
<< "; number_of_present_entries: "
<< connection_state_map_.number_of_present_entries()
<< "; packet number: " << packet_number
<< "; unacked_map: " << unacked_packet_map_->DebugString()
<< "; total_bytes_sent: " << total_bytes_sent_
<< "; total_bytes_acked: " << total_bytes_acked_
<< "; total_bytes_lost: " << total_bytes_lost_
<< "; total_bytes_neutered: " << total_bytes_neutered_
<< "; last_acked_packet_sent_time: "
<< last_acked_packet_sent_time_
<< "; total_bytes_sent_at_last_acked_packet: "
<< total_bytes_sent_at_last_acked_packet_
<< "; least_unacked_packet_info: "
<< (unacked_packet_map_->IsUnacked(maybe_least_unacked)
? unacked_packet_map_
->GetTransmissionInfo(maybe_least_unacked)
.DebugString()
: "n/a");
} else {
QUIC_BUG << "BandwidthSampler in-flight packet map has exceeded maximum "
"number of tracked packets.";
}
}
bool success = connection_state_map_.Emplace(packet_number, sent_time, bytes,
bytes_in_flight + bytes, *this);
QUIC_BUG_IF(!success) << "BandwidthSampler failed to insert the packet "
"into the map, most likely because it's already "
"in it.";
}
void BandwidthSampler::OnPacketNeutered(QuicPacketNumber packet_number) {
connection_state_map_.Remove(
packet_number, [&](const ConnectionStateOnSentPacket& sent_packet) {
QUIC_CODE_COUNT(quic_bandwidth_sampler_packet_neutered);
total_bytes_neutered_ += sent_packet.size;
});
}
BandwidthSamplerInterface::CongestionEventSample
BandwidthSampler::OnCongestionEvent(QuicTime ack_time,
const AckedPacketVector& acked_packets,
const LostPacketVector& lost_packets,
QuicBandwidth max_bandwidth,
QuicBandwidth est_bandwidth_upper_bound,
QuicRoundTripCount round_trip_count) {
CongestionEventSample event_sample;
SendTimeState last_lost_packet_send_state;
for (const LostPacket& packet : lost_packets) {
SendTimeState send_state =
OnPacketLost(packet.packet_number, packet.bytes_lost);
if (send_state.is_valid) {
last_lost_packet_send_state = send_state;
}
}
if (acked_packets.empty()) {
// Only populate send state for a loss-only event.
event_sample.last_packet_send_state = last_lost_packet_send_state;
return event_sample;
}
SendTimeState last_acked_packet_send_state;
for (const auto& packet : acked_packets) {
BandwidthSample sample =
OnPacketAcknowledged(ack_time, packet.packet_number);
if (!sample.state_at_send.is_valid) {
continue;
}
last_acked_packet_send_state = sample.state_at_send;
if (!sample.rtt.IsZero()) {
event_sample.sample_rtt = std::min(event_sample.sample_rtt, sample.rtt);
}
if (sample.bandwidth > event_sample.sample_max_bandwidth) {
event_sample.sample_max_bandwidth = sample.bandwidth;
event_sample.sample_is_app_limited = sample.state_at_send.is_app_limited;
}
const QuicByteCount inflight_sample =
total_bytes_acked() - last_acked_packet_send_state.total_bytes_acked;
if (inflight_sample > event_sample.sample_max_inflight) {
event_sample.sample_max_inflight = inflight_sample;
}
}
if (!last_lost_packet_send_state.is_valid) {
event_sample.last_packet_send_state = last_acked_packet_send_state;
} else if (!last_acked_packet_send_state.is_valid) {
event_sample.last_packet_send_state = last_lost_packet_send_state;
} else {
// If two packets are inflight and an alarm is armed to lose a packet and it
// wakes up late, then the first of two in flight packets could have been
// acknowledged before the wakeup, which re-evaluates loss detection, and
// could declare the later of the two lost.
event_sample.last_packet_send_state =
lost_packets.back().packet_number > acked_packets.back().packet_number
? last_lost_packet_send_state
: last_acked_packet_send_state;
}
max_bandwidth = std::max(max_bandwidth, event_sample.sample_max_bandwidth);
event_sample.extra_acked = OnAckEventEnd(
std::min(est_bandwidth_upper_bound, max_bandwidth), round_trip_count);
return event_sample;
}
QuicByteCount BandwidthSampler::OnAckEventEnd(
QuicBandwidth bandwidth_estimate,
QuicRoundTripCount round_trip_count) {
const QuicByteCount newly_acked_bytes =
total_bytes_acked_ - total_bytes_acked_after_last_ack_event_;
if (newly_acked_bytes == 0) {
return 0;
}
total_bytes_acked_after_last_ack_event_ = total_bytes_acked_;
QuicByteCount extra_acked = max_ack_height_tracker_.Update(
bandwidth_estimate, round_trip_count, last_acked_packet_ack_time_,
newly_acked_bytes);
// If |extra_acked| is zero, i.e. this ack event marks the start of a new ack
// aggregation epoch, save LessRecentPoint, which is the last ack point of the
// previous epoch, as a A0 candidate.
if (overestimate_avoidance_ && extra_acked == 0) {
a0_candidates_.push_back(recent_ack_points_.LessRecentPoint());
QUIC_DVLOG(1) << "New a0_candidate:" << a0_candidates_.back();
}
return extra_acked;
}
BandwidthSample BandwidthSampler::OnPacketAcknowledged(
QuicTime ack_time,
QuicPacketNumber packet_number) {
ConnectionStateOnSentPacket* sent_packet_pointer =
connection_state_map_.GetEntry(packet_number);
if (sent_packet_pointer == nullptr) {
// See the TODO below.
return BandwidthSample();
}
BandwidthSample sample =
OnPacketAcknowledgedInner(ack_time, packet_number, *sent_packet_pointer);
return sample;
}
BandwidthSample BandwidthSampler::OnPacketAcknowledgedInner(
QuicTime ack_time,
QuicPacketNumber packet_number,
const ConnectionStateOnSentPacket& sent_packet) {
total_bytes_acked_ += sent_packet.size;
total_bytes_sent_at_last_acked_packet_ =
sent_packet.send_time_state.total_bytes_sent;
last_acked_packet_sent_time_ = sent_packet.sent_time;
last_acked_packet_ack_time_ = ack_time;
if (overestimate_avoidance_) {
recent_ack_points_.Update(ack_time, total_bytes_acked_);
}
if (is_app_limited_) {
// Exit app-limited phase in two cases:
// (1) end_of_app_limited_phase_ is not initialized, i.e., so far all
// packets are sent while there are buffered packets or pending data.
// (2) The current acked packet is after the sent packet marked as the end
// of the app limit phase.
if (!end_of_app_limited_phase_.IsInitialized() ||
packet_number > end_of_app_limited_phase_) {
is_app_limited_ = false;
}
}
// There might have been no packets acknowledged at the moment when the
// current packet was sent. In that case, there is no bandwidth sample to
// make.
if (sent_packet.last_acked_packet_sent_time == QuicTime::Zero()) {
QUIC_BUG << "sent_packet.last_acked_packet_sent_time is zero";
return BandwidthSample();
}
// Infinite rate indicates that the sampler is supposed to discard the
// current send rate sample and use only the ack rate.
QuicBandwidth send_rate = QuicBandwidth::Infinite();
if (sent_packet.sent_time > sent_packet.last_acked_packet_sent_time) {
send_rate = QuicBandwidth::FromBytesAndTimeDelta(
sent_packet.send_time_state.total_bytes_sent -
sent_packet.total_bytes_sent_at_last_acked_packet,
sent_packet.sent_time - sent_packet.last_acked_packet_sent_time);
}
AckPoint a0;
if (overestimate_avoidance_ &&
ChooseA0Point(sent_packet.send_time_state.total_bytes_acked, &a0)) {
QUIC_DVLOG(2) << "Using a0 point: " << a0;
} else {
a0.ack_time = sent_packet.last_acked_packet_ack_time,
a0.total_bytes_acked = sent_packet.send_time_state.total_bytes_acked;
}
// During the slope calculation, ensure that ack time of the current packet is
// always larger than the time of the previous packet, otherwise division by
// zero or integer underflow can occur.
if (ack_time <= a0.ack_time) {
// TODO(wub): Compare this code count before and after fixing clock jitter
// issue.
if (a0.ack_time == sent_packet.sent_time) {
// This is the 1st packet after quiescense.
QUIC_CODE_COUNT_N(quic_prev_ack_time_larger_than_current_ack_time, 1, 2);
} else {
QUIC_CODE_COUNT_N(quic_prev_ack_time_larger_than_current_ack_time, 2, 2);
}
QUIC_LOG_EVERY_N_SEC(ERROR, 60)
<< "Time of the previously acked packet:"
<< a0.ack_time.ToDebuggingValue()
<< " is larger than the ack time of the current packet:"
<< ack_time.ToDebuggingValue()
<< ". acked packet number:" << packet_number
<< ", total_bytes_acked_:" << total_bytes_acked_
<< ", overestimate_avoidance_:" << overestimate_avoidance_
<< ", sent_packet:" << sent_packet;
return BandwidthSample();
}
QuicBandwidth ack_rate = QuicBandwidth::FromBytesAndTimeDelta(
total_bytes_acked_ - a0.total_bytes_acked, ack_time - a0.ack_time);
BandwidthSample sample;
sample.bandwidth = std::min(send_rate, ack_rate);
// Note: this sample does not account for delayed acknowledgement time. This
// means that the RTT measurements here can be artificially high, especially
// on low bandwidth connections.
sample.rtt = ack_time - sent_packet.sent_time;
SentPacketToSendTimeState(sent_packet, &sample.state_at_send);
if (sample.bandwidth.IsZero()) {
QUIC_LOG_EVERY_N_SEC(ERROR, 60)
<< "ack_rate: " << ack_rate << ", send_rate: " << send_rate
<< ". acked packet number:" << packet_number
<< ", overestimate_avoidance_:" << overestimate_avoidance_ << "a1:{"
<< total_bytes_acked_ << "@" << ack_time << "}, a0:{"
<< a0.total_bytes_acked << "@" << a0.ack_time
<< "}, sent_packet:" << sent_packet;
}
return sample;
}
bool BandwidthSampler::ChooseA0Point(QuicByteCount total_bytes_acked,
AckPoint* a0) {
if (a0_candidates_.empty()) {
QUIC_BUG << "No A0 point candicates. total_bytes_acked:"
<< total_bytes_acked;
return false;
}
if (a0_candidates_.size() == 1) {
*a0 = a0_candidates_.front();
return true;
}
for (size_t i = 1; i < a0_candidates_.size(); ++i) {
if (a0_candidates_[i].total_bytes_acked > total_bytes_acked) {
*a0 = a0_candidates_[i - 1];
if (i > 1) {
a0_candidates_.pop_front_n(i - 1);
}
return true;
}
}
// All candidates' total_bytes_acked is <= |total_bytes_acked|.
*a0 = a0_candidates_.back();
a0_candidates_.pop_front_n(a0_candidates_.size() - 1);
return true;
}
SendTimeState BandwidthSampler::OnPacketLost(QuicPacketNumber packet_number,
QuicPacketLength bytes_lost) {
// TODO(vasilvv): see the comment for the case of missing packets in
// BandwidthSampler::OnPacketAcknowledged on why this does not raise a
// QUIC_BUG when removal fails.
SendTimeState send_time_state;
total_bytes_lost_ += bytes_lost;
ConnectionStateOnSentPacket* sent_packet_pointer =
connection_state_map_.GetEntry(packet_number);
if (sent_packet_pointer != nullptr) {
SentPacketToSendTimeState(*sent_packet_pointer, &send_time_state);
}
return send_time_state;
}
void BandwidthSampler::SentPacketToSendTimeState(
const ConnectionStateOnSentPacket& sent_packet,
SendTimeState* send_time_state) const {
*send_time_state = sent_packet.send_time_state;
send_time_state->is_valid = true;
}
void BandwidthSampler::OnAppLimited() {
is_app_limited_ = true;
end_of_app_limited_phase_ = last_sent_packet_;
}
void BandwidthSampler::RemoveObsoletePackets(QuicPacketNumber least_unacked) {
// A packet can become obsolete when it is removed from QuicUnackedPacketMap's
// view of inflight before it is acked or marked as lost. For example, when
// QuicSentPacketManager::RetransmitCryptoPackets retransmits a crypto packet,
// the packet is removed from QuicUnackedPacketMap's inflight, but is not
// marked as acked or lost in the BandwidthSampler.
connection_state_map_.RemoveUpTo(least_unacked);
}
QuicByteCount BandwidthSampler::total_bytes_sent() const {
return total_bytes_sent_;
}
QuicByteCount BandwidthSampler::total_bytes_acked() const {
return total_bytes_acked_;
}
QuicByteCount BandwidthSampler::total_bytes_lost() const {
return total_bytes_lost_;
}
QuicByteCount BandwidthSampler::total_bytes_neutered() const {
return total_bytes_neutered_;
}
bool BandwidthSampler::is_app_limited() const {
return is_app_limited_;
}
QuicPacketNumber BandwidthSampler::end_of_app_limited_phase() const {
return end_of_app_limited_phase_;
}
} // namespace quic