Useful Articles

25/recent/ticker-posts

BGP Best Path Selection Criteria

BGP Best Path Selection Criteria

BGP Best Path Selection Criteria is mechanism in BGP that helps finding the best path to a destination network. While you configure BGP (Border Gateway Protocol) between two peers, both the peers go through the various BGP Neighbor Adjaceny States and exchange a few BGP Messages to form the BGP Adjacency. As the BGP neighborship is formed between the two routers, they exchange NLRI (Network Layer Reachability Information) information along with specific information related to BGP Attributes using BGP Update messages. The exchange NLRIs of the prefixes from the neighbors are first stored in each router's BGP database also known as the BGP table(show ip bgp), and BGP process calculates the best path to reach each destination using some rules known as the BGP Best Path Selection Algorithm.

Multiple paths might exist to reach a specific destination prefix and all the paths, either best or non best, are kept in the BGP table. As paths for the destination prefix/network are evaluated using BGP Route Selection Criteria, those determined not to be the best path are eliminated from the selection criteria but kept in the BGP table in case the best path becomes inaccessible. The best routes are used to form the routing table. BGP chooses only a single best path to reach a specific destination.

 

BGP Path Selection

BGP is not designed to perform load balancing and the paths are chosen because of policy, not based on bandwidth. The BGP best path selection algorithm eliminates any multiple paths until a single best path is left.

Before jumping to the BGP Best Path Selection Method, it is mandatory that next-hop for a particular destination should be reachable. Else, BGP will ignore the path in the calculation.
The following are the rules of the BGP Best Path Selection Criteria.

BGP Attributes play an important role in how BGP selects the best path. An administrator can also manipulate the default values of various BGP Attributes to influence the best path as per the network requirements.

1. Weight

Prefer the route with the highest Weight. Recall that the Weight is a Cisco proprietary Attribute and is local to the router only. Default Weight for local BGP routes is 32768 and Default Weight for BGP routes learned from other peers (internal or external) is zero.

2. Local Preference

If multiple routes have the same weight, prefer the route with the highest local preference. (Just to remind that the Local Preference is used within an AS.) Default Local Preference is 100.

3. Origin

If multiple routes have the same local preference, prefer the route that was originated by the local router. A locally originated route has a next hop of 0.0.0.0 in the BGP table. The Routes advertised in BGP using the Network or Redistribute command more preferred than the BGP routes sourced via the "aggregate-address" command.
 

4. AS-Path

If none of the routes were originated by the local router, prefer the route with the shortest AS-path. AS-Path check is ignored if the "bgp bestpath as-path ignore" command is configured.

5. Origin Code

If the AS-path length is the same, prefer the lowest-origin code (IGP < EGP < Incomplete). This step is further explained later this article with help of the lab simulation. Kindly note that that routes are redistributed from other routing protocols (example - RIP, OSPF, etc.) are installed with incomplete Origin code in the BGP table.

6. MED (Multi-Exit Discriminator)

If all origin codes are the same, prefer the path with the lowest MED. We must remember that the MED comparison is done only if the neighboring AS is the same for all routes considered unless the "bgp always-compare-med" router configuration command is enabled.
 
Kindly also note that the most recent Internet Engineering Task Force (IETF) decision about BGP MED assigns a value of infinity to a missing MED, making a route lacking the MED variable the least preferred. The default behavior of BGP routers running Cisco IOS Software is to treat routes without the MED attribute as having a MED of 0, making a route lacking the MED variable the most preferred. To configure the router to conform to the IETF standard, use the bgp bestpath med missing-as-worst router configuration command. 
 

7. eBGP over iBGP Path

If the routes have the same MED, prefer external paths (EBGP - AD 20) over internal paths (IBGP - AD 200).
 

8. Shortest IGP Path

If BGP synchronization is disabled and only internal paths remain, prefer the path through the closest IGP neighbor. This means that the router prefers the shortest internal path (via IGP) within the AS to reach the destination (the shortest IGP path or the path with the lowest IGP metric to the BGP next-hop).
 

9. BGP Multipath

If maximum-paths command is configured, based on this criteria, BGP checks if multiple paths to the destination prefix can be installed or not.

10. Prefer Oldest Path

For the eBGP paths, select the oldest route, to minimize the effect of routes going up and down (flapping).

11. Lowest Router ID

Prefer the route with the lowest neighbor BGP router ID value.
 

12. Shortest Cluster-List

If the BGP route is originated by a peer and is received via multiple Internal Paths, prefer the path with the minimum cluster-list length. This step is followed when BGP Route-Reflectors are present in the domain. 
 
For example, prefix 10.10.0.6/32 is advertised to AS 100. The next-hop router R5 advertises this prefix further to R1 via RRs. There are two paths in the topology as shown below. R1 will prefer the route to 10.10.0.6/32 from RR R4 based on shorter cluster-list compared to the upper path shown in topology irrespective of RR R4's IP is highest compared to RID of RRs R2 and R3.
 
BGP Best Path Selection Criteria - BGP Path Selection
 

If the lower path in the above topology also had two RRs for example, R4, and R7, then R1 would have preferred the route from RR R2 because cluster-list becomes equal from both the upper and lower paths and now lowest RID value of RR will be used as a tie-breaker as per Rule 11. 

13. Lowest Neighbor IP

If the BGP Router IDs are the same, prefer the route with the lowest neighbor IP address.
 
 

BGP Best Path Selection Criteria Lab Scenario


BGP Best Path Selection Criteria Lab Scenario


