quiche/
minmax.rs

1// Copyright (C) 2020, Cloudflare, Inc.
2// Copyright (C) 2017, Google, Inc.
3//
4// Use of this source code is governed by the following BSD-style license:
5//
6// Redistribution and use in source and binary forms, with or without
7// modification, are permitted provided that the following conditions are
8// met:
9//
10//    * Redistributions of source code must retain the above copyright
11// notice, this list of conditions and the following disclaimer.
12//    * Redistributions in binary form must reproduce the above
13// copyright notice, this list of conditions and the following disclaimer
14// in the documentation and/or other materials provided with the
15// distribution.
16//
17//    * Neither the name of Google Inc. nor the names of its
18// contributors may be used to endorse or promote products derived from
19// this software without specific prior written permission.
20//
21// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32
33// lib/minmax.c: windowed min/max tracker
34//
35// Kathleen Nichols' algorithm for tracking the minimum (or maximum)
36// value of a data stream over some fixed time interval.  (E.g.,
37// the minimum RTT over the past five minutes.) It uses constant
38// space and constant time per update yet almost always delivers
39// the same minimum as an implementation that has to keep all the
40// data in the window.
41//
42// The algorithm keeps track of the best, 2nd best & 3rd best min
43// values, maintaining an invariant that the measurement time of
44// the n'th best >= n-1'th best. It also makes sure that the three
45// values are widely separated in the time window since that bounds
46// the worse case error when that data is monotonically increasing
47// over the window.
48//
49// Upon getting a new min, we can forget everything earlier because
50// it has no value - the new min is <= everything else in the window
51// by definition and it's the most recent. So we restart fresh on
52// every new min and overwrites 2nd & 3rd choices. The same property
53// holds for 2nd & 3rd best.
54
55use std::ops::Deref;
56
57use std::time::Duration;
58use std::time::Instant;
59
60#[derive(Copy, Clone)]
61struct MinmaxSample<T> {
62    time: Instant,
63    value: T,
64}
65
66pub struct Minmax<T> {
67    estimate: [MinmaxSample<T>; 3],
68}
69
70impl<T> Deref for Minmax<T> {
71    type Target = T;
72
73    fn deref(&self) -> &Self::Target {
74        &self.estimate[0].value
75    }
76}
77
78impl<T: PartialOrd + Copy> Minmax<T> {
79    pub fn new(val: T) -> Self {
80        Minmax {
81            estimate: [MinmaxSample {
82                time: Instant::now(),
83                value: val,
84            }; 3],
85        }
86    }
87
88    /// Resets the estimates to the given value.
89    pub fn reset(&mut self, time: Instant, meas: T) -> T {
90        let val = MinmaxSample { time, value: meas };
91
92        for i in self.estimate.iter_mut() {
93            *i = val;
94        }
95
96        self.estimate[0].value
97    }
98
99    /// Updates the min estimate based on the given measurement, and returns it.
100    pub fn running_min(&mut self, win: Duration, time: Instant, meas: T) -> T {
101        let val = MinmaxSample { time, value: meas };
102
103        let delta_time = time.duration_since(self.estimate[2].time);
104
105        // Reset if there's nothing in the window or a new min value is found.
106        if val.value <= self.estimate[0].value || delta_time > win {
107            return self.reset(time, meas);
108        }
109
110        if val.value <= self.estimate[1].value {
111            self.estimate[2] = val;
112            self.estimate[1] = val;
113        } else if val.value <= self.estimate[2].value {
114            self.estimate[2] = val;
115        }
116
117        self.subwin_update(win, time, meas)
118    }
119
120    /// Updates the max estimate based on the given measurement, and returns it.
121    #[cfg(test)]
122    pub fn running_max(&mut self, win: Duration, time: Instant, meas: T) -> T {
123        let val = MinmaxSample { time, value: meas };
124
125        let delta_time = time.duration_since(self.estimate[2].time);
126
127        // Reset if there's nothing in the window or a new max value is found.
128        if val.value >= self.estimate[0].value || delta_time > win {
129            return self.reset(time, meas);
130        }
131
132        if val.value >= self.estimate[1].value {
133            self.estimate[2] = val;
134            self.estimate[1] = val;
135        } else if val.value >= self.estimate[2].value {
136            self.estimate[2] = val
137        }
138
139        self.subwin_update(win, time, meas)
140    }
141
142    /// As time advances, update the 1st, 2nd and 3rd estimates.
143    fn subwin_update(&mut self, win: Duration, time: Instant, meas: T) -> T {
144        let val = MinmaxSample { time, value: meas };
145
146        let delta_time = time.duration_since(self.estimate[0].time);
147
148        if delta_time > win {
149            // Passed entire window without a new val so make 2nd estimate the
150            // new val & 3rd estimate the new 2nd choice. we may have to iterate
151            // this since our 2nd estimate may also be outside the window (we
152            // checked on entry that the third estimate was in the window).
153            self.estimate[0] = self.estimate[1];
154            self.estimate[1] = self.estimate[2];
155            self.estimate[2] = val;
156
157            if time.duration_since(self.estimate[0].time) > win {
158                self.estimate[0] = self.estimate[1];
159                self.estimate[1] = self.estimate[2];
160                self.estimate[2] = val;
161            }
162        } else if self.estimate[1].time == self.estimate[0].time &&
163            delta_time > win.div_f32(4.0)
164        {
165            // We've passed a quarter of the window without a new val so take a
166            // 2nd estimate from the 2nd quarter of the window.
167            self.estimate[2] = val;
168            self.estimate[1] = val;
169        } else if self.estimate[2].time == self.estimate[1].time &&
170            delta_time > win.div_f32(2.0)
171        {
172            // We've passed half the window without finding a new val so take a
173            // 3rd estimate from the last half of the window.
174            self.estimate[2] = val;
175        }
176
177        self.estimate[0].value
178    }
179}
180
181#[cfg(test)]
182mod tests {
183    use super::*;
184
185    #[test]
186    fn reset_filter_rtt() {
187        let mut f = Minmax::new(Duration::ZERO);
188        let now = Instant::now();
189        let rtt = Duration::from_millis(50);
190
191        let rtt_min = f.reset(now, rtt);
192        assert_eq!(rtt_min, rtt);
193
194        assert_eq!(f.estimate[0].time, now);
195        assert_eq!(f.estimate[0].value, rtt);
196
197        assert_eq!(f.estimate[1].time, now);
198        assert_eq!(f.estimate[1].value, rtt);
199
200        assert_eq!(f.estimate[2].time, now);
201        assert_eq!(f.estimate[2].value, rtt);
202    }
203
204    #[test]
205    fn reset_filter_bandwidth() {
206        let mut f = Minmax::new(0);
207        let now = Instant::now();
208        let bw = 2000;
209
210        let bw_min = f.reset(now, bw);
211        assert_eq!(bw_min, bw);
212
213        assert_eq!(f.estimate[0].time, now);
214        assert_eq!(f.estimate[0].value, bw);
215
216        assert_eq!(f.estimate[1].time, now);
217        assert_eq!(f.estimate[1].value, bw);
218
219        assert_eq!(f.estimate[2].time, now);
220        assert_eq!(f.estimate[2].value, bw);
221    }
222
223    #[test]
224    fn get_windowed_min_rtt() {
225        let mut f = Minmax::new(Duration::ZERO);
226        let rtt_25 = Duration::from_millis(25);
227        let rtt_24 = Duration::from_millis(24);
228        let win = Duration::from_millis(500);
229        let mut time = Instant::now();
230
231        let mut rtt_min = f.reset(time, rtt_25);
232        assert_eq!(rtt_min, rtt_25);
233
234        time += Duration::from_millis(250);
235        rtt_min = f.running_min(win, time, rtt_24);
236        assert_eq!(rtt_min, rtt_24);
237        assert_eq!(f.estimate[1].value, rtt_24);
238        assert_eq!(f.estimate[2].value, rtt_24);
239
240        time += Duration::from_millis(600);
241        rtt_min = f.running_min(win, time, rtt_25);
242        assert_eq!(rtt_min, rtt_25);
243        assert_eq!(f.estimate[1].value, rtt_25);
244        assert_eq!(f.estimate[2].value, rtt_25);
245    }
246
247    #[test]
248    fn get_windowed_min_bandwidth() {
249        let mut f = Minmax::new(0);
250        let bw_200 = 200;
251        let bw_500 = 500;
252        let win = Duration::from_millis(500);
253        let mut time = Instant::now();
254
255        let mut bw_min = f.reset(time, bw_500);
256        assert_eq!(bw_min, bw_500);
257
258        time += Duration::from_millis(250);
259        bw_min = f.running_min(win, time, bw_200);
260        assert_eq!(bw_min, bw_200);
261        assert_eq!(f.estimate[1].value, bw_200);
262        assert_eq!(f.estimate[2].value, bw_200);
263
264        time += Duration::from_millis(600);
265        bw_min = f.running_min(win, time, bw_500);
266        assert_eq!(bw_min, bw_500);
267        assert_eq!(f.estimate[1].value, bw_500);
268        assert_eq!(f.estimate[2].value, bw_500);
269    }
270
271    #[test]
272    fn get_windowed_max_rtt() {
273        let mut f = Minmax::new(Duration::ZERO);
274        let rtt_25 = Duration::from_millis(25);
275        let rtt_24 = Duration::from_millis(24);
276        let win = Duration::from_millis(500);
277        let mut time = Instant::now();
278
279        let mut rtt_max = f.reset(time, rtt_24);
280        assert_eq!(rtt_max, rtt_24);
281
282        time += Duration::from_millis(250);
283        rtt_max = f.running_max(win, time, rtt_25);
284        assert_eq!(rtt_max, rtt_25);
285        assert_eq!(f.estimate[1].value, rtt_25);
286        assert_eq!(f.estimate[2].value, rtt_25);
287
288        time += Duration::from_millis(600);
289        rtt_max = f.running_max(win, time, rtt_24);
290        assert_eq!(rtt_max, rtt_24);
291        assert_eq!(f.estimate[1].value, rtt_24);
292        assert_eq!(f.estimate[2].value, rtt_24);
293    }
294
295    #[test]
296    fn get_windowed_max_bandwidth() {
297        let mut f = Minmax::new(0);
298        let bw_200 = 200;
299        let bw_500 = 500;
300        let win = Duration::from_millis(500);
301        let mut time = Instant::now();
302
303        let mut bw_max = f.reset(time, bw_200);
304        assert_eq!(bw_max, bw_200);
305
306        time += Duration::from_millis(5000);
307        bw_max = f.running_max(win, time, bw_500);
308        assert_eq!(bw_max, bw_500);
309        assert_eq!(f.estimate[1].value, bw_500);
310        assert_eq!(f.estimate[2].value, bw_500);
311
312        time += Duration::from_millis(600);
313        bw_max = f.running_max(win, time, bw_200);
314        assert_eq!(bw_max, bw_200);
315        assert_eq!(f.estimate[1].value, bw_200);
316        assert_eq!(f.estimate[2].value, bw_200);
317    }
318
319    #[test]
320    fn get_windowed_min_estimates_rtt() {
321        let mut f = Minmax::new(Duration::ZERO);
322        let rtt_25 = Duration::from_millis(25);
323        let rtt_24 = Duration::from_millis(24);
324        let rtt_23 = Duration::from_millis(23);
325        let rtt_22 = Duration::from_millis(22);
326        let win = Duration::from_secs(1);
327        let mut time = Instant::now();
328
329        let mut rtt_min = f.reset(time, rtt_23);
330        assert_eq!(rtt_min, rtt_23);
331
332        time += Duration::from_millis(300);
333        rtt_min = f.running_min(win, time, rtt_24);
334        assert_eq!(rtt_min, rtt_23);
335        assert_eq!(f.estimate[1].value, rtt_24);
336        assert_eq!(f.estimate[2].value, rtt_24);
337
338        time += Duration::from_millis(300);
339        rtt_min = f.running_min(win, time, rtt_25);
340        assert_eq!(rtt_min, rtt_23);
341        assert_eq!(f.estimate[1].value, rtt_24);
342        assert_eq!(f.estimate[2].value, rtt_25);
343
344        time += Duration::from_millis(300);
345        rtt_min = f.running_min(win, time, rtt_22);
346        assert_eq!(rtt_min, rtt_22);
347        assert_eq!(f.estimate[1].value, rtt_22);
348        assert_eq!(f.estimate[2].value, rtt_22);
349    }
350
351    #[test]
352    fn get_windowed_min_estimates_bandwidth() {
353        let mut f = Minmax::new(0);
354        let bw_500 = 500;
355        let bw_400 = 400;
356        let bw_300 = 300;
357        let bw_200 = 200;
358        let win = Duration::from_secs(1);
359        let mut time = Instant::now();
360
361        let mut bw_min = f.reset(time, bw_300);
362        assert_eq!(bw_min, bw_300);
363
364        time += Duration::from_millis(300);
365        bw_min = f.running_min(win, time, bw_400);
366        assert_eq!(bw_min, bw_300);
367        assert_eq!(f.estimate[1].value, bw_400);
368        assert_eq!(f.estimate[2].value, bw_400);
369
370        time += Duration::from_millis(300);
371        bw_min = f.running_min(win, time, bw_500);
372        assert_eq!(bw_min, bw_300);
373        assert_eq!(f.estimate[1].value, bw_400);
374        assert_eq!(f.estimate[2].value, bw_500);
375
376        time += Duration::from_millis(300);
377        bw_min = f.running_min(win, time, bw_200);
378        assert_eq!(bw_min, bw_200);
379        assert_eq!(f.estimate[1].value, bw_200);
380        assert_eq!(f.estimate[2].value, bw_200);
381    }
382
383    #[test]
384    fn get_windowed_max_estimates_rtt() {
385        let mut f = Minmax::new(Duration::ZERO);
386        let rtt_25 = Duration::from_millis(25);
387        let rtt_24 = Duration::from_millis(24);
388        let rtt_23 = Duration::from_millis(23);
389        let rtt_26 = Duration::from_millis(26);
390        let win = Duration::from_secs(1);
391        let mut time = Instant::now();
392
393        let mut rtt_max = f.reset(time, rtt_25);
394        assert_eq!(rtt_max, rtt_25);
395
396        time += Duration::from_millis(300);
397        rtt_max = f.running_max(win, time, rtt_24);
398        assert_eq!(rtt_max, rtt_25);
399        assert_eq!(f.estimate[1].value, rtt_24);
400        assert_eq!(f.estimate[2].value, rtt_24);
401
402        time += Duration::from_millis(300);
403        rtt_max = f.running_max(win, time, rtt_23);
404        assert_eq!(rtt_max, rtt_25);
405        assert_eq!(f.estimate[1].value, rtt_24);
406        assert_eq!(f.estimate[2].value, rtt_23);
407
408        time += Duration::from_millis(300);
409        rtt_max = f.running_max(win, time, rtt_26);
410        assert_eq!(rtt_max, rtt_26);
411        assert_eq!(f.estimate[1].value, rtt_26);
412        assert_eq!(f.estimate[2].value, rtt_26);
413    }
414
415    #[test]
416    fn get_windowed_max_estimates_bandwidth() {
417        let mut f = Minmax::new(0);
418        let bw_500 = 500;
419        let bw_400 = 400;
420        let bw_300 = 300;
421        let bw_600 = 600;
422        let win = Duration::from_secs(1);
423        let mut time = Instant::now();
424
425        let mut bw_max = f.reset(time, bw_500);
426        assert_eq!(bw_max, bw_500);
427
428        time += Duration::from_millis(300);
429        bw_max = f.running_max(win, time, bw_400);
430        assert_eq!(bw_max, bw_500);
431        assert_eq!(f.estimate[1].value, bw_400);
432        assert_eq!(f.estimate[2].value, bw_400);
433
434        time += Duration::from_millis(300);
435        bw_max = f.running_max(win, time, bw_300);
436        assert_eq!(bw_max, bw_500);
437        assert_eq!(f.estimate[1].value, bw_400);
438        assert_eq!(f.estimate[2].value, bw_300);
439
440        time += Duration::from_millis(300);
441        bw_max = f.running_max(win, time, bw_600);
442        assert_eq!(bw_max, bw_600);
443        assert_eq!(f.estimate[1].value, bw_600);
444        assert_eq!(f.estimate[2].value, bw_600);
445    }
446}
quiche/minmax.rs

quiche/
minmax.rs
