Reducing the complexity of BGP stability analysis with hybrid combinatorial-algebraic models

@inproceedings{Perouli2012b,
	title        = {Reducing the complexity of BGP stability analysis with hybrid combinatorial-algebraic models},
	author       = {Debbie Perouli and Stefano Vissicchio and Alexander Gurney and Olaf Maennel and Timothy Griffin and Iain Phillips and Sonia Fahmy and Cristel Pelsser},
	year         = 2012,
	month        = nov,
	journal      = {2012 The 2nd International Workshop on Rigorous Protocol Engineering ({WRiPE})},
	booktitle    = {The 2nd International Workshop on Rigorous Protocol Engineering ({WRiPE})},
	publisher    = {{IEEE} Computer Society},
	address      = {Austin, TX, USA},
	pages        = {1--6},
	doi          = {10.1109/ICNP.2012.6459945},
	isbn         = {978-1-4673-2446-5},
	issn         = {1092-1648},
	abstract     = {Routing stability and correctness in the Internet have long been a concern. Despite this, few theoretical frameworks have been proposed to check BGP configurations for convergence and safety. The most popular approach is based on the Stable Paths Problem (SPP) model. Unfortunately, SPP requires enumeration of all possible control-plane paths, which is infeasible in large networks. In this work, we study how to apply algebraic frameworks to the BGP configuration checking problem. We propose an extension of the Stratified Shortest Path Problem (SSPP) model that has a similar expressive power to SPP, but enables more efficient checking of configuration correctness. Our approach remains valid when BGP policies are applied to iBGP sessions - a case which is often overlooked by previous work, although common in today's Internet. While this paper focuses mainly on iBGP problems, our methodology can be extended to eBGP if operators are willing to share their local-preference configurations.},
	bibsource    = {dblp computer science bibliography, https://dblp.org},
	biburl       = {https://dblp.org/rec/conf/icnp/PerouliVGMGPFP12.bib},
	eventdate    = {30 Oct.-2 Nov. 2012},
	eventtitleaddon = {Austin, TX, USA},
	file         = {:https\://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6459945:PDF},
	groups       = {International Conferences},
	keywords     = {BGP, Internet Routing, Algebraic Modeling}
}