The Border Gateway Protocol (BGP) is responsible for finding the best route for data transmission between two endpoints connected across the internet. In this article, we dive deep into its inner workings to answer a common network engineering question: How do BGP attributes work? Before we launch into an explanation, let’s first review a few fundamental concepts that we’ll reference throughout this article.
Introduction
The Border Gateway Protocol (BGP) is responsible for finding the best route for data transmission between two endpoints connected across the internet. In this article, we dive deep into its inner workings to answer a common network engineering question: How do BGP attributes work?
Before we launch into an explanation, let’s first review a few fundamental concepts that we’ll reference throughout this article.
Definitions for Context
- Autonomous System: An Autonomous System (AS) represents a set of IP prefixes that belong to a network and are managed by a single organization. Each AS is assigned an Autonomous System Number (ASN), which is unique to the network.
- Internal and External BGP: Border Gateway Protocol (BGP) is the protocol that runs the internet. It is a routing protocol that exchanges routing and reachability information between AS on the internet. Small enterprises run BGP only on the edge where they are connected to their ISPs (one or more ISPs and each ISP is connected to at least one router for redundancy purposes). Large enterprises utilize internal BGPs to facilitate communication within a single AS.
- Connection to peer AS: An enterprise or any given organization that owns an AS can be connected to one or more upstreams. To each upstream, there can be one or more connections and these connections can be all to the same device or spread among multiple devices.
BGP Attribute Categories
There are four categories of BGP attributes:
- Well-known mandatory:Recognized by all BGP peers, passed to all peers, and present in all Update messages. Well-known mandatory attributes include:- Next-hop- Origin- AS PATH
- Well-known discretionary:Recognized by all routers, passed to all peers, and optionally included in the Update message. Well-known discretionary attributes include:- Local Preference- Atomic Aggregate
- Optional transitive:Possibly recognized by BGP routers and passed to BGP peers. Optional transitive attributes are marked as partial when not recognized. Optional transitive attributes include:- Aggregator- Community
- Optional non-transitive:Possibly recognized by BGP routers but not passed to peers. Optional non-transitive attributes include:- Multi-exit discriminator (MED)- Originator ID- Cluster-ID
Each networking equipment vendor can create their own BGP attributes, which are understood by their routers. However, attributes that are not understood go ignored. That said, it is unlikely that a network will be running BGP without Cisco routers (there might be enterprises that do not use Cisco, but their number is very small).
While on the topic of vendor-specific attributes, it’s worth mentioning an important but proprietary Cisco attribute which we will reference later in this article: Weight. Weight has local significance for preferred route selection and a higher value is favored.
{{banner-3="/design/banners"}}
BGP Update Message
An Update message is used to transfer routing information between BGP neighbours, making the advertisement and withdrawal of routes possible. The following are the most important BGP fields for Update messages:
- Total Path Attribute Length: Indicates the total length of the Path Attributes field.
- Path Attributes: Follows the format of <type, length,="" value=""> and contains the following two subfields:</type,>
- Attribute Flags: Defines if the attribute is well-known, optional, transitive, or non-transitive. States if the information from the Update is partial or complete.
- Attribute Type Code: Identifies the attribute (for instance, the ORIGIN attribute has the type code 1).
BGP Best Path Selection Algorithm
To decide which route is the best, each BGP router has a “best path selection” algorithm, where the information from two similar paths are compared. This is because it is not unusual for a BGP speaker to receive the same route from multiple peers. In fact, this is quite normal when you have multiple upstreams or peers.
Before we cover how the BGP best path selection algorithm works, however, it’s important to know that not all of the received BGP routes are candidates for being selected as the best route. There are many reasons for this, a common one being that the next-hop advertised as an attribute for the route is inaccessible.
Now, let’s take a look at the factors that govern selecting a best route candidate (and the order they are considered in) using the BGP selection algorithm on a Cisco router:
- A path with the highest Weight attribute is preferred (other vendors ignore this attribute).
- A path with the highest “local preference” is preferred (usually set to 100).
- A path that was locally originated using “network” or “aggregate” command or using redistribution from IGP is preferred.
- A path with the shortest AS Path is preferred (skippable via router configuration).
- A path with the lowest origin type is preferred. Origin types are preferred in this order:- IGP- EGP- Incomplete
- A path with the lowest MED is preferred. By default, the MED is compared only if the neighbour AS is the same for the paths that are compared (this is configurable). There are multiple commands related to how and when to treat the MED value of the paths, which, due to its complexity, is outside the scope of this article.
- A path that is an External BGP path is preferred (versus internal).
- A path with the lowest IGP metric for BGP next-hop is preferred. At this point, if multipath is configured, the Router installs the routes. If not, the algorithm continues to the next step.
- If both routes are external, the oldest route is preferred. This step is skipped if the BGP is configured to compare the router-ID or the paths have the same router-ID.
- A path with the lowest router ID is preferred. The router-ID can be manually set or it can be set automatically using the highest IP address configured (first the loopback interfaces are considered and then the physical interfaces).
- A path with the shortest cluster list length is preferred. This step is applicable only in a route reflector environment. If this is not the case, this step is skipped.
- A path from the lowest neighbour address is preferred. At this point, at least one route should be selected as the best route (or multiple, after step 8).
{{banner-7="/design/banners"}}
Examples
Let’s look at some examples where a router compares various BGP attributes to select the best route.
Weight
In the scenario illustrated below, R1 sets the Weight value for prefixes coming from R12 (from AS 12 - 200) and leaves the attribute to the default value for the prefixes coming from R11 from AS 11.
When R1 runs the best path selection algorithm (because it is a Cisco device), it compares the Weight value locally set for the prefixes. If one of the paths has a higher value than the others, it is selected and the algorithm stops.
Considering the following example, R1 should prefer the path received from R12:
Router Input
Local Preference
Local preference is a well-known discretionary attribute. In other words, it is recognized by all the routers if it is present in the update.
In this scenario, R1 sets the Weight to 200 for the prefixes from every BGP peer. If the Weight attribute is equal, then the best path selection algorithm compares the Local preference attribute value.
Considering the following scenario:
R1 chooses the path from R11 because the Local preference for the routes coming from R11 is set to 110, which is higher than the default value, 100, set for the routes coming from R12.
Router Input
AS Path
The AS_PATH attribute is a well-known mandatory attribute and represents the list of the AS the prefix has crossed. Each AS is added in front of the current AS PATH.
In the following example, the route received by R1 from R11 has the AS_PATH 11 111 and the route received from R12 has the AS_PATH 12 22 111.
Because a shorter AS_PATH is better than a longer AS_PATH, if all the previous steps of the algorithm could not select the best route, the route with the shortest AS_PATH is selected as the best route.
Router Input
Origin
At step 5 of the best path selection algorithm, a router compares the value of the Origin attribute. The Origin attribute has three possible values (or codes):
- i - IGP
- e - EGP
- ? - incomplete
In the following scenario, R1 sees the routes from R11 with an origin of “IGP” and the routes from R12 with an origin of “incomplete.” Because all the previous steps of the best path selection algorithm could not select the best path (due to the fact that all the values were equal), the Origin values must be compared.
Since Origin IGP is better than Origin Incomplete, the route from R11 is chosen as the best route.
Router Input
Multi-exit Discriminator (MED)
MED is an optional non-transitive BGP attribute. It is exchanged between the AS, propagated to all the routers in the AS, but not advertised to any other AS.
In the following scenario, R111 advertises the route to R11 and R12 routers with different MED values. R11 and R12 both advertise the route to R1, which has to run the BGP best path selection algorithm.
Considering that all the previous steps could not be used to select the best path, MED is evaluated and the path with the lowest MED value is chosen.
From R1, it can be seen that the routes received from R11 and R12 are keeping the MED values set by R111 and the route chosen is the one with the lowest MED.
Router Input
Community
A BGP community is an optional transitive BGP attribute that can traverse from AS to AS. The BGP communities can be set, removed, or modified selectively (e.g., you can add additional communities). BGP communities can be used to tag routes with the purpose of enforcing routing policies. To give an example, when a route received has a specific BGP community attached to it, the router can perform various operations on other BGP attributes of that route.
There are four well known BGP communities:
- Internet: Prefix can be advertised to all BGP neighbors.
- No-Advertise: Prefix should not be advertised to any BGP neighbors.
- No-Export: Prefix should not be advertised to any External BGP neighbors.
- Local-AS: Prefix should not be advertised outside of the sub-AS.
While a BGP community is not a BGP attribute that is evaluated in order to select the best route, it allows the operator to influence the result of the BGP best path selection algorithm.
In the following scenario, R11 and R12 set a specific Local Preference value to routes, based on the community that is attached when they are sent by R111. R1 receives the same route twice and must run the BGP best path selection algorithm.
So now, R1 must choose between a path with LOCAL_PREF of 110 and a path with LOCAL_PREF of 105.
Router Input
As mentioned, the algorithm does not evaluate the community. However it evaluates one of the attributes that was changed due to matching a specific community.
Summary
Now you know how a router evaluates the BGP attributes found in the UPDATE messages to select the best path to be installed in the routing table. Although vendors can define their own BGP attribution methods, most routers are made by Cisco and thus use Cisco’s best path selection algorithm.
Learn about our approach to BGP monitoring with Network Insights.