1 // Copyright (c) 2016 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #include "net/third_party/quiche/src/quic/core/congestion_control/windowed_filter.h"
6 
7 #include "net/third_party/quiche/src/quic/core/congestion_control/rtt_stats.h"
8 #include "net/third_party/quiche/src/quic/core/quic_bandwidth.h"
9 #include "net/third_party/quiche/src/quic/core/quic_packets.h"
10 #include "net/third_party/quiche/src/quic/platform/api/quic_logging.h"
11 #include "net/third_party/quiche/src/quic/platform/api/quic_test.h"
12 
13 namespace quic {
14 namespace test {
15 
16 class WindowedFilterTest : public QuicTest {
17  public:
18   // Set the window to 99ms, so 25ms is more than a quarter rtt.
WindowedFilterTest()19   WindowedFilterTest()
20       : windowed_min_rtt_(QuicTime::Delta::FromMilliseconds(99),
21                           QuicTime::Delta::Zero(),
22                           QuicTime::Zero()),
23         windowed_max_bw_(QuicTime::Delta::FromMilliseconds(99),
24                          QuicBandwidth::Zero(),
25                          QuicTime::Zero()) {}
26 
27   // Sets up windowed_min_rtt_ to have the following values:
28   // Best = 20ms, recorded at 25ms
29   // Second best = 40ms, recorded at 75ms
30   // Third best = 50ms, recorded at 100ms
InitializeMinFilter()31   void InitializeMinFilter() {
32     QuicTime now = QuicTime::Zero();
33     QuicTime::Delta rtt_sample = QuicTime::Delta::FromMilliseconds(10);
34     for (int i = 0; i < 5; ++i) {
35       windowed_min_rtt_.Update(rtt_sample, now);
36       QUIC_VLOG(1) << "i: " << i << " sample: " << rtt_sample.ToMilliseconds()
37                    << " mins: "
38                    << " " << windowed_min_rtt_.GetBest().ToMilliseconds() << " "
39                    << windowed_min_rtt_.GetSecondBest().ToMilliseconds() << " "
40                    << windowed_min_rtt_.GetThirdBest().ToMilliseconds();
41       now = now + QuicTime::Delta::FromMilliseconds(25);
42       rtt_sample = rtt_sample + QuicTime::Delta::FromMilliseconds(10);
43     }
44     EXPECT_EQ(QuicTime::Delta::FromMilliseconds(20),
45               windowed_min_rtt_.GetBest());
46     EXPECT_EQ(QuicTime::Delta::FromMilliseconds(40),
47               windowed_min_rtt_.GetSecondBest());
48     EXPECT_EQ(QuicTime::Delta::FromMilliseconds(50),
49               windowed_min_rtt_.GetThirdBest());
50   }
51 
52   // Sets up windowed_max_bw_ to have the following values:
53   // Best = 900 bps, recorded at 25ms
54   // Second best = 700 bps, recorded at 75ms
55   // Third best = 600 bps, recorded at 100ms
InitializeMaxFilter()56   void InitializeMaxFilter() {
57     QuicTime now = QuicTime::Zero();
58     QuicBandwidth bw_sample = QuicBandwidth::FromBitsPerSecond(1000);
59     for (int i = 0; i < 5; ++i) {
60       windowed_max_bw_.Update(bw_sample, now);
61       QUIC_VLOG(1) << "i: " << i << " sample: " << bw_sample.ToBitsPerSecond()
62                    << " maxs: "
63                    << " " << windowed_max_bw_.GetBest().ToBitsPerSecond() << " "
64                    << windowed_max_bw_.GetSecondBest().ToBitsPerSecond() << " "
65                    << windowed_max_bw_.GetThirdBest().ToBitsPerSecond();
66       now = now + QuicTime::Delta::FromMilliseconds(25);
67       bw_sample = bw_sample - QuicBandwidth::FromBitsPerSecond(100);
68     }
69     EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(900),
70               windowed_max_bw_.GetBest());
71     EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(700),
72               windowed_max_bw_.GetSecondBest());
73     EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(600),
74               windowed_max_bw_.GetThirdBest());
75   }
76 
77  protected:
78   WindowedFilter<QuicTime::Delta,
79                  MinFilter<QuicTime::Delta>,
80                  QuicTime,
81                  QuicTime::Delta>
82       windowed_min_rtt_;
83   WindowedFilter<QuicBandwidth,
84                  MaxFilter<QuicBandwidth>,
85                  QuicTime,
86                  QuicTime::Delta>
87       windowed_max_bw_;
88 };
89 
90 namespace {
91 // Test helper function: updates the filter with a lot of small values in order
92 // to ensure that it is not susceptible to noise.
UpdateWithIrrelevantSamples(WindowedFilter<uint64_t,MaxFilter<uint64_t>,uint64_t,uint64_t> * filter,uint64_t max_value,uint64_t time)93 void UpdateWithIrrelevantSamples(
94     WindowedFilter<uint64_t, MaxFilter<uint64_t>, uint64_t, uint64_t>* filter,
95     uint64_t max_value,
96     uint64_t time) {
97   for (uint64_t i = 0; i < 1000; i++) {
98     filter->Update(i % max_value, time);
99   }
100 }
101 }  // namespace
102 
TEST_F(WindowedFilterTest,UninitializedEstimates)103 TEST_F(WindowedFilterTest, UninitializedEstimates) {
104   EXPECT_EQ(QuicTime::Delta::Zero(), windowed_min_rtt_.GetBest());
105   EXPECT_EQ(QuicTime::Delta::Zero(), windowed_min_rtt_.GetSecondBest());
106   EXPECT_EQ(QuicTime::Delta::Zero(), windowed_min_rtt_.GetThirdBest());
107   EXPECT_EQ(QuicBandwidth::Zero(), windowed_max_bw_.GetBest());
108   EXPECT_EQ(QuicBandwidth::Zero(), windowed_max_bw_.GetSecondBest());
109   EXPECT_EQ(QuicBandwidth::Zero(), windowed_max_bw_.GetThirdBest());
110 }
111 
TEST_F(WindowedFilterTest,MonotonicallyIncreasingMin)112 TEST_F(WindowedFilterTest, MonotonicallyIncreasingMin) {
113   QuicTime now = QuicTime::Zero();
114   QuicTime::Delta rtt_sample = QuicTime::Delta::FromMilliseconds(10);
115   windowed_min_rtt_.Update(rtt_sample, now);
116   EXPECT_EQ(QuicTime::Delta::FromMilliseconds(10), windowed_min_rtt_.GetBest());
117 
118   // Gradually increase the rtt samples and ensure the windowed min rtt starts
119   // rising.
120   for (int i = 0; i < 6; ++i) {
121     now = now + QuicTime::Delta::FromMilliseconds(25);
122     rtt_sample = rtt_sample + QuicTime::Delta::FromMilliseconds(10);
123     windowed_min_rtt_.Update(rtt_sample, now);
124     QUIC_VLOG(1) << "i: " << i << " sample: " << rtt_sample.ToMilliseconds()
125                  << " mins: "
126                  << " " << windowed_min_rtt_.GetBest().ToMilliseconds() << " "
127                  << windowed_min_rtt_.GetSecondBest().ToMilliseconds() << " "
128                  << windowed_min_rtt_.GetThirdBest().ToMilliseconds();
129     if (i < 3) {
130       EXPECT_EQ(QuicTime::Delta::FromMilliseconds(10),
131                 windowed_min_rtt_.GetBest());
132     } else if (i == 3) {
133       EXPECT_EQ(QuicTime::Delta::FromMilliseconds(20),
134                 windowed_min_rtt_.GetBest());
135     } else if (i < 6) {
136       EXPECT_EQ(QuicTime::Delta::FromMilliseconds(40),
137                 windowed_min_rtt_.GetBest());
138     }
139   }
140 }
141 
TEST_F(WindowedFilterTest,MonotonicallyDecreasingMax)142 TEST_F(WindowedFilterTest, MonotonicallyDecreasingMax) {
143   QuicTime now = QuicTime::Zero();
144   QuicBandwidth bw_sample = QuicBandwidth::FromBitsPerSecond(1000);
145   windowed_max_bw_.Update(bw_sample, now);
146   EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(1000), windowed_max_bw_.GetBest());
147 
148   // Gradually decrease the bw samples and ensure the windowed max bw starts
149   // decreasing.
150   for (int i = 0; i < 6; ++i) {
151     now = now + QuicTime::Delta::FromMilliseconds(25);
152     bw_sample = bw_sample - QuicBandwidth::FromBitsPerSecond(100);
153     windowed_max_bw_.Update(bw_sample, now);
154     QUIC_VLOG(1) << "i: " << i << " sample: " << bw_sample.ToBitsPerSecond()
155                  << " maxs: "
156                  << " " << windowed_max_bw_.GetBest().ToBitsPerSecond() << " "
157                  << windowed_max_bw_.GetSecondBest().ToBitsPerSecond() << " "
158                  << windowed_max_bw_.GetThirdBest().ToBitsPerSecond();
159     if (i < 3) {
160       EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(1000),
161                 windowed_max_bw_.GetBest());
162     } else if (i == 3) {
163       EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(900),
164                 windowed_max_bw_.GetBest());
165     } else if (i < 6) {
166       EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(700),
167                 windowed_max_bw_.GetBest());
168     }
169   }
170 }
171 
TEST_F(WindowedFilterTest,SampleChangesThirdBestMin)172 TEST_F(WindowedFilterTest, SampleChangesThirdBestMin) {
173   InitializeMinFilter();
174   // RTT sample lower than the third-choice min-rtt sets that, but nothing else.
175   QuicTime::Delta rtt_sample =
176       windowed_min_rtt_.GetThirdBest() - QuicTime::Delta::FromMilliseconds(5);
177   // This assert is necessary to avoid triggering -Wstrict-overflow
178   // See crbug/616957
179   ASSERT_GT(windowed_min_rtt_.GetThirdBest(),
180             QuicTime::Delta::FromMilliseconds(5));
181   // Latest sample was recorded at 100ms.
182   QuicTime now = QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(101);
183   windowed_min_rtt_.Update(rtt_sample, now);
184   EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetThirdBest());
185   EXPECT_EQ(QuicTime::Delta::FromMilliseconds(40),
186             windowed_min_rtt_.GetSecondBest());
187   EXPECT_EQ(QuicTime::Delta::FromMilliseconds(20), windowed_min_rtt_.GetBest());
188 }
189 
TEST_F(WindowedFilterTest,SampleChangesThirdBestMax)190 TEST_F(WindowedFilterTest, SampleChangesThirdBestMax) {
191   InitializeMaxFilter();
192   // BW sample higher than the third-choice max sets that, but nothing else.
193   QuicBandwidth bw_sample =
194       windowed_max_bw_.GetThirdBest() + QuicBandwidth::FromBitsPerSecond(50);
195   // Latest sample was recorded at 100ms.
196   QuicTime now = QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(101);
197   windowed_max_bw_.Update(bw_sample, now);
198   EXPECT_EQ(bw_sample, windowed_max_bw_.GetThirdBest());
199   EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(700),
200             windowed_max_bw_.GetSecondBest());
201   EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(900), windowed_max_bw_.GetBest());
202 }
203 
TEST_F(WindowedFilterTest,SampleChangesSecondBestMin)204 TEST_F(WindowedFilterTest, SampleChangesSecondBestMin) {
205   InitializeMinFilter();
206   // RTT sample lower than the second-choice min sets that and also
207   // the third-choice min.
208   QuicTime::Delta rtt_sample =
209       windowed_min_rtt_.GetSecondBest() - QuicTime::Delta::FromMilliseconds(5);
210   // This assert is necessary to avoid triggering -Wstrict-overflow
211   // See crbug/616957
212   ASSERT_GT(windowed_min_rtt_.GetSecondBest(),
213             QuicTime::Delta::FromMilliseconds(5));
214   // Latest sample was recorded at 100ms.
215   QuicTime now = QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(101);
216   windowed_min_rtt_.Update(rtt_sample, now);
217   EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetThirdBest());
218   EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetSecondBest());
219   EXPECT_EQ(QuicTime::Delta::FromMilliseconds(20), windowed_min_rtt_.GetBest());
220 }
221 
TEST_F(WindowedFilterTest,SampleChangesSecondBestMax)222 TEST_F(WindowedFilterTest, SampleChangesSecondBestMax) {
223   InitializeMaxFilter();
224   // BW sample higher than the second-choice max sets that and also
225   // the third-choice max.
226   QuicBandwidth bw_sample =
227       windowed_max_bw_.GetSecondBest() + QuicBandwidth::FromBitsPerSecond(50);
228   // Latest sample was recorded at 100ms.
229   QuicTime now = QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(101);
230   windowed_max_bw_.Update(bw_sample, now);
231   EXPECT_EQ(bw_sample, windowed_max_bw_.GetThirdBest());
232   EXPECT_EQ(bw_sample, windowed_max_bw_.GetSecondBest());
233   EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(900), windowed_max_bw_.GetBest());
234 }
235 
TEST_F(WindowedFilterTest,SampleChangesAllMins)236 TEST_F(WindowedFilterTest, SampleChangesAllMins) {
237   InitializeMinFilter();
238   // RTT sample lower than the first-choice min-rtt sets that and also
239   // the second and third-choice mins.
240   QuicTime::Delta rtt_sample =
241       windowed_min_rtt_.GetBest() - QuicTime::Delta::FromMilliseconds(5);
242   // This assert is necessary to avoid triggering -Wstrict-overflow
243   // See crbug/616957
244   ASSERT_GT(windowed_min_rtt_.GetBest(), QuicTime::Delta::FromMilliseconds(5));
245   // Latest sample was recorded at 100ms.
246   QuicTime now = QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(101);
247   windowed_min_rtt_.Update(rtt_sample, now);
248   EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetThirdBest());
249   EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetSecondBest());
250   EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetBest());
251 }
252 
TEST_F(WindowedFilterTest,SampleChangesAllMaxs)253 TEST_F(WindowedFilterTest, SampleChangesAllMaxs) {
254   InitializeMaxFilter();
255   // BW sample higher than the first-choice max sets that and also
256   // the second and third-choice maxs.
257   QuicBandwidth bw_sample =
258       windowed_max_bw_.GetBest() + QuicBandwidth::FromBitsPerSecond(50);
259   // Latest sample was recorded at 100ms.
260   QuicTime now = QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(101);
261   windowed_max_bw_.Update(bw_sample, now);
262   EXPECT_EQ(bw_sample, windowed_max_bw_.GetThirdBest());
263   EXPECT_EQ(bw_sample, windowed_max_bw_.GetSecondBest());
264   EXPECT_EQ(bw_sample, windowed_max_bw_.GetBest());
265 }
266 
TEST_F(WindowedFilterTest,ExpireBestMin)267 TEST_F(WindowedFilterTest, ExpireBestMin) {
268   InitializeMinFilter();
269   QuicTime::Delta old_third_best = windowed_min_rtt_.GetThirdBest();
270   QuicTime::Delta old_second_best = windowed_min_rtt_.GetSecondBest();
271   QuicTime::Delta rtt_sample =
272       old_third_best + QuicTime::Delta::FromMilliseconds(5);
273   // Best min sample was recorded at 25ms, so expiry time is 124ms.
274   QuicTime now = QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(125);
275   windowed_min_rtt_.Update(rtt_sample, now);
276   EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetThirdBest());
277   EXPECT_EQ(old_third_best, windowed_min_rtt_.GetSecondBest());
278   EXPECT_EQ(old_second_best, windowed_min_rtt_.GetBest());
279 }
280 
TEST_F(WindowedFilterTest,ExpireBestMax)281 TEST_F(WindowedFilterTest, ExpireBestMax) {
282   InitializeMaxFilter();
283   QuicBandwidth old_third_best = windowed_max_bw_.GetThirdBest();
284   QuicBandwidth old_second_best = windowed_max_bw_.GetSecondBest();
285   QuicBandwidth bw_sample =
286       old_third_best - QuicBandwidth::FromBitsPerSecond(50);
287   // Best max sample was recorded at 25ms, so expiry time is 124ms.
288   QuicTime now = QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(125);
289   windowed_max_bw_.Update(bw_sample, now);
290   EXPECT_EQ(bw_sample, windowed_max_bw_.GetThirdBest());
291   EXPECT_EQ(old_third_best, windowed_max_bw_.GetSecondBest());
292   EXPECT_EQ(old_second_best, windowed_max_bw_.GetBest());
293 }
294 
TEST_F(WindowedFilterTest,ExpireSecondBestMin)295 TEST_F(WindowedFilterTest, ExpireSecondBestMin) {
296   InitializeMinFilter();
297   QuicTime::Delta old_third_best = windowed_min_rtt_.GetThirdBest();
298   QuicTime::Delta rtt_sample =
299       old_third_best + QuicTime::Delta::FromMilliseconds(5);
300   // Second best min sample was recorded at 75ms, so expiry time is 174ms.
301   QuicTime now = QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(175);
302   windowed_min_rtt_.Update(rtt_sample, now);
303   EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetThirdBest());
304   EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetSecondBest());
305   EXPECT_EQ(old_third_best, windowed_min_rtt_.GetBest());
306 }
307 
TEST_F(WindowedFilterTest,ExpireSecondBestMax)308 TEST_F(WindowedFilterTest, ExpireSecondBestMax) {
309   InitializeMaxFilter();
310   QuicBandwidth old_third_best = windowed_max_bw_.GetThirdBest();
311   QuicBandwidth bw_sample =
312       old_third_best - QuicBandwidth::FromBitsPerSecond(50);
313   // Second best max sample was recorded at 75ms, so expiry time is 174ms.
314   QuicTime now = QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(175);
315   windowed_max_bw_.Update(bw_sample, now);
316   EXPECT_EQ(bw_sample, windowed_max_bw_.GetThirdBest());
317   EXPECT_EQ(bw_sample, windowed_max_bw_.GetSecondBest());
318   EXPECT_EQ(old_third_best, windowed_max_bw_.GetBest());
319 }
320 
TEST_F(WindowedFilterTest,ExpireAllMins)321 TEST_F(WindowedFilterTest, ExpireAllMins) {
322   InitializeMinFilter();
323   QuicTime::Delta rtt_sample =
324       windowed_min_rtt_.GetThirdBest() + QuicTime::Delta::FromMilliseconds(5);
325   // This assert is necessary to avoid triggering -Wstrict-overflow
326   // See crbug/616957
327   ASSERT_LT(windowed_min_rtt_.GetThirdBest(),
328             QuicTime::Delta::Infinite() - QuicTime::Delta::FromMilliseconds(5));
329   // Third best min sample was recorded at 100ms, so expiry time is 199ms.
330   QuicTime now = QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(200);
331   windowed_min_rtt_.Update(rtt_sample, now);
332   EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetThirdBest());
333   EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetSecondBest());
334   EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetBest());
335 }
336 
TEST_F(WindowedFilterTest,ExpireAllMaxs)337 TEST_F(WindowedFilterTest, ExpireAllMaxs) {
338   InitializeMaxFilter();
339   QuicBandwidth bw_sample =
340       windowed_max_bw_.GetThirdBest() - QuicBandwidth::FromBitsPerSecond(50);
341   // Third best max sample was recorded at 100ms, so expiry time is 199ms.
342   QuicTime now = QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(200);
343   windowed_max_bw_.Update(bw_sample, now);
344   EXPECT_EQ(bw_sample, windowed_max_bw_.GetThirdBest());
345   EXPECT_EQ(bw_sample, windowed_max_bw_.GetSecondBest());
346   EXPECT_EQ(bw_sample, windowed_max_bw_.GetBest());
347 }
348 
349 // Test the windowed filter where the time used is an exact counter instead of a
350 // timestamp.  This is useful if, for example, the time is measured in round
351 // trips.
TEST_F(WindowedFilterTest,ExpireCounterBasedMax)352 TEST_F(WindowedFilterTest, ExpireCounterBasedMax) {
353   // Create a window which starts at t = 0 and expires after two cycles.
354   WindowedFilter<uint64_t, MaxFilter<uint64_t>, uint64_t, uint64_t> max_filter(
355       2, 0, 0);
356 
357   const uint64_t kBest = 50000;
358   // Insert 50000 at t = 1.
359   max_filter.Update(50000, 1);
360   EXPECT_EQ(kBest, max_filter.GetBest());
361   UpdateWithIrrelevantSamples(&max_filter, 20, 1);
362   EXPECT_EQ(kBest, max_filter.GetBest());
363 
364   // Insert 40000 at t = 2.  Nothing is expected to expire.
365   max_filter.Update(40000, 2);
366   EXPECT_EQ(kBest, max_filter.GetBest());
367   UpdateWithIrrelevantSamples(&max_filter, 20, 2);
368   EXPECT_EQ(kBest, max_filter.GetBest());
369 
370   // Insert 30000 at t = 3.  Nothing is expected to expire yet.
371   max_filter.Update(30000, 3);
372   EXPECT_EQ(kBest, max_filter.GetBest());
373   UpdateWithIrrelevantSamples(&max_filter, 20, 3);
374   EXPECT_EQ(kBest, max_filter.GetBest());
375   QUIC_VLOG(0) << max_filter.GetSecondBest();
376   QUIC_VLOG(0) << max_filter.GetThirdBest();
377 
378   // Insert 20000 at t = 4.  50000 at t = 1 expires, so 40000 becomes the new
379   // maximum.
380   const uint64_t kNewBest = 40000;
381   max_filter.Update(20000, 4);
382   EXPECT_EQ(kNewBest, max_filter.GetBest());
383   UpdateWithIrrelevantSamples(&max_filter, 20, 4);
384   EXPECT_EQ(kNewBest, max_filter.GetBest());
385 }
386 
387 }  // namespace test
388 }  // namespace quic
389