Data plane verification (DPV) analyzes routing tables and detects routing abnormalities and policy violations during network operation and planning. Thus, it has become an important tool to harden the networking infrastructure and the computing systems built on top. Substantial advancements have been made in the last decade and state-of-the-art DPV systems can achieve sub-$\mu$s verification for an update of a single forwarding rule. In this article, we introducefast inverse model transformation(FIMT), the first theoretical framework to systematically model and analyze centralized DPV systems. FIMT reveals the algebraic structure in themodel updateprocess, a key step in fast DPV systems. Thus, it can systematically analyze the correctness of several DPV systems and optimization techniques, using algebraic properties. The theory also guides the design and implementation of Uimt, a generic DPV framework with provable optimization techniques. Using Uimt, we create two variants of existing DPV systems, NeoFlash and NeoDeltaNet. Evaluations show that NeoFlash outperforms existing state-of-the-art centralized DPV systems in various datasets and reveal insights to key techniques towards fast DPV.

Data plane verification can be an important technique to reduce network disruptions, and researchers have recently made significant progress in achieving fast data plane verification. However, as we apply existing data plane verification techniques to large-scale networks, two problems appear due to extremes. First, existing techniques cannot handle too-fast arrivals, which we call update storms, when a large number of data plane updates must be processed in a short time. Second, existing techniques cannot handle well too-slow arrivals, which we call long-tail update arrivals, when the updates from a number of switches take a long time to arrive.

Despite the emergence of multi-table pipelining as a key feature of next-generation SDN data-path models, there is no existing work that addresses the substantial programming challenge of utilizing multi-tables automatically. In this paper, we present Magellan, the first system that addresses the aforementioned challenge. Introducing two novel, substantial algorithms, map-explore and table-design, Magellan achieves automatic derivation and population of multi-table pipelines from a datapath-oblivious, high-level SDN program written in a general-purpose language. Comparing the flow tables generated by Magellan with those produced by standard SDN controllers including OpenDaylight and Floodlight, we show that Magellan uses between 46-68x fewer rules.