ORB · Aerospace — Satellite Networking
Orbital Mesh Routing Engine
A deterministic, zero-heap C++17 routing kernel for moving satellite networks — the layer deciding, on every tick of a constellation's clock, which satellite forwards each packet to which next hop.
Overview
OMRE is written in the style flight software asks for: the kernel never allocates on the heap (every buffer is a fixed-size member of the engine object), uses no exceptions and no RTTI, bounds every per-tick loop by compile-time limits, and publishes bit-identical route tables across runs, compilers, optimisation levels and caller floating-point rounding modes. It is not certified to any flight-software standard.
On every tick it propagates each satellite, places ground terminals on the rotating Earth, decides which candidate links exist, computes all-pairs shortest paths and publishes forwarding tables. Recomputation is kept apart from per-packet lookup: in the exact modes forwarding is one bounds check and one indexed load into a precomputed next-hop matrix; in the hierarchical mode it is two or three small table loads.
Three exact modes — flat and cache-blocked Floyd-Warshall and a zero-heap Dijkstra from every node — produce bit-identical tables. A hierarchical cluster-overlay router trades exactness for speed: at 256 nodes it recomputes about 48× faster than flat Floyd-Warshall, at a mean path stretch of 1.23 and a worst pair of 12.5×. Propagation is two-body Kepler with J2 secular drift, alongside a strict, allocation-free TLE parser; positions from the acquirer's own propagator plug in directly.
The problem
Constellation routing is a recomputation problem disguised as a forwarding problem. The topology changes every tick, so all-pairs shortest paths must be recomputed continuously, and exact recomputation grows steeply with node count. Flight computers add static memory budgets, bounded execution and reproducibility requirements that general-purpose graph libraries, which allocate on the heap, are not designed to meet.
What it does
- Exact all-pairs shortest paths: flat Floyd-Warshall, cache-blocked Floyd-Warshall and zero-heap Dijkstra from every node, with bit-identical canonical next-hop tables.
- Hierarchical cluster-overlay routing with compact two-level forwarding tables; loop-free, never cheaper than the optimum, and falls back to exact blocked Floyd-Warshall in any tick it cannot be used.
- Kepler propagation with J2 secular drift, or externally supplied positions from the acquirer's own propagator.
- Strict, allocation-free TLE parser, fuzzed with libFuzzer.
- Integer-only link feasibility and routing (exact 128-bit line-of-sight test, fixed-point link costs) and deterministic in-house trigonometry instead of libm.
- Double-buffered published routes with a sequence number and timestamp, so forwarding threads can read concurrently and detect stale routes.
- Audit-evidence bundle in one script: build matrix, zero-allocation symbol audit, runtime allocation trap, pinned replay-identity hash and a measured-maximum regression gate.
Performance
Measured 2026-10-09| Metric | Figure | Basis |
|---|---|---|
| Hierarchical vs flat Floyd-Warshall recompute, 256 nodes (shipped settings) | 48.3× (median) / 51.4× (minimum); 48.4× vs the fastest exact mode (Dijkstra); mean stretch 1.23, p99 2.75, worst 12.5×, 0 lost pairs | Measured by Vlaander |
| Hierarchical vs flat Floyd-Warshall recompute, other sizes | 14.9× at 128 nodes (mean stretch 1.51, worst 18.4×); 105.4× at 512 nodes (mean stretch 1.21, worst 13.7×) | Measured by Vlaander |
| Forwarding lookup, 256 nodes (throughput / dependent chain) | 1.6 / 3.8 ns in the full-table modes; 2.8 / 4.7 ns in the hierarchical mode | Measured by Vlaander |
| Static memory footprint | 640.5 KiB per 256-node instance (193.7 KiB at 128 nodes, 2,329.1 KiB at 512) | Measured by Vlaander |
| Test suite | 86 cases, 3,493,147 assertions, 0 failures on GCC 14.3, GCC 12.2 and Clang 16, at -O0 and with -march=x86-64-v3 | Measured by Vlaander |
| Replay identity | Pinned hash 35efc30d33564cdc reproduced on every build and in all three non-default caller rounding modes | Measured by Vlaander |
- Date
- 2026-10-09
- Hardware
- AMD EPYC 7763, GitHub Codespace (shared Azure VM), 4 vCPU (2 cores), 15 GiB
- Toolchain
- GCC 14.3, -O3 -fno-exceptions -fno-rtti -ffp-contract=off, baseline x86-64 (no -march), single thread; audit matrix adds GCC 12.2 and Clang 16.0
- Source archive SHA-256
- bd6e4909e41f500fae05f9c851f9e4d64ee9dcd812cd5f3bc7f438210c924ad4
- Method
- Built from the delivered source archive. orb-bench, full mode: Walker delta shells (16 satellites per plane, 550 km, 53°), clusters of 4 planes × 4 slots, at most 4 gateways per cluster and 1 kept link per adjacent cluster pair; flat, blocked, Dijkstra and hierarchical recomputes interleaved, medians and minima over live topologies; stretch is the cost of the path packets actually follow over the optimal cost, across all reachable pairs. scripts/audit.sh for the build matrix, symbol audit, allocation trap, replay hash and regression gate.
- The catalogue's figures (57–65× hierarchical speed-up, ≈10 ns forwarding as a single indexed load, 62 cases / 45,460 assertions, ≈5,300 lines, GCC 11+ / Clang 13+ / MSVC) predate this build. As delivered, the speed-up at 256 nodes is 48.3–51.4× (53.3–55.7× with 3 gateways per cluster, at a mean stretch of 1.31) and is exceeded only at 512 nodes; a single indexed load holds in the full-table modes only.
- The hierarchical router has no a-priori stretch bound: its envelope is measured on the reference Walker shell, and pruning can disconnect pairs on other graphs. Use an exact mode where shortest paths are required.
- The regression gate records the maximum full-tick time of eleven scenarios, including the hierarchical-with-fallback path, against loose host-specific budgets. It is not a WCET analysis and bounds nothing on other hardware.
- Vlaander's internal quality review (2026-10-07, an earlier commit, on a loaded host) found ORB's flat Floyd-Warshall about 1.6× faster than the Boost Graph Library's and Boost's per-node Dijkstra 1.4–3.6× faster than ORB's flat Floyd-Warshall on these sparse graphs; ORB's own Dijkstra mode, added since, has not been compared against Boost. No competitive benchmark position is claimed.
- The host is a shared VM (1-minute load average 1.4–1.7 during the benchmark); figures moved by up to about 10% between runs on this machine, and the timing gate's budgets are host-specific, so a heavily loaded run can exceed them.
Value in your own metrics
- Recompute cost at scale
- Hierarchical recompute about 48× cheaper than flat Floyd-Warshall at 256 nodes (mean stretch 1.23) and about 105× at 512, measured by Vlaander on the hardware above.
- Per-packet forwarding cost
- 1.6–3.8 ns per lookup in the full-table modes and 2.8–4.7 ns in the hierarchical mode, measured by Vlaander on the hardware above.
- Qualification-supporting evidence
- Zero-allocation symbol audit, runtime allocation trap, pinned replay hash and a measured-maximum regression gate in one script, which passed in 138 s on the hardware above.
- Static memory footprint
- 640.5 KiB per 256-node instance with no heap use; quadratic in node count (2,329.1 KiB at 512 nodes).
Assurance and build
- Language
- C++17
- Build
- Verified on GCC 12.2, GCC 14.3 and Clang 16.0 (Linux x86-64) · -fno-exceptions · -fno-rtti · -ffp-contract=off · -Werror · MSVC untested
- Determinism
- Pinned replay hash identical across compilers, -O0/-O3, baseline x86-64 and x86-64-v3, and caller rounding modes; flat == blocked == Dijkstra tables — passing
- Allocation
- No allocation symbols in the kernel object; 0 heap calls under the runtime allocation trap — passing
- Execution time
- Measured-maximum regression gate, 11 cases including the fallback path and 512-node runs, host-specific budgets — passing (not a WCET analysis)
- Static analysis
- clang-tidy 16 (cert · cppcoreguidelines · hicpp) over the kernel: 0 findings
- Sanitizers
- Full test suite under ASan+UBSan with GCC 14 and Clang 16 — passing
- Fuzzing
- TLE parser, libFuzzer + ASan + UBSan with the shipped dictionary and corpus: 14,185,998 executions on the delivered code in 5 minutes, no findings
- Tests
- 86 cases · 3,493,147 assertions · 4 layers (unit, property against a Dijkstra oracle, integration, audit) — passing
- Codebase size
- 6,337 lines (3,072 kernel); no third-party code
- Source archive SHA-256
- bd6e4909e41f500fae05f9c851f9e4d64ee9dcd812cd5f3bc7f438210c924ad4
Releases are not yet cryptographically signed, and no release manifests or external audit summaries are published. Check the source tarball you receive against its SHA-256 in Schedule 1 of your Sale and Assignment Agreement, which you see before you sign.
Scope and maturity
What is real today, what is deliberately excluded, and what is pending — published unprompted.
Included today
- The routing kernel: flat and cache-blocked Floyd-Warshall, zero-heap Dijkstra, hierarchical cluster-overlay routing with exact fallback, Kepler + J2 propagation, and an allocation-free TLE parser.
- The audit-evidence bundle — build matrix, zero-allocation symbol audit, runtime allocation trap, pinned replay hash, measured-maximum regression gate — reproducible on the buyer's hardware with one script.
- 86 test cases and 3,493,147 assertions across four layers, including property tests against a Dijkstra oracle; benchmark, replay and allocation-trap tools; a TLE fuzz harness.
Explicitly scoped out
- The routing kernel only. Link-layer protocol, MAC scheduling, congestion control, queueing and packet I/O remain the acquirer's domain.
- Two-body Kepler propagation with J2 secular rates only (not SGP4: no periodic terms, drag or third body), sufficient for routing-feasibility decisions; higher-fidelity propagators feed positions in through the external-satellite interface.
- Targets the persistently connected LEO/MEO regime; Contact-Graph (DTN) routing for deep space is not bundled.
- Spherical, uniformly rotating Earth for ground sites and occlusion.
Pending
- Not DO-178C or ECSS-Q-ST-80 certified. The design (no heap, bounded loops, deterministic replay) is intended to ease a qualification programme; certification artefacts and a real WCET analysis are the acquirer's to add.
- Verified on Linux x86-64 only. Cross-compilation for specific flight hardware (LEON3, RAD5545, Vorago VA416xx), other architectures such as AArch64, and MSVC builds are untested and the acquirer's responsibility.
Who it's for
- LEO and MEO constellation operators building inter-satellite mesh networking.
- Satellite prime contractors and flight-software houses under schedule pressure on the routing subsystem.
- Defence integrators requiring deterministic, auditable routing for proliferated architectures.
- Ground-segment and hybrid space-terrestrial operators needing one routing model across moving and fixed nodes.
Before you buy
- The source ships with scripts/audit.sh, which reruns the whole evidence bundle (builds, tests, allocation audit, replay hash, timing gate) on your hardware after delivery; it took 138 s on the hardware above. The timing gate's budgets are host-measured, so expect to regenerate them for your machine.
- Cost the certification gap explicitly: not certified to DO-178C or ECSS-Q-ST-80, and the execution-time gate is a measured regression check, not a WCET analysis.
- Measure the hierarchical router's stretch on your own constellation against your link budget and latency SLOs; its envelope is empirical on the reference shell, not a guaranteed bound.
- Validate the 640.5 KiB footprint at your node count; it is quoted at 256 nodes and grows quadratically with node count.
- Scope cross-compilation to your target flight processor, and its regression budgets, as acquirer work.
What transfers
- The asset's sourceSubject to the Sale and Assignment Agreement, Vlaander assigns to the verified Buyer the transferable right, title and interest that Vlaander owns in the specified Asset. The assignment excludes Third Party Materials, open-source components, Vlaander’s pre-existing tools, generic know-how, development methods, trademarks, confidential information and any rights that cannot lawfully be assigned.
- Its testsThe test suite the published assurance claims rest on, as delivered in the source archive.
- Its audit artefactsSpecifications, model-checking output, reviews and the software bill of materials, where the asset has them.
- Not includedThird-party and open-source materials are not sold or assigned by Vlaander. They remain under their own licences, listed in each asset’s software bill of materials (SBOM.md in the archive), and the Buyer is responsible for complying with those licences.
First described in: VLA-GEN catalogue, 3 August 2026, §3.5. Revised by Vlaander against the delivered source; every figure is labelled with its basis.
From test to source
- 01
Check
Read the engine's page: what Vlaander measured and on which hardware, what it has not measured, and the open review findings. Nothing runs before purchase.
- 02
Buy
Verified businesses only. Place the order, give your company's details, have your authorised signatory sign the Sale and Assignment Agreement, then pay the invoice in naira by bank transfer, or in USDC on Polygon. Once the payment is verified, your account shows Paid.
- 03
Receive
We confirm the funds and release the source tarball to you. Delivering, then Download ready. Check it against the SHA-256 in Schedule 1, then rerun the tests and benchmarks yourself.