Ryan Beckett
Todd Millstein
ABSTRACT
We develop Propane, a language and compiler to help network operators with a challenging, error-prone task—bridging the gap between network-wide routing objectives and low-level configurations of devices that run complex, distributed protocols. The language allows operators to specify their objectives naturally, using high-level constraints on both the shape and relative preference of traffic paths. The compiler automatically translates these specifications to router-level BGP configurations, using an effective intermediate representation that compactly encodes the flow of routing information along policy-compliant paths. It guarantees that the compiled configurations correctly implement the specified policy under all possible combinations of failures. We show that Propane can effectively express the policies of datacenter and backbone networks of a large cloud provider; and despite its strong guarantees, our compiler scales to networks with hundreds or thousands of routers.
- 1.M. Al-Fares, A. Loukissas, and A. Vahdat. A scalable, commodity data center network architecture. In SIGCOMM, August 2008. Google Scholar
Digital Library
- 2.C. Alaettinoglu, C. Villamizar, E. Gerich, D. Kessens, D. Meyer, T. Bates, D. Karrenberg, and M. Terpstra. Routing policy specification language (RPSL). RFC 2622, RFC Editor, June 1999. http://www.rfc-editor.org/rfc/rfc2622.txt. Google ScholarDigital Library
- 3.C. J. Anderson, N. Foster, A. Guha, J.-B. Jeannin, D. Kozen, C. Schlesinger, and D. Walker. NetKAT: Semantic foundations for networks. In POPL, January 2014. Google ScholarDigital Library
- 4.M. Anderson. Time warner cable says outages largely resolved. http://www.seattletimes.com/business/time-warner-cable-says-outages-largely-resolved, August 2014.Google Scholar
- 5.P. Berde, M. Gerola, J. Hart, Y. Higuchi, M. Kobayashi, T. Koide, B. Lantz, B. O'Connor, P. Radoslavov, W. Snow, and G. Parulkar. ONOS: Towards an open, distributed SDN OS. In HotSDN, August 2014. Google ScholarDigital Library
- 6.News and press | BGPMon. http://www.bgpmon.net/news-and-events/.Google Scholar
- 7.M. Bjorklund. YANG - a data modeling language for the network configuration protocol (NETCONF). RFC 6020, RFC Editor, October 2010. http://www.rfc-editor.org/rfc/rfc6020.txt.Google Scholar
- 8.M. Casado, M. J. Freedman, J. Pettit, J. Luo, N. McKeown, and S. Shenker. Ethane: Taking control of the enterprise. In SIGCOMM, August 2007. Google ScholarDigital Library
- 9.R. Enns, M. Bjorklund, J. Schoenwaelder, and A. Bierman. Network configuration protocol (NETCONF). RFC 6241, RFC Editor, June 2011. http://www.rfc-editor.org/rfc/rfc6241.txt.Google Scholar
- 10.N. Feamster and H. Balakrishnan. Detecting BGP configuration faults with static analysis. In NSDI, May 2005. Google ScholarDigital Library
- 11.N. Feamster, J. Winick, and J. Rexford. A model of BGP routing for network engineering. In SIGMETRICS, June 2004. Google ScholarDigital Library
- 12.A. Fogel, S. Fung, L. Pedrosa, M. Walraed-Sullivan, R. Govindan, R. Mahajan, and T. Millstein. A general approach to network configuration analysis. In NSDI, March 2015. Google ScholarDigital Library
- 13.N. Foster, M. J. Freedman, A. Guha, R. Harrison, N. P. Katta, C. Monsanto, J. Reich, M. Reitblatt, J. Rexford, C. Schlesinger, A. Story, and D. Walker. Languages for software-defined networks. IEEE Communications Magazine, 51(2):128–134, February 2013.Google ScholarCross Ref
- 14.W. Gelade and F. Neven. Succinctness of the complement and intersection of regular expressions. ACM Trans. Comput. Logic, 13(1):4:1–4:19, January 2012. Google ScholarDigital Library
- 15.A. Gember-Jacobson, R. Viswanathan, A. Akella, and R. Mahajan. Fast control plane analysis using an abstract representation. In SIGCOMM, August 2016. Google ScholarDigital Library
- 16.P. Gill, N. Jain, and N. Nagappan. Understanding network failures in data centers: Measurement, analysis, and implications. In SIGCOMM, August 2011. Google ScholarDigital Library
- 17.T. G. Griffin and G. Wilfong. On the correctness of IBGP configuration. In SIGCOMM, August 2002. Google ScholarDigital Library
- 18.Hatch – create and share configurations. http://www.hatchconfigs.com/.Google Scholar
- 19.P. Lapukhov, A. Premji, and J. Mitchell. Use of BGP for routing in large-scale data centers. Internet draft, August 2015.Google Scholar
- 20.F. Le, G. G. Xie, and H. Zhang. On route aggregation. In CoNEXT, December 2011. Google ScholarDigital Library
- 21.T. Lengauer and R. Tarjan. A fast algorithm for finding dominators in a flowgraph. In TOPLAS, July 1979. Google ScholarDigital Library
- 22.R. Mahajan, D. Wetherall, and T. Anderson. Understanding BGP misconfiguration. In SIGCOMM, August 2002. Google ScholarDigital Library
- 23.J. McCauley, A. Panda, M. Casado, T. Koponen, and S. Shenker. Extending SDN to large-scale networks. In Open Networking Summit, April 2013.Google Scholar
- 24.S. Narain. Network configuration management via model finding. In LISA, December 2005. Google ScholarDigital Library
- 25.S. Narain, G. Levin, S. Malik, and V. Kaul. Declarative infrastructure configuration synthesis and debugging. Journal of Network Systems Management, 16(3):235–258, October 2008. Google ScholarDigital Library
- 26.S. Narain, R. Talpade, and G. Levin. Guide to Reliable Internet Services and Applications, chapter Network Configuration Validation. Springer, 2010.Google Scholar
- 27.S. Narayana, M. Tahmasbi, J. Rexford, and D. Walker. Compiling path queries. In NSDI, March 2016. Google ScholarDigital Library
- 28.S. Owens, J. Reppy, and A. Turon. Regular-expression derivatives re-examined. In J. Funct. Program., March 2009. Google ScholarDigital Library
- 29.M. Reitblatt, M. Canini, N. Foster, and A. Guha. FatTire: Declarative fault tolerance for software defined networks. In HotSDN, August 2013. Google ScholarDigital Library
- 30.R. Soulé, S. Basu, P. J. Marandi, F. Pedone, R. Kleinberg, E. G. Sirer, and N. Foster. Merlin: A language for provisioning network resources. In CoNEXT, December 2014. Google ScholarDigital Library
- 31.configuration templates | thwack. https://thwack.solarwinds.com/search.jspa?q=configuration+templates.Google Scholar
- 32.K. Weitz, D. Woos, E. Torlak, M. D. Ernst, A. Krishnamurthy, and Z. Tatlock. Formal semantics and automated verification for the border gateway protocol. In NetPL, March 2016.Google Scholar
Index Terms
- Don't Mind the Gap: Bridging Network-wide Objectives and Device-level Configurations
Recommendations
Network configuration synthesis with abstract topologies
PLDI 2017: Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and ImplementationWe develop Propane/AT, a system to synthesize provably-correct BGP (border gateway protocol) configurations for large, evolving networks from high-level specifications of topology, routing policy, and fault-tolerance requirements. Propane/AT is based ...
Don't mind the gap: Bridging network-wide objectives and device-level configurations: brief reflections on abstractions for network programming
We reflect on the historical context that lead to Propane, a high-level language and compiler to help network operators bridge the gap between network-wide routing objectives and low-level configurations of devices that run complex, distributed ...
Programming Distributed Control Planes: Invited Demo: Demo
SOSR '17: Proceedings of the Symposium on SDN ResearchWe describe Propane, a system that consists of a language for specifying the end-to-end routing policy for a network and a compiler for implementing the policy by generating a collection of device configurations for the BGP routing protocol that run on ...
Comments