You might have heard people comparing the Internet to a network of highways connecting cities. This comparison is not far off. But if the Internet correspond to a network of highways, who controls the flow of traffic?
The short answer is Border Gateway Protocol (BGP). BGP serves as the standardized routing protocol of the Internet, which exchanges routing information between autonomous systems. Without it, the Internet would not be possible. It uses the BGP best path selection algorithm to sort through the different network routes and select the best path.
The BGP Best Path Selection Algorithm
The Internet is a huge mesh of individual interconnected networks. Each network creates connections to neighboring networks through BGP routers. BGP routers build up routing tables which contain records of routes to other BGP routers. These routing tables correspond to maps, outlining the routes to neighboring routers. BGP routers exchange these maps with their neighbors. At last count there were upwards of 600,000 entries in the BGP routing table.
The best path selection algorithm then has to sort through the routes to select the best path. Choosing one route over another can have huge consequences for the speed, availability and cost of Internet traffic.
Criteria for Selecting Best Path
The best path selection algorithm uses a pre-defined set of criteria to come up with the most efficient route through a network. In the event that no criteria is in place, BGP will always route Internet traffic over the shortest path, with the lowest number of intervening autonomous systems (AS) hops. Network administrators frequently alter this criteria to route Internet traffic according to their network or business needs.
The criteria for Cisco’s BGP best path selection algorithm are presented below:
As pointed out earlier, BGP routers are usually presented with multiple paths through a network. The first criteria for making routing decisions is weight. The best path algorithm prefers the path with the highest weight.
Network engineers can define weight through a number of commands. These include the neighbor command, AS_PATH access lists, or route maps. Weight can carry a value from 0 to 65,535. Paths that originate at the router carry a weight value of 32,768 by default. Paths that originate externally have a weight value of 0. Weight is locally assigned to the BGP routers and is not propagated through any subsequent route updates.
The next criteria used by the best path selection algorithm is local preference. Paths with the highest value of local preference are chosen to route internet traffic.
Local preference signals to the AS the preference that a path has to exit the AS, and reach an external network. Local preference is chosen through route updates between routers with the same AS, and has a default value of 100.
The best path selection algorithm uses this criteria to prefer paths that originate locally via an aggregate or network. Aggregating network routes into one makes internet routing more efficient by saving network space.
AS_Path Length criteria comes into play whenever the best path algorithm cannot differentiate between paths based on the previous criteria. This usually happens when all the potential network paths carry similar values for all previous criteria. It prefers paths which have the lowest number of AS hops.
Origin Type criteria differentiates between paths based on origin type. Based on this criteria, the best path algorithm chooses the path with the lowest origin type. A higher preference is given to Exterior gateway protocol (EGP), like BGP, as compared to IGP (Interior gateway protocol).
Multi-Exit Discriminator (MED)
This criteria differentiates between routes based on multi-exit discriminator or MED. MED indicates to other external routers the preferred route for entry into an AS. The path which has the lowest value of MED is preferred.
eBGP over iBGP
With this criteria the best path algorithm prefers eBGP over iBGP. iBGP or internal BGP runs within the same AS, whereas eBGP or external BGP operates between AS’s.
Using this criterion the best path selection algorithm prefers the path with the lowest IGP value to the next hop.
This criteria works if multiple paths are required to be installed in the routing table. With BGP multipath, many paths can be installed into the IP routing table. These multiple paths can then be used for load sharing.
This criteria differentiates between external paths based on when they were received. The path that is older, or was received first, is preferred.
With this criteria BGP’s best path selection algorithm prefers the path that originates from the BGP router with the lowest router ID. The router ID can be set manually and refers to the IP address with the highest router value.
If one route can still not be chosen because of similar router IDs, best path selection algorithm then differentiates based on cluster list. The path with the lowest cluster list length is preferred.
The next differentiating factor for best path selection is neighbor address. Paths that have the lowest neighbor address are preferred.
Customizing BGP Best Path Selection
The best path selection algorithm can be customized through the BGP cost community attribute. With the cost community feature, local route preferences can be influenced by associating a cost value to candidate paths. This feature, however, is limited in terms of making any meaningful changes to network routes to improve performance.
It can only be configured to work within an AS and is transmitted only to peers residing inside that particular AS. Cost community attribute only comes into play once the preceding criteria has been exhausted and can be used as a tie breaker.
Re-Implementing BGP Best Path Selection
At Datapath.io we have come-up with our own implementation of BGP. We re-engineer the best path selection algorithm of BGP to our own specifications. BGP routing decisions are performance agnostic. We insert a set of performance metrics into the best path selection process. Our implementation is based on the Openflow protocol.
To learn more about network performance optimization download the Whitepaper.