CN104780101B - Content center network Forwarding plane fib table structure and its search method - Google Patents

Abstract

The invention discloses a content-centric network forwarding plane FIB table structure, which includes an on-chip storage unit and two off-chip storage units; Use multiple locatable Bloom data structures as data indexes; among the two off-chip storage units, one off-chip storage unit is composed of a CBF memory group, and the CBF memory group uses multiple CBF data structures to realize the FIB table update operation, and the other An off-chip storage unit is an off-chip static memory, and the off-chip static memory uses a static storage structure to store forwarding information of actual data packets. The FIB table structure of the present invention can realize high-efficiency routing information storage while satisfying the million-level message processing capability of the forwarding plane of the content-centric network, and fast message matching and updating operations of the FIB table based on the longest prefix matching principle, and can Deployed in the current hardware environment.

Description

Content-centric network forwarding plane FIB table structure and retrieval method

technical field

The invention belongs to the field of high-performance router structure design, and is particularly aimed at the problem of querying and updating a high-performance FIB table in a content-centric network (Named DataNetworking) forwarding plane.

Background technique

With the wider popularization and application of Internet technology, the original TCP/IP-based Internet architecture can no longer meet people's needs in terms of speed, energy consumption, security, mobility, and communication quality. obstacles to further development. Therefore, a new content-centric future Internet architecture: Content-Centric Networking (Named Data Networking) was proposed in 2009 and has developed rapidly.

The content-centric network adopts a data-centric communication mode. By establishing a new Internet network architecture system, it breaks the original location-based communication mode (Location-Based), that is, it does not consider the physical location where the content is stored, and realizes the network from The basic meaning of the revolutionary change from "where" to "what" is to adjust the needs of the entire Internet from hosts to data content. Its advantage is that it greatly improves the sharing rate of network resources and improves network performance.

A large number of studies have shown that in order to realize the new Internet architecture of the content-centric network, its forwarding plane is required to have an efficient routing storage structure to support higher-speed packet matching and routing update operations. Among them, under the connection rate of 10Gbps to 20Gbps, the storage structure should have a message processing capacity of one million levels, and at the same time, it can realize the FIB table query and update operations based on the Longest Prefix Matching principle (Longest Prefix Matching); secondly, it should be fully Consider new variable-length data naming schemes in this network and the current state of the art in hardware memory. However, currently commonly used FIB storage structures based on the Hash method, Bloom filter technology or Name Component Encoding tree coding scheme cannot fully meet the above requirements.

Contents of the invention

In view of the above problems, the present invention designs a novel FIB table storage structure aimed at the characteristics of the content-centric network forwarding plane. This structure can achieve efficient routing information storage while satisfying the million-level packet processing capability of the content-centric network forwarding plane. The FIB table based on the longest prefix matching principle can quickly match and update packets, and can be deployed in the current In the hardware environment.

In order to solve the above technical problems, a content-centric network forwarding plane FIB table structure proposed by the present invention includes an on-chip storage unit and two off-chip storage units; the on-chip storage unit is composed of a locateable Bloom memory group , the locatable Bloom memory group uses a plurality of locatable Bloom data structures as data indexes; among the two off-chip storage units, one off-chip storage unit is composed of a CBF memory group, and the CBF memory group uses multiple A CBF (Counter Bloom filter) data structure is used to realize the FIB table update operation, and another off-chip storage unit is composed of an off-chip static memory, and the off-chip static memory uses a static storage structure to store the forwarding information of the actual data message.

A kind of positionable Bloom data structure proposed by the present invention comprises a general type Bloom filter array BF and a positioning array MA, wherein said general type Bloom filter array BF is used to determine whether an element is in a set, and said positioning The array MA is a bit array that has a certain mapping relationship with the general-purpose Bloom filter array BF. According to the value of the positioning array MA, the offset of the element in the storage structure mapped by the locatable Bloom data structure can be determined. address.

A method for retrieving the FIB table structure of the forwarding plane of the content-centric network proposed by the present invention is based on the FIB table structure of the forwarding plane of the content-centric network proposed in the present invention. Wherein, the locatable Bloom memory group uses the above-mentioned locatable Bloom data structure proposed in the present invention as a data index; the retrieval method of the content-centric network forwarding plane FIB table structure includes FIB table message matching query, FIB The longest prefix matching query is performed in the locateable Bloom data structure for table update and message name prefix; where:

The steps of FIB table message matching query include:

