Spanning Tree & Routing

Routing in FIPS has no central routing table. Each node makes local forwarding decisions using three data structures: a spanning tree, a set of bloom filters, and a coordinate system derived from the tree. Together, these let any node forward a packet toward any other node, using only information it already has from its direct peers.

Building the spanning tree

Every FIPS mesh has a root. The root is the node with the lexicographically smallest node_addr. No election protocol is needed. Each node picks the smallest address it has heard about, and because the sorting is deterministic, all nodes converge on the same root.

Each node selects one of its peers as a parent. The parent is the peer that offers the best path to the root, weighted by link cost (measured via MMP: round-trip time, loss rate, jitter). The resulting parent-child relationships form a spanning tree over the mesh.

Coordinates

A node's tree coordinate is the sequence of node_addr values from itself to the root: [self, parent, ..., root]. Because the tree is rooted and parents are unique, this coordinate uniquely identifies a node's position in the tree.

Tree distance between two nodes is the total hops from each to their lowest common ancestor. This is computed by finding the longest common suffix of their coordinate arrays.

Simulator

Drag nodes to reposition them. Click a node to inspect it. Use "Route From" to select a source, then click a destination to visualize the greedy routing path. "Kill Link" severs a random mesh link and the tree reconverges.

Bloom filters for reachability

Each node maintains one outbound bloom filter per peer. The filter for peer Q summarizes the set of node_addr values reachable through this node, excluding anything Q already knows about. When a packet arrives for an unknown destination, the node queries each peer's most recent inbound filter. A "no" answer means the destination is definitely unreachable through that peer. A "yes" means it might be reachable (bloom filters have false positives, but never false negatives).

Two rules shape how filters propagate. Tree-only merge: only filters received from tree peers (parent + children) are merged into outgoing filters. Non-tree mesh peers still send and receive FilterAnnounce messages, but their filters are only consulted for direct single-hop shortcuts, not propagated further. This keeps filters from saturating as the mesh grows. Split-horizon exclusion: the outbound filter to peer Q never includes entries learned from Q itself, which prevents the two peers from echoing each other's contents back and forth. Routing loops are prevented separately, by the strict-decreasing tree-distance check at every hop.

The widget below uses the same ten demo nodes as the simulator above. Each label hashes to a node_addr, which is what actually lands in the filter. Insert a few, then query a node you never inserted. Most will come back "definitely not present"; a few will come back "maybe present" even though they were never added. That is a false positive.

The routing priority chain

When a node needs to forward a packet, it runs through find_next_hop(), which follows this priority chain:

1. Local delivery. Is the destination me? Deliver locally.
2. Direct peer. Is the destination a direct peer? Forward to it.
3. Bloom filter candidate. Does any peer's bloom filter claim reachability? Forward to the closest such peer by tree distance. Requires the destination's coordinates to be in the local cache.
4. Greedy tree routing. Fallback when bloom filters have not converged yet. Forward to the peer that minimizes tree distance to the destination's coordinates.
5. No route. No peer is strictly closer to the destination than this node, or the destination's coordinates are missing. Drop the packet and emit a PathBroken or CoordsRequired error signal back to the source. There is no "forward to the parent and hope" fallback: the source is responsible for repairing the routing state.

The step-through below implements a simplified version (without bloom filter lookup) on a five-node mesh. Pick a source and destination, then step through the decision process.

What happens when the network splits

If a partition separates the mesh into two (or more) disconnected segments, each segment independently reconverges. The segment without the original root elects a new root (the smallest node_addr in the segment). When segments rejoin, the globally smallest root wins, and the tree re-stabilizes.

This reconvergence happens through normal gossip. Nodes periodically exchange their root and depth information with peers. When the numbers disagree, they re-evaluate their parent choices. The process converges in O(diameter) rounds, proportional to the depth of the tree.