Reference. A Fast Quantitative Analyzer for NetKAT

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.

Cite

Cite as @lu-2026-a (helia, typst) · \cite{lu-2026-a} (LaTeX)
BibTeX
bibtex · 8 lines
@misc{lu-2026-a,
  author = {Thomas Lu and Qiancheng Fu and Kevin Batz and Oliver Bøving and Tiago Ferreira and Mark Moeller and Nate Foster and Alexandra Silva},
  title = {A Fast Quantitative Analyzer for NetKAT},
  year = {2026},
  month = {7},
  eprint = {2607.14420},
  archiveprefix = {arXiv}
}
hayagriva YAML (typst)
yaml · 15 lines
lu-2026-a:
  type: misc
  title: A Fast Quantitative Analyzer for NetKAT
  author:
  - Lu, Thomas
  - Fu, Qiancheng
  - Batz, Kevin
  - Bøving, Oliver
  - Ferreira, Tiago
  - Moeller, Mark
  - Foster, Nate
  - Silva, Alexandra
  date: 2026-07
  serial-number:
    arxiv: '2607.14420'
Cites 65 works (4 here)
With notes (4)

Weighted NetKAT: A Programming Language for Quantitative Network Verification suarezacevedo-2026-weighted

We introduce weighted NetKAT, a domain-specific language for modeling and verifying quantitative quantitative network properties. The language is parametric on a semiring , enabling the treatment of a wide range of quantities in a uniform way. We provide a denotational semantics and an equivalent operational semantics, the latter based on a novel model of weighted NetKAT automata ( WNKA ) capturing the stateful behavior of our language. With WNKA , we obtain a class of generic decision procedures for reasoning about quantitative safety and reachability in a fully automatic way, even in the presence of possibly unbounded iteration. We demonstrate the applicability of our framework in a case study using Internet2’s Abilene network as the underlying topology.
PDF · DOI · arXiv · pldb

Probabilistic NetKAT foster-2016-probabilistic

PDF · DOI · pldb

NetKAT: Semantic foundations for networks anderson2014netkat

Recent years have seen growing interest in high-level languages for programming networks. But the design of these languages has been largely ad hoc, driven more by the needs of applications and the capabilities of network hardware than by foundational principles. The lack of a semantic foundation has left language designers with little guidance in determining how to incorporate new features, and programmers without a means to reason precisely about their code. This paper presents NetKAT, a new network programming language that is based on a solid mathematical foundation and comes equipped with a sound and complete equational theory. We describe the design of NetKAT, including primitives for filtering, modifying, and transmitting packets; union and sequential composition operators; and a Kleene star operator that iterates programs. We show that NetKAT is an instance of a canonical and well-studied mathematical structure called a Kleene algebra with tests (KAT) and prove that its equational theory is sound and complete with respect to its denotational semantics. Finally, we present practical applications of the equational theory including syntactic techniques for checking reachability, proving non-interference properties that ensure isolation between programs, and establishing the correctness of compilation algorithms.
PDF · DOI · pldb

Kleene algebra with tests kozen1997kleene

We introduce Kleene algebra with tests, an equational system for manipulating programs. We give a purely equational proof, using Kleene algebra with tests and commutativity conditions, of the following classical result: every while program can be simulated by a while program with at most one while loop. The proof illustrates the use of Kleene algebra with tests and commutativity conditions in program equivalence proofs.
PDF · DOI · pldb
External (61)
lu-2026-a reference entries/refs/lu-2026-a/lu-2026-a.hel