2023 · 21 citations · 15 references
ComputingComputer EngineeringComputer ScienceFault-tolerant ComputingFault-tolerant SystemsFormal MethodsDeductive VerificationModel CheckingNetwork ProtocolsProtocol VerificationRoutingVerificationBgp Route ControlModularityNetwork VerificationNode FailuresReachabilityTopology Verification
Current network control plane verification tools cannot scale to large networks because of the complexity of jointly reasoning about the behaviors of all network nodes. We present a modular approach to control plane verification, where end-to-end network properties are verified via a set of purely local checks on individual nodes and edges. The approach targets verification of reachability properties for BGP configurations, and provides guarantees in the face of arbitrary external route announcements and, for some properties, arbitrary node/link failures. We have proven the approach correct and implemented it in a tool Lightyear. Experimentally we show Lightyear scales dramatically better than prior control plane verifiers. Further, Lightyear has been used for six months to verify properties of a major cloud provider network containing hundreds of routers and tens of thousands of edges, finding and fixing bugs in the process. To our knowledge no prior control-plane verification tool has been shown to scale to that size and complexity. Our modular approach also makes it easy to localize configuration errors and enables incremental re-verification.
15
An axiomatic basis for computer programming
C. A. R. Hoare · Communications of the ACM · 1969 · 3.9K citations · Full text
Carolyn Jane Anderson, Nate Foster, Arjun Guha et al. · 2014 · 374 citations
A General Approach to Network Configuration Verification
Ryan Beckett, Aarti Gupta, Ratul Mahajan et al. · 2017 · 230 citations
Ahmed Khurshid, Wenxuan Zhou, Matthew Caesar et al. · ACM SIGCOMM Computer Communication Review · 2012 · 178 citations
Debugging the data plane with anteater
Haohui Mai, Ahmed Khurshid, Rachit Agarwal et al. · ACM SIGCOMM Computer Communication Review · 2011 · 159 citations