ndn_discovery/strategy/
backoff.rs

1//! Exponential-backoff probe scheduler.
2//!
3//! Starts at [`DiscoveryConfig::hello_interval_base`] and doubles on each tick
4//! where no probe is needed, up to [`DiscoveryConfig::hello_interval_max`].
5//! Jitter of ±[`DiscoveryConfig::hello_jitter`] × interval is applied to
6//! each computed deadline to desynchronise nodes that started simultaneously.
7//!
8//! # Reset behaviour
9//!
10//! Any [`TriggerEvent`] resets the interval to the base and sets
11//! `pending_immediate = true` so that the very next [`on_tick`] call emits
12//! a [`ProbeRequest::Broadcast`] without waiting for the deadline.  A
13//! successful probe ([`on_probe_success`]) similarly resets the interval; a
14//! probe timeout ([`on_probe_timeout`]) advances to the next (doubled) level.
15
16use std::time::{Duration, Instant};
17
18use crate::backoff::{BackoffConfig, BackoffState};
19use crate::config::DiscoveryConfig;
20use crate::strategy::{NeighborProbeStrategy, ProbeRequest, TriggerEvent};
21
22// ─── BackoffScheduler ────────────────────────────────────────────────────────
23
24/// Probe scheduler that uses exponential back-off with jitter.
25pub struct BackoffScheduler {
26    cfg: BackoffConfig,
27    state: BackoffState,
28    /// When the next probe should be sent.
29    next_probe_at: Option<Instant>,
30    /// Set to `true` by trigger events so the next `on_tick` fires immediately.
31    pending_immediate: bool,
32}
33
34impl BackoffScheduler {
35    /// Build from the relevant fields of a [`DiscoveryConfig`].
36    pub fn from_discovery_config(cfg: &DiscoveryConfig) -> Self {
37        let backoff_cfg = BackoffConfig {
38            initial_interval: cfg.hello_interval_base,
39            max_interval: cfg.hello_interval_max,
40            jitter_fraction: cfg.hello_jitter as f64,
41        };
42        Self {
43            cfg: backoff_cfg,
44            state: BackoffState::new(seed_from_now()),
45            next_probe_at: None,
46            pending_immediate: true, // send on the very first tick
47        }
48    }
49
50    /// Schedule a deadline `interval` from `now`.
51    fn schedule_next(&mut self, now: Instant, interval: Duration) {
52        self.next_probe_at = Some(now + interval);
53    }
54}
55
56impl NeighborProbeStrategy for BackoffScheduler {
57    fn on_tick(&mut self, now: Instant) -> Vec<ProbeRequest> {
58        let fire = self.pending_immediate || self.next_probe_at.map(|t| now >= t).unwrap_or(true);
59
60        if !fire {
61            return Vec::new();
62        }
63
64        self.pending_immediate = false;
65        // Advance to next backoff level.
66        let interval = self.state.next_failure(&self.cfg);
67        self.schedule_next(now, interval);
68
69        vec![ProbeRequest::Broadcast]
70    }
71
72    fn on_probe_success(&mut self, _rtt: Duration) {
73        self.state.reset(&self.cfg);
74        // Schedule next probe at base interval.
75        let next = self.cfg.initial_interval;
76        self.schedule_next(Instant::now(), next);
77    }
78
79    fn on_probe_timeout(&mut self) {
80        // Advance backoff on next on_tick via the existing state; no change
81        // needed here — next_failure will be called from on_tick.
82    }
83
84    fn trigger(&mut self, _event: TriggerEvent) {
85        // Reset to base and fire immediately.
86        self.state.reset(&self.cfg);
87        self.pending_immediate = true;
88    }
89}
90
91// ─── RNG seed ────────────────────────────────────────────────────────────────
92
93fn seed_from_now() -> u32 {
94    let ns = Instant::now().elapsed().subsec_nanos();
95    if ns == 0 { 0xdeadbeef } else { ns }
96}
97
98// ─── Tests ────────────────────────────────────────────────────────────────────
99
100#[cfg(test)]
101mod tests {
102    use std::time::Duration;
103
104    use super::*;
105    use crate::config::{DiscoveryConfig, DiscoveryProfile};
106
107    fn lan_sched() -> BackoffScheduler {
108        BackoffScheduler::from_discovery_config(&DiscoveryConfig::for_profile(
109            &DiscoveryProfile::Lan,
110        ))
111    }
112
113    #[test]
114    fn fires_on_first_tick() {
115        let mut s = lan_sched();
116        let now = Instant::now();
117        let reqs = s.on_tick(now);
118        assert_eq!(reqs, vec![ProbeRequest::Broadcast]);
119    }
120
121    #[test]
122    fn no_fire_before_deadline() {
123        let mut s = lan_sched();
124        let now = Instant::now();
125        s.on_tick(now); // consume the immediate probe
126        // Immediately after — still within interval.
127        let reqs = s.on_tick(now);
128        assert!(reqs.is_empty());
129    }
130
131    #[test]
132    fn trigger_causes_immediate_probe() {
133        let mut s = lan_sched();
134        let now = Instant::now();
135        s.on_tick(now); // consume initial
136        s.on_tick(now); // still within deadline
137
138        s.trigger(TriggerEvent::FaceUp);
139        let reqs = s.on_tick(now);
140        assert_eq!(reqs, vec![ProbeRequest::Broadcast]);
141    }
142
143    #[test]
144    fn success_resets_interval() {
145        let mut s = lan_sched();
146        let now = Instant::now();
147        // Advance state by failing a few times.
148        s.on_tick(now);
149        s.on_probe_timeout();
150        s.on_tick(now + Duration::from_secs(100));
151        // After success the next deadline should be at base interval.
152        s.on_probe_success(Duration::from_millis(10));
153        assert_eq!(s.state.current(), Duration::ZERO);
154    }
155}
ndn_discovery/strategy/backoff.rs

ndn_discovery/strategy/
backoff.rs
