Control plane compression

Ryan Beckett, Aarti Gupta, Ratul Mahajan, David P. Walker

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

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.

Original languageEnglish (US)
Title of host publicationSIGCOMM 2018 - Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication
PublisherAssociation for Computing Machinery, Inc
Pages476-489
Number of pages14
ISBN (Electronic)9781450355674
DOIs
StatePublished - Aug 7 2018
Event2018 Conference of the ACM Special Interest Group on Data Communication, ACM SIGCOMM 2018 - Budapest, Hungary
Duration: Aug 20 2018Aug 25 2018

Publication series

NameSIGCOMM 2018 - Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication

Other

Other2018 Conference of the ACM Special Interest Group on Data Communication, ACM SIGCOMM 2018
CountryHungary
CityBudapest
Period8/20/188/25/18

Fingerprint

Electric network analysis
behavior control
network analysis
equivalence
simulation

All Science Journal Classification (ASJC) codes

  • Communication
  • Electrical and Electronic Engineering
  • Computer Networks and Communications
  • Signal Processing

Cite this

Beckett, R., Gupta, A., Mahajan, R., & Walker, D. P. (2018). Control plane compression. In SIGCOMM 2018 - Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication (pp. 476-489). (SIGCOMM 2018 - Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication). Association for Computing Machinery, Inc. https://doi.org/10.1145/3230543.3230583
Beckett, Ryan ; Gupta, Aarti ; Mahajan, Ratul ; Walker, David P. / Control plane compression. SIGCOMM 2018 - Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication. Association for Computing Machinery, Inc, 2018. pp. 476-489 (SIGCOMM 2018 - Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication).
@inproceedings{b0c5d657aefb42018fca806275d5f430,
title = "Control plane compression",
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.",
author = "Ryan Beckett and Aarti Gupta and Ratul Mahajan and Walker, {David P.}",
year = "2018",
month = "8",
day = "7",
doi = "10.1145/3230543.3230583",
language = "English (US)",
series = "SIGCOMM 2018 - Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication",
publisher = "Association for Computing Machinery, Inc",
pages = "476--489",
booktitle = "SIGCOMM 2018 - Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication",

}

Beckett, R, Gupta, A, Mahajan, R & Walker, DP 2018, Control plane compression. in SIGCOMM 2018 - Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication. SIGCOMM 2018 - Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication, Association for Computing Machinery, Inc, pp. 476-489, 2018 Conference of the ACM Special Interest Group on Data Communication, ACM SIGCOMM 2018, Budapest, Hungary, 8/20/18. https://doi.org/10.1145/3230543.3230583

Control plane compression. / Beckett, Ryan; Gupta, Aarti; Mahajan, Ratul; Walker, David P.

SIGCOMM 2018 - Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication. Association for Computing Machinery, Inc, 2018. p. 476-489 (SIGCOMM 2018 - Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Control plane compression

AU - Beckett, Ryan

AU - Gupta, Aarti

AU - Mahajan, Ratul

AU - Walker, David P.

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.

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

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

ER -

Beckett R, Gupta A, Mahajan R, Walker DP. Control plane compression. In SIGCOMM 2018 - Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication. Association for Computing Machinery, Inc. 2018. p. 476-489. (SIGCOMM 2018 - Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication). https://doi.org/10.1145/3230543.3230583