Step 1-1, inputting the message name based on the hierarchical structure into the addressable Bloom memory group;

Step 1-2: According to the longest prefix matching principle, perform query operations in parallel in the locateable Bloom memory group, so as to determine whether the forwarding information of the message name is in the FIB table,

If there is a matching message name in the addressable Bloom memory group, then perform steps 1-3;

If there is no matching message name in the addressable Bloom memory group, then perform steps 1-4;

Step 1-3: Read the forwarding information in the off-chip static memory, obtain the offset address of the longest matching prefix in the off-chip static memory according to the output result of the addressable Bloom memory group, and follow the offset Shift the address and read the next-hop routing forwarding information corresponding to the longest matching prefix in the off-chip static memory;

Step 1-4: Return the FIB table query result to the forwarding plane, and end the FIB table message matching query;

The steps to update the FIB table include:

Step 2-1. Input the name prefix of the message to be updated based on the hierarchical structure into the CBF storage group.

Step 2-2, perform the update operation of the CBF memory in the CBF memory corresponding to the message name prefix to be updated according to the longest prefix matching principle, and judge whether the corresponding CBF memory bit value of the message name prefix is Variety,

If the value of the CBF memory bit corresponding to the message name prefix in the CBF memory group changes, that is, from 0 to 1 or from 1 to 0, then perform steps 2-3;

If the value of the CBF memory bit corresponding to the message name prefix in the CBF memory group does not change, then perform steps 2-4;

Step 2-3, synchronizing the value of the positionable Bloom memory bits in the on-chip storage unit corresponding to the CBF memory in the off-chip CBF memory group;

Step 2-4, return the FIB table update result to the forwarding plane, and end the FIB table update;

The steps of carrying out the longest prefix matching query in the addressable Bloom data structure of the message name prefix include:

Step 3-1. Set the values of all bits in the positioning array MA to 0;

Step 3-2, inputting the corresponding message name prefix into the locatable Bloom memory, wherein the length of the message name prefix corresponds to the serial number of the locatable Bloom memory;

Step 3-3, performing K hash mapping operations on the prefix of the message name, wherein the hash function is MD5 or SHA1, and at the same time, adjust the encoding length and mapping times K according to the specific size of the general-purpose Bloom filter array BF value;

Step 3-4, determine whether the BF bit values of the general-purpose Bloom filter array mapped by K hash mapping operations are all 1,

If the mapping values are all 1, go to step 3-5; otherwise, go to step 3-7;

Step 3-5, calculate the value of the positioning array MA according to the mapping value of K hash mapping operations in the general-purpose Bloom filter array BF;

Step 3-6, the numerical value of positioning array MA calculated by step 3-5 is exported to the FIB system as the offset address of the prefix of the message name in the off-chip static memory;

Steps 3-7, return the query result to the forwarding plane, and end the longest prefix matching query.

Compared with prior art, the beneficial effect of the present invention is:

The FIB table structure of the center network forwarding plane in the present invention is based on a locatable Bloom data structure, which not only can realize efficient search and update operations, but also has good deployability. The realization of the present invention can use SRAM for on-chip deployment, and meets the communication requirement that the error rate of the current Internet is lower than 1%.

Description of drawings

Fig. 1 is a system structure diagram of the content center network forwarding plane FIB table structure of the present invention;

Fig. 2 is a schematic diagram of a positionable Bloom data structure involved in the present invention;

Fig. 3 is the flow chart diagram about FIB table message matching query in the retrieval method of the present invention;

Fig. 4 is the flowchart about FIB table update operation in the retrieval method of the present invention;

Fig. 5 is a flow chart of the longest prefix matching query of the packet name prefix in its corresponding locateable Bloom data structure in the retrieval method of the present invention.

detailed description

The technical solutions of the present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments.

As shown in Figure 1, a content-centric network forwarding plane FIB table structure of the present invention includes an on-chip storage unit and two off-chip storage units; ) constitutes, the described positionable type Bloom memory group comprises W positionable type Bloom memory (in Fig. 1, a plurality of positionable type Bloom memory is expressed as MBF (1), MBF (2), MBF (3) , ... , MBF(W)), the locatable type Bloom memory group uses a plurality of locatable type Bloom data structures as data indexes; among the two off-chip storage units, one off-chip storage unit consists of a CBF memory group (Counter Bloom filters), the CBF memory group uses a plurality of CBF data structures to realize the FIB table update operation, and another off-chip storage unit is an off-chip static memory, and the off-chip static memory uses a static storage structure to store The forwarding information of the actual data packet.

