BGP Path Selection Algorithm
In this discussion we will dive into the BGP Path Selection Algorithm. There are 3 (Rejection, Selection, Tie-Break) rounds of BGP Path Selection which involve 18 different steps. The first round is Rejection where any route matching certain condition will be rejected. The second Round is Selection where BGP Best Path Compiler will choose a path matching certain conditions. The last round is Tie-Break where the BGP Best Path Compiler will make the final decision based on certain criteria.
Any roues matching the following conditions will be rejected by default.
AS_PATH Contains Local AS
Route is a received only route.
Route is Dampened Route.
Route Learned by iBGP, not present in IGP and Sync is Enabled.
NEXT_HOP is Unreachable.
The above behavior can be changed with explicit configuration. We will discuss each with an example in another tutorial.
In this steps one route will be preferred over another in case it fulfill the any of the below conditions which include certain Path Attributes and other constraints.
Originate (Locally Injected/Originated > Learned)
Best ORIGIN_CODE(i > e > ?)
BGP Path (Routes from EBGP > Routes from iBGP)
Shortest IGP Path (iBGP)
if BGP Multipath is enabled then STOP here.
You can further remember the steps with the following mnemonic.
|“We Love Oranges AS Oranges Mean Pure Perfect Refreshment”|
|O||ORIGIN Code (IGP > EGP > Incomplete)|
|P||Paths (External > Internal)|
|P||Shortest IGP Path (for iBGP)|
If BGP Multipath is configured then the BGP Best Path Compiler must stop and choose all path as best and start load sharing among multiple paths. Otherwise BGP must look into the Tie-Break round.
If BGP Best Path Compiler could not find a best path using the above algorithm then is uses the final decision using tie-break round.
Oldest Route (EBGP)
Lowest Router ID
Lowest Neighbor IP
How the Best Path Algorithm Works
BGP assigns the first valid path as the current best path. BGP then compares the best path with the next path in the list, until BGP reaches the end of the list of valid paths. This list provides the rules that are used to determine the best path:
- Prefer the path with the highest WEIGHT.
WEIGHT is a Cisco-specific parameter. It is local to the router on which it is configured.
- Prefer the path with the highest LOCAL_PREF.
By defauls an route learned from EBGP have the LP unset and a route learned from iBGP have LP 100. This attribute is exchanged only between iBGP peers and is used to determine local policy. We can change the default LP value with the "bgp default local-preference <0-4294967295>" command.
- Prefer the path that was locally originated via a network or aggregate BGP subcommand or through redistribution from an IGP over learned routes.
A routes originated from the same AS would be prefered over originated from same AS and learned via another AS(Allow AS in). Local paths that are sourced by the network or redistribute commands are preferred over local aggregates that are sourced by the "aggregate-address" command because the ATOMIC_AGGREGATE attribute present in a route make it less preferred. If AIGP is configured AND the "bgp bestpath aigp ignore" command is not configured, the decision process considers the AIGP metric. See Configure the AIGP Metric Attribute for BGP for further detail. Locally Injected > Locally Originated > Learned(Network command) > Learned(redistribute command) > Learned(aggregate)
- Prefer the path with the shortest AS_PATH.
This step is skipped if you have configured the "bgp bestpath as-path ignore" command. An AS_SET counts as 1, no matter how many ASs are in the set. The AS_CONFED_SEQUENCE and AS_CONFED_SET are not included in the AS_PATH length.
- Prefer the path with the lowest origin type.
IGP(i) is lower than Exterior Gateway Protocol(e), and EGP is lower than INCOMPLETE(?).
- Prefer the path with the lowest multi-exit discriminator (MED).
This comparison only occurs if the first (the neighboring) AS is the same in the two paths. Any confederation sub-ASs are ignored. In other words, MEDs are compared only if the first AS in the AS_SEQUENCE is the same for multiple paths. Any preceding AS_CONFED_SEQUENCE is ignored. If "bgp always-compare-med" is enabled, MEDs are compared for all paths. You must disable this option over the entire AS. Otherwise, routing loops can occur. If "bgp bestpath med-confed" is enabled, MEDs are compared for all paths that consist only of AS_CONFED_SEQUENCE.These paths originated within the local confederation. Paths received with no MED are assigned a MED of 0, unless you have enabled bgp "bestpath med missing-as-worst".If you have enabled "bgp bestpath med missing-as-worst", the paths are assigned a MED of 4,294,967,295. The "bgp deterministic-med" command can also influence this step.Refer to How BGP Routers Use the Multi-Exit Discriminator for Best Path Selection for a demonstration.
- Prefer eBGP over iBGP paths.
Even if bestpath is selected, go to Step 14 (multipath).
- Prefer the path with the lowest IGP metric to the BGP next hop.
Continue, even if bestpath is already selected.
- Determine if multiple paths require installation in the routing table for BGP Multipath.
Continue, if bestpath is not yet selected.
- When both paths are external, prefer the path that was received first (the oldest one).
This step minimizes route-flap because a newer path does not displace an older one, even if the newer path would be the preferred route based on the next decision criteria. Skip this step if any of these items is true: 1. You have enabled the "bgp best path compare-routerid" command. 2. The router ID is the same for multiple paths because the routes were received from the same router. 3. There is no current best path.
- 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.
This is only present in BGP RR environments. It allows clients to peer with RRs or clients in other clusters. In this scenario, the client must be aware of the RR-specific BGP attribute.
- Prefer the path that comes from the lowest neighbor address.