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), which uniquely identifies each network on the Internet. This number is allocated to an autonomous system (AS) and plays a crucial role in Border Gateway Protocol (BGP) routing. BGP enables network operators, including ISPs, to exchange routing information with other networks worldwide. Understanding BGP is essential for professionals working in ISPs or large organizations connected to multiple ISPs, as it governs how data travels across the internet. Tools like AS information lookup services can help identify the ASN associated with your ISP.
Unlike other commonly used routing protocols such as RIP, OSPF, and EIGRP, which are classified as Interior Gateway Protocols (IGPs), BGP operates as an External Gateway Protocol (EGP). IGPs prioritize finding the shortest path to a destination based on metrics like hop count, cost, or delay, making them suitable for routing within a single AS. However, these protocols lack the scalability required for the broader internet.
BGP, on the other hand, is designed for routing between autonomous systems on a global scale. It focuses more on controlling traffic paths rather than simply choosing the shortest route. This capability is crucial for managing traffic across vast, complex networks like the Internet.
If you’re curious about how internet traffic flows from New Zealand to destinations in Western Europe or North America, tools such as BGP Looking Glass servers provide a view of the internet routing table, providing a real-time trace of these paths. In summary, BGP is a cornerstone of internet routing, essential for ensuring efficient and flexible data exchange between diverse networks.
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:
Category | Description |
---|---|
Well-known Mandatory | Supported by all implementations of BGP, and are always included in every BGP update |
Well-known Discretionary | Supported by all BGP implementations, and are optionally included in BGP updates |
Optional Transitive | 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. |
Optional Non-Transitive | 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.
Priority | Attribute | The Attribute Prefers... |
---|---|---|
1 | Weight | the path with the highest weight. The default value is 0 for all routes not originated by the local router. |
2 | Local Preference | the path with the highest local preference. The default value is 100. |
3 | Locally Originated | the path that the local router originated. |
4 | AS path length | the path with the shortest AS path length. |
5 | Origin code | the lowest origin code. |
6 | MED | the path with the lowest MED. |
7 | eBGP path over iBGP path | eBGP (external BGP) over iBGP (internal BGP) paths. |
8 | Shortest IGP path to BGP next-hop | the path within the AS with the lowest IGP metric to the BGP next hop. |
9 | Oldest path | the path that was received first. |
10 | Router ID | the path with the lowest BGP neighbor router ID. |
11 | 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.
BGP FAQs
How does BGP use the AS-path and next-hop attributes?
In the BGP, the AS is an autonomous system, which means an address space. For routing, the AS signifies a router and the AS-path attribute lists all of the routers that a connection passed through. The next-hop attribute is the neighboring router that leads to the path list.
What can affect the BGP selection more than the attributes?
The BGP system calculates a score for each path based on its attributes. The system compares the score of each path to a given destination and selects the path with the highest score. It will ignore paths where the next hop device is unavailable or if the path is marked as not synchronized.
What attributes are exported in BGP?
There are three attributes that are mandatory and have to be included in the export of a path. These are: Origin, AS Path, and Next Hop.