BGP Path Selection Algorithm
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.
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.
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:
On Cisco Devices :
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.
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.
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 the bgp best path 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.
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.
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. - THE MED of paths that are received from a neighbor with
a MED of 4,294,967,295 are considered valid and are inserted into BGP
table with effect to Codes fixed for Cisco bug ID CSCef34800. - 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.
missing-as-worst , the paths are assigned a MED of 4,294,967,294.
If you have enabled bgp bestpath med
missing-as-worst , the paths are assigned a MED of 4,294,967,295 with
effect to Codes fixed for Cisco bug ID CSCef34800.
missing-as-worst , the paths are assigned a MED of 4,294,967,295 with
effect to Codes fixed for Cisco bug ID CSCef34800.
- The bgp deterministic-med command can also
influence this step.
Refer to How BGP Routers Use the Multi-Exit
Discriminator for Best Path Selection for a demonstration.
Discriminator for Best Path Selection for a demonstration.
7- 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.
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.
8- Prefer the path with the lowest IGP metric to the BGP next hop. Continue, even if bestpath is already selected.
9- Determine if multiple paths require installation in the routing table for BGP Multipath. Continue, if bestpath is not yet selected.
10- 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).
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.
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.
example, the neighbor that offers the path goes down.
11- Prefer the route
that comes from the BGP router with the lowest router ID.
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 thebgp router-id command to manually set the router ID.
highest IP address on the router, with preference given to loopback addresses.
Also, you can use thebgp 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.
contains route reflector (RR) attributes, the originator ID is substituted for
the router ID in the path selection process.
12- If the originator or
router ID is the same for multiple paths, prefer the path with the minimum
cluster list length.
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.
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.
13- 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.
On Huawei Devices:
1-
Prefers the route with the largest PreVal.
Prefers the route with the largest PreVal.
PrefVal
is a Huawei-specific parameter. It is valid only on the device where it is
configured.
is a Huawei-specific parameter. It is valid only on the device where it is
configured.
2-
Prefers the route with the highest Local_Pref.
Prefers the route with the highest Local_Pref.
A
route without Local_Pref is considered to have had the value set by using
the default local-preference command or to have a value of 100 by
default.
route without Local_Pref is considered to have had the value set by using
the default local-preference command or to have a value of 100 by
default.
3-
Prefers a locally originated route. A locally originated route takes precedence
over a route learned from a peer.
Prefers a locally originated route. A locally originated route takes precedence
over a route learned from a peer.
Locally
originated routes include routes imported by using the network command
or the import-route command, manually aggregated routes, and
automatically summarized routes.
originated routes include routes imported by using the network command
or the import-route command, manually aggregated routes, and
automatically summarized routes.
a.
A summarized route is preferred. A summarized route takes
precedence over a non-summarized route.
A summarized route is preferred. A summarized route takes
precedence over a non-summarized route.
b.
A route obtained by using the aggregate command is
preferred over a route obtained by using the summary automaticcommand.
A route obtained by using the aggregate command is
preferred over a route obtained by using the summary automaticcommand.
c.
A route imported by using the network command is
preferred over a route imported by using the import-route command.
A route imported by using the network command is
preferred over a route imported by using the import-route command.
4-
Prefers the route with the shortest AS_Path.
Prefers the route with the shortest AS_Path.
·
The AS_CONFED_SEQUENCE and AS_CONFED_SET are not included in the
AS_Path length.
The AS_CONFED_SEQUENCE and AS_CONFED_SET are not included in the
AS_Path length.
·
An AS_SET counts as 1, no matter how many ASs are in the set.
An AS_SET counts as 1, no matter how many ASs are in the set.
·
After the bestroute as-path-neglect command is run, the
AS_Path attributes of routes are not compared in the route selection process.
After the bestroute as-path-neglect command is run, the
AS_Path attributes of routes are not compared in the route selection process.
5-
Prefers the route with the highest Origin type. IGP is higher than EGP, and EGP
is higher than Incomplete.
Prefers the route with the highest Origin type. IGP is higher than EGP, and EGP
is higher than Incomplete.
6-
Prefers the route with the lowest Multi Exit Discriminator (MED).
Prefers the route with the lowest Multi Exit Discriminator (MED).
·
The MEDs of only routes from the same AS but not a confederation
sub-AS are compared. MEDs of two routes are compared only when the first AS
number in the AS_SEQUENCE (excluding AS_CONFED_SEQUENCE) is the same for the
two routes.
The MEDs of only routes from the same AS but not a confederation
sub-AS are compared. MEDs of two routes are compared only when the first AS
number in the AS_SEQUENCE (excluding AS_CONFED_SEQUENCE) is the same for the
two routes.
·
A route without any MED is assigned a MED of 0, unless the bestroute
med-none-as-maximum command is run. If thebestroute med-none-as-maximum command
is run, the route is assigned the highest MED of 4294967295.
A route without any MED is assigned a MED of 0, unless the bestroute
med-none-as-maximum command is run. If thebestroute med-none-as-maximum command
is run, the route is assigned the highest MED of 4294967295.
·
After compare-different-as-med command is run, the MEDs
in routes sent from peers in different ASs are compared. Do not use this
command unless it is confirmed that different ASs use the same IGP and route
selection mode. Otherwise, a loop may occur.
After compare-different-as-med command is run, the MEDs
in routes sent from peers in different ASs are compared. Do not use this
command unless it is confirmed that different ASs use the same IGP and route
selection mode. Otherwise, a loop may occur.
·
If the bestroute med-confederation command is run, MEDs
are compared for routes that consist only of AS_CONFED_SEQUENCE. The first AS
number in the AS_CONFED_SEQUENCE must be the same for the routes.
If the bestroute med-confederation command is run, MEDs
are compared for routes that consist only of AS_CONFED_SEQUENCE. The first AS
number in the AS_CONFED_SEQUENCE must be the same for the routes.
·
After the deterministic-med command is run, routes are
not selected in the sequence in which routes are received.
After the deterministic-med command is run, routes are
not selected in the sequence in which routes are received.
7-
Prefers EBGP routes over IBGP routes.
Prefers EBGP routes over IBGP routes.
EBGP
is higher than IBGP, IBGP is higher than LocalCross, and LocalCross is higher
than RemoteCross.
is higher than IBGP, IBGP is higher than LocalCross, and LocalCross is higher
than RemoteCross.
If
the ERT of a VPNv4 route in the routing table of a VPN instance on a PE matches
the IRT of another VPN instance on the PE, the VPNv4 route will be added to the
routing table of the second VPN instance. This is called LocalCross. If the ERT
of a VPNv4 route from a remote PE is learned by the local PE and matches the
IRT of a VPN instance on the local PE, the VPNv4 route will be added to the
routing table of that VPN instance. This is called RemoteCross.
the ERT of a VPNv4 route in the routing table of a VPN instance on a PE matches
the IRT of another VPN instance on the PE, the VPNv4 route will be added to the
routing table of the second VPN instance. This is called LocalCross. If the ERT
of a VPNv4 route from a remote PE is learned by the local PE and matches the
IRT of a VPN instance on the local PE, the VPNv4 route will be added to the
routing table of that VPN instance. This is called RemoteCross.
8-
Prefers the route with the lowest IGP metric to the BGP next hop.
Prefers the route with the lowest IGP metric to the BGP next hop.
NOTE:
Assume that load balancing is configured. If the
preceding rules are the same and there are multiple external routes with the
same AS_Path, load balancing will be performed based on the number of
configured routes.
preceding rules are the same and there are multiple external routes with the
same AS_Path, load balancing will be performed based on the number of
configured routes.
9-
Prefers the route with the shortest Cluster_List.
Prefers the route with the shortest Cluster_List.
10-
Prefers the route advertised by the CX device with the smallest
router ID.
Prefers the route advertised by the CX device with the smallest
router ID.
NOTE:
If routes carry the Originator_ID, the
originator ID is substituted for the router ID during route selection. The
route with the smallest Originator_ID is preferred.
originator ID is substituted for the router ID during route selection. The
route with the smallest Originator_ID is preferred.
11-
Prefers the route learned from the peer with the smallest address if the IP
addresses of peers are compared in the route selection process.
Prefers the route learned from the peer with the smallest address if the IP
addresses of peers are compared in the route selection process.
On Juniper
Devices:
Devices:
1- Verify that the next
hop can be resolved.
hop can be resolved.
2- Choose the path with
the lowest preference value (routing protocol process preference).
the lowest preference value (routing protocol process preference).
Routes that are not
eligible to be used for forwarding (for example, because they were rejected by
routing policy or because a next hop is inaccessible) have a preference of –1
and are never chosen.
eligible to be used for forwarding (for example, because they were rejected by
routing policy or because a next hop is inaccessible) have a preference of –1
and are never chosen.
3- Prefer the path with
higher local preference.
higher local preference.
For non-BGP paths,
choose the path with the lowest preference2 value.
choose the path with the lowest preference2 value.
4- If the accumulated
interior gateway protocol (AIGP) attribute is enabled, prefer the path with the
lower AIGP attribute.
interior gateway protocol (AIGP) attribute is enabled, prefer the path with the
lower AIGP attribute.
5- Prefer the path with
the shortest autonomous system (AS) path value (skipped if the as-path-ignore statement
is configured).
the shortest autonomous system (AS) path value (skipped if the as-path-ignore statement
is configured).
A confederation segment
(sequence or set) has a path length of 0. An AS set has a path length of 1.
(sequence or set) has a path length of 0. An AS set has a path length of 1.
6- Prefer the route with
the lower origin code.
the lower origin code.
Routes learned from an
IGP have a lower origin code than those learned from an exterior gateway
protocol (EGP), and both have lower origin codes than incomplete routes (routes
whose origin is unknown).
IGP have a lower origin code than those learned from an exterior gateway
protocol (EGP), and both have lower origin codes than incomplete routes (routes
whose origin is unknown).
7- Prefer the path with
the lowest multiple exit discriminator (MED) metric.
the lowest multiple exit discriminator (MED) metric.
Depending on whether
nondeterministic routing table path selection behavior is configured, there are
two possible cases:
nondeterministic routing table path selection behavior is configured, there are
two possible cases:
·
If nondeterministic routing table path selection behavior is not
configured (that is, if the path-selection cisco-nondeterministic statement
is not included in the BGP configuration), for paths with the same neighboring
AS numbers at the front of the AS path, prefer the path with the lowest MED
metric. To always compare MEDs whether or not the peer ASs of the compared
routes are the same, include the path-selection always-compare-med statement.
If nondeterministic routing table path selection behavior is not
configured (that is, if the path-selection cisco-nondeterministic statement
is not included in the BGP configuration), for paths with the same neighboring
AS numbers at the front of the AS path, prefer the path with the lowest MED
metric. To always compare MEDs whether or not the peer ASs of the compared
routes are the same, include the path-selection always-compare-med statement.
·
If nondeterministic routing table path selection behavior is
configured (that is, the path-selection cisco-nondeterministic statement
is included in the BGP configuration), prefer the path with the lowest MED
metric.
If nondeterministic routing table path selection behavior is
configured (that is, the path-selection cisco-nondeterministic statement
is included in the BGP configuration), prefer the path with the lowest MED
metric.
Confederations are not
considered when determining neighboring ASs. A missing MED metric is treated as
if a MED were present but zero.
considered when determining neighboring ASs. A missing MED metric is treated as
if a MED were present but zero.
|
|
Note: MED
comparison works for single path selection within an AS (when the route does not include an AS path), though this usage Is uncommon. |
By default, only the
MEDs of routes that have the same peer autonomous systems (ASs) are compared.
You can configure routing table path selection options to obtain different
behaviors.
MEDs of routes that have the same peer autonomous systems (ASs) are compared.
You can configure routing table path selection options to obtain different
behaviors.
8- Prefer strictly
internal paths, which include IGP routes and locally generated routes (static,
direct, local, and so forth).
internal paths, which include IGP routes and locally generated routes (static,
direct, local, and so forth).
9- Prefer strictly
external BGP (EBGP) paths over external paths learned through internal BGP
(IBGP) sessions.
external BGP (EBGP) paths over external paths learned through internal BGP
(IBGP) sessions.
10- Prefer the path
whose next hop is resolved through the IGP route with the lowest metric.
whose next hop is resolved through the IGP route with the lowest metric.
|
|
Note: A
path is considered a BGP equal-cost path (and will be used for forwarding) if a tie-break is performed after the previous step. All paths with the same neighboring AS, learned by a multipath-enabled BGP neighbor, are considered. BGP
multipath does not apply to paths that share the same MED-plus-IGP cost yet differ in IGP cost. Multipath path selection is based on the IGP cost metric, even if two paths have the same MED-plus-IGP cost. |
11- If both paths are
external, prefer the currently active path to minimize route-flapping. This
rule is not used if any one of the following conditions is true:
external, prefer the currently active path to minimize route-flapping. This
rule is not used if any one of the following conditions is true:
·
path-selection external-router-id is configured.
path-selection external-router-id is configured.
·
Both peers have the same router ID.
Both peers have the same router ID.
·
Either peer is a confederation peer.
Either peer is a confederation peer.
·
Neither path is the current active path.
Neither path is the current active path.
12- Prefer a primary
route over a secondary route. A primary route is one that belongs to the
routing table. A secondary route is one that is added to the routing table
through an export policy.
route over a secondary route. A primary route is one that belongs to the
routing table. A secondary route is one that is added to the routing table
through an export policy.
13- Prefer the path from
the peer with the lowest router ID. For any path with an originator ID
attribute, substitute the originator ID for the router ID during router ID
comparison.
the peer with the lowest router ID. For any path with an originator ID
attribute, substitute the originator ID for the router ID during router ID
comparison.
14- Prefer the path with
the shortest cluster list length. The length is 0 for no list.
the shortest cluster list length. The length is 0 for no list.
15-
Prefer the path from the peer with the lowest peer IP address.
Prefer the path from the peer with the lowest peer IP address.
(Visited 4,882 times, 1 visits today)