slow link a hop more

1 files changed, 73 insertions, 17 deletions

diff --git a/src/swarm/tree.rs b/src/swarm/tree.rs
index 29186d8..0aef94c 100644
--- a/src/swarm/tree.rs
+++ b/src/swarm/tree.rs
@@ -7,8 +7,9 @@
 //! (`swarm::reach`). Every member's distance from the writer over that graph orders the
 //! members: by distance, then whether it reaches a member a hop closer, then pair key;
 //! a member's parent is the neighbour it reaches that comes before it, the closest to
-//! the writer first, then one that reaches closer, then the one it has the shortest
-//! round trip to (as it said, a bucket: `rtt::bucket`), then by pair score
+//! the writer first (a link much slower than its fastest to one counting a hop more),
+//! then one that reaches closer, then the one it has the shortest round trip to (as it
+//! said, a bucket: `rtt::bucket`), then by pair score
 //! (`topology::pair_score`). Coming before rules out cycles, and taking only a neighbour
 //! it reaches routes around links that don't work: where a writer behind NAT reaches a
 //! single member, that one comes first and the others take it.
@@ -95,7 +96,8 @@ fn distances(state: &AppState, writer: u64) -> Option<(Arc<Graph>, Arc<HashMap<S
 /// Members are ordered by distance from the writer, then whether they reach a member a
 /// hop closer (as they say: else, while it hasn't the change from its own side, it is
 /// as good as farther), then pair key; a member's parent is the neighbour it reaches
-/// that comes before it, by the same, then round trip, then pair score. So where the writer reaches few
+/// that comes before it, by the same (a much slower link counting a hop more), then
+/// round trip, then pair score. So where the writer reaches few
 /// (behind NAT), those it reaches come first among the members as far from it, and the
 /// others take them as parents. What a member reaches we know of ourselves and our
 /// neighbours, as they said; of others, the graph is taken as right (if we're wrong,
@@ -127,11 +129,19 @@ fn rank(
     Some((d, !closer, topology::pair_key(member)))
 }
 
+/// A link to a possible parent this many round-trip buckets slower than the member's
+/// fastest to one (`rtt::bucket`; with doubling bounds, at least twice the round trip)
+/// counts as a hop more (`parent`): a member whose link to the writer is a slow circuit
+/// takes one as close to the writer as itself, if it has a fast link to one, rather than
+/// lag behind the others with every change.
+const SLOW_BY_BUCKETS: u8 = 2;
+
 /// `member`'s parent in the writer's tree (`rank`): the neighbour it reaches that comes
-/// before it, the closest to the writer first, then one that reaches closer, then the
-/// one it has the shortest round trip to, as it said (`round_trip(member, candidate)`,
-/// a bucket: `rtt::bucket`), then by pair score; None if none does (or it is the
-/// writer).
+/// before it, the closest to the writer first (a link `SLOW_BY_BUCKETS` slower than its
+/// fastest to one counting a hop more), then one that reaches closer, then the one it
+/// has the shortest round trip to, as it said (`round_trip(member, candidate)`, a
+/// bucket: `rtt::bucket`), then by pair score; None if none does (or it is the writer).
+/// Its round trips are what its neighbours know too, so they compute the same parent.
 fn parent<'g>(
     graph: &'g Graph,
     distance: &HashMap<String, u32>,
@@ -140,7 +150,7 @@ fn parent<'g>(
     member: &str,
 ) -> Option<&'g str> {
     let its_rank = rank(graph, distance, reached, member)?;
-    graph
+    let candidates: Vec<&str> = graph
         .get(member)
         .into_iter()
         .flatten()
@@ -149,15 +159,22 @@ fn parent<'g>(
             rank(graph, distance, reached, candidate).is_some_and(|r| r < its_rank)
                 && reached(member, candidate)
         })
-        .min_by_key(|candidate| {
-            let (d, far, _) = rank(graph, distance, reached, candidate).expect("ranked");
-            (
-                d,
-                far,
-                round_trip(member, candidate),
-                topology::pair_score(candidate, member),
-            )
-        })
+        .collect();
+    let fastest = candidates
+        .iter()
+        .map(|candidate| round_trip(member, candidate))
+        .min()?;
+    candidates.into_iter().min_by_key(|candidate| {
+        let (d, far, _) = rank(graph, distance, reached, candidate).expect("ranked");
+        let bucket = round_trip(member, candidate);
+        let slow = u32::from(bucket >= fastest.saturating_add(SLOW_BY_BUCKETS));
+        (
+            d + slow,
+            far,
+            bucket,
+            topology::pair_score(candidate, member),
+        )
+    })
 }
 
 /// `writer`'s whole tree, as far as `reached` knows whom each member reaches and
@@ -643,6 +660,45 @@ mod tests {
         }
     }
 
+    /// A member whose link to the writer is much slower than to another member as close
+    /// to the writer, one that comes before it, takes that one; one bucket slower, it
+    /// keeps the writer.
+    #[test]
+    fn a_slow_link_counts_a_hop_more() {
+        let mut graph = Graph::new();
+        for (a, b) in [("w", "a"), ("w", "x"), ("a", "x")] {
+            graph.entry(a.into()).or_default().insert(b.into());
+            graph.entry(b.into()).or_default().insert(a.into());
+        }
+        let distance: HashMap<String, u32> = [("w", 0), ("a", 1), ("x", 1)]
+            .into_iter()
+            .map(|(member, d)| (member.to_owned(), d))
+            .collect();
+        let reached = |_: &str, _: &str| true;
+        // Whichever of the two comes first (pair key) may be the other's parent.
+        let (first, second) = if topology::pair_key("a") < topology::pair_key("x") {
+            ("a", "x")
+        } else {
+            ("x", "a")
+        };
+        for (to_writer, expected) in [(6, first), (5, "w")] {
+            let round_trip = |by: &str, member: &str| match (by, member) {
+                (by, "w") if by == second => to_writer,
+                (by, m) if by == second && m == first => 4,
+                _ => rtt::UNKNOWN_BUCKET,
+            };
+            assert_eq!(
+                parent(&graph, &distance, &reached, &round_trip, second),
+                Some(expected),
+                "{to_writer}"
+            );
+            assert_eq!(
+                parent(&graph, &distance, &reached, &round_trip, first),
+                Some("w")
+            );
+        }
+    }
+
     /// Hops along parents from us; members without a parent, below one without, or
     /// not connected count as off the tree.
     #[test]