BGP Path Selection

describes the logic used by BGP to identify the best path when multiple routes are installed in the BGP table.

• 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.
• This section explains the logic used by a router that uses BGP when forwarding packets.

Understanding BGP Path Selection

Routing Path Selections Using Longest Match Routers always select the path by examining the prefix length of a network entry. The path selected is chosen where the longest prefix length is always preferred. This logic can be used to influence path selection in BGP. Assume that an organization owns the 100.64.0.0/16 network range but only needs to advertise two subnets (100.64.1.0/24 and 100.64.2.0/24). It could advertise both prefixes (100.64.1.0/24 and 100.64.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 BGP path attributes (PAs) that are advertised externally, but an SP could have a BGP routing policy that ignores path attributes, resulting in random receipt of network traffic. A way that guarantees that paths are selected deterministically outside the organization is to advertise a summary prefix (100.64.0.0/16) out both routers. Then the organization can advertise a longer matching prefix out the router that should receive network traffic for that prefix. The Figure shows R1 advertising the 100.64.1.0/24 prefix, R2 advertising the 100.64.2.0/24 prefix, and both routers advertising the 100.64.0.0/16 summary prefix.  

Understanding BGP Path Selection

BGP Best-Path Algorithm 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 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. A BGP router advertises only the best path to the neighboring routers. The best path is installed in the RIB. If the best path is no longer available, the router can use the existing paths to 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.

BGP Best-Path Algorithm

The BGP best-path algorithm uses the following attributes, in the order shown, for best-path selection:

1. Weight – BGP weight is a Cisco-defined attribute. The path with the higher weight is preferred. Influences only outbound routes from a router or an AS. Not advertised to peers.
2. Local preference – (LOCAL_PREF) is a well-known path attribute included with path advertisements within the AS. Not advertised between eBGP peers.
3. Local originated (network statement, redistribution, or aggregation) – determination as to whether the route originated within the AS. Preference is given to routes advertised or aggregated locally.
4. Accumulated Interior Gateway Protocol (AIGP) – provides the ability for BGP to make routing decisions based on IGP path metrics.
5. Shortest AS_Path – AS path length typically correlates to the AS hop count. A shorter AS path is preferred over a longer AS path.
6. Origin type – The next best-path decision factor is the well-known mandatory BGP attribute named origin. Routes with IGP origin are preferred over those with EGP or incomplete origin (least preferred).

BGP Best-Path Algorithm

1. Lowest MED – The next BGP best-path decision factor is the non-transitive BGP attribute named multiple-exit discriminator (MED). A lower MED is preferred over a higher MED.
2. eBGP over iBGP – The best path selection route source preference order is: eBGP peers (most desirable), confederation member AS peers, and iBGP peers (less desirable)..
3. Lowest IGP next hop- The next decision step is to use the lowest IGP cost to the BGP next-hop address.
4. Oldest eBGP Path – BGP maintains stability in a network by preferring the path from the oldest (established) BGP 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.
5. Router ID – Prefer the route that comes from the BGP peer with the lower router ID (RID)
6. Minimum Cluster List Length – Prefer the route with the minimum cluster list length. In simplest terms, this step locates the path that has traveled the lowest number of iBGP advertisement hops.
7. Lowest neighbor address – The last step is to use 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 tie breaker.

Weight Attribute (Cisco-defined)

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 Attribute

Local Preference – (LOCAL_PREF) is a discretionary path attribute 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 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 leaving an autonomous system. A higher value is preferred over a lower value. The default local preference value of 100 is used during best-path calculation, and is included in advertisements to other iBGP peers. Local preference can influence path selection on other iBGP peers without impacting eBGP peers because local preference is not advertised outside the autonomous system.     Example 12-29 shows the BGP table for the 172.16.1.0/24 network prefix on R2. On the third line of the output, the router indicates that two paths exist, and the first path is the best path. The BGP weight does not exist, so then the local preference is used. The path learned through AS 65300 is the best path because it has a local preference of 333.

Locally Originated Attribute

The third decision point in the best-path algorithm is to determine whether the route originated locally. Preference is given in the following order:

1. Routes that were advertised locally
2. Networks that have been aggregated locally
3. Routes received by BGP peers

Accumulated Interior Gateway Protocol (AIGP) Attribute   Accumulated Interior Gateway Protocol (AIGP) – is an optional nontransitive path attribute that is included with advertisements throughout an AS. BGP does not use path metric due to scalability issues combined with the notion that each AS may use a different routing policy to calculate metrics. The ability for BGP to make routing decisions based on a path metric is a viable option because all the ASs are under the control of a single domain, with consistent routing policies for BGP and IGPs. IGPs are redistributed into BGP.

• A path with an AIGP metric is preferred to a path without an AIGP metric.
• If the next-hop address requires a recursive lookup, the AIGP path needs to calculate a derived metric to include the distance to the next-hop address. The formula is: Derived AIGP metric = (Original AIGP metric + Next-hop AIGRP metric)
• If multiple AIGP paths exist and one next-hop address contains an AIGP metric and the other does not, the non-AIGP path is not used.
• The next-hop AIGP metric is recursively added if multiple lookups are performed.

Shortest AS Path Attribute

The path length typically correlates to the AS hop count. A shorter AS path is preferred over a longer AS path. Prepending ASNs to the AS path makes it longer, thereby making that path less desirable compared to other paths. Typically, the AS path is prepended with the network owner’s ASN. In general, a path that has had the AS path prepended is not selected as the BGP best path because the AS path is longer than the non-prepended path advertisement. Inbound traffic is influenced by prepending AS path length in advertisements to other ASs, and outbound traffic is influenced by prepending advertisements received from other ASs.     Example 12-30 shows the BGP table for the 172.16.1.0/24 network prefix on R2. The second route learned through AS 65100 is the best path. There is not a weight set on either path, and the local preference is identical. The second path has an AS path length of 1, while the first path has an AS path length of 2 (65300 and 65300).

Origin Type Path Attribute

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 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)

