BGP Best Path Selection Algorithm of Cisco IOS & Hidden Commands

Because most online material / books does not summarize the full algorithm or does not summarize all the steps it is harder to troubleshoot a BGP issue. In order to change the routing in your desired way, you should understand why the current best path is selected.

Here is a summary of all the 13 comparison steps of the best path selection algorithm of Cisco IOS..

(01) Weight (highest preferred,)
(02) Local Preference (highest preferred)
(03) Origination (local originate, next-hop 0.0.0.0 preferred)
(04) AS Path (shortest preferred)
(05) Origin Code (i preferred over ?)
(06) MED (lowest preferred, compared if routes learned from same AS by default)
(07) Path Type (external preferred over internal)
(08) IGP metric to Next-hop (lowest preferred, if equal go to next step)
(09) Multipath configured check (if configured, install in local routing table and go to next step)
(10) Age of the Route (oldest preferred, compares for external routes only)
(11) Router ID (lowest preferred, Originator ID is used as router-id for routes learned from RRs)
(12) Cluster List length (shortest preferred, learned from clients preferred over non-clients)
(13) Neighbor ID (lowest preferred)

Following are some facts associated with the attributes and links to some practical examples where they are used to manipulate routing..

Weight
 - Default Weight is 32768 for locally originated routes
 - Cisco proprietary
 - Locally significant
BGP Path Selection by Weight

Local Preference
 - Default Weight is 100 for all iBGP/eBGP originated routes
 - Customized Local Preference is not advertised to eBGP peers
 - Carried through confederation eBGP
BGP Path Selection by Local Preference

Origination
 - Locally originated routes have next-hop 0.0.0.0
 - Include routes from network / aggregate-address commands, redistribution
BGP Path Selection by Origination

AS Path
BGP Path Selection by AS-Path

Origin Code
 - Status codes i>e>?
BGP Path Selection by Origin Code

MED
 - Only compared for prefixes learned by same AS by default
BGP Path Selection by MED (Multi-Exit Discriminator)
BGP Path Selection by MED for Routes Learned from Different ASes

Paths
BGP Path Selection by Path Type (eBGP vs iBGP) and Hidden Local Preference

IGP metric to Next-hop

Multipath
 - If the IGP metric to the next hop is equal and if configured to use multipath, the routes will be             installed in routing table of the local router.
 - But will select one best route to advertise neighbors through next steps

Age of the Route
 - Compared only for eBGP routes.

Router ID
 - Originator ID is used as router-id for routes learned from RRs
BGP Path Selection by Router ID

Cluster List length
 - Learned from clients preferred over non-clients

Neighbor ID


Commands to Change the Default Behavior

AS-Path
 - Hidden command to ignore AS path lookup
 - bgp bestpath as-path ignore

MED
 - bgp always-compare-med
 - bgp bestpath med-confed
   compares MED for routes locally originated in the confederation
 - bgp bestpath med missing-as-worst
   assign MED of 4294967294 to null MED
 - bgp deterministic med
   compare MED against all possible paths

IGP Metric
 - bgp bestpath igp-metric ignore
 - Introduced in IOS-XE 3.4S

Multipath
 - Hidden command to allow multi-path if AS_PATH is not the same (has to be same length)
    bgp bestpath as-path multipath-relax
 - maximum-paths [ibgp|eibgp] is used to  configure load balancing

Router ID
 - no bgp bestpath compare-router id


Further Reference:
https://www.cisco.com/c/en/us/support/docs/ip/border-gateway-protocol-bgp/13753-25.html

"FD is Infinity" Problem of EIGRP which Stops Advertising Routes

Refer the following scenario where AS 100 and AS 200 are BGP Autonomous Systems and EIGRP is configured on all 3 routers to be in a same EIGRP Autonomous System to advertise everything on every link (using network 0.0.0.0 command for ease of configuration on lab) for underlay routing.

R1 e0/0:192.168.12.1

R2 e0/0:192.168.12.2

R3 e0/0:192.168.13.3

L0 of R1: 1.1.1.1/32

Following are the BGP configuration of routers..

R1(config)#router bgp 100
R1(config-router)#network 1.1.1.1 mask 255.255.255.255
R1(config-router)#neighbor 192.168.12.2 remote-as 200

R2(config)#router bgp 100
R2(config-router)#neighbor 192.168.12.1 remote-as 100

