How MeshTopologyTracker Tracks Network Topology for Routing in BitChat

MeshTopologyTracker is a Swift service in BitChat that collects neighbor announcements, maintains a freshness-weighted view of mesh connectivity, and computes version-gated source routes using bidirectional edge confirmation and breadth-first search.

BitChat implements a peer-to-peer mesh network where devices periodically broadcast their directly reachable neighbors. The MeshTopologyTracker class, located in bitchat/Services/MeshTopologyTracker.swift, serves as the authoritative source for network topology and routing decisions. This article examines its internal data structures, update mechanisms, and route computation algorithm based on the BitChat source code.

---

Core Data Structures

The tracker maintains four critical pieces of state, all protected by a serial DispatchQueue named mesh.topology with barrier-wrapped writes:

Property	Type	Purpose
claims	[RoutingID: Set<RoutingID>]	Directed neighbor claims—each node's announced view of reachable peers
lastSeen	[RoutingID: Date]	Timestamp of the most recent update per node
observedVersions	[RoutingID: (version: UInt8, seenAt: Date)]	Highest protocol version observed from each peer
routeFreshnessThreshold	TimeInterval (60s)	Maximum age for edges to be considered valid during routing

Nodes without entries in observedVersions are assumed to support only legacy v1 protocol, enabling backward compatibility while allowing selective v2 routing.

---

Updating Network Topology

Neighbor Announcements

When a device receives a directNeighbors broadcast, it invokes:

tracker.updateNeighbors(for: sourceData, neighbors: neighborDataArray)

This method, implemented at lines 30–39 in MeshTopologyTracker.swift, performs three sanitization steps:

• Validates and truncates RoutingID values to fixed hop size
• Removes self-loop edges (a node claiming itself as neighbor)
• Stores the claim in claims[sourceData] with current timestamp in lastSeen[sourceData]

Protocol Version Tracking

Upon decoding packets with protocol version > 1, the routing layer calls:

tracker.recordObservedVersion(version, for: peerData)

Implemented at lines 42–49, this updates observedVersions with the highest version seen for that peer, enabling version-gated routing where all intermediate hops must support advanced features.

Stale Entry Pruning

The tracker provides explicit cleanup via:

tracker.prune(olderThan: TimeInterval)

This method (lines 68–78) removes entries from all three maps whose lastSeen timestamp exceeds the threshold, preventing routing through disappeared nodes.

---

Route Computation Algorithm

MeshTopologyTracker.computeRoute(from:to:maxHops:requiringVersion:) implements breadth-first search with three constraint layers:

1. Freshness Validation

Both current node and candidate neighbor must satisfy:

lastSeen[node] > now - routeFreshnessThreshold

This check appears at lines 12–15, activated for every edge exploration.

2. Bidirectional Edge Confirmation

An edge is valid only when mutually claimed:

// Lines 24–30 in computeRoute implementation
claims[last].contains(neighbor) && claims[neighbor].contains(last)

This bidirectional confirmation eliminates "ghost" links from asymmetric radio conditions or outdated announcements.

3. Version Gating

When requiringVersion is specified (lines 81–94), every intermediate hop and the destination must have:

observedVersions[node]?.version >= requiringVersion

This ensures feature compatibility along the entire path—critical for v2 source routing with signed packet headers.

BFS Execution

The search explores paths up to maxHops + 1 nodes. Upon reaching the destination, the method returns intermediate hops only—excluding source and target IDs—for direct insertion into v2 source-routed packets (**lines 40–44). Returns nil` if no path satisfies all constraints.

---

Integration with Routing Policy

The mesh routing layer (BLESourceRouteOriginationPolicy) consults the tracker per the specification in docs/SOURCE_ROUTING.md. For a packet to qualify for v2 source routing (lines 52–70):

• Sender must be local device
• Packet must be directed (not broadcast)
• TTL must exceed 1
• Recipient must not be directly reachable
• computeRoute(..., requiringVersion: 2) must return a complete path

Failure of any gate triggers fallback to flooding or direct-write approaches (lines 76–78).

---

Practical Usage Example

import bitchat

// Initialize tracker
let meshTracker = MeshTopologyTracker()

// Register our observed neighbors (normally from BLE advertisements)
let selfID = Data(hexString: "0102030405060708")!
let neighborIDs = [
    Data(hexString: "1112131415161718")!,
    Data(hexString: "2122232425262728")!
]
meshTracker.updateNeighbors(for: selfID, neighbors: neighborIDs)

// Record version capability for path gating
meshTracker.recordObservedVersion(2, for: neighborIDs[0])

// Attempt v2-routed delivery to remote peer
let destination = Data(hexString: "3132333435363738")!
if let hops = meshTracker.computeRoute(
    from: selfID,
    to: destination,
    requiringVersion: 2
) {
    // hops contains [RoutingID] of relay nodes only
    print("Source route: \(hops.map { $0.hexString }.joined(separator: " → "))")
} else {
    print("No valid v2 route — falling back to mesh flood")
}

// Maintenance: remove silent nodes
meshTracker.prune(olderThan: 120)

This pattern mirrors the test implementations in MeshTopologyTrackerTests.swift, which verify neighbor tracking, edge confirmation, version gating, and hop limit enforcement.

---

Summary

• Thread-safe state managed via DispatchQueue barrier writes protects concurrent access to claims, lastSeen, and observedVersions
• Bidirectional edge confirmation prevents routing through asymmetric or stale links
• Freshness thresholding (60s default) automatically excludes disappeared nodes without immediate pruning
• Version gating enables protocol evolution by requiring minimum capability along entire paths
• BFS route computation returns intermediate hops suitable for v2 source-routed packet headers

---

Frequently Asked Questions

How does MeshTopologyTracker handle stale neighbor information?

The tracker uses a routeFreshnessThreshold of 60 seconds during route computation—ignoring edges where lastSeen exceeds this age. Explicit cleanup via prune(olderThan:) removes entries entirely, but the freshness check operates without requiring synchronous pruning, allowing lazy garbage collection.

Why does BitChat require bidirectional edge confirmation for routing?

Unidirectional radio links or asymmetric propagation can create "ghost" edges where node A hears node B but A's transmissions never reach B. The condition claims[A].contains(B) && claims[B].contains(A) ensures both parties can actually communicate, eliminating black-holed traffic through confirmed symmetric links.

What happens when no version-2 route exists to the destination?

computeRoute returns nil when the freshness, version-gate, or edge-confirmation constraints cannot be satisfied. Per SOURCE_ROUTING.md, the routing policy then falls back to legacy flooding or direct BLE writes rather than attempting incompatible v2 source routing.

Can the freshness threshold be adjusted for different network conditions?

Yes—while routeFreshnessThreshold defaults to 60 seconds, the prune(olderThan:) method accepts arbitrary intervals. Deployments with highly mobile nodes might reduce this for faster convergence, while stable deployments could increase tolerance for intermittent beacon loss.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}