What is the BGP Best Path Selection?

BGP, or Border Gateway Protocol, is a crucial exterior gateway protocol (EGP) that plays a central role in how data is routed across the internet. One of its key functions is the BGP Best Path Selection Algorithm, which helps determine the most efficient route for forwarding traffic. This is particularly important because BGP routers often encounter multiple paths leading to the same destination prefix.

Unlike traditional interior gateway protocols (IGPs) such as EIGRP and OSPF, which typically use a shortest path selection method based on metrics, BGP does not rely on classic additive metrics. This is mainly due to the multi-hop nature of BGP peering. As a result, BGP employs a more complex procedure for selecting the best path rather than simply opting for the shortest one.

In this guide, we will learn and understand what is BGP Best Path Selection? How does it work and all the attributes like weight, network origin, local preference etc. As a part of our Cisco certification training material, this article also demonstrates the practical configuration of weight attribute on Cisco routers.

What is BGP Best Path Selection Algorithm?

The BGP Best Path Selection Algorithm, a crucial component of the Border Gateway Protocol (BGP), was developed in the late 1980s to manage routing between autonomous systems (AS) as the internet grew. Its primary purpose is to choose the most efficient route for data packets among multiple available paths, ensuring optimal traffic flow and network performance.

The algorithm operates by evaluating various attributes, such as weight, local preference, AS path length, origin type, and Multi-Exit Discriminator (MED), in a specific order to systematically determine and install the best route into the routing table.

By prioritizing routes based on these criteria, BGP can effectively handle complex routing scenarios, accommodate increasing numbers of routes, and adapt to diverse network policies, maintaining stability and efficient resource utilization in large networks.

CCNP Online TrainingLearn more about these concepts in our CCNP training live class.Explore course

Properties of BGP Best Path Selection Algorithm

The purpose of the BGP path selection algorithm procedure is to select optimal paths based on administrative preferences while maintaining the following properties:

1. BGP Routing Loop Detection:

The BGP best path selection should form a loop-free topology. It implements this by filtering prefixes with the AS number matching the local AS in the AS_PATH attributes.

2. BGP Deterministic Path Selection:

All BGP routers under the same conditions (such as all IBGP speakers configured similarly) must select the same best paths.

3. BGP Routing Table Stability:

The best path selection in BGP should not result in constant oscillating route insertion and removals.

4. Information Flooding Minimization:

A BGP speaker only sends the best paths to its neighbors when bgp states are established. This significantly reduces the amount of update flooding, saving bandwidth and CPU cycles. 

Before we start with BGP path selection criteria process, recall that every BGP prefix has a set of attributes associated with it. The procedure uses those attributes when looking for optimal paths. 

How does BGP Best Path Selection Algorithm Work?

The BGP Best Path Selection Algorithm works by evaluating multiple attributes associated with each route to determine the optimal path for traffic forwarding. When a BGP router receives multiple paths to the same destination prefix, it compares these paths based on a predefined order of attributes, including weight, local preference, AS path length, origin type, and others.

If paths are tied at any point in the evaluation, the algorithm continues to the next attribute until a single best path is identified. Additionally, BGP implements Prefix Exclusion Criteria to discard certain paths from consideration.

Paths that are marked as "not synchronized", or paths originating from an eBGP neighbor when the local AS is not reachable are excluded from the selection process. This ensures that only viable routes are evaluated for optimal path selection.

Prefix Exclusion Criteria for Best Path Selection in BGP

Before the procedure runs for finding the best path, BGP best path selection process excludes some prefixes based on the following criteria:

1. No valid next-hop

This is the most common cause for the prefix being ignored by the selection process. BGP prefixes carry their next-hop as a separate attribute (NEXT_HOP attribute). If the next-hop address is NOT reachable via IGP, the prefix is marked as invalid and is not considered.

This usually happens with eBGP-learned prefixes when you forget to enter the command next-hop-self or advertise the link subnet into IGP/BGP.

2. BGP Synchronization

When it enables and the prefix is not in the IGP table. The best path selection in BGP process will ignore this prefix. This is a legacy restriction, but you may occasionally run into it.

3. AS_PATH Loop

Prefixes from the neighbor that has the local AS number in the AS_PATH attribute are dropped. This is the well-known BGP loop detection mechanism.

All eligible paths are then sorted, and prefixes for the same destination (subnet/mask) are grouped together (the actual implementation may differ, though, as a result of various optimizations). 

BGP Best Path Selection Attributes

The BGP Best Path Selection Algorithm uses a specific order of attributes to determine the optimal route for traffic forwarding. The attributes, in order of priority, are explained in the table below:

Configure Weight Attribute on Cisco Routers

Here we will learn how to change weight attribute on Cisco Routers. Weight attribute is of the highest priority in BGP best path selection algorithm. The diagram below shows the topology setup on which we will be working. To perform the practical, you can join UniNets CCNP virtual lab, which already has this setup.

In this practical example we will be configuring the R7 (router 7) and achieve the following:

● Traffic from AS 300 going to prefixes originated in AS 54 exits toward R3

● Traffic from AS 300 going to prefixes originated in AS 254 exits toward R6 

Before everything else, BGP prefers paths with the highest weight value. Weight is Cisco-specific and is not transported along with BGP prefixes/updates.

