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 "quiche/quic/core/congestion_control/bandwidth_sampler.h"
6 
7 #include <cstdint>
8 #include <set>
9 
10 #include "quiche/quic/core/quic_bandwidth.h"
11 #include "quiche/quic/core/quic_time.h"
12 #include "quiche/quic/core/quic_types.h"
13 #include "quiche/quic/platform/api/quic_flags.h"
14 #include "quiche/quic/platform/api/quic_logging.h"
15 #include "quiche/quic/platform/api/quic_test.h"
16 #include "quiche/quic/test_tools/mock_clock.h"
17 
18 namespace quic {
19 namespace test {
20 
21 class BandwidthSamplerPeer {
22  public:
GetNumberOfTrackedPackets(const BandwidthSampler & sampler)23   static size_t GetNumberOfTrackedPackets(const BandwidthSampler& sampler) {
24     return sampler.connection_state_map_.number_of_present_entries();
25   }
26 
GetPacketSize(const BandwidthSampler & sampler,QuicPacketNumber packet_number)27   static QuicByteCount GetPacketSize(const BandwidthSampler& sampler,
28                                      QuicPacketNumber packet_number) {
29     return sampler.connection_state_map_.GetEntry(packet_number)->size();
30   }
31 };
32 
33 const QuicByteCount kRegularPacketSize = 1280;
34 // Enforce divisibility for some of the tests.
35 static_assert((kRegularPacketSize & 31) == 0,
36               "kRegularPacketSize has to be five times divisible by 2");
37 
38 struct TestParameters {
39   bool overestimate_avoidance;
40 };
41 
42 // Used by ::testing::PrintToStringParamName().
PrintToString(const TestParameters & p)43 std::string PrintToString(const TestParameters& p) {
44   return p.overestimate_avoidance ? "enable_overestimate_avoidance"
45                                   : "no_enable_overestimate_avoidance";
46 }
47 
48 // A test fixture with utility methods for BandwidthSampler tests.
49 class BandwidthSamplerTest : public QuicTestWithParam<TestParameters> {
50  protected:
BandwidthSamplerTest()51   BandwidthSamplerTest()
52       : sampler_(nullptr, /*max_height_tracker_window_length=*/0),
53         sampler_app_limited_at_start_(sampler_.is_app_limited()),
54         bytes_in_flight_(0),
55         max_bandwidth_(QuicBandwidth::Zero()),
56         est_bandwidth_upper_bound_(QuicBandwidth::Infinite()),
57         round_trip_count_(0) {
58     // Ensure that the clock does not start at zero.
59     clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1));
60     if (GetParam().overestimate_avoidance) {
61       sampler_.EnableOverestimateAvoidance();
62     }
63   }
64 
65   MockClock clock_;
66   BandwidthSampler sampler_;
67   bool sampler_app_limited_at_start_;
68   QuicByteCount bytes_in_flight_;
69   QuicBandwidth max_bandwidth_;  // Max observed bandwidth from acks.
70   QuicBandwidth est_bandwidth_upper_bound_;
71   QuicRoundTripCount round_trip_count_;  // Needed to calculate extra_acked.
72 
PacketsToBytes(QuicPacketCount packet_count)73   QuicByteCount PacketsToBytes(QuicPacketCount packet_count) {
74     return packet_count * kRegularPacketSize;
75   }
76 
SendPacketInner(uint64_t packet_number,QuicByteCount bytes,HasRetransmittableData has_retransmittable_data)77   void SendPacketInner(uint64_t packet_number, QuicByteCount bytes,
78                        HasRetransmittableData has_retransmittable_data) {
79     sampler_.OnPacketSent(clock_.Now(), QuicPacketNumber(packet_number), bytes,
80                           bytes_in_flight_, has_retransmittable_data);
81     if (has_retransmittable_data == HAS_RETRANSMITTABLE_DATA) {
82       bytes_in_flight_ += bytes;
83     }
84   }
85 
SendPacket(uint64_t packet_number)86   void SendPacket(uint64_t packet_number) {
87     SendPacketInner(packet_number, kRegularPacketSize,
88                     HAS_RETRANSMITTABLE_DATA);
89   }
90 
AckPacketInner(uint64_t packet_number)91   BandwidthSample AckPacketInner(uint64_t packet_number) {
92     QuicByteCount size = BandwidthSamplerPeer::GetPacketSize(
93         sampler_, QuicPacketNumber(packet_number));
94     bytes_in_flight_ -= size;
95     BandwidthSampler::CongestionEventSample sample = sampler_.OnCongestionEvent(
96         clock_.Now(), {MakeAckedPacket(packet_number)}, {}, max_bandwidth_,
97         est_bandwidth_upper_bound_, round_trip_count_);
98     max_bandwidth_ = std::max(max_bandwidth_, sample.sample_max_bandwidth);
99     BandwidthSample bandwidth_sample;
100     bandwidth_sample.bandwidth = sample.sample_max_bandwidth;
101     bandwidth_sample.rtt = sample.sample_rtt;
102     bandwidth_sample.state_at_send = sample.last_packet_send_state;
103     EXPECT_TRUE(bandwidth_sample.state_at_send.is_valid);
104     return bandwidth_sample;
105   }
106 
MakeAckedPacket(uint64_t packet_number) const107   AckedPacket MakeAckedPacket(uint64_t packet_number) const {
108     QuicByteCount size = BandwidthSamplerPeer::GetPacketSize(
109         sampler_, QuicPacketNumber(packet_number));
110     return AckedPacket(QuicPacketNumber(packet_number), size, clock_.Now());
111   }
112 
MakeLostPacket(uint64_t packet_number) const113   LostPacket MakeLostPacket(uint64_t packet_number) const {
114     return LostPacket(QuicPacketNumber(packet_number),
115                       BandwidthSamplerPeer::GetPacketSize(
116                           sampler_, QuicPacketNumber(packet_number)));
117   }
118 
119   // Acknowledge receipt of a packet and expect it to be not app-limited.
AckPacket(uint64_t packet_number)120   QuicBandwidth AckPacket(uint64_t packet_number) {
121     BandwidthSample sample = AckPacketInner(packet_number);
122     return sample.bandwidth;
123   }
124 
OnCongestionEvent(std::set<uint64_t> acked_packet_numbers,std::set<uint64_t> lost_packet_numbers)125   BandwidthSampler::CongestionEventSample OnCongestionEvent(
126       std::set<uint64_t> acked_packet_numbers,
127       std::set<uint64_t> lost_packet_numbers) {
128     AckedPacketVector acked_packets;
129     for (auto it = acked_packet_numbers.begin();
130          it != acked_packet_numbers.end(); ++it) {
131       acked_packets.push_back(MakeAckedPacket(*it));
132       bytes_in_flight_ -= acked_packets.back().bytes_acked;
133     }
134 
135     LostPacketVector lost_packets;
136     for (auto it = lost_packet_numbers.begin(); it != lost_packet_numbers.end();
137          ++it) {
138       lost_packets.push_back(MakeLostPacket(*it));
139       bytes_in_flight_ -= lost_packets.back().bytes_lost;
140     }
141 
142     BandwidthSampler::CongestionEventSample sample = sampler_.OnCongestionEvent(
143         clock_.Now(), acked_packets, lost_packets, max_bandwidth_,
144         est_bandwidth_upper_bound_, round_trip_count_);
145     max_bandwidth_ = std::max(max_bandwidth_, sample.sample_max_bandwidth);
146     return sample;
147   }
148 
LosePacket(uint64_t packet_number)149   SendTimeState LosePacket(uint64_t packet_number) {
150     QuicByteCount size = BandwidthSamplerPeer::GetPacketSize(
151         sampler_, QuicPacketNumber(packet_number));
152     bytes_in_flight_ -= size;
153     LostPacket lost_packet(QuicPacketNumber(packet_number), size);
154     BandwidthSampler::CongestionEventSample sample = sampler_.OnCongestionEvent(
155         clock_.Now(), {}, {lost_packet}, max_bandwidth_,
156         est_bandwidth_upper_bound_, round_trip_count_);
157     EXPECT_TRUE(sample.last_packet_send_state.is_valid);
158     EXPECT_EQ(sample.sample_max_bandwidth, QuicBandwidth::Zero());
159     EXPECT_EQ(sample.sample_rtt, QuicTime::Delta::Infinite());
160     return sample.last_packet_send_state;
161   }
162 
163   // Sends one packet and acks it.  Then, send 20 packets.  Finally, send
164   // another 20 packets while acknowledging previous 20.
Send40PacketsAndAckFirst20(QuicTime::Delta time_between_packets)165   void Send40PacketsAndAckFirst20(QuicTime::Delta time_between_packets) {
166     // Send 20 packets at a constant inter-packet time.
167     for (int i = 1; i <= 20; i++) {
168       SendPacket(i);
169       clock_.AdvanceTime(time_between_packets);
170     }
171 
172     // Ack packets 1 to 20, while sending new packets at the same rate as
173     // before.
174     for (int i = 1; i <= 20; i++) {
175       AckPacket(i);
176       SendPacket(i + 20);
177       clock_.AdvanceTime(time_between_packets);
178     }
179   }
180 };
181 
182 INSTANTIATE_TEST_SUITE_P(
183     BandwidthSamplerTests, BandwidthSamplerTest,
184     testing::Values(TestParameters{/*overestimate_avoidance=*/false},
185                     TestParameters{/*overestimate_avoidance=*/true}),
186     testing::PrintToStringParamName());
187 
188 // Test the sampler in a simple stop-and-wait sender setting.
TEST_P(BandwidthSamplerTest,SendAndWait)189 TEST_P(BandwidthSamplerTest, SendAndWait) {
190   QuicTime::Delta time_between_packets = QuicTime::Delta::FromMilliseconds(10);
191   QuicBandwidth expected_bandwidth =
192       QuicBandwidth::FromBytesPerSecond(kRegularPacketSize * 100);
193 
194   // Send packets at the constant bandwidth.
195   for (int i = 1; i < 20; i++) {
196     SendPacket(i);
197     clock_.AdvanceTime(time_between_packets);
198     QuicBandwidth current_sample = AckPacket(i);
199     EXPECT_EQ(expected_bandwidth, current_sample);
200   }
201 
202   // Send packets at the exponentially decreasing bandwidth.
203   for (int i = 20; i < 25; i++) {
204     time_between_packets = time_between_packets * 2;
205     expected_bandwidth = expected_bandwidth * 0.5;
206 
207     SendPacket(i);
208     clock_.AdvanceTime(time_between_packets);
209     QuicBandwidth current_sample = AckPacket(i);
210     EXPECT_EQ(expected_bandwidth, current_sample);
211   }
212   sampler_.RemoveObsoletePackets(QuicPacketNumber(25));
213 
214   EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
215   EXPECT_EQ(0u, bytes_in_flight_);
216 }
217 
TEST_P(BandwidthSamplerTest,SendTimeState)218 TEST_P(BandwidthSamplerTest, SendTimeState) {
219   QuicTime::Delta time_between_packets = QuicTime::Delta::FromMilliseconds(10);
220 
221   // Send packets 1-5.
222   for (int i = 1; i <= 5; i++) {
223     SendPacket(i);
224     EXPECT_EQ(PacketsToBytes(i), sampler_.total_bytes_sent());
225     clock_.AdvanceTime(time_between_packets);
226   }
227 
228   // Ack packet 1.
229   SendTimeState send_time_state = AckPacketInner(1).state_at_send;
230   EXPECT_EQ(PacketsToBytes(1), send_time_state.total_bytes_sent);
231   EXPECT_EQ(0u, send_time_state.total_bytes_acked);
232   EXPECT_EQ(0u, send_time_state.total_bytes_lost);
233   EXPECT_EQ(PacketsToBytes(1), sampler_.total_bytes_acked());
234 
235   // Lose packet 2.
236   send_time_state = LosePacket(2);
237   EXPECT_EQ(PacketsToBytes(2), send_time_state.total_bytes_sent);
238   EXPECT_EQ(0u, send_time_state.total_bytes_acked);
239   EXPECT_EQ(0u, send_time_state.total_bytes_lost);
240   EXPECT_EQ(PacketsToBytes(1), sampler_.total_bytes_lost());
241 
242   // Lose packet 3.
243   send_time_state = LosePacket(3);
244   EXPECT_EQ(PacketsToBytes(3), send_time_state.total_bytes_sent);
245   EXPECT_EQ(0u, send_time_state.total_bytes_acked);
246   EXPECT_EQ(0u, send_time_state.total_bytes_lost);
247   EXPECT_EQ(PacketsToBytes(2), sampler_.total_bytes_lost());
248 
249   // Send packets 6-10.
250   for (int i = 6; i <= 10; i++) {
251     SendPacket(i);
252     EXPECT_EQ(PacketsToBytes(i), sampler_.total_bytes_sent());
253     clock_.AdvanceTime(time_between_packets);
254   }
255 
256   // Ack all inflight packets.
257   QuicPacketCount acked_packet_count = 1;
258   EXPECT_EQ(PacketsToBytes(acked_packet_count), sampler_.total_bytes_acked());
259   for (int i = 4; i <= 10; i++) {
260     send_time_state = AckPacketInner(i).state_at_send;
261     ++acked_packet_count;
262     EXPECT_EQ(PacketsToBytes(acked_packet_count), sampler_.total_bytes_acked());
263     EXPECT_EQ(PacketsToBytes(i), send_time_state.total_bytes_sent);
264     if (i <= 5) {
265       EXPECT_EQ(0u, send_time_state.total_bytes_acked);
266       EXPECT_EQ(0u, send_time_state.total_bytes_lost);
267     } else {
268       EXPECT_EQ(PacketsToBytes(1), send_time_state.total_bytes_acked);
269       EXPECT_EQ(PacketsToBytes(2), send_time_state.total_bytes_lost);
270     }
271 
272     // This equation works because there is no neutered bytes.
273     EXPECT_EQ(send_time_state.total_bytes_sent -
274                   send_time_state.total_bytes_acked -
275                   send_time_state.total_bytes_lost,
276               send_time_state.bytes_in_flight);
277 
278     clock_.AdvanceTime(time_between_packets);
279   }
280 }
281 
282 // Test the sampler during regular windowed sender scenario with fixed
283 // CWND of 20.
TEST_P(BandwidthSamplerTest,SendPaced)284 TEST_P(BandwidthSamplerTest, SendPaced) {
285   const QuicTime::Delta time_between_packets =
286       QuicTime::Delta::FromMilliseconds(1);
287   QuicBandwidth expected_bandwidth =
288       QuicBandwidth::FromKBytesPerSecond(kRegularPacketSize);
289 
290   Send40PacketsAndAckFirst20(time_between_packets);
291 
292   // Ack the packets 21 to 40, arriving at the correct bandwidth.
293   QuicBandwidth last_bandwidth = QuicBandwidth::Zero();
294   for (int i = 21; i <= 40; i++) {
295     last_bandwidth = AckPacket(i);
296     EXPECT_EQ(expected_bandwidth, last_bandwidth) << "i is " << i;
297     clock_.AdvanceTime(time_between_packets);
298   }
299   sampler_.RemoveObsoletePackets(QuicPacketNumber(41));
300 
301   EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
302   EXPECT_EQ(0u, bytes_in_flight_);
303 }
304 
305 // Test the sampler in a scenario where 50% of packets is consistently lost.
TEST_P(BandwidthSamplerTest,SendWithLosses)306 TEST_P(BandwidthSamplerTest, SendWithLosses) {
307   const QuicTime::Delta time_between_packets =
308       QuicTime::Delta::FromMilliseconds(1);
309   QuicBandwidth expected_bandwidth =
310       QuicBandwidth::FromKBytesPerSecond(kRegularPacketSize) * 0.5;
311 
312   // Send 20 packets, each 1 ms apart.
313   for (int i = 1; i <= 20; i++) {
314     SendPacket(i);
315     clock_.AdvanceTime(time_between_packets);
316   }
317 
318   // Ack packets 1 to 20, losing every even-numbered packet, while sending new
319   // packets at the same rate as before.
320   for (int i = 1; i <= 20; i++) {
321     if (i % 2 == 0) {
322       AckPacket(i);
323     } else {
324       LosePacket(i);
325     }
326     SendPacket(i + 20);
327     clock_.AdvanceTime(time_between_packets);
328   }
329 
330   // Ack the packets 21 to 40 with the same loss pattern.
331   QuicBandwidth last_bandwidth = QuicBandwidth::Zero();
332   for (int i = 21; i <= 40; i++) {
333     if (i % 2 == 0) {
334       last_bandwidth = AckPacket(i);
335       EXPECT_EQ(expected_bandwidth, last_bandwidth);
336     } else {
337       LosePacket(i);
338     }
339     clock_.AdvanceTime(time_between_packets);
340   }
341   sampler_.RemoveObsoletePackets(QuicPacketNumber(41));
342 
343   EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
344   EXPECT_EQ(0u, bytes_in_flight_);
345 }
346 
347 // Test the sampler in a scenario where the 50% of packets are not
348 // congestion controlled (specifically, non-retransmittable data is not
349 // congestion controlled).  Should be functionally consistent in behavior with
350 // the SendWithLosses test.
TEST_P(BandwidthSamplerTest,NotCongestionControlled)351 TEST_P(BandwidthSamplerTest, NotCongestionControlled) {
352   const QuicTime::Delta time_between_packets =
353       QuicTime::Delta::FromMilliseconds(1);
354   QuicBandwidth expected_bandwidth =
355       QuicBandwidth::FromKBytesPerSecond(kRegularPacketSize) * 0.5;
356 
357   // Send 20 packets, each 1 ms apart. Every even packet is not congestion
358   // controlled.
359   for (int i = 1; i <= 20; i++) {
360     SendPacketInner(
361         i, kRegularPacketSize,
362         i % 2 == 0 ? HAS_RETRANSMITTABLE_DATA : NO_RETRANSMITTABLE_DATA);
363     clock_.AdvanceTime(time_between_packets);
364   }
365 
366   // Ensure only congestion controlled packets are tracked.
367   EXPECT_EQ(10u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
368 
369   // Ack packets 2 to 21, ignoring every even-numbered packet, while sending new
370   // packets at the same rate as before.
371   for (int i = 1; i <= 20; i++) {
372     if (i % 2 == 0) {
373       AckPacket(i);
374     }
375     SendPacketInner(
376         i + 20, kRegularPacketSize,
377         i % 2 == 0 ? HAS_RETRANSMITTABLE_DATA : NO_RETRANSMITTABLE_DATA);
378     clock_.AdvanceTime(time_between_packets);
379   }
380 
381   // Ack the packets 22 to 41 with the same congestion controlled pattern.
382   QuicBandwidth last_bandwidth = QuicBandwidth::Zero();
383   for (int i = 21; i <= 40; i++) {
384     if (i % 2 == 0) {
385       last_bandwidth = AckPacket(i);
386       EXPECT_EQ(expected_bandwidth, last_bandwidth);
387     }
388     clock_.AdvanceTime(time_between_packets);
389   }
390   sampler_.RemoveObsoletePackets(QuicPacketNumber(41));
391 
392   // Since only congestion controlled packets are entered into the map, it has
393   // to be empty at this point.
394   EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
395   EXPECT_EQ(0u, bytes_in_flight_);
396 }
397 
398 // Simulate a situation where ACKs arrive in burst and earlier than usual, thus
399 // producing an ACK rate which is higher than the original send rate.
TEST_P(BandwidthSamplerTest,CompressedAck)400 TEST_P(BandwidthSamplerTest, CompressedAck) {
401   const QuicTime::Delta time_between_packets =
402       QuicTime::Delta::FromMilliseconds(1);
403   QuicBandwidth expected_bandwidth =
404       QuicBandwidth::FromKBytesPerSecond(kRegularPacketSize);
405 
406   Send40PacketsAndAckFirst20(time_between_packets);
407 
408   // Simulate an RTT somewhat lower than the one for 1-to-21 transmission.
409   clock_.AdvanceTime(time_between_packets * 15);
410 
411   // Ack the packets 21 to 40 almost immediately at once.
412   QuicBandwidth last_bandwidth = QuicBandwidth::Zero();
413   QuicTime::Delta ridiculously_small_time_delta =
414       QuicTime::Delta::FromMicroseconds(20);
415   for (int i = 21; i <= 40; i++) {
416     last_bandwidth = AckPacket(i);
417     clock_.AdvanceTime(ridiculously_small_time_delta);
418   }
419   EXPECT_EQ(expected_bandwidth, last_bandwidth);
420 
421   sampler_.RemoveObsoletePackets(QuicPacketNumber(41));
422 
423   EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
424   EXPECT_EQ(0u, bytes_in_flight_);
425 }
426 
427 // Tests receiving ACK packets in the reverse order.
TEST_P(BandwidthSamplerTest,ReorderedAck)428 TEST_P(BandwidthSamplerTest, ReorderedAck) {
429   const QuicTime::Delta time_between_packets =
430       QuicTime::Delta::FromMilliseconds(1);
431   QuicBandwidth expected_bandwidth =
432       QuicBandwidth::FromKBytesPerSecond(kRegularPacketSize);
433 
434   Send40PacketsAndAckFirst20(time_between_packets);
435 
436   // Ack the packets 21 to 40 in the reverse order, while sending packets 41 to
437   // 60.
438   QuicBandwidth last_bandwidth = QuicBandwidth::Zero();
439   for (int i = 0; i < 20; i++) {
440     last_bandwidth = AckPacket(40 - i);
441     EXPECT_EQ(expected_bandwidth, last_bandwidth);
442     SendPacket(41 + i);
443     clock_.AdvanceTime(time_between_packets);
444   }
445 
446   // Ack the packets 41 to 60, now in the regular order.
447   for (int i = 41; i <= 60; i++) {
448     last_bandwidth = AckPacket(i);
449     EXPECT_EQ(expected_bandwidth, last_bandwidth);
450     clock_.AdvanceTime(time_between_packets);
451   }
452   sampler_.RemoveObsoletePackets(QuicPacketNumber(61));
453 
454   EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
455   EXPECT_EQ(0u, bytes_in_flight_);
456 }
457 
458 // Test the app-limited logic.
TEST_P(BandwidthSamplerTest,AppLimited)459 TEST_P(BandwidthSamplerTest, AppLimited) {
460   const QuicTime::Delta time_between_packets =
461       QuicTime::Delta::FromMilliseconds(1);
462   QuicBandwidth expected_bandwidth =
463       QuicBandwidth::FromKBytesPerSecond(kRegularPacketSize);
464 
465   // Send 20 packets at a constant inter-packet time.
466   for (int i = 1; i <= 20; i++) {
467     SendPacket(i);
468     clock_.AdvanceTime(time_between_packets);
469   }
470 
471   // Ack packets 1 to 20, while sending new packets at the same rate as
472   // before.
473   for (int i = 1; i <= 20; i++) {
474     BandwidthSample sample = AckPacketInner(i);
475     EXPECT_EQ(sample.state_at_send.is_app_limited,
476               sampler_app_limited_at_start_);
477     SendPacket(i + 20);
478     clock_.AdvanceTime(time_between_packets);
479   }
480 
481   // We are now app-limited. Ack 21 to 40 as usual, but do not send anything for
482   // now.
483   sampler_.OnAppLimited();
484   for (int i = 21; i <= 40; i++) {
485     BandwidthSample sample = AckPacketInner(i);
486     EXPECT_FALSE(sample.state_at_send.is_app_limited);
487     EXPECT_EQ(expected_bandwidth, sample.bandwidth);
488     clock_.AdvanceTime(time_between_packets);
489   }
490 
491   // Enter quiescence.
492   clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1));
493 
494   // Send packets 41 to 60, all of which would be marked as app-limited.
495   for (int i = 41; i <= 60; i++) {
496     SendPacket(i);
497     clock_.AdvanceTime(time_between_packets);
498   }
499 
500   // Ack packets 41 to 60, while sending packets 61 to 80.  41 to 60 should be
501   // app-limited and underestimate the bandwidth due to that.
502   for (int i = 41; i <= 60; i++) {
503     BandwidthSample sample = AckPacketInner(i);
504     EXPECT_TRUE(sample.state_at_send.is_app_limited);
505     EXPECT_LT(sample.bandwidth, 0.7f * expected_bandwidth);
506 
507     SendPacket(i + 20);
508     clock_.AdvanceTime(time_between_packets);
509   }
510 
511   // Run out of packets, and then ack packet 61 to 80, all of which should have
512   // correct non-app-limited samples.
513   for (int i = 61; i <= 80; i++) {
514     BandwidthSample sample = AckPacketInner(i);
515     EXPECT_FALSE(sample.state_at_send.is_app_limited);
516     EXPECT_EQ(sample.bandwidth, expected_bandwidth);
517     clock_.AdvanceTime(time_between_packets);
518   }
519   sampler_.RemoveObsoletePackets(QuicPacketNumber(81));
520 
521   EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
522   EXPECT_EQ(0u, bytes_in_flight_);
523 }
524 
525 // Test the samples taken at the first flight of packets sent.
TEST_P(BandwidthSamplerTest,FirstRoundTrip)526 TEST_P(BandwidthSamplerTest, FirstRoundTrip) {
527   const QuicTime::Delta time_between_packets =
528       QuicTime::Delta::FromMilliseconds(1);
529   const QuicTime::Delta rtt = QuicTime::Delta::FromMilliseconds(800);
530   const int num_packets = 10;
531   const QuicByteCount num_bytes = kRegularPacketSize * num_packets;
532   const QuicBandwidth real_bandwidth =
533       QuicBandwidth::FromBytesAndTimeDelta(num_bytes, rtt);
534 
535   for (int i = 1; i <= 10; i++) {
536     SendPacket(i);
537     clock_.AdvanceTime(time_between_packets);
538   }
539 
540   clock_.AdvanceTime(rtt - num_packets * time_between_packets);
541 
542   QuicBandwidth last_sample = QuicBandwidth::Zero();
543   for (int i = 1; i <= 10; i++) {
544     QuicBandwidth sample = AckPacket(i);
545     EXPECT_GT(sample, last_sample);
546     last_sample = sample;
547     clock_.AdvanceTime(time_between_packets);
548   }
549 
550   // The final measured sample for the first flight of sample is expected to be
551   // smaller than the real bandwidth, yet it should not lose more than 10%. The
552   // specific value of the error depends on the difference between the RTT and
553   // the time it takes to exhaust the congestion window (i.e. in the limit when
554   // all packets are sent simultaneously, last sample would indicate the real
555   // bandwidth).
556   EXPECT_LT(last_sample, real_bandwidth);
557   EXPECT_GT(last_sample, 0.9f * real_bandwidth);
558 }
559 
560 // Test sampler's ability to remove obsolete packets.
TEST_P(BandwidthSamplerTest,RemoveObsoletePackets)561 TEST_P(BandwidthSamplerTest, RemoveObsoletePackets) {
562   SendPacket(1);
563   SendPacket(2);
564   SendPacket(3);
565   SendPacket(4);
566   SendPacket(5);
567 
568   clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(100));
569 
570   EXPECT_EQ(5u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
571   sampler_.RemoveObsoletePackets(QuicPacketNumber(4));
572   EXPECT_EQ(2u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
573   LosePacket(4);
574   sampler_.RemoveObsoletePackets(QuicPacketNumber(5));
575 
576   EXPECT_EQ(1u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
577   AckPacket(5);
578 
579   sampler_.RemoveObsoletePackets(QuicPacketNumber(6));
580 
581   EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
582 }
583 
TEST_P(BandwidthSamplerTest,NeuterPacket)584 TEST_P(BandwidthSamplerTest, NeuterPacket) {
585   SendPacket(1);
586   EXPECT_EQ(0u, sampler_.total_bytes_neutered());
587 
588   clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(10));
589   sampler_.OnPacketNeutered(QuicPacketNumber(1));
590   EXPECT_LT(0u, sampler_.total_bytes_neutered());
591   EXPECT_EQ(0u, sampler_.total_bytes_acked());
592 
593   // If packet 1 is acked it should not produce a bandwidth sample.
594   clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(10));
595   BandwidthSampler::CongestionEventSample sample = sampler_.OnCongestionEvent(
596       clock_.Now(),
597       {AckedPacket(QuicPacketNumber(1), kRegularPacketSize, clock_.Now())}, {},
598       max_bandwidth_, est_bandwidth_upper_bound_, round_trip_count_);
599   EXPECT_EQ(0u, sampler_.total_bytes_acked());
600   EXPECT_EQ(QuicBandwidth::Zero(), sample.sample_max_bandwidth);
601   EXPECT_FALSE(sample.sample_is_app_limited);
602   EXPECT_EQ(QuicTime::Delta::Infinite(), sample.sample_rtt);
603   EXPECT_EQ(0u, sample.sample_max_inflight);
604   EXPECT_EQ(0u, sample.extra_acked);
605 }
606 
TEST_P(BandwidthSamplerTest,CongestionEventSampleDefaultValues)607 TEST_P(BandwidthSamplerTest, CongestionEventSampleDefaultValues) {
608   // Make sure a default constructed CongestionEventSample has the correct
609   // initial values for BandwidthSampler::OnCongestionEvent() to work.
610   BandwidthSampler::CongestionEventSample sample;
611 
612   EXPECT_EQ(QuicBandwidth::Zero(), sample.sample_max_bandwidth);
613   EXPECT_FALSE(sample.sample_is_app_limited);
614   EXPECT_EQ(QuicTime::Delta::Infinite(), sample.sample_rtt);
615   EXPECT_EQ(0u, sample.sample_max_inflight);
616   EXPECT_EQ(0u, sample.extra_acked);
617 }
618 
619 // 1) Send 2 packets, 2) Ack both in 1 event, 3) Repeat.
TEST_P(BandwidthSamplerTest,TwoAckedPacketsPerEvent)620 TEST_P(BandwidthSamplerTest, TwoAckedPacketsPerEvent) {
621   QuicTime::Delta time_between_packets = QuicTime::Delta::FromMilliseconds(10);
622   QuicBandwidth sending_rate = QuicBandwidth::FromBytesAndTimeDelta(
623       kRegularPacketSize, time_between_packets);
624 
625   for (uint64_t i = 1; i < 21; i++) {
626     SendPacket(i);
627     clock_.AdvanceTime(time_between_packets);
628     if (i % 2 != 0) {
629       continue;
630     }
631 
632     BandwidthSampler::CongestionEventSample sample =
633         OnCongestionEvent({i - 1, i}, {});
634     EXPECT_EQ(sending_rate, sample.sample_max_bandwidth);
635     EXPECT_EQ(time_between_packets, sample.sample_rtt);
636     EXPECT_EQ(2 * kRegularPacketSize, sample.sample_max_inflight);
637     EXPECT_TRUE(sample.last_packet_send_state.is_valid);
638     EXPECT_EQ(2 * kRegularPacketSize,
639               sample.last_packet_send_state.bytes_in_flight);
640     EXPECT_EQ(i * kRegularPacketSize,
641               sample.last_packet_send_state.total_bytes_sent);
642     EXPECT_EQ((i - 2) * kRegularPacketSize,
643               sample.last_packet_send_state.total_bytes_acked);
644     EXPECT_EQ(0u, sample.last_packet_send_state.total_bytes_lost);
645     sampler_.RemoveObsoletePackets(QuicPacketNumber(i - 2));
646   }
647 }
648 
TEST_P(BandwidthSamplerTest,LoseEveryOtherPacket)649 TEST_P(BandwidthSamplerTest, LoseEveryOtherPacket) {
650   QuicTime::Delta time_between_packets = QuicTime::Delta::FromMilliseconds(10);
651   QuicBandwidth sending_rate = QuicBandwidth::FromBytesAndTimeDelta(
652       kRegularPacketSize, time_between_packets);
653 
654   for (uint64_t i = 1; i < 21; i++) {
655     SendPacket(i);
656     clock_.AdvanceTime(time_between_packets);
657     if (i % 2 != 0) {
658       continue;
659     }
660 
661     // Ack packet i and lose i-1.
662     BandwidthSampler::CongestionEventSample sample =
663         OnCongestionEvent({i}, {i - 1});
664     // Losing 50% packets means sending rate is twice the bandwidth.
665     EXPECT_EQ(sending_rate, sample.sample_max_bandwidth * 2);
666     EXPECT_EQ(time_between_packets, sample.sample_rtt);
667     EXPECT_EQ(kRegularPacketSize, sample.sample_max_inflight);
668     EXPECT_TRUE(sample.last_packet_send_state.is_valid);
669     EXPECT_EQ(2 * kRegularPacketSize,
670               sample.last_packet_send_state.bytes_in_flight);
671     EXPECT_EQ(i * kRegularPacketSize,
672               sample.last_packet_send_state.total_bytes_sent);
673     EXPECT_EQ((i - 2) * kRegularPacketSize / 2,
674               sample.last_packet_send_state.total_bytes_acked);
675     EXPECT_EQ((i - 2) * kRegularPacketSize / 2,
676               sample.last_packet_send_state.total_bytes_lost);
677     sampler_.RemoveObsoletePackets(QuicPacketNumber(i - 2));
678   }
679 }
680 
TEST_P(BandwidthSamplerTest,AckHeightRespectBandwidthEstimateUpperBound)681 TEST_P(BandwidthSamplerTest, AckHeightRespectBandwidthEstimateUpperBound) {
682   QuicTime::Delta time_between_packets = QuicTime::Delta::FromMilliseconds(10);
683   QuicBandwidth first_packet_sending_rate =
684       QuicBandwidth::FromBytesAndTimeDelta(kRegularPacketSize,
685                                            time_between_packets);
686 
687   // Send packets 1 to 4 and ack packet 1.
688   SendPacket(1);
689   clock_.AdvanceTime(time_between_packets);
690   SendPacket(2);
691   SendPacket(3);
692   SendPacket(4);
693   BandwidthSampler::CongestionEventSample sample = OnCongestionEvent({1}, {});
694   EXPECT_EQ(first_packet_sending_rate, sample.sample_max_bandwidth);
695   EXPECT_EQ(first_packet_sending_rate, max_bandwidth_);
696 
697   // Ack packet 2, 3 and 4, all of which uses S(1) to calculate ack rate since
698   // there were no acks at the time they were sent.
699   round_trip_count_++;
700   est_bandwidth_upper_bound_ = first_packet_sending_rate * 0.3;
701   clock_.AdvanceTime(time_between_packets);
702   sample = OnCongestionEvent({2, 3, 4}, {});
703   EXPECT_EQ(first_packet_sending_rate * 2, sample.sample_max_bandwidth);
704   EXPECT_EQ(max_bandwidth_, sample.sample_max_bandwidth);
705 
706   EXPECT_LT(2 * kRegularPacketSize, sample.extra_acked);
707 }
708 
709 class MaxAckHeightTrackerTest : public QuicTest {
710  protected:
MaxAckHeightTrackerTest()711   MaxAckHeightTrackerTest() : tracker_(/*initial_filter_window=*/10) {
712     tracker_.SetAckAggregationBandwidthThreshold(1.8);
713     tracker_.SetStartNewAggregationEpochAfterFullRound(true);
714   }
715 
716   // Run a full aggregation episode, which is one or more aggregated acks,
717   // followed by a quiet period in which no ack happens.
718   // After this function returns, the time is set to the earliest point at which
719   // any ack event will cause tracker_.Update() to start a new aggregation.
AggregationEpisode(QuicBandwidth aggregation_bandwidth,QuicTime::Delta aggregation_duration,QuicByteCount bytes_per_ack,bool expect_new_aggregation_epoch)720   void AggregationEpisode(QuicBandwidth aggregation_bandwidth,
721                           QuicTime::Delta aggregation_duration,
722                           QuicByteCount bytes_per_ack,
723                           bool expect_new_aggregation_epoch) {
724     ASSERT_GE(aggregation_bandwidth, bandwidth_);
725     const QuicTime start_time = now_;
726 
727     const QuicByteCount aggregation_bytes =
728         aggregation_bandwidth * aggregation_duration;
729 
730     const int num_acks = aggregation_bytes / bytes_per_ack;
731     ASSERT_EQ(aggregation_bytes, num_acks * bytes_per_ack)
732         << "aggregation_bytes: " << aggregation_bytes << " ["
733         << aggregation_bandwidth << " in " << aggregation_duration
734         << "], bytes_per_ack: " << bytes_per_ack;
735 
736     const QuicTime::Delta time_between_acks = QuicTime::Delta::FromMicroseconds(
737         aggregation_duration.ToMicroseconds() / num_acks);
738     ASSERT_EQ(aggregation_duration, num_acks * time_between_acks)
739         << "aggregation_bytes: " << aggregation_bytes
740         << ", num_acks: " << num_acks
741         << ", time_between_acks: " << time_between_acks;
742 
743     // The total duration of aggregation time and quiet period.
744     const QuicTime::Delta total_duration = QuicTime::Delta::FromMicroseconds(
745         aggregation_bytes * 8 * 1000000 / bandwidth_.ToBitsPerSecond());
746     ASSERT_EQ(aggregation_bytes, total_duration * bandwidth_)
747         << "total_duration: " << total_duration
748         << ", bandwidth_: " << bandwidth_;
749 
750     QuicByteCount last_extra_acked = 0;
751     for (QuicByteCount bytes = 0; bytes < aggregation_bytes;
752          bytes += bytes_per_ack) {
753       QuicByteCount extra_acked = tracker_.Update(
754           bandwidth_, true, RoundTripCount(), last_sent_packet_number_,
755           last_acked_packet_number_, now_, bytes_per_ack);
756       QUIC_VLOG(1) << "T" << now_ << ": Update after " << bytes_per_ack
757                    << " bytes acked, " << extra_acked << " extra bytes acked";
758       // |extra_acked| should be 0 if either
759       // [1] We are at the beginning of a aggregation epoch(bytes==0) and the
760       //     the current tracker implementation can identify it, or
761       // [2] We are not really aggregating acks.
762       if ((bytes == 0 && expect_new_aggregation_epoch) ||  // [1]
763           (aggregation_bandwidth == bandwidth_)) {         // [2]
764         EXPECT_EQ(0u, extra_acked);
765       } else {
766         EXPECT_LT(last_extra_acked, extra_acked);
767       }
768       now_ = now_ + time_between_acks;
769       last_extra_acked = extra_acked;
770     }
771 
772     // Advance past the quiet period.
773     const QuicTime time_after_aggregation = now_;
774     now_ = start_time + total_duration;
775     QUIC_VLOG(1) << "Advanced time from " << time_after_aggregation << " to "
776                  << now_ << ". Aggregation time["
777                  << (time_after_aggregation - start_time) << "], Quiet time["
778                  << (now_ - time_after_aggregation) << "].";
779   }
780 
RoundTripCount() const781   QuicRoundTripCount RoundTripCount() const {
782     return (now_ - QuicTime::Zero()).ToMicroseconds() / rtt_.ToMicroseconds();
783   }
784 
785   MaxAckHeightTracker tracker_;
786   QuicBandwidth bandwidth_ = QuicBandwidth::FromBytesPerSecond(10 * 1000);
787   QuicTime now_ = QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(1);
788   QuicTime::Delta rtt_ = QuicTime::Delta::FromMilliseconds(60);
789   QuicPacketNumber last_sent_packet_number_;
790   QuicPacketNumber last_acked_packet_number_;
791 };
792 
TEST_F(MaxAckHeightTrackerTest,VeryAggregatedLargeAck)793 TEST_F(MaxAckHeightTrackerTest, VeryAggregatedLargeAck) {
794   AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6),
795                      1200, true);
796   AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6),
797                      1200, true);
798   now_ = now_ - QuicTime::Delta::FromMilliseconds(1);
799 
800   if (tracker_.ack_aggregation_bandwidth_threshold() > 1.1) {
801     AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6),
802                        1200, true);
803     EXPECT_EQ(3u, tracker_.num_ack_aggregation_epochs());
804   } else {
805     AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6),
806                        1200, false);
807     EXPECT_EQ(2u, tracker_.num_ack_aggregation_epochs());
808   }
809 }
810 
TEST_F(MaxAckHeightTrackerTest,VeryAggregatedSmallAcks)811 TEST_F(MaxAckHeightTrackerTest, VeryAggregatedSmallAcks) {
812   AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6), 300,
813                      true);
814   AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6), 300,
815                      true);
816   now_ = now_ - QuicTime::Delta::FromMilliseconds(1);
817 
818   if (tracker_.ack_aggregation_bandwidth_threshold() > 1.1) {
819     AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6),
820                        300, true);
821     EXPECT_EQ(3u, tracker_.num_ack_aggregation_epochs());
822   } else {
823     AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6),
824                        300, false);
825     EXPECT_EQ(2u, tracker_.num_ack_aggregation_epochs());
826   }
827 }
828 
TEST_F(MaxAckHeightTrackerTest,SomewhatAggregatedLargeAck)829 TEST_F(MaxAckHeightTrackerTest, SomewhatAggregatedLargeAck) {
830   AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50),
831                      1000, true);
832   AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50),
833                      1000, true);
834   now_ = now_ - QuicTime::Delta::FromMilliseconds(1);
835 
836   if (tracker_.ack_aggregation_bandwidth_threshold() > 1.1) {
837     AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50),
838                        1000, true);
839     EXPECT_EQ(3u, tracker_.num_ack_aggregation_epochs());
840   } else {
841     AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50),
842                        1000, false);
843     EXPECT_EQ(2u, tracker_.num_ack_aggregation_epochs());
844   }
845 }
846 
TEST_F(MaxAckHeightTrackerTest,SomewhatAggregatedSmallAcks)847 TEST_F(MaxAckHeightTrackerTest, SomewhatAggregatedSmallAcks) {
848   AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50), 100,
849                      true);
850   AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50), 100,
851                      true);
852   now_ = now_ - QuicTime::Delta::FromMilliseconds(1);
853 
854   if (tracker_.ack_aggregation_bandwidth_threshold() > 1.1) {
855     AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50),
856                        100, true);
857     EXPECT_EQ(3u, tracker_.num_ack_aggregation_epochs());
858   } else {
859     AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50),
860                        100, false);
861     EXPECT_EQ(2u, tracker_.num_ack_aggregation_epochs());
862   }
863 }
864 
TEST_F(MaxAckHeightTrackerTest,NotAggregated)865 TEST_F(MaxAckHeightTrackerTest, NotAggregated) {
866   AggregationEpisode(bandwidth_, QuicTime::Delta::FromMilliseconds(100), 100,
867                      true);
868   EXPECT_LT(2u, tracker_.num_ack_aggregation_epochs());
869 }
870 
TEST_F(MaxAckHeightTrackerTest,StartNewEpochAfterAFullRound)871 TEST_F(MaxAckHeightTrackerTest, StartNewEpochAfterAFullRound) {
872   last_sent_packet_number_ = QuicPacketNumber(10);
873   AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50), 100,
874                      true);
875 
876   last_acked_packet_number_ = QuicPacketNumber(11);
877   // Update with a tiny bandwidth causes a very low expected bytes acked, which
878   // in turn causes the current epoch to continue if the |tracker_| doesn't
879   // check the packet numbers.
880   tracker_.Update(bandwidth_ * 0.1, true, RoundTripCount(),
881                   last_sent_packet_number_, last_acked_packet_number_, now_,
882                   100);
883 
884   EXPECT_EQ(2u, tracker_.num_ack_aggregation_epochs());
885 }
886 
887 }  // namespace test
888 }  // namespace quic
889