IntroductionThis document describes the function of the Border Gateway Protocol (BGP) best path algorithm. 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. Show
Why Routers Ignore PathsAssume 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
How the Best Path Algorithm WorksBGP 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 in order to determine the best path:
Example: BGP Best Path SelectionIn this example, 9 paths are available for the network 10.30.116.0/23. The Router R1#show ip bgp vpnv4 rd 1100:1001 10.30.116.0/23 BGP routing table entry for 1100:1001:10.30.116.0/23, version 26765275 Paths: (9 available, best #6, no table) Advertised to update-groups: 1 2 3 (65001 64955 65003) 65089, (Received from a RR-client) 172.16.254.226 (metric 20645) from 172.16.224.236 (172.16.224.236) Origin IGP, metric 0, localpref 100, valid, confed-internal Extended Community: RT:1100:1001 mpls labels in/out nolabel/362 (65008 64955 65003) 65089 172.16.254.226 (metric 20645) from 10.131.123.71 (10.131.123.71) Origin IGP, metric 0, localpref 100, valid, confed-external Extended Community: RT:1100:1001 mpls labels in/out nolabel/362 (65001 64955 65003) 65089 172.16.254.226 (metric 20645) from 172.16.216.253 (172.16.216.253) Origin IGP, metric 0, localpref 100, valid, confed-external Extended Community: RT:1100:1001 mpls labels in/out nolabel/362 (65001 64955 65003) 65089 172.16.254.226 (metric 20645) from 172.16.216.252 (172.16.216.252) Origin IGP, metric 0, localpref 100, valid, confed-external Extended Community: RT:1100:1001 mpls labels in/out nolabel/362 (64955 65003) 65089 172.16.254.226 (metric 20645) from 10.77.255.57 (10.77.255.57) Origin IGP, metric 0, localpref 100, valid, confed-external Extended Community: RT:1100:1001 mpls labels in/out nolabel/362 (64955 65003) 65089 172.16.254.226 (metric 20645) from 10.57.255.11 (10.57.255.11) Origin IGP, metric 0, localpref 100, valid, confed-external, best Extended Community: RT:1100:1001 mpls labels in/out nolabel/362 !--- BGP selects this as the Best Path on comparing BGP selects the best path out of these 9 paths through the consideration of various attributes that are explained in this document. In the output shown here, BGP compares the available paths and selects Path# 6 as the best path based on its lower router-ID. Comparing path 1 with path 2: Both paths have reachable next hops Both paths have a WEIGHT of 0 Both paths have a LOCAL_PREF of 100 Both paths are learned Both paths have AS_PATH length 1 Both paths are of origin IGP The paths have different neighbor AS's so ignoring MED Both paths are internal (no distinction is made between confed-internal and confed-external) Both paths have an IGP metric to the NEXT_HOP of 20645 Path 2 is better than path 1 because it has a lower Router-ID. Comparing path 2 with path 3: Both paths have reachable next hops Both paths have a WEIGHT of 0 Both paths have a LOCAL_PREF of 100 Both paths are learned Both paths have AS_PATH length 1 Both paths are of origin IGP Both paths have the same neighbor AS, 65089, so comparing MED. Both paths have a MED of 0 Both paths are confed-external Both paths have an IGP metric to the NEXT_HOP of 20645 Path 2 is better than path 3 because it has a lower Router-ID. Comparing path 2 with path 4: Both paths have reachable next hops Both paths have a WEIGHT of 0 Both paths have a LOCAL_PREF of 100 Both paths are learned Both paths have AS_PATH length 1 Both paths are of origin IGP Both paths have the same neighbor AS, 65089, so comparing MED. Both paths have a MED of 0 Both paths are confed-external Both paths have an IGP metric to the NEXT_HOP of 20645 Path 2 is better than path 4 because it has a lower Router-ID. Comparing path 2 with path 5: Both paths have reachable next hops Both paths have a WEIGHT of 0 Both paths have a LOCAL_PREF of 100 Both paths are learned Both paths have AS_PATH length 1 Both paths are of origin IGP Both paths have the same neighbor AS, 65089, so comparing MED. Both paths have a MED of 0 Both paths are confed-external Both paths have an IGP metric to the NEXT_HOP of 20645 Path 5 is better than path 2 because it has a lower Router-ID. Comparing path 5 with path 6: Both paths have reachable next hops Both paths have a WEIGHT of 0 Both paths have a LOCAL_PREF of 100 Both paths are learned Both paths have AS_PATH length 1 Both paths are of origin IGP Both paths have the same neighbor AS, 65089, so comparing MED. Both paths have a MED of 0 Both paths are confed-external Both paths have an IGP metric to the NEXT_HOP of 20645 Path 6 is better than path 5 because it has a lower Router-ID. Comparing path 6 with path 7: Both paths have reachable next hops Both paths have a WEIGHT of 0 Both paths have a LOCAL_PREF of 100 Both paths are learned Both paths have AS_PATH length 1 Both paths are of origin IGP Both paths have the same neighbor AS, 65089, so comparing MED. Both paths have a MED of 0 Both paths are internal (no distinction is made between confed-internal and confed-external) Both paths have an IGP metric to the NEXT_HOP of 20645 Path 6 is better than path 7 because it has a lower Router-ID. Comparing path 6 with path 8: Both paths have reachable next hops Both paths have a WEIGHT of 0 Both paths have a LOCAL_PREF of 100 Both paths are learned Both paths have AS_PATH length 1 Both paths are of origin IGP Both paths have the same neighbor AS, 65089, so comparing MED. Both paths have a MED of 0 Both paths are confed-external Both paths have an IGP metric to the NEXT_HOP of 20645 Path 6 is better than path 8 because it has a lower Router-ID. Comparing path 6 with path 9: Both paths have reachable next hops Both paths have a WEIGHT of 0 Both paths have a LOCAL_PREF of 100 Both paths are learned Both paths have AS_PATH length 1 Both paths are of origin IGP The paths have different neighbor AS's so ignoring MED Both paths are internal (no distinction is made between confed-internal and confed-external) Both paths have an IGP metric to the NEXT_HOP of 20645 Path 6 is better than path 9 because it has a lower Router-ID. The best path is #6 Customize the Path Selection ProcessThe extended community attribute, which is called BGP Cost Community, provides a way to customize the best path selection process. An additional step, in which cost communities are compared, is added to the algorithm that the How the Best Path Algorithm Works section describes. This step comes after the required step (point of insertion) in the algorithm. The path with the lowest cost value is preferred. Note: Be aware of these items: - This step is skipped if you have issued the - The cost community set clause is configured with a cost community ID number (0 to 255) and cost number value (0 to 4,294,967,295). The cost number value determines the preference for the path. The path with the lowest cost number value is preferred. Paths that are not specifically configured with the cost number value are assigned a default cost number value of 2,147,483,647. This value is the midpoint between 0 and 4,294,967,295. These paths are then evaluated accordingly by the best path selection process. If two paths are configured with the same cost number value, the path selection process prefers the path with the lowest community ID. If the paths have unequal pre-bestpath cost communities, the path with the lower pre-bestpath cost community is selected as the best path. - The ABSOLUTE_VALUE is considered the first step in order to determine the degree of preference of a path. For example, when EIGRP is redistributed to BGP VPNv4, the ABSOLUTE_VALUE type is used for cost community. The IGB_Cost is considered after the interior (IGP) distance to the next hop has been compared. This means that cost communities with the IGP_COST point of insertion are considered after step 8 of the algorithm in How the Best Path Algorithm Works. BGP MultipathBGP Multipath allows installation into the IP routing table of multiple BGP paths to the same destination. These paths are installed in the table together with the best path for load sharing. BGP Multipath does not affect bestpath selection. For example, a router still designates one of the paths as the best path, per the algorithm, and advertises this best path to its neighbors. These are the BGP Multipath features:
In order to be candidates for multipath, paths to the same destination need to have these characteristics equal to the best-path characteristics:
Some BGP Multipath features put additional requirements on multipath candidates. These are the additional requirements for eBGP multipath:
These are the additional requirements for iBGP multipath:
BGP inserts up to n most recently received paths from multipath candidates in the IP routing table. The maximum value of n is currently 6. The default value, when multipath is disabled, is 1. For unequal-cost load balancing, you can also use BGP Link Bandwidth. 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. Related Information
Which criteria does OSPF use to find the best path?If there are multiple routes to a network with the same route type, the OSPF metric calculated as cost based on the bandwidth is used for selecting the best route. The route with the lowest value for cost is chosen as the best route.
Which is first criteria router use to best path selection process?1) Weight — weight is the first criterion used by the router and it is set locally on the user's router. The Weight is not passed to the following router updates. In case there are multiple paths to a certain IP address, BGP always selects the path with the highest weight.
How does a router select optimal route?When multiple routes are available to send packets from a router to the destination, the router can select the optimal route from an IP routing table. Optimal route selection depends on routing protocol preferences and metrics of routes.
What is typically used by a routing protocol to determine the best path?Routing protocols use metrics to identify the optimal or shortest path to a destination network. Various routing protocols may have distinct metrics. Generally, a lower metric indicates a superior path. Hops, bandwidth, delay, reliability, and load can be used to determine a metric's value.
|