As shown in Figure 2, the positionable Bloom data structure described in the present invention includes a general-purpose Bloom filter array BF and a positioning array MA, wherein the general-purpose Bloom filter array BF is used to determine whether an element is in the set Wherein, the positioning array MA is a bit array having a certain mapping relationship with the general-purpose Bloom filter array BF, and according to the value of the positioning array MA, it is determined that the elements are in the mapped storage structure of the positioning type Bloom data structure The offset address in .

As shown in Figure 2, a specific example of adding elements to the locateable Bloom data structure is given. In the locateable Bloom data structure, K=3 hash functions are used, and the size of BF (that is, the general-purpose Bloom filter array BF) is set to 32 bits, and at the same time, BF is equally divided into 8 parts. The corresponding alignment array MA is set to 8 bits, therefore, the indexable Bloom data structure can store ²⁸ elements in it off-chip. In this positionable Bloom data structure, the three elements X, Y, and Z are input in sequence, and the MA array is initialized to all 0s before each element input. When X is input, the 1st, 6th, and 11th bits in BF are hash-mapped, that is to say, there are hash maps in the 1st, 2nd, and 3rd parts of BF, so MA locates the 1st, 2nd, and 3rd bits of the array The value of the bit will be set to 1, and the value of other positions will be 0. Finally, the value of the MA positioning array is 11100000, that is, the offset address of the X element in the off-chip memory is 11100000. When Y is input, the 6th, 14th, and 22nd bits in BF are hash-mapped, that is to say, there are hash maps in the 2nd, 4th, and 6th parts of BF, so the 2nd, 4th, and 6th bits of the MA positioning array The value of the bit will be set to 1, and the value of other positions will be 0. Finally, the value of the MA positioning array is 01010100, that is, the offset address of the Y element in the off-chip memory is 01010100. When Z is input, the 17th, 22nd, and 27th bits in BF are hash-mapped, that is to say, there are hash maps in the 5th, 6th, and 7th parts of BF, so MA locates the 5th, 6th, and 7th bits of the array The value of the bit will be set to 1, and the value of other positions will be 0. Finally, the value of the MA positioning array is 00001110, that is, the offset address of the Z element in the off-chip memory is 00001110.

The retrieval method of the content-centric network forwarding plane FIB table structure of the present invention is based on the above-mentioned content-centric network forwarding plane FIB table structure (as shown in Figure 1), wherein the locatable Bloom memory group uses the above-mentioned locatable Bloom data structure (as shown in Figure 2) is used as a data index, and the retrieval method of the FIB table structure of the content-centric network forwarding plane includes FIB table message matching query, FIB table update, and message name prefix in the locateable Bloom data Longest prefix match lookup in the structure.

When using the content-centric network forwarding plane FIB table structure proposed by the present invention to perform FIB table message matching query, as shown in Figure 3, it specifically includes the following steps:

Step 1-1. Enter the message name. first inputting a hierarchy-based message name into said addressable Bloom memory bank;

Step 1-2: Determine whether the forwarding information of the message is in the FIB table, and perform query operations in parallel in the locateable Bloom memory group according to the longest prefix matching principle.

If there is a matching message name in the locateable Bloom memory group, it indicates that the longest prefix forwarding information of the message exists in the FIB table, and steps 1-3 are performed;

If there is no matching message name in the locateable Bloom memory group, it indicates that the longest prefix forwarding information of the message does not exist in the FIB table, and perform steps 1-4;

Step 1-3: Read the forwarding information in the off-chip static memory. According to the output result of the addressable Bloom memory group, the offset address of the longest matching prefix in the off-chip static memory is obtained, and the longest matching prefix is read in the off-chip static memory according to the offset address Corresponding next-hop route forwarding information;

Steps 1-4: Return the FIB table query result to the forwarding plane, and end the FIB table message matching query.

For example, as shown in Figures 1 and 3, first, the input message name is divided into W prefixes according to the message classification method of the content-centric network, and each length of the prefix corresponds to an MBF numbered from 1 to W (positionable type Bloom data structure). Next, W prefixes perform query operations in parallel in their corresponding MBFs, as shown in FIG. 1 . If there is a matching prefix in any one or several MBFs among the W MBFs, it indicates that the next-hop routing and forwarding information of the packet exists in the FIB table. Finally, the output result of the MBF corresponding to the matching prefix with the largest number will be used by the system as the offset address of the message in the off-chip static memory to read the next-hop routing information.

