Skip to main content

Abstract interpretation of distributed network control planes

Author(s): Beckett, Ryan; Gupta, Aarti; Mahajan, Ratul; Walker, David

To refer to this page use:
Abstract: The control plane of most computer networks runs distributed routing protocols that determine if and how traffic is forwarded. Errors in the configuration of network control planes frequently knock down critical online services, leading to economic damage for service providers and significant hardship for users. Validation via ahead-of-time simulation can help find configuration errors but such techniques are expensive or even intractable for large industrial networks. We explore the use of abstract interpretation to address this fundamental scaling challenge and find that the right abstractions can reduce the asymptotic complexity of network simulation. Based on this observation, we build a tool called ShapeShifter for reachability analysis. On a suite of 127 production networks from a large cloud provider, ShapeShifter provides an asymptotic improvement in runtime and memory over the state-of-the-art simulator. These gains come with a minimal loss in precision. Our abstract analysis accurately predicts reachability for all destinations for 95% of the networks and for most destinations for the remaining 5%. We also find that abstract interpretation of network control planes not only speeds up existing analyses but also facilitates new kinds of analyses. We illustrate this advantage through a new destination "hijacking" analysis for the border gateway protocol (BGP), the globally-deployed routing protocol.
Publication Date: Dec-2019
Citation: Beckett, Ryan, Aarti Gupta, Ratul Mahajan, and David Walker. "Abstract interpretation of distributed network control planes." Proceedings of the ACM on Programming Languages 4, no. POPL (2019): pp. 42:1-42:27. doi:10.1145/3371110
DOI: 10.1145/3371110
EISSN: 2475-1421
Pages: 42:1 - 42:27
Type of Material: Journal Article
Journal/Proceeding Title: Proceedings of the ACM on Programming Languages
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.