Adaptive Mesh Routing

Choosing a peer-to-peer routing algorithm also means choosing assumptions about connectivity and available resources. A protocol may depend on frequent neighbor updates, spare bandwidth, or storage for messages awaiting delivery. These assumptions often remain implicit in its design. Its operating limits can become apparent only after conditions change.

I built Jacquard to make these system contracts and their failure conditions more explicit.¹ It combines a Rust routing library with a deterministic simulator. The larger question is whether understanding those limits can guide an adaptive routing algorithm. Such an algorithm would adjust its behavior as connectivity and resource availability change.

Comparing routing strategies

Consider two groups of devices joined by an intermittent relay. During a contact window, the relay provides a connected path between them. Between windows, a message may need to remain on a device until another transfer becomes possible. Several conversations may compete for that opportunity.

Routing strategies incur different costs in this situation. Maintaining next-hop tables consumes bandwidth for control traffic, while explicit search spends work constructing paths. Store-carry-forward uses storage and later contacts to move messages across disconnection. Changes in relay availability or resource budgets can make a previously suitable strategy ineffective.

Jacquard compares seven engines spanning proactive next-hop routing, explicit-path search, deferred delivery, and hybrid corridors.² The proactive group includes BATMAN variants, Babel’s distance-vector approach, and OLSRv2’s link-state approach. Engines propose routes through a shared contract, while a common router manages admission and installed route identities. Each engine states whether it exposes a path, a next hop, a corridor, or an opportunistic-delivery claim.

Making the contract explicit

A system contract connects a strategy’s operating requirements to the service it can provide. Jacquard makes parts of that relationship explicit through capability declarations, resource limits, and admission checks. An engine uses observed conditions to assess a proposed route. The router assigns an accepted route an identity and a period of validity.

Later observations can undermine the evidence supporting that route. A lost link may require local repair, a different route, or a change of strategy. The engine reports the outcome through an explicit lifecycle. This gives adaptation a defined place to act, although detecting every violated assumption remains an experimental problem.

This distinction also permits honest descriptions of disconnection. Scatter can claim that opportunistic delivery is supportable without publishing a connected path. A corridor engine can distinguish loss of connected support from a decision to retain a message. Applications can make waiting an explicit requirement, and admission checks must preserve its meaning across a change of strategy.

Experiments that can be replayed

The experiments first ask where each strategy’s operating assumptions stop supporting useful routing. A further question is whether observations of changing conditions can guide a better response. Jacquard compares implementations under controlled changes in connectivity, workload, and resource pressure. The scenarios include asymmetric links, partitions, delayed observations, and overloaded relays.

Each experiment runs a scenario across explicit seeds and engine configurations, allowing comparisons across multiple realizations of the same modeled conditions. Tuning sweeps identify operating points before comparative runs hold configurations fixed. Measurements include activation, route presence, recovery, and route changes. Additional experiments measure the weakest flow and check installed forwarding evidence against changed topology.³

The simulator drives the same router and host integration used by the reference client. Routing state uses integer quantities, explicit logical time, and deterministic ordering. Replaying the same inputs reproduces the modeled execution. This makes a failed transition inspectable, although physical radios and uncontrolled traffic still require separate validation.

Finding the failure conditions

The shared-relay experiments exposed a severe problem with averaging across objectives. Pathway alone gave one flow complete route availability while two others remained entirely unserved. BATMAN Bellman, Mercator, Scatter, and the combined Pathway–BATMAN stack avoided that starvation in the same families.⁴ Their minimum per-flow availability reached 100% on the measured fairness window.

A high average concealed a failure to support concurrent requests. An adaptive policy needs to detect that failure even while aggregate availability remains high. Measuring the weakest flow makes neglected requests visible. These experiments measure route availability, so successful packet delivery and throughput fairness remain further questions.

Delayed information creates another discrepancy between route presence and valid support. In the recovery-window experiment, Mercator published no unusable connected routes after the disruption but provided a route for less of the run. Pathway maintained higher publication presence while retaining unusable connected routes for nine rounds. The table counts rounds with unsupported connected routes after disruption alongside total-window publication presence.⁵

Choosing among engines

Registering several engines provides options for adaptation. In one high-loss connected scenario, however, the mixed router achieved 87.5% route presence. The best standalone engines reached 91.6% under their representative configurations.⁷ Having a better option registered did not ensure its selection.

The router can retain an early acceptable route until maintenance or expiry triggers reconsideration. That policy preserves continuity, but it can delay a useful switch. Adaptive routing therefore requires criteria for reconsidering a strategy before its existing route disappears. The current experiments expose that requirement without yet establishing a reliable selection rule.

Mercator explores a response to these findings. It maintains a bounded collection of evidence and plans a primary route with alternatives.⁸ It tracks underserved objectives and pressure on heavily used relays. Its repair process invalidates evidence after topology changes and withdraws connected support when surviving alternatives are insufficient.

Carrying messages across gaps

Disconnection requires a different measure of success. A message can arrive through successive contacts without any simultaneous path between sender and recipient. Jacquard’s separate diffusion experiments measure delivery by a common workload deadline, undelivered targets, latency, and resource costs. Selective forwarding and suppression performed well under several modeled scarcity and congestion conditions.⁹

Those experiments simulate contact policies rather than executing every engine’s actual forwarding implementation. Unresolved deadlines remain unmeasured, and the same application outcomes still need instrumentation across actual engines. Some policies also use delivery and cluster information that a deployed system would need to obtain. Its acquisition cost and reliability remain unresolved.

Mercator’s implementation also has an important boundary. Its corridor planning and maintenance are implemented, but its router forwarding hook currently accepts payloads without transmitting them.¹⁰ Its experimental results support further development of the design. They do not establish a finished Mercator delivery service.

Using Jacquard as a library

For developers building peer-to-peer mesh systems, Jacquard supplies reusable routing contracts and an environment for evaluating implementations. The reference client combines in-tree engines with an in-memory network, allowing developers to inspect route activation and failure before supplying their own transport implementation. Applications construct topology observations, activate routing objectives, and advance explicit rounds.¹¹ A host bridge handles incoming events, logical time, and queued transport sends.

Custom deployments can implement an engine, transport, or device profile against the shared interfaces. A transport adapter describes observed links and carries bytes. The router manages route identity and lifetime. A custom composition connects these responsibilities to the application’s executor and radio stack.

The most immediate use is to investigate a proposed routing design’s operating contract. Developers can vary conditions and inspect the failures that follow. Several engines already invoke transport senders, while production relay behavior still needs application integration. The same experiments can test whether an adaptive policy recognizes those failures and changes behavior soon enough to preserve service.