noq_proto/congestion/bbr3/
max_filter.rs

1use std::fmt::Debug;
2
3const MAX_FILTER_LEN: usize = 3;
4
5/// Based on Linux kernel code released here:
6/// <https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=f672258391b42a5c7cc2732c9c063e56a85c8dbe>
7///
8/// Kathleen Nichols' algorithm for tracking the maximum
9/// value of a data stream over some fixed time interval.  (E.g.,
10/// the maximum Bandwidth achieved over the past 3 rounds.) It uses constant
11/// space and constant time per update yet almost always delivers
12/// the same maximum as an implementation that has to keep all the
13/// data in the window.
14///
15/// The algorithm keeps track of the best, 2nd best & 3rd highest max
16/// values, maintaining an invariant that the measurement time of
17/// the n'th best >= n-1'th best. It also makes sure that the three
18/// values are widely separated in the time window since that bounds
19/// the worst case error when that data is monotonically increasing
20/// over the window.
21///
22/// Upon getting a new max, we can forget everything earlier because
23/// it has no value - the new max is >= everything else in the window
24/// by definition, and it samples the most recent one. So we restart fresh on
25/// every new max and overwrites 2nd & 3rd choices. The same property
26/// holds for 2nd & 3rd best.
27#[derive(Copy, Clone, Debug)]
28pub(super) struct MaxFilter {
29    window: u64,
30    // sample on index 0 has the maximum value followed in descending order
31    // by samples on index 1 and then 2
32    samples: [MaxSample; MAX_FILTER_LEN],
33}
34
35impl MaxFilter {
36    pub(super) fn new(window: u64) -> Self {
37        Self {
38            window,
39            samples: [Default::default(); MAX_FILTER_LEN],
40        }
41    }
42    pub(super) fn get_max(&self) -> u64 {
43        self.samples[0].value.unwrap_or(0)
44    }
45
46    /// `current_round` represents a sequence number counting upwards from 0 monotonically
47    /// `measurement` is what is tracked as the max values over time
48    pub(super) fn update_max(&mut self, current_round: u64, measurement: u64) {
49        let sample = MaxSample {
50            round: current_round,
51            value: Some(measurement),
52        };
53
54        if self.samples[0].value.is_none()  // uninitialised
55            ||  sample.value >= self.samples[0].value // found new max?
56            ||  sample.round.saturating_sub(self.samples[2].round) > self.window
57        // nothing left in window?
58        {
59            self.samples.fill(sample); // forget earlier samples
60            return;
61        }
62
63        if sample.value >= self.samples[1].value {
64            self.samples[1] = sample;
65            self.samples[2] = sample;
66        } else if sample.value >= self.samples[2].value {
67            self.samples[2] = sample;
68        }
69
70        self.subwin_update(sample);
71    }
72
73    /// As time advances, update the 1st, 2nd, and 3rd choices.
74    fn subwin_update(&mut self, sample: MaxSample) {
75        let dt = sample.round.saturating_sub(self.samples[0].round);
76        if dt > self.window {
77            /*
78             * Passed entire window without a new sample so make 2nd
79             * choice the new sample & 3rd choice the new 2nd choice.
80             * we may have to iterate this since our 2nd choice
81             * may also be outside the window (we checked on entry
82             * that the third choice was in the window).
83             */
84            self.samples[0] = self.samples[1];
85            self.samples[1] = self.samples[2];
86            self.samples[2] = sample;
87            if sample.round.saturating_sub(self.samples[0].round) > self.window {
88                self.samples[0] = self.samples[1];
89                self.samples[1] = self.samples[2];
90                self.samples[2] = sample;
91            }
92        } else if self.samples[1].round == self.samples[0].round && dt > self.window / 4 {
93            /*
94             * We've passed a quarter of the window without a new sample
95             * so take a 2nd choice from the 2nd quarter of the window.
96             */
97            self.samples[2] = sample;
98            self.samples[1] = sample;
99        } else if self.samples[2].round == self.samples[1].round && dt > self.window / 2 {
100            /*
101             * We've passed half the window without finding a new sample
102             * so take a 3rd choice from the last half of the window
103             */
104            self.samples[2] = sample;
105        }
106    }
107}
108
109impl Default for MaxFilter {
110    fn default() -> Self {
111        Self {
112            window: 10,
113            samples: [Default::default(); MAX_FILTER_LEN],
114        }
115    }
116}
117
118#[derive(Debug, Copy, Clone, Default)]
119struct MaxSample {
120    /// `round` count, not a timestamp as per <https://www.ietf.org/archive/id/draft-ietf-ccwg-bbr-05.html#section-5.5.1>
121    /// can also be a count of cycle as per <https://www.ietf.org/archive/id/draft-ietf-ccwg-bbr-05.html#section-5.5.6>
122    round: u64,
123    value: Option<u64>,
124}
125
126#[cfg(test)]
127mod test {
128    use super::*;
129
130    #[test]
131    fn test() {
132        let round = 25;
133        let mut max_filter = MaxFilter::default();
134        max_filter.update_max(round + 1, 100);
135        assert_eq!(100, max_filter.get_max());
136        max_filter.update_max(round + 3, 120);
137        assert_eq!(120, max_filter.get_max());
138        max_filter.update_max(round + 5, 160);
139        assert_eq!(160, max_filter.get_max());
140        max_filter.update_max(round + 7, 100);
141        assert_eq!(160, max_filter.get_max());
142        max_filter.update_max(round + 10, 100);
143        assert_eq!(160, max_filter.get_max());
144        max_filter.update_max(round + 14, 100);
145        assert_eq!(160, max_filter.get_max());
146        max_filter.update_max(round + 16, 100);
147        assert_eq!(100, max_filter.get_max());
148        max_filter.update_max(round + 18, 130);
149        assert_eq!(130, max_filter.get_max());
150    }
151}
noq_proto/congestion/bbr3/max_filter.rs

noq_proto/congestion/bbr3/
max_filter.rs
