subetha_cxc/
rtt_shape_sensor.rs

1//! Link-type fingerprint from the SHAPE of the RTT distribution - no new
2//! packets, no OS wireless read.
3//!
4//! 802.11 MAC retransmission splits the round-trip time into two clusters: a
5//! frame that succeeds on the first transmit returns quickly, a frame that is
6//! retried (collision, weak signal) returns a contention-window-and-retry later.
7//! So a Wi-Fi hop makes the RTT distribution **bimodal**, while a wired link is
8//! tight and **unimodal**. Sarle's bimodality coefficient
9//! `b = (skewness^2 + 1) / kurtosis` captures exactly this: `b > 5/9` indicates
10//! bimodality (a uniform distribution sits at `5/9`, a normal near `1/3`, and a
11//! two-peaked distribution above `5/9`).
12//!
13//! Because the coefficient reads the END-TO-END RTT, a Wi-Fi hop ANYWHERE on
14//! the path shows up - so a wired host can detect that its peer is on Wi-Fi,
15//! filling the `Link` class when the local OS wireless read is unavailable.
16//!
17//! The four central moments are maintained online (Pebay's streaming update),
18//! so the fingerprint costs O(1) per RTT sample and no storage.
19
20/// Minimum RTT samples before the bimodality coefficient is trusted - the
21/// third and fourth moments need a population to be stable.
22const MIN_SAMPLES: u64 = 30;
23
24/// Sarle's bimodality threshold: a uniform distribution sits exactly here, a
25/// unimodal one below, a bimodal one above.
26const SARLE_THRESHOLD: f64 = 5.0 / 9.0;
27
28/// Streaming RTT-distribution shape estimator.
29#[derive(Debug, Clone, Default)]
30pub struct RttShape {
31    n: u64,
32    mean: f64,
33    m2: f64,
34    m3: f64,
35    m4: f64,
36}
37
38impl RttShape {
39    pub fn new() -> Self {
40        Self::default()
41    }
42
43    /// Fold one RTT sample (microseconds) into the running moments via Pebay's
44    /// streaming update of the first four central moments.
45    pub fn observe(&mut self, rtt_us: f64) {
46        let n1 = self.n as f64;
47        self.n += 1;
48        let n = self.n as f64;
49        let delta = rtt_us - self.mean;
50        let delta_n = delta / n;
51        let delta_n2 = delta_n * delta_n;
52        let term1 = delta * delta_n * n1;
53        self.mean += delta_n;
54        self.m4 += term1 * delta_n2 * (n * n - 3.0 * n + 3.0) + 6.0 * delta_n2 * self.m2
55            - 4.0 * delta_n * self.m3;
56        self.m3 += term1 * delta_n * (n - 2.0) - 3.0 * delta_n * self.m2;
57        self.m2 += term1;
58    }
59
60    /// Sarle's bimodality coefficient `b = (skewness^2 + 1) / kurtosis`, or
61    /// `None` until `MIN_SAMPLES` samples and a non-degenerate spread. `b` is
62    /// bounded `0..=1`; above `SARLE_THRESHOLD` the distribution is bimodal.
63    pub fn bimodality(&self) -> Option<f64> {
64        if self.n < MIN_SAMPLES || self.m2 <= 0.0 {
65            return None;
66        }
67        let n = self.n as f64;
68        // Population skewness and (non-excess) kurtosis from the central moments.
69        let skewness = n.sqrt() * self.m3 / self.m2.powf(1.5);
70        let kurtosis = n * self.m4 / (self.m2 * self.m2);
71        if kurtosis <= 0.0 {
72            return None;
73        }
74        Some((skewness * skewness + 1.0) / kurtosis)
75    }
76
77    /// Confidence in `0..=1` that the path carries a Wi-Fi hop, from how far the
78    /// bimodality coefficient sits above Sarle's threshold. 0 below threshold
79    /// (unimodal - wired) or before enough samples; rising to 1 as the RTT
80    /// distribution becomes strongly two-peaked (Wi-Fi MAC retransmission).
81    pub fn wifi_confidence(&self) -> f32 {
82        match self.bimodality() {
83            Some(b) if b > SARLE_THRESHOLD => {
84                (((b - SARLE_THRESHOLD) / (1.0 - SARLE_THRESHOLD)).clamp(0.0, 1.0)) as f32
85            }
86            _ => 0.0,
87        }
88    }
89
90    /// Samples folded so far (diagnostics).
91    pub fn samples(&self) -> u64 {
92        self.n
93    }
94}
95
96#[cfg(test)]
97mod tests {
98    use super::*;
99
100    /// A tight unimodal distribution (a wired link: one cluster of RTTs) sits
101    /// below Sarle's threshold, so the Wi-Fi confidence is zero.
102    #[test]
103    fn unimodal_is_not_wifi() {
104        let mut s = RttShape::new();
105        // A narrow triangular bump around 1000 us - one mode.
106        let center = [990.0, 995.0, 1000.0, 1005.0, 1010.0];
107        let weight = [1, 3, 6, 3, 1];
108        for _ in 0..8 {
109            for (v, w) in center.iter().zip(weight) {
110                for _ in 0..w {
111                    s.observe(*v);
112                }
113            }
114        }
115        let b = s.bimodality().expect("enough samples");
116        assert!(b < SARLE_THRESHOLD, "unimodal b={b} should be below 5/9");
117        assert_eq!(s.wifi_confidence(), 0.0, "unimodal -> not Wi-Fi");
118    }
119
120    /// A two-peaked distribution (a Wi-Fi link: a fast first-transmit cluster
121    /// and a slow retried cluster) sits above Sarle's threshold, so the Wi-Fi
122    /// confidence is positive.
123    #[test]
124    fn bimodal_is_wifi() {
125        let mut s = RttShape::new();
126        // Two clusters: ~1000 us first-tx, ~6000 us retried.
127        for _ in 0..60 {
128            s.observe(1000.0);
129            s.observe(6000.0);
130        }
131        let b = s.bimodality().expect("enough samples");
132        assert!(b > SARLE_THRESHOLD, "bimodal b={b} should be above 5/9");
133        assert!(s.wifi_confidence() > 0.0, "bimodal -> Wi-Fi confidence");
134    }
135
136    /// Before enough samples the coefficient is withheld (the higher moments are
137    /// not yet stable), so the fingerprint never fires on a handful of RTTs.
138    #[test]
139    fn withholds_until_enough_samples() {
140        let mut s = RttShape::new();
141        for _ in 0..(MIN_SAMPLES - 1) {
142            s.observe(1000.0);
143        }
144        assert!(s.bimodality().is_none(), "withheld before MIN_SAMPLES");
145        assert_eq!(s.wifi_confidence(), 0.0);
146    }
147}
subetha_cxc/rtt_shape_sensor.rs

subetha_cxc/
rtt_shape_sensor.rs
