  Data plane verification (DPV) is important for finding network errors.
Current DPV tools employ a centralized architecture, where a server collects
the data planes of all devices and verifies them. Despite substantial efforts
on accelerating DPV, this centralized architecture is inherently unscalable. In
this paper, to tackle the scalability challenge of DPV, we circumvent the
scalability bottleneck of centralized design and design Coral, a distributed,
on-device DPV framework. The key insight of Coral is that DPV can be
transformed into a counting problem on a directed acyclic graph, which can be
naturally decomposed into lightweight tasks executed at network devices,
enabling scalability. Coral consists of (1) a declarative requirement
specification language, (2) a planner that employs a novel data structure DVNet
to systematically decompose global verification into on-device counting tasks,
and (3) a distributed verification (DV) protocol that specifies how on-device
verifiers communicate task results efficiently to collaboratively verify the
requirements. We implement a prototype of Coral. Extensive experiments with
real-world datasets (WAN/LAN/DC) show that Coral consistently achieves scalable
DPV under various networks and DPV scenarios, i.e., up to 1250 times speed up
in the scenario of burst update, and up to 202 times speed up on 80% quantile
of incremental verification, than state-of-the-art DPV tools, with little
overhead on commodity network devices.
