CN100365986C - A Method for Saving Routing Table Memory Consumption in Border Gateway Protocol Routers - Google Patents

Abstract

The invention provides a method for saving routing table memory consumption of the border gateway protocol, which belongs to the field of computer network communication. The method comprises: after locally receiving or self-generated routing, using Loc-Rib as a public shared buffer pool, saving all existing routing information, creating each routing in the Loc-Rib information base and Adj-Rib- The mapping relationship of Out, the route is sent to the arbitration decision module to filter the local policy, if the decision of the arbitration module is passed, the route that is considered appropriate locally will be notified to other Peers. Due to the establishment of the corresponding relationship between the route in the Adj-Rib-Out information base and a certain route in the Loc-Rib information base, Adj-Rib-Out does not need to maintain a copy of the route to be sent to realize information sharing and save It can significantly save the memory consumption of the BGP routing table.

Description

A Method for Saving Routing Table Memory Consumption in Border Gateway Protocol Routers

Technical field

The invention belongs to the field of broadband network communication, and in particular relates to a method for saving routing table memory consumption of a Border Gateway Protocol (BGP) router.

Background technique

As a type of EGP protocol, BGP is used to discover and transfer routes between autonomous systems. Its basic function is to advertise and store routes. Between BGP peers, exchange routes through UPDATE (update) messages; when a BGP router receives an UPDATE message, it performs policy filtering, and then notifies other BGP Peer (neighbors) of the route it considers appropriate locally; finally To achieve network reachability between autonomous systems.

Referring to Figure 1, in the BGP protocol, routes are stored in the routing information base (Routing Information Base, RIB); by introducing three logical levels, the storage and notification of routes are finally realized. Adj-RIBs-In: used to save the routes received from each BGP peer; Loc-RIB: used to save the routes allowed by the local BGP peer; Adj-RIBs-Out: used to save the routes to be advertised to Routes to other BGP peers. With reference to Fig. 2, Adj-Ribs-In is associated with each BGP peer, is used for storing the route information that this peer receives; A subset of Adj-Ribs-In that passes the input policy check); Adj-Rib-Out is associated with each BGP peer, and is used to store the locally selected route information to be notified to the remote BGP peer. The benefits of such a design are self-evident, but it leads to the problem of excessive memory consumption; since Adj-Ribs-Out is associated with a BGP peer, in other words, how many Peers need to receive the routing information, How many copies of routes will be copied and saved in the corresponding PEER structure respectively, calculated according to the 64 bytes of each route, when there are N routes and need to be sent to M Peers, only Adj-Rib-Out needs (M *N*64)byte. If there are many routes and many peers, this problem will become particularly prominent. Obviously, the BGP protocol, as an inter-domain gateway protocol, generally runs on the core routers, and there must be many routes interacting with each other. According to statistics, there are currently more than 100,000 routes on the Internet, and this number will continue to grow. Such a large memory consumption will seriously affect the cost performance of the product. How to effectively reduce the memory consumption of the routing table will be the first issue that every network equipment supplier should consider.

Contents of the invention

The present invention can effectively solve the above-mentioned problem of excessive memory consumption caused by the expansion of the routing table, and provides a solution for efficiently saving the memory consumption of the BGP routing table.

Technical contents of the present invention: a method for saving routing table memory consumption of a border gateway protocol routing table, using Loc-Rib as a public shared buffer pool to save the routing information;

Create a mapping relationship with the Peer in the Adj-Rib-Out information base for each route in the Loc-Rib information base;

By establishing a mapping bitmap between Peer and the global index, each Peer can uniquely correspond to a specific index. When a certain route in the Loc-Rib local routing information base undergoes a series of local policy arbitrations, it can be obtained The conclusion of whether it is necessary to notify the Peer, if the routing information needs to be notified to a corresponding Peer, it is necessary to mark the Peer mapping bitmap associated with the routing node at this time, the purpose is to indicate that the route belongs to the Adj-Rib- Out is part of the routing information database, implying that the route has been sent to the specified Peer;

If the result of the local policy arbitration does not need to be sent to the corresponding Peer, it means that the route has been revoked, then it is necessary to determine whether the route is in the Adj-Rib-Out information base, that is, to determine the corresponding Whether the location has been marked, if it exists, it means that the route has been notified to Peer, and now the route is no longer valid, and it needs to be notified to Peer again to cancel the route, and delete the corresponding mapping relationship from the local Adj-Rib-Out information base , and clear the management information corresponding to the Peer.

During the route display process, if you need to know whether the route has been advertised to the corresponding Peer, you only need to scan the mapping bitmap between the route and the Peer. If the corresponding position is marked, it indicates that the route has been advertised to the corresponding Peer.