Following are the EIGRP configuration of routers..

R1(config)#router eigrp 100
R1(config-router)#network 0.0.0.0

R2(config)#router eigrp 100
R2(config-router)#network 0.0.0.0

R2(config)#router eigrp 100
R2(config-router)#network 0.0.0.0

Following are the topology tables of the routers..

As you can see, R3 is not learning the 1.1.1.1/32 route from R2 because the FD is Infinity for that route on R2.

Let's examine the topology table entry in R2 for that route to get more info about it..

Looks like there is no Successor for the route. And of course the FD is Infinity, but it shows a composite metric..

To understand why it is showing this problem, let's create a debug and see what happens when the router is going to put it in it's IP routing table..

R2(config)#access-list 1 permit 1.1.1.1 /32
R1#debug ip routing 1

There is the reason, eBGP route has a lower Administrative Distance and the router is going to install it flushing the EIGRP route. Router makes it's EIGRP route to be a route with an Infinite value for it's Feasible Distande (FD) and will stop updating it to it's other neighbors..

If you run debug eigrp fsm (debug for EIGRP Finite State Machine) you will find the actual FD the router make to be this route an infinite..
(click on the image to view in full size)

BGP Path Selection by MED for Routes Learned from Different ASes

MED is the sixth BGP attribute in the list.. Though the abbreviation  stands for Multi-Exit Discriminator it simply means the metric of BGP..

Please go through the following post to learn about MED in BGP and its influence for path selection for the routes learned from same AS.

BGP Path Selection by MED (Multi-Exit Discriminator)

Above example and most of the examples you may find online or in books are created for routes learned for same AS. But in Cisco IOS, MED is not taken in to the consideration if the routes are coming from different ASes.

Let's see such an example..

See the snippet, All are eBGP neighbors and R4 on AS 400 is originating a route 44.44.44.44/32 and propagating to R3 through R1 and R2.


R1 and R2 are configured with route-maps to manually set the MED because they are not originating the prefix and needs advertise the MED to an eBGP neighbor R3..










Following are the configurations of the routers..

By examining the  configuration you can see a low metric is advertised by R2.
Let's see the BGP table of R3,

As you can see, It is chosen the high metric route as the best route..

According to the best path selection algorithm of Cisco IOS,

(01) Weight (highest preferred,)
(02) Local Preference (highest preferred)
(03) Origination ((local originate, next-hop 0.0.0.0 preferred))
(04) AS Path (shortest preferred)
(05) Origin Code (i preferred over ?)
(06) MED (lowest preferred, compared if routes learned from same AS by default)
(07) Path Type (external preferred over internal)
(08) IGP metric to Next-hop (lowest preferred, if equal go to next step)
(09) Multipath configured check (if configured, install in local routing table and go to next step)
(10) Age of the Route (oldest preferred, compares for external routes only)
(11) Router ID (lowest preferred, Originator ID is used as router-id for routes learned from RRs)
(12) Cluster List length (shortest preferred, learned from clients preferred over non-clients)
(13) Neighbor ID (lowest preferred)

In this case if MED is not taken into consideration, all are equal until the Age of the Route. So the 1st learned route should be from the 1.1.1.1 and it is preferred here. This is because the route is learned via 2 ASes and MED is compared for the routes learned via same AS by default..

How ever we can change this behavior by entering the following command in BGP process of R3,

R3(config-router)#bgp always-compare-med

BGP Path Selection by Path Type (eBGP vs iBGP) and Hidden Local Pref.

Path type is the 7th attribute in the list..

External paths are preferred over internal paths..

Let's go through a practical example and see how it is really working..

As illustrated in the diagram, R1 and R2 are in AS 100 and R3 is in AS 300.

EIGRP is configured on all inter router links and Loopback 0s for underlay routing and following snippets show the BGP configuration on  all routers.

Only the Loopback 1 which is 33.33.33.33/32 is configured in R3 and it is advertised to both its eBGP peers.

R1 and R2 will exchange this route via their iBGP neighborship.

Let's see the BGP tables of both R1 and R2 now..

As you can see the best path for 33.33.33.33/32 on both routers is the eBGP learned route. This is because the eBGP route is more preferred than the iBGP route. But you can see the Local Preference is 100 for the iBGP route and as we know the Local Preference should be considered before the Path Type; shouldn't the iBGP route be chosen to be the best path?

This leads to a confusion as some people think eBGP route is more preferred over the iBGP route because eBGP has AD of 20 and iBGP has AD of 200 and in a case like this BGP best path selection process is ignored.

But this is not true..

Then what is happening here? Let's query the route attributes on the BGP rib for this route on R2,

As you can see there is a hidden Local Preference value and it is is also 100. Which means it will narrow down to the 7th attribute and eBGP route is preferred over iBGP route..

To verify this theory I am changing the Local Preference of R1 advertising routes and see what happens..

R1(config)#router bgp 100
R1(config-router)#bgp default local-preference 500

Now the Local Preference is higher from iBGP route and it is chosen..

To understand the Local Preference route selection please go here.

Conclusion:-

Note that if you change the Local Preference from the eBGP neighbor, it will not make a change in R1 or R2 as Local Preference is advertised only to iBGP peers. But you can see that for all the routes learned (regardless of type of the neighbor), Local Preference is set to 100 by default even though it is not showing in the BGP table for eBGP routes but it is also taken in to consideration while calculating the best path..

A Note on Regular Expressions Used in Cisco IOS

Regular expressions are commonly used to filter out show commands like show ip bgp and to identify a route in AS-Path Lists.

Character	Meaning
^	start of a string
$	end of a string
[]	range of characters
-	used to specify range ( i.e. [0-9] )
( )	logical grouping
.	any single character
*	repeat previous character zero or more times
+	repeat previous character one or more times
?	repeat previous character zero or one time
_	matches the space between AS numbers
\\	an escape character used for BGP confederations

Some commonly used examples:-

String	Meaning
.*	anything, all prefixes, will match everything
^$	match all prefixes learned from the local AS
^67_	match all prefixes learned from AS 67
_67$	match all prefixes originated in AS 67
_67_	match all prefixes any instance of AS 67
^[0-9]+$	match all prefixesprefixes originated from directly connected ASes

Now let's see the above expressions applied in the following real BGP table..

Expressions are used in the order of the table..

RIP Neighbor Establishing Packets

This is a RIP packet capture when initially forming adjacency. The setup we use is simple and has 2 routers with network 0.0.0.0 command which indicates advertise everything on every link.

Packet flow will be like the following.. (click on the images to view in full size)

It is very simple that only 2 broadcast packets are exchanged to form adjacency. Note that this is RIPv1 because it is the default when we enable RIP on a Cisco router.

Let's see the content of the packet.

Both routers are just broadcasting what they know but does not broadcast back to the same routes learned by neighbor because of the split horizon rule.

Let's enable RIPv2 by entering version 2 process level command on both routers.

Now we can see it uses multicast packets to exchange routing information. Only difference is that it shows the subnet mask.

Download the packet capture from here.

EIGRP Neighbor Establishing Packets

This is an EIGRP packet capture when initially forming adjacency. The setup we use is simple and has 2 routers with network 0.0.0.0 command which indicates advertise everything on every link.

Packet flow will be like the following.. (click on the images to view in full size)

1st let's analyze a Hello packet before the adjacency happen.

As you can see the K values are there and looks like by default it is supporting the wide metrics because K6 is there.

We can see there are 2 unicast Update packets exchanging. Let's see what is in it.

Actually nothing important like routing information is not there.. Looks like both routers are exchanging them for some other reason than exchanging routes.

Now let's see what is inside the 14th packet which is sent to the multicast address as an Update.

Now it is sending it's routes out. If we expand one route we can find all the valuable information about that route like metrics, next-hop, DUAL settings used to calculate the metric etc..
















Now we can see R2 is also sending a multicast Update. Let's see what is inside it..

Same routes which is advertised by R1? Well by split horizon rule it should not advertise the same routes to the neighbor it learned but looks like multicast does not care it. Anyway then the adjacency
is formed and Hello packets are exchanged to maintain the adjacency.

Looks like something actually does not work like in the book 😐

Download the packet capture from here.

EIGRP Route Filtering using Prefix-Lists

Distribute lists are used to filter routing updates in routing protocols. Actually it is just an access-list or prefix list to capture traffic and bind it with distribute list command to filter exchanging route updates inbound or outbound with a neighboring router or within the process itself. Note that this won't affect locally originated EIGRP routes.

Setup is simple, there are 4 loopback interfaces on R1.

I am going to start a basic EIGRP process in both R1 & R2 which runs on all the interfaces..



R1(config)#router eigrp 10
R1(config-router)#network 0.0.0.0

R2(config)#router eigrp 10
R2(config-router)#network 0.0.0.0

Above commands will result the following output in R2's routing table..

All the loopback interfaces of R1 are advertised to R2 by R1 in EIGRP process.

I am creating a prefix-list to capture the routes which starts from 192.168.0.0 and has the prefix length greater than or equal to /25

R1(config)#ip prefix-list TEST seq 10 deny 192.168.0.0/16 ge 25
R1(config)#ip prefix-list TEST seq 20 permit 0.0.0.0/0 le 32

R1(config)#router eigrp 10
R1(config-router)#distribute-list prefix TEST out ethernet 0/0

Note:-

If we didn't specify the exact interface, it will by default be applied to all the interfaces..
If we wanted to configure the distribute list on R2, we would have used it inbound like the following..

R2(config)#ip prefix-list TEST seq 10 deny 192.168.0.0/16 ge 25
R2(config)#ip prefix-list TEST seq 20 permit 0.0.0.0/0 le 32

R2(config)#router eigrp 10
R2(config-router)#distribute-list prefix TEST in

Routes will not be in the R2's topology table even.

Prefix lists can also be used to filter routes from a specific gateway (neighbor).

In this topology there is only 1 neighbor to the R2, but the logic can apply for a setup of several neighbors. Here the prefix match the neighbor address and gateway command is used.

R2(config)#ip prefix-list NOT-FROM-R1 seq 10 deny 10.1.1.1/32
R2(config)#ip prefix-list NOT-FROM-R1 seq 20 permit 0.0.0.0/0 le 32

R2(config)#router eigrp 10
R2(config-router)#distribute-list prefix gateway NOT-FROM-R1 in

Also note that;
R2(config-router)#distribute-list prefix PREFIX-LIST-1 gateway PREFIX-LIST-2 in

will filter updates and gateway independently. Routing updates permitted from PREFIX-LIST-1 and the updates from gateways which are permitted from PREFIX-LIST-2 will be in the topology table.
Note that this is different from the filtering using extended ACLs where it can filter a specific route from a specific neighbor.

EIGRP Route Filtering using Access-Lists

Distribute lists are used to filter routing updates in routing protocols. Actually it is just an access-list or prefix list to capture traffic and bind it with distribute list command to filter exchanging route updates inbound or outbound with a neighboring router or within the process itself. Note that this won't affect locally originated EIGRP routes.

Setup is simple, there are 4 loopback interfaces on R1.

I am going to start a basic EIGRP process in both R1 & R2 which runs on all the interfaces..



R1(config)#router eigrp 10
R1(config-router)#network 0.0.0.0

R2(config)#router eigrp 10
R2(config-router)#network 0.0.0.0

Above commands will result the following output in R2's routing table..

All the loopback interfaces of R1 are advertised to R2 by R1 in EIGRP process.

Filtering using an Standard ACL

If we don't want a specific route (ex:- 192.168.3.0/26) to be advertised to R2, we will simply create an ACL to capture that route and apply in distribute list command..

R1(config)#access-list 10 deny 192.168.3.0 0.0.0.63
R1(config)#access-list 10 permit any

R1(config)#router eigrp 10
R1(config-router)#distribute-list 10 out ethernet 0/0

Now we can see 192.168.3.0/26 is no longer advertised to R2.

Note:-

If we didn't specify the exact interface, it will by default be applied to all the interfaces..
If we wanted to configure the distribute list on R2, we would have used it inbound like the following..


R1(config)#access-list 10 deny 192.168.3.0 0.0.0.63
R1(config)#access-list 10 permit any

R1(config)#router eigrp 10
R1(config-router)#distribute-list 10 in

Either way it will filter the route and will not put in the R2's topology table even.

Filtering using an Extended ACL

In this case it is bit different, now the source field is the sourcing neighbor and the destination field is the route. So that means we can filter routes from a specific neighbor using an extended ACL.

R2(config)#access-list 101 deny ip host 10.1.1.1 192.168.3.0 0.0.0.63
R2(config)#access-list 101 permit ip any any

R2(config)#router eigrp 10
R2(config-router)#distribute-list 101 in

Result will be the same for this example but when we have several neighbors this can be a useful application.