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.

Related Documents

Exercises

© 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.