Difference between revisions of "Manual:BGP Best Path Selection Algorithm"

From MikroTik Wiki
Jump to: navigation, search
m (How Routers Select the best Path)
 
(11 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 
==Introduction==
 
==Introduction==
Routers running Border Gateway Protocol (BGP) typically receive multiple paths to the destination. The BGP best path selection algorithm decides which is the best path to instal in the IP routing table and use for forwarding traffic.
 
  
Best path algorithm compares routes received by a single BGP instance. Routes installed by different BGP instances are compared by the general algorithm, i.e. route distances are compared and the route with lower distance is preferred.
+
With the full Internet BGP routing table being upward of 300K routes and with a BGP router having the potential to be receiving multiple copies of that routing table from multiple providers, it has to have some way to compare those multiple BGP routing tables and select only the best route to go into the IP routing table on the router. It uses the BGP Best Path Selection Algorithm to do this.
  
==Why Routers Ignore Paths==
+
You should note that MikroTik and Cisco BGP routers have weight as the first criteria in the table where other brands do not.
A router running BGP arranges all paths for the same prefix in a list that is later used to select the best path. Some paths in this list are not considered for the best path selection algorithm. Routers ignore paths in the following circumstances:
 
  
* Paths from an external BGP (eBGP) neighbor if the local autonomous system (AS) appears in the [[BGP_Case_Studies_2#AS_PATH_Attribute|AS_PATH]] attribute.
+
Best path algorithm compares routes received by a <b>single BGP instance</b>. Routes installed by different BGP instances are compared by the general algorithm, i.e. route distances are compared and the route with lower distance is preferred.
  
: Such paths are not even installed in the BGP Routing Information Base (RIB) and thus do not consume memory. The same applies to any path that is discarded ('''action=discard''') by the routing filters.
+
==BEST PATH ALGORITHM==
  
==How Routers Select the best Path==
+
<ol class="bullets">
*Prefer the path with the highest [[BGP_Case_Studies_2#WEIGHT_Attribute|WEIGHT]].
+
<li>Router is ignoring received path if the route is not <b>valid</b>. Route is valid if:
:[[BGP_Case_Studies_2#WEIGHT_Attribute|WEIGHT]] parameter is local to the router on which it is configured. A route without assigned [[BGP_Case_Studies_2#WEIGHT_Attribute|WEIGHT]] have a default value of 0.
+
<ul class="bullets">
 +
<li> NEXT_HOP of the route is valid and reachable
 +
<li> AS_PATH received from external peers does not contain the local AS
 +
<li> route is not rejected by routing filters
 +
</ul>
 +
For more information read [[M:BGP_nexthop_selection_and_validation_in_RouterOS_3.x |nexthop selection and validation]].
  
*Prefer the path with the highest [[BGP_Case_Studies_2#LOCAL_PREF_Attribute|LOCAL_PREF]].
+
<li>The first path received is automatically considered 'best path'. Any further received paths are compared to first received to determine if the new path is better.
:A path without [[BGP_Case_Studies_2#LOCAL_PREF_Attribute|LOCAL_PREF]] have a value of 100 by default.
 
  
*Prefer the path with the shortest [[BGP_Case_Studies_2#AS_PATH_Attribute|AS_PATH]]. (skipped if '''ignore-as-path-len''' set to '''yes''')
+
<li>Prefer the path with the highest <b>WEIGHT</b>.
:The router does not compare [[BGP_Case_Studies_2#AS_PATH_Attribute|AS_PATH]] length if '''ignore-as-path-len''' parameter is set to '''yes''' for the respective BGP instance. Each AS_SET counts as 1, regardless of the set size. The AS_CONFED_SEQUENCE and AS_CONFED_SET are not included in the [[BGP_Case_Studies_2#AS_PATH_Attribute|AS_PATH]] length.
+
:WEIGHT parameter is local to the router on which it is configured. A route without assigned WEIGHT have a default value of 0.
  
*Prefer the path that was locally originated via [[BGP_Case_Studies_1#BGP_Aggregates|aggregate]] BGP subcommand
+
<li>Prefer the path with the highest <b>LOCAL_PREF</b>. It is used only within an AS.
 +
:A path without <b>LOCAL_PREF</b> attribute have a value of 100 by default.
  
*Prefer the path with the lowest origin type.
+
<li>Prefer the path with the shortest <b>AS_PATH</b>. (skipped if [[M:Routing/BGP#Instance | <var>ignore-as-path-len</var>]] set to '''yes''')
:Interior Gateway Protocol (IGP) is lower than Exterior Gateway Protocol (EGP), and EGP is lower than INCOMPLETE
+
: Each <b>AS_SET</b> counts as 1, regardless of the set size. The <b>AS_CONFED_SEQUENCE</b> and <b>AS_CONFED_SET</b> are not included in the <b>AS_PATH</b> length.
  
*Prefer the path with the lowest multi-exit discriminator ([[BGP_Case_Studies_2#MULTI_EXIT_DISC_Attribute|MED]]).
+
<li>Prefer the path that was locally originated via [[M:BGP_Case_Studies#BGP_Aggregates|aggregate]] or [[M:Routing/BGP#Network | BGP network]]
: The router compare [[BGP_Case_Studies_2#MULTI_EXIT_DISC_Attribute|MED]] only for paths that have the same neighboring (leftmost) AS. Paths with now [[BGP_Case_Studies_2#MULTI_EXIT_DISC_Attribute|MED]] are assigned a [[BGP_Case_Studies_2#MULTI_EXIT_DISC_Attribute|MED]] of 0
 
  
*Prefer eBGP over iBGP paths
+
<li>Prefer the path with the lowest <b>ORIGIN</b> type.
 +
:Interior Gateway Protocol (IGP) is lower than Exterior Gateway Protocol (EGP), and EGP is lower than INCOMPLETE
 +
in other words <b>IGP < EGP < INCOMPLETE</b>
  
*Prefer the route that comes from the BGP router with the lowest router ID. If a route carries the ORIGINATOR_ID attribute, then the ORIGINATOR_ID is used instead of router ID.
+
<li>Prefer the path with the lowest <b>multi-exit discriminator</b> (MED).
 +
: The router compare MED attribute only for paths that have the same neighboring (leftmost) AS. Paths without explicit MED value are treated as with MED of 0
  
*Prefer the route with the shortest route reflection cluster list. Routes without a cluster list are considered to have a cluster list of length 0.
+
<li>Prefer <b>eBGP</b> over <b>iBGP</b> paths
  
*Prefer the path that comes from the lowest neighbor address
+
<li>Prefer the route that comes from the BGP router with the lowest <b>router ID</b>. If a route carries the <b>ORIGINATOR_ID</b> attribute, then the <b>ORIGINATOR_ID</b> is used instead of router ID.
[[User:Eugene|Eugene]]
 
  
[[Category:Routing]]
+
<li>Prefer the route with the shortest <b>route reflection cluster list</b>. Routes without a cluster list are considered to have a cluster list of length 0.
 +
 
 +
<li>Prefer the path that comes from the lowest neighbor address
 +
</ol>
 +
 
 +
 
 +
[[Category:Routing|B]]
 +
[[Category:Manual|B]]
 +
[[Category:BGP]]
 +
[[Category:Case Studies|B]]

Latest revision as of 15:39, 19 March 2014

Introduction

With the full Internet BGP routing table being upward of 300K routes and with a BGP router having the potential to be receiving multiple copies of that routing table from multiple providers, it has to have some way to compare those multiple BGP routing tables and select only the best route to go into the IP routing table on the router. It uses the BGP Best Path Selection Algorithm to do this.

You should note that MikroTik and Cisco BGP routers have weight as the first criteria in the table where other brands do not.

Best path algorithm compares routes received by a single BGP instance. Routes installed by different BGP instances are compared by the general algorithm, i.e. route distances are compared and the route with lower distance is preferred.

BEST PATH ALGORITHM

  1. Router is ignoring received path if the route is not valid. Route is valid if:
    • NEXT_HOP of the route is valid and reachable
    • AS_PATH received from external peers does not contain the local AS
    • route is not rejected by routing filters

    For more information read nexthop selection and validation.

  2. The first path received is automatically considered 'best path'. Any further received paths are compared to first received to determine if the new path is better.
  3. Prefer the path with the highest WEIGHT.
    WEIGHT parameter is local to the router on which it is configured. A route without assigned WEIGHT have a default value of 0.
  4. Prefer the path with the highest LOCAL_PREF. It is used only within an AS.
    A path without LOCAL_PREF attribute have a value of 100 by default.
  5. Prefer the path with the shortest AS_PATH. (skipped if ignore-as-path-len set to yes)
    Each AS_SET counts as 1, regardless of the set size. The AS_CONFED_SEQUENCE and AS_CONFED_SET are not included in the AS_PATH length.
  6. Prefer the path that was locally originated via aggregate or BGP network
  7. Prefer the path with the lowest ORIGIN type.
    Interior Gateway Protocol (IGP) is lower than Exterior Gateway Protocol (EGP), and EGP is lower than INCOMPLETE
    in other words IGP < EGP < INCOMPLETE
  8. Prefer the path with the lowest multi-exit discriminator (MED).
    The router compare MED attribute only for paths that have the same neighboring (leftmost) AS. Paths without explicit MED value are treated as with MED of 0
  9. Prefer eBGP over iBGP paths
  10. Prefer the route that comes from the BGP router with the lowest router ID. If a route carries the ORIGINATOR_ID attribute, then the ORIGINATOR_ID is used instead of router ID.
  11. Prefer the route with the shortest route reflection cluster list. Routes without a cluster list are considered to have a cluster list of length 0.
  12. Prefer the path that comes from the lowest neighbor address