Border Gateway Protocol (BGP) is the routing protocol of the internet, used to exchange routing and reachability information among autonomous systems (a collection of networks under a single administrative domain) on the internet.
Internet Service Providers (ISPs) are required to have an officially registered autonomous system number (ASN). These numbers are important because they uniquely identify each network on the internet. A unique autonomous system number is allocated to each autonomous system (AS) for use in BGP routing. This allows network operators (such as ISPs) across the world to exchange routing information with other network operators. BGP is an important concept to grasp if you work for an ISP or a large company that is connected to two or more ISPs. You can use this AS information lookup tool to find out the AS number for your ISP.
BGP differs from other popular routing protocols such as RIP, OSPF, and EIGRP. Those three routing protocols have one thing in common: they are all classified as Interior Gateway Protocol (IGP), and focus on finding the shortest path (either in terms of hop count, cost, or delay) to destinations. We only use them within autonomous systems but not for networks as large as the internet, because they lack the required scalability. When it comes to routing through the internet or routing between different autonomous systems, being able to manipulate traffic paths is far more important than finding the shortest path. This is where the External Gateway Protocol (EGP) comes into play. There is only one EGP in use on the internet today – BGP. If for instance, you wanted to know the path internet traffic from say New Zealand takes to get to someone in Western Europe or North America, it’s possible to see it using a BGP Looking Glass (routers that have public view access to the internet routing table).
Unlike IGPs, BGP utilizes a set of attributes to determine the best path for each destination. These attributes can be subdivided into four distinct categories. The table below is a summary of the various subdivisions:
Supported by all implementations of BGP, and are always included in every BGP update
Supported by all BGP implementations, and are optionally included in BGP updates
May not be supported by all implementations of BGP. Transitive indicates that a non-compliant BGP router will forward the unsupported attribute unchanged when sending updates to peers.
May not be supported by all implementations of BGP. Non-Transitive indicates that a non-compliant BGP router will strip out the unsupported attribute when sending updates to peers.
Table 1.0 The four distinct categories of BGP attributes
In this article, we’ll explain how BGP selects the best path to destinations based on a list of attributes.
BGP Best Path Selection Algorithm
BGP path selection is done through the best path algorithm. If BGP contains multiple routes to the same destination, it successively analyzes or compares them to determine which path is the most efficient to take. The attributes are compared in the specific order shown in the table below.
The Attribute Prefers...
the path with the highest weight. The default value is 0 for all routes not originated by the local router.
the path with the highest local preference. The default value is 100.
the path that the local router originated.
AS path length
the path with the shortest AS path length.
the lowest origin code.
the path with the lowest MED.
eBGP path over iBGP path
eBGP (external BGP) over iBGP (internal BGP) paths.
Shortest IGP path to BGP next-hop
the path within the AS with the lowest IGP metric to the BGP next hop.
the path that was received first.
the path with the lowest BGP neighbor router ID.
Neighbor IP address
the path with the lowest neighbor IP address.
Table 2.0 BGP best path selection algorithm
Which path does the BGP take? Well, it starts with the Weight attribute which is at the very top of the BGP attributes list as shown in Table 2.0 above. If one path has a better weight, the BGP selects that path as the best path. If the weight is equal, it moves down to the next attribute Local Preference. If one path has a better local preference, it selects that path as the best path. If the local preference is equal, it moves down to the next attribute on the list, until we have a tiebreaker to select the best path. If all paths have the same BGP attributes, then we end up with the last attribute Neighbor IP Address. We will go through each attribute in detail.
Weight: The BGP attribute Weight is the first on the list in terms of the order priority. The Weight attribute is applied to inbound routes, where decisions about the best exit (outbound) path are made. Here are the key points you need to know about Weight:
- Weight is a Cisco-proprietary attribute, therefore other router vendors don’t support it
- It’s not passed between BGP neighbors
- It’s only locally significant on the router
- The path with the highest weight is preferred
A route originating on the local router will be assigned a weight of 32768, by default. All other routes will be assigned a weight of 0, by default. Using the diagram in Figure 1.0, you can define a weight value for all routes advertised from a specific neighbor using the following command:
LOS_Router(config)# router bgp 500 LOS_Router(config)# neighbor 10.10.1.2 weight 200
Local Preference: The BGP attribute Local Preference is the second on the list in terms of the order priority; and it can be used to inform internal BGP routers how to exit the AS if multiple paths exist. It is applied to inbound external routes, where decisions about the best exit (outbound) path for an autonomous system are made. Here are some key points you need to know about Local Preference:
- Local preference is sent to all internal BGP routers in your AS when sending updates
- It’s not passed between external BGP neighbors
- Local preference is a well-known discretionary BGP attribute, therefore it must be recognized by all BGP routers
- Its presence in a BGP update is optional
- The default value is 100
- The path with the highest local preference is preferred
Local Preference is a 32-bit number ranging from 0 to 4294967295. Using the diagram in Figure 1.0, you can define a Local Preference value for all inbound external routes, on a global basis for BGP using the following command:
NYC_Router(config)# router bgp 500 NYC_Router(config-router)# bgp default local-preference 200 ATL_Router(config)# router bgp 500 ATL_Router(config-router)# bgp default local-preference 300
The implication of the above configuration is that NYC_Router and ATL_Router will include the Local Preference attribute in updates to internal BGP neighbors. Because ATL_Router is the path with the highest local preference, LOS_Router and NYC_Router will now prefer it as the route to reach any destination outside the local AS.
Locally Originated: The BGP attribute Locally Originated just as the name implies, prefer the path that the local router originated. A BGP router will prefer routes that it installed into BGP itself, over a route that another router installed in BGP.
AS-Path Length: The BGP attribute AS-Path is the fourth BGP attribute; and it’s usually applied to outbound (exit) routes, where decisions about the best inbound (entry) path are made. Here are some key points you need to know about AS-Path:
- BGP prefers the shortest AS path to get to a destination
- Prepending adds to the existing AS-Path, resulting in a longer AS-Path
- You can influence routing by using AS path prepending to make routes less desirable for inbound traffic
If you want to get traffic to enter an AS through a preferred path, you can add the specific AS number multiple times, so the AS-Path becomes longer and of course a less desirable route for inbound traffic. This can be accomplished using the following configuration:
NYC_Router(config)# access-list 5 permit 10.30.0.0 0.0.15.255 NYC_Router(config)# route-map ASPREPEND permit 10 NYC_Router(config-route-map)# match ip address 5 NYC_Router(config-route-map)# set as-path prepend 200 200 NYC_Router(config-route-map)# route-map ASPREPEND permit 20 NYC_Router(config)# router bgp 500 NYC_Router(config-router)# neighbor 192.168.6.2 route-map ASPREPEND out
The implication of the above configuration is that the MAN_Router will prefer the path through ATL_Router to reach the network 10.30.1.1/20 because the path through NYC_Router has the longest AS-Path.
Origin Code: The BGP attribute Origin Code identifies the source of the route. There are three origin codes that the BGP table can show:
- IGP: If the BGP table shows IGP, it indicates that the route originated from an interior gateway protocol (such as RIP or OSPF), which means that you advertised the network yourself in BGP, using the BGP network command. The origin code of “i” is most preferred.
- EGP: If the BGP table shows EGP, it indicates that the route originated from an external gateway protocol. However, EGP is an outdated routing protocol that is no longer in use.
- Incomplete: If the BGP table shows the incomplete or unknown origin, it means that you have redistributed something into BGP (either from connected, static, or IGP routes). An origin code of “?” is the least preferred.
The origin code is usually listed at the end of each line in the BGP routing table such as the one shown in the output below:
NYC_Router# show ip bgp Network Next Hop Metric LocPrf Weight Path *> 10.30.0.0 10.10.1.1 0 0 0 i *> 172.20.1.0 192.168.6.2 0 100 0 700 ?
From the routing table above, the “i” at the end of the first entry indicates that the 10.30.0.0 network originated via an IGP, perhaps with the BGP network command; while the “?” at the end of the last entry indicates the network 172.20.1.0 was probably redistributed into BGP in AS 700.
MultiExit Discriminator (MED): The BGP attribute MED is exchanged between AS’s, and you can use it to inform other AS’s of the path they should take to enter your AS. Here are some key points you need to know about MED:
- MED is propagated to all routers within the neighbor AS, but not passed along any other AS’s
- It can be used to inform your neighbors how they should enter your AS
- It is exchanged between AS’s
- The MED is identified as the BGP metric on the routing table
- The lowest MED (metric) is the preferred path
- The default MED value is 0
In our diagram in Figure 1.0, there are two entry points into AS 500. To force AS 700 to prefer the path through ATL_Router to reach the network 10.30.0.0/20, the set metric command can be used with a route-map as shown in the configuration below:
NYC_Router(config)# access-list 5 permit 10.30.0.0 0.0.15.255 NYC_Router(config)# route-map SETMED permit 10 NYC_Router(config-route-map)# match ip address 5 NYC_Router(config-route-map)# set metric 200 NYC_Router(config)# router bgp 500 NYC_Router(config-router)# neighbor 192.168.6.2 route-map SETMED out
When you examine the BGP routing table on MAN_Router as shown in the output below, you’ll see that the route from NYC_Router now has a higher metric, thereby making it a less desirable path, and forcing AS 700 to go through ATL_Router to reach the network 10.30.0.0/20
MAN_Router# show ip bgp Network Next Hop Metric LocPrf Weight Path * 10.30.0.0 192.168.5.1 200 100 0 100 i *> 10.30.0.0 192.168.6.1 0 100 0 100 i
BGP uses two MED commands bgp deterministic-med and bgp always-compare-med to lessen potential sub-optimal routing selection issues that may arise as a result of the order of comparison of multiple routes to the same destination in the BGP routing table. Both commands are disabled by default, which means that the MED value is by default not compared between paths from different AS’s.
You can enable both commands on all routers within the AS using the following configuration:
Enable bgp deterministic-med LON_Router(config)# router bgp 500 LON_Router(config-router)# bgp deterministic-med Enable bgp always-compare-med LON_Router(config)# router bgp 500 LON_Router(config-router)# bgp always-compare-med
The above configuration forces the MED value to be compared when multiple routes to the same network are received via multiple routers, regardless of the order of routes in the BGP routing table. The key difference is that bgp deterministic-med involves routers from the same AS, while bgp always-compare-med involves routers from different AS’s.
eBGP path over iBGP Path: The BGP attribute eBGP path over the iBGP path is similar to the Origin Code attribute. The Internal BGP (iBGP) protocol runs within the same AS, whereas the external BGP (eBGP) protocol operates between AS’s. The best path algorithm prefers eBGP over iBGP.
Shortest IGP path to BGP Next Hop: With this criterion, the best path selection algorithm prefers the path within the autonomous system with the lowest IGP value to the BGP next hop.
Oldest Path: The BGP attribute Oldest Path differentiates between external paths based on when they were received. The best path selection algorithm prefers the path that was received first (the path that is older), hence the term, oldest path.
Router ID: The BGP attribute Router ID refers to the IP address with the highest router value. If you have a loopback interface, then the IP address on the loopback will be used. The router ID can also be manually configured. With these criteria, BGP’s best path selection algorithm prefers the path that originates from the BGP router with the lowest router ID.
If the router IDs are similar, the best path selection algorithm then differentiates based on the cluster list. The path with the lowest cluster list length is preferred.
Neighbor IP Address: If at this point the BGP best path selection algorithm fails to select the best path based on the fact that all paths have the same BGP attributes, then we end up with the last attribute Neighbor IP Address. With this criterion, the path with the lowest neighbor IP address eventually becomes the tiebreaker.