Let's review the BGP Best Path Selection Process using the above lab topology. For example, let's see which path is taken by Router R4 to reach R1's loopback prefix 10.10.0.1/32. Let's check the BGP table for the best path.

R4#show ip bgp
BGP table version is 41, local router ID is 10.10.0.4
    Network          Next Hop            Metric  LocPrf   Weight     Path
*  i10.10.0.1/32     10.10.56.6               0     100          0           600 100 i
*> i10.10.23.2                                0     100          0           200 100 i

R4#show ip bgp 10.10.0.1
BGP routing table entry for 10.10.0.1/32, version 34
Paths: (2 available, best #2, table default)
  Not advertised to any peer
600 100
    10.10.56.6 (metric 2) from 10.10.0.5 (10.10.0.5)
    Origin IGP, metric 0, localpref 100, valid, internal
  200 100
    10.10.23.2 (metric 2) from 10.10.0.3 (10.10.0.3)
    Origin IGP, metric 0, localpref 100, valid, internal, best


From R4, to reach 10.10.0.1/32, the best path (denoted by ">") is via 10.10.23.2 (R3-R2) path.  Let's study the reason by reviewing all rules of BGP Best Path Selection Criteria.

Rule 1 says, select the path with the highest Weight which is 0 for both the paths, i.e. via 10.10.56.6 and via 10.10.23.2.  Therefore, we need to jump to Rule 2 as weight is equal (0) from both paths.
 
Rule 2 says, select the path with the highest Local Preference which is 100 for both the paths. Therefore, we need to jump to Rule 3.
 
Rule 3 says, select the locally originated route. i.e. the route which is generated by router R4 itself, which is not the case here because 10.10.0.1/32 is a remote prefix. Therefore, we need to jump to Rule 4.
 
Rule 4 says, select the path with the shortest AS path, which is again equal in this case because 10.10.0.1/32 can be reachable after crossing 2 AS from both directions. i.e. we have to cross AS 600 and then 100 (two AS in the path) if we go via 10.10.56.6 (via R6) and we have to cross AS 200 and then 100 (again 2 AS in the path) via 10.10.23.2 (via R2). Therefore, we need to jump to Rule 5.
 
Rule 5 says, prefer the path with the lowest origin code. Again the Origin is the same i.e. IGP(denoted by rightmost "i" for each path. Kindly note that as the route is advertised using protocol BGP, the origin code will show as "i". Therefore, we need to move to Rule 6 if we can get a tiebreaker.
 
Rule 6 says, prefer the path with the lowest MED which is again zero here because it is not set. Therefore, we need to jump to Rule 7.
 
Rule 7 says, prefer the path/route learned from an eBGP peer compared to an iBGP peer. On R4, the route is learned via the iBGP peers (R3 and R5) and not via an eBGP peer. This is denoted again by "i" but this time it is the leftmost one show after the  *  sign. Again, we have to jump to Rule 8 as prefix 10.10.0.1/32 is learned on R4 via iBGP peers.
 
Rule 8 says, if both paths are internal (route learned via iBGP peers) which is exactly the case here, prefer the path that has Shortest IGP metric to the next hop.  As highlighted in bolds in the output below, the route is learned with metric 2 (OSPF) from both paths.

R4#show ip bgp 10.10.0.1
BGP routing table entry for 10.10.0.1/32, version 34
Paths: (2 available, best #2, table default)
  Not advertised to any peer
  600 100
    10.10.56.6 (metric 2) from 10.10.0.5 (10.10.0.5)
      Origin IGP, metric 0, localpref 100, valid, internal
  200 100
    10.10.23.2 (metric 2) from 10.10.0.3 (10.10.0.3)
      Origin IGP, metric 0, localpref 100, valid, internal, best


We can also see this using the OSPF routing table, where the route to R3 and R5's loopbacks are learned with the OSPF metric 2 as highlighted in bold.

R4#show ip route ospf
      10.0.0.0/8 is variably subnetted, 14 subnets, 2 masks
O        10.10.0.3/32 [110/2] via 10.10.34.3, 01:07:19, FastEthernet1/0
O        10.10.0.5/32 [110/2] via 10.10.45.5, 01:05:13, FastEthernet1/1


Therefore, we need to move to Rule 9 to check for a tiebreaker.

Rule 9 says, if maximum-paths commands are configured on BGP peer then we can install multiple routes to the destination. In our case, we have only a single path to both the gateways R3 and R5 and therefore, we have to move to Rule 10.
 
Rule 10 says, if the paths are eBGP, prefer the oldest route, which is again not the case here because the route is learned via iBGP peers and we have to move to Rule 10.
 
Rule 11 says, prefer the path from the neighbor that has the lowest BGP Router-ID(RID) value. Here, Router R3 has the lowest Router ID (10.10.0.3) compared to the RID of R5 (10.10.0.5). So we got the tiebreaker here in Rule 10. R4 will prefer to reach R1's loopback 10.10.0.1/32 via R3 because it has the lowest RID value compared to the RID value of the iBGP neighbor R5.
 
We need not jump to Rule 12 and 13 as BGP successfully got the best path to reach destination 10.10.0.1/32 from R4 while following the Rule 11.


 


I hope you have found this article informative and useful and now have a fair understanding of BGP Best Path Selection Criteria and the important role played by the various BGP Attributes in BGP Best Path Selection. For any of the related queries or feedback, kindly write to us at networkurge@gmail.com


Post a comment

0 Comments