When utilizing the content-centric network forwarding plane FIB table structure proposed by the present invention to perform the FIB table update operation, as shown in Figure 4, the following steps are included:

Step 2-1. Enter the prefix of the message name to be updated. Input the name prefix of the message to be updated based on the hierarchical structure into the CBF storage group.

Step 2-2. Perform an update operation in the CBF memory bank. Carry out the update operation of the CBF memory in the CBF memory corresponding to the message name prefix to be updated according to the longest prefix matching principle, and judge whether the bit value of the CBF memory corresponding to the message name prefix changes.

If the value of the CBF memory bit corresponding to the message name prefix in the CBF memory group changes, that is, from 0 to 1 or from 1 to 0, then perform steps 2-3;

If the value of the CBF memory bit corresponding to the message name prefix in the CBF memory group has not changed, then there is no need to perform an update operation, and directly perform steps 2-4;

Step 2-3, synchronizing the CBF memory with its corresponding locateable Bloom memory. Synchronizing the value of the bits of the addressable Bloom memory in the on-chip storage unit corresponding to the CBF memory in the off-chip CBF memory group completes the update operation of the FIB table.

Step 2-4, return the FIB table update result to the forwarding plane, and end the FIB table update;

When using the content-centric network forwarding plane FIB table structure proposed by the present invention to carry out the longest prefix matching query in the addressable Bloom data structure for the message name prefix, as shown in Figure 5, the following steps are included:

Step 3-1. The positioning array MA is initialized. Set the values of all bits in the positioning array MA to 0;

Step 3-2. Enter the packet name prefix. Inputting the corresponding message name prefix into the locatable Bloom memory, wherein the length of the message name prefix corresponds to the number of the locatable Bloom memory;

Step 3-3: Perform K times of hash mapping operations on the packet name prefix. Among them, MD5 or SHA1 is selected as the hash function, and at the same time, the encoding length and the mapping times K value are adjusted according to the specific size of the general-purpose Bloom filter array BF;

Step 3-4, judging whether the BF bit values of the general-purpose Bloom filter array mapped by K times of hash mapping operations are all 1.

If the mapping values are all 1, then the packet name prefix exists in the prefix set corresponding to the locateable Bloom memory, and proceed to steps 3-5; otherwise, the packet name prefix does not exist in the locateable Bloom memory In the prefix set corresponding to the type Bloom memory, and perform steps 3-7;

Step 3-5, calculating the value of the MA positioning array. Calculate the value of the positioning array MA according to the mapping value of K hash mapping operations in the general-purpose Bloom filter array BF;

Step 3-6, output the offset address. The value of the positioning array MA calculated in steps 3-5 is output to the FIB system as the offset address of the message name prefix in the off-chip static memory;

Steps 3-7, return the query result to the forwarding plane, and end the longest prefix matching query.

For example, as shown in Figure 2 and Figure 5, in order to realize the mapping operation from BF (general Bloom filter array BF) to MA (positioning data MA) to calculate the value of positioning array MA, first, divide BF into J on average parts of the same size, while the size of the MA array is defined as J bits. Each part of the BF corresponds to a bit of the MA array in turn. When performing prefix matching, if there is a hash map in the i (i=1, 2, ..., J-1, J) part of the BF, the value of the i-th bit of the corresponding MA array will be set to 1 , otherwise the value of this bit is 0. Finally, the value of the J-bit MA positioning array is obtained.

Experimental example:

By using C++ language, the content-centric network forwarding plane FIB table structure of the present invention has been deployed for software testing on a PC configured as Intel Core i3-3220 3.30GHz, DDR3 4GB SDRAM. Considering the design requirements of the content-centric network forwarding plane FIB table, two million messages from DMOZ and ALEXA are input into the content-centric network forwarding plane FIB table. Experimental results show that the content-centric network forwarding plane FIB table can be deployed on-chip using SRAM, and can meet the communication requirements of the current Internet with an error rate of less than 1%. This shows that the content-centric network forwarding plane FIB table structure proposed by the present invention can not only realize efficient search and update operations, but also has good deployability.

Although the present invention has been described above in conjunction with the accompanying drawings, the present invention is not limited to the above-mentioned specific embodiments, and the above-mentioned specific embodiments are only illustrative, rather than restrictive. Under the enlightenment of the present invention, many modifications can be made without departing from the gist of the present invention, and these all belong to the protection of the present invention.