This attribute is configured locally on the router, using the command neighbor weight , where the value can range from 0 to 65535.

As mentioned, higher-weight values are preferred, and the default weight is zero for learned prefixes. Thus, among two equal prefixes with different weights, the one with the highest weight is preferred.

This attribute is commonly used in scenarios where the local router has multiple uplinks, and you want to prefer one uplink over another. In addition to the neighbor command, the weight attribute could be set using inbound route-map associated with the neighbor, for example:

This method could be used to change specific prefix preference without affecting any other subnets learned from the same peer.

Remember that BGP weight attribute manipulations only affect the way that the traffic leaves the local router.

Notice that IOS routers assign the weight value of 32768 to all locally advertised prefixes—prefixes advertised using the network or aggregate-address commands or via route redistribution. This feature ensures that all locally originated prefixes are always preferred over the same prefixes learned from the peers. 

The solution for this task uses AS-PATH access-lists to match all prefixes from AS 54 and 254. The regular expressions to match all networks originated from AS 54 and 254, respectively, are 54$ and 254$ . R7 peers with R6 and R3, and we manipulate weight values as follows:

For prefixes originated from AS 254 and received from R6, we set the weight value to 1000. This makes R7 prefer paths to AS 254 via R6, as opposed to R3. 

For prefixes originate from AS 54 and received from R3, we set the weight value to 1000 as well. As a result, R7 prefers paths to AS 54 via R3, where it should prefer paths via R9 by default. Always remember to create a “permit” entry at the end of your route-maps, or you may unintentionally filter non-matching networks.

R7:

BGP Weight Attribute - Verification

Before you start any verification, use the command clear ip bgp * soft to force R7 to refresh the information learned from its peers. By default, when you apply any new policy it does not take effect unless the new updates are received/sent.

Because BGP does not use periodic updates, you may need to force an update manually. The command performs a “soft-reset”; it does not tear down BGP sessions but simply sends out BGP updates and requests route-refresh from the peers.

Compared to clear ip bgp * , it causes much less load on the router’s CPU and does not disrupt traffic routing:

Now let’s look through the BGP table in R7. Notice the use of regex-based filter _54$ to select only the prefixes originated in AS 54. Look at the prefixes received from R3, they are selected as “best” and marked with the “>” sign, and the weight assigned is 1000. The “losing” prefixes have the weight value of 0 (the default):

R7#show ip bgp regexp _54$

BGP table version is 36, local router ID is 150.1.7.7

Status codes: s suppressed, d damped, h history, * valid, > best, i - internal,

r RIB-failure, S Stale, m multipath, b backup-path, f RT-Filter,

x best-external, a additional-path, c RIB-compressed,

Origin codes: i - IGP, e - EGP, ? - incomplete

RPKI validation codes: V valid, I invalid, N Not found

   Network                          Next Hop                          Metric      LocPrf      Weight      Path

* 28.119.16.0/24              155.1.67.6                                                                     0      100 200 54 i

*                                          155.1.79.9                                                                      0     54 i

*>                                        155.1.37.3                                                               1000     200 54 i

* 28.119.17.0/24              155.1.67.6                                                                       0    100 200 54 i

*                                          155.1.79.9                                                                        0   54 i

*>                                        155.1.37.3                                                                1000   200 54 i

* 114.0.0.0                         155.1.67.6                                                                        0  100 200 54 i

*>                                        155.1.37.3                                                                 1000   200 54 i

*                                          155.1.79.9                                    0                                  0   54 i

----------------------------output snipped------------------------------

Repeat the same check with the prefixes originated in AS 254. Notice that now R6 is selected as the upstream peer to route to these subnets:

R7#show ip bgp regexp 254$

BGP table version is 36, local router ID is 150.1.7.7

Status codes: s suppressed, d damped, h history, * valid, > best, i - internal,

r RIB-failure, S Stale, m multipath, b backup-path, f RT-Filter,

x best-external, a additional-path, c RIB-compressed,

Origin codes: i - IGP, e - EGP, ? - incomplete

RPKI validation codes: V valid, I invalid, N Not found

Network                          Next Hop                          Metric      LocPrf      Weight      Path

*> 51.51.51.51/32         155.1.67.6                                                           1000         100 200 254 ?

*                                       155.1.37.3                                                                  0         200 254 ?

*> 192.10.1.0                 155.1.67.6                                                           1000         100 200 254 ?

*                                       155.1.37.3                                                                   0        200 254 ?

*> 205.90.31.0              155.1.67.6                                                             1000       100 200 254 ?

----------------------------output snipped------------------------------

BGP Best Path Selection Algorithm - Summing Up!!

In this guide, we learned that the BGP Best Path Selection Algorithm is essential for determining the optimal route for data transmission across networks. It evaluates multiple attributes, including weight, local preference, and AS path length, to identify the best path among several options.

The weight attribute, a Cisco-specific feature, is the first criterion considered; it ranges from 0 to 65535 and is not shared with other routers. By configuring the weight for specific neighbors or routes, network administrators can influence routing decisions effectively.

The best Path Selection Algorithm ensures efficient traffic management and stability within large networks. Understanding its working and configuration is crucial for optimizing BGP routing policies.

To learn more about BGP and its working check out our IT infrastructure courses.