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
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.
Probabilistic NetKAT foster-2016-probabilistic
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.
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.
External (61)
- RNG: Flat Datacenter Networks at Scale (2026)
- KATch2: a symbolic verifier for reversible NetKAT in Rust (2025)
- Alibaba HPN: A Data Center Network for Large Language Model Training (2024)
- KATch: A Fast Symbolic Verifier for NetKAT (2024)
- Lessons from the evolution of the Batfish configuration analysis tool (2023)
- Targeted multiobjective Dijkstra algorithm (2023)
- P4Testgen: An Extensible Test Oracle For P4 (2022)
- An Improved Multiobjective Shortest Path Algorithm (2021)
- Semiring Provenance for Fixed-Point Logic (2021)
- Provenance-Based Algorithms for Rich Queries over Graph Databases (2021)
- An algebraic framework for multi-objective and robust variants of path problems (2020)
- The probabilistic model checker Storm (2020)
- APKeep: Realtime Verification for Real Networks (2020)
- Tiramisu: Fast Multilayer Network Verification (2020)
- Validating datacenters at scale (2019)
- Reachability Analysis for AWS-Based Networks (2019)
- Scalable verification of probabilistic networks (2019)
- Asynchronous convergence of policy-rich distributed bellman-ford routing protocols (2018)
- p4v: practical verification for programmable data planes (2018)
- Debugging P4 programs with vera (2018)
- Bayonet: probabilistic inference for networks (2018)
- A General Approach to Network Configuration Verification (2017)
- Fast Control Plane Analysis Using an Abstract Representation (2016)
- A fast compiler for NetKAT (2015)
- Jupiter rising: a decade of Clos topologies and centralized control in Google's datacenter network (2015)
- A general approach to network configuration analysis (2015)
- A Knowledge Compilation Map for Ordered Real-Valued Decision Diagrams (2014)
- Circuits for Datalog Provenance (2014)
- Real-time verification of network properties using atomic predicates (2013)
- Real Time Network Policy Checking Using Header Space Analysis (2013)
- VeriFlow: verifying network-wide invariants in real time (2013)
- Header Space Analysis: Static Checking for Networks (2012)
- Solving multi-metric network problems: An interplay between idempotent semiring rules (2011)
- The Internet Topology Zoo (2011)
- Jellyfish: Networking Data Centers Randomly (2011)
- Quantitative Multi-objective Verification for Probabilistic Systems (2011)
- PRISM 4.0: verification of probabilistic real-time systems (2011)
- Semiring-Induced Propositional Logic: Definition and Basic Algorithms (2010)
- Semirings and Formal Power Series (2009)
- A Soft Approach to Multi-objective Optimization (2008)
- Graphs, dioids and semirings : new models and algorithms (2008)
- Iteration semirings (2008)
- Multi-objective model checking of Markov decision processes (2007)
- Provenance semirings (2007)
- Decision Diagrams for the Computation of Semiring Valuations (2005)
- An Algebra of Pareto Points (2005)
- Metarouting (2005)
- Inductive *-semirings (2004)
- Semiring Frameworks and Algorithms for Shortest-Distance Problems (2002)
- Network Calculus: A Theory of Deterministic Queuing Systems for the Internet (2001)
- Analysis of an Equal-Cost Multi-Path Algorithm (2000)
- Multi-Terminal Binary Decision Diagrams: An Efficient Data Structure for Matrix Representation (1997)
- Algebraic decision diagrams and their applications (1997)
- Domain theory (1995)
- The Fourier transform and semirings of Pareto sets (1992)
- Edge-valued binary decision diagrams for multi-level hierarchical verification (1992)
- Automata and languages generalized to ω-continuous semirings (1991)
- Graph-Based Algorithms for Boolean Function Manipulation (1986)
- Algebraic Structures for Transitive Closure (1976)
- Finding the K shortest loopless paths in a network (1971)
- Automating the Analysis and Improvement of Dynamic Programming Algorithms with Applications to Natural Language Processing