Skip to main content

hopr_protocol_session/processing/
reorder.rs

1//! The reordering a Session's incoming frames show, and the gap wait it supports.
2
3use std::{
4    collections::VecDeque,
5    sync::Arc,
6    time::{Duration, Instant},
7};
8
9use crate::protocol::FrameId;
10
11/// How long a reordering sample informs the gap wait.
12///
13/// Long enough to carry what a Session learned across an idle spell: a forward path that died
14/// while nothing was sent shows only once data resumes. Short enough that reordering on paths
15/// since replaced stops lengthening every later gap.
16const REORDER_MEMORY: Duration = Duration::from_secs(60);
17
18/// The gap wait as a multiple of the deepest reordering remembered.
19const REORDER_FACTOR: u32 = 2;
20
21/// The shortest gap wait reordering can bring the wait down to.
22pub(crate) const REORDER_FLOOR: Duration = Duration::from_millis(250);
23
24/// Abandoned gaps remembered, to tell a frame that comes after its gap was given up.
25pub(crate) const ABANDONED_MEMORY: usize = 64;
26
27/// The fewest samples, and the shortest time they must span within [`REORDER_MEMORY`], before the
28/// gap wait is sized by them rather than kept at `max_wait`.
29///
30/// A window that trusts its first samples is sized by whatever paths those happened to take. On a
31/// cluster, the Entry's first echo frames assembled within 24–66 ms while frames a second later took
32/// 330 ms: the wait fell to its floor at once, and frames whose last segments came later than it
33/// were given up, then their segments dropped as already seen, 15 % of a warm-up lost. Five seconds
34/// span the paths a Session's first refreshes plan.
35const MIN_SAMPLES: u32 = 8;
36const MIN_OBSERVATION: Duration = Duration::from_secs(5);
37
38/// The reordering a Session's incoming frames have shown, and the gap wait it supports.
39///
40/// Two kinds of sample, both a span over which data sent together arrived apart:
41/// - the sequencer's: how long a frame came after the earliest frame already waiting behind it, because its gap closed
42///   when it arrived or because it came after its gap was given up (which is what a wait too short for the Session
43///   leads to, and what lengthens the wait again);
44/// - the reassembler's: how long a frame of several segments took from its first segment to its last. Its segments are
45///   sent together and take different paths, so this is the spread of the paths' latencies, and frames sent one after
46///   another cannot arrive further apart than that. Frames that are many segments each rarely arrive out of order, so
47///   without this a Session of such frames would have no sample at all.
48///
49/// A late arrival counts too: a segment that comes after its frame's gap was given up is noticed
50/// where segments come in, since its frame never completes, and is a sample of how late it came.
51///
52/// The gap wait is [`REORDER_FACTOR`] times the deepest sample of the last [`REORDER_MEMORY`],
53/// within `[REORDER_FLOOR, max_wait]`; it is `max_wait` until at least [`MIN_SAMPLES`] samples
54/// span [`MIN_OBSERVATION`] of that memory.
55#[derive(Debug, Default)]
56struct ReorderWindow {
57    /// The samples that are still the deepest of everything recorded after them, oldest first, so
58    /// each is shallower than the one before it and the front is the deepest of the memory: a
59    /// sliding-window maximum, constant time per sample however many frames arrive.
60    deepest: VecDeque<(Instant, Duration)>,
61    /// How many samples were recorded, per second of the memory: when its first sample came, and
62    /// how many came within the second after it.
63    counts: VecDeque<(Instant, u32)>,
64    /// When the latest sample was recorded: the samples in the memory span from the first of
65    /// [`counts`](Self::counts) to this.
66    last: Option<Instant>,
67    abandoned: VecDeque<(FrameId, Instant)>,
68}
69
70impl ReorderWindow {
71    fn forget_before(&mut self, now: Instant) {
72        let gone = |at: &Instant| now.saturating_duration_since(*at) > REORDER_MEMORY;
73        while self.deepest.front().is_some_and(|(at, _)| gone(at)) {
74            self.deepest.pop_front();
75        }
76        while self.counts.front().is_some_and(|(at, _)| gone(at)) {
77            self.counts.pop_front();
78        }
79    }
80
81    /// Whether the samples in the memory are enough to size the wait by: [`MIN_SAMPLES`] of them,
82    /// the first and the latest [`MIN_OBSERVATION`] apart. It is the span of the samples that counts,
83    /// not the age of the oldest: samples that all came in the first second of a Session that then
84    /// went quiet span that second, however long ago it was.
85    fn seen_enough(&self) -> bool {
86        self.counts.iter().map(|(_, count)| *count).sum::<u32>() >= MIN_SAMPLES
87            && self
88                .counts
89                .front()
90                .zip(self.last)
91                .is_some_and(|((first, _), last)| last.saturating_duration_since(*first) >= MIN_OBSERVATION)
92    }
93}
94
95/// A [`ReorderWindow`] shared by a Session's reassembler and sequencer.
96#[derive(Clone, Debug, Default)]
97pub(crate) struct SharedReorder(Arc<parking_lot::Mutex<ReorderWindow>>);
98
99impl SharedReorder {
100    /// Records a span over which data sent together arrived apart.
101    pub(crate) fn record(&self, now: Instant, sample: Duration) {
102        let mut window = self.0.lock();
103        window.forget_before(now);
104        // A sample no deeper than this one, and older, can never be the deepest again.
105        while window.deepest.back().is_some_and(|(_, deepest)| *deepest <= sample) {
106            window.deepest.pop_back();
107        }
108        window.deepest.push_back((now, sample));
109        match window.counts.back_mut() {
110            Some((second, count)) if now.saturating_duration_since(*second) < Duration::from_secs(1) => *count += 1,
111            _ => window.counts.push_back((now, 1)),
112        }
113        window.last = window.last.max(Some(now));
114    }
115
116    /// How long to wait on a gap: see [`ReorderWindow`].
117    pub(crate) fn wait(&self, now: Instant, max_wait: Duration) -> Duration {
118        let mut window = self.0.lock();
119        window.forget_before(now);
120        if !window.seen_enough() {
121            return max_wait;
122        }
123        window
124            .deepest
125            .front()
126            .map(|(_, deepest)| *deepest)
127            .map_or(max_wait, |deepest| {
128                deepest
129                    .saturating_mul(REORDER_FACTOR)
130                    .clamp(REORDER_FLOOR.min(max_wait), max_wait)
131            })
132    }
133
134    /// Remembers that the gap at `id` was given up while the frame behind it had waited since
135    /// `behind_since`.
136    pub(crate) fn note_abandoned(&self, id: FrameId, behind_since: Instant) {
137        let mut window = self.0.lock();
138        if window.abandoned.len() == ABANDONED_MEMORY {
139            window.abandoned.pop_front();
140        }
141        window.abandoned.push_back((id, behind_since));
142    }
143
144    /// A window that has already seen enough to size the wait by: [`MIN_SAMPLES`] samples of 1 ms
145    /// spread over the [`MIN_OBSERVATION`] before the last second.
146    #[cfg(test)]
147    pub(crate) fn warmed() -> Self {
148        let window = Self::default();
149        let now = Instant::now();
150        let first = now
151            .checked_sub(MIN_OBSERVATION + Duration::from_secs(1))
152            .expect("monotonic clock older than the observation");
153        for i in 0..MIN_SAMPLES {
154            window.record(
155                first + MIN_OBSERVATION * i / (MIN_SAMPLES - 1),
156                Duration::from_millis(1),
157            );
158        }
159        window
160    }
161
162    /// How late `id` came, if its gap was given up.
163    pub(crate) fn late(&self, id: FrameId, now: Instant) -> Option<Duration> {
164        self.0
165            .lock()
166            .abandoned
167            .iter()
168            .find(|(abandoned, _)| *abandoned == id)
169            .map(|(_, behind_since)| now.duration_since(*behind_since))
170    }
171}
172
173#[cfg(test)]
174mod tests {
175    use super::*;
176
177    #[test]
178    fn the_wait_should_be_max_wait_before_any_sample() {
179        let window = SharedReorder::default();
180        assert_eq!(
181            Duration::from_secs(3),
182            window.wait(Instant::now(), Duration::from_secs(3))
183        );
184    }
185
186    /// A window that has seen [`MIN_SAMPLES`] shallow samples spread over [`MIN_OBSERVATION`],
187    /// ending at the returned instant.
188    fn warmed(window: &SharedReorder, start: Instant) -> Instant {
189        for i in 0..MIN_SAMPLES {
190            window.record(
191                start + MIN_OBSERVATION * i / (MIN_SAMPLES - 1),
192                Duration::from_millis(1),
193            );
194        }
195        start + MIN_OBSERVATION
196    }
197
198    /// The first samples say little about the paths a Session will take: until enough of them span
199    /// enough time, the wait stays at `max_wait`, however shallow they are and however long ago they
200    /// came.
201    #[test]
202    fn the_wait_should_stay_at_max_wait_until_enough_samples_span_enough_time() {
203        let window = SharedReorder::default();
204        let start = Instant::now();
205        let max_wait = Duration::from_secs(3);
206
207        for i in 0..100u32 {
208            window.record(start + Duration::from_millis(u64::from(i)), Duration::from_millis(20));
209        }
210        assert_eq!(
211            max_wait,
212            window.wait(start + Duration::from_secs(1), max_wait),
213            "many, but within a second"
214        );
215        assert_eq!(
216            max_wait,
217            window.wait(start + MIN_OBSERVATION, max_wait),
218            "many, and long ago, but all within a second: a Session that went quiet"
219        );
220
221        let few = SharedReorder::default();
222        few.record(start, Duration::from_millis(20));
223        few.record(start + MIN_OBSERVATION, Duration::from_millis(20));
224        assert_eq!(
225            max_wait,
226            few.wait(start + MIN_OBSERVATION, max_wait),
227            "long enough, but too few"
228        );
229
230        window.record(start + MIN_OBSERVATION, Duration::from_millis(20));
231        assert_eq!(
232            REORDER_FLOOR,
233            window.wait(start + MIN_OBSERVATION, max_wait),
234            "enough of both"
235        );
236    }
237
238    #[test]
239    fn the_wait_should_be_twice_the_deepest_sample_within_its_bounds() {
240        let window = SharedReorder::default();
241        let now = warmed(&window, Instant::now());
242        let max_wait = Duration::from_secs(3);
243
244        window.record(now, Duration::from_millis(50));
245        assert_eq!(REORDER_FLOOR, window.wait(now, max_wait), "floored");
246
247        window.record(now, Duration::from_millis(400));
248        window.record(now, Duration::from_millis(300));
249        assert_eq!(
250            Duration::from_millis(800),
251            window.wait(now, max_wait),
252            "the deepest counts"
253        );
254
255        window.record(now, Duration::from_secs(2));
256        assert_eq!(max_wait, window.wait(now, max_wait), "capped");
257
258        assert_eq!(
259            Duration::from_millis(100),
260            window.wait(now, Duration::from_millis(100)),
261            "a max_wait under the floor is kept"
262        );
263    }
264
265    #[test]
266    fn a_sample_should_be_forgotten_after_the_memory() {
267        let window = SharedReorder::default();
268        let then = warmed(&window, Instant::now());
269        let max_wait = Duration::from_secs(3);
270
271        window.record(then, Duration::from_millis(400));
272        assert_eq!(Duration::from_millis(800), window.wait(then, max_wait));
273        let later = then + REORDER_MEMORY + Duration::from_secs(1);
274        assert_eq!(max_wait, window.wait(later, max_wait), "nothing left in the memory");
275
276        warmed(&window, later);
277        window.record(later + MIN_OBSERVATION, Duration::from_millis(200));
278        assert_eq!(
279            Duration::from_millis(400),
280            window.wait(later + MIN_OBSERVATION, max_wait),
281            "only the fresh one"
282        );
283    }
284
285    /// However many frames arrive, the window keeps only the samples that can still be the deepest.
286    #[test]
287    fn the_window_should_keep_only_samples_that_can_still_be_the_deepest() {
288        let window = SharedReorder::default();
289        let start = Instant::now();
290        let max_wait = Duration::from_secs(3);
291
292        // Shrinking samples are each still the deepest of what follows them ...
293        for i in 0..5u64 {
294            window.record(start + Duration::from_millis(i), Duration::from_millis(500 - 100 * i));
295        }
296        assert_eq!(5, window.0.lock().deepest.len());
297        // ... until a deeper one makes all of them moot.
298        window.record(start + Duration::from_millis(10), Duration::from_millis(600));
299        assert_eq!(1, window.0.lock().deepest.len());
300
301        for i in 0..100_000u64 {
302            window.record(
303                start + Duration::from_millis(20 + i / 100),
304                Duration::from_millis(i % 7),
305            );
306        }
307        assert!(window.0.lock().deepest.len() <= 8, "{}", window.0.lock().deepest.len());
308        // A shallow sample well past the observation, so that the samples span it before and after
309        // the deep one is forgotten.
310        let spanned = start + MIN_OBSERVATION + Duration::from_secs(2);
311        window.record(spanned, Duration::from_millis(1));
312        assert_eq!(Duration::from_millis(1200), window.wait(spanned, max_wait));
313
314        // Once the deep one is past the memory, the next deepest takes over.
315        let later = start + Duration::from_millis(10) + REORDER_MEMORY + Duration::from_millis(1);
316        assert_eq!(REORDER_FLOOR, window.wait(later, max_wait));
317    }
318
319    #[test]
320    fn an_abandoned_gap_should_be_remembered_for_a_bounded_number_of_gaps() {
321        let window = SharedReorder::default();
322        let then = Instant::now();
323        for id in 1..=(ABANDONED_MEMORY as FrameId + 1) {
324            window.note_abandoned(id, then);
325        }
326        let now = then + Duration::from_millis(700);
327        assert_eq!(None, window.late(1, now), "the oldest is dropped");
328        assert_eq!(Some(Duration::from_millis(700)), window.late(2, now));
329        assert_eq!(None, window.late(1000, now), "never abandoned");
330    }
331}