TY - GEN
T1 - Control plane compression
AU - Beckett, Ryan
AU - Gupta, Aarti
AU - Mahajan, Ratul
AU - Walker, David
N1 - Funding Information:
We would like to thank the ACM SIGCOMM reviewers and our shepherd Laurent Vanbever, whose feedback helped improve this paper. This work was supported in part by NSF Grants 1703493 and 1525936, and gifts from Cisco and Facebook. Any opinions, findings, and conclusions expressed herein are those of the authors and do not necessarily reflect those of the NSF, Cisco or Facebook.
Publisher Copyright:
© 2018 Copyright held by the owner/author(s).
PY - 2018/8/7
Y1 - 2018/8/7
N2 - 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.
AB - 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.
KW - Network Verification
KW - Stable Routing Problem
UR - http://www.scopus.com/inward/record.url?scp=85056419618&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85056419618&partnerID=8YFLogxK
U2 - 10.1145/3230543.3230583
DO - 10.1145/3230543.3230583
M3 - Conference contribution
AN - SCOPUS:85056419618
T3 - SIGCOMM 2018 - Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication
SP - 476
EP - 489
BT - SIGCOMM 2018 - Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication
PB - Association for Computing Machinery, Inc
T2 - 2018 Conference of the ACM Special Interest Group on Data Communication, ACM SIGCOMM 2018
Y2 - 20 August 2018 through 25 August 2018
ER -