quiche/recovery/gcongestion/bbr/
windowed_filter.rs

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// Implements Kathleen Nichols' algorithm for tracking the minimum (or maximum)
6// estimate of a stream of samples over some fixed time interval. (E.g.,
7// the minimum RTT over the past five minutes.) The algorithm keeps track of
8// the best, second best, and third best min (or max) estimates, maintaining an
9// invariant that the measurement time of the n'th best >= n-1'th best.
10
11// The algorithm works as follows. On a reset, all three estimates are set to
12// the same sample. The second best estimate is then recorded in the second
13// quarter of the window, and a third best estimate is recorded in the second
14// half of the window, bounding the worst case error when the true min is
15// monotonically increasing (or true max is monotonically decreasing) over the
16// window.
17//
18// A new best sample replaces all three estimates, since the new best is lower
19// (or higher) than everything else in the window and it is the most recent.
20// The window thus effectively gets reset on every new min. The same property
21// holds true for second best and third best estimates. Specifically, when a
22// sample arrives that is better than the second best but not better than the
23// best, it replaces the second and third best estimates but not the best
24// estimate. Similarly, a sample that is better than the third best estimate
25// but not the other estimates replaces only the third best estimate.
26//
27// Finally, when the best expires, it is replaced by the second best, which in
28// turn is replaced by the third best. The newest sample replaces the third
29// best.
30
31use std::ops::Div;
32use std::ops::Sub;
33
34#[derive(Debug, Clone, Copy)]
35struct Sample<T, I> {
36    sample: T,
37    time: I,
38}
39
40#[derive(Debug)]
41pub struct WindowedFilter<T, I, D> {
42    window_length: D,
43    estimates: [Option<Sample<T, I>>; 3],
44}
45
46impl<T, I, D> WindowedFilter<T, I, D>
47where
48    T: Ord + Copy,
49    I: Sub<I, Output = D> + Copy,
50    D: Ord + Div<usize, Output = D> + Copy,
51{
52    pub fn new(window_length: D) -> Self {
53        WindowedFilter {
54            window_length,
55            estimates: [None, None, None],
56        }
57    }
58
59    pub fn reset(&mut self, new_sample: T, new_time: I) {
60        let sample = Some(Sample {
61            sample: new_sample,
62            time: new_time,
63        });
64
65        self.estimates = [sample, sample, sample];
66    }
67
68    pub fn get_best(&self) -> Option<T> {
69        self.estimates[0].as_ref().map(|e| e.sample)
70    }
71
72    pub fn get_second_best(&self) -> Option<T> {
73        self.estimates[1].as_ref().map(|e| e.sample)
74    }
75
76    pub fn get_third_best(&self) -> Option<T> {
77        self.estimates[2].as_ref().map(|e| e.sample)
78    }
79
80    pub fn clear(&mut self) {
81        self.estimates = [None, None, None];
82    }
83
84    pub fn update(&mut self, new_sample: T, new_time: I) {
85        // Reset all estimates if they have not yet been initialized, if new
86        // sample is a new best, or if the newest recorded estimate is too
87        // old.
88        if match &self.estimates[0] {
89            None => true,
90            Some(best) if new_sample > best.sample => true,
91            _ =>
92                new_time - self.estimates[2].as_ref().unwrap().time >
93                    self.window_length,
94        } {
95            return self.reset(new_sample, new_time);
96        }
97
98        if new_sample > self.estimates[1].unwrap().sample {
99            self.estimates[1] = Some(Sample {
100                sample: new_sample,
101                time: new_time,
102            });
103            self.estimates[2] = self.estimates[1];
104        } else if new_sample > self.estimates[2].unwrap().sample {
105            self.estimates[2] = Some(Sample {
106                sample: new_sample,
107                time: new_time,
108            });
109        }
110
111        // Expire and update estimates as necessary.
112        if new_time - self.estimates[0].unwrap().time > self.window_length {
113            // The best estimate hasn't been updated for an entire window, so
114            // promote second and third best estimates.
115            self.estimates[0] = self.estimates[1];
116            self.estimates[1] = self.estimates[2];
117            self.estimates[2] = Some(Sample {
118                sample: new_sample,
119                time: new_time,
120            });
121            // Need to iterate one more time. Check if the new best estimate is
122            // outside the window as well, since it may also have been recorded a
123            // long time ago. Don't need to iterate once more since we cover that
124            // case at the beginning of the method.
125            if new_time - self.estimates[0].unwrap().time > self.window_length {
126                self.estimates[0] = self.estimates[1];
127                self.estimates[1] = self.estimates[2];
128            }
129            return;
130        }
131
132        if self.estimates[1].unwrap().sample == self.estimates[0].unwrap().sample &&
133            new_time - self.estimates[1].unwrap().time > self.window_length / 4
134        {
135            // A quarter of the window has passed without a better sample, so the
136            // second-best estimate is taken from the second quarter of the
137            // window.
138            self.estimates[1] = Some(Sample {
139                sample: new_sample,
140                time: new_time,
141            });
142            self.estimates[2] = self.estimates[1];
143            return;
144        }
145
146        if self.estimates[2].unwrap().sample == self.estimates[1].unwrap().sample &&
147            new_time - self.estimates[2].unwrap().time > self.window_length / 2
148        {
149            // We've passed a half of the window without a better estimate, so
150            // take a third-best estimate from the second half of the
151            // window.
152            self.estimates[2] = Some(Sample {
153                sample: new_sample,
154                time: new_time,
155            });
156        }
157    }
158}
quiche/recovery/gcongestion/bbr/windowed_filter.rs

quiche/recovery/gcongestion/bbr/
windowed_filter.rs
