  Real-time network verification promises to automatically detect violations of
network-wide reachability invariants on the data plane. To be useful in
practice, these violations need to be detected in the order of milliseconds,
without raising false alarms. To date, most real-time data plane checkers
address this problem by exploiting at least one of the following two
observations: (i) only small parts of the network tend to be affected by
typical changes to the data plane, and (ii) many different packets tend to
share the same forwarding behaviour in the entire network. This paper shows how
to effectively exploit a third characteristic of the problem, namely:
similarity among forwarding behaviour of packets through parts of the network,
rather than its entirety. We propose the first provably amortized quasi-linear
algorithm to do so. We implement our algorithm in a new real-time data plane
checker, Delta-net. Our experiments with SDN-IP, a globally deployed ONOS
software-defined networking application, and several hundred million IP prefix
rules generated using topologies and BGP updates from real-world deployed
networks, show that Delta-net checks a rule insertion or removal in
approximately 40 microseconds on average, a more than 10X improvement over the
state-of-the-art. We also show that Delta-net eliminates an inherent bottleneck
in the state-of-the-art that restricts its use in answering Datalog-style "what
if" queries.
