You are on page 1of 6

BGP Best Path Selection Algorithm

Document ID: 13753

Introduction
Prerequisites
Requirements
Components Used
Conventions
Why Routers Ignore Paths
How the Best Path Algorithm Works
Customize the Path Selection Process
BGP Multipath
NetPro Discussion Forums − Featured Conversations
Related Information

Introduction
Border Gateway Protocol (BGP) routers typically receive multiple paths to the same destination. The BGP
best path algorithm decides which is the best path to install in the IP routing table and to use for traffic
forwarding.

Prerequisites
Requirements
There are no specific requirements for this document.

Components Used
This document is not restricted to specific software and hardware versions.

Conventions
Refer to Cisco Technical Tips Conventions for more information on document conventions.

Why Routers Ignore Paths
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.

• 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 AS_SEQUENCE In this case. This list provides the rules that are used to determine the best path: 1. However. How the Best Path Algorithm Works BGP assigns the first valid path as the current best path. unless you have configured soft−reconfiguration inbound for the neighbor. 3. Prefer the path that was locally originated via a network or aggregate BGP subcommand or through redistribution from an IGP. Prefer the path with the highest LOCAL_PREF. until BGP reaches the end of the list of valid paths. Note: Be aware of these items: ♦ This step is skipped if you have configured the bgp bestpath as−path ignore command.2(8)T and later. no matter how many ASs are in the set. AS_PATH. and EGP is lower than INCOMPLETE. Prefer the path with the lowest origin type. Note: Synchronization is disabled by default in Cisco IOS Software Release 12. Local paths that are sourced by the network or redistribute commands are preferred over local aggregates that are sourced by the aggregate−address command. or to have a value of 100 by default. Note: Be aware of these items: . 2. 5. ♦ An AS_SET counts as 1. • 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). Prefer the path with the lowest multi−exit discriminator (MED). • 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. Note: IGP is lower than Exterior Gateway Protocol (EGP). prefix. the router sends a notification and closes the session. Note: WEIGHT is a Cisco−specific parameter. or community lists. BGP then compares the best path with the next path in the list. ♦ The AS_CONFED_SEQUENCE and AS_CONFED_SET are not included in the AS_PATH length. • Paths that are marked as (received−only) in the show ip bgp longer−prefixes output The policy has rejected these paths. the router has stored the paths because you have configured soft−reconfiguration inbound for the neighbor that sends the path. Note: A path without LOCAL_PREF is considered to have had the value set with the bgp default local−preference command. Prefer the path with the shortest AS_PATH. 6. The same applies to any path that is denied by a routing policy that is implemented via access. Prefer the path with the highest WEIGHT. 4. It is local to the router on which it is configured.

routing loops can occur. . If you have enabled bgp bestpath missing−as−worst.1. the neighbor that offers the path goes down. even if the newer path would be the preferred route based on the next decision criteria (Steps 11.11SC. ♦ THE MED of paths that are received from a neighbor with a MED of 4.0.3. 12. If bestpath is selected. MEDs are compared for all paths.11S3.0. Prefer the route that comes from the BGP router with the lowest router ID. You must disable this option over the entire AS. 12.0. 12.294. for example. When both paths are external.967. Otherwise. 12. if bestpath is not yet selected. ♦ The router ID is the same for multiple paths because the routes were received from the same router.E introduced this command. go to Step 9 (multipath).294. 7.3. 12. ♦ Paths received with no MED are assigned a MED of 0. Continue. 9. The current best path can be lost when. Prefer eBGP over iBGP paths. Skip this step if any of these items is true: ♦ You have enabled the bgp best path compare−routerid command.T. Continue. prefer the path that was received first (the oldest one). Any preceding AS_CONFED_SEQUENCE is ignored. Therefore. This step minimizes route−flap because a newer path does not displace an older one. Note: Paths that contain AS_CONFED_SEQUENCE and AS_CONFED_SET are local to the confederation. unless you have enabled bgp bestpath missing−as−worst . Note: Cisco IOS Software Releases 12. In other words. There is no distinction between Confederation External and Confederation Internal. Determine if multiple paths require installation in the routing table for BGP Multipath. these paths are treated as internal paths. 10. even if bestpath is already selected.1. Any confederation sub−ASs are ignored. ♦ If bgp always−compare−med is enabled. the paths are assigned a MED of 4.294. These paths originated within the local confederation. 8.3. and 12.1. The MED changes to to 4.1. ♦ If bgp bestpath med−confed is enabled.294.967. Refer to How BGP Routers Use the Multi−Exit Discriminator for Best Path Selection for a demonstration. ♦ The bgp deterministic med command can also influence this step. MEDs are compared for all paths that consist only of AS_CONFED_SEQUENCE. 12. 11.295 is changed before insertion into the BGP table.967. ♦ There is no current best path.3AA.11S. Prefer the path with the lowest IGP metric to the BGP next hop.294. ♦ This comparison only occurs if the first (the neighboring) AS is the same in the two paths. and 13). MEDs are compared only if the first AS in the AS_SEQUENCE is the same for multiple paths.

