BGP

This research page is based on the van Beijnum text, chapters 1 and 2.

Definitions

Term	Definition
IX	Internet Exchange
Transit	Accessing a backbone which interconnects other networks
Peering	Providing an interconnect between two or more networks
Tier 1 ISP	Only peers with other ISPs, connecting to all tier 1 ISPs guarantees connectivity to the entire internet
Tier 2 ISP	An ISP which uses a combination of peering and transit from Tier 1 ISPs
Tier 3 ISP	A smaller ISP with a minimal network, very little peering, receiving transit from a tier 1 or 2 ISP
IGP	Interior Gateway Protocol, a type of routing protocol used on smaller-scale, sometimes multi-site networks
EGP	Exterior Gateway Protocol, a type of routing protocol used outside of a network for internetwork, not to be confused with the deprecated protocol by the same name
BGP	Border Gateway Protocol, a routing protocol used for large-scale, internetworking applications
RIP	Routing Information Protocol, a distance-vector routing protocol
OSPF	Open Shortest Path First, a link-state routing protocol
AS	Autonomous System, a value used by BGP to group routes

Routing

Typically, routers store a table of the possible routes for an IP packet to take. These tables are usually a combination of directly connected routes and routes that have been statically set to point at another gateway which is directly connected. An example routing table is below for reference:

Route	Next Hop	Cost
10.0.0.0/16	Directly Connected on interface eth0	0
10.1.0.0/16	Directly Connected on interface eth1	0
10.2.0.0/16	10.1.25.4	10

In this scenario, a packet from 10.0.2.45 destined for 10.2.55.4 would be forwarded to the router at 10.1.25.4, which is directly available to the current router.

On larger and more complex networks, manually maintaining these routing tables becomes tedious, especially in complex network setups with multiple possible routes of varying cost. The solution to this problem is to use routing protocols, which automatically distribute routes and calculate cost to optimize routing.

Routing Protocols

The most basic of routing protocols is the distance-vector Routing Information Protocol, which periodically broadcasts the routes onto the specified broadcast domain, listening for other routers to share their routes, and forwarding received routes onto its other broadcast domains (in the process incrementing the cost). Notably, early versions of RIP predate Variable-Length Subnet Masks (VLSM), as they did not carry a subnet mask and instead used classful networking. A more powerful and complex alternative is Open Shortest Path First (OSPF). Unlike RIP and its newer alternatives, OSPF only sends updates when there is a change in the network, maintaining an internal topology map, and distributing limited updates to confirm that the router is still online. OSPF is therefore a link-state protocol, which calculates its cost metric based not just on the hop count but also the capacity of a particular link.

BGP is a distance-path protocol, which tracks more than just the hop count but does not attempt to maintain an internal topology map. Rather than using OSPF "areas", which group together routes to build an internal map, BGP makes use of Autonomous Systems (AS) numbers (or ASNs for short). BGP routing tables therefore contain ASNs, presuming that if a router can reach one network which is a part of that ASN, it can reach the rest as well. BGP routers only forward on the shortest routes it knows to a destination, but it can maintain multiple routes to a destination for fault tolerance.

BGP supports carrying routes of many types, including both classless and classful networks, and it even supports single IP addresses where the address is not a network or broadcast address. Since its creation in 1989, BGP has undergone 3 further revisions, adding support for AS identification, connection termination when two routers attempt to establish a TCP session with each other at the same time, and CIDR and aggregation support.

BGP Protocol

BGP (RFC 1771) uses TCP port 179, unlike most other routing protocols, which either run on top of IP directly or broadcast using UDP. With BGP, the peer addresses area already known, so TCP connections can be initiated directly. BGP packets use the following format:

Marker	Length	Type	Data
16 bytes	2 bytes	1 byte	0 - 4077 bytes

The message type can be one of either open (1), update (2), notification (3), or keepalive (4), or a newer message type defined in later RFCs. Each message type has a different format, stored in the data field.

Open

The open message is sent after the TCP connection is opened, to describe the capabilities of the client.

Version	ASN	Hold Time	Identifier	Parameter Length	Optional Parameters
1 bytes	2 bytes	2 bytes	4 bytes	1 byte	0 - 255 bytes

The BGP version nowadays should be 4. Next, the ASN of the sender identifies who is introducing the routes, and the hold time describes how long the BGP (not TCP) session should be kept alive. The hold time must be at least 3 seconds, the lowest of the hold times between the sender and receiver will be used, and if the time is set to 0, the connection will remain open indefinitely. The identifier is one of the sender's IP addresses, and must remain the same for all BGP sessions. Next, the parameter length specifies the size, in bytes, of the optional parameters field. The optional parameters field, in turn, contains options in the following format:

Parameter Identifier	Value
1 byte	1 byte

Once an open message has been accepted by the receiver, the two routers will exchange keepalive messages and send the full routing table using update messages, as configured. Once complete, only keepalive messages and incremental updates will be sent.

Update

Update messages contain routes and are used to both transfer the entire routing table from one device to another, and to send incremental updates to that table.