Example 12-31 shows the BGP table for the 172.16.1.0/24 network prefix on R2. The second path learned through AS 65100 is the best path because it has an origin of IGP, while first path has an origin of incomplete, which is the least preferred.

Multi-Exit Discriminator (MED) Path Attribute

Multiple-Exit discriminator (MED) – is a non-transitive BGP attribute. MED uses a 32-bit value 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 to other eBGP peers outside the AS that received it. A lower MED is preferred over a higher MED. For MED to be an effective decision factor, the paths being decided upon must come from the same ASN. RFC 4451 guidelines state that a prefix without a MED value should be given priority and, in essence, should be compared with a value of 0. If the MED is missing from a prefix learned from an eBGP peer, devices use a MED of 0 for the best-path calculation. IOS routers advertise a MED of 0 to iBGP peers. Example 12-32 shows the BGP table for the 172.16.1.0/24 network prefix on R2. Notice that R2 is peering only with AS 65300 for MED to be eligible for the best-path selection process. The first path has a MED of 0, and the second path has a MED of 33. The first path is preferred as the MED is lower.

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 selection order is:

1. eBGP peers (most desirable)
2. Confederation member AS peers
3. iBGP peers (least desirable)

Note: BGP confederations are beyond the scope of the CCNP and CCIE Enterprise Core Lowest IGP Metric   The next decision step is to use the lowest IGP cost to the BGP next-hop address. Figure 12-12 illustrates a topology where R2, R3, R4, and R5 are in AS 400. AS 400 peers in a full mesh and establishes BGP sessions using Loopback 0 interfaces. R1 advertises the 172.16.0.0/24 network prefix to R2 and R4. R3 prefers the path from R2 compared to the iBGP path from R4 because the metric to reach the next-hop address is lower. R5 prefers the path from R4 compared to the iBGP path from R2 because the metric to reach the next-hop address is lower.

Oldest eBGP Path, Router ID, and Minimum Cluster List Length

• 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 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 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 use the oldest received path as the tie breaker. Figure 12-13 demonstrates the concept of choosing the router with the lowest neighbor address. R1 is advertising the 172.16.0.0/24 network prefix to R2. R1 and R2 have established two BGP sessions using the 10.12.1.0/24 and 10.12.2.0/24 networks. R2 selects the path advertised from 10.12.1.1 as it is the lower IP address.   Other useful information:

• Full ENCOR Course
• CCNP Enterprise Certificate Information
• 350-401 ENCOR Exam Questions and Solutions
• 350-401 ENCOR Exam Topics