BGP is a protocol which performs routing information exchange among routers to determine the optimal paths for the traffic flow. A BGP router forms a neighbor relationship by connecting to its neighbors and exchanging the routes, once the connection is established.
BGP Best Path Selection Algorithm is used to choose and install the best routes into the router’s routing table. Due to the fact that the full Internet BGP routing table includes way over 400,000 routes and because BGP router can receive numerous copies of those routes from various providers, it has to compare the multiple BGP routing tables and choose the optimal route on the router.
If there are no specific settings that can affect the outcome, BGP Best Path Selection Algorithm determines the best route by selecting the shortest path to the destination. An Autonomous System is a single network or a set of networks and routers, which are under the control of one administrative entity. Nevertheless, network administrators frequently manipulate such options as local preference, lowest multi-exit discriminator and weight.
The list of the selection criteria is presented below in the same order in which BGP uses them to select the optimal routes to be injected into the IP Routing table:
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. The weight parameter can be set either through neighbor command, route maps or via the AS-path access list.
2) Local Preference — this criterion indicates which route has local preference and BGP selects the one with the highest preference. Local Preference default is 100.
3) Network or Aggregate — this criterion chooses the path that was originated locally via an aggregate or a network, as the aggregation of certain routes in one is quite effective and helps to save a lot of space on the network.
4) Shortest AS_PATH — this criterion is used by BGP only in case it detects two similar paths with nearly the same local preference, weight and locally originated or aggregate addresses.
5) Lowest origin type — this criterion assigns higher preference to Exterior Gateway Protocol (EGP) and lower preference to Interior Gateway Protocol (IGP).
6) Lowest multi-exit discriminator (MED) — this criterion, representing the external metric of a route, gives preference to the lower MED value.
7) eBGP over iBGP — just like the “Lowest origin type” criterion, this criterion prefers eBGP rather than iBGP.
8) Lowest IGP metric — this criterion selects the path with the lowest IGP metric to the BGP next hop.
9) Multiple paths — this criterion serves as indication whether multiple routes need to be installed in the routing table.
10) External paths — out of several external paths, this criterion selects the first received path.
11) Lowest router ID — this criterion selects the path which connects to the BGP router that has the lowest router ID.
12) Minimum cluster list — in case multiple paths have the same router ID or originator, this criterion selects the path with the minimum length of the cluster list.
13) Lowest neighbor address — this criterion selects the path, which originates from the lowest neighbor address.
BGP best path selection algorithm also provides a mechanism to discard paths that are not considered as candidates for the best path. The following Paths will be discarded:
- “Not synchronized” marked paths;
- Paths without access to the NEXT_HOP;
- Paths originating from an eBGP neighbor, in case the local AS is shown in the AS-PATH
- In the case that BGP enforce-first-as is enabled and the update does not contain the AS of the neighbor as the first AS number in the AS-SEQUENCE;
- “Received-only” marked paths;
Best Path selection algorithm makes basic decisions to select the best routes to be installed into the routing table. Currently, BGP is considered to be a standard protocol for the inter-domain information exchange.