← All papers
First page of A Fast Quantitative Analyzer for NetKAT

A Fast Quantitative Analyzer for NetKAT

Thomas Lu, Qiancheng Fu, Kevin Batz, Oliver Bøving, Tiago Ferreira, Mark Moeller, Nate Foster, Alexandra Silva

cs.PL Jul 15, 2026 · v1
The weighted NetKAT symbolic analysis framework, including weighted symbolic packet programs and semiring semantics, is formalized in Lean.
When designing a network, engineers must navigate trade-offs (e.g., one topology offers more aggregate bandwidth, another lower latency or better resilience) that demand reasoning about quantitative properties. We present a fast analyzer for quantitative network properties based on weighted NetKAT (wNetKAT), a domain-specific language that provides a semantic foundation for quantitative reasoning by modeling network behavior using weights drawn from a semiring. At the core of our development is the design of a symbolic data structure – weighted symbolic packet programs (wSPPs) – that compactly represent the semantics of weighted policies, for which a direct implementation would be intractable. We show how to compute all policy constructs symbolically; unsurprisingly, the crux is Kleene star, for which we design a tailored algorithm. We further develop trace-carrying Pareto semirings, which compute multi-objective frontiers together with the network paths that realize them. We formalize the development in Lean and provide an optimized Rust implementation. Being parametric on a semiring, our implementation covers both classical and quantitative analyses: we show that it is competitive with KATch, a heavily optimized Boolean-reachability verifier, and orders of magnitude faster than McNetKAT and Storm on probabilistic analyses. A case study comparing Fat-tree and Jellyfish data-center topologies shows the framework supports multi-objective design-time analysis.

Network engineers must reason about quantitative properties (bandwidth, latency, resilience) when designing networks, requiring efficient analysis of quantitative network policies. Direct implementations of weighted NetKAT semantics are intractable.

A fast analyzer for weighted NetKAT (wNetKAT) is developed, based on weights drawn from a semiring. A symbolic data structure called weighted symbolic packet programs (wSPPs) compactly represents weighted policy semantics, with all policy constructs computed symbolically including a tailored Kleene star algorithm. Trace-carrying Pareto semirings compute multi-objective frontiers along with realizing network paths. The development is formalized in Lean with an optimized Rust implementation.

The implementation is competitive with KATch (a Boolean-reachability verifier) and orders of magnitude faster than McNetKAT and Storm on probabilistic analyses. A case study comparing Fat-tree and Jellyfish data-center topologies demonstrates multi-objective design-time analysis.