×

Warning message

  • Cisco Support Forums is in Read Only mode while the site is being migrated.
  • Cisco Support Forums is in Read Only mode while the site is being migrated.

Understanding BGP Best Path Selection & Manipulation

Document

Mon, 03/10/2014 - 13:17
Feb 12th, 2013
User Badges:

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.

 

BGP Best Path Visio.png

 

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.

Loading.
Joksan Flores-Rivera (not verified) Wed, 02/20/2013 - 04:29
User Badges:

Excelent document, I really liked that is is very concise. If someone needs to learn BGP path selection, I think this document is a great starting point. It is also very good for refreshing what you already know. Thanks James!

Dennis McLaughlin Tue, 11/19/2013 - 18:34
User Badges:
  • Cisco Employee,

Great doc Brooks. Very detailed and easy to follow along. Keep up the good work.

Thanks,

Actions

This Document

Related Content