round trips in trees

1 files changed, 63 insertions, 0 deletions

diff --git a/src/swarm/rtt.rs b/src/swarm/rtt.rs
index cf91ac2..370754c 100644
--- a/src/swarm/rtt.rs
+++ b/src/swarm/rtt.rs
@@ -108,6 +108,51 @@ impl RttTable {
     }
 }
 
+/// Upper bounds of the round-trip buckets in which members tell how far those they
+/// reach are (`swarm::reach`), in ms; the last bucket is above them all. Doubling: a
+/// writer's tree only needs to tell which of a member's possible parents is clearly the
+/// faster (`swarm::tree`), and a coarse value changes seldom, and with it what is told.
+const BUCKET_BOUNDS_MS: [u64; 6] = [25, 50, 100, 200, 400, 800];
+
+/// The bucket of a link without a round trip measured: in the middle, neither fast
+/// nor slow.
+pub(crate) const UNKNOWN_BUCKET: u8 = 3;
+
+/// How far past a bound a round trip goes before its bucket changes: a round trip close
+/// to a bound would otherwise move between two buckets, and every move is told to every
+/// neighbour and may change who passes changes to whom.
+const BUCKET_HYSTERESIS: f64 = 0.2;
+
+/// The round-trip bucket of a link (`BUCKET_BOUNDS_MS`): `rtt`'s, unless it is still
+/// within `BUCKET_HYSTERESIS` of the bucket `before` (as last told). Without a round
+/// trip, as before; never measured, `UNKNOWN_BUCKET`.
+pub(crate) fn bucket(rtt: Option<Duration>, before: Option<u8>) -> u8 {
+    let Some(rtt) = rtt else {
+        return before.unwrap_or(UNKNOWN_BUCKET);
+    };
+    let ms = rtt.as_secs_f64() * 1000.0;
+    let plain = BUCKET_BOUNDS_MS
+        .iter()
+        .take_while(|bound| ms >= **bound as f64)
+        .count() as u8;
+    let Some(before) = before.filter(|before| *before != plain) else {
+        return plain;
+    };
+    let index = usize::from(before);
+    let lower = index
+        .checked_sub(1)
+        .and_then(|below| BUCKET_BOUNDS_MS.get(below))
+        .map_or(0.0, |bound| *bound as f64 * (1.0 - BUCKET_HYSTERESIS));
+    let upper = BUCKET_BOUNDS_MS.get(index).map_or(f64::INFINITY, |bound| {
+        *bound as f64 * (1.0 + BUCKET_HYSTERESIS)
+    });
+    if (lower..upper).contains(&ms) {
+        before
+    } else {
+        plain
+    }
+}
+
 #[cfg(test)]
 mod tests {
     use super::*;
@@ -169,4 +214,22 @@ mod tests {
         let stale = start + FRESH + Duration::from_secs(1);
         assert_eq!(table.effective("a", stale, FRESH), None);
     }
+
+    #[test]
+    fn buckets_double_and_hold_near_their_bounds() {
+        let ms = |ms| Some(Duration::from_millis(ms));
+        assert_eq!(bucket(ms(10), None), 0);
+        assert_eq!(bucket(ms(25), None), 1);
+        assert_eq!(bucket(ms(150), None), 3);
+        assert_eq!(bucket(ms(5000), None), 6);
+        assert_eq!(bucket(None, None), UNKNOWN_BUCKET);
+        assert_eq!(bucket(None, Some(1)), 1, "unmeasured now: as before");
+        // Just past a bound: still the bucket told before.
+        assert_eq!(bucket(ms(110), Some(2)), 2);
+        assert_eq!(bucket(ms(45), Some(2)), 2);
+        // Well past it: the new one.
+        assert_eq!(bucket(ms(130), Some(2)), 3);
+        assert_eq!(bucket(ms(35), Some(2)), 1);
+        assert_eq!(bucket(ms(2000), Some(6)), 6);
+    }
 }