diff options
| -rw-r--r-- | docs/peers.md | 4 | ||||
| -rw-r--r-- | src/swarm/tree.rs | 90 |
2 files changed, 76 insertions, 18 deletions
diff --git a/docs/peers.md b/docs/peers.md index eefb0cc..29512a5 100644 --- a/docs/peers.md +++ b/docs/peers.md @@ -351,7 +351,9 @@ built on the graph the member list gives (as if every member reached every other on whom each member says it reaches. Members are ordered by their distance from the writer over that graph, then whether they reach a member a hop closer, then by 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 said it has the shortest +writer first (a link at least two round-trip buckets slower than its fastest to one +counting a hop more: a slow circuit to the writer is passed over for a fast link to a +member as close), then one that reaches closer, then the one it said it has the shortest round trip to, then by pair score. Coming before rules out cycles; taking only one it reaches routes around links that don't work: where a writer behind NAT reaches a single member, that one comes first among those as far from it, 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] |