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    pub fn running_max(&mut self, win: Duration, time: Instant, meas: T) -> T {
122        let val = MinmaxSample { time, value: meas };
123
124        let delta_time = time.duration_since(self.estimate[2].time);
125
126        // Reset if there's nothing in the window or a new max value is found.
127        if val.value >= self.estimate[0].value || delta_time > win {
128            return self.reset(time, meas);
129        }
130
131        if val.value >= self.estimate[1].value {
132            self.estimate[2] = val;
133            self.estimate[1] = val;
134        } else if val.value >= self.estimate[2].value {
135            self.estimate[2] = val
136        }
137
138        self.subwin_update(win, time, meas)
139    }
140
141    /// As time advances, update the 1st, 2nd and 3rd estimates.
142    fn subwin_update(&mut self, win: Duration, time: Instant, meas: T) -> T {
143        let val = MinmaxSample { time, value: meas };
144
145        let delta_time = time.duration_since(self.estimate[0].time);
146
147        if delta_time > win {
148            // Passed entire window without a new val so make 2nd estimate the
149            // new val & 3rd estimate the new 2nd choice. we may have to iterate
150            // this since our 2nd estimate may also be outside the window (we
151            // checked on entry that the third estimate was in the window).
152            self.estimate[0] = self.estimate[1];
153            self.estimate[1] = self.estimate[2];
154            self.estimate[2] = val;
155
156            if time.duration_since(self.estimate[0].time) > win {
157                self.estimate[0] = self.estimate[1];
158                self.estimate[1] = self.estimate[2];
159                self.estimate[2] = val;
160            }
161        } else if self.estimate[1].time == self.estimate[0].time &&
162            delta_time > win.div_f32(4.0)
163        {
164            // We've passed a quarter of the window without a new val so take a
165            // 2nd estimate from the 2nd quarter of the window.
166            self.estimate[2] = val;
167            self.estimate[1] = val;
168        } else if self.estimate[2].time == self.estimate[1].time &&
169            delta_time > win.div_f32(2.0)
170        {
171            // We've passed half the window without finding a new val so take a
172            // 3rd estimate from the last half of the window.
173            self.estimate[2] = val;
174        }
175
176        self.estimate[0].value
177    }
178}
179
180#[cfg(test)]
181mod tests {
182    use super::*;
183
184    #[test]
185    fn reset_filter_rtt() {
186        let mut f = Minmax::new(Duration::ZERO);
187        let now = Instant::now();
188        let rtt = Duration::from_millis(50);
189
190        let rtt_min = f.reset(now, rtt);
191        assert_eq!(rtt_min, rtt);
192
193        assert_eq!(f.estimate[0].time, now);
194        assert_eq!(f.estimate[0].value, rtt);
195
196        assert_eq!(f.estimate[1].time, now);
197        assert_eq!(f.estimate[1].value, rtt);
198
199        assert_eq!(f.estimate[2].time, now);
200        assert_eq!(f.estimate[2].value, rtt);
201    }
202
203    #[test]
204    fn reset_filter_bandwidth() {
205        let mut f = Minmax::new(0);
206        let now = Instant::now();
207        let bw = 2000;
208
209        let bw_min = f.reset(now, bw);
210        assert_eq!(bw_min, bw);
211
212        assert_eq!(f.estimate[0].time, now);
213        assert_eq!(f.estimate[0].value, bw);
214
215        assert_eq!(f.estimate[1].time, now);
216        assert_eq!(f.estimate[1].value, bw);
217
218        assert_eq!(f.estimate[2].time, now);
219        assert_eq!(f.estimate[2].value, bw);
220    }
221
222    #[test]
223    fn get_windowed_min_rtt() {
224        let mut f = Minmax::new(Duration::ZERO);
225        let rtt_25 = Duration::from_millis(25);
226        let rtt_24 = Duration::from_millis(24);
227        let win = Duration::from_millis(500);
228        let mut time = Instant::now();
229
230        let mut rtt_min = f.reset(time, rtt_25);
231        assert_eq!(rtt_min, rtt_25);
232
233        time += Duration::from_millis(250);
234        rtt_min = f.running_min(win, time, rtt_24);
235        assert_eq!(rtt_min, rtt_24);
236        assert_eq!(f.estimate[1].value, rtt_24);
237        assert_eq!(f.estimate[2].value, rtt_24);
238
239        time += Duration::from_millis(600);
240        rtt_min = f.running_min(win, time, rtt_25);
241        assert_eq!(rtt_min, rtt_25);
242        assert_eq!(f.estimate[1].value, rtt_25);
243        assert_eq!(f.estimate[2].value, rtt_25);
244    }
245
246    #[test]
247    fn get_windowed_min_bandwidth() {
248        let mut f = Minmax::new(0);
249        let bw_200 = 200;
250        let bw_500 = 500;
251        let win = Duration::from_millis(500);
252        let mut time = Instant::now();
253
254        let mut bw_min = f.reset(time, bw_500);
255        assert_eq!(bw_min, bw_500);
256
257        time += Duration::from_millis(250);
258        bw_min = f.running_min(win, time, bw_200);
259        assert_eq!(bw_min, bw_200);
260        assert_eq!(f.estimate[1].value, bw_200);
261        assert_eq!(f.estimate[2].value, bw_200);
262
263        time += Duration::from_millis(600);
264        bw_min = f.running_min(win, time, bw_500);
265        assert_eq!(bw_min, bw_500);
266        assert_eq!(f.estimate[1].value, bw_500);
267        assert_eq!(f.estimate[2].value, bw_500);
268    }
269
270    #[test]
271    fn get_windowed_max_rtt() {
272        let mut f = Minmax::new(Duration::ZERO);
273        let rtt_25 = Duration::from_millis(25);
274        let rtt_24 = Duration::from_millis(24);
275        let win = Duration::from_millis(500);
276        let mut time = Instant::now();
277
278        let mut rtt_max = f.reset(time, rtt_24);
279        assert_eq!(rtt_max, rtt_24);
280
281        time += Duration::from_millis(250);
282        rtt_max = f.running_max(win, time, rtt_25);
283        assert_eq!(rtt_max, rtt_25);
284        assert_eq!(f.estimate[1].value, rtt_25);
285        assert_eq!(f.estimate[2].value, rtt_25);
286
287        time += Duration::from_millis(600);
288        rtt_max = f.running_max(win, time, rtt_24);
289        assert_eq!(rtt_max, rtt_24);
290        assert_eq!(f.estimate[1].value, rtt_24);
291        assert_eq!(f.estimate[2].value, rtt_24);
292    }
293
294    #[test]
295    fn get_windowed_max_bandwidth() {
296        let mut f = Minmax::new(0);
297        let bw_200 = 200;
298        let bw_500 = 500;
299        let win = Duration::from_millis(500);
300        let mut time = Instant::now();
301
302        let mut bw_max = f.reset(time, bw_200);
303        assert_eq!(bw_max, bw_200);
304
305        time += Duration::from_millis(5000);
306        bw_max = f.running_max(win, time, bw_500);
307        assert_eq!(bw_max, bw_500);
308        assert_eq!(f.estimate[1].value, bw_500);
309        assert_eq!(f.estimate[2].value, bw_500);
310
311        time += Duration::from_millis(600);
312        bw_max = f.running_max(win, time, bw_200);
313        assert_eq!(bw_max, bw_200);
314        assert_eq!(f.estimate[1].value, bw_200);
315        assert_eq!(f.estimate[2].value, bw_200);
316    }
317
318    #[test]
319    fn get_windowed_min_estimates_rtt() {
320        let mut f = Minmax::new(Duration::ZERO);
321        let rtt_25 = Duration::from_millis(25);
322        let rtt_24 = Duration::from_millis(24);
323        let rtt_23 = Duration::from_millis(23);
324        let rtt_22 = Duration::from_millis(22);
325        let win = Duration::from_secs(1);
326        let mut time = Instant::now();
327
328        let mut rtt_min = f.reset(time, rtt_23);
329        assert_eq!(rtt_min, rtt_23);
330
331        time += Duration::from_millis(300);
332        rtt_min = f.running_min(win, time, rtt_24);
333        assert_eq!(rtt_min, rtt_23);
334        assert_eq!(f.estimate[1].value, rtt_24);
335        assert_eq!(f.estimate[2].value, rtt_24);
336
337        time += Duration::from_millis(300);
338        rtt_min = f.running_min(win, time, rtt_25);
339        assert_eq!(rtt_min, rtt_23);
340        assert_eq!(f.estimate[1].value, rtt_24);
341        assert_eq!(f.estimate[2].value, rtt_25);
342
343        time += Duration::from_millis(300);
344        rtt_min = f.running_min(win, time, rtt_22);
345        assert_eq!(rtt_min, rtt_22);
346        assert_eq!(f.estimate[1].value, rtt_22);
347        assert_eq!(f.estimate[2].value, rtt_22);
348    }
349
350    #[test]
351    fn get_windowed_min_estimates_bandwidth() {
352        let mut f = Minmax::new(0);
353        let bw_500 = 500;
354        let bw_400 = 400;
355        let bw_300 = 300;
356        let bw_200 = 200;
357        let win = Duration::from_secs(1);
358        let mut time = Instant::now();
359
360        let mut bw_min = f.reset(time, bw_300);
361        assert_eq!(bw_min, bw_300);
362
363        time += Duration::from_millis(300);
364        bw_min = f.running_min(win, time, bw_400);
365        assert_eq!(bw_min, bw_300);
366        assert_eq!(f.estimate[1].value, bw_400);
367        assert_eq!(f.estimate[2].value, bw_400);
368
369        time += Duration::from_millis(300);
370        bw_min = f.running_min(win, time, bw_500);
371        assert_eq!(bw_min, bw_300);
372        assert_eq!(f.estimate[1].value, bw_400);
373        assert_eq!(f.estimate[2].value, bw_500);
374
375        time += Duration::from_millis(300);
376        bw_min = f.running_min(win, time, bw_200);
377        assert_eq!(bw_min, bw_200);
378        assert_eq!(f.estimate[1].value, bw_200);
379        assert_eq!(f.estimate[2].value, bw_200);
380    }
381
382    #[test]
383    fn get_windowed_max_estimates_rtt() {
384        let mut f = Minmax::new(Duration::ZERO);
385        let rtt_25 = Duration::from_millis(25);
386        let rtt_24 = Duration::from_millis(24);
387        let rtt_23 = Duration::from_millis(23);
388        let rtt_26 = Duration::from_millis(26);
389        let win = Duration::from_secs(1);
390        let mut time = Instant::now();
391
392        let mut rtt_max = f.reset(time, rtt_25);
393        assert_eq!(rtt_max, rtt_25);
394
395        time += Duration::from_millis(300);
396        rtt_max = f.running_max(win, time, rtt_24);
397        assert_eq!(rtt_max, rtt_25);
398        assert_eq!(f.estimate[1].value, rtt_24);
399        assert_eq!(f.estimate[2].value, rtt_24);
400
401        time += Duration::from_millis(300);
402        rtt_max = f.running_max(win, time, rtt_23);
403        assert_eq!(rtt_max, rtt_25);
404        assert_eq!(f.estimate[1].value, rtt_24);
405        assert_eq!(f.estimate[2].value, rtt_23);
406
407        time += Duration::from_millis(300);
408        rtt_max = f.running_max(win, time, rtt_26);
409        assert_eq!(rtt_max, rtt_26);
410        assert_eq!(f.estimate[1].value, rtt_26);
411        assert_eq!(f.estimate[2].value, rtt_26);
412    }
413
414    #[test]
415    fn get_windowed_max_estimates_bandwidth() {
416        let mut f = Minmax::new(0);
417        let bw_500 = 500;
418        let bw_400 = 400;
419        let bw_300 = 300;
420        let bw_600 = 600;
421        let win = Duration::from_secs(1);
422        let mut time = Instant::now();
423
424        let mut bw_max = f.reset(time, bw_500);
425        assert_eq!(bw_max, bw_500);
426
427        time += Duration::from_millis(300);
428        bw_max = f.running_max(win, time, bw_400);
429        assert_eq!(bw_max, bw_500);
430        assert_eq!(f.estimate[1].value, bw_400);
431        assert_eq!(f.estimate[2].value, bw_400);
432
433        time += Duration::from_millis(300);
434        bw_max = f.running_max(win, time, bw_300);
435        assert_eq!(bw_max, bw_500);
436        assert_eq!(f.estimate[1].value, bw_400);
437        assert_eq!(f.estimate[2].value, bw_300);
438
439        time += Duration::from_millis(300);
440        bw_max = f.running_max(win, time, bw_600);
441        assert_eq!(bw_max, bw_600);
442        assert_eq!(f.estimate[1].value, bw_600);
443        assert_eq!(f.estimate[2].value, bw_600);
444    }
445}
quiche/minmax.rs

quiche/
minmax.rs
