Networking

Understand how the BGP Best Path Selection Algorithm works on your router

The Border Gateway Protocol allows us to surf the Web, receive e-mail, and even read this article. BGP creates the routes connecting us to whatever Internet data we desire within milliseconds. David Davis explains how the BGP Best Path Selection Algorithm actually works on your router.

The Border Gateway Protocol (BGP) allows us to surf the Web, receive our e-mail, and read this article. BGP is a path-vector routing protocol, which simply means that its job is to exchange routing information between autonomous systems to find the most efficient path for your data to the Internet. Each BGP router connects to its neighbor (or neighbors) with neighbor statements. Once it forms that neighbor relationship, the BGP routers exchange routes. Last time I checked, the full Internet routing table was about 125,000 routes, so you need a strong router to receive the full Internet BGP routing table.

I have authored three different TechRepublic articles about BGP:

Now, I'd like to focus on a different aspect of BGP -- how BGP selects the best path, through the Internet, out of all the routes that it might receive.

What is the BGP Best Path Selection Algorithm?

With the full Internet BGP routing table being upward of 200K 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 Cisco BGP routers have weight as the first criteria in the table where other brands of routers do not. Cisco's official BGP Best Path Selection Algorithm documentation lists these criteria, but below I will list each of them with my own commentary and examples.

Unless there are no options in place to influence the result, the BGP Best Path selects the best path based on the shortest Autonomous System (AS), one or more networks under a single administrative control. However, many times options like weight, local preference, and MED are put in place by network administrators.

Let's look at the selection criteria, in order, that BGP uses to select the best routes to install into the IP Routing table:

#1 Weight -- This is a Cisco-defined attribute that is assigned locally to your router and does not get carried through to the router updates. If there are multiple paths to a particular IP address (which is very common), then BGP looks for the path with the highest weight. There are several ways to set the weight parameter, such as the neighbor command, the as-path access list, or route maps. #2 Local Preference -- This is an indicator to the AS as to which path has local preference, with the highest preference being preferred. The default is 100. For example:
bgp default local-preference 150
#3 Network or Aggregate -- This criterion prefers the path that was locally originated via a network or aggregate. The aggregation of specific routes into one route is very efficient and saves space on your network. For more information on aggregate, please see the Cisco article "Understanding Route Aggregation in BGP." #4 Shortest AS_PATH -- BGP uses this one only when there is a "tie" comparing weight, local preference, and locally originated vs. aggregate addresses. #5 Lowest origin type -- This deals with protocols such as Interior Gateway Protocol (IGP) being a lower preference than Exterior Gateway Protocol (EGP). #6 Lowest multi-exit discriminator (MED) -- This is also known as the external metric of a route. A lower MED value is preferred over a higher value. #7 eBGP over iBGP -- Similar to #5, BGP AS Path prefers eBGP over iBGP. #8 Lowest IGP metric -- This criterion prefers the path with the lowest IGP metric to the BGP next hop. #9 Multiple paths -- This determines if multiple paths require installation in the routing table. Check out this link for information on BGP Multipath. #10 External paths -- When both paths are external, it prefers the path that was received first (the oldest one). #11 Lowest router ID -- This prefers the route that comes from the BGP router with the lowest router ID. #12 Minimum cluster list -- If the originator or router ID is the same for multiple paths, it prefers the path with the minimum cluster list length. #13 Lowest neighbor address -- This prefers the path that comes from the lowest neighbor address.

There are some commands that you will use over and over with the BGP metrics. They are show ip bgp and show ip bgp summary. In fact, I usually create aliases for these commands to make using them quicker (see my article "Enter Commands More Efficiently with Cisco Command Aliases"). These commands will give you a quick snapshot of BGP and its relationship to the routers. Here is a truncated example of output from the show ip bgp command:

 RTA# show ip bgp
 BGP table version is 14, local router ID is 203.250.15.10
Status codes: s suppressed, d damped, h history, * valid, > best, i -internal
 Origin codes: i - IGP, e - EGP, ? - incomplete
 Network          Next Hop          Metric LocPrf Weight Path
*>i128.213.0.0      128.213.63.2           0    200      0 200 i
> 192.208.10.0     192.208.10.5           0    300      0 300 i
*>i200.200.0.0/16   128.213.63.2                200      0 200 400 i
>i203.250.13.0     203.250.13.41          0    100      0 i
*>i203.250.14.0     203.250.13.41          0    100      0 i
*> 203.250.15.0     0.0.0.0                0         32768 i

The routes with the * beside them were selected as the best path by the BGP Best Path Selection Algorithm.

Conclusion

Whether you are a network administrator who uses BGP or you are just interested in BGP for CCNP or CCIE certification, understanding how it works is valuable knowledge. As you have seen, using the metrics and the show commands can really narrow down the criteria for easy resolution.

For more information, see Cisco's official BGP Best Path Selection Algorithm documentation and Cisco's Configuring BGP documentation.

3 comments
rpedrosa1979
rpedrosa1979

Hello, could you please answer my question about my BGP configuration? I can send e-mail for u. Please contact me. ricardo.pedrosa@bancobmg.com.br

Photogenic Memory
Photogenic Memory

Since I've never seen a home router display these stats( Linksys, Dlink, Netegear, etc. ); what does my home router do to determine these routes? A home router just does NAT with a basic( a very basic ) SPI, correct? Since I'm connected to a cable modem from the ISP ( COX sucks by the way here in SD ); my "router" isn't actually doing the talking is it? In fact it's not really a router at all? True? So I guess my real question is how does my cable modem factor into the equation of routing the internet to me? I take it that the cable modem has a MAC address that gets authenticate by a ISP switch that identifies it( or is told to by the cable tech ) and a VLAN is created upon syncing up with it? Since that's the case; how can I see that connection information without asking the ISP? Any applications other than traceroute and ping to log? Why do I even want this info? Well, I think it would make for a great argument on bargaining for a better bandwidth for starters! How many of us buy connections and get fluctuating upload/download speeds? A lot of my friends using AT&T would agree. Anyone have any suggestions?

ddavis
ddavis

Hi Photogenic Memory, Thanks for the post! Great questions! Let me try to answer some of them... - No, home routers don't use BGP or need it. Only routers that have at least two Internet connections need BGP, in general. With a home router, you only have one route (a default route to your ISP). - Your router is actually a router as it is routing between two networks - your home network and the network going to your ISP. This is really a very simple job for a router and that is why we all have such small routers at home that can do a ton of stuff like NAT, routing, firewall, wireless, and more. - Your cable modem is really more of a media translator, taking the Ethernet LAN and turning it into "cable". If I recall, it is the Ethernet MAC on the local LAN side of the switch that is authenticated by the ISP. - My recommnedation to be able to get more insight into your cable connection would be to look for a "smarter" & more manageable cable modem. I have an old Motorola but even it tracks errors, has SNMP, a web interface, configurable MAC, etc. I am sure that these days there are much smarter cable modems that might give you what you are looking for. Thanks for reading my TechRepublic articles! Anyone else have cable modem help to offer? -David Davis www.TrainSignalTraining.com www.HappyRouter.com