Bifröst: Spatial Networking with Bigraphs

Josh Millar, Ryan Gibb, Roy Ang, Anil Madhavapeddy, Hamed HaddadiarXiv 2025 · DOI · arXiv

Abstract

Bifröst is a novel architecture for spatial networking that aligns digital network boundaries with physical ones, such as walls and rooms. By leveraging the mathematical framework of bigraphs, Bifröst enables developers to define policies and instantiate services that automatically appear when users enter a physical space and dissolve upon their departure. This approach addresses the "spatial disconnect" in modern networking, providing a local-first, privacy-preserving alternative to cloud-centric architectures.

Introduction

Current networking paradigms suffer from a significant "Spatial Disconnect." Cloud-first architectures often route commands from a user to a nearby device through distant data centers, introducing latency and privacy concerns. Conversely, local hubs typically create "flat" networks where a smart appliance in a kitchen shares the same network segment as a private workstation in an office. Achieving room-level isolation currently requires complex, manual configuration of VLANs and firewalls.

Bifröst proposes a spatial abstraction where physical containment—being inside a room—naturally dictates network hierarchy, naming, and security. By treating physical boundaries as network perimeters, it allows for intuitive, automated management of smart environments.

The Bigraph Framework

The core of Bifröst is the Bigraph, a formalism originally proposed by Robin Milner. A bigraph consists of two overlapping structures that represent the state of a spatial network:

  • The Place Graph: A tree representing physical containment (e.g., Building → Floor → Room → Device).
  • The Link Graph: A hypergraph representing logical connectivity, defining which entities can communicate.
Figure 1: The bigraph formalism combines a place graph (containment) and a link graph (connectivity) to model spatial networks.

Key Innovations

  1. Reaction Rules: These are "if-this-then-that" patterns for space. For example, a rule might specify: "If three authorized users are in the Conference Room, spawn a transcription service." The service is automatically dissolved when the condition is no longer met.
  2. Spatial Name System (SNS): Devices receive names based on their location (e.g., mic.room-101) rather than static IP addresses. If hardware is replaced, the new device inherits the existing spatial identity.
  3. Automated Ingestion: The system bootstraps its spatial map using OpenStreetMap for building footprints and Apple’s RoomPlan (LiDAR scans) for precise indoor layouts.

Implementation and Mapping

The Bifröst runtime is implemented in OCaml, utilizing Cap’n Proto for efficient communication between local hubs and devices. To bridge the gap between the physical world and the digital bigraph, the system processes 3D scans into structured data.

Figure 5: The ingestion pipeline converts 3D RoomPlan scans into structured JSON nodes, which are then mapped into the bigraph.

Evaluation and Results

Bifröst was evaluated using synthetic graphs of up to 10,000 nodes, real-world 3D scans of office environments, and OpenStreetMap data.

  • Scalability: Reaction times scale linearly. Even at a campus-scale (10,000 nodes), the system identifies and applies rules within milliseconds.
  • Efficiency: The memory footprint remains under 50MB for large-scale graphs, making the system suitable for low-power hardware like Raspberry Pis.
  • Performance: In end-to-end tests of a spatially-scoped meeting service, the Bifröst logic took less than 1ms to execute, with the primary bottleneck being the startup time of the associated Docker containers.

Discussion and Future Work

Bifröst introduces "Just-in-Time" (JIT) networking, where secure tunnels and services "evaporate" when no longer needed, leaving no residual access. Because policies are written against types (e.g., MeetingRoom) rather than specific IDs, they are highly portable across different buildings.

Future work will address the latency of spawning service containers, perhaps through "pre-warming" services as users approach a room. Additionally, protecting the detailed bigraph map from unauthorized access remains a critical privacy challenge. The authors also envision using Large Language Models (LLMs) to author spatial policies, provided they can be formally verified to prevent security vulnerabilities.

Summary updated

BibTeX
@misc{millar2025bifrost,
  author = {Josh Millar and Ryan Gibb and Roy Ang and Anil Madhavapeddy and Hamed Haddadi},
  title = {{Bifröst: Spatial Networking with Bigraphs}},
  year = {2025},
  eprint = {2507.22687},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.22687},
}
Figure