Route Selection

One of the most common questions I get concerns path selection within the router. Everyone knows (or at least they should know) that a more specific prefix will be preferred, but until you learn the basics, you’ll never be able to debug why a router is using a sub optimal path. There are a couple layers to processes when building the routing table, first we have to consider the individual routing protocols. Within each protocol there are several considerations for route selection. First, lets discuss selection within an IGP.

Metrics

This is a number generated by the routing protocol to calculate the best path to a given destination, if it learns multiple paths to the same destination. Every routing protocol uses its own unique metric. If there are multiple paths to the same destination from a single routing protocol, then the multiple paths would have the same administrative distance and the best path is selected based on the metrics. Metrics are values associated with specific routes, ranking them from most preferred to least preferred. The parameters used to determine the metrics differ for different routing protocols. The path with the lowest metric is selected as the optimal path and installed in the routing table. If there are multiple paths to the same destination with equal metrics, load balancing is done on these equal cost paths.

How the BGP Path Selection Algorithm Works

On your edge, there is only one protocol. BGP is a totally different beast when it comes to route selection, part of which makes it so great. BGP has a rather long route selection process. All of which allows you to tune your route paths very effeciently. As the table is scanned 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:

1. Prefer the path with the highest WEIGHT.
   Note: Weight is not a universal parameter. It is local to the router on which it is configured.
2. Prefer the path with the highest Local Preference.
3. Prefer the path that was locally originated via a network or aggregate BGP subcommand or through redistribution from an IGP.
   Note: Paths sourced by network or redistribute commands are preferred over local aggregates from the aggregate-address command.
4. Prefer the path with the shortest AS_PATH.
   Note: This step is skipped if you have configured the bgp bestpath as-path ignore command.
5. Prefer the path with the lowest origin type.
   Note: IGP is preferred over EGP which is preferred over ‘incomplete’.
6. Prefer the path with the lowest multi-exit discriminator (MED).
   Note the following:
   • 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.
   • THE MED of paths that are received from a neighbor with a MED of 4,294,967,295 is changed before insertion into the BGP table. The MED changes to to 4,294,967,294.
   • 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,294.
7. Prefer eBGP over iBGP paths.
   If bestpath is selected, go to Step 9 (multipath).
8. Prefer the path with the lowest IGP metric to the BGP next hop.
   Continue, even if bestpath is already selected.
9. Determine if multiple paths require installation in the routing table for BGP Multipath.
   Continue, if bestpath is not yet selected.
10. 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 (Steps 11, 12, and 13).
    Skip this step if any of these items is true:
    • You have enabled the bgp best path compare-routerid command.
    • The router ID is the same for multiple paths because the routes were received from the same router.
    • There is no current best path.
    • The current best path can be lost when, for example, the neighbor that offers the path goes down.
11. Prefer the route that comes from the BGP router with the lowest router ID.
    The router ID is the highest IP address on the router, with preference given to loopback addresses. Also, you can use the bgp router-id command to manually set the router ID.
    Note: If a path contains route reflector (RR) attributes, the originator ID is substituted for the router ID in the path selection process.
12. 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.
13. Prefer the path that comes from the lowest neighbor address.
    This address is the IP address that is used in the BGP neighbor configuration. The address corresponds to the remote peer that is used in the TCP connection with the local router.

Administrative Distance

After each protocol determines its best route, the router may still have duplicate routes from multiple protocols. Administrative Distance is the measure of trustworthiness of the source of the route. If a router learns about a destination from more than one routing protocol, administrative distance is compared and the preference is given to the routes with lower administrative distance. In other words, it is the believability of the source of the route.

Default Administrative Distances

Troublshooting, aka Why Routers Ignore Paths

Lets assume that all paths that a router receives for a particular prefix are arranged in a list. The list is similar to the output of the show ip bgp longer-prefixes command. In this case, some paths are not considered as candidates for the best path. Such paths typically do not have the valid flag in the output of the show ip bgp longer-prefixes command. Routers ignore paths in these circumstances:

• Paths that are marked as not synchronized in the show ip bgp longer-prefixes output
  If BGP synchronization is enabled, there must be a match for the prefix in the IP routing table in order for an internal BGP (iBGP) path to be considered a valid path. BGP synchronization is enabled by default in Cisco IOS® Software. If the matching route is learned from an Open Shortest Path First (OSPF) neighbor, its OSPF router ID must match the BGP router ID of the iBGP neighbor. Most users prefer to disable synchronization with use of the no synchronization BGP subcommand.
• Paths for which the Next Hop is inaccessible
  Be sure that there is an Interior Gateway Protocol (IGP) route to the next hop that is associated with the path.
• Paths from an external BGP (eBGP) neighbor if the local autonomous system (AS) appears in the AS path
  Such paths are denied upon ingress into the router and are not even installed in the BGP Routing Information Base (RIB). The same applies to any path that is denied by a routing policy that is implemented via access, prefix, AS path, or community lists, unless you have configured soft-reconfiguration inbound for the neighbor.
• If you enabled bgp enforce-first-as and the update does not contain the AS of the neighbor as the first AS number in the sequence.
  In this case, the router sends a notification and closes the session.
• Paths that are marked as (received-only) in the show ip bgp longer-prefixes output
  The policy has rejected these paths. However, the router has stored the paths because you have configured soft-reconfiguration inbound for the neighbor that sends the path.