| // 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 "quiche/quic/core/congestion_control/bandwidth_sampler.h" |
| |
| #include <cstdint> |
| #include <set> |
| |
| #include "quiche/quic/core/quic_bandwidth.h" |
| #include "quiche/quic/core/quic_time.h" |
| #include "quiche/quic/core/quic_types.h" |
| #include "quiche/quic/platform/api/quic_flags.h" |
| #include "quiche/quic/platform/api/quic_logging.h" |
| #include "quiche/quic/platform/api/quic_test.h" |
| #include "quiche/quic/test_tools/mock_clock.h" |
| |
| namespace quic { |
| namespace test { |
| |
| class BandwidthSamplerPeer { |
| public: |
| static size_t GetNumberOfTrackedPackets(const BandwidthSampler& sampler) { |
| return sampler.connection_state_map_.number_of_present_entries(); |
| } |
| |
| static QuicByteCount GetPacketSize(const BandwidthSampler& sampler, |
| QuicPacketNumber packet_number) { |
| return sampler.connection_state_map_.GetEntry(packet_number)->size; |
| } |
| }; |
| |
| const QuicByteCount kRegularPacketSize = 1280; |
| // Enforce divisibility for some of the tests. |
| static_assert((kRegularPacketSize & 31) == 0, |
| "kRegularPacketSize has to be five times divisible by 2"); |
| |
| struct TestParameters { |
| bool overestimate_avoidance; |
| }; |
| |
| // Used by ::testing::PrintToStringParamName(). |
| std::string PrintToString(const TestParameters& p) { |
| return p.overestimate_avoidance ? "enable_overestimate_avoidance" |
| : "no_enable_overestimate_avoidance"; |
| } |
| |
| // A test fixture with utility methods for BandwidthSampler tests. |
| class BandwidthSamplerTest : public QuicTestWithParam<TestParameters> { |
| protected: |
| BandwidthSamplerTest() |
| : sampler_(nullptr, /*max_height_tracker_window_length=*/0), |
| sampler_app_limited_at_start_(sampler_.is_app_limited()), |
| bytes_in_flight_(0), |
| max_bandwidth_(QuicBandwidth::Zero()), |
| est_bandwidth_upper_bound_(QuicBandwidth::Infinite()), |
| round_trip_count_(0) { |
| // Ensure that the clock does not start at zero. |
| clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1)); |
| if (GetParam().overestimate_avoidance) { |
| sampler_.EnableOverestimateAvoidance(); |
| } |
| } |
| |
| MockClock clock_; |
| BandwidthSampler sampler_; |
| bool sampler_app_limited_at_start_; |
| QuicByteCount bytes_in_flight_; |
| QuicBandwidth max_bandwidth_; // Max observed bandwidth from acks. |
| QuicBandwidth est_bandwidth_upper_bound_; |
| QuicRoundTripCount round_trip_count_; // Needed to calculate extra_acked. |
| |
| QuicByteCount PacketsToBytes(QuicPacketCount packet_count) { |
| return packet_count * kRegularPacketSize; |
| } |
| |
| void SendPacketInner(uint64_t packet_number, QuicByteCount bytes, |
| HasRetransmittableData has_retransmittable_data) { |
| sampler_.OnPacketSent(clock_.Now(), QuicPacketNumber(packet_number), bytes, |
| bytes_in_flight_, has_retransmittable_data); |
| if (has_retransmittable_data == HAS_RETRANSMITTABLE_DATA) { |
| bytes_in_flight_ += bytes; |
| } |
| } |
| |
| void SendPacket(uint64_t packet_number) { |
| SendPacketInner(packet_number, kRegularPacketSize, |
| HAS_RETRANSMITTABLE_DATA); |
| } |
| |
| BandwidthSample AckPacketInner(uint64_t packet_number) { |
| QuicByteCount size = BandwidthSamplerPeer::GetPacketSize( |
| sampler_, QuicPacketNumber(packet_number)); |
| bytes_in_flight_ -= size; |
| BandwidthSampler::CongestionEventSample sample = sampler_.OnCongestionEvent( |
| clock_.Now(), {MakeAckedPacket(packet_number)}, {}, max_bandwidth_, |
| est_bandwidth_upper_bound_, round_trip_count_); |
| max_bandwidth_ = std::max(max_bandwidth_, sample.sample_max_bandwidth); |
| BandwidthSample bandwidth_sample; |
| bandwidth_sample.bandwidth = sample.sample_max_bandwidth; |
| bandwidth_sample.rtt = sample.sample_rtt; |
| bandwidth_sample.state_at_send = sample.last_packet_send_state; |
| EXPECT_TRUE(bandwidth_sample.state_at_send.is_valid); |
| return bandwidth_sample; |
| } |
| |
| AckedPacket MakeAckedPacket(uint64_t packet_number) const { |
| QuicByteCount size = BandwidthSamplerPeer::GetPacketSize( |
| sampler_, QuicPacketNumber(packet_number)); |
| return AckedPacket(QuicPacketNumber(packet_number), size, clock_.Now()); |
| } |
| |
| LostPacket MakeLostPacket(uint64_t packet_number) const { |
| return LostPacket(QuicPacketNumber(packet_number), |
| BandwidthSamplerPeer::GetPacketSize( |
| sampler_, QuicPacketNumber(packet_number))); |
| } |
| |
| // Acknowledge receipt of a packet and expect it to be not app-limited. |
| QuicBandwidth AckPacket(uint64_t packet_number) { |
| BandwidthSample sample = AckPacketInner(packet_number); |
| return sample.bandwidth; |
| } |
| |
| BandwidthSampler::CongestionEventSample OnCongestionEvent( |
| std::set<uint64_t> acked_packet_numbers, |
| std::set<uint64_t> lost_packet_numbers) { |
| AckedPacketVector acked_packets; |
| for (auto it = acked_packet_numbers.begin(); |
| it != acked_packet_numbers.end(); ++it) { |
| acked_packets.push_back(MakeAckedPacket(*it)); |
| bytes_in_flight_ -= acked_packets.back().bytes_acked; |
| } |
| |
| LostPacketVector lost_packets; |
| for (auto it = lost_packet_numbers.begin(); it != lost_packet_numbers.end(); |
| ++it) { |
| lost_packets.push_back(MakeLostPacket(*it)); |
| bytes_in_flight_ -= lost_packets.back().bytes_lost; |
| } |
| |
| BandwidthSampler::CongestionEventSample sample = sampler_.OnCongestionEvent( |
| clock_.Now(), acked_packets, lost_packets, max_bandwidth_, |
| est_bandwidth_upper_bound_, round_trip_count_); |
| max_bandwidth_ = std::max(max_bandwidth_, sample.sample_max_bandwidth); |
| return sample; |
| } |
| |
| SendTimeState LosePacket(uint64_t packet_number) { |
| QuicByteCount size = BandwidthSamplerPeer::GetPacketSize( |
| sampler_, QuicPacketNumber(packet_number)); |
| bytes_in_flight_ -= size; |
| LostPacket lost_packet(QuicPacketNumber(packet_number), size); |
| BandwidthSampler::CongestionEventSample sample = sampler_.OnCongestionEvent( |
| clock_.Now(), {}, {lost_packet}, max_bandwidth_, |
| est_bandwidth_upper_bound_, round_trip_count_); |
| EXPECT_TRUE(sample.last_packet_send_state.is_valid); |
| EXPECT_EQ(sample.sample_max_bandwidth, QuicBandwidth::Zero()); |
| EXPECT_EQ(sample.sample_rtt, QuicTime::Delta::Infinite()); |
| return sample.last_packet_send_state; |
| } |
| |
| // Sends one packet and acks it. Then, send 20 packets. Finally, send |
| // another 20 packets while acknowledging previous 20. |
| void Send40PacketsAndAckFirst20(QuicTime::Delta time_between_packets) { |
| // Send 20 packets at a constant inter-packet time. |
| for (int i = 1; i <= 20; i++) { |
| SendPacket(i); |
| clock_.AdvanceTime(time_between_packets); |
| } |
| |
| // Ack packets 1 to 20, while sending new packets at the same rate as |
| // before. |
| for (int i = 1; i <= 20; i++) { |
| AckPacket(i); |
| SendPacket(i + 20); |
| clock_.AdvanceTime(time_between_packets); |
| } |
| } |
| }; |
| |
| INSTANTIATE_TEST_SUITE_P( |
| BandwidthSamplerTests, BandwidthSamplerTest, |
| testing::Values(TestParameters{/*overestimate_avoidance=*/false}, |
| TestParameters{/*overestimate_avoidance=*/true}), |
| testing::PrintToStringParamName()); |
| |
| // Test the sampler in a simple stop-and-wait sender setting. |
| TEST_P(BandwidthSamplerTest, SendAndWait) { |
| QuicTime::Delta time_between_packets = QuicTime::Delta::FromMilliseconds(10); |
| QuicBandwidth expected_bandwidth = |
| QuicBandwidth::FromBytesPerSecond(kRegularPacketSize * 100); |
| |
| // Send packets at the constant bandwidth. |
| for (int i = 1; i < 20; i++) { |
| SendPacket(i); |
| clock_.AdvanceTime(time_between_packets); |
| QuicBandwidth current_sample = AckPacket(i); |
| EXPECT_EQ(expected_bandwidth, current_sample); |
| } |
| |
| // Send packets at the exponentially decreasing bandwidth. |
| for (int i = 20; i < 25; i++) { |
| time_between_packets = time_between_packets * 2; |
| expected_bandwidth = expected_bandwidth * 0.5; |
| |
| SendPacket(i); |
| clock_.AdvanceTime(time_between_packets); |
| QuicBandwidth current_sample = AckPacket(i); |
| EXPECT_EQ(expected_bandwidth, current_sample); |
| } |
| sampler_.RemoveObsoletePackets(QuicPacketNumber(25)); |
| |
| EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); |
| EXPECT_EQ(0u, bytes_in_flight_); |
| } |
| |
| TEST_P(BandwidthSamplerTest, SendTimeState) { |
| QuicTime::Delta time_between_packets = QuicTime::Delta::FromMilliseconds(10); |
| |
| // Send packets 1-5. |
| for (int i = 1; i <= 5; i++) { |
| SendPacket(i); |
| EXPECT_EQ(PacketsToBytes(i), sampler_.total_bytes_sent()); |
| clock_.AdvanceTime(time_between_packets); |
| } |
| |
| // Ack packet 1. |
| SendTimeState send_time_state = AckPacketInner(1).state_at_send; |
| EXPECT_EQ(PacketsToBytes(1), send_time_state.total_bytes_sent); |
| EXPECT_EQ(0u, send_time_state.total_bytes_acked); |
| EXPECT_EQ(0u, send_time_state.total_bytes_lost); |
| EXPECT_EQ(PacketsToBytes(1), sampler_.total_bytes_acked()); |
| |
| // Lose packet 2. |
| send_time_state = LosePacket(2); |
| EXPECT_EQ(PacketsToBytes(2), send_time_state.total_bytes_sent); |
| EXPECT_EQ(0u, send_time_state.total_bytes_acked); |
| EXPECT_EQ(0u, send_time_state.total_bytes_lost); |
| EXPECT_EQ(PacketsToBytes(1), sampler_.total_bytes_lost()); |
| |
| // Lose packet 3. |
| send_time_state = LosePacket(3); |
| EXPECT_EQ(PacketsToBytes(3), send_time_state.total_bytes_sent); |
| EXPECT_EQ(0u, send_time_state.total_bytes_acked); |
| EXPECT_EQ(0u, send_time_state.total_bytes_lost); |
| EXPECT_EQ(PacketsToBytes(2), sampler_.total_bytes_lost()); |
| |
| // Send packets 6-10. |
| for (int i = 6; i <= 10; i++) { |
| SendPacket(i); |
| EXPECT_EQ(PacketsToBytes(i), sampler_.total_bytes_sent()); |
| clock_.AdvanceTime(time_between_packets); |
| } |
| |
| // Ack all inflight packets. |
| QuicPacketCount acked_packet_count = 1; |
| EXPECT_EQ(PacketsToBytes(acked_packet_count), sampler_.total_bytes_acked()); |
| for (int i = 4; i <= 10; i++) { |
| send_time_state = AckPacketInner(i).state_at_send; |
| ++acked_packet_count; |
| EXPECT_EQ(PacketsToBytes(acked_packet_count), sampler_.total_bytes_acked()); |
| EXPECT_EQ(PacketsToBytes(i), send_time_state.total_bytes_sent); |
| if (i <= 5) { |
| EXPECT_EQ(0u, send_time_state.total_bytes_acked); |
| EXPECT_EQ(0u, send_time_state.total_bytes_lost); |
| } else { |
| EXPECT_EQ(PacketsToBytes(1), send_time_state.total_bytes_acked); |
| EXPECT_EQ(PacketsToBytes(2), send_time_state.total_bytes_lost); |
| } |
| |
| // This equation works because there is no neutered bytes. |
| EXPECT_EQ(send_time_state.total_bytes_sent - |
| send_time_state.total_bytes_acked - |
| send_time_state.total_bytes_lost, |
| send_time_state.bytes_in_flight); |
| |
| clock_.AdvanceTime(time_between_packets); |
| } |
| } |
| |
| // Test the sampler during regular windowed sender scenario with fixed |
| // CWND of 20. |
| TEST_P(BandwidthSamplerTest, SendPaced) { |
| const QuicTime::Delta time_between_packets = |
| QuicTime::Delta::FromMilliseconds(1); |
| QuicBandwidth expected_bandwidth = |
| QuicBandwidth::FromKBytesPerSecond(kRegularPacketSize); |
| |
| Send40PacketsAndAckFirst20(time_between_packets); |
| |
| // Ack the packets 21 to 40, arriving at the correct bandwidth. |
| QuicBandwidth last_bandwidth = QuicBandwidth::Zero(); |
| for (int i = 21; i <= 40; i++) { |
| last_bandwidth = AckPacket(i); |
| EXPECT_EQ(expected_bandwidth, last_bandwidth) << "i is " << i; |
| clock_.AdvanceTime(time_between_packets); |
| } |
| sampler_.RemoveObsoletePackets(QuicPacketNumber(41)); |
| |
| EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); |
| EXPECT_EQ(0u, bytes_in_flight_); |
| } |
| |
| // Test the sampler in a scenario where 50% of packets is consistently lost. |
| TEST_P(BandwidthSamplerTest, SendWithLosses) { |
| const QuicTime::Delta time_between_packets = |
| QuicTime::Delta::FromMilliseconds(1); |
| QuicBandwidth expected_bandwidth = |
| QuicBandwidth::FromKBytesPerSecond(kRegularPacketSize) * 0.5; |
| |
| // Send 20 packets, each 1 ms apart. |
| for (int i = 1; i <= 20; i++) { |
| SendPacket(i); |
| clock_.AdvanceTime(time_between_packets); |
| } |
| |
| // Ack packets 1 to 20, losing every even-numbered packet, while sending new |
| // packets at the same rate as before. |
| for (int i = 1; i <= 20; i++) { |
| if (i % 2 == 0) { |
| AckPacket(i); |
| } else { |
| LosePacket(i); |
| } |
| SendPacket(i + 20); |
| clock_.AdvanceTime(time_between_packets); |
| } |
| |
| // Ack the packets 21 to 40 with the same loss pattern. |
| QuicBandwidth last_bandwidth = QuicBandwidth::Zero(); |
| for (int i = 21; i <= 40; i++) { |
| if (i % 2 == 0) { |
| last_bandwidth = AckPacket(i); |
| EXPECT_EQ(expected_bandwidth, last_bandwidth); |
| } else { |
| LosePacket(i); |
| } |
| clock_.AdvanceTime(time_between_packets); |
| } |
| sampler_.RemoveObsoletePackets(QuicPacketNumber(41)); |
| |
| EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); |
| EXPECT_EQ(0u, bytes_in_flight_); |
| } |
| |
| // Test the sampler in a scenario where the 50% of packets are not |
| // congestion controlled (specifically, non-retransmittable data is not |
| // congestion controlled). Should be functionally consistent in behavior with |
| // the SendWithLosses test. |
| TEST_P(BandwidthSamplerTest, NotCongestionControlled) { |
| const QuicTime::Delta time_between_packets = |
| QuicTime::Delta::FromMilliseconds(1); |
| QuicBandwidth expected_bandwidth = |
| QuicBandwidth::FromKBytesPerSecond(kRegularPacketSize) * 0.5; |
| |
| // Send 20 packets, each 1 ms apart. Every even packet is not congestion |
| // controlled. |
| for (int i = 1; i <= 20; i++) { |
| SendPacketInner( |
| i, kRegularPacketSize, |
| i % 2 == 0 ? HAS_RETRANSMITTABLE_DATA : NO_RETRANSMITTABLE_DATA); |
| clock_.AdvanceTime(time_between_packets); |
| } |
| |
| // Ensure only congestion controlled packets are tracked. |
| EXPECT_EQ(10u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); |
| |
| // Ack packets 2 to 21, ignoring every even-numbered packet, while sending new |
| // packets at the same rate as before. |
| for (int i = 1; i <= 20; i++) { |
| if (i % 2 == 0) { |
| AckPacket(i); |
| } |
| SendPacketInner( |
| i + 20, kRegularPacketSize, |
| i % 2 == 0 ? HAS_RETRANSMITTABLE_DATA : NO_RETRANSMITTABLE_DATA); |
| clock_.AdvanceTime(time_between_packets); |
| } |
| |
| // Ack the packets 22 to 41 with the same congestion controlled pattern. |
| QuicBandwidth last_bandwidth = QuicBandwidth::Zero(); |
| for (int i = 21; i <= 40; i++) { |
| if (i % 2 == 0) { |
| last_bandwidth = AckPacket(i); |
| EXPECT_EQ(expected_bandwidth, last_bandwidth); |
| } |
| clock_.AdvanceTime(time_between_packets); |
| } |
| sampler_.RemoveObsoletePackets(QuicPacketNumber(41)); |
| |
| // Since only congestion controlled packets are entered into the map, it has |
| // to be empty at this point. |
| EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); |
| EXPECT_EQ(0u, bytes_in_flight_); |
| } |
| |
| // 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_P(BandwidthSamplerTest, CompressedAck) { |
| const QuicTime::Delta time_between_packets = |
| QuicTime::Delta::FromMilliseconds(1); |
| QuicBandwidth expected_bandwidth = |
| QuicBandwidth::FromKBytesPerSecond(kRegularPacketSize); |
| |
| Send40PacketsAndAckFirst20(time_between_packets); |
| |
| // Simulate an RTT somewhat lower than the one for 1-to-21 transmission. |
| clock_.AdvanceTime(time_between_packets * 15); |
| |
| // Ack the packets 21 to 40 almost immediately at once. |
| QuicBandwidth last_bandwidth = QuicBandwidth::Zero(); |
| QuicTime::Delta ridiculously_small_time_delta = |
| QuicTime::Delta::FromMicroseconds(20); |
| for (int i = 21; i <= 40; i++) { |
| last_bandwidth = AckPacket(i); |
| clock_.AdvanceTime(ridiculously_small_time_delta); |
| } |
| EXPECT_EQ(expected_bandwidth, last_bandwidth); |
| |
| sampler_.RemoveObsoletePackets(QuicPacketNumber(41)); |
| |
| EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); |
| EXPECT_EQ(0u, bytes_in_flight_); |
| } |
| |
| // Tests receiving ACK packets in the reverse order. |
| TEST_P(BandwidthSamplerTest, ReorderedAck) { |
| const QuicTime::Delta time_between_packets = |
| QuicTime::Delta::FromMilliseconds(1); |
| QuicBandwidth expected_bandwidth = |
| QuicBandwidth::FromKBytesPerSecond(kRegularPacketSize); |
| |
| Send40PacketsAndAckFirst20(time_between_packets); |
| |
| // Ack the packets 21 to 40 in the reverse order, while sending packets 41 to |
| // 60. |
| QuicBandwidth last_bandwidth = QuicBandwidth::Zero(); |
| for (int i = 0; i < 20; i++) { |
| last_bandwidth = AckPacket(40 - i); |
| EXPECT_EQ(expected_bandwidth, last_bandwidth); |
| SendPacket(41 + i); |
| clock_.AdvanceTime(time_between_packets); |
| } |
| |
| // Ack the packets 41 to 60, now in the regular order. |
| for (int i = 41; i <= 60; i++) { |
| last_bandwidth = AckPacket(i); |
| EXPECT_EQ(expected_bandwidth, last_bandwidth); |
| clock_.AdvanceTime(time_between_packets); |
| } |
| sampler_.RemoveObsoletePackets(QuicPacketNumber(61)); |
| |
| EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); |
| EXPECT_EQ(0u, bytes_in_flight_); |
| } |
| |
| // Test the app-limited logic. |
| TEST_P(BandwidthSamplerTest, AppLimited) { |
| const QuicTime::Delta time_between_packets = |
| QuicTime::Delta::FromMilliseconds(1); |
| QuicBandwidth expected_bandwidth = |
| QuicBandwidth::FromKBytesPerSecond(kRegularPacketSize); |
| |
| // Send 20 packets at a constant inter-packet time. |
| for (int i = 1; i <= 20; i++) { |
| SendPacket(i); |
| clock_.AdvanceTime(time_between_packets); |
| } |
| |
| // Ack packets 1 to 20, while sending new packets at the same rate as |
| // before. |
| for (int i = 1; i <= 20; i++) { |
| BandwidthSample sample = AckPacketInner(i); |
| EXPECT_EQ(sample.state_at_send.is_app_limited, |
| sampler_app_limited_at_start_); |
| SendPacket(i + 20); |
| clock_.AdvanceTime(time_between_packets); |
| } |
| |
| // We are now app-limited. Ack 21 to 40 as usual, but do not send anything for |
| // now. |
| sampler_.OnAppLimited(); |
| for (int i = 21; i <= 40; i++) { |
| BandwidthSample sample = AckPacketInner(i); |
| EXPECT_FALSE(sample.state_at_send.is_app_limited); |
| EXPECT_EQ(expected_bandwidth, sample.bandwidth); |
| clock_.AdvanceTime(time_between_packets); |
| } |
| |
| // Enter quiescence. |
| clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1)); |
| |
| // Send packets 41 to 60, all of which would be marked as app-limited. |
| for (int i = 41; i <= 60; i++) { |
| SendPacket(i); |
| clock_.AdvanceTime(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 (int i = 41; i <= 60; i++) { |
| BandwidthSample sample = AckPacketInner(i); |
| EXPECT_TRUE(sample.state_at_send.is_app_limited); |
| EXPECT_LT(sample.bandwidth, 0.7f * expected_bandwidth); |
| |
| SendPacket(i + 20); |
| clock_.AdvanceTime(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 (int i = 61; i <= 80; i++) { |
| BandwidthSample sample = AckPacketInner(i); |
| EXPECT_FALSE(sample.state_at_send.is_app_limited); |
| EXPECT_EQ(sample.bandwidth, expected_bandwidth); |
| clock_.AdvanceTime(time_between_packets); |
| } |
| sampler_.RemoveObsoletePackets(QuicPacketNumber(81)); |
| |
| EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); |
| EXPECT_EQ(0u, bytes_in_flight_); |
| } |
| |
| // Test the samples taken at the first flight of packets sent. |
| TEST_P(BandwidthSamplerTest, FirstRoundTrip) { |
| const QuicTime::Delta time_between_packets = |
| QuicTime::Delta::FromMilliseconds(1); |
| const QuicTime::Delta rtt = QuicTime::Delta::FromMilliseconds(800); |
| const int num_packets = 10; |
| const QuicByteCount num_bytes = kRegularPacketSize * num_packets; |
| const QuicBandwidth real_bandwidth = |
| QuicBandwidth::FromBytesAndTimeDelta(num_bytes, rtt); |
| |
| for (int i = 1; i <= 10; i++) { |
| SendPacket(i); |
| clock_.AdvanceTime(time_between_packets); |
| } |
| |
| clock_.AdvanceTime(rtt - num_packets * time_between_packets); |
| |
| QuicBandwidth last_sample = QuicBandwidth::Zero(); |
| for (int i = 1; i <= 10; i++) { |
| QuicBandwidth sample = AckPacket(i); |
| EXPECT_GT(sample, last_sample); |
| last_sample = sample; |
| clock_.AdvanceTime(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_P(BandwidthSamplerTest, RemoveObsoletePackets) { |
| SendPacket(1); |
| SendPacket(2); |
| SendPacket(3); |
| SendPacket(4); |
| SendPacket(5); |
| |
| clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(100)); |
| |
| EXPECT_EQ(5u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); |
| sampler_.RemoveObsoletePackets(QuicPacketNumber(4)); |
| EXPECT_EQ(2u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); |
| LosePacket(4); |
| sampler_.RemoveObsoletePackets(QuicPacketNumber(5)); |
| |
| EXPECT_EQ(1u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); |
| AckPacket(5); |
| |
| sampler_.RemoveObsoletePackets(QuicPacketNumber(6)); |
| |
| EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); |
| } |
| |
| TEST_P(BandwidthSamplerTest, NeuterPacket) { |
| SendPacket(1); |
| EXPECT_EQ(0u, sampler_.total_bytes_neutered()); |
| |
| clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(10)); |
| sampler_.OnPacketNeutered(QuicPacketNumber(1)); |
| EXPECT_LT(0u, sampler_.total_bytes_neutered()); |
| EXPECT_EQ(0u, sampler_.total_bytes_acked()); |
| |
| // If packet 1 is acked it should not produce a bandwidth sample. |
| clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(10)); |
| BandwidthSampler::CongestionEventSample sample = sampler_.OnCongestionEvent( |
| clock_.Now(), |
| {AckedPacket(QuicPacketNumber(1), kRegularPacketSize, clock_.Now())}, {}, |
| max_bandwidth_, est_bandwidth_upper_bound_, round_trip_count_); |
| EXPECT_EQ(0u, sampler_.total_bytes_acked()); |
| EXPECT_EQ(QuicBandwidth::Zero(), sample.sample_max_bandwidth); |
| EXPECT_FALSE(sample.sample_is_app_limited); |
| EXPECT_EQ(QuicTime::Delta::Infinite(), sample.sample_rtt); |
| EXPECT_EQ(0u, sample.sample_max_inflight); |
| EXPECT_EQ(0u, sample.extra_acked); |
| } |
| |
| TEST_P(BandwidthSamplerTest, CongestionEventSampleDefaultValues) { |
| // Make sure a default constructed CongestionEventSample has the correct |
| // initial values for BandwidthSampler::OnCongestionEvent() to work. |
| BandwidthSampler::CongestionEventSample sample; |
| |
| EXPECT_EQ(QuicBandwidth::Zero(), sample.sample_max_bandwidth); |
| EXPECT_FALSE(sample.sample_is_app_limited); |
| EXPECT_EQ(QuicTime::Delta::Infinite(), sample.sample_rtt); |
| EXPECT_EQ(0u, sample.sample_max_inflight); |
| EXPECT_EQ(0u, sample.extra_acked); |
| } |
| |
| // 1) Send 2 packets, 2) Ack both in 1 event, 3) Repeat. |
| TEST_P(BandwidthSamplerTest, TwoAckedPacketsPerEvent) { |
| QuicTime::Delta time_between_packets = QuicTime::Delta::FromMilliseconds(10); |
| QuicBandwidth sending_rate = QuicBandwidth::FromBytesAndTimeDelta( |
| kRegularPacketSize, time_between_packets); |
| |
| for (uint64_t i = 1; i < 21; i++) { |
| SendPacket(i); |
| clock_.AdvanceTime(time_between_packets); |
| if (i % 2 != 0) { |
| continue; |
| } |
| |
| BandwidthSampler::CongestionEventSample sample = |
| OnCongestionEvent({i - 1, i}, {}); |
| EXPECT_EQ(sending_rate, sample.sample_max_bandwidth); |
| EXPECT_EQ(time_between_packets, sample.sample_rtt); |
| EXPECT_EQ(2 * kRegularPacketSize, sample.sample_max_inflight); |
| EXPECT_TRUE(sample.last_packet_send_state.is_valid); |
| EXPECT_EQ(2 * kRegularPacketSize, |
| sample.last_packet_send_state.bytes_in_flight); |
| EXPECT_EQ(i * kRegularPacketSize, |
| sample.last_packet_send_state.total_bytes_sent); |
| EXPECT_EQ((i - 2) * kRegularPacketSize, |
| sample.last_packet_send_state.total_bytes_acked); |
| EXPECT_EQ(0u, sample.last_packet_send_state.total_bytes_lost); |
| sampler_.RemoveObsoletePackets(QuicPacketNumber(i - 2)); |
| } |
| } |
| |
| TEST_P(BandwidthSamplerTest, LoseEveryOtherPacket) { |
| QuicTime::Delta time_between_packets = QuicTime::Delta::FromMilliseconds(10); |
| QuicBandwidth sending_rate = QuicBandwidth::FromBytesAndTimeDelta( |
| kRegularPacketSize, time_between_packets); |
| |
| for (uint64_t i = 1; i < 21; i++) { |
| SendPacket(i); |
| clock_.AdvanceTime(time_between_packets); |
| if (i % 2 != 0) { |
| continue; |
| } |
| |
| // Ack packet i and lose i-1. |
| BandwidthSampler::CongestionEventSample sample = |
| OnCongestionEvent({i}, {i - 1}); |
| // Losing 50% packets means sending rate is twice the bandwidth. |
| EXPECT_EQ(sending_rate, sample.sample_max_bandwidth * 2); |
| EXPECT_EQ(time_between_packets, sample.sample_rtt); |
| EXPECT_EQ(kRegularPacketSize, sample.sample_max_inflight); |
| EXPECT_TRUE(sample.last_packet_send_state.is_valid); |
| EXPECT_EQ(2 * kRegularPacketSize, |
| sample.last_packet_send_state.bytes_in_flight); |
| EXPECT_EQ(i * kRegularPacketSize, |
| sample.last_packet_send_state.total_bytes_sent); |
| EXPECT_EQ((i - 2) * kRegularPacketSize / 2, |
| sample.last_packet_send_state.total_bytes_acked); |
| EXPECT_EQ((i - 2) * kRegularPacketSize / 2, |
| sample.last_packet_send_state.total_bytes_lost); |
| sampler_.RemoveObsoletePackets(QuicPacketNumber(i - 2)); |
| } |
| } |
| |
| TEST_P(BandwidthSamplerTest, AckHeightRespectBandwidthEstimateUpperBound) { |
| QuicTime::Delta time_between_packets = QuicTime::Delta::FromMilliseconds(10); |
| QuicBandwidth first_packet_sending_rate = |
| QuicBandwidth::FromBytesAndTimeDelta(kRegularPacketSize, |
| time_between_packets); |
| |
| // Send packets 1 to 4 and ack packet 1. |
| SendPacket(1); |
| clock_.AdvanceTime(time_between_packets); |
| SendPacket(2); |
| SendPacket(3); |
| SendPacket(4); |
| BandwidthSampler::CongestionEventSample sample = OnCongestionEvent({1}, {}); |
| EXPECT_EQ(first_packet_sending_rate, sample.sample_max_bandwidth); |
| EXPECT_EQ(first_packet_sending_rate, max_bandwidth_); |
| |
| // Ack packet 2, 3 and 4, all of which uses S(1) to calculate ack rate since |
| // there were no acks at the time they were sent. |
| round_trip_count_++; |
| est_bandwidth_upper_bound_ = first_packet_sending_rate * 0.3; |
| clock_.AdvanceTime(time_between_packets); |
| sample = OnCongestionEvent({2, 3, 4}, {}); |
| EXPECT_EQ(first_packet_sending_rate * 2, sample.sample_max_bandwidth); |
| EXPECT_EQ(max_bandwidth_, sample.sample_max_bandwidth); |
| |
| EXPECT_LT(2 * kRegularPacketSize, sample.extra_acked); |
| } |
| |
| class MaxAckHeightTrackerTest : public QuicTest { |
| protected: |
| MaxAckHeightTrackerTest() : tracker_(/*initial_filter_window=*/10) { |
| tracker_.SetAckAggregationBandwidthThreshold(1.8); |
| tracker_.SetStartNewAggregationEpochAfterFullRound(true); |
| } |
| |
| // Run a full aggregation episode, which is one or more aggregated acks, |
| // followed by a quiet period in which no ack happens. |
| // After this function returns, the time is set to the earliest point at which |
| // any ack event will cause tracker_.Update() to start a new aggregation. |
| void AggregationEpisode(QuicBandwidth aggregation_bandwidth, |
| QuicTime::Delta aggregation_duration, |
| QuicByteCount bytes_per_ack, |
| bool expect_new_aggregation_epoch) { |
| ASSERT_GE(aggregation_bandwidth, bandwidth_); |
| const QuicTime start_time = now_; |
| |
| const QuicByteCount aggregation_bytes = |
| aggregation_bandwidth * aggregation_duration; |
| |
| const int num_acks = aggregation_bytes / bytes_per_ack; |
| ASSERT_EQ(aggregation_bytes, num_acks * bytes_per_ack) |
| << "aggregation_bytes: " << aggregation_bytes << " [" |
| << aggregation_bandwidth << " in " << aggregation_duration |
| << "], bytes_per_ack: " << bytes_per_ack; |
| |
| const QuicTime::Delta time_between_acks = QuicTime::Delta::FromMicroseconds( |
| aggregation_duration.ToMicroseconds() / num_acks); |
| ASSERT_EQ(aggregation_duration, num_acks * time_between_acks) |
| << "aggregation_bytes: " << aggregation_bytes |
| << ", num_acks: " << num_acks |
| << ", time_between_acks: " << time_between_acks; |
| |
| // The total duration of aggregation time and quiet period. |
| const QuicTime::Delta total_duration = QuicTime::Delta::FromMicroseconds( |
| aggregation_bytes * 8 * 1000000 / bandwidth_.ToBitsPerSecond()); |
| ASSERT_EQ(aggregation_bytes, total_duration * bandwidth_) |
| << "total_duration: " << total_duration |
| << ", bandwidth_: " << bandwidth_; |
| |
| QuicByteCount last_extra_acked = 0; |
| for (QuicByteCount bytes = 0; bytes < aggregation_bytes; |
| bytes += bytes_per_ack) { |
| QuicByteCount extra_acked = tracker_.Update( |
| bandwidth_, true, RoundTripCount(), last_sent_packet_number_, |
| last_acked_packet_number_, now_, bytes_per_ack); |
| QUIC_VLOG(1) << "T" << now_ << ": Update after " << bytes_per_ack |
| << " bytes acked, " << extra_acked << " extra bytes acked"; |
| // |extra_acked| should be 0 if either |
| // [1] We are at the beginning of a aggregation epoch(bytes==0) and the |
| // the current tracker implementation can identify it, or |
| // [2] We are not really aggregating acks. |
| if ((bytes == 0 && expect_new_aggregation_epoch) || // [1] |
| (aggregation_bandwidth == bandwidth_)) { // [2] |
| EXPECT_EQ(0u, extra_acked); |
| } else { |
| EXPECT_LT(last_extra_acked, extra_acked); |
| } |
| now_ = now_ + time_between_acks; |
| last_extra_acked = extra_acked; |
| } |
| |
| // Advance past the quiet period. |
| const QuicTime time_after_aggregation = now_; |
| now_ = start_time + total_duration; |
| QUIC_VLOG(1) << "Advanced time from " << time_after_aggregation << " to " |
| << now_ << ". Aggregation time[" |
| << (time_after_aggregation - start_time) << "], Quiet time[" |
| << (now_ - time_after_aggregation) << "]."; |
| } |
| |
| QuicRoundTripCount RoundTripCount() const { |
| return (now_ - QuicTime::Zero()).ToMicroseconds() / rtt_.ToMicroseconds(); |
| } |
| |
| MaxAckHeightTracker tracker_; |
| QuicBandwidth bandwidth_ = QuicBandwidth::FromBytesPerSecond(10 * 1000); |
| QuicTime now_ = QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(1); |
| QuicTime::Delta rtt_ = QuicTime::Delta::FromMilliseconds(60); |
| QuicPacketNumber last_sent_packet_number_; |
| QuicPacketNumber last_acked_packet_number_; |
| }; |
| |
| TEST_F(MaxAckHeightTrackerTest, VeryAggregatedLargeAck) { |
| AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6), |
| 1200, true); |
| AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6), |
| 1200, true); |
| now_ = now_ - QuicTime::Delta::FromMilliseconds(1); |
| |
| if (tracker_.ack_aggregation_bandwidth_threshold() > 1.1) { |
| AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6), |
| 1200, true); |
| EXPECT_EQ(3u, tracker_.num_ack_aggregation_epochs()); |
| } else { |
| AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6), |
| 1200, false); |
| EXPECT_EQ(2u, tracker_.num_ack_aggregation_epochs()); |
| } |
| } |
| |
| TEST_F(MaxAckHeightTrackerTest, VeryAggregatedSmallAcks) { |
| AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6), 300, |
| true); |
| AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6), 300, |
| true); |
| now_ = now_ - QuicTime::Delta::FromMilliseconds(1); |
| |
| if (tracker_.ack_aggregation_bandwidth_threshold() > 1.1) { |
| AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6), |
| 300, true); |
| EXPECT_EQ(3u, tracker_.num_ack_aggregation_epochs()); |
| } else { |
| AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6), |
| 300, false); |
| EXPECT_EQ(2u, tracker_.num_ack_aggregation_epochs()); |
| } |
| } |
| |
| TEST_F(MaxAckHeightTrackerTest, SomewhatAggregatedLargeAck) { |
| AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50), |
| 1000, true); |
| AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50), |
| 1000, true); |
| now_ = now_ - QuicTime::Delta::FromMilliseconds(1); |
| |
| if (tracker_.ack_aggregation_bandwidth_threshold() > 1.1) { |
| AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50), |
| 1000, true); |
| EXPECT_EQ(3u, tracker_.num_ack_aggregation_epochs()); |
| } else { |
| AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50), |
| 1000, false); |
| EXPECT_EQ(2u, tracker_.num_ack_aggregation_epochs()); |
| } |
| } |
| |
| TEST_F(MaxAckHeightTrackerTest, SomewhatAggregatedSmallAcks) { |
| AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50), 100, |
| true); |
| AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50), 100, |
| true); |
| now_ = now_ - QuicTime::Delta::FromMilliseconds(1); |
| |
| if (tracker_.ack_aggregation_bandwidth_threshold() > 1.1) { |
| AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50), |
| 100, true); |
| EXPECT_EQ(3u, tracker_.num_ack_aggregation_epochs()); |
| } else { |
| AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50), |
| 100, false); |
| EXPECT_EQ(2u, tracker_.num_ack_aggregation_epochs()); |
| } |
| } |
| |
| TEST_F(MaxAckHeightTrackerTest, NotAggregated) { |
| AggregationEpisode(bandwidth_, QuicTime::Delta::FromMilliseconds(100), 100, |
| true); |
| EXPECT_LT(2u, tracker_.num_ack_aggregation_epochs()); |
| } |
| |
| TEST_F(MaxAckHeightTrackerTest, StartNewEpochAfterAFullRound) { |
| last_sent_packet_number_ = QuicPacketNumber(10); |
| AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50), 100, |
| true); |
| |
| last_acked_packet_number_ = QuicPacketNumber(11); |
| // Update with a tiny bandwidth causes a very low expected bytes acked, which |
| // in turn causes the current epoch to continue if the |tracker_| doesn't |
| // check the packet numbers. |
| tracker_.Update(bandwidth_ * 0.1, true, RoundTripCount(), |
| last_sent_packet_number_, last_acked_packet_number_, now_, |
| 100); |
| |
| EXPECT_EQ(2u, tracker_.num_ack_aggregation_epochs()); |
| } |
| |
| } // namespace test |
| } // namespace quic |