The address corresponds to the remote peer that is used in the TCP connection with the local router. the client must be aware of the RR−specific BGP attribute. paths to the same destination need to have these characteristics equal to the best−path characteristics: • Weight . • Currently. and advertises this best path to its neighbors. The path with the lowest cost value is preferred.647. These paths are installed in the table together with the best path for load sharing. If two paths are configured with the same cost number value. a router still designates one of the paths as the best path. The path with the lowest cost number value is preferred.483.294. This value is the midpoint between 0 and 4. according to the algorithm. the path selection process prefers the path with the lowest community ID. An additional step. in which Cost Communities are compared. only the IGP_COST point of insertion is implemented. This address is the IP address that is used in the BGP neighbor configuration. Also. If the originator or router ID is the same for multiple paths. you can use the bgp router−id command to manually set the router ID. prefer the path with the minimum cluster list length. These paths are then evaluated accordingly by the best path selection process.294. The cost number value determines the preference for the path. Note: Be aware of these items: • This step is skipped if you have issued the bgp bestpath cost−community ignore command. BGP Multipath BGP Multipath allows installation into the IP routing table of multiple BGP paths to the same destination. the originator ID is substituted for the router ID in the path selection process. It allows clients to peer with RRs or clients in other clusters.967. In this scenario. is added to the algorithm that the How the Best Path Algorithm Works section describes. which is called BGP Cost Community. 12. Paths that are not specifically configured with the cost number value are assigned a default cost number value of 2.967. BGP Multipath does not affect bestpath selection. Customize the Path Selection Process The extended community attribute. provides a way to customize the best path selection process.295).147. This means that only Cost Communities with the IGP_COST point of insertion are considered after Step 8 of the algorithm in How the Best Path Algorithm Works. with preference given to loopback addresses. Prefer the path that comes from the lowest neighbor address. For example. 13. Note: If a path contains route reflector (RR) attributes. These are the BGP Multipath features: • eBGP Multipathmaximum−paths n • iBGP Multipathmaximum−paths ibgp n • eiBGP Multipathmaximum−paths eibgp n In order to be candidates for multipath. The router ID is the highest IP address on the router.295. This step comes after the required step (point of insertion) in the algorithm. • The cost community set clause is configured with a cost community ID number (0 to 255) and cost number value (0 to 4. This is only present in BGP RR environments.

These are the additional requirements for iBGP multipath: • The path should be learned from an internal neighbor (iBGP). NetPro Discussion Forums − Featured Conversations for RP Service Providers: MPLS Virtual Private Networks: Services Virtual Private Networks: Security Related Information • Troubleshooting BGP • How BGP Routers Use the Multi−Exit Discriminator for Best Path Selection • Configuring BGP • BGP Support Page • Technical Support & Documentation − Cisco Systems All contents are Copyright © 2006−2007 Cisco Systems. Important Notices and Privacy Statement. The maximum value of n is currently 6. when multipath is disabled. is 1. The featured links are some of the most recent conversations available in this technology. • Local preference • AS−PATH length • Origin • MED • One of these: ♦ Neighboring AS or sub−AS (before the addition of the eiBGP Multipath feature) ♦ AS−PATH (after the addition of the eiBGP Multipath feature) Some BGP Multipath features put additional requirements on multipath candidates. • The IGP metric to the BGP next hop should be equal to the best−path IGP metric. suggestions. NetPro Discussion Forums − Featured Conversations Networking Professionals Connection is a forum for networking professionals to share questions. you can also use BGP Link Bandwidth. and information about networking solutions. For unequal−cost load balancing. and technologies. Inc. Note: The equivalent next−hop−self is performed on the best path that is selected among eBGP multipaths before it is forwarded to internal peers. BGP inserts up to n most recently received paths from multipath candidates in the IP routing table. The default value. • The IGP metric to the BGP next hop should be equal to the best−path IGP metric. unless the router is configured for unequal−cost iBGP multipath. . All rights reserved. products. These are the additional requirements for eBGP multipath: • The path should be learned from an external or confederation−external neighbor (eBGP).

Updated: May 24. 2006 Document ID: 13753 .