Introduction
This document outlines the BGP best path
selection algorithm, and covers specific configuration examples on how
to manipulate BGP’s best path decision based on different attributes.
Initial Topology
The
following topology will be referenced for the entirety of this document
unless otherwise stated. EIGRP is being used as the underlying IGP for
basic connectivity.
In the topology above R1 is receiving a similar BGP route
(172.16.1.0/24) via R2 and R3. Prior to any user manipulation, R1
prefers the path advertised from R2 over the path advertised from R3.
This can be seen in the following output:
R1#sh ip bgp
BGP table version is 2, local router ID is 13.13.13.1
Status codes: s suppressed, d damped, h history, * valid, > best, i - internal,
r RIB-failure, S Stale, m multipath, b backup-path, f RT-Filter,
x best-external, a additional-path, c RIB-compressed,
Origin codes: i - IGP, e - EGP, ? - incomplete
RPKI validation codes: V valid, I invalid, N Not found
Network Next Hop Metric LocPrf Weight Path
* 172.16.1.0/24 13.13.13.3 0 200 300 i
*> 12.12.12.2 0 200 300 i
The '
>' shown in the output above indicates that the path with a next hop of 12.12.12.2 (R2) is the current best path.
R1#sh ip bgp 172.16.1.0/24
BGP routing table entry for 172.16.1.0/24, version 2
Paths: (2 available, best #2, table default)
Advertised to update-groups:
1
Refresh Epoch 1
200 300
13.13.13.3 from 13.13.13.3 (34.34.34.3)
Origin IGP, localpref 100, valid, external
Refresh Epoch 1
200 300
12.12.12.2 from 12.12.12.2 (24.24.24.2)
Origin IGP, localpref 100, valid, external, best
R1#
The
above output further illustrates that the path with a next hop address
of 12.12.12.2 is currently being chosen as 'best', as well as the BGP
path attributes associated to the paths that are being compared.
Once
R1 has selected the best path it performs a recursive routing lookup on
the associated next hop address. In this case the next hop address is
12.12.12.2, so the lookup will result in a next hop interface of
FastEthernet0/0.
R1#sh ip route 12.12.12.2
Routing entry for 12.12.12.0/24
Known via "connected", distance 0, metric 0 (connected, via interface)
Redistributing via eigrp 1
Routing Descriptor Blocks:
* directly connected, via FastEthernet0/0
Route metric is 0, traffic share count is 1
Once
the lookup has been done for the Next Hop Address we now have the
associated next hop interface which is installed for the CEF entry:
R1#sh ip cef 172.16.1.0/24
172.16.1.0/24
nexthop 12.12.12.2 FastEthernet0/0
Determining Which Path is Best
BGP
compares multiple path attributes when choosing which path is best. The
list of steps that are performed in the comparison can also be found in
the
Best Path Selection Algorithm.
The default Best Path Selection Algorithm includes the following steps:
1. Compare Weight
The path with the
highest weight is preferred. If the weight is identical, move on to step 2.
This
path attribute is only locally significant. If you change the weight on
one router, it will not affect any other router within the Autonomous
System. This is a Cisco Proprietary feature.
2. Compare Local Preference
The path with the
highest local preference is preferred. If the local preference is identical, move on to step 3.
This
path attribute is not locally significant. If you change the local
preference on one router, it will affect other routers within the
Autonomous System.
3. Is the Path Locally Originated?
Any
path that has been originated on a local router will be preferred over
any paths learned from a BGP Peer. If no locally originated prefix
exists in the BGP table for the paths being compared, move on to step 4.
In Cisco IOS this step is implemented by associating a weight of 32768 to any prefixes advertised into BGP on the local router.
For example, when R4 advertised the 172.16.1.0/24 prefix into BGP with the command network 172.16.1.0 mask 255.255.255.0 it automatically added a weight of 32768 to that prefix in the BGP table. This can be seen from the following output:
R4#sh ip bgp 172.16.1.0/24
BGP routing table entry for 172.16.1.0/24, version 2
Paths: (1 available, best #1, table default)
Advertised to update-groups:
1
Refresh Epoch 1
Local
0.0.0.0 from 0.0.0.0 (172.16.1.1)
Origin IGP, metric 0, localpref 100, weight 32768, valid, sourced, local, best
This
means that R4 will prefer its next hop address for the 172.16.1.0/24
subnet, regardless of similar paths learned via its BGP peers.
4. Compare AS Path
The path with the
shortest AS Path is preferred. If the AS Path is identical in length, move on to step 5.
5. Compare Origin
This step in the Best Path Selection process compares how BGP learned about a path originally. There are 3 origin codes:
IGP - the path was learned by BGP via the
network statement and is interior to the originating Autonomous System
INCOMPLETE - the path was learned BGP in an unknown fashion, typically via Redistribution.
IGP > INCOMPLETE
If the origin is identical, move on to step 6.
6. Compare the Multi-Exit Discrimiator (MED)
The path with the
lowest
MED is preferred. This check is only done if the first hop AS is
identical in the paths being compared. If the first hop AS is different
or the MED is identical, move on to step 7.
7. Compare Neighbor Type
Paths
learned from eBGP peers are preferred over paths learned from iBGP
peers. If all paths were learned from the same type of peer, move on to
step 8. If the best path is selected during this step, skip step 8 and
move on to step 9.
8. IGP Metric
BGP advertises a prefix and a next hop address with any path. The path with the
lower IGP metric to the associated next hop address is preferred. If the IGP metrics are identical on all paths, move on to step 9.
9. Are Multiple Paths Allowed?
BGP by default will only install one path as best. If you configure the
maximum-paths command to allow more than one path to be installed, BGP will use the IGP to load balance to the associated destination prefix.
At this point if the best path has not been selected, move on to step 10.
10. Compare Route Age
When both paths are learned from eBGP peers, BGP prefers the
route that was learned first.
The
logic is that the longer a route has been in the BGP Table, the more
stable that path must be. This does not apply to iBGP routes.
11. Compare Neighbor's Router-ID
Prefer the path that is learned from the peer with the
lower BGP Router-ID. If the Router-ID is identical, move on to step 12.
12. Compare Cluster List Length
The path with the
minimum Cluster List Length is preferred. (This only comes into play in BGP Route-Reflector environments)
If the Cluster List Length is identical, move on to step 13.
13. Compare the Neighbor Address
This is the catch-all rule in the best path selection process. The path with the
lower peer address (the IP address configured with the
neighbor statement)
is preferred. You cannot configure multiple neighbors with the same IP
address, so it is impossible for this step to result in a tie.
Manipulating the Best Path
This
section covers how to manipulate BGP Path Attributes to alter which
path BGP chooses is best. The following Path Attributes will be
illustrated:
- Weight
- Local Preference
- AS Path
- MED
- Installing Multiple Paths
NOTE:
All best path manipulation covered in this section will be done on a
per neighbor basis. Altering path attributes per prefix is not discussed
to reduce complexity.
In
each of the following examples BGP has chosen R2 as the preferred next
hop to the 172.16.1.0/24 subnet prior to any user configuration.
R1#sh ip bgp 172.16.1.0/24
BGP routing table entry for 172.16.1.0/24, version 2
Paths: (2 available, best #2, table default)
Advertised to update-groups:
1
Refresh Epoch 1
200 300
13.13.13.3 from 13.13.13.3 (34.34.34.3)
Origin IGP, localpref 100, valid, external
Refresh Epoch 1
200 300
12.12.12.2 from 12.12.12.2 (24.24.24.2)
Origin IGP, localpref 100, valid, external, best
Manipulating WEIGHT
R1's
weight can be altered to prefer the next hop address of 13.13.13.3 for
the 172.16.1.0/24 prefix. The following example uses the
weight keyword to do so, instead of setting the value with a route-map.
On R1:
Here we configure a WEIGHT of 1 to all prefixes learned from the neighbor 13.13.13.3:
R1#conf t
Enter configuration commands, one per line. End with CNTL/Z.
R1(config)#router bgp 100
R1(config-router)#neighbor 13.13.13.3 weight 1
R1(config-router)#end
R1#
The
Prefixes learned from R3 must be updated for this configuration to take
affect. You can request a route refresh from R3 to accomplish this with
the command
clear ip bgp 13.13.13.3 soft in.
Now
when BGP goes to compare the Best Path Attributes of the two known
paths the first thing that is checked is weight. Since the weight of the
R3 path is 1, and the weight of the R2 path is 0 (by default) R1
prefers the path with a next hop address of 13.13.13.3.
R1#sh ip bgp 172.16.1.0/24
BGP routing table entry for 172.16.1.0/24, version 5
Paths: (2 available, best #1, table default)
Advertised to update-groups:
1
Refresh Epoch 2
200 300
13.13.13.3 from 13.13.13.3 (34.34.34.3)
Origin IGP, localpref 100, weight 1, valid, external, best
Refresh Epoch 2
200 300
12.12.12.2 from 12.12.12.2 (24.24.24.2)
Origin IGP, localpref 100, valid, external
R1#
Weight is only illustrated in the
show ip bgp output
when a value is present. The Path with a next hop of 12.12.12.2 does
not illustrate the weight in this example because no value has been set
by the user.
The next hop interface for traffic destined to the 172.16.1.0/24 prefix is now updated to FastEthernet0/1.
R1#sh ip cef 172.16.1.0/24
172.16.1.0/24
nexthop 13.13.13.3 FastEthernet0/1
R1#
Manipulating LOCAL PREFERENCE
R1's
local preference can be altered to prefer the next hop address of
13.13.13.3 for the 172.16.1.0/24 prefix. The following example uses a
route-map to set the value.
On R1:
Here we configure a Local Preference of 101 (the default is 100) to all prefixes learned from the neighbor 13.13.13.3:
R1#
R1#conf t
Enter configuration commands, one per line. End with CNTL/Z.
R1(config)#route-map RM_LOCAL_PREF permit 10
R1(config-route-map)#set local-preference 101
R1(config-route-map)#exit
R1(config)#
R1(config)#router bgp 100
R1(config-router)#neighbor 13.13.13.3 route-map RM_LOCAL_PREF in (can only be set inbound)
R1(config-router)#end
R1#clear ip bgp 13.13.13.3 soft in
R1#
Since
the weight of both paths are identical, BGP then checks the local
preference to determine which path is best. Since the path learned from
R3 now has a higher local preference, it is preferred:
R1#sh ip bgp 172.16.1.0/24
BGP routing table entry for 172.16.1.0/24, version 3
Paths: (2 available, best #2, table default)
Advertised to update-groups:
3
Refresh Epoch 2
200 300
12.12.12.2 from 12.12.12.2 (24.24.24.2)
Origin IGP, localpref 100, valid, external
Refresh Epoch 3
200 300
13.13.13.3 from 13.13.13.3 (34.34.34.3)
Origin IGP, localpref 101, valid, external, best
R1#
The next hop interface for traffic destined to the 172.16.1.0/24 prefix is now updated to FastEthernet0/1.
R1#sh ip cef 172.16.1.0/24
172.16.1.0/24
nexthop 13.13.13.3 FastEthernet0/1
R1#
Manipulating the AS PATH
R1's
AS Path can be altered to prefer the next hop address of 13.13.13.3
for the 172.16.1.0/24 prefix.The following example uses a route-map to
prepend additional hops onto the AS Path of the path learned from R2.
On R1:
Here we configure an AS Path with 2 additional hops for all of prefixes learned from the neighbor 12.12.12.2:
R1#
R1#conf t
Enter configuration commands, one per line. End with CNTL/Z.
R1(config)#route-map RM_AS_PATH_PREPEND
R1(config-route-map)#set as-path prepend 200 200
R1(config-route-map)#exit
R1(config)#router bgp 100
R1(config-router)#neighbor 12.12.12.2 route-map RM_AS_PATH_PREPEND in (could be done inbound or outbound)
R1(config-router)#end
R1#clear ip bgp 12.12.12.2 soft in
R1#
Now
the path learned from R2 will have 2 additional hops associated to it.
This will make the path from R3 more preferred since it is shorter:
R1#sh ip bgp 172.16.1.0/24
BGP routing table entry for 172.16.1.0/24, version 3
Paths: (2 available, best #1, table default)
Advertised to update-groups:
4
Refresh Epoch 2
200 300
13.13.13.3 from 13.13.13.3 (34.34.34.3)
Origin IGP, localpref 100, valid, external, best
Refresh Epoch 3
200 200 200 300
12.12.12.2 from 12.12.12.2 (24.24.24.2)
Origin IGP, localpref 100, valid, external
R1#
The next hop interface for traffic destined to the 172.16.1.0/24 prefix is now updated to FastEthernet0/1.
R1#sh ip cef 172.16.1.0/24
172.16.1.0/24
nexthop 13.13.13.3 FastEthernet0/1
R1#
Manipulating MED
R1's
MED can be altered to prefer the next hop address of 13.13.13.3 for
the 172.16.1.0/24 prefix. The following example uses a route-map to set
the value.
On R2:
MED can only be configured outbound to
influence which path is the preferred entry point into an Automonous
System. We want to influence R1 to prefer the path via R3, so we
configure a higher MED value to be advertised from R2 to R1 than from R3
to R1.
R2#
R2#conf t
Enter configuration commands, one per line. End with CNTL/Z.
R2(config)#route-map RM_MED permit 10
R2(config-route-map)#set metric 1 (In Cisco IOS, you use the metric keyword to alter MED for BGP)
R2(config-route-map)#exit
R2(config)#router bgp 200
R2(config-router)#neighbor 12.12.12.1 route-map RM_MED out
R2(config-router)#end
R2#clear ip bgp 12.12.12.1 soft out
R2#
Now
when R1 reaches step 6 in the best path selection process, it will
choose the path learned from R3 since the MED is lower (a default of 0)
than what is advertised by R2:
R1#sh ip bgp 172.16.1.0/24
BGP routing table entry for 172.16.1.0/24, version 3
Paths: (2 available, best #2, table default)
Advertised to update-groups:
5
Refresh Epoch 2
200 300
12.12.12.2 from 12.12.12.2 (24.24.24.2)
Origin IGP, metric 1, localpref 100, valid, external
Refresh Epoch 3
200 300
13.13.13.3 from 13.13.13.3 (34.34.34.3)
Origin IGP, localpref 100, valid, external, best
R1#
If a MED value has not been set by the BGP peer, we will not show the value of 0 in the
show ip bgp output.
The next hop interface for traffic destined to the 172.16.1.0/24 prefix is now updated to FastEthernet0/1.
R1#sh ip cef 172.16.1.0/24
172.16.1.0/24
nexthop 13.13.13.3 FastEthernet0/1
R1#
Installing Multiple Paths
By
default BGP will only choose one path as best. If multiple paths are
learned to a destination subnet the user can configure BGP to load
balance with the underlying IGP.
On R1:
Adjusting the number of paths that BGP is allowed to install can be done as follows:
R1#
R1#conf t
Enter configuration commands, one per line. End with CNTL/Z.
R1(config)#router bgp 100
R1(config-router)#maximum-paths 2
R1(config-router)#end
R1#
With
this configuration in place BGP can now install 2 paths to the
172.16.1.0/24 subnet. The path that R2 and R3 advertise are identical in
the best path selection process up to step 9, so they're both
candidates for installation in the Routing Table.
R1#sh ip bgp 172.16.1.0/24
BGP routing table entry for 172.16.1.0/24, version 4
Paths: (2 available, best #2, table default)
Multipath: eBGP
Advertised to update-groups:
5
Refresh Epoch 4
200 300
12.12.12.2 from 12.12.12.2 (24.24.24.2)
Origin IGP, localpref 100, valid, external, multipath(oldest)
Refresh Epoch 3
200 300
13.13.13.3 from 13.13.13.3 (34.34.34.3)
Origin IGP, localpref 100, valid, external, multipath, best
R1#
Now
when BGP does the recursive routing lookup for the Next Hop addresses
of each path it will use both next hop interfaces to load balance
traffic via the IGP (in this case EIGRP):
R1#sh ip cef 172.16.1.0/24
172.16.1.0/24
nexthop 12.12.12.2 FastEthernet0/0
nexthop 13.13.13.3 FastEthernet0/1
R1#
Now both interfaces are used to forward traffic.
Final Thoughts
The
advantage that BGP has over all other routing protocols is the ability
to control path selection based on different routing policies. The
policy to apply to influence traffic into and out of your network should
be based on what fits within your existing deployment and what you find
easiest to manage.