Technical effect of the present invention: after receiving the UPDATE message that certain Peer sends, at first according to policy decision whether need to carry out the preservation of local Adj-Ribs-In information base, the main purpose of Adj-Ribs-In routing information base preservation It is for the realization of soft restart. If Peer’s capability negotiation finds that the peer supports the route refresh mechanism, there is no need to save the Adj-Ribs-In information base locally, thus saving the memory of the local Adj-Ribs-In information base as much as possible. consume. Use the Loc-Rib information base as a public shared buffer pool to save all existing routing information; establish the corresponding relationship between the route in the Adj-Rib-Out information base and a certain route in the Loc-Rib information base, Adj- The Rib-Out information base does not need to maintain a copy of the route to be sent. It only needs to know how to map with the specific routing nodes in the Loc-Rib information base to realize information sharing (the three routing information bases share one routing information), saving memory. And when displaying, it is only necessary to judge whether a specific position on the Peer mapping bitmap associated with the route is clicked, which reduces a search process and further improves processing efficiency. The present invention abolishes the linear relationship between the routing table and the number of Peers, thereby solving the impact of routing table expansion on memory consumption.

Description of drawings

Fig. 1 is a schematic diagram of the logical relationship of each routing information library of the border gateway protocol of the present invention;

Fig. 2 is the routing storage and notification flowchart of the border gateway protocol of the present invention;

Fig. 3 is a flow chart of route notification processing in the present invention;

Fig. 4 is a flow chart of route display processing in the present invention.

Detailed ways

Let's take a specific route processing as an example to briefly explain the specific processing process:

1) When a route is received for the first time, a new routing node is created locally, the specific information of the route is saved, and it is placed in the specific location of the Loc-Rib local routing information database;

2) Start the background processing job, and be responsible for completing the notification processing process of the route to the Peer;

3) After the background job is scheduled, the route is sent to the arbitration decision module to filter the local policy. If the decision of the arbitration module is passed, it indicates that the route needs to be notified to the corresponding Peer. At this time, the routing node needs to Dots on the Peer mapping bitmap, indicating that the route is in the Adj-Rib-Out information base of the corresponding Peer;

4) If the local policy changes subsequently, and the network management user inputs some new policies, for example: a new route-map is configured, or a withdrawal message about the route is received from other peers, the local route selection information All the best routes of the library are sent to the arbitration module in turn for re-decision:

a) If the result of the decision at this time is still passed, then judge the mapping relationship between the route and the Peer, whether the corresponding position in the mapping bitmap is dotted, if it is dotted, it means that the route has been notified to the Peer before, and there is no need to do it again Notification; otherwise, if there is no dot, it means that the route has not been notified to Peer before and needs to be re-notified, then dot at the corresponding position and notify the specific route to Peer;

b) If the result of the decision at this time indicates that it is not passed, that is, the route is no longer valid, it is necessary to determine whether the route announcement has been sent to the Peer. It can be known from the mapping bitmap between the route and the Peer. If the route has been sent to the Peer before After sending the route, if there is dot information at the specific location of the mapping bitmap, it is necessary to explicitly send a cancellation message about this route to the Peer, and at the same time, clear the corresponding dot information on the mapping bitmap; if there is no dot information to the Peer before After sending this route, if there is no dot information at the specific position on the mapping bitmap, then there is no need to do any follow-up processing, and there is no need to explicitly send the revoked route.

The following further describes the basic process of route display:

Since the user needs to know whether a certain route has been sent to the corresponding Peer, for the traditional implementation, it is necessary to search again in the Adj-Rib-Out routing information database corresponding to the Peer according to the routing information, and determine whether there is a matching routing node , if it exists, it means that the route has been notified to the corresponding Peer, otherwise, it will prompt that the route has not been notified to the Peer; by using the method for saving routing table memory consumption provided by the present invention, when performing the route display process, if necessary To know whether the route has been advertised to the corresponding Peer, just scan the mapping bitmap of the route and the Peer, if the corresponding position is dotted, it indicates that the route has been notified to the corresponding Peer, otherwise, if the corresponding position has not been dotted , it indicates that the route has not been advertised to the corresponding Peer.

Claims (4)

1. a method for saving routing table memory consumption of a border gateway protocol router, characterized in that: after locally receiving or self-generated routing, the Loc-Rib information storehouse is used as a public shared buffer pool to preserve the routing information; Set up a mapping bitmap of Peer and global index, so that each Peer can uniquely correspond to a specific index, create the Peer in the Adj-Rib-Out information base for the described route in the Loc-Rib information base mapping relationship; The arbitration decision module filters the route according to the local policy, and if the route passes the decision of the arbitration module, the route needs to be notified to the corresponding Peer. 2. the method for saving routing table memory consumption of the border gateway protocol router as claimed in claim 1, is characterized in that: when needing described route announcement to corresponding Peer, if the Peer mapping bitmap of described routing node does not manage , then put a dot on the Peer mapping bitmap of the routing node; otherwise, do not put a dot on the Peer mapping bitmap of the routing node. 3. the saving routing table memory consumption method of border gateway protocol router as claimed in claim 1, it is characterized in that: if not by local policy arbitration, judge whether once dot on the corresponding position of this routing node Peer mapping bitmap, if once If the point is passed, the corresponding Peer is notified to cancel the route, the corresponding mapping relationship is deleted from the local Adj-Rib-Out information base, and the point information corresponding to the Peer is cleared. 4. the saving routing table memory consumption method of border gateway protocol router as claimed in claim 2 or 3, it is characterized in that: when carrying out route display process, if need to know whether this route once notified to corresponding Peer, just need Scan the mapping bitmap between route and Peer. If the corresponding position is dotted, it indicates that the route has been advertised to the corresponding Peer.

Images