BGP Best Path Selection Algorithm Cisco router
BGP is the protocol used to announce prefixes throughout the internet. It’s a very robust protocol, and very useful to carry lot of prefixes, such as the Internet prefixes or internal client prefixes of an ISP. BGP Best Path Selection Algorithm Cisco router when a prefix is received in BGP, the path passes through two steps before being chosen as candidate to populate the RIB.
The first step consists on checking if the path is valid. If it is, the prefix will get into the BGP table, and later the second step of selection will start.
In order to pass this first check, the path must meet the following requirements:
- The prefix must not been marked as “not-synchronized”
- There must be a route in the RIB to reach the next-hop
- For prefixes learned through eBGP sessions, the local ASN must not be in the AS_PATH of the prefix
In the second step, the best path to reach the prefix is selected. If there is only one path, no comparison needed. If there are many paths to reach the prefix, there is a special algorithm that BGP uses to select the best path, and this is what I want to talk about.
BGP Best Path Selection Algorithm are:
- Prefer the path with the highest WEIGHT
- Prefer the path with the highest LOCAL PREFERENCE
- Prefer the path that was locally originated via a network o redistribute command over aggregate-address command
- Prefer the path with the lowest AS_PATH
- Prefer the path with the lowest ORIGIN type
- Prefer the path with the lowest MULTI-EXIT DISCRIMINATOR (MED)
- Prefer eBGP over iBGP
- Prefer the path with the lowest IGP metric to the BGP next-hop
- When both path are external, prefer the one that was received first
- Prefer the route that comes from the BGP router with the lowest router ID
- If the originator or router ID is the same for multiple paths, prefer the path with the minimum cluster list length
- Prefer the path that comes from the lowest neighbor address
As you can see, the selection process is quite long, although in most cases the selection doesn’t go further than point 8.
- Next Hop – At first, the router will check whether the next-hop is reachable, either via IGP, or by means of static routes. Should the next-hop not be reachable, the route will not be considered any further. The NEXT-HOP is a well-known mandatory BGP attribute.
- Weight – This is a Cisco proprietary, optional, non-transitive, locally-significant attribute. Upon a BGP update, the receiving router will set this attribute to 0 (zero); it will however set the weight to 32768 for all locally originated routes. In regards to path selection, the highest value will always be preferred.
- Local Preference – this is a well-known, discretionary BGP attribute – it is included in BGP updates between iBGP peers only, hence, for routing purposes, it is only significant within the local AS. Over a eBGP session, this attribute will be reset to the default value of 100 and the highest value, will always be preferred.
- Locally Originated – these are routes which show in the BGP table with the next-hop value set to 0.0.0.0 (the local router!). All routes originated using the “network” , “redistribute” or “aggregate-address” commands will show as locally originated routes and they will always have a higher preference over the routes learn from remote BGP peers.
- AS Path is a Well-Known Mandatory attribute; it doesn’t hold a specific value, rather an array of different values pointing to the different AS’s the route has been advertised through. Apart from very specific/special cases, the AS_PATH attribute will not be updated over iBGP sessions; it is however included in every BGP update and it must be accepted accordingly. The shortest this array is, more preferable the route will be.
- Origin Code equates to whether a route has been originated within the local AS’s IGP, in which case ORIGIN=“i”. In cases where the route originated outside the local AS or, through redistribution, the ORIGIN attribute will hold a value of “?”. Routes with the ORIGIN of “i”, will always be preferred.
- Multi Exit Discriminator – MED is a Optional Non-Transitive attribute which translates to the BGP route metric – the lowest value, will always be preferred. By default, MED is always set to zero, unless the route is known via redistribution from IGP – in this case, the IGP metric will be carried into MED. The MED is normally set on routes advertised out to eBGP peers in an attempt to influence preference of incoming traffic.
- External Paths over Internal Paths – routes learn from eBGP neighbors will always be preferred over those learn from iBGP peers; to reinforce this rule, by default, eBGP administrative distance is set to 20, unlike iBGP’s, which is set to 200.
- Router ID (RID) – at last, the router with the lower Router ID will be considered as the next-hop to reach the destination network.
I am sure you’ve noticed the highlighted, Green letters… These, will help us never again forget the BGP Path Selection algorithm, by simply trying to remember the following mnemonic:
Now, every time you will be enjoying a nice, juicy orange, BGP will also come to your mind!