Everyone wants to know about BGP, routing strategy is handled like this

About the author: Xiao Honghui, graduated from the Graduate School of the Chinese Academy of Sciences, has 8 years of work experience, including 6 years of experience in cloud computing development. He is active in the OpenStack community and has contributed more than 300 commits and more than 30,000 lines of code. He is currently focusing on virtual network technologies such as SDN/NFV. All opinions in this article represent the author's personal opinions only and have nothing to do with the author's current or previous company.

Routing protocol, in IT terms, is actually a distributed database system, which includes data transmission between nodes and data processing within nodes. For BGP, the connection between nodes is based on TCP (port 179). On this basis, EBGP between ASs and IBGP within ASs can be built. IBGP has full mesh, BGP route reflector, etc. These are all ways to connect BGP nodes. This time, let's see how the BGP router processes data.

BGP is a path vector routing protocol. Compared with other types of routing protocols, path vector carries more auxiliary information with the route, and the processing is slightly more complicated. The internal processing flow of BGP is briefly drawn as shown below. The actual implementation of each company may be slightly different, but it should be similar.

Before looking at this process, let's take a look at some related concepts.

Path Attribute (PA)

Path corresponds to route, which, as the name implies, is some parameter attributes of BGP Route. Path Attribute is the basic component element of BGP, which runs through the entire BGP routing process.

First, the BGP message transmitted between BGP nodes is composed of NLRI (Network Layer Reachability Information) and PA. This can be seen from the BGP Update Message. If only IP routing is considered, then NLRI is the IP prefix.

Secondly, the processing of BGP policy engine is centered around Path Attribute. Thirdly, BGP best path selection is an algorithm based on PA.

Path attributes are divided into four categories:

• Well-known Mandatory: All BGP routers must recognize this attribute, and all BGP Messages must contain this attribute.
• Well-known Discretionary: All BGP routers must recognize this attribute, and BGP Messages may not contain this attribute.
• Optional Transitive: BGP router may not recognize this attribute. If it does not recognize this attribute, it will ignore it.
• Optional Non-transitive: BGP router may not recognize this attribute. If it does not recognize it, it will discard this BGP Message.

The following table lists common BGP Path Attributes:

Here, NEXT_HOP also belongs to the Path Attribute. NEXT_HOP can be modified during BGP processing. By default, the EBGP router will modify NEXT_HOP to itself, while the IBGP router will not modify NEXT_HOP by default, as mentioned in the previous article.

Routing Information Base (RIB)

RIB is actually a term used by equipment vendors. It may not be appropriate, but Global RIB can correspond to the routing table in the operating system. Both Global RIB and routing table determine the path of Layer 3 forwarding of IP packets. In addition to storing routing entries, RIB also stores some auxiliary information related to routing protocols. In addition to Global RIB, each routing protocol has its own RIB, so that routing protocols can isolate some raw data from real application data. BGP maintains several RIBs, including:

• BGP Adjacent In RIB: Saves all received BGP Messages. There may be multiple BGP Messages pointing to the same destination IP prefix.
• BGP Local RIB: Saves the processed and calculated ***BGP Message. For the same destination IP prefix, there is only one ***BGP Message.
• BGP Adjacent out RIB: Saves the BGP Message to be sent to the BGP Peer

The data sent and received by the BGP protocol will not be written directly to the Global RIB, but to BGP's own RIB. It will be written to the Global RIB at an appropriate time. As mentioned earlier, this can achieve data isolation and selectively write BGP data into the main routing table. The three RIBs of BGP store BGP Messages at different processing stages and provide data for operations at different stages. Next, let's go through the BGP routing process.

Route Processing

1. BGP Adjacent in RIB

This step is relatively simple. All incoming BGP messages are accepted and stored in BGP Adjacent in RIB.

2. Input Policy

The nput policy will complete two parts of work, filtering and manipulation.

Filtering will filter BGP Messages based on Path Attribute. Here we need to pay attention to two built-in filters. One is to determine whether the current AS is in the AS_PATH of the BGP Message. If it is, then this is a message that has passed through the current AS before, and this message will be filtered. The other will determine whether the NEXT_HOP in the BGP Message is reachable. If it is not reachable, then this message will be marked as Invalid and will also be filtered. In addition to the built-in filters, users (yes, network engineers) and control programs can also add filtering rules, such as through route-map, access-list, distribution-list, etc.

Manipulation modifies the Path Attribute of a BGP Message, which can control subsequent steps, such as Best Path Selection. For example, if a BGP Router receives BGP Messages with the same IP prefix from two neighbors, it can modify the PA of one of the neighbor's BGP Messages to make one of the BGP Messages win in the next step.

3. Best path Selection

Local routes are local routes that are expected to be published through BGP. For example, Cisco devices can publish local routes through the network command, and can also redistribute IGP routes to BGP through redistribution. These local routes will be converted into BGP messages and participate in the Best Path Selection together with the BGP messages that have been filtered and modified by the Input policy.

Best Path Selection is a process of selecting the best path from multiple BGP messages pointing to the same destination IP prefix based on Path Attribute calculations. This process is not complicated, but it is quite tedious. There are many corresponding introductions. Due to space limitations, I will not expand on it. If you are interested, you can read Cisco's document BGP Best Path Selection Algorithm.

4.BGP Local RIB

Best Path Selection ensures that there is only one (or more, depending on multipath) best BGP message pointing to the same IP prefix, and these BGP messages are stored in the BGP Local RIB. The subsequent processing is divided into two paths.

The first is written into the Global RIB, which is the global routing table. When no other routing protocol in the router generates a route pointing to the same destination IP prefix, or if there is, the Administrative Distance (AD) of the routing protocol is greater than the AD value of BGP, then the route of BGP Local RIB will be written into the Global RIB. The AD value of EBGP is 20, which is smaller than most routing protocols, and the AD value of IBGP is 200, which is larger than most routing protocols.

The second is output to the Output Policy and then sent to other BGP Peers.

These two paths do not affect each other. Even if BGP does not compete with other routing protocols and does not write routes to the global routing table, it does not affect the transmission of routes to other BGP peers.

5.Output Policy

Similar to Input Policy, filtering and manipulation are also performed here.

Filtering will filter BGP Messages based on Path Attribute, which can be defined by yourself or by the built-in filtering of the BGP program. Taking AS_PATH as an example, if the AS of the destination BGP Peer is in the AS_PATH of the BGP Message, then this BGP Message will not generate a corresponding BGP Message sent to the BGP Peer.

Manipulation modifies the path attributes of BGP messages, such as the MED value, and then generates a BGP message to be sent to the BGP peer.

After the Output Policy, a BGP Message will generate multiple BGP Messages for each BGP Peer that can be delivered. Although they come from the same BGP Message, the Path Attribute contained in each BGP Message may be different due to the definition policy.

6.BGP Adjacent out RIB

Similar to the first step, this part is also simple. The generated BGP Message is sent to the other BGP Peer.

***

The above is the BGP routing process, which is all centered around Path Attribute. If BGP is based on TCP transmission and brings reliability to the transmission between BGP routers, then Path Attribute brings flexibility to the application of BGP.