The BGP best-path selection algorithm influences how traffic enters or leaves an AS. Some router configurations modify the BGP attributes to influence inbound traffic, outbound traffic, or inbound and outbound traffic, depending on the network design requirements. A lot of network engineers do not understand BGP best-path selection, which can often result in suboptimal routing. This article explains the logic used by a router that uses BGP when forwarding packets.
Routing Path Selection Using Longest Match
Routers always select the path a packet should take by examining the prefix length of a network entry. The path selected for a packet is chosen based on the prefix length, where the path length with the longest prefix length is always preferred.
This logic can be used to influence path selection in BGP routers. Assume that an organization owns the 100.10.0.0/16 network range but only needs to advertise two subnets (100.10.1.0/24 and 100.10.2.0/24). It could advertise both prefixes (100.10.1.0/24 and 100.10.2.0/24) from all its routers, but how can it distribute the load for each subnet if all traffic comes in on one router (such as R1)?
The organization could modify various internal BGP and path attributes (PAs) that are advertised externally, but an SP could have a BGP routing policy that ignores those path attributes, resulting in the random receipt of network traffic.
A more elegant way that guarantees that paths are selected deterministically outside the organization is to advertise a summary prefix (100.10.0.0/16) out of both routers. Then the organization can advertise a longer matching prefix out the local router that should receive network traffic for that prefix. The figure below shows the concept, with R1 advertising the 100.10.1.0/24 prefix, R2 advertising the 100.10.2.0/24 prefix, and both routers advertising the 100.10.0.0/16 summary network prefix.
BGP Path Selection Using Longest Match
Regardless of an SP’s routing policy, the more specific prefixes are advertised out of only one router. Redundancy is provided by advertising the summary address. If Router1 crashes, devices use Router2’s route advertisement of 100.10.0.0/16 to reach the 100.10.1.0/24 network.
BGP Best Path Overview
In BGP, route advertisements consist of Network Layer Reachability Information (NLRI) and path attributes (PAs). The NLRI consists of the network prefix and prefix length, and the BGP attributes of multiple routes such as AS_Path, origin, and so on are stored in the PAs. A BGP route may contain multiple paths to the same destination network. Every path’s attributes impact the desirability of the route when a router selects the best path. A BGP router advertises only the best path to the neighboring routers.
Inside the BGP Loc-RIB routing table here, all the routes and their path attributes are maintained with the best path calculated. The best path is then installed in the RIB of the router. If the best path is no longer available, the router can use the existing paths to quickly identify a new best path. BGP recalculates the best path for a prefix upon four possible events:
- BGP next-hop reachability change
- Failure of an interface connected to an eBGP peer
- Redistribution change
- Reception of new or removed paths for a route
BGP automatically installs the first received path as the best path. When additional paths are received for the same network prefix length, the newer paths are compared against the current best path. If there is a tie, processing continues until a best-path winner is identified.
The BGP best-path algorithm uses the following attributes, in the order shown, for the best-path path selection process:
- Weight
- Local preference
- Local originated (network statement, redistribution, or aggregation)
- AIGP
- Shortest AS_Path
- Origin type
- Lowest MED
- eBGP over iBGP
- Lowest IGP next hop
- If both paths are external (eBGP), prefer the first (oldest)
- Prefer the route that comes from the BGP peer with the lower RID
- Prefer the route with the minimum cluster list length
- Prefer the path that comes from the lowest neighbor address
The BGP routing policy can vary from organization to organization, based on the manipulation of the BGP PAs. Because some PAs are transitive and carry from one AS to another AS, those changes could impact downstream routing for other SPs, too.
Other PAs are non-transitive and only influence the routing policy within the organization. Network prefixes are conditionally matched on a variety of factors, such as AS_Path length, specific ASN, BGP communities, or other attributes.
BGP Path Selection Weight
BGP weight is a Cisco-defined attribute and the first step for selecting the BGP best path. Weight is a 16-bit value (0 to 65,535) assigned locally on the router; it is not advertised to other routers. The path with the higher weight is preferred. Weight can be set for specific routes with an inbound route map or for all routes learned from a specific neighbor.
Weight is not advertised to peers and only influences outbound traffic from a router or an AS. Because it is the first step in the best-path algorithm, it should be used when other attributes should not influence the best path for a specific network.
Local Preference
Local preference (LOCAL_PREF) is a well-known discretionary path attribute and is included with path advertisements throughout an AS. The local preference attribute is a 32-bit value (0 to 4,294,967,295) that indicates the highest local preference for exiting the AS to the destination network.
The local preference is not advertised between eBGP peers and is typically used to influence the next-hop address for outbound traffic (that is, leaving an autonomous system). Local preference can be set for specific routes by using a route map or for all routes received from a specific neighbor.
A higher value is preferred over a lower default value. If an edge BGP router does not define the local preference upon receipt of a prefix, the default local preference value of 100 is used during best-path calculation, and it is included in advertisements to other iBGP peers. Modifying the local preference can influence the path selection of other iBGP peers without impacting eBGP peers because local preference is not advertised outside the autonomous system.
Locally Originated via Network or Aggregate Advertisement
The third decision point in the best-path algorithm is to determine whether the route originated locally. Preference is given in the following order:
- Routes that were advertised locally
- Networks that have been aggregated locally
- Routes received by BGP peers
Accumulated Interior Gateway Protocol
Accumulated Interior Gateway Protocol (AIGP) is an optional nontransitive path attribute that is included with advertisements throughout an AS. IGPs typically use the lowest-path metric to identify the shortest path to a destination but cannot provide the scalability of a BGP routing table. BGP uses an AS to identify a single domain of control for a routing policy.
BGP does not use path metrics due to scalability issues combined with the notion that each AS may use a different routing policy to calculate metrics. AIGP provides the ability for BGP to maintain and calculate a conceptual path metric in environments that use multiple ASs with unique IGP routing domains in each AS.
The ability for BGP to make routing decisions based on a path metric is a viable option because all the ASs is under the control of a single domain, with consistent routing policies for BGP and IGPs.
Origin Type
The next BGP best-path decision factor is the well-known mandatory BGP attribute named origin. By default, networks that are advertised through the network statement are set as path with the IGP or i origin, and redistributed networks are assigned the Incomplete or? origin attribute. The origin preference order is:
1. IGP origin (most)
2. EGP origin
3. Incomplete origin (least)
Multi-Exit Discriminator
The next BGP best-path decision factor is the non-transitive external BGP side attribute named multiple-exit discriminator (MED). MED uses a 32-bit value (0 to 4,294,967,295) called a metric. BGP sets the MED automatically to the IGP path metric during network advertisement or redistribution.
If the MED is received from an eBGP session, it can be advertised to other iBGP peers, but it should not be sent outside the AS that received it. MED’s purpose is to influence traffic flows inbound from a different AS. A lower MED is preferred over a higher MED.
eBGP over iBGP
The next BGP best-path decision factor is whether the route comes from an iBGP, eBGP, or confederation member AS (sub-AS) peering. The best-path path selection criteria in order is:
- eBGP peers (most desirable)
- Confederation member AS peers
- iBGP peers (least desirable)
Lowest IGP Metric
Prefer the Oldest eBGP Path
BGP can maintain large routing tables, and unstable sessions result in the BGP best-path calculation executing frequently. BGP maintains stability in a network by preferring the path from the oldest (established) BGP table per session. The downfall of this technique is that it does not lead to a deterministic method of identifying the BGP best path from a design perspective.
Router ID
The next step for the BGP best-path algorithm is to select the best path using the lowest router ID of the advertising eBGP router. If the route was received by a route reflector, then the originator ID is substituted for the router ID.
Minimum Cluster List Length
The next step in the BGP best-path algorithm is to select the best path using the path with the lowest cluster list length. The cluster list is a non-transitive BGP attribute that is appended (not overwritten) by a route reflector with its cluster-ID.
Route reflectors use the cluster-ID attribute as a loop-prevention mechanism. The cluster ID is not advertised between ASs and is locally significant. In simplest terms, this step locates the path that has traveled the lowest number of iBGP advertisement hops.
Lowest Neighbor Address
The last step of the BGP best-path algorithm is to select the path that comes from the lowest BGP neighbor address. This step is limited to iBGP peerings because eBGP peerings used the oldest received path as the tiebreaker.
Download our Free CCNA Study Guide PDF for complete notes on all the CCNA 200-301 exam topics in one book.
We recommend the Cisco CCNA Gold Bootcamp as your main CCNA training course. It’s the highest rated Cisco course online with an average rating of 4.8 from over 30,000 public reviews and is the gold standard in CCNA training:
