BGP Best Path Selection Algorithm

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.

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:
1.Paths that are marked as not synchronized in the show ip bgp longer-prefixes output
2.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.
Note: Synchronization is disabled by default in Cisco IOS Software Release 12.2(8)T and later.
3.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.
4.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). The same applies to any path that is denied by a routing policy that is implemented via access, prefix, AS_PATH, or community lists, unless you have configured soft-reconfiguration inbound for the neighbor.
5.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, the router sends a notification and closes the session.
6.Paths that are marked as (received-only) in the show ip bgp longer-prefixes output
The policy has rejected these paths. However, the router has stored the paths because you have configured soft-reconfiguration inbound for the neighbor that sends the path.
How the Best Path Algorithm Works
BGP 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 to determine the best path:
1.Prefer the path with the highest WEIGHT.
Note: WEIGHT is a Cisco-specific parameter. It is local to the router on which it is configured.
2.Prefer the path with the highest LOCAL PREF.
Note: A path without LOCAL_PREF is considered to have had the value set with the bgp default local-preference command, or to have a value of 100 by default.
3.Prefer the path that was locally originated via a network or aggregate BGP subcommand or through redistribution from an IGP.
Local paths that are sourced by the network or redistribute commands are preferred over local aggregates that are sourced by the aggregate address command.
4.Prefer the path with the shortest AS_PATH.
Note: Be aware of these items:
This step is skipped if you have configured thebgp best as-path ignore command.
An AS_SET counts as 1, no matter how many ASs are in the set.
The AS_CONFED_SEQUENCE and AS_CONFED_SET are not included in the AS_PATH length.
5.Prefer the path with the lowest origin type.
Note: IGP is lower than Exterior Gateway Protocol (EGP), and EGP is lower than INCOMPLETE.
6.Prefer the path with the lowest multi -exit discriminator(MED).
Note: Be aware of these items:
This comparison only occurs if the first (the neighboring) AS is the same in the two paths. Any confederation sub-ASs are ignored.
In other words, MEDs are compared only if the first AS in the AS_SEQUENCE is the same for multiple paths. Any preceding AS_CONFED_SEQUENCE is ignored.
If bgp always-compare-med is enabled, MEDs are compared for all paths.
You must disable this option over the entire AS. Otherwise, routing loops can occur.
If bgp bestpath med-confed is enabled, MEDs are compared for all paths that consist only of AS_CONFED_SEQUENCE.
These paths originated within the local confederation.
THE MED of paths that are received from a neighbor with a MED of 4,294,967,295 is changed before insertion into the BGP table. The MED changes to to 4,294,967,294.
Paths received with no MED are assigned a MED of 0, unless you have enabled bgp bestpath med missing - as - worst .
If you have enabled bgp bestpath med missing-as-worst, the paths are assigned a MED of 4,294,967,294.
The bgp deterministic med command can also influence this step.

Prefer eBGP over iBGP paths.
If bestpath is selected, go to Step 9 (multipath).
Note: Paths that contain AS_CONFED_SEQUENCE and AS_CONFED_SET are local to the confederation. Therefore, these paths are treated as internal paths. There is no distinction between Confederation External and Confederation Internal.
7.Prefer the path with the lowest IGP metric to the BGP next hop.
Continue, even if bestpath is already selected.
8.Determine if multiple paths require installation in the routing table for BGP Multipath.
Continue, if bestpath is not yet selected.
9.When both paths are external, prefer the path that was received first (the oldest one).
This step minimizes route-flap because a newer path does not displace an older one, even if the newer path would be the preferred route based on the next decision criteria (Steps 11, 12, and 13).
Skip this step if any of these items is true:
You have enabled the bgp best path compare-routerid command.
Note: Cisco IOS Software Releases 12.0.11S, 12.0.11SC, 12.0.11S3, 12.1.3, 12.1.3AA, 12.1.3.T, and 12.1.3.E introduced this command.
The router ID is the same for multiple paths because the routes were received from the same router.
There is no current best path.
The current best path can be lost when, for example, the neighbor that offers the path goes down.
10.Prefer the route that comes from the BGP router with the lowest router ID.
The router ID is the highest IP address on the router, with preference given to loopback addresses. Also, you can use the bgp router-id command to manually set the router ID.
Note: If a path contains route reflector (RR) attributes, the originator ID is substituted for the router ID in the path selection process.
11.If the originator or router ID is the same for multiple paths, prefer the path with the minimum cluster list length.
This is only present in BGP RR environments. It allows clients to peer with RRs or clients in other clusters. In this scenario, the client must be aware of the RR-specific BGP attribute.
12.Prefer the path that comes from the lowest neighbor address.
This address is the IP address that is used in the BGP neighbor configuration. The address corresponds to the remote peer that is used in the TCP connection with the local router.

Customize the Path Selection Process
The 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 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 bgp bestpath cost-community ignore command.
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.
Currently, only the IGP_COST point of insertion is implemented. 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 Algorthm Works.

BGP Multipath
BGP 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, according to the algorithm, and advertises this best path to its neighbors.
These are the BGP Multipath features:
eBGP Multipath—maximum-paths n
iBGP Multipath—maximum-paths ibgp n
eiBGP Multipath—maximum-paths eibgp n
In order to be candidates for multipath, paths to the same destination need to have these characteristics equal to the best-path characteristics:
Weight
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.
These are the additional requirements for eBGP multipath:
The path should be learned from an external or confederation-external neighbor (eBGP).
The IGP metric to the BGP next hop should be equal to the best-path IGP metric.
These are the additional requirements for iBGP multipath:
The path should be learned from an internal neighbor (iBGP).
The IGP metric to the BGP next hop should be equal to the best-path IGP metric, unless the router is configured for unequal-cost 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 Bandbidth.
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.

OSPF-Build an OSPF network, version 1.0

OSPF Definition: Open Shortest Path First (OSPF), is a routing protocol used to determine the correct route for packets within IP networks. It was designed by the Internet Engineering Task Force to serve as an Interior Gateway Protocol replacing RIP.

Advantages of OSPF:

Changes in an OSPF network are propagated quickly.

OSPF is heirarchical, using area 0 as the top as the heirarchy.

OSPF is a Link State Algorith

OSPF supports Variable Length Subnet Mask(VLSM)
OSPF uses multicasting within areas.

After initialization, OSPF only sends updates on routing table sections which have changed, it does not send the entire routing table.

Using areas, OSPF networks can be logically segmented to decrease the size of routing tables. Table size can be further reduced by using route summarization.

OSPF is an open standard, not related to any particular vendor.

Disadvantages of OSPF:

OSPF is very processor intensive.

OSPF maintains multiple copies of routing information, increasing the amount of memory needed.
Using areas, OSPF can be logically segmented (this can be a good thing and a bad thing).

OSPF is not as easy to learn as some other protocols.

In the case where an entire network is running OSPF, and one link within it is "bouncing" every few seconds, OSPF updates would dominate the network by informing every other router every time the link changed state (I've done this).

OSPF routers check the status of other routers on the network by sending a small hello packet at regular intervals. If a router does not respond to the hello packet, it is assumed dead, and routing updates are sent to every other router by using a multicaste address.

In the case where there are no network changes, OSPF will use very little bandwidth (only sending hello packets). As soon as there is an outage, however, OSPF will flood the network as the change is sent to every router (and then every router notifies every other router about the change). This system of near silence when possible and flooding when necessary ensures that routing information gets propagated throughout the network as quickly as possible.

It's now time to...

Build an OSPF network, version 1.0

Scenario: Camp Swampy is running out of IP addresses. They have a fully meshed base backbone consisting of five seperate routers, here known as A through E:

Camp Swampy's Base Network Topology

Camp Swampy has been given the Class B network 181.160.0.0. The network uses IGRP as their routing protocol, and they are using an 8 bit subnet mask (255.255.255.0).

Since IGRP does not support VLSM`s , Camp Swampy is forced to use an 8 bit mask throughout their entire network. For networks that contain users, this should be acceptable, but for network connections, such as the network that connects A and B, this is a huge waste of IP ADDRESS. We will rebuild their base network using OSPF for one reason only: To free up IP addresses by using Variable Length Subnet Masks.

This means we are going to have to get into binary, just a little...

Pick a class C equivalent network (in other words, pick a number out of the range available in their third octet), and use it for network connections within their base backbone. In this case, lets use 181.160.254.0. We could use a 14 bit subnet mask, 255.255.255.252 (which would only leave two bits for the host part) to get the maximum number of networks out of the 254 subnet, but that only allows two hosts per network. Since the Camp Swampy admin regularly put sniffers and other devices on their network connections, we need to scale the subnet mask back a bit to 13, 255.255.255.248 (leaves three bits for hosts, a total of 6 possible devices on each net).

You can't use the first or last network to connect to hosts, since the first net is always the network address for the ENTIRE network (for instance, you don't see many IP addresses like 181.160.0.1), and the broadcast address for the last subnetted network is also the broadcast address for the ENTIRE network .

Here's what is entered on the "A" Router to implement the change to OSPF: A-router# config t
Enter configuration commands, one per line. End with CNTL/Z.
A-router(config)# interface e 0 A - B connection
A-router(config-if)# ip address 181.160.254.9 255.255.255.248
A-router(config-if)# exit
A-router(config)# interface e 1 A - C connection
A-router(config-if)# ip address 181.160.254.41 255.255.255.248
A-router(config-if)# exit
A-router(config)# interface e 2 A - D connection
A-router(config-if)# ip address 181.160.254.49 255.255.255.248
A-router(config-if)# exit
A-router(config)# interface e 3 A - E connection
A-router(config-if)# ip address 181.160.254.81 255.255.255.248
A-router(config-if)# exit
A-router(config)# no router igrp 200 turn off igrp routing
A-router(config)# router ospf 1 start ospf routing, Autonomous System # 1
A-router(config)# network 181.160.0.0 0.0.255.255 area 0 entire net is area 0
A-router(config)# ^Z
A-router(config)# write save the configuration

BGP-show ip bgp injected-paths

show ip bgp injected-paths
To display all the injected paths in the BGP routing table, use the show ip bgp injected-paths command in EXEC mode.show ip bgp injected-paths
Syntax Description: This command has no arguments or keywords.
Command Modes EXEC
Examples

BGP As_path Attribute

BGP As_path Attribute

Whenever a route update passes through an AS, the AS number is prepended to that update. The AS_path attribute is actually the list of AS numbers that a route has traversed in order to reach a destination.
An AS−SET is an ordered mathematical set {} of all the ASs that have been traversed. An example of AS−SET is given later.
In the above example, network 190.10.0.0 is advertised by RTB in AS200, when that route traverses AS300 and RTC will append its own AS number to it. So when 190.10.0.0 reaches RTA it will have two AS numbers attached to it: first 200 then 300. So as far as RTA is concerned the path to reach 190.10.0.0 is (300,200).
The same applies for 170.10.0.0 and 180.10.0.0. RTB will have to take path (300,100) i.e. traverse AS300 and then AS100 in order to reach 170.10.0.0. RTC will have to traverse path (200) in order to reach 190.10.0.0 and path (100) in order to reach 170.10.0.0.

eBGP and iBGP

eBGP and iBGP

If an AS has multiple BGP speakers, it could be used as a transit service for other ASs. As you see below, AS200 is a transit AS for AS100 and AS300.
It is necessary to ensure reachability for networks within an AS before sending the information to external ASs. This is done by a combination of internal BGP (iBGP) peering between routers inside an AS and by redistributing BGP information to Internal Gateway Protocols (IGPs) running in the AS.
As far as this paper is concerned, when BGP is running between routers belonging to two different ASs, we call this exterior BGP (eBGP). When BGP is running between routers in the same AS, we call this iBGP.

BGP-How Does BGP Work

How Does BGP Work ?

BGP uses TCP as its transport protocol (port 179). Two BGP routers form a TCP connection between one another (peer routers) and exchange messages to open and confirm the connection parameters.BGP routers exchange network reachability information. This information is mainly an indication of the full paths (BGP AS numbers) that a route should take in order to reach the destination network. This information helps in constructing a graph of ASs that are loop−free and where routing policies can be applied in order to enforce some restrictions on the routing behavior.Any two routers that have formed a TCP connection in order to exchange BGP routing information are called peers, or neighbors. BGP peers initially exchange their full BGP routing tables. After this exchange, incremental updates are sent as the routing table changes. BGP keeps a version number of the BGP table, which should be the same for all of its BGP peers. The version number changes whenever BGP updates the table due to routing information changes. Keepalive packets are sent to ensure that the connection is alive between the BGP peers and notification packets are sent in response to errors or special conditions.

BGP BACKDOOR ATTRIBUTE

BGP BACKDOOR ATTRIBUTE

Consider the above diagram, RTA and RTC are running EBGP, and RTB and RTC are running EBGP. RTA and RTB are running some kind of IGP (RIP, IGRP, etc.). By definition, EBGP updates have a distance of 20 which is lower than the IGP distances. Default distance is 120 for RIP, 100 for IGRP, 90 for EIGRP and 110 for OSPF.

RTA will receive updates about 160.10.0.0 via two routing protocols:

EBGP with a distance of 20 and IGP with a distance higher than 20.

By default, BGP has the following distances, but that could be changed by the distance command:
distance bgp external−distance internal−distance Local−distance

external−distance:20

internal−distance:200

local−distance:200

RTA will pick EBGP via RTC because of the lower distance.

If we want RTA to learn about 160.10.0.0 via RTB (IGP), then we have two options:
Change EBGP's external distance or IGP's distance, which is not recommended.
Use BGP backdoor.

BGP backdoor makes the IGP route the preferred route.

Use the following network address backdoor command.

The configured network is the network that we would like to reach via IGP. For BGP this network will be treated as a locally assigned network except it will not be advertised in BGP updates.

RTA#

router eigrp 10

network 160.10.0.0

router bgp 100

neighbor 2.2.2.1 remote−as 300

network 160.10.0.0 backdoor

Network 160.10.0.0 is treated as a local entry, but is not advertised as a normal network entry.

RTA learns 160.10.0.0 from RTB via EIGRP with distance 90, and also learns it from RTC via EBGP with distance 20. Normally EBGP is preferred, but because of the backdoor command EIGRP is preferred.