Best-Path Calculation

‚  < ‚  Free Open Study ‚  > ‚  

Best- Path Calculation

Material in this section is based on the Cisco document "BGP Best Path Selection Algorithm," available at www.cisco.com/warp/public/459/25.shtml.

By design, a BGP speaker receiving updates picks only a single best update from a set of multiple updates and installs it in the routing table. BGP best-path calculation goes through a series of comparisons between multiple updates. The comparison is done over the BGP attributes, and a series of tests is performed until one update wins over the other and the best path update is placed in the routing table.

With the best-path algorithm, 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 it reaches the end of the list of valid paths.

The following list of rules determines the best path:

  1. Prefer the path with the largest WEIGHT. WEIGHT is a Cisco proprietary parameter, local to the router on which it is configured.

  2. Prefer the path with the largest local preference (LOCAL_PREF).

  3. Prefer the path that was locally originated through a network or aggregate BGP subcommand, or through redistribution from an IGP. Local paths sourced by network / redistribute commands are preferred over local aggregates sourced by the aggregate-address command.

  4. Prefer the path with the shortest AS_PATH. The AS_PATH is a listing of the autonomous systems through which this particular update traveled to reach the local autonomous system. The fewer autonomous systems it crossed, the more preferred the route is. Note the following:

    - This step is skipped if you configure bgp bestpath as-path ignore.

    - An AS_SET counts as 1, no matter how many autonomous systems are in the set.

    - The AS_CONFED_SEQUENCE is not included in the AS_PATH length.

  5. Prefer the path with the lowest origin type: IGP is lower than EGP, and EGP is lower than INCOMPLETE.

  6. Prefer the path with the lowest multi-exit discriminator (MED). Note the following:

    - This comparison is done only if the first (neighboring) AS is the same in the two paths; any Confederation Sub-autonomous systems 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. This option needs to be enabled 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 (paths originated within the local confederation).

    - Paths received from a neighbor with a MED of 4,294,967,295 will have the MED changed to 4,294,967,294 before insertion into the BGP table.

    - Paths received with no MED are assigned a MED of 0, unless bgp bestpath missing-as-worst is enabled; in that case, they are assigned a MED of 4,294,967,294.

    - The bgp deterministic med command also can influence this step.

  7. Prefer external (eBGP) over internal (iBGP) paths. Paths containing AS_CONFED_SEQUENCE are local to the confederation and, therefore, are treated as internal paths. There is no distinction between Confederation External and Confederation Internal.

  8. Prefer the path with the lowest IGP metric to the BGP next hop.

  9. If the maximum-paths n command is enabled and there are multiple external or confederation external paths from the same neighboring AS or Sub-AS, BGP inserts up to n most recently received paths in the IP routing table. This allows eBGP multi-path load sharing. The maximum value of n is currently 6. The default value, when this option is disabled, is 1. The oldest received path is marked as the best path in the output of show ip bgp longer-prefixes, and the equivalent of next-hop-self is performed before forwarding this best path to internal peers.

  10. If both paths are external, prefer the path that was received first (the oldest one). This step minimizes route flapping because a newer path won't displace an older one, even if it was the preferred route based on the RID. It is better practice to apply the additional decision steps in 11, 12, and 13 to iBGP paths only, to ensure a consistent best path decision within the network and thereby avoid loops. This step is skipped if any of the following is true:

    - The bgp best path compare-routerid command is enabled.

    - The router ID is the same for multiple paths because the routes were received from the same router.

    - No current best path exists. An example of losing the current best path occurs when the neighbor offering the path goes down.

  11. Prefer the route coming 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. It can also be set manually using the bgp router-id command. If a path contains RR attributes, the originator ID is substituted for the router ID in the path selection process.

  12. If the originator or RID is the same for multiple paths, prefer the path with the minimum cluster ID length. This will be present only in a BGP Route-Reflector environment in which clients 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 coming from the lowest neighbor address. This is the IP address used in the BGP neighbor configuration, and it corresponds to the remote peer used in the TCP connection with the local router.

Example 14-32 shows how a best path is calculated. Example 14-32 is taken from route-server.cerf.net and is slightly modified to make it more interesting. route-server.cerf.net is a route server available on the Internet.

Example 14-32 Configuration to Demonstrate Calculation of the Best Path
 show ip bgp 3.0.0.0 BGP routing table entry for 3.0.0.0/8, version 16396661 Paths: (4 available, best #4)   Not advertised to any peer  !Path 1  1740 701 80     192.157.69.5 from 192.157.69.5 (134.24.127.201)       Origin IGP, metric 20,  localpref 100  , valid, external,  !Path 2  1740 701 80     198.32.176.25 from 198.32.176.25 (134.24.127.35)       Origin IGP, metric 20,  localpref 110  , valid, external,  !Path 3  1740 701 80     134.24.88.55 from 134.24.88.55 (134.24.127.27)       Origin IGP,  metric 20  ,  localpref 100  , valid, external,  !Path 4  1740 701 80     192.41.177.69 from 192.41.177.69 (134.24.127.131)       Origin IGP,  metric 10  ,  localpref 110, valid, external, best, 

By going through the BGP best-path decision algorithm step by step, path 4 is the best for these reasons:

  • Path 2 is better than path 1 because it has a higher LOCAL_PREF.

  • Path 2 is better than path 3 because it has a higher LOCAL_PREF.

  • Path 4 is better than path 2 because it has a lower MED.

‚  < ‚  Free Open Study ‚  > ‚  


Troubleshooting IP Routing Protocols
Troubleshooting IP Routing Protocols (CCIE Professional Development Series)
ISBN: 1587050196
EAN: 2147483647
Year: 2002
Pages: 260

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net