So now I'd like to turn my attention to
the BGP path selection algorithm.
We have looked at all the BGP attributes and
what they do and how they work.
We've been discussing the BGP attributes up to
now and how they are used to influence different policies within BGP.
So the path selection algorithm has 14 steps,
which we will look at in turn.
Now let's consider that we have one destination,
and there are several paths to that
destination, let's say we have 2 paths.
What BGP does, it will run this algorithm
every time it has more than one path to a destination.
So the first step in the
path selection algorithm is to consider the path
and the availability of a route to
the next hop.
If there's no route to the next hop then we do not consider the path.
If routes to the next hop exist
on both the paths that we're considering
then we move on to the next step.
The second one is do not consider
the iBGP path if not synchronized.
Now synchronization was something we used
more than 20 years ago and is definitely historical.
These days BGP no longer is
synchronized with interior routing protocol,
so this step isn't really
considered in any modern routers.
The third step is: look at the highest weight.
Now when we were discussing the weight
when we looked at the BGP attributes, we
said weight wasn't an attribute.
But it's still considered as part of the path
selection process.
The highest weight wins and this is local to the router.
If the weights are the same we then look and compare the local preference.
The highest local preference will win, within the autonomous system.
If the local preferences are the same we move to the next step.
Step 5 prefers the
locally originated route.
So in other words, if the route is originated on the
local device rather than being originated elsewhere in the autonomous system.
The local one is preferred.
Otherwise, we move on to the sixth step.
And that's looking at the length of the AS path.
The shortest AS path wins.
So if we have different AS path lengths to the destination we're considering, we
pick the shortest one.
If the AS path lengths are the same, we
move on to the next.
Number seven is the lowest origin code.
We prefer IGP, if you
remember that's a route originated by BGP itself.
That's preferred before EGP,
if you remember that's the old EGP routing protocol that predates BGP.
And
that is preferred before incomplete.
Which you remember was a route that has
come from another routing protocol.
For example redistributed from a static
route.
If the origin codes are the same,
we then move on to the next one, we
compare the multi-exit discriminators or MEDs.
And the lowest MED wins, if the
paths are from the same autonomous system.
MEDs are only considered if the paths are from the same AS.
However, the vendors, and we've got Cisco example here,
have added knobs (at request of network operators),
to modify the MED comparison from the default specified in the BGP standard.
So we have two possibilities here,
we mentioned "bgp-deterministic-med" as the Cisco example earlier.
And that
orders the paths by autonomous system before we compare them.
So we group all the lowest ASes first and then the next and so on and so on and then compare the
MEDs after that.
There's also feature to let us always
compare the MED even if the paths are from different neighboring ASes.
We may get to a destination going through say,
two different peers or an
upstream provider to a different upstream providers.
With "always-compare-med" configured,
BGP will compare the MED from these two different immediate neighbors.
If the MED is the same,
then we prefer eBGP path over iBGP path.
This is normally done on a border router.
You're border router may see a direct
path to the eBGP neighbor,
and it may see another path learned through the local
autonomous system to another border router somewhere in the network.
Well
given the destination is outside our network,
logic would probably say we will
use the external path rather than the internal one to reach there.
This is the
so-called hot-potato routing.
We're at the edge of the network and we head out
because we don't want to transport
the traffic to the destination,
which is outside a network, over our own backbone.
If that one doesn't produce a
result, we move on to step 10:
path with the lowest IGP metric to the next hop.
And that's really saying, the fewest number of hops and/or the biggest
bandwidth to the edge of our network.
If that is still all the same, step 11 is
really all about, again, an addition that Cisco has made.
You won't find this
in the BGP path selection algorithm.
In IOS,
if multipath is enabled we put
those number of parallel paths in the
forwarding table.
And the number in the forwarding table really depends on how many there are, up to a limit specified by the hardware.
Cisco also has a feature which
lets you compare paths by age.
So the oldest path would win
over a more recent one.
Some network operators find this really useful,
other network operators don't find this so useful,
and it can be turned off if desired.
After that we then compare the lowest router-id.
So this is the IP address or the router-id
of the router that inserted the prefix
into BGP in the AS.
If we have route reflectors within our network the shortest cluster list wins.
And this is really an attempt to try to get internal destinations through the least number of route reflectors.
Just, again, part of the path selection.
And if we still don't have a best path result,
the final step in the path selection algorithm
is the lowest neighbor address.
Given IP addresses are
unique within a network (we would hope),
lowest neighbor address would give you a
result.
So those are the 14 steps of the BGP path selection algorithm.
They
have to follow the BGP standard,
but as I said at the start, many implementations
have added a few additional knobs,
as they're called,
so that network operators
can fine tune the BGP path selection algorithm according to their own local requirements.
© Produced by Philip Smith and the Network Startup Resource Center, through the University of Oregon.
Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)
This is a human-readable summary of (and not a substitute for) the license. Disclaimer. You are free to: Share — copy and redistribute the material in any medium or format Adapt — remix, transform, and build upon the material The licensor cannot revoke these freedoms as long as you follow the license terms. Under the following terms: Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use. NonCommercial — You may not use the material for commercial purposes. No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.