A companion, a room server, or a sensor does not relay a trace with the firmware defaults (allowPacketForward in Mesh.cpp: client repeat is off, and allowed only on 433.000, 869.495, and 918.000 MHz; disable_fwd is on). A walk that turned at one of them never came home: the history held 36 companion traces and no reply from a real one. The route to such a node is the same. Only the walk changes: it turns at the last relay of the route, and the node is not in the spec. The route out of a walk that comes home is still the full route to the node, so the Device route row can offer it for DMs and admin. - relays_traces() in models states the rule. render_forced_spec takes relays=False, and forced_outbound reads the route back from a walk. - services/trace_plan holds the route choice that the trace screen made inline (radio route, outbound paths, best observed, last trace, direct), so the CLI uses the same one. - The trace screen names the relay where the walk turns, in a line under the route. With no relay to turn at, Trace is dim. A neighbour that does not relay gets "no relays" offered on the Device route row, with the packets heard directly as its proof. - The trace session turns a caller's spec (node page, Message paths) at the last relay, so the callers do not need the rule. A sender that is not a contact gets its type from its stored adverts. - The composer and Explore paths turn the walk at the last hop. - `meshterm trace -t NAME` with no --path walks the menu's route and says on stderr where it turns. With no known relay, it is a usage error. - The connection turns a device-routed trace at the last learned relay. The simulator now stops a walk at a node that does not relay, as the mesh does, and the tests that walked through Alice walk repeaters. The picker keeps one list with no mark, sorted as before (JP's choice). Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
1418 lines
69 KiB
Python
1418 lines
69 KiB
Python
# SPDX-License-Identifier: Apache-2.0
|
||
"""The observed mesh topology: a link graph made from each path that we ever received.
|
||
|
||
MeshCore never tells us the shape of the network directly. But almost everything that we
|
||
receive carries a part of it:
|
||
|
||
* A successful trace is proof that the packet went through each link in its path (out
|
||
and back, with an SNR reading at each hop).
|
||
* The firmware's ``out_path`` for each contact is a route made from received floods.
|
||
* When the packet logging of the companion is on, each overheard packet reports the relay
|
||
chain on which it arrived.
|
||
|
||
We can ask for a fourth part. A repeater on which we have admin rights reports its own
|
||
neighbour table (the nodes that it hears directly, and at what SNR) when we query it over
|
||
the mesh. This is a second point of view. It shows links, and whole nodes, from which our
|
||
device never received anything. This module combines these parts into one undirected
|
||
graph of evidence. It answers the questions that the trace path composer asks of the
|
||
graph:
|
||
|
||
* Which nodes are neighbours: :meth:`MeshTopology.next_hops`, the suggestion list when
|
||
the user composes a path hop by hop, with the strongest observed link first.
|
||
* How can we reach a target: :meth:`MeshTopology.scenarios`, ranked candidate outbound
|
||
paths (the learned route of the device, the direct path, and the best alternatives that
|
||
the evidence supports), ready for a trace or a probe.
|
||
|
||
Links are undirected on purpose. Radio paths work in both directions, and each reading is
|
||
evidence for the same physical link: an SNR measured at either end, or a route learned
|
||
from the opposite direction. Node identity is canonicalized against the contact list,
|
||
because the same node shows in different sources at different widths (a 1-byte trace hop
|
||
hash, a 12-hex key prefix in an observation, a full public key).
|
||
|
||
All of this module is pure data in, data out. The callers supply repository rows and
|
||
contacts, so a unit test can test the graph without a device or a database.
|
||
"""
|
||
|
||
from __future__ import annotations
|
||
|
||
import bisect
|
||
import heapq
|
||
import math
|
||
import statistics
|
||
from collections.abc import Sequence
|
||
from dataclasses import dataclass, field
|
||
from datetime import datetime
|
||
from itertools import chain, pairwise
|
||
|
||
from ..core.models import Contact, utcnow
|
||
from ..persistence.repository import NeighbourLink, PacketPath, TracedPath
|
||
|
||
#: The canonical id for our node in the graph (its 12-hex key prefix when known). By
|
||
#: construction, it is different from hop hashes, because it comes from the full public key.
|
||
|
||
#: The half-life of link evidence, in days. A reading that is one week old counts half as
|
||
#: much as a reading from now. Old links stay available as suggestions, but new
|
||
#: observations have the most effect on the ranking.
|
||
_EVIDENCE_HALF_LIFE_DAYS = 7.0
|
||
|
||
#: The SNR range that maps onto the link-quality factor. -15 dB (barely readable) gets the
|
||
#: floor, and +10 dB (excellent) gets the ceiling. This is the same span as the quality bar
|
||
#: on the trace screen.
|
||
_SNR_FLOOR_DB = -15.0
|
||
_SNR_CEIL_DB = 10.0
|
||
_QUALITY_MIN = 0.15
|
||
_QUALITY_MAX = 1.5
|
||
|
||
#: The cost for each hop, added when MeshTerm ranks candidate paths. Thus a longer path
|
||
#: that is only a little "stronger" does not win over a short path. Each extra hop is real
|
||
#: airtime and a real point of failure (and a trace goes through it two times: out and
|
||
#: back).
|
||
_HOP_PENALTY = 0.35
|
||
|
||
#: The limits for scenario generation: how many alternatives to offer, and how deep a
|
||
#: suggested route can go (the boomerang of the trace goes through each hop two times).
|
||
_MAX_SCENARIOS = 5
|
||
_MAX_SCENARIO_HOPS = 5
|
||
|
||
#: How close two outbound routes must score to be a tie, as a fraction of the higher score.
|
||
#: In a tie, the outbound path that the user put first wins (refer to
|
||
#: :meth:`MeshTopology.outbound_scenarios`). A strength is a noisy estimate, so a small
|
||
#: difference must not override the knowledge of the user.
|
||
_NEAR_TIE = 0.15
|
||
|
||
#: The strength that a route gets for a part that the user vouches for: a target that is a
|
||
#: hop of an outbound path. No link of the route is left to score, and the user trusts
|
||
#: each link of the path. Thus the route ranks above each route that the evidence scores.
|
||
_TRUSTED_STRENGTH = 1e6
|
||
|
||
#: The test that an ambiguous short hash must pass before it merges into one of the nodes
|
||
#: that it can name (refer to :meth:`MeshTopology._corroborated_owner`). The first value is
|
||
#: how many discriminating neighbours (neighbours that link to exactly one candidate) must
|
||
#: vote for the winner. The second value is how far in front of the second candidate the
|
||
#: winner must be. Both values leave a contested stub as it is. Two independent neighbours
|
||
#: that agree, with no neighbour against them, are evidence. One neighbour is a
|
||
#: coincidence. A close second means that the hash probably combines the traffic of two
|
||
#: nodes.
|
||
_MIN_CORROBORATION = 2
|
||
_CORROBORATION_MARGIN = 3
|
||
|
||
#: The full width of a canonical node id, in hex digits (6 bytes of key). An id of this
|
||
#: width is never under-specified. Thus it cannot merge into another id, and it cannot
|
||
#: extend one. For this reason, the prefix settle walks only the ids below this width
|
||
#: (refer to :meth:`MeshTopology.coalesce_prefixes`).
|
||
_CANONICAL_WIDTH = 12
|
||
|
||
_HEX_DIGITS = frozenset("0123456789abcdef")
|
||
|
||
#: Tells apart "cached as None" and "not cached" in the identity caches.
|
||
_MISS = object()
|
||
|
||
|
||
def is_path_hash(value: str) -> bool:
|
||
"""Whether ``value`` can be a path hash: hex that is not empty, a whole number of bytes.
|
||
|
||
This is the only test. All the code that must tell a hop id from a name or a graph
|
||
sentinel uses it. The length must be even, because a hash is bytes, never a half byte.
|
||
This rule also keeps out an endpoint marker of one character.
|
||
"""
|
||
return bool(value) and len(value) % 2 == 0 and all(c in _HEX_DIGITS for c in value)
|
||
|
||
|
||
def render_forced_spec(
|
||
hops: tuple[str, ...], target_hash: str, width_bytes: int, *, relays: bool = True
|
||
) -> str:
|
||
"""Render a symmetric forced-path spec: the outbound hops, the target, the mirror back.
|
||
|
||
The MeshCore trace protocol has no separate "return path" field. The full boomerang
|
||
(out to the target, and back to our node) is one path that the repeaters walk in
|
||
order. Thus the spec must give the return hops explicitly, not only the outbound
|
||
hops. This function renders the symmetric round trip: the return leg is the outbound
|
||
hops in reverse. This function adds them, so the caller does not have to give them. A
|
||
route that the user composed, and that comes back on a different path, is rendered
|
||
exactly as given by :func:`render_custom_spec` instead.
|
||
|
||
A target that does not relay (a companion, a room server, or a sensor, refer to
|
||
:func:`~meshterm.core.models.relays_traces`) cannot be the turn of a walk, because the
|
||
trace stops there. Then the walk turns at the last hop of the route, the relay that
|
||
hears the target, and the target is not in the spec. The hops are the same route to
|
||
the target in the two cases. Only the walk on the air is different.
|
||
|
||
Args:
|
||
hops: Intermediate repeaters, in order from our node outward, without the two
|
||
endpoints (empty means to trace the target directly, with no forced hops).
|
||
target_hash: The hex hash of the target (any width ≥ 1 byte).
|
||
width_bytes: The preferred path-hash width for each hop, in bytes (1, 2, 4, or
|
||
8). :func:`collapse_width` makes it smaller when the known hash of a hop is
|
||
narrower.
|
||
relays: Whether the target relays a trace. ``False`` turns the walk at the last
|
||
hop.
|
||
|
||
Returns:
|
||
A comma-separated hex spec, for example ``"3d,f2,3d"`` for one forced hop. It is
|
||
``""`` for a target that does not relay with no hops: there is no relay at which
|
||
the walk can turn.
|
||
"""
|
||
if relays:
|
||
turn, legs = target_hash, hops
|
||
elif hops:
|
||
turn, legs = hops[-1], hops[:-1]
|
||
else:
|
||
return ""
|
||
width = collapse_width(*legs, turn, ceiling=width_bytes)
|
||
outbound = [h[: width * 2] for h in (*legs, turn)]
|
||
outbound.extend(h[: width * 2] for h in reversed(legs))
|
||
return ",".join(outbound)
|
||
|
||
|
||
def forced_outbound(
|
||
tokens: Sequence[str], target_hash: str, *, relays: bool = True
|
||
) -> tuple[str, ...] | None:
|
||
"""The route to the target that a symmetric walk carries: the inverse of the forced spec.
|
||
|
||
:func:`render_forced_spec` makes a walk from a route. This function finds the route
|
||
again in a walk. The walk must be a palindrome of odd length, the shape of each walk
|
||
that the forced spec makes. For a target that relays, the middle hop must be the
|
||
target, and the route is the hops before it. For a target that does not relay, the
|
||
middle hop is the last relay of the route, and the route is the hops up to and with
|
||
it.
|
||
|
||
Args:
|
||
tokens: The hop hashes of the walk, in walk order, without our node.
|
||
target_hash: The hex hash of the target (any width). The middle hop of a walk to a
|
||
target that relays must be a prefix of it.
|
||
relays: Whether the target relays a trace.
|
||
|
||
Returns:
|
||
The hop hashes of the route, in order from our node outward (empty means that the
|
||
target is a neighbour). ``None`` when the walk is not a boomerang of this shape.
|
||
"""
|
||
hops = [t.lower() for t in tokens]
|
||
if not hops or len(hops) % 2 == 0 or hops != hops[::-1]:
|
||
return None
|
||
mid = len(hops) // 2
|
||
if not relays:
|
||
return tuple(hops[: mid + 1])
|
||
if not target_hash.lower().startswith(hops[mid]):
|
||
return None
|
||
return tuple(hops[:mid])
|
||
|
||
|
||
def render_custom_spec(hops: tuple[str, ...], width_bytes: int) -> str:
|
||
"""Render a path spec that the user composed (asymmetric), exactly as given.
|
||
|
||
This is the counterpart of :func:`render_forced_spec` for a route that the user gave
|
||
in full: out to the target, and back home on the path that the user chose. This
|
||
function adds nothing and mirrors nothing: the hops are the path. The trace protocol
|
||
walks any sequence that ends in radio range of our node. Only the shared width rules
|
||
apply.
|
||
|
||
Args:
|
||
hops: Each hop of the route in walk order, with the target, but without our
|
||
node at the two ends (the reply comes to our node from the last hop).
|
||
width_bytes: The preferred path-hash width for each hop, in bytes (1, 2, 4, or
|
||
8). :func:`collapse_width` makes it smaller when the known hash of a hop is
|
||
narrower.
|
||
|
||
Returns:
|
||
A comma-separated hex spec, for example ``"3d,f2,27"``, or ``""`` with no hops
|
||
(a custom route with zero hops has no meaning).
|
||
"""
|
||
if not hops:
|
||
return ""
|
||
width = collapse_width(*hops, ceiling=width_bytes)
|
||
return ",".join(h[: width * 2] for h in hops)
|
||
|
||
|
||
def collapse_width(*hashes: str, ceiling: int) -> int:
|
||
"""The widest per-hop hash width that a spec can use and that each given hash can supply.
|
||
|
||
Trace paths transmit all hops at one width: 1, 2, 4, or 8 bytes. Canonical node ids
|
||
are usually 6 bytes. But an unidentified hop can be as short as the width at which it
|
||
was traced before. Thus the spec must become as narrow as its narrowest hash.
|
||
|
||
Args:
|
||
*hashes: The hex hashes for one spec.
|
||
ceiling: The width that the caller prefers (in bytes, itself 1, 2, 4, or 8).
|
||
|
||
Returns:
|
||
The largest of 1, 2, 4, and 8 that is ≤ ``ceiling`` and ≤ the byte length of each
|
||
hash.
|
||
"""
|
||
limit = min([ceiling, *(len(h) // 2 for h in hashes if h)] or [ceiling])
|
||
return max(s for s in (1, 2, 4, 8) if s <= max(limit, 1))
|
||
|
||
|
||
@dataclass(slots=True)
|
||
class Link:
|
||
"""The evidence that MeshTerm collected for one undirected link between two nodes.
|
||
|
||
Attributes:
|
||
a: The canonical id of one endpoint (the lexically smaller one, so that the pair
|
||
is a key).
|
||
b: The canonical id of the other endpoint.
|
||
samples: How many independent readings went through this link, from any source.
|
||
snrs: The SNR readings (dB) for the link, in either direction.
|
||
last_seen: The time when the link was most recently observed.
|
||
sources: The evidence classes that observed it (``trace``, ``route``,
|
||
``packet``, ``neighbour``).
|
||
heard_at: The same SNR readings, divided by the endpoint that measured them. The
|
||
key is the id of the node that received. Its list holds what that node
|
||
measured on the packets from the other end. A radio link is not symmetric:
|
||
a repeater that we hear well can hear our node badly. ``snrs`` pools the two
|
||
directions for the ranking, and this field keeps them apart, so that a caller
|
||
can ask about one direction (refer to :meth:`MeshTopology.readings`).
|
||
"""
|
||
|
||
a: str
|
||
b: str
|
||
samples: int = 0
|
||
snrs: list[float] = field(default_factory=list)
|
||
last_seen: datetime | None = None
|
||
sources: set[str] = field(default_factory=set)
|
||
heard_at: dict[str, list[float]] = field(default_factory=dict)
|
||
|
||
@property
|
||
def median_snr(self) -> float | None:
|
||
"""The median SNR (dB) of the readings of the link, or ``None`` if there are none."""
|
||
return statistics.median(self.snrs) if self.snrs else None
|
||
|
||
def heard_by(self, node: str) -> list[float]:
|
||
"""The SNR readings that ``node`` measured on this link, from the other end.
|
||
|
||
Args:
|
||
node: The id of one endpoint of the link.
|
||
|
||
Returns:
|
||
The readings in dB, oldest first. The list is empty when ``node`` never
|
||
measured the other end, also when the other end measured ``node`` many times.
|
||
"""
|
||
return self.heard_at.get(node, [])
|
||
|
||
def strength(self, now: datetime | None = None, *, snrs: list[float] | None = None) -> float:
|
||
"""Score the observed reliability of the link, for the ranking (higher is stronger).
|
||
|
||
Three factors multiply:
|
||
|
||
* Evidence: the sample count on a log scale. Thus ten observations win over one,
|
||
but a thousand do not hide all the others.
|
||
* Recency: exponential decay with a
|
||
:data:`one-week half-life <_EVIDENCE_HALF_LIFE_DAYS>`.
|
||
* Quality: the median SNR, mapped linearly from -15 dB → :data:`_QUALITY_MIN` to
|
||
+10 dB → more than 1.0. Links with no SNR reading (for example, links known only
|
||
from a firmware route) get a neutral 1.0. They do not get a penalty for missing
|
||
data.
|
||
|
||
Args:
|
||
now: The reference time for recency (the default is the current time).
|
||
snrs: The readings for the quality factor, in place of the pooled readings of
|
||
the two directions. The graph gives the readings of one direction here for
|
||
the first link of a route out of our node (refer to
|
||
:meth:`MeshTopology.outward_strength`).
|
||
|
||
Returns:
|
||
The strength score of the link, ``> 0``.
|
||
"""
|
||
now = now or utcnow()
|
||
evidence = 1.0 + math.log2(1 + self.samples)
|
||
recency = 1.0
|
||
if self.last_seen is not None and getattr(self.last_seen, "tzinfo", None):
|
||
age_days = max(0.0, (now - self.last_seen).total_seconds() / 86400.0)
|
||
recency = 0.5 ** (age_days / _EVIDENCE_HALF_LIFE_DAYS)
|
||
snr = self.median_snr if snrs is None else (statistics.median(snrs) if snrs else None)
|
||
quality = 1.0
|
||
if snr is not None:
|
||
span = _SNR_CEIL_DB - _SNR_FLOOR_DB
|
||
frac = (snr - _SNR_FLOOR_DB) / span
|
||
reach = _QUALITY_MIN + frac * (_QUALITY_MAX - _QUALITY_MIN)
|
||
quality = min(_QUALITY_MAX, max(_QUALITY_MIN, reach))
|
||
return evidence * recency * quality
|
||
|
||
|
||
@dataclass(slots=True)
|
||
class HopSuggestion:
|
||
"""One suggested next hop, when the user composes a path.
|
||
|
||
Attributes:
|
||
node: The canonical id of the suggested node.
|
||
link: The evidence for the link from the current end of the path to ``node``.
|
||
strength: The strength of the link, calculated before (the sort key). Thus the UI
|
||
can render a stable ranking, and does not calculate the score again at each
|
||
paint.
|
||
"""
|
||
|
||
node: str
|
||
link: Link
|
||
strength: float
|
||
|
||
|
||
@dataclass(slots=True)
|
||
class PathScenario:
|
||
"""One candidate outbound route to a target, ready for a trace.
|
||
|
||
A scenario stores only the outbound leg. The return is always the symmetric mirror,
|
||
so there is nothing to choose for it. But :meth:`spec` renders the full boomerang,
|
||
because the trace protocol has no separate field for the return path: the full route
|
||
out and back is one spec that the repeaters walk in order.
|
||
|
||
Attributes:
|
||
label: A short description for the user, of where the route came from.
|
||
hops: The canonical ids of the intermediate repeaters, in order from our node
|
||
outward, without the two endpoints (empty means to trace the target directly).
|
||
source: The evidence class that proposed the route (``device``, ``outbound``,
|
||
``direct``, ``observed``).
|
||
score: The ranking score (higher first): the strength of the weakest link of the
|
||
path, with a penalty for the hop count. Direct and device scenarios with no
|
||
observed evidence score 0.
|
||
weakest_snr: The lowest median SNR (dB) of a link on the route, when known. This
|
||
is the bottleneck that the trace will probably measure.
|
||
samples: The total of the readings on the links of the route (an approximate
|
||
measure of confidence).
|
||
rank: For an ``outbound`` scenario, the place of its outbound path in the list of
|
||
the user, from 1. It is 0 for each other source.
|
||
"""
|
||
|
||
label: str
|
||
hops: tuple[str, ...]
|
||
source: str
|
||
score: float
|
||
weakest_snr: float | None = None
|
||
samples: int = 0
|
||
rank: int = 0
|
||
|
||
def spec(self, target_hash: str, width_bytes: int, *, relays: bool = True) -> str:
|
||
"""Render the scenario as a forced-path spec, with the return leg.
|
||
|
||
Refer to :func:`render_forced_spec` for the rules of the width, the return leg,
|
||
and a target that does not relay.
|
||
|
||
Args:
|
||
target_hash: The hex hash of the target (any width ≥ 1 byte).
|
||
width_bytes: The preferred path-hash width for each hop, in bytes (1, 2, 4,
|
||
or 8).
|
||
relays: Whether the target relays a trace.
|
||
|
||
Returns:
|
||
A comma-separated hex spec, for example ``"3d,f2,3d"``. It is ``""`` when the
|
||
walk has no relay at which to turn.
|
||
"""
|
||
return render_forced_spec(self.hops, target_hash, width_bytes, relays=relays)
|
||
|
||
|
||
class MeshTopology:
|
||
"""The evidence graph of the observed mesh links, which answers queries for route suggestions.
|
||
|
||
Build one with :func:`build_topology`. Instances are snapshots that cost little, and
|
||
that are immutable in intent. When new evidence arrives, build a new one, and do not
|
||
change the old one.
|
||
"""
|
||
|
||
def __init__(self, self_id: str, contacts: list[Contact]) -> None:
|
||
"""Make an empty graph, with our node at its root.
|
||
|
||
Args:
|
||
self_id: The canonical id of our node (12-hex key prefix, in lower case).
|
||
contacts: The known contacts. MeshTerm uses them to canonicalize hop hashes of
|
||
any width to stable node ids, and to name nodes for display.
|
||
"""
|
||
self.self_id = self_id.lower().removeprefix("0x")[:12]
|
||
self._links: dict[tuple[str, str], Link] = {}
|
||
self._now = utcnow()
|
||
# The contact index for canonicalization: full public keys in lower case (or the
|
||
# stored prefix, if there is no key), mapped to the 12-hex canonical id and the
|
||
# display name.
|
||
self._known: list[tuple[str, str, str]] = [] # (full_key, canonical, name)
|
||
for c in contacts:
|
||
key = (c.public_key or c.key_prefix or "").lower().removeprefix("0x")
|
||
if key:
|
||
self._known.append((key, key[:12], c.name))
|
||
# ``_known`` never changes after construction. A build sends the same few dozen
|
||
# distinct hashes through canonical() thousands of times (each hop of each stored
|
||
# packet path). Thus both identity lookups cache their results for each instance.
|
||
self._canonical_memo: dict[str, str | None] = {}
|
||
self._name_memo: dict[str, str | None] = {}
|
||
# Route search results for each (target, k), valid for one shape of the graph.
|
||
# Each change to a link increments the version, so a cached run of Yen's algorithm
|
||
# can never stay longer than the evidence that it ranked. Callers ask for the same
|
||
# target two times when a screen opens (suggested() and scenarios() both run the
|
||
# search). The search is the most costly part of an open that uses the topology.
|
||
self._graph_version = 0
|
||
self._routes_memo: dict[tuple, list[tuple[str, ...]]] = {}
|
||
|
||
# --- identity ----------------------------------------------------------------
|
||
|
||
def canonical(self, hop: str | None) -> str | None:
|
||
"""Map a hop hash of any width onto a stable node id.
|
||
|
||
Trace hops arrive at the path-hash width of the command (1-8 bytes), observation
|
||
ids (key prefixes) at 12 hex, and routes at the width of the region. All of them
|
||
name the same nodes. A hash that is a prefix of exactly one known contact takes
|
||
the 12-hex id of that contact. An ambiguous or unknown hash stays as it is. Thus
|
||
MeshTerm keeps the evidence about nodes that it cannot identify (under the short
|
||
id), and does not guess them onto the wrong node.
|
||
|
||
Args:
|
||
hop: The raw hex hash (any case, optional ``0x``), or ``None`` or empty.
|
||
|
||
Returns:
|
||
The canonical id, or ``None`` for a missing or non-hex hop (non-hex includes
|
||
old simulator artefacts such as ``hop0``).
|
||
"""
|
||
if not hop:
|
||
return None
|
||
cached = self._canonical_memo.get(hop, _MISS)
|
||
if cached is not _MISS:
|
||
return cached
|
||
needle = hop.lower().removeprefix("0x")
|
||
if not is_path_hash(needle):
|
||
result: str | None = None
|
||
else:
|
||
matches = {
|
||
canonical
|
||
for key, canonical, _name in self._known
|
||
if key.startswith(needle) or needle.startswith(key[:12])
|
||
}
|
||
result = next(iter(matches)) if len(matches) == 1 else needle[:12]
|
||
self._canonical_memo[hop] = result
|
||
return result
|
||
|
||
def display_name(self, node: str) -> str | None:
|
||
"""The contact name for a canonical id, or ``None`` when it is not known."""
|
||
cached = self._name_memo.get(node, _MISS)
|
||
if cached is not _MISS:
|
||
return cached
|
||
result = next((name for _key, canonical, name in self._known if canonical == node), None)
|
||
self._name_memo[node] = result
|
||
return result
|
||
|
||
# --- construction ------------------------------------------------------------
|
||
|
||
def add_walk(
|
||
self,
|
||
nodes: list[str | None],
|
||
*,
|
||
snrs: list[float | None] | None = None,
|
||
when: datetime | None = None,
|
||
source: str,
|
||
) -> None:
|
||
"""Add one walked node sequence to the graph, as a set of link readings.
|
||
|
||
Each pair of consecutive nodes becomes one reading on their undirected link.
|
||
``nodes`` holds canonical ids. ``None`` entries (hops that cannot be resolved)
|
||
break the chain, so that no false adjacency is invented across them. The method
|
||
skips self-loops (a hash repeated two times in sequence, for example a
|
||
there-and-back path that the user forced).
|
||
|
||
Args:
|
||
nodes: The walked sequence, with the endpoints, in order.
|
||
snrs: Optional SNR readings for each link, aligned with the links
|
||
(``snrs[i]`` is for the ``nodes[i] → nodes[i+1]`` link, measured at
|
||
arrival). Thus ``nodes[i+1]`` measured it, and the reading goes into the
|
||
direction of the link that ends at that node (refer to
|
||
:attr:`Link.heard_at`). A caller with a reading that the *first* node of
|
||
a pair measured must give the pair in the reverse order.
|
||
when: When the walk was observed (this sets the recency of each touched link).
|
||
source: The evidence class tag (``trace``, ``route``, ``packet``,
|
||
``neighbour``).
|
||
"""
|
||
self._graph_version += 1 # link evidence changed, so cached route searches expire
|
||
for i in range(len(nodes) - 1):
|
||
a, b = nodes[i], nodes[i + 1]
|
||
if not a or not b or a == b:
|
||
continue
|
||
key = (a, b) if a < b else (b, a)
|
||
link = self._links.get(key)
|
||
if link is None:
|
||
link = self._links[key] = Link(a=key[0], b=key[1])
|
||
link.samples += 1
|
||
link.sources.add(source)
|
||
snr = snrs[i] if snrs and i < len(snrs) else None
|
||
if snr is not None:
|
||
link.snrs.append(snr)
|
||
link.heard_at.setdefault(b, []).append(snr)
|
||
if when is not None and (link.last_seen is None or when > link.last_seen):
|
||
link.last_seen = when
|
||
|
||
def coalesce_prefixes(self) -> None:
|
||
"""Merge each under-specified node id into the one longer id that it can be.
|
||
|
||
The same physical node comes into the graph at different hash widths: a trace hop
|
||
logged at 1 byte (``27``), a packet relay at 3 bytes (``27d439``), and a full
|
||
6-byte contact id (``27d4396a2967``). :meth:`canonical` widens a hop to a contact
|
||
id only when the prefix names exactly one contact. But the mesh has two nodes whose
|
||
keys both start with ``27`` (``27d4…`` and ``27e4…``). Thus the bare ``27`` hop
|
||
stays short, and stands next to the wide ``27d4396a2967`` as a false second node.
|
||
If nothing corrects this, the node shows two times on each surface that the graph
|
||
supplies. The mesh walk draws it two times, the route graph draws two lanes to one
|
||
repeater, and the scenario ranker offers a redundant weaker route through the stub.
|
||
|
||
This method closes the gap with the evidence that the graph has, not with the full
|
||
contact list. It uses two passes, in the order of decreasing confidence:
|
||
|
||
1. **By prefix only** (:meth:`_next_prefix_merge`). A short id merges into a longer
|
||
node id in the graph when it is a strict prefix of **exactly one** of them. The
|
||
method follows a prefix chain (``65`` → ``6532`` → ``6532eb``) to its longest
|
||
end. Nothing is inferred: the short id can only mean that one node.
|
||
2. **By corroboration** (:meth:`_next_corroborated_merge`). A short id that is the
|
||
start of two different longer nodes (``c5`` → ``c5bc…`` and ``c5ba…``) is
|
||
ambiguous by prefix. But the graph usually knows which node it is. The stub
|
||
carries the links of the node that it really was, so its neighbourhood names
|
||
the owner. Neighbours that can tell the candidates apart vote, and a decisive
|
||
result merges the stub into the winner. Refer to that method for the test that a
|
||
vote must pass.
|
||
|
||
The passes alternate. The graph changes with each merge, so an ambiguity can
|
||
resolve itself after a neighbouring stub merges. The certain pass always runs again
|
||
before the inference pass gets another turn.
|
||
|
||
A short id that is the start of no longer node (a node that we only heard with a
|
||
narrow hash) keeps its width. It is one node, with only a short name. A short id
|
||
whose vote stays contested also keeps its width. A merge moves the links of the
|
||
short id into the links of the wide id. It adds the samples, combines the SNR
|
||
readings and the sources, and keeps the newest observation. Thus the wide node gets
|
||
each reading that the stub collected. Idempotent: a second call finds nothing more
|
||
to merge.
|
||
|
||
:func:`build_topology` calls this method one time at its end, so each consumer
|
||
sees each node one time. It is safe for our node (its 12-hex id is never a
|
||
candidate as a short prefix).
|
||
|
||
**The method builds one neighbour table, and then keeps it through the merges.** It
|
||
does not walk the full graph again at each turn. Before, three separate passes over
|
||
each link ran for each merge. One found the node set, one built the neighbour table
|
||
that the corroboration vote reads, and one found the links that name the id to
|
||
merge. On the real mesh that was measured, that was approximately 1150 links walked
|
||
three times, approximately eighty times: the largest remaining cost when the mesh
|
||
walk opened. The same table answers all three questions. The effect of a merge on
|
||
the table is known exactly where the merge occurs (refer to :meth:`_merge_node`).
|
||
Thus the table is the live node set and adjacency of the graph for all the settle.
|
||
Its keys are the node ids: a node is in the table exactly while it holds a link.
|
||
"""
|
||
adjacency = self._adjacency()
|
||
while True:
|
||
# Only an under-specified id can merge, and a full-width id extends nothing.
|
||
# Thus both passes walk only the short ids, the shortest first (a 65 → 6532 →
|
||
# 6532eb chain collapses from the end inward over the next turns). A graph of
|
||
# nodes that all have full names settles, and neither pass examines a link.
|
||
#
|
||
# Ties break lexicographically, and this makes a settle repeatable. An order by
|
||
# length only leaves ids of equal width in the iteration order of the node set,
|
||
# and CPython randomizes string hashing in each process. Thus two runs over the
|
||
# same evidence could do the merges in different orders. Where a merge changes
|
||
# what a later merge sees, the two runs could make graphs that are different.
|
||
shorts = sorted(
|
||
(node for node in adjacency if len(node) < _CANONICAL_WIDTH),
|
||
key=lambda node: (len(node), node),
|
||
)
|
||
if not shorts:
|
||
return
|
||
ordered = sorted(adjacency)
|
||
merge = self._next_prefix_merge(shorts, ordered) or self._next_corroborated_merge(
|
||
shorts, ordered, adjacency
|
||
)
|
||
if merge is None:
|
||
return
|
||
self._merge_node(*merge, adjacency=adjacency)
|
||
|
||
def _node_ids(self) -> set[str]:
|
||
"""Each node id that is now an endpoint of a link."""
|
||
return set(chain.from_iterable(self._links))
|
||
|
||
def _next_prefix_merge(self, shorts: list[str], ordered: list[str]) -> tuple[str, str] | None:
|
||
"""The next ``(short, long)`` pair to merge, or ``None`` when no pair remains.
|
||
|
||
A short id (shorter than the full canonical width of 6 bytes) merges when the
|
||
longer ids in the graph that extend it are all on one prefix chain. That is, the
|
||
longest of them starts with each of the others. Thus the short id can only mean
|
||
that one node.
|
||
|
||
Args:
|
||
shorts: The under-specified node ids, the shortest first. Thus a ``65`` →
|
||
``6532`` → ``6532eb`` chain collapses from the end inward over the next
|
||
calls.
|
||
ordered: Each node id, sorted lexicographically (refer to :meth:`_extensions`).
|
||
"""
|
||
for short in shorts:
|
||
exts = self._extensions(short, ordered)
|
||
if not exts:
|
||
continue
|
||
longest = max(exts, key=len)
|
||
if all(longest.startswith(ext) for ext in exts): # one node, not two
|
||
return short, longest
|
||
return None
|
||
|
||
@staticmethod
|
||
def _extensions(short: str, ordered: list[str]) -> list[str]:
|
||
"""Each node id in ``ordered`` that strictly extends the under-specified ``short``.
|
||
|
||
Empty for a full-width canonical id (12 hex is never under-specified), and for a
|
||
short id that nothing in the graph extends.
|
||
|
||
``ordered`` must be the node ids sorted lexicographically. This makes the method
|
||
fast: all the ids that have the same prefix sort into one contiguous run. Thus the
|
||
extensions are a slice that a binary search finds, not a scan of the full graph.
|
||
This is important, because the caller asks this question one time for each node,
|
||
and the caller of that caller starts the full pass again after each merge. On a
|
||
mesh with approximately 1100 links and a few hundred merges to settle, a linear
|
||
scan here made approximately 24 million ``len`` calls, and the mesh walk took
|
||
sixteen seconds to open.
|
||
"""
|
||
if len(short) >= _CANONICAL_WIDTH:
|
||
return []
|
||
out: list[str] = []
|
||
width = len(short)
|
||
for i in range(bisect.bisect_left(ordered, short), len(ordered)):
|
||
other = ordered[i]
|
||
if not other.startswith(short):
|
||
break # after the run: no later id can have the prefix
|
||
if len(other) > width:
|
||
out.append(other)
|
||
return out
|
||
|
||
def _next_corroborated_merge(
|
||
self, shorts: list[str], ordered: list[str], adjacency: dict[str, set[str]]
|
||
) -> tuple[str, str] | None:
|
||
"""The next ambiguous stub that the neighbourhood evidence resolves, or ``None``.
|
||
|
||
:meth:`_next_prefix_merge` merges only what the hash alone settles. This method
|
||
answers the case that the other method leaves: a short id such as ``bf`` that is
|
||
the start of two real nodes (``bf61f2…`` and ``bfbeef…``). By prefix, that is a
|
||
coin toss. But the stub is not an empty label. It carries the links of the node
|
||
that it really was, so its neighbours name its owner. Each neighbour that can tell
|
||
the candidates apart is a vote: a neighbour of the stub that links to exactly one
|
||
candidate. Both candidates share the other neighbours, and two repeaters in the
|
||
same city have many of them. These neighbours do not vote, so that the local
|
||
density does not hide the signal.
|
||
|
||
The test is high on purpose, because a wrong merge does what this full routine
|
||
exists to prevent: it gives the evidence of one node to another node. The winner
|
||
must get at least :data:`_MIN_CORROBORATION` discriminating votes, and must be
|
||
:data:`_CORROBORATION_MARGIN`× in front of the second candidate. Thus a stub that
|
||
is really contested stays exactly where it was: by itself, with a short name, but
|
||
with no false claim. The neighbours of such a stub point to both candidates, that
|
||
is, the stub really is the traffic of two nodes combined under one hash.
|
||
|
||
The shortest ids come first, the same as in :meth:`_next_prefix_merge`. Only the
|
||
maximal candidates compete. The inner links of a chain (``f0`` → ``f062eb`` →
|
||
``f062eb…``) are the same node, so they never split their own vote.
|
||
|
||
Args:
|
||
shorts: The under-specified node ids, the shortest first.
|
||
ordered: Each node id, sorted lexicographically (refer to :meth:`_extensions`).
|
||
adjacency: The live neighbour table of the graph, which the settle loop that
|
||
calls this method carries (refer to :meth:`coalesce_prefixes`).
|
||
"""
|
||
for short in shorts:
|
||
exts = self._extensions(short, ordered)
|
||
candidates = [
|
||
ext
|
||
for ext in exts
|
||
if not any(other != ext and other.startswith(ext) for other in exts)
|
||
]
|
||
if len(candidates) < 2: # the certain pass settled (or ignored) this id
|
||
continue
|
||
owner = self._corroborated_owner(short, candidates, adjacency)
|
||
if owner is not None:
|
||
return short, owner
|
||
return None
|
||
|
||
def _adjacency(self) -> dict[str, set[str]]:
|
||
"""The graph as neighbour sets, for questions that are difficult to ask of link pairs."""
|
||
adjacency: dict[str, set[str]] = {}
|
||
for a, b in self._links:
|
||
adjacency.setdefault(a, set()).add(b)
|
||
adjacency.setdefault(b, set()).add(a)
|
||
return adjacency
|
||
|
||
@staticmethod
|
||
def _corroborated_owner(
|
||
short: str, candidates: list[str], adjacency: dict[str, set[str]]
|
||
) -> str | None:
|
||
"""The candidate that the discriminating neighbours of the stub elect, if any.
|
||
|
||
A neighbour votes only when it separates the candidates: it is a neighbour of
|
||
exactly one candidate. Thus shared neighbours count for nothing, and the ``short``
|
||
and candidate ids never vote for their own case. ``None`` means that there is no
|
||
decisive winner: too few votes, or a second candidate so close that the stub may
|
||
be the traffic of both nodes under one hash.
|
||
|
||
Args:
|
||
short: The under-specified id to resolve.
|
||
candidates: The distinct node ids that it can name (two or more).
|
||
adjacency: The neighbour sets of the full graph (refer to :meth:`_adjacency`).
|
||
|
||
Returns:
|
||
The elected candidate, or ``None`` to leave the stub as it is.
|
||
"""
|
||
field = set(candidates) | {short}
|
||
votes = dict.fromkeys(candidates, 0)
|
||
for neighbour in adjacency.get(short, ()) - field:
|
||
electors = [c for c in candidates if neighbour in adjacency.get(c, ())]
|
||
if len(electors) == 1:
|
||
votes[electors[0]] += 1
|
||
ranked = sorted(votes.items(), key=lambda pair: (-pair[1], pair[0]))
|
||
(winner, top), (_runner, second) = ranked[0], ranked[1]
|
||
if top < _MIN_CORROBORATION or top < _CORROBORATION_MARGIN * second:
|
||
return None
|
||
return winner
|
||
|
||
def _merge_node(
|
||
self, src: str, dst: str, *, adjacency: dict[str, set[str]] | None = None
|
||
) -> None:
|
||
"""Relabel each link of ``src`` to ``dst``, and combine the links that they share.
|
||
|
||
The method finds the links through the neighbour table, not with a scan of the
|
||
graph. A link is addressed by its two endpoints, so the neighbours of ``src`` name
|
||
its links directly. That is a few dict lookups, not a walk over each link in the
|
||
mesh, for each of the many merges of a settle.
|
||
|
||
Args:
|
||
src: The under-specified id to merge away.
|
||
dst: The node id that it can only mean.
|
||
adjacency: The live neighbour table of the caller, **updated in place** to
|
||
agree with the changed graph. ``src`` leaves it, and ``dst`` gets the
|
||
neighbours of ``src``. In one special case, ``dst`` itself also leaves:
|
||
when each link of ``src`` went to ``dst``. Each of these links collapses to
|
||
a self-loop and is discarded, so ``dst`` goes with them, unless it had a
|
||
link of its own. No other node can lose its last link here: a relabelled
|
||
link keeps its far end. Omit this argument for a single merge, and the
|
||
method builds the table here (and discards it after).
|
||
"""
|
||
if adjacency is None:
|
||
adjacency = self._adjacency()
|
||
self._graph_version += 1 # the graph changes shape, so cached searches expire
|
||
for far in adjacency.pop(src, ()):
|
||
link = self._links.pop((src, far) if src < far else (far, src), None)
|
||
if link is None:
|
||
continue
|
||
adjacency[far].discard(src)
|
||
if far == dst: # a src→dst link (src is a prefix of dst) becomes a self-loop
|
||
continue
|
||
new_key = (dst, far) if dst < far else (far, dst)
|
||
# The readings that src measured become the readings of dst, the node that
|
||
# src is. The readings that far measured keep their key.
|
||
heard = {(dst if node == src else node): snrs for node, snrs in link.heard_at.items()}
|
||
existing = self._links.get(new_key)
|
||
if existing is None:
|
||
self._links[new_key] = Link(
|
||
a=new_key[0],
|
||
b=new_key[1],
|
||
samples=link.samples,
|
||
snrs=list(link.snrs),
|
||
last_seen=link.last_seen,
|
||
sources=set(link.sources),
|
||
heard_at={node: list(snrs) for node, snrs in heard.items()},
|
||
)
|
||
else:
|
||
existing.samples += link.samples
|
||
existing.snrs.extend(link.snrs)
|
||
existing.sources |= link.sources
|
||
for node, snrs in heard.items():
|
||
existing.heard_at.setdefault(node, []).extend(snrs)
|
||
if link.last_seen is not None and (
|
||
existing.last_seen is None or link.last_seen > existing.last_seen
|
||
):
|
||
existing.last_seen = link.last_seen
|
||
adjacency.setdefault(dst, set()).add(far)
|
||
adjacency[far].add(dst)
|
||
if not adjacency.get(dst, ()):
|
||
adjacency.pop(dst, None) # all its links went to the stub that is now merged
|
||
|
||
# --- queries -----------------------------------------------------------------
|
||
|
||
@property
|
||
def link_count(self) -> int:
|
||
"""How many distinct links the graph has evidence for."""
|
||
return len(self._links)
|
||
|
||
def links(self) -> list[Link]:
|
||
"""Each link that the graph has evidence for (in no specific order).
|
||
|
||
This is the view of the full graph that the Mesh walk draws. For path queries,
|
||
use :meth:`next_hops` or :meth:`scenarios` instead, because these rank and filter.
|
||
"""
|
||
return list(self._links.values())
|
||
|
||
def link(self, a: str, b: str) -> Link | None:
|
||
"""The evidence for the undirected link between ``a`` and ``b``, if there is any."""
|
||
return self._links.get((a, b) if a < b else (b, a))
|
||
|
||
def outward_strength(self, a: str, b: str, link: Link) -> float:
|
||
"""The strength of ``link`` for a packet that goes from ``a`` to ``b``.
|
||
|
||
A link that leaves our node is scored from what the far end measured from our node
|
||
(the first hop of a trace reports it), when such readings exist. The pooled readings
|
||
are mostly what our node *heard*: each received packet adds one, and only a trace
|
||
adds a reading of the other direction. A repeater that our node hears well can
|
||
hear our node badly, and a route out of our node depends on the second fact. Each
|
||
other link keeps its pooled strength: the graph knows both directions of those
|
||
links only from the same few traces.
|
||
|
||
Args:
|
||
a: The canonical id of the node that transmits.
|
||
b: The canonical id of the node that receives.
|
||
link: The link between them.
|
||
|
||
Returns:
|
||
The strength score of the link, in that direction.
|
||
"""
|
||
if a == self.self_id:
|
||
outward = link.heard_by(b)
|
||
if outward:
|
||
return link.strength(self._now, snrs=outward)
|
||
return link.strength(self._now)
|
||
|
||
def readings(self, sender: str, receiver: str) -> list[float]:
|
||
"""The SNR readings of one direction of a link: what ``receiver`` measured from ``sender``.
|
||
|
||
The ranking pools the two directions of a link (refer to :class:`Link`). This
|
||
method keeps them apart. For the link from our node to a repeater, ``readings(us,
|
||
repeater)`` is how well the repeater hears our node. Only a trace gives these
|
||
readings, because the first hop of a trace reports the SNR at which it received
|
||
our packet. ``readings(repeater, us)`` is how well our node hears the repeater:
|
||
each packet that the repeater relayed to us, and the last hop of each trace that
|
||
came home through it.
|
||
|
||
Args:
|
||
sender: The canonical id of the node that transmitted.
|
||
receiver: The canonical id of the node that measured.
|
||
|
||
Returns:
|
||
The readings in dB. The list is empty when there is no link, or when no
|
||
reading in that direction exists.
|
||
"""
|
||
link = self.link(sender, receiver)
|
||
return list(link.heard_by(receiver)) if link is not None else []
|
||
|
||
def next_hops(self, tail: str, *, exclude: frozenset[str] = frozenset()) -> list[HopSuggestion]:
|
||
"""Suggest the nodes that ``tail`` can reach, with the strongest observed link first.
|
||
|
||
This is the step-by-step feed of the composer. From the current end of the path,
|
||
it gives each node that ``tail`` can hear, as the evidence says (links are
|
||
bidirectional, so a path observed in either direction is accepted). It does not
|
||
give the nodes that the path already uses.
|
||
|
||
Args:
|
||
tail: The canonical id at which the path ends now (our own id at the start).
|
||
exclude: The canonical ids to omit (the nodes already in the path). A node
|
||
used again is never useful, and repeaters discard duplicate hops in any
|
||
case.
|
||
|
||
Returns:
|
||
Suggestions sorted by decreasing link strength.
|
||
"""
|
||
out: list[HopSuggestion] = []
|
||
for (a, b), link in self._links.items():
|
||
other = b if a == tail else a if b == tail else None
|
||
if other is None or other in exclude:
|
||
continue
|
||
strength = self.outward_strength(tail, other, link)
|
||
out.append(HopSuggestion(node=other, link=link, strength=strength))
|
||
out.sort(key=lambda s: (-s.strength, s.node))
|
||
return out
|
||
|
||
def scenarios(
|
||
self,
|
||
target: str,
|
||
*,
|
||
device_route: tuple[str, ...] | None = None,
|
||
outbound: Sequence[tuple[str, ...]] = (),
|
||
silent_before: datetime | None = None,
|
||
) -> list[PathScenario]:
|
||
"""Rank the candidate outbound routes to ``target``.
|
||
|
||
Four families, without duplicates, in this order of priority:
|
||
|
||
1. **device**: the route that the firmware itself learned from received floods
|
||
(the route that an auto-routed trace walks), when the caller supplies one.
|
||
2. **outbound**: one route through each outbound path of the user (refer to
|
||
:meth:`outbound_scenarios`). When the user has outbound paths and the device
|
||
route does not start with one of them, this family comes first. The firmware
|
||
learns its route from floods that our node *received*, and a radio link is not
|
||
symmetric. The user knows the way out, and the received floods do not.
|
||
3. **direct**: no repeaters at all. MeshTerm always offers it as the baseline.
|
||
4. **observed**: the strongest simple paths through the evidence graph (the score
|
||
is the weakest link, with a penalty for each hop). This family gives the paths
|
||
that the device never learned, but that the data supports.
|
||
|
||
Each scenario stores only an outbound leg. The return is always those hops in
|
||
mirror order, so there is nothing to rank there. But :meth:`PathScenario.spec`
|
||
renders the full boomerang. The trace implicitly goes through the intermediate
|
||
links two times.
|
||
|
||
Args:
|
||
target: The canonical id of the target.
|
||
device_route: The learned route of the firmware (canonical intermediate
|
||
hops), if the contact has one.
|
||
outbound: The outbound paths of the user, in order, as canonical ids.
|
||
silent_before: Skip an outbound path whose first hop was last heard before
|
||
this time (refer to :meth:`outbound_scenarios`).
|
||
|
||
Returns:
|
||
Scenarios ranked with the best evidence first. The device route, when there
|
||
is one, is first, whatever its score, because it is what "auto" does. The one
|
||
exception is a device route that does not start with an outbound path of the
|
||
user: then the outbound routes are first.
|
||
"""
|
||
first = self.outbound_scenarios(target, outbound, silent_before=silent_before)
|
||
seen: set[tuple[str, ...]] = {s.hops for s in first}
|
||
out: list[PathScenario] = []
|
||
|
||
def add(label: str, hops: tuple[str, ...], source: str) -> None:
|
||
if hops in seen or len(hops) > _MAX_SCENARIO_HOPS or target in hops:
|
||
return
|
||
seen.add(hops)
|
||
score, weakest, samples = self._score_route(hops, target)
|
||
out.append(
|
||
PathScenario(
|
||
label=label,
|
||
hops=hops,
|
||
source=source,
|
||
score=score,
|
||
weakest_snr=weakest,
|
||
samples=samples,
|
||
)
|
||
)
|
||
|
||
device: list[PathScenario] = []
|
||
if device_route is not None:
|
||
if device_route in seen: # the device learned one of the outbound routes
|
||
device = [s for s in first if s.hops == device_route]
|
||
first = [s for s in first if s.hops != device_route]
|
||
else:
|
||
add("device route", device_route, "device")
|
||
device = [s for s in out if s.source == "device"]
|
||
out = [s for s in out if s.source != "device"]
|
||
add("direct", (), "direct")
|
||
for hops in self._best_routes(target, k=_MAX_SCENARIOS):
|
||
add("observed path", hops, "observed")
|
||
|
||
# Rank the observed evidence, but keep the device route pinned at the top. It is
|
||
# the reference point for the comparison of each alternative. The outbound routes
|
||
# go in front of a device route that starts on a path the user did not name.
|
||
rest = sorted(out, key=lambda s: (-s.score, len(s.hops)))
|
||
starts_outbound = bool(device) and any(
|
||
device[0].hops[: len(path)] == path for path in outbound
|
||
)
|
||
head = device + first if (starts_outbound or not first) else first + device
|
||
return (head + rest)[: max(_MAX_SCENARIOS, len(head))]
|
||
|
||
def outbound_scenarios(
|
||
self,
|
||
target: str,
|
||
outbound: Sequence[tuple[str, ...]],
|
||
*,
|
||
silent_before: datetime | None = None,
|
||
) -> list[PathScenario]:
|
||
"""One route to ``target`` through each outbound path of the user, the best first.
|
||
|
||
The route through an outbound path is the path, then the cheapest continuation
|
||
from its last hop to the target (a node of the path is never used again). When
|
||
the target is a hop of the path, the route is the part of the path before it.
|
||
|
||
The score is the weakest link of the continuation only, with the penalty for each
|
||
hop of the full route. The user vouches for the links of the outbound path, and
|
||
the evidence for these links is mostly what our node *heard*, which says little
|
||
about how well a repeater hears our node. A route that ends inside its path has no
|
||
link to score, and gets :data:`_TRUSTED_STRENGTH`.
|
||
|
||
The best score is first. When two scores are within :data:`_NEAR_TIE`, the path
|
||
that the user put first wins. A path whose first hop was last heard before
|
||
``silent_before`` is skipped: that repeater is probably off, or out of reach from
|
||
here. A first hop with no evidence at all is not silent, because nothing says so.
|
||
|
||
Args:
|
||
target: The canonical id of the target.
|
||
outbound: The outbound paths, in the order of the user, as canonical ids.
|
||
silent_before: The time before which a first hop counts as silent, or
|
||
``None`` to keep each path.
|
||
|
||
Returns:
|
||
The scenarios (source ``outbound``, with the rank of their path), the best
|
||
first. A path that cannot reach the target is not in the list.
|
||
"""
|
||
found: list[PathScenario] = []
|
||
for rank, path in enumerate(outbound, start=1):
|
||
if not path or self.self_id in path:
|
||
continue
|
||
first_link = self.link(self.self_id, path[0])
|
||
if (
|
||
silent_before is not None
|
||
and first_link is not None
|
||
and first_link.last_seen is not None
|
||
and getattr(first_link.last_seen, "tzinfo", None) is not None
|
||
and first_link.last_seen < silent_before
|
||
):
|
||
continue
|
||
if target in path:
|
||
hops = path[: path.index(target)]
|
||
score = _TRUSTED_STRENGTH / (1.0 + _HOP_PENALTY * len(hops))
|
||
found.append(
|
||
PathScenario(f"outbound path {rank}", hops, "outbound", score, rank=rank)
|
||
)
|
||
continue
|
||
# The search gives its candidates by cost, and the score is the weakest link.
|
||
# The two orders differ (one weak direct link costs less than two strong links),
|
||
# so the best continuation is the best score among a few candidates.
|
||
best: PathScenario | None = None
|
||
for tail in self._best_routes(
|
||
target,
|
||
k=_MAX_SCENARIOS,
|
||
source=path[-1],
|
||
banned=frozenset({self.self_id, *path[:-1]}),
|
||
max_hops=_MAX_SCENARIO_HOPS - len(path),
|
||
):
|
||
hops = (*path, *tail)
|
||
strength, weakest, samples = self._weakest([path[-1], *tail, target])
|
||
score = strength / (1.0 + _HOP_PENALTY * len(hops))
|
||
if best is None or score > best.score:
|
||
best = PathScenario(
|
||
label=f"outbound path {rank}",
|
||
hops=hops,
|
||
source="outbound",
|
||
score=score,
|
||
weakest_snr=weakest,
|
||
samples=samples,
|
||
rank=rank,
|
||
)
|
||
if best is not None:
|
||
found.append(best)
|
||
found.sort(key=lambda s: -s.score)
|
||
# A near tie goes to the path that the user put first. The list is short (one
|
||
# entry for each outbound path), so a bubble pass is enough.
|
||
moved = True
|
||
while moved:
|
||
moved = False
|
||
for i in range(len(found) - 1):
|
||
ahead, behind = found[i], found[i + 1]
|
||
if behind.rank < ahead.rank and behind.score * (1.0 + _NEAR_TIE) >= ahead.score:
|
||
found[i], found[i + 1] = behind, ahead
|
||
moved = True
|
||
unique: list[PathScenario] = []
|
||
for scenario in found:
|
||
if all(scenario.hops != kept.hops for kept in unique):
|
||
unique.append(scenario)
|
||
return unique
|
||
|
||
def suggested(
|
||
self,
|
||
target: str,
|
||
*,
|
||
outbound: Sequence[tuple[str, ...]] = (),
|
||
silent_before: datetime | None = None,
|
||
) -> PathScenario | None:
|
||
"""The one best outbound route to ``target`` that has evidence, if one exists.
|
||
|
||
This is the answer from the data to "what is the best way to reach this node?".
|
||
It is the **observed** scenario with the highest score: a route through repeaters
|
||
that the recorder observed when they carried traffic (traces, overheard relay
|
||
chains, neighbour tables that MeshTerm read). It is ranked by its weakest link,
|
||
with a penalty for each hop, and the sample counts and median SNR of its links are
|
||
behind the score. It ignores on purpose the device and direct families that
|
||
:meth:`scenarios` also offers. The learned route of the firmware is what an
|
||
auto-routed trace already walks (the caller prefers it when it has one). A direct
|
||
path is the trivial fallback. Neither is a suggestion that the observations made.
|
||
For a node that the evidence can only reach directly (or not at all), the method
|
||
returns ``None``. Thus the caller keeps the default that it uses otherwise.
|
||
|
||
When the user has outbound paths, the best route through one of them comes first
|
||
(refer to :meth:`outbound_scenarios`). The user knows the way out of our node,
|
||
and the evidence about it is mostly what our node heard.
|
||
|
||
Args:
|
||
target: The canonical id of the target.
|
||
outbound: The outbound paths of the user, in order, as canonical ids.
|
||
silent_before: Skip an outbound path whose first hop was last heard before
|
||
this time.
|
||
|
||
Returns:
|
||
The best outbound :class:`PathScenario`, else the best observed one (always
|
||
with at least one intermediate hop, and a positive score from evidence), or
|
||
``None`` when nothing is better than a direct route.
|
||
"""
|
||
through = self.outbound_scenarios(target, outbound, silent_before=silent_before)
|
||
if through:
|
||
return through[0]
|
||
for scenario in self.scenarios(target):
|
||
if scenario.source == "observed" and scenario.hops and scenario.score > 0:
|
||
return scenario
|
||
return None
|
||
|
||
# --- internals -----------------------------------------------------------------
|
||
|
||
def _score_route(self, hops: tuple[str, ...], target: str) -> tuple[float, float | None, int]:
|
||
"""Score one outbound route by its weakest observed link.
|
||
|
||
A chain is only as reliable as its weakest link. Thus the score of the route is
|
||
the minimum link strength along ``us → hops… → target``, reduced for each hop
|
||
(refer to :data:`_HOP_PENALTY`). A route that has a link with no evidence scores
|
||
0. MeshTerm can offer it, but ranks it below all the routes that it observed.
|
||
|
||
Args:
|
||
hops: The intermediate canonical ids (can be empty for a direct route).
|
||
target: The canonical id of the destination.
|
||
|
||
Returns:
|
||
``(score, weakest_median_snr, total_samples)``.
|
||
"""
|
||
strength, weakest_snr, samples = self._weakest([self.self_id, *hops, target])
|
||
return strength / (1.0 + _HOP_PENALTY * len(hops)), weakest_snr, samples
|
||
|
||
def _weakest(self, chain: list[str]) -> tuple[float, float | None, int]:
|
||
"""The weakest link of a chain of nodes: its strength, the lowest SNR, the readings.
|
||
|
||
Args:
|
||
chain: The canonical ids of the nodes, in order.
|
||
|
||
Returns:
|
||
``(weakest_strength, weakest_median_snr, total_samples)``. The strength is 0
|
||
when a link of the chain has no evidence.
|
||
"""
|
||
weakest_strength: float | None = None
|
||
weakest_snr: float | None = None
|
||
samples = 0
|
||
for a, b in pairwise(chain):
|
||
link = self.link(a, b)
|
||
if link is None:
|
||
return 0.0, None, samples
|
||
strength = self.outward_strength(a, b, link)
|
||
samples += link.samples
|
||
if weakest_strength is None or strength < weakest_strength:
|
||
weakest_strength = strength
|
||
snr = link.median_snr
|
||
if snr is not None and (weakest_snr is None or snr < weakest_snr):
|
||
weakest_snr = snr
|
||
return weakest_strength or 0.0, weakest_snr, samples
|
||
|
||
def _best_routes(
|
||
self,
|
||
target: str,
|
||
*,
|
||
k: int,
|
||
source: str | None = None,
|
||
banned: frozenset[str] = frozenset(),
|
||
max_hops: int = _MAX_SCENARIO_HOPS,
|
||
) -> list[tuple[str, ...]]:
|
||
"""Find up to ``k`` strong simple paths from our node to ``target``, lowest cost first.
|
||
|
||
This is Yen's k-shortest-loopless-paths over the evidence graph. Each link costs
|
||
``1/strength + _HOP_PENALTY``, so a weak or indirect path costs more. The routes
|
||
come back ranked by total cost, the lowest first (:meth:`scenarios` then scores
|
||
this candidate set again by the weakest link). The method finds only simple
|
||
(loopless) paths, because a node visited again is never useful. It also finds only
|
||
routes with :data:`_MAX_SCENARIO_HOPS` intermediate hops or fewer. A longer chain
|
||
is more airtime and more points of failure than is good for a trace (and the trace
|
||
goes through it two times).
|
||
|
||
Yen's algorithm uses plain Dijkstra. It does not enumerate simple paths with a
|
||
best-first frontier, because that frontier is pathological on a real mesh graph. A
|
||
well-heard core has low-cost links everywhere, so a search of partial paths spreads
|
||
through all of the core. Each indirect prefix through the core costs less than the
|
||
one weak link in front of a distant target. Thus the search explores millions of
|
||
dead-end prefixes before it reaches the target (tens of seconds for a busy node).
|
||
Yen's algorithm instead finds the single shortest path. Then it finds each
|
||
next-shortest path when it routes around one edge of the previous path. Thus the
|
||
work stays polynomial in the graph size, however dense the core is. The result is
|
||
the same routes, in the same cost order (except for ties), in milliseconds.
|
||
|
||
Args:
|
||
target: The canonical id of the destination.
|
||
k: The maximum number of routes to return.
|
||
source: The canonical id where the routes start. The default is our node. An
|
||
outbound route continues from the last hop of its outbound path with it.
|
||
banned: The ids that a route must not go through (the hops of an outbound
|
||
path before ``source``, and our node).
|
||
max_hops: The most intermediate hops that a route can have.
|
||
|
||
Returns:
|
||
The intermediate-hop tuples of the routes that the method found (without the
|
||
endpoints), the lowest total cost first. The result is cached for each graph
|
||
version (refer to ``_routes_memo``). Callers must use the list as read-only,
|
||
and they do (both consumers only iterate it).
|
||
"""
|
||
start = self.self_id if source is None else source
|
||
memo_key = (target, k, self._graph_version, start, banned, max_hops)
|
||
memoized = self._routes_memo.get(memo_key)
|
||
if memoized is not None:
|
||
return memoized
|
||
neighbors: dict[str, list[tuple[str, float]]] = {}
|
||
for (a, b), link in self._links.items():
|
||
# Each direction has its own cost: a link out of our node is scored from what
|
||
# the far end measured from us (refer to outward_strength).
|
||
neighbors.setdefault(a, []).append(
|
||
(b, 1.0 / max(self.outward_strength(a, b, link), 1e-6) + _HOP_PENALTY)
|
||
)
|
||
neighbors.setdefault(b, []).append(
|
||
(a, 1.0 / max(self.outward_strength(b, a, link), 1e-6) + _HOP_PENALTY)
|
||
)
|
||
|
||
def shortest(
|
||
source: str, banned_nodes: set[str], banned_edges: set[tuple[str, str]]
|
||
) -> tuple[float, list[str]] | None:
|
||
"""Dijkstra ``source``→``target`` without the banned nodes and edges, or ``None``."""
|
||
dist: dict[str, float] = {source: 0.0}
|
||
prev: dict[str, str] = {}
|
||
heap: list[tuple[float, str]] = [(0.0, source)]
|
||
done: set[str] = set()
|
||
while heap:
|
||
d, u = heapq.heappop(heap)
|
||
if u in done:
|
||
continue
|
||
done.add(u)
|
||
if u == target:
|
||
break
|
||
for v, cost in neighbors.get(u, ()):
|
||
if v in banned_nodes or v in banned or (u, v) in banned_edges:
|
||
continue
|
||
nd = d + cost
|
||
if nd < dist.get(v, math.inf):
|
||
dist[v] = nd
|
||
prev[v] = u
|
||
heapq.heappush(heap, (nd, v))
|
||
if target not in dist:
|
||
return None
|
||
path = [target]
|
||
while path[-1] != source:
|
||
path.append(prev[path[-1]])
|
||
path.reverse()
|
||
return dist[target], path
|
||
|
||
def path_cost(path: list[str]) -> float:
|
||
total = 0.0
|
||
for a, b in pairwise(path):
|
||
total += min((c for v, c in neighbors.get(a, ()) if v == b), default=math.inf)
|
||
return total
|
||
|
||
first = shortest(start, set(), set())
|
||
if first is None or len(first[1]) - 2 > max_hops:
|
||
self._routes_memo[memo_key] = []
|
||
return []
|
||
accepted: list[list[str]] = [first[1]]
|
||
# Spur candidates, in a min-heap by total cost. A counter breaks ties, so that the
|
||
# heap never compares the path lists of candidates that have equal cost.
|
||
candidates: list[tuple[float, int, list[str]]] = []
|
||
seen: set[tuple[str, ...]] = {tuple(first[1])}
|
||
counter = 0
|
||
while len(accepted) < k:
|
||
prev_path = accepted[-1]
|
||
for i in range(len(prev_path) - 1):
|
||
spur = prev_path[i]
|
||
root = prev_path[: i + 1]
|
||
# Ban the next edge that each accepted path with this same root took. Thus
|
||
# the spur must take a really different route out of the spur node...
|
||
banned_edges: set[tuple[str, str]] = set()
|
||
for p in accepted:
|
||
if p[: i + 1] == root and len(p) > i + 1:
|
||
banned_edges.add((p[i], p[i + 1]))
|
||
banned_edges.add((p[i + 1], p[i]))
|
||
# ...and ban the interior nodes of the root, so that the detour stays loopless.
|
||
banned_nodes = set(root[:-1])
|
||
spur_result = shortest(spur, banned_nodes, banned_edges)
|
||
if spur_result is None:
|
||
continue
|
||
full = root[:-1] + spur_result[1]
|
||
if len(full) - 2 > max_hops:
|
||
continue
|
||
key = tuple(full)
|
||
if key in seen:
|
||
continue
|
||
seen.add(key)
|
||
counter += 1
|
||
heapq.heappush(candidates, (path_cost(full), counter, full))
|
||
if not candidates:
|
||
break
|
||
_, _, best_path = heapq.heappop(candidates)
|
||
accepted.append(best_path)
|
||
routes = [tuple(path[1:-1]) for path in accepted]
|
||
self._routes_memo[memo_key] = routes
|
||
return routes
|
||
|
||
|
||
def build_topology(
|
||
*,
|
||
self_id: str,
|
||
contacts: list[Contact],
|
||
trace_paths: list[TracedPath],
|
||
packet_paths: list[PacketPath],
|
||
neighbour_links: tuple[NeighbourLink, ...] | list[NeighbourLink] = (),
|
||
) -> MeshTopology:
|
||
"""Make the evidence graph from all that we received, or asked for.
|
||
|
||
Four sources go into the graph. :meth:`MeshTopology.add_walk` walks each one:
|
||
|
||
* **traces**: the hop sequence of each successful trace, with our node at the two
|
||
ends. The boomerang leaves our node and comes back to it, and the last hop, which
|
||
has no hash, is our node. The SNR of each hop is a reading on the link on which it
|
||
arrived.
|
||
* **contact routes**: the learned ``out_path`` of the firmware for each contact: a
|
||
chain from our node through its repeaters to the contact. There is no SNR. But the
|
||
route comes from real received floods, so it counts as one reading for each link
|
||
(with the last-heard time of the contact). A learned direct route is a direct link
|
||
to our node.
|
||
* **packets**: packets in the RX log: the relay chain, with the originator first when
|
||
known, and always with our node at the end (we heard the last relay). The measured
|
||
SNR is for that last link only.
|
||
* **neighbour reports**: links that a remote repeater reported about itself when we
|
||
read its neighbour table: one two-node walk for each entry, with the SNR as the
|
||
repeater measured it. This is the only evidence here that does not come from our
|
||
own reception. It can add nodes that we never heard from another source.
|
||
|
||
Args:
|
||
self_id: The key or hash of our device (any width, canonicalized to 12 hex).
|
||
contacts: The known contacts of the device (for canonicalization and route
|
||
evidence).
|
||
trace_paths: Stored successful trace walks (refer to ``Repository.trace_paths``).
|
||
packet_paths: Stored packet paths from the RX log (refer to
|
||
``Repository.packet_paths``).
|
||
neighbour_links: The current links that repeaters reported (refer to
|
||
``Repository.neighbour_links``). Empty when MeshTerm read no neighbour table.
|
||
|
||
Returns:
|
||
The populated :class:`MeshTopology`.
|
||
"""
|
||
topo = MeshTopology(self_id, contacts)
|
||
us = topo.self_id
|
||
|
||
for traced in trace_paths:
|
||
nodes: list[str | None] = [us]
|
||
snrs: list[float | None] = []
|
||
for hop, snr in traced.hops:
|
||
# The last hop, which has no hash, is the reply that comes back to our node.
|
||
nodes.append(topo.canonical(hop) if hop is not None else us)
|
||
snrs.append(snr)
|
||
topo.add_walk(nodes, snrs=snrs, when=traced.when, source="trace")
|
||
|
||
for contact in contacts:
|
||
if contact.route_hops is None:
|
||
continue
|
||
contact_id = topo.canonical(contact.public_key or contact.key_prefix)
|
||
route = [topo.canonical(h) for h in contact.route_hops]
|
||
topo.add_walk([us, *route, contact_id], when=contact.last_seen, source="route")
|
||
|
||
for packet in packet_paths:
|
||
nodes = []
|
||
if packet.origin:
|
||
nodes.append(topo.canonical(packet.origin))
|
||
nodes.extend(topo.canonical(h) for h in packet.hops)
|
||
nodes.append(us)
|
||
if len(nodes) < 2:
|
||
continue
|
||
# Only the last link (last relay → us) has the measured reception SNR.
|
||
snrs = [None] * (len(nodes) - 2) + [packet.snr]
|
||
topo.add_walk(nodes, snrs=snrs, when=packet.when, source="packet")
|
||
|
||
for reported in neighbour_links:
|
||
# The repeater measured the SNR when it received from its neighbour. add_walk
|
||
# gives a reading to the second node of a pair, so the neighbour goes first.
|
||
topo.add_walk(
|
||
[topo.canonical(reported.neighbour), topo.canonical(reported.repeater)],
|
||
snrs=[reported.snr],
|
||
when=reported.when,
|
||
source="neighbour",
|
||
)
|
||
|
||
# All the sources are in the graph. Collapse each node that reached our node at two
|
||
# hash widths (a bare trace hop next to its wide contact id), so that each node shows
|
||
# one time everywhere.
|
||
topo.coalesce_prefixes()
|
||
return topo
|