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.
