BGP Configuration Validation Jennifer Rexford The Internet is, by definition, a "network of networks," and the responsibility for gluing together the tens of thousands of independently-administered networks falls to the Border Gateway Protocol (BGP) [RFC 4271, Stewart 1999]. A network, or Autonomous System (AS), uses BGP to tell neighboring networks about each block of IP addresses, it can reach; in turn, neighboring ASes propagate this information to their neighbors, allowing the entire Internet to learn how to direct packets toward their ultimate destinations. On the surface, BGP is a relatively simple path-vector routing protocol, where each router selects a single best route among those learned from its neighbors, adds its own AS number to the front of the path, and propagates the updated routing information to its neighbors for their consideration; packets flow in the reverse direction, with each router directing traffic along the chosen path in a hop-by-hop fashion. Yet, BGP is a highly configurable protocol, giving network operators significant control over how each router selects a "best" route and whether that route is disseminated to its neighbors. The configuration of BGP across the many routers in an AS collectively expresses a routing policy that is based on potentially complex business objectives [Casear 2005]. For example, a large Internet Service Provider (ISP) uses BGP policies to direct traffic on revenue-generating paths through their own downstream customers, rather than using paths through their upstream providers. A small AS like a university campus or corporate network typically does not propagate a BGP route learned from one upstream provider to another, to avoid carrying data traffic between the two larger networks. In addition, network operators may configure BGP to filter unexpected routes that arise from configuration mistakes and malicious attacks in other ASes [Nordstrom 2004, Butler 2008]. BGP configuration also affects the scalability of the AS, where network operators choose not to propagate routes for their customers' small address blocks to reduce the size of BGP routing tables in the rest of the Internet. Finally, network operators tune their BGP configuration to direct traffic away from congested paths to balance load and improve user-perceived performance [Feamster 2007]. The routing policy is configured as a "route map" that consists of a sequence of clauses that match on some attributes in the BGP route and take a specific action, such as discarding the route or modifying its attributes with the goal of influencing the route-selection process. The BGP protocol defines many different attributes, and the route-selection process compares the routes one attribute at a time to ultimately identify one "best" route. This somewhat indirect mechanism for selecting and propagating routes, coupled with the large number of route attributes and route-selection steps, makes configuring BGP routing policy immensely complicated and error-prone. Network operators often use tools for automatically configuring their BGP-speaking routers [Gottlieb 2003, Boehm 2005, Enck 2009]. These tools typically consist of a template that specifies the sequence of vendor-specific commands to send to the router, with parameters unique to each BGP session populated from a database; for example, these parameters might indicate a customer's name, AS number, address block(s), and the appropriate route-maps to use. When automated tools are not used, the network operators typically have configuration-checking tools to ensure that the sessions are configured correctly, and that different sessions are configured in a consistent manner [Feamster 2005, Caldwell 2003]. Configuring the BGP sessions with neighboring ASes, while important, is not the only challenge in BGP configuration. In practice, an AS consists of multiple routers in different locations; in fact, a large ISP may easily have hundreds if not thousands of routers connected by numerous links into a backbone topology. Different routers connect to different neighbor ASes, giving each router only a partial view of the candidate BGP routes. As such, large ISPs typically run BGP inside their networks to allow the routers to construct a more complete view of the available routes. These internal BGP (iBGP) sessions must be configured correctly to ensure that each router has all the information it needs to select routes that satisfy the AS's policy. The simplest solution is to have a "full mesh" configuration, with an iBGP session between each pair of routers. However, this approach does not scale, forcing large ISPs to introduce hierarchy by configuring route reflectors or confederations that limit the number of iBGP sessions and constrain the dissemination of routes. Each route reflector, for instance, selects a single "best route" that it disseminates to its clients; as such, the route-reflector clients do not learn all the candidate routes they would have learned in a full-mesh configuration. When the "topology" formed by these iBGP sessions violates certain properties, routing anomalies like protocol oscillations, forwarding loops, traffic blackholes, and violations of business contracts can arise [Griffin 2002, Basu 2002, Zhang-Shen 2008]. Fortunately, static analysis of the iBGP topology, spread over the configuration of the routers inside the AS, can detect when these problems might arise [Feamster 2005]. Such tools check, for instance, that the top-level route reflectors are fully connected by a "full mesh" of iBGP sessions. This prevents "signaling partitions" that could prevent some routers from learning any route for a destination. Static analysis can also check that route reflectors are "close" to their clients in the underlying network topology, to ensure that the route reflectors make the same routing decisions that their clients would have made with full information about the alternate routes. Finally, these tools can validate an ISP's own local rules for ensuring reliability in the face of router failures. For instance, static analysis can verify that each router is configured with at least two route-reflector parents. Collectively, these kinds of checks on the static configuration of the network can prevent a wide variety of routing anomalies. For the most part, configuration-validation tools operate on the vendor-specific configuration commands applied to individual routers. Configuration languages vary from one vendor to another---for example, Cisco and Juniper routers have very different syntax and commands, even for relatively similar configuration tasks. Even within a single company, different router products and different generations of the router operating system have different commands and options. This makes configuration validation an immensely challenging task, where the configuration-checking tools much support a wide range of languages and commands. To address these challenges, research and standards activities have led to new BGP configuration languages that are independent of the vendor-specific command syntax [RFC 2622, Nettle], particularly in the area of BGP routing policy. In addition to abstracting vendor-specific details, these frameworks provide some support for configuring entire networks rather than individual routers. For example, the Routing Policy Specification Language (RPSL) [RFC 2622] is object-oriented, where objects contain AS-wide policy and administrative information that can be published in Internet Routing Registries (IRRs). Routing policy can be expressed in terms of user-friendly keywords for defining actions and groups of address blocks or AS number. Configuration-generation tools can read these specifications to generate vendor-specific commands to apply to the individual routers [IRR-Toolset]. However, while RPSL is used for publishing information in the IRRs, many ISPs still use their own configuration tools (or manual processes) for configuring their underlying routers. In summary, the configuration of BGP takes place at many levels---within a single router (to specify a single end-point of a BGP session with the appropriate route-maps and addresses), between pairs of routers (to ensure consistent configuration of the two ends of a BGP session), across different sessions to the same neighboring AS (to ensure consistent application of the routing policy at each connection point), and across an entire AS (to ensure the iBGP topology is configured correctly). In recent years, tools have emerged for static analysis of router-configuration data to identify potential configuration mistakes, and for automated generation of the configuration commands that are sent to the routers. Still, many interesting challenges remain in raising the level of abstraction for configuring BGP, to move from the low-level focus on configuring individual routers and BGP sessions toward configuring an entire network, and from the specific details of the BGP route attributes and route-selection process to a high-level specification of an AS's routing policy. As the Internet continues to grow, and the business relationships between ASes become increasingly complex, these issues will only become more important in the years ahead. [Basu 2002] A. Basu, C.-H. Ong, A. Rasala, F. B. Shepherd, and G. Wilfong, "Route oscillations in I-BGP with route reflection," Proc. ACM SIGCOMM, August 2002. [Bohm 2005] H. Bohm, A. Feldmann, O. Maennel, C. Reiser, and R. Volk, "Network-wide interdomain routing policies: Design and realization," unpublished report, http://www.net.t-labs.tu-berlin.de/papers/BFMRV-NIRP-05.pdf, 2005. [Butler 2008] Kevin Butler, Toni Farley, Patrick McDaniel, and Jennifer Rexford, "A survey of BGP security issues and solutions," in submission, August 2008. [Caesar 2005] Matt Caesar and Jennifer Rexford, "BGP routing policies in ISP networks," IEEE Network Magazine, special issue on interdomain routing, November/December 2005. [Caldwell 2003] Don Caldwell, Anna Gilbert, Joel Gottlieb, Albert Greenberg, Gisli Hjalmtysson, and Jennifer Rexford, "The cutting EDGE of IP router configuration," Proc. ACM SIGCOMM HotNets Workshop, November 2003. [Enck 2009] William Enck, Thomas Moyer, Patrick McDaniel, Subhabrata Sen, Panagiotis Sebos, Sylke Spoerel, Albert Greenberg, Yu-Wei Eric Sung, Sanjay Rao, and William Aiello, "Configuration Management at Massive Scale: System Design and Experience," IEEE Journal on Selected Areas in Communications, 2009. [Feamster 2005] N. Feamster and H. Balakrishnan. "Detecting BGP configuration faults with static analysis," Proc. Symposium on Networked Systems Design and Implementation, May 2005. [Feamster 2007] Nick Feamster and Jennifer Rexford, "Network-wide prediction of BGP routes," IEEE/ACM Transactions on Networking, April 2007, pp. 253-266. [Gottlieb 2003] Joel Gottlieb, Albert Greenberg, Jennifer Rexford, and Jia Wang, "Automated provisioning of BGP customers," IEEE Network Magazine, November/December 2003. [Griffin 2002] T. G. Griffin and G. Wilfong, "On the correctness of IBGP configuration," Proc. ACM SIGCOMM, August 2002. [IRR-Toolset] Internet Routing Registry Toolset Project, https://www.isc.org/software/IRRtoolset [Nettle] Andreas Voellmy and Paul Hudak, "Nettle: A domain-specific language for routing configuration," Web site, http://bebop.cs.yale.edu/voellmy/nettle.html [Nordstrom 2004] O. Nordstrom and C. Dovrolis, "Beware of BGP attacks,'' ACM SIGCOMM Computer Communications Review, vol. 34, no. 2, pp. 1-8, Apr. 2004. [RFC 2622] C. Alaettinoglu and C. Villamizar and E. Gerich and D. Kessens and D. Meyer and T. Bates and D. Karrenberg and M. Terpstra, "Routing Policy Specification Language (RPSL)," RFC 2622, June 1999. [RFC 4271] Y. Rekhter, T. Li, and S. Hares, "A Border Gateway Protocol 4 (BGP-4),'' RFC 4271, Jan. 2006. [Stewart 1999] J. Stewart, BGP4: Inter-Domain Routing in the Internet. Reading, MA: Addison-Wesley, 1999. [Zhang-Shen 2008] R. Zhang-Shen, Y. Wang, and J. Rexford, "Atomic routing theory: Making an AS route like a single node," Princeton University Computer Science technical report TR-827-08, July 2008.