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.

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

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

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

These are the additional requirements for iBGP multipath: • The path should be learned from an internal neighbor (iBGP). The default value. unless the router is configured for unequal−cost iBGP multipath. • 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. and information about networking solutions. Inc. • The IGP metric to the BGP next hop should be equal to the best−path IGP metric. BGP inserts up to n most recently received paths from multipath candidates in the IP routing table. suggestions. The featured links are some of the most recent conversations available in this technology. and technologies. when multipath is disabled. products. NetPro Discussion Forums − Featured Conversations Networking Professionals Connection is a forum for networking professionals to share questions. 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. These are the additional requirements for eBGP multipath: • The path should be learned from an external or confederation−external neighbor (eBGP). you can also use BGP Link Bandwidth. • The IGP metric to the BGP next hop should be equal to the best−path IGP metric. For unequal−cost load balancing. is 1. All rights reserved. . 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.

2006 Document ID: 13753 .Updated: May 24.