Control plane compression
Authors:
Open Access
- 7 August 2018
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 476-489
Abstract
We develop an algorithm capable of compressing large networks into smaller ones with similar control plane behavior: For every stable routing solution in the large, original network, there exists a corresponding solution in the compressed network, and vice versa. Our compression algorithm preserves a wide variety of network properties including reachability, loop freedom, and path length. Consequently, operators may speed up network analysis, based on simulation, emulation, or verification, by analyzing only the compressed network. Our approach is based on a new theory of control plane equivalence. We implement these ideas in a tool called Bonsai and apply it to real and synthetic networks. Bonsai can shrink real networks by over a factor of 5 and speed up analysis by several orders of magnitude.Keywords
All Related Versions
Funding Information
- National Science Foundation (1703493, 1525936)
- Cisco Systems
This publication has 27 references indexed in Scilit:
- Real-Time Verification of Network Properties Using Atomic PredicatesIEEE/ACM Transactions on Networking, 2015
- Debugging the data plane with anteaterACM SIGCOMM Computer Communication Review, 2011
- Detecting and resolving policy misconfigurations in access-control systemsACM Transactions on Information and System Security, 2011
- Metarouting2005
- Predicate Abstraction of ANSI-C Programs Using SATFormal Methods in System Design, 2004
- Understanding BGP misconfiguration2002
- The stable paths problem and interdomain routingIEEE/ACM Transactions on Networking, 2002
- Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints1977
- An axiomatic basis for computer programmingCommunications of the ACM, 1969
- Assigning meanings to programs1967