Adds BandwidthSampler for BBR.
This prepares for making the BBR implementation more identical to the
implementation in Quic, this is to ensure that results are comparable.
Bug: webrtc:8415
Change-Id: Ic2dc4394dc9923e5109ffa5f146c23b527f0c395
Reviewed-on: https://webrtc-review.googlesource.com/76582
Commit-Queue: Sebastian Jansson <srte@webrtc.org>
Reviewed-by: Björn Terelius <terelius@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#23262}diff --git a/modules/congestion_controller/bbr/BUILD.gn b/modules/congestion_controller/bbr/BUILD.gn
index fa0bdbf..7c4ad21 100644
--- a/modules/congestion_controller/bbr/BUILD.gn
+++ b/modules/congestion_controller/bbr/BUILD.gn
@@ -38,6 +38,25 @@
"../../../rtc_base/system:fallthrough",
]
}
+
+rtc_source_set("bandwidth_sampler") {
+ visibility = [ ":*" ]
+ sources = [
+ "bandwidth_sampler.cc",
+ "bandwidth_sampler.h",
+ ]
+ deps = [
+ ":packet_number_indexed_queue",
+ "../../../api:optional",
+ "../../../api/units:data_rate",
+ "../../../api/units:data_size",
+ "../../../api/units:time_delta",
+ "../../../api/units:timestamp",
+ "../../../rtc_base:checks",
+ "../../../rtc_base:rtc_base_approved",
+ ]
+}
+
rtc_source_set("data_transfer_tracker") {
visibility = [ ":*" ]
sources = [
@@ -85,6 +104,7 @@
rtc_source_set("bbr_unittests") {
testonly = true
sources = [
+ "bandwidth_sampler_unittest.cc",
"bbr_network_controller_unittest.cc",
"data_transfer_tracker_unittest.cc",
"packet_number_indexed_queue_unittest.cc",
@@ -92,6 +112,7 @@
"windowed_filter_unittest.cc",
]
deps = [
+ ":bandwidth_sampler",
":bbr",
":bbr_controller",
":data_transfer_tracker",
diff --git a/modules/congestion_controller/bbr/bandwidth_sampler.cc b/modules/congestion_controller/bbr/bandwidth_sampler.cc
new file mode 100644
index 0000000..b9e2c27
--- /dev/null
+++ b/modules/congestion_controller/bbr/bandwidth_sampler.cc
@@ -0,0 +1,204 @@
+/*
+ * Copyright (c) 2018 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+// Based on the Quic implementation in Chromium.
+
+#include <algorithm>
+
+#include "modules/congestion_controller/bbr/bandwidth_sampler.h"
+#include "rtc_base/logging.h"
+
+namespace webrtc {
+namespace bbr {
+namespace {
+constexpr int64_t kMaxTrackedPackets = 10000;
+}
+
+BandwidthSampler::BandwidthSampler()
+ : total_data_sent_(DataSize::Zero()),
+ total_data_acked_(DataSize::Zero()),
+ total_data_sent_at_last_acked_packet_(DataSize::Zero()),
+ last_acked_packet_sent_time_(),
+ last_acked_packet_ack_time_(),
+ last_sent_packet_(0),
+ is_app_limited_(false),
+ end_of_app_limited_phase_(0),
+ connection_state_map_() {}
+
+BandwidthSampler::~BandwidthSampler() {}
+
+void BandwidthSampler::OnPacketSent(Timestamp sent_time,
+ int64_t packet_number,
+ DataSize data_size,
+ DataSize data_in_flight) {
+ last_sent_packet_ = packet_number;
+
+ total_data_sent_ += data_size;
+
+ // 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 (data_in_flight.IsZero()) {
+ last_acked_packet_ack_time_ = sent_time;
+ total_data_sent_at_last_acked_packet_ = total_data_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() + kMaxTrackedPackets) {
+ RTC_LOG(LS_WARNING)
+ << "BandwidthSampler in-flight packet map has exceeded maximum "
+ "number "
+ "of tracked packets.";
+ }
+
+ bool success =
+ connection_state_map_.Emplace(packet_number, sent_time, data_size, *this);
+ if (!success)
+ RTC_LOG(LS_WARNING) << "BandwidthSampler failed to insert the packet "
+ "into the map, most likely because it's already "
+ "in it.";
+}
+
+BandwidthSample BandwidthSampler::OnPacketAcknowledged(Timestamp ack_time,
+ int64_t packet_number) {
+ ConnectionStateOnSentPacket* sent_packet_pointer =
+ connection_state_map_.GetEntry(packet_number);
+ if (sent_packet_pointer == nullptr) {
+ return BandwidthSample();
+ }
+ BandwidthSample sample =
+ OnPacketAcknowledgedInner(ack_time, packet_number, *sent_packet_pointer);
+ connection_state_map_.Remove(packet_number);
+ return sample;
+}
+
+BandwidthSample BandwidthSampler::OnPacketAcknowledgedInner(
+ Timestamp ack_time,
+ int64_t packet_number,
+ const ConnectionStateOnSentPacket& sent_packet) {
+ total_data_acked_ += sent_packet.size;
+ total_data_sent_at_last_acked_packet_ = sent_packet.total_data_sent;
+ last_acked_packet_sent_time_ = sent_packet.sent_time;
+ last_acked_packet_ack_time_ = ack_time;
+
+ // Exit app-limited phase once a packet that was sent while the connection is
+ // not app-limited is acknowledged.
+ if (is_app_limited_ && 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 ||
+ !sent_packet.last_acked_packet_ack_time) {
+ return BandwidthSample();
+ }
+
+ // Infinite rate indicates that the sampler is supposed to discard the
+ // current send rate sample and use only the ack rate.
+ DataRate send_rate = DataRate::Infinity();
+ if (sent_packet.sent_time > *sent_packet.last_acked_packet_sent_time) {
+ DataSize sent_delta = sent_packet.total_data_sent -
+ sent_packet.total_data_sent_at_last_acked_packet;
+ TimeDelta time_delta =
+ sent_packet.sent_time - *sent_packet.last_acked_packet_sent_time;
+ send_rate = sent_delta / time_delta;
+ }
+
+ // 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 <= *sent_packet.last_acked_packet_ack_time) {
+ RTC_LOG(LS_WARNING)
+ << "Time of the previously acked packet is larger than the time "
+ "of the current packet.";
+ return BandwidthSample();
+ }
+ DataSize ack_delta =
+ total_data_acked_ - sent_packet.total_data_acked_at_the_last_acked_packet;
+ TimeDelta time_delta = ack_time - *sent_packet.last_acked_packet_ack_time;
+ DataRate ack_rate = ack_delta / time_delta;
+
+ 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;
+ // A sample is app-limited if the packet was sent during the app-limited
+ // phase.
+ sample.is_app_limited = sent_packet.is_app_limited;
+ return sample;
+}
+
+void BandwidthSampler::OnPacketLost(int64_t packet_number) {
+ connection_state_map_.Remove(packet_number);
+}
+
+void BandwidthSampler::OnAppLimited() {
+ is_app_limited_ = true;
+ end_of_app_limited_phase_ = last_sent_packet_;
+}
+
+void BandwidthSampler::RemoveObsoletePackets(int64_t least_unacked) {
+ while (!connection_state_map_.IsEmpty() &&
+ connection_state_map_.first_packet() < least_unacked) {
+ connection_state_map_.Remove(connection_state_map_.first_packet());
+ }
+}
+
+DataSize BandwidthSampler::total_data_acked() const {
+ return total_data_acked_;
+}
+
+bool BandwidthSampler::is_app_limited() const {
+ return is_app_limited_;
+}
+
+int64_t BandwidthSampler::end_of_app_limited_phase() const {
+ return end_of_app_limited_phase_;
+}
+
+BandwidthSampler::ConnectionStateOnSentPacket::ConnectionStateOnSentPacket(
+ Timestamp sent_time,
+ DataSize size,
+ const BandwidthSampler& sampler)
+ : sent_time(sent_time),
+ size(size),
+ total_data_sent(sampler.total_data_sent_),
+ total_data_sent_at_last_acked_packet(
+ sampler.total_data_sent_at_last_acked_packet_),
+ last_acked_packet_sent_time(sampler.last_acked_packet_sent_time_),
+ last_acked_packet_ack_time(sampler.last_acked_packet_ack_time_),
+ total_data_acked_at_the_last_acked_packet(sampler.total_data_acked_),
+ is_app_limited(sampler.is_app_limited_) {}
+
+BandwidthSampler::ConnectionStateOnSentPacket::ConnectionStateOnSentPacket()
+ : sent_time(Timestamp::ms(0)),
+ size(DataSize::Zero()),
+ total_data_sent(DataSize::Zero()),
+ total_data_sent_at_last_acked_packet(DataSize::Zero()),
+ last_acked_packet_sent_time(),
+ last_acked_packet_ack_time(),
+ total_data_acked_at_the_last_acked_packet(DataSize::Zero()),
+ is_app_limited(false) {}
+
+BandwidthSampler::ConnectionStateOnSentPacket::~ConnectionStateOnSentPacket() {}
+
+} // namespace bbr
+} // namespace webrtc
diff --git a/modules/congestion_controller/bbr/bandwidth_sampler.h b/modules/congestion_controller/bbr/bandwidth_sampler.h
new file mode 100644
index 0000000..9f448a6
--- /dev/null
+++ b/modules/congestion_controller/bbr/bandwidth_sampler.h
@@ -0,0 +1,261 @@
+/*
+ * Copyright (c) 2018 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+// Based on the Quic implementation in Chromium.
+
+#ifndef MODULES_CONGESTION_CONTROLLER_BBR_BANDWIDTH_SAMPLER_H_
+#define MODULES_CONGESTION_CONTROLLER_BBR_BANDWIDTH_SAMPLER_H_
+
+#include "api/optional.h"
+#include "api/units/data_rate.h"
+#include "api/units/data_size.h"
+#include "api/units/time_delta.h"
+#include "api/units/timestamp.h"
+#include "modules/congestion_controller/bbr/packet_number_indexed_queue.h"
+
+namespace webrtc {
+namespace bbr {
+
+namespace test {
+class BandwidthSamplerPeer;
+} // namespace test
+
+struct BandwidthSample {
+ // The bandwidth at that particular sample. Zero if no valid bandwidth sample
+ // is available.
+ DataRate bandwidth;
+
+ // The RTT measurement at this particular sample. Zero if no RTT sample is
+ // available. Does not correct for delayed ack time.
+ TimeDelta rtt;
+
+ // Indicates whether the sample might be artificially low because the sender
+ // did not have enough data to send in order to saturate the link.
+ bool is_app_limited;
+
+ BandwidthSample()
+ : bandwidth(DataRate::Zero()),
+ rtt(TimeDelta::Zero()),
+ is_app_limited(false) {}
+};
+
+// BandwidthSampler keeps track of sent and acknowledged packets and outputs a
+// bandwidth sample for every packet acknowledged. The samples are taken for
+// individual packets, and are not filtered; the consumer has to filter the
+// bandwidth samples itself. In certain cases, the sampler will locally severely
+// underestimate the bandwidth, hence a maximum filter with a size of at least
+// one RTT is recommended.
+//
+// This class bases its samples on the slope of two curves: the number of
+// data_size sent over time, and the number of data_size acknowledged as
+// received over time. It produces a sample of both slopes for every packet that
+// gets acknowledged, based on a slope between two points on each of the
+// corresponding curves. Note that due to the packet loss, the number of
+// data_size on each curve might get further and further away from each other,
+// meaning that it is not feasible to compare byte values coming from different
+// curves with each other.
+//
+// The obvious points for measuring slope sample are the ones corresponding to
+// the packet that was just acknowledged. Let us denote them as S_1 (point at
+// which the current packet was sent) and A_1 (point at which the current packet
+// was acknowledged). However, taking a slope requires two points on each line,
+// so estimating bandwidth requires picking a packet in the past with respect to
+// which the slope is measured.
+//
+// For that purpose, BandwidthSampler always keeps track of the most recently
+// acknowledged packet, and records it together with every outgoing packet.
+// When a packet gets acknowledged (A_1), it has not only information about when
+// it itself was sent (S_1), but also the information about the latest
+// acknowledged packet right before it was sent (S_0 and A_0).
+//
+// Based on that data, send and ack rate are estimated as:
+// send_rate = (data_size(S_1) - data_size(S_0)) / (time(S_1) - time(S_0))
+// ack_rate = (data_size(A_1) - data_size(A_0)) / (time(A_1) - time(A_0))
+//
+// Here, the ack rate is intuitively the rate we want to treat as bandwidth.
+// However, in certain cases (e.g. ack compression) the ack rate at a point may
+// end up higher than the rate at which the data was originally sent, which is
+// not indicative of the real bandwidth. Hence, we use the send rate as an upper
+// bound, and the sample value is
+// rate_sample = min(send_rate, ack_rate)
+//
+// An important edge case handled by the sampler is tracking the app-limited
+// samples. There are multiple meaning of "app-limited" used interchangeably,
+// hence it is important to understand and to be able to distinguish between
+// them.
+//
+// Meaning 1: connection state. The connection is said to be app-limited when
+// there is no outstanding data to send. This means that certain bandwidth
+// samples in the future would not be an accurate indication of the link
+// capacity, and it is important to inform consumer about that. Whenever
+// connection becomes app-limited, the sampler is notified via OnAppLimited()
+// method.
+//
+// Meaning 2: a phase in the bandwidth sampler. As soon as the bandwidth
+// sampler becomes notified about the connection being app-limited, it enters
+// app-limited phase. In that phase, all *sent* packets are marked as
+// app-limited. Note that the connection itself does not have to be
+// app-limited during the app-limited phase, and in fact it will not be
+// (otherwise how would it send packets?). The boolean flag below indicates
+// whether the sampler is in that phase.
+//
+// Meaning 3: a flag on the sent packet and on the sample. If a sent packet is
+// sent during the app-limited phase, the resulting sample related to the
+// packet will be marked as app-limited.
+//
+// With the terminology issue out of the way, let us consider the question of
+// what kind of situation it addresses.
+//
+// Consider a scenario where we first send packets 1 to 20 at a regular
+// bandwidth, and then immediately run out of data. After a few seconds, we send
+// packets 21 to 60, and only receive ack for 21 between sending packets 40 and
+// 41. In this case, when we sample bandwidth for packets 21 to 40, the S_0/A_0
+// we use to compute the slope is going to be packet 20, a few seconds apart
+// from the current packet, hence the resulting estimate would be extremely low
+// and not indicative of anything. Only at packet 41 the S_0/A_0 will become 21,
+// meaning that the bandwidth sample would exclude the quiescence.
+//
+// Based on the analysis of that scenario, we implement the following rule: once
+// OnAppLimited() is called, all sent packets will produce app-limited samples
+// up until an ack for a packet that was sent after OnAppLimited() was called.
+// Note that while the scenario above is not the only scenario when the
+// connection is app-limited, the approach works in other cases too.
+class BandwidthSampler {
+ public:
+ BandwidthSampler();
+ ~BandwidthSampler();
+ // Inputs the sent packet information into the sampler. Assumes that all
+ // packets are sent in order. The information about the packet will not be
+ // released from the sampler until the packet is either acknowledged or
+ // declared lost.
+ void OnPacketSent(Timestamp sent_time,
+ int64_t packet_number,
+ DataSize data_size,
+ DataSize data_in_flight);
+
+ // Notifies the sampler that the |packet_number| is acknowledged. Returns a
+ // bandwidth sample. If no bandwidth sample is available, bandwidth is set to
+ // DataRate::Zero().
+ BandwidthSample OnPacketAcknowledged(Timestamp ack_time,
+ int64_t packet_number);
+
+ // Informs the sampler that a packet is considered lost and it should no
+ // longer keep track of it.
+ void OnPacketLost(int64_t packet_number);
+
+ // Informs the sampler that the connection is currently app-limited, causing
+ // the sampler to enter the app-limited phase. The phase will expire by
+ // itself.
+ void OnAppLimited();
+
+ // Remove all the packets lower than the specified packet number.
+ void RemoveObsoletePackets(int64_t least_unacked);
+
+ // Total number of data_size currently acknowledged by the receiver.
+ DataSize total_data_acked() const;
+
+ // Application-limited information exported for debugging.
+ bool is_app_limited() const;
+ int64_t end_of_app_limited_phase() const;
+
+ private:
+ friend class test::BandwidthSamplerPeer;
+ // ConnectionStateOnSentPacket represents the information about a sent packet
+ // and the state of the connection at the moment the packet was sent,
+ // specifically the information about the most recently acknowledged packet at
+ // that moment.
+ struct ConnectionStateOnSentPacket {
+ // Time at which the packet is sent.
+ Timestamp sent_time;
+
+ // Size of the packet.
+ DataSize size;
+
+ // The value of |total_data_sent_| at the time the packet was sent.
+ // Includes the packet itself.
+ DataSize total_data_sent;
+
+ // The value of |total_data_sent_at_last_acked_packet_| at the time the
+ // packet was sent.
+ DataSize total_data_sent_at_last_acked_packet;
+
+ // The value of |last_acked_packet_sent_time_| at the time the packet was
+ // sent.
+ rtc::Optional<Timestamp> last_acked_packet_sent_time;
+
+ // The value of |last_acked_packet_ack_time_| at the time the packet was
+ // sent.
+ rtc::Optional<Timestamp> last_acked_packet_ack_time;
+
+ // The value of |total_data_acked_| at the time the packet was
+ // sent.
+ DataSize total_data_acked_at_the_last_acked_packet;
+
+ // The value of |is_app_limited_| at the time the packet was
+ // sent.
+ bool is_app_limited;
+
+ // Snapshot constructor. Records the current state of the bandwidth
+ // sampler.
+ ConnectionStateOnSentPacket(Timestamp sent_time,
+ DataSize size,
+ const BandwidthSampler& sampler);
+
+ // Default constructor. Required to put this structure into
+ // PacketNumberIndexedQueue.
+ ConnectionStateOnSentPacket();
+ ~ConnectionStateOnSentPacket();
+ };
+
+ // The total number of congestion controlled data_size sent during the
+ // connection.
+ DataSize total_data_sent_;
+
+ // The total number of congestion controlled data_size which were
+ // acknowledged.
+ DataSize total_data_acked_;
+
+ // The value of |total_data_sent_| at the time the last acknowledged packet
+ // was sent. Valid only when |last_acked_packet_sent_time_| is valid.
+ DataSize total_data_sent_at_last_acked_packet_;
+
+ // The time at which the last acknowledged packet was sent. Set to
+ // Timestamp::Zero() if no valid timestamp is available.
+ rtc::Optional<Timestamp> last_acked_packet_sent_time_;
+
+ // The time at which the most recent packet was acknowledged.
+ rtc::Optional<Timestamp> last_acked_packet_ack_time_;
+
+ // The most recently sent packet.
+ int64_t last_sent_packet_;
+
+ // Indicates whether the bandwidth sampler is currently in an app-limited
+ // phase.
+ bool is_app_limited_;
+
+ // The packet that will be acknowledged after this one will cause the sampler
+ // to exit the app-limited phase.
+ int64_t end_of_app_limited_phase_;
+
+ // Record of the connection state at the point where each packet in flight was
+ // sent, indexed by the packet number.
+ PacketNumberIndexedQueue<ConnectionStateOnSentPacket> connection_state_map_;
+
+ // Handles the actual bandwidth calculations, whereas the outer method handles
+ // retrieving and removing |sent_packet|.
+ BandwidthSample OnPacketAcknowledgedInner(
+ Timestamp ack_time,
+ int64_t packet_number,
+ const ConnectionStateOnSentPacket& sent_packet);
+};
+
+} // namespace bbr
+} // namespace webrtc
+
+#endif // MODULES_CONGESTION_CONTROLLER_BBR_BANDWIDTH_SAMPLER_H_
diff --git a/modules/congestion_controller/bbr/bandwidth_sampler_unittest.cc b/modules/congestion_controller/bbr/bandwidth_sampler_unittest.cc
new file mode 100644
index 0000000..45f3f48
--- /dev/null
+++ b/modules/congestion_controller/bbr/bandwidth_sampler_unittest.cc
@@ -0,0 +1,337 @@
+/*
+ * Copyright 2018 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+// Based on the Quic implementation in Chromium.
+
+#include <algorithm>
+
+#include "modules/congestion_controller/bbr/bandwidth_sampler.h"
+
+#include "test/gtest.h"
+
+namespace webrtc {
+namespace bbr {
+namespace test {
+
+class BandwidthSamplerPeer {
+ public:
+ static size_t GetNumberOfTrackedPackets(const BandwidthSampler& sampler) {
+ return sampler.connection_state_map_.number_of_present_entries();
+ }
+
+ static DataSize GetPacketSize(const BandwidthSampler& sampler,
+ int64_t packet_number) {
+ return sampler.connection_state_map_.GetEntry(packet_number)->size;
+ }
+};
+
+const int64_t kRegularPacketSizeBytes = 1280;
+// Enforce divisibility for some of the tests.
+static_assert((kRegularPacketSizeBytes & 31) == 0,
+ "kRegularPacketSizeBytes has to be five times divisible by 2");
+
+const DataSize kRegularPacketSize = DataSize::bytes(kRegularPacketSizeBytes);
+
+// A test fixture with utility methods for BandwidthSampler tests.
+class BandwidthSamplerTest : public ::testing::Test {
+ protected:
+ BandwidthSamplerTest()
+ : clock_(Timestamp::seconds(100)), bytes_in_flight_(DataSize::Zero()) {}
+
+ Timestamp clock_;
+ BandwidthSampler sampler_;
+ DataSize bytes_in_flight_;
+
+ void SendPacketInner(int64_t packet_number, DataSize bytes) {
+ sampler_.OnPacketSent(clock_, packet_number, bytes, bytes_in_flight_);
+ bytes_in_flight_ += bytes;
+ }
+
+ void SendPacket(int64_t packet_number) {
+ SendPacketInner(packet_number, kRegularPacketSize);
+ }
+
+ BandwidthSample AckPacketInner(int64_t packet_number) {
+ DataSize size =
+ BandwidthSamplerPeer::GetPacketSize(sampler_, packet_number);
+ bytes_in_flight_ -= size;
+ return sampler_.OnPacketAcknowledged(clock_, packet_number);
+ }
+
+ // Acknowledge receipt of a packet and expect it to be not app-limited.
+ DataRate AckPacket(int64_t packet_number) {
+ BandwidthSample sample = AckPacketInner(packet_number);
+ EXPECT_FALSE(sample.is_app_limited);
+ return sample.bandwidth;
+ }
+
+ void LosePacket(int64_t packet_number) {
+ DataSize size =
+ BandwidthSamplerPeer::GetPacketSize(sampler_, packet_number);
+ bytes_in_flight_ -= size;
+ sampler_.OnPacketLost(packet_number);
+ }
+
+ // Sends one packet and acks it. Then, send 20 packets. Finally, send
+ // another 20 packets while acknowledging previous 20.
+ void Send40PacketsAndAckFirst20(TimeDelta time_between_packets) {
+ // Send 20 packets at a constant inter-packet time.
+ for (int64_t i = 1; i <= 20; i++) {
+ SendPacket(i);
+ clock_ += time_between_packets;
+ }
+
+ // Ack packets 1 to 20, while sending new packets at the same rate as
+ // before.
+ for (int64_t i = 1; i <= 20; i++) {
+ AckPacket(i);
+ SendPacket(i + 20);
+ clock_ += time_between_packets;
+ }
+ }
+};
+
+// Test the sampler in a simple stop-and-wait sender setting.
+TEST_F(BandwidthSamplerTest, SendAndWait) {
+ TimeDelta time_between_packets = TimeDelta::ms(10);
+ DataRate expected_bandwidth =
+ kRegularPacketSize * 100 / TimeDelta::seconds(1);
+
+ // Send packets at the constant bandwidth.
+ for (int64_t i = 1; i < 20; i++) {
+ SendPacket(i);
+ clock_ += time_between_packets;
+ DataRate current_sample = AckPacket(i);
+ EXPECT_EQ(expected_bandwidth, current_sample);
+ }
+
+ // Send packets at the exponentially decreasing bandwidth.
+ for (int64_t i = 20; i < 25; i++) {
+ time_between_packets = time_between_packets * 2;
+ expected_bandwidth = expected_bandwidth * 0.5;
+
+ SendPacket(i);
+ clock_ += time_between_packets;
+ DataRate current_sample = AckPacket(i);
+ EXPECT_EQ(expected_bandwidth, current_sample);
+ }
+ EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
+ EXPECT_TRUE(bytes_in_flight_.IsZero());
+}
+
+// Test the sampler during regular windowed sender scenario with fixed
+// CWND of 20.
+TEST_F(BandwidthSamplerTest, SendPaced) {
+ const TimeDelta time_between_packets = TimeDelta::ms(1);
+ DataRate expected_bandwidth = kRegularPacketSize / time_between_packets;
+
+ Send40PacketsAndAckFirst20(time_between_packets);
+
+ // Ack the packets 21 to 40, arriving at the correct bandwidth.
+ DataRate last_bandwidth = DataRate::Zero();
+ for (int64_t i = 21; i <= 40; i++) {
+ last_bandwidth = AckPacket(i);
+ EXPECT_EQ(expected_bandwidth, last_bandwidth);
+ clock_ += time_between_packets;
+ }
+ EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
+ EXPECT_TRUE(bytes_in_flight_.IsZero());
+}
+
+// Test the sampler in a scenario where 50% of packets is consistently lost.
+TEST_F(BandwidthSamplerTest, SendWithLosses) {
+ const TimeDelta time_between_packets = TimeDelta::ms(1);
+ DataRate expected_bandwidth = kRegularPacketSize / time_between_packets * 0.5;
+
+ // Send 20 packets, each 1 ms apart.
+ for (int64_t i = 1; i <= 20; i++) {
+ SendPacket(i);
+ clock_ += time_between_packets;
+ }
+
+ // Ack packets 1 to 20, losing every even-numbered packet, while sending new
+ // packets at the same rate as before.
+ for (int64_t i = 1; i <= 20; i++) {
+ if (i % 2 == 0) {
+ AckPacket(i);
+ } else {
+ LosePacket(i);
+ }
+ SendPacket(i + 20);
+ clock_ += time_between_packets;
+ }
+
+ // Ack the packets 21 to 40 with the same loss pattern.
+ DataRate last_bandwidth = DataRate::Zero();
+ for (int64_t i = 21; i <= 40; i++) {
+ if (i % 2 == 0) {
+ last_bandwidth = AckPacket(i);
+ EXPECT_EQ(expected_bandwidth, last_bandwidth);
+ } else {
+ LosePacket(i);
+ }
+ clock_ += time_between_packets;
+ }
+ EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
+ EXPECT_TRUE(bytes_in_flight_.IsZero());
+}
+
+// Simulate a situation where ACKs arrive in burst and earlier than usual, thus
+// producing an ACK rate which is higher than the original send rate.
+TEST_F(BandwidthSamplerTest, CompressedAck) {
+ const TimeDelta time_between_packets = TimeDelta::ms(1);
+ DataRate expected_bandwidth = kRegularPacketSize / time_between_packets;
+
+ Send40PacketsAndAckFirst20(time_between_packets);
+
+ // Simulate an RTT somewhat lower than the one for 1-to-21 transmission.
+ clock_ += time_between_packets * 15;
+
+ // Ack the packets 21 to 40 almost immediately at once.
+ DataRate last_bandwidth = DataRate::Zero();
+ TimeDelta ridiculously_small_time_delta = TimeDelta::us(20);
+ for (int64_t i = 21; i <= 40; i++) {
+ last_bandwidth = AckPacket(i);
+ clock_ += ridiculously_small_time_delta;
+ }
+ EXPECT_EQ(expected_bandwidth, last_bandwidth);
+ EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
+ EXPECT_TRUE(bytes_in_flight_.IsZero());
+}
+
+// Tests receiving ACK packets in the reverse order.
+TEST_F(BandwidthSamplerTest, ReorderedAck) {
+ const TimeDelta time_between_packets = TimeDelta::ms(1);
+ DataRate expected_bandwidth = kRegularPacketSize / time_between_packets;
+
+ Send40PacketsAndAckFirst20(time_between_packets);
+
+ // Ack the packets 21 to 40 in the reverse order, while sending packets 41 to
+ // 60.
+ DataRate last_bandwidth = DataRate::Zero();
+ for (int64_t i = 0; i < 20; i++) {
+ last_bandwidth = AckPacket(40 - i);
+ EXPECT_EQ(expected_bandwidth, last_bandwidth);
+ SendPacket(41 + i);
+ clock_ += time_between_packets;
+ }
+
+ // Ack the packets 41 to 60, now in the regular order.
+ for (int64_t i = 41; i <= 60; i++) {
+ last_bandwidth = AckPacket(i);
+ EXPECT_EQ(expected_bandwidth, last_bandwidth);
+ clock_ += time_between_packets;
+ }
+ EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
+ EXPECT_TRUE(bytes_in_flight_.IsZero());
+}
+
+// Test the app-limited logic.
+TEST_F(BandwidthSamplerTest, AppLimited) {
+ const TimeDelta time_between_packets = TimeDelta::ms(1);
+ DataRate expected_bandwidth = kRegularPacketSize / time_between_packets;
+
+ Send40PacketsAndAckFirst20(time_between_packets);
+
+ // We are now app-limited. Ack 21 to 40 as usual, but do not send anything for
+ // now.
+ sampler_.OnAppLimited();
+ for (int64_t i = 21; i <= 40; i++) {
+ DataRate current_sample = AckPacket(i);
+ EXPECT_EQ(expected_bandwidth, current_sample);
+ clock_ += time_between_packets;
+ }
+
+ // Enter quiescence.
+ clock_ += TimeDelta::seconds(1);
+
+ // Send packets 41 to 60, all of which would be marked as app-limited.
+ for (int64_t i = 41; i <= 60; i++) {
+ SendPacket(i);
+ clock_ += time_between_packets;
+ }
+
+ // Ack packets 41 to 60, while sending packets 61 to 80. 41 to 60 should be
+ // app-limited and underestimate the bandwidth due to that.
+ for (int64_t i = 41; i <= 60; i++) {
+ BandwidthSample sample = AckPacketInner(i);
+ EXPECT_TRUE(sample.is_app_limited);
+ EXPECT_LT(sample.bandwidth, 0.7f * expected_bandwidth);
+
+ SendPacket(i + 20);
+ clock_ += time_between_packets;
+ }
+
+ // Run out of packets, and then ack packet 61 to 80, all of which should have
+ // correct non-app-limited samples.
+ for (int64_t i = 61; i <= 80; i++) {
+ DataRate last_bandwidth = AckPacket(i);
+ EXPECT_EQ(expected_bandwidth, last_bandwidth);
+ clock_ += time_between_packets;
+ }
+
+ EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
+ EXPECT_TRUE(bytes_in_flight_.IsZero());
+}
+
+// Test the samples taken at the first flight of packets sent.
+TEST_F(BandwidthSamplerTest, FirstRoundTrip) {
+ const TimeDelta time_between_packets = TimeDelta::ms(1);
+ const TimeDelta rtt = TimeDelta::ms(800);
+ const int num_packets = 10;
+ const DataSize num_bytes = kRegularPacketSize * num_packets;
+ const DataRate real_bandwidth = num_bytes / rtt;
+
+ for (int64_t i = 1; i <= 10; i++) {
+ SendPacket(i);
+ clock_ += time_between_packets;
+ }
+
+ clock_ += rtt - num_packets * time_between_packets;
+
+ DataRate last_sample = DataRate::Zero();
+ for (int64_t i = 1; i <= 10; i++) {
+ DataRate sample = AckPacket(i);
+ EXPECT_GT(sample, last_sample);
+ last_sample = sample;
+ clock_ += time_between_packets;
+ }
+
+ // The final measured sample for the first flight of sample is expected to be
+ // smaller than the real bandwidth, yet it should not lose more than 10%. The
+ // specific value of the error depends on the difference between the RTT and
+ // the time it takes to exhaust the congestion window (i.e. in the limit when
+ // all packets are sent simultaneously, last sample would indicate the real
+ // bandwidth).
+ EXPECT_LT(last_sample, real_bandwidth);
+ EXPECT_GT(last_sample, 0.9f * real_bandwidth);
+}
+
+// Test sampler's ability to remove obsolete packets.
+TEST_F(BandwidthSamplerTest, RemoveObsoletePackets) {
+ SendPacket(1);
+ SendPacket(2);
+ SendPacket(3);
+ SendPacket(4);
+ SendPacket(5);
+
+ clock_ += TimeDelta::ms(100);
+
+ EXPECT_EQ(5u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
+ sampler_.RemoveObsoletePackets(4);
+ EXPECT_EQ(2u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
+ sampler_.OnPacketLost(4);
+ EXPECT_EQ(1u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
+ AckPacket(5);
+ EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
+}
+
+} // namespace test
+} // namespace bbr
+} // namespace webrtc