UR Length	Withdrawn Routes	PA Length	Path attributes	NLRI
2 bytes	0 - 65535 bytes	2 bytes	0 - 65535 bytes	Variable

The unfeasible routes (UR) length field stores the length of the withdrawn routes field. The withdrawn routes come in the form of a prefix length field, and enough bytes to store the prefix. The path attributes (PA) fields function similarly, though the format for each path attribute differs. The attributes are made up of a byte containing the flags for the attribute, followed by the attribute type. The flag bits are as follows:

• Optional (the most significant bit): 0 states that the attribute is well-known and supported by all routes, 1 indicates it is optional
• Transitive: 0 states that the attribute is nontransitive, 1 states it is well-known and transitive
• Partial: 0 states that the attribute is nontransitive, well-known or complete, 1 states that the attribute is partial and likely unprocessed by the source router
• Extended: 0 states that the attribute length field is 1 byte, 1 means it is 2 bytes

The attribute types are (from 1-5):

• Origin
• AS path
• Next hop
• Multi Exit Discriminator
• Local Preference

The path attributes contain information which is by the receiving router to decide which routes are most viable when multiple are received for the same destination. The Network Layer Reachability Information (NLRI) field is of variable length, and occupies the remaining space in the BGP message. It is a list of prefixes in the same format as the withdrawn routes field.

Notification

The notification message type is sent when a fatal error occurs, and is used to tear down the BGP session.

Error Code	Error Subcode	Optional Data
1 byte	1 byte	Variable

Keepalive

The keepalive message is used to maintain the BGP session and indicate the sending router is still up, and consists of a BGP message header with a type of 4, and no contents.

Propagation

Routes are propagated using the following steps:

• Upon receiving a new route update message, the router checks if it is allowed by filters and then accepts it
• The route is inserted into the BGP routing table
• If the new route is better than an existing alternative, it will replace the old route
• If the new route is worse, it is dropped
• The router sends a BGP withdrawal for the old route to all of its neighbors
• The router sends the new route to its neighbors

Due to the quirks of BGP route filtering, it's possible that a downstream router might accept the withdrawal for an existing route but reject a better alternative.

Path Selection

BGP considers multiple factors when selecting the "best" route. These metrics are typically vendor- and configuration-dependent, so some may be considered in certain scenarios while others may not.

Metric	Description
Local Preference	A vendor-specific metric, BGP will select the route with the highest local preference, which is used to force route selection in intra-AS propagation
AS Path	BGP maintains a list of AS's that exist between the source and destination AS, and it uses this to avoid routing loops, pick routes with the fewest hops, and select routes based on the presence of a preferred transiting AS
Multi Exit Discriminator	Typically used as a last-resort when the cost of two routes is otherwise equal, the MED is used to indicate when a specific link is preferred, for example due to capacity
Communities	Communicated in the format <ASN>:<NUMBER>, where the number is a value that is known to have some meaning by that AS, this is rarely used for route selection but can be used to trigger other actions

The MED differs from the local preference in that the lowest MED is preferred, and it stores the cumulative results from each hop, for example containing the total cost of the route.

The nature of BGP's complex collection of metrics is that it can be customized heavily to fit a particular environment. From the [BGP BOOK]:

If the route is learned from a BGP speaker in a neighboring autonomous system, then the degree of preference shall be computed based on preconfigured policy information. The exact nature of this policy information and the computation involved is a local matter.

Typically vendors simply allow the administrator to tweak the importance of the available metrics, rather than adding complex logic to perform route selection, so some of the power of BGP is lost. In the case of a tie between two or more routes, they are whittled down by:

• Selecting the route with the lowest MED (if MED is in use)
• Selecting the route with the lowest cost for the next hop address, as set by an IGP or manually
• Selecting the route with the lowest IP address in the identifier field, preferring external BGP peers to internal ones

Multiprotocol Support

BGP originally was designed to be used with IPv4, but the introduction of IPv6 necessitated a change to support it without completely replacing BGP. Current versions of BGP can support multiprotocol extensions, referred to as MBGP or BGP4+, which allows for the NLRI field to be dynamically defined by specifying the protocol type with an extension. The extension is also designed to support other address families like E.164 (phone numbers).

AFI	SAFI	NH length	Next hop	SNPAs	SNPA	NLRI
2 bytes	1 byte	1 byte	variable	1 byte	variable	variable

The AFI, or Address Family Indicator, specifies the address type, like IPv6 or E.164. The Subsequent Address Family Information (SAFI), expands on this by specifying whether the prefixes it will originate are (in the IP world) multicast or unicast. It's important to know that while the standard is for multi-protocol extensions, the extensions actually carry information about the addressing, not any protocols. While IPv4 and IPv6 addresses are tied to a protocol, other addresses like E.164 aren't tied to a specific protocol. Next come the next hop length and value fields (allowing for variable-length next hops), plus the Sub-Network Point of Attachment count and values. The SNPAs are additional information that might be needed by a protocol for routing, these can be thought of as intermediary MAC addresses required in addition to a next hop IP address. Each SNPA has a 4-bit length field followed by the value, a rather unclean (though functional) solution. The NLRI field maintains the same format as the normal update message.