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