Claims (1)

1. a kind of search method of content center network Forwarding plane fib table structure, wherein, it is flat to use content center network forwarding Face fib table structure and can the grand data structure of location type cloth；

The content center network Forwarding plane fib table structure includes a piece internal memory storage unit and the outer memory cell of two pieces； Described internal memory storage unit by can the grand memory group of location type cloth form, it is described can the grand memory group of location type cloth using it is multiple can The grand data structure of location type cloth is as data directory；In the outer memory cell of two pieces, the outer memory cell of a piece is by CBF memories Group is formed, and the CBF memories group, to realize fib table renewal operation, list is stored outside another piece using multiple CBF data structures Member is the outer static memory of piece, and described outer static memory is using static storage structure to store the forwarding of real data message Information；

It is described can the grand data structure of location type cloth include a universal Bloom filter arrays BF and one positioning array MA, Wherein described universal Bloom filter arrays BF is used to determine an element whether in set, and the positioning array MA is One has certain mapping relations bit array with the universal Bloom filter arrays BF, according to the positioning array MA's Numerical value determine the element can the grand data structure of location type cloth map memory in offset address；

It is characterized in that：The search method includes fib table message matching inquiry, fib table renewal and message name prefix can Longest prefix match inquiry is carried out in the grand data structure of location type cloth；Wherein：

The step of fib table message matching inquiry, includes：

Step 1-1, by the message name based on hierarchy be input to it is described can be in the grand memory group of location type cloth；

Step 1-2, according to longest prefix match principle described inquiry operation can be carried out parallel in the grand memory group of location type cloth, To judge the forwarding information of the message name whether in fib table,

If in the message name that there can be matching in the grand memory group of location type cloth, step 1-3 is performed；

If in the message name that matching can be not present in the grand memory group of location type cloth, step 1-4 is performed；

Step 1-3, forwarding information is read in static memory outside piece, according to can the grand memory group of location type cloth output knot Fruit, offset address of the longest matching prefix in piece external memory static state reservoir is obtained, and static state is deposited outside piece according to the offset address The next-hop routing forwarding information corresponding to the longest matching prefix is read in reservoir；

Step 1-4, fib table Query Result is returned to Forwarding plane, terminates fib table message matching inquiry；

The step of fib table updates includes：

Step 2-1, by the message name prefix to be updated input CBF memory groups based on hierarchy；

Step 2-2, according to longest prefix match principle in the CBF memories corresponding to the message name prefix to be updated The renewal operation of CBF memories is performed, and judges whether the CBF memory bits bit value corresponding to the message name prefix becomes Change,

If the numerical value of CBF memory bits corresponding to message name prefix changes in the CBF memories group, i.e., It is changed into 1 from 0 or is changed into 0 from 1, then performs step 2-3；

If the numerical value of CBF memory bits corresponding to message name prefix does not change in CBF memory groups, Perform step 2-4；

Step 2-3, can location type cloth be grand deposits in piece internal memory storage unit corresponding to CBF memories in the outer CBF memory groups of synchronous piece The numerical value of reservoir bit；

Step 2-4, fib table renewal result is returned to Forwarding plane, terminates fib table renewal；

Message name prefix includes can carry out longest prefix match inquiry in the grand data structure of location type cloth the step of：

Step 3-1, the numerical value for positioning all bits in array MA is disposed as 0；

Step 3-2, to it is described this can in the grand memory of location type cloth input with it corresponding to message name prefix, wherein message The length of name prefix correspond to can the grand memory of location type cloth numbering；

Step 3-3, K Hash mapping operation is carried out to the message name prefix, wherein, hash function selects MD5 or SHA1, Meanwhile code length and mapping number K values are adjusted according to universal Bloom filter arrays BF specific size；

Step 3-4, judge whether is universal Bloom filter arrays BF bits numerical value that the operation of K Hash mapping mapped It is all 1,

If mapping value is all 1, step 3-5 is performed；Otherwise, step 3-7 is performed；

Step 3-5, the mapping value in universal Bloom filter arrays BF is operated according to K Hash mapping, calculates positioning Array MA numerical value；

Step 3-6, the numerical value that step 3-5 is calculated to gained positioning array MA is deposited as message name prefix static state outside piece Offset address in reservoir is exported into FIB system；

Step 3-7, Query Result is returned to Forwarding plane, terminates longest prefix match inquiry.