Border Gateway Protocol
In many ways the Border Gateway Protocol (BGP) is simply another routing protocol, yet it plays a very different role to the routing protocols used within an enterprise. BGP is the glue that makes the Internet work. The Internet is a large complex collection of subnets interconnected to form a global network. The subnets are owned and managed by different, often competing, organizations. The term autonomous system (AS), is used to describe the individual subnets. An AS, while not truly autonomous, is autonomous in that it is administered by a single authority. BGP is the protocol used to forge the agreements on how these ASs pass information.
In situations where there are multiple gateways within an AS, BGP is used internally between the gateways to determine which gateway offers the best route to a given destination network. Therefore, BGP has to implement two types of communication, one to other ASs, and one to other gateways within the AS.
Peering is the term used to describe the transit arrangements between ISPs. There are really two levels of peering, either you are a peer or a client. Peer networks agree to carry traffic of a peer without charging for it. Today it has become very difficult to get a peer agreement with a national ISP (NSP). Normally they require peering agreements to be in pace with multiple NSPs and high-speed (DS-3) connections to multiple NAPs. The requiring of other agreements can make this something of a chicken and egg situation. Clients have agreements and pay for transit.
Connections between networks can be private point-to-point links or through an exchange. Many NSPs are tending to move to private connections due to the overload situation at many of the NAPs.
So what has all this to do with BGP? BGP is the protocol used to exchange routing information between the various networks. Administrative agreements about ISP relationships have to be built into the BGP configuration.
Types of BGP Sessions
While the stated purpose of BGP is to allow for the conveyance of routing information between autonomous systems (AS), sometimes (particularly in the case of transit ASs) an AS must carry BGP updates internally from one border router to another. Clearly, BGP routers must communicate differently when they share a common AS (as opposed to being in different ASs). In fact, this is the distinction between Internal BGP (IBGP) and External BGP (EBGP).
These two variations on the same protocol act virtually the same in most instances. The differences between them lie in three areas.
- Routing update processing: A “best” route to a certain destination can be different for the BGP peers within the same AS.
- Handling of route attributes: Some BGP attributes are meaningless within an AS.
- Connectivity requirements: IBGP peers must be logically connected by TCP connections in a full mesh topology. This is necessary because IBGP does not repeat routes learned from one IBGP peer to other IBGP peers, in order to avoid creating routing loops. As the number of IBGP peers increases, the number of TCP connections grows quickly. BGP “confederations” and “route reflectors” have been developed to circumvent the full mesh requirement.
BGP Message Types
There are four types of BGP messages, each with its own role in setting up, maintaining, or tearing down a BGP peering session. They are listed below.
- OPEN messages are sent by the router initiating the BGP connection, in order to identify itself and to begin the exchange of routing information.
- UPDATE messages are sent by BGP peers in order to carry the network reachability information and path attributes between them. These messages are the “heart” of the protocol.
- KEEPALIVE messages are exchanged between peers to continually verify peer reachability when no updates are sent for a period of time.
- NOTIFICATION messages are BGP’s way of providing error messaging and control services. For example, peer A will send a NOTIFICATION 24 message to peer B if peer B attempts to use an attribute that peer A does not support. There are codes for approximately 25 different error conditions.
None of these messages may be exchanged until two BGP routers have first set up a TCP session between themselves on port 179. Errors on that TCP link will trigger BGP NOTIFICATION messages that will close the connection.
Listed below is the structure of a BGP OPEN message.
- Marker: This 16 byte field (not shown on the visual) contains a value used for synchronizations or authentication. When the message is an OPEN message and no authentication procedure is being used, the field is set to all ones.
- Length: This two byte field (not shown on the visual) indicates the total length of the message in octets.
- Type: This one byte field (not shown on the visual) reflects one of four BGP message types and is set to 1 for an OPEN message.
- Version: This one byte field reflects the version of BGP that the peer is running. The most current version is 4, but peers will negotiate to the highest common version they support.
- Autonomous system (AS) Number: This is a two byte value that indicates the sender’s AS number.
- Hold Time: This two byte integer is the number of seconds between keepalives and/or update messages. Peers will negotiate and select the minimum value, which must be at least three seconds. Zero is also a valid value (indicates no keepalives), but is typically not used.
- BGP Identifier: This four byte integer is the sender ID. It is set to one of the IP addresses, real or virtual, of the sending router. Cisco selects the highest IP address assigned to the router.
BGP UPDATE messages are used to withdraw routes or advertise routes. Withdrawn routes are noted in the variable length, withdrawn route portion of the UPDATE message, and advertised routes are noted in the variable length Network Layer Reachability Information (NLRI) portion of the UPDATE message. Both the withdrawn and NLRI portions are in a length, prefix format. Length, one octet, reflects the number of bits in the prefix, and prefix variable length is set to the prefix being advertised. For example, an aggregated range of class C address might be 16,200.1, which reflects the addresses 184.108.40.206 through 220.127.116.11. A single class B would be 16,150.3.
All the prefixes contained in the update share the path attributes contained in the UPDATE message. Attributes are a set of parameters that describe the path associated with the prefix. Attributes are associated with prefixes and are inputs to the BGP routing decision process. For example, when parallel routes to a prefix exist, the value of the attributes might dictate which route to use. An example of an attribute included in all updates is AS_PATH, which typically provides the list of AS the advertised prefix has traversed.
Becoming BGP Peers
BGP can be likened to a distribution application between routers. Similar to other TCP/IP applications, it uses TCP as the transport protocol to provide guaranteed delivery of messages.
As long as no extraordinary errors are encountered, the BGP session passes through two states, known as the IDLE and OPENSENT states, before routing information may be exchanged. (Errors or delays in the initial connection process can result in the routers entering other states, which will not be discussed here.)
In the IDLE state, the connection between peers is established on TCP port 179. BGP then enters the OPENSENT state, while the originating router sends a BGP OPEN message to its peer, indicating its desire to establish a BGP session. Upon receiving acknowledgment from the peer in the form of a KEEPALIVE message, and after responding to the peer’s own OPEN message, the session then enters the ESTABLISHED state in which routing information may be exchanged.
Routing information (called NLRI in the BGP vernacular) is exchanged in the form of UPDATE messages between the peers. These BGP updates also contain a list of attributes that apply to the path to the reachable networks, as well as a optional list of other routes that are no longer reachable on that path.
When first establishing sessions with its neighbors, a BGP router typically goes through a brief period of intense activity, during which its routing table is synchronized with those of its neighbors by the exchange of multiple UPDATE messages. Once that initial synchronization is obtained, however, UPDATEs are sent only when necessary to remove or add routes.
BGP Attribute Categories
BGP routing updates are more complex than the typical Interior Gateway Protocol (IGP), such as RIP. Rather than simply providing a destination address (prefix) and a cost, BGP provides the Network Layer reachability information (prefix) and a series of attributes associated with the prefix (network). Attributes are used in the routing decision process. They might also be used in the input and output policy definition process.
The four categories of attributes are described below.
- Well-known Mandatory: Attributes are required to be recognized by all BGP implementations (well-known) and are required in all BGP updates (mandatory).
- Well-known Discretionary: Attributes are required to be recognized by all BGP implementations (well-known) and may or may not be sent in a particular update message (discretionary).
- Optional Transitive: Attributes are not required to be recognized by all BGP implementations (optional), but if they are not recognized, the router will not act on the information contained in the attribute field. Transitive attributes are passed on to neighbors by the routers.
- Optional Nontransitive: Attributes are not required to be recognized by all BGP implementations (optional), but if they are not recognized, the router will not act on the information contained in the attribute field. Nontransitive attributes are consigned to the bit bucket.
BGP Routing Process
Most routing protocols receive routing information, use it to build and maintain a routing table, and share that table (or a subset of the table) with other routers in the network. The information included in the routing table and shared with others on the network is usually controllable only by the physical configuration of the network and by the application of relatively manual filters to the ports of the router.
What makes the BGP unique is its ability to apply policies to the information contained in routing updates (rather than the ports), and therefore accept or reject update information based on attributes of the information itself.
When routing updates are first received at a BGP router, they are subject to a series of policies (called input policies) that govern how or when the information will be stored and acted upon by the router. For example, a router might have a policy stating that it does not ever wish to access network 18.104.22.168 through AS 1159. Thus, if an update contains network reachability information stating a path to 22.214.171.124 through AS 1159, the router’s input policy engine would prohibit that update from reaching the routing table, resulting in the router never using that path. Alternatively, an administrator might wish to label a path undesirable, but not unusable. In that instance the input policy engine could be set to add the router’s own AS number to the path several times upon receipt, making the destination seem farther away (and therefore less desirable) to the routing process via that path.
BGP allows for output policies as well. These can filter outbound routing advertisements (e.g., “Don’t send any BGP information about 126.96.36.199 to AS47.”) or change attributes in the updates based on policy information set by the network administration.
Listed below are the RFCs associated with BGP and a few references that further describe BGP and Internet routing.
- RFC 1771: A Border Gateway Protocol 4 (BGP4)
- RFC 1772: Application of the Border Gateway Protocol in the Internet
- RFC 1773: Experience with the BGP4 Protocol
- RFC 1774: BGP4 Protocol Analysis
- RFC 1965: Autonomous System Confederations for BGP
- RFC 1966: BGP Route Reflection: An Alternative to Full Mesh IGBP
- RFC 1997: BGP Communities Attribute
- RFC 1998: An Application of the BGP Community Attribute in Multihome Routing
- RFC 1657: Definition of Managed Objects for the Fourth Version of BGP4 using SMIv2 (the BGP MIB)
- RFC 2008: Implications of Various Address Allocation Policies for Internet Routing
- RFC 2260: Scalable Support for Multihomed Multiprovider Connectivity
- RFC 2439: BGP Route Flap Dampening
- Stewart, John W. BGP4: Inter-Domain Routing in the Internet. Reading, MA: Addison-Wesley, 1999.
- Halabi, Sam and Danny McPherson. Internet Routing Architectures. 2nd ed. Indianapolis: Cisco Press, 2000.
|<mp3>http://podcast.hill-vt.com/podsnacks/2007q2/bgp.mp3%7Cdownload</mp3> | Border Gateway Protocol (BGP)|
|<mp3>http://podcast.hill-vt.com/podsnacks/2008q1/bgp_youtube.mp3%7Cdownload</mp3> | BGP and YouTube|