CN102271087B - A kind of method for searching route and device - Google Patents

Abstract

The present invention discloses a routing search method and device. Based on the counting bloom filter data structure, routing table item information is stored in an external memory or a routing addressing chip, and the routing table item corresponding to the destination IP address is searched from the stored routing table item information. information. Compared with the stream processing based on the tree structure in the prior art, the present invention obviously reduces the storage requirement and is easy to maintain the stored routing table items. Adopting the routing search solution of the present invention reduces the use of routing addressing chips, and does not generate large power consumption and heat generation.

Description

Method and device for routing search

technical field

The invention relates to the technical field of data communication, in particular to a route search method and device.

Background technique

With the rapid development of the Internet, the interface rate of the core router used for the interconnection of the backbone network reaches 100Gbps, which requires the core router to support a large-capacity routing table with a routing lookup rate of several million times per second.

Each routing entry information in the routing table contains prefix and next hop information. When searching for the destination IP (Internet Protocol, Internet Protocol) address, it is necessary to obtain the longest matching prefix. Due to the need for high-speed searching, the software searching method is no longer applicable. In recent years, researchers have proposed a variety of hardware search methods to increase the search rate, among which pipeline processing and TCAM (ternary content addressable memory, ternary content addressable memory) are the most popular.

Pipeline processing is usually based on a tree structure, which can get a higher throughput rate. However, due to the particularity of the tree structure, it is difficult to achieve storage balance at each level of pipeline, and each tree node must maintain child node information, resulting in a large storage requirement. Even if some optimization methods can be used to achieve storage balance, it is easy to cause too many pipeline stages and it is difficult to maintain.

TCAM is currently a widely used technology in routing lookup. The lookup process is simple, but to meet the search rate requirement of 100Gbps, multiple TCAMs are required to schedule lookups, and power consumption and heat generation will become serious problems.

Contents of the invention

The technical problem to be solved by the present invention is to provide a routing search method and device, which realize routing search based on bloom filter algorithm, and overcome the defects of high power consumption and heat generation caused by implementing routing search by hardware in the prior art.

The technical solution adopted in the present invention is that the route search method includes:

Based on the counting bloom filter data structure, the routing table entry information is stored in the external memory or the routing addressing chip, and the routing table entry information corresponding to the destination IP address is searched from the stored routing table entry information.

Further, the storing routing table item information based on the counting bloom filter data structure specifically includes:

Based on the counting bloom filter data structure, all the routing table item information in the routing table is stored in the external memory, and the routing table item information that overflows during the process of storing in the external memory is stored in the routing addressing chip.

Further, the searching for the routing table item information corresponding to the destination IP address from the stored routing table item information based on the counting bloom filter data structure specifically includes:

Based on the counting bloom filter data structure, look up the routing table entry information corresponding to the destination IP address in the external memory, and at the same time look up the routing table entry information corresponding to the destination IP address in the routing addressing chip;

If the routing table entry information is only found in the external memory or the routing addressing chip, use it as the routing table entry information corresponding to the destination IP address;

If the routing table entry information is found in both the external memory and the routing addressing chip, the one with the longer prefix is used as the routing table entry information corresponding to the destination IP address.

Further, the searching the routing entry information corresponding to the destination IP address in the external memory based on the counting bloom filter data structure specifically includes:

Match the target prefix for the destination IP address based on the counting bloom filter data structure, and determine the external memory address according to the bit set to 1 in the target prefix;

The external memory is accessed through the external memory address to obtain the longest prefix corresponding to the destination IP address, and the routing table entry information where the longest prefix is located is the routing table entry information corresponding to the finally found destination IP address.

Further, the matching target prefix for the destination IP address based on the counting bloom filter data structure, and determining the external memory address according to the bit set to 1 in the target prefix, specifically includes:

Let the counting bloom filter data structure correspond to more than two storage spaces respectively, and match the destination IP address in parallel in each storage space to obtain the corresponding result set and address set;

After ANDing the result sets corresponding to each storage space, the target prefix matching the target IP address is obtained;

The external memory address is determined according to the content of the corresponding position in the address set corresponding to the bit set to 1 in the target prefix.

Based on the above method, the present invention also provides a routing search device, including:

The storage operation unit is used to store routing table item information in the external memory or routing addressing chip based on the counting bloom filter data structure;

A search operation unit, configured to search for routing table entry information corresponding to the destination IP address from stored routing table entry information based on the counting bloom filter data structure.

Further, the storage operation unit specifically includes:

The first storage operation module is used to store all the routing entry information in the routing table into the external memory based on the counting bloom filter data structure, and call the second storage operation submodule when overflow occurs;

The second storage operation module is used for storing the routing table item information overflowed during the storage into the external memory into the routing addressing chip.

Further, the search operation unit specifically includes:

The first search operation module is used to search the routing table entry information corresponding to the destination IP address in the external memory based on the counting bloom filter data structure;

The second search operation module is used to start simultaneously with the first search operation module, and find the routing entry information corresponding to the destination IP address in the routing addressing chip;

The comparison module is configured to use the one with the longer prefix as the routing table entry information corresponding to the destination IP address when both the first search operation module and the second search operation module find the routing table entry information.

Further, the first search operation module specifically includes:

The address determination submodule is used to match the target prefix for the destination IP address based on the counting bloom filter data structure, and determine the external memory address according to the bit set to 1 in the target prefix;

The prefix determination submodule is used to access the external memory through the external memory address, and obtain the longest prefix corresponding to the destination IP address, and the routing table entry information where the longest prefix is located is the routing table entry corresponding to the destination IP address that is finally found information.

Further, the address determination submodule is specifically used for:

Match the destination IP address in parallel in two or more storage spaces corresponding to the counting bloom filter data structure to obtain the corresponding result set and address set, and compare the result sets corresponding to each storage space to obtain the target prefix matching the destination IP address , determine the external memory address according to the content of the corresponding position in the address set corresponding to the bit set to 1 in the target prefix.

Adopt above-mentioned technical scheme, the present invention has following advantage at least:

The routing search method and device of the present invention realize routing search based on the counting bloom filter data structure. Compared with the tree structure-based pipeline processing in the prior art, the storage capacity requirements are significantly reduced, and the stored routing is also easy. Table entries are maintained. Adopting the routing search solution of the present invention reduces the use of routing addressing chips, and does not generate large power consumption and heat generation.

Description of drawings

Fig. 1 is the flow chart of the route lookup method of the first embodiment of the present invention;

FIG. 2 is a schematic diagram of a route lookup scheme according to the first embodiment of the present invention;

3 is a schematic diagram of the process of searching the routing entry information corresponding to the destination IP address in the external memory based on the counting bloom filter data structure in step S103 of the first embodiment of the present invention;

FIG. 4 is a specific flowchart of step A1 of the first embodiment of the present invention;

5 is a schematic structural diagram of a route lookup device according to a second embodiment of the present invention;

6 is a schematic structural diagram of a route lookup device according to a third embodiment of the present invention;

Fig. 7(a) is a schematic structural diagram of the first and second storage spaces in the fourth embodiment of the present invention;

Fig. 7(b) is a schematic diagram of the structure of the third storage space in the fourth embodiment of the present invention;

FIG. 8 is a schematic diagram of the corresponding relationship between the filter index index of the third storage space and the offset address of the off-chip dram (dynamic random access memory, dynamic random access memory) in the fourth embodiment of the present invention.

detailed description

In order to further explain the technical means and functions adopted by the present invention to achieve the intended purpose, the present invention will be described in detail below in conjunction with the accompanying drawings and preferred embodiments.

In the first embodiment of the present invention, a route search method, as shown in Figure 1, includes the following specific steps:

Step S101, based on the counting bloom filter data structure, store all the routing table item information in the routing table into the external memory, store the overflowing routing table item information in the process of storing the external memory into the routing addressing chip, and the routing addressing chip Can be TCAM. External memory can be off-chip dram. Step S101 specifically includes:

Assume that the counting bloom filter data structure corresponds to a first storage space with a bit width of M bits and an address length of N bits. M can be an integer greater than or equal to 1, and the larger M is, the higher the probability of false positives occurring in subsequent searches. Low, but limited by the storage space provided by the hardware, the maximum value of M can usually be 4.

The value that can be filled in each unit block of the first storage space is 0, 1, ..., 2 ^M -1, and the address of each unit block in the first storage space is represented by a filter index index; in the art It is known that, using the P1 hash functions bound to the storage space corresponding to the counting bloom filter data structure, the value of the result obtained from the operation on the prefix in the routing entry information will not exceed the address range of the storage space.

Perform P1 hash function operations on the prefix in each routing entry information in the routing table, each hash calculation can get a filter index index of a unit block, and count the number of occurrences of each filter index index Accumulate and fill the count value into the unit block corresponding to the filter index index, and the initial value of the count value is 0.

If the count value of the filter index index obtained by the current routing table item information through a hash function operation is 2 ^M -1 before the accumulation, it means overflow occurs, the count value will not be accumulated, and the routing table item information will be filled Into the routing addressing chip;

If the count value of the filter index index obtained by P1 hash function operations on the prefix in the current routing entry information does not exceed 2 ^M -1, select the filter index index with the smallest count value and offset it in the external memory The address is (2 ^M -1)×index and fill in the information of this routing entry.

As known in the art, the conversion relationship between the address length N of the storage space, the number P1 of hash functions, and the false positive probability F during routing lookup in the external memory is as follows:

N=ceil((n log(F))/log(1.0/(pow(2.0, log(2.0))))); P1=round(Nlog(2.0)/n); n represents the routing entry to be inserted number.

Step S102, searching the internal memory for routing entry information corresponding to the destination IP address, if found, the process ends, if not found, then step S103 is executed. A schematic diagram of a routing lookup solution in this embodiment is shown in FIG. 2 . The internal memory may be on-chip sram (static random access memory, static random access memory), or on-chip edram (enhanced dynamic random access memory, enhanced dynamic random access memory).

Step S103, based on the counting bloom filter data structure, look up the routing table entry information corresponding to the destination IP address in the external memory, and at the same time look up the routing table entry information corresponding to the destination IP address in the routing addressing chip. According to the situation of the search, it is divided into the following two Ways to deal with:

1) If the routing table entry information is only found in the external memory or routing addressing chip, then use it as the routing table entry information corresponding to the destination IP address;

2) If the routing table entry information is found in both the external memory and the routing addressing chip, the one with the longer prefix is used as the routing table entry information corresponding to the destination IP address.

In step S103, the process of searching the routing entry information corresponding to the destination IP address in the external memory based on the counting bloom filter data structure, as shown in Figure 3, specifically includes:

A1, based on the counting bloom filter data structure, match the target prefix for the destination IP address. As shown in Figure 4, step A1 specifically includes:

Let the length of the destination IP address be L, and the range of all prefixes of the destination IP address be from length 1 to length L; let the counting bloom filter data structure correspond to more than two storage spaces respectively, and each unit block of the storage space The address is represented by the filter index index, and different storage spaces are respectively bound to different hash functions. The bit width of the space can be the same or different, and the address length can be the same or different. In this step, M can be an integer greater than or equal to 1, and the larger M is, the lower the probability of false positives occurring in subsequent searches, but limited by the storage space provided by the hardware, M can usually be up to 4 at most.

A11, inserting information related to the destination IP address into each storage space.

In a specific storage space, P2 hash function operations are performed sequentially on all prefixes of the destination IP address, each hash calculation can obtain a filter index index of a unit block, and the number of occurrences of each filter index index is calculated The count is accumulated and the count value is filled into the unit block corresponding to the filter index index:

If the count value of the filter index index obtained by the current length prefix of the destination IP address through a hash function operation does not reach the upper limit of the count value before the accumulation, the count value will be increased by 1;

If the count value of the filter index index obtained by the current length prefix of the destination IP address through a certain hash function operation has reached the upper limit of the count value before the accumulation, the count value is no longer accumulated. Unit blocks in storage spaces with different bit widths have different upper limit count values. Let M1 be the bit width of the storage space, then the upper limit count value of the storage space is 2 ^M1 -1.

A12. Determine the result set and address set corresponding to the destination IP address according to the count values in each storage space.

The destination IP address is matched in parallel in each storage space to obtain a corresponding result set and address set. Each result set and address set can be regarded as an array with a length of L, and the bit set to 1 in the result set corresponds to the content filled in the corresponding position of the address set.

The specific process of matching in each storage space is: in a specific storage space, if P2 hash function operations are performed on a prefix of a certain length of the destination IP address, the units corresponding to P2 filter indexes are obtained. If the count values filled in the block are all non-zero, then the prefix is successfully matched in the storage space, and the corresponding position of the prefix length in the result set of length L is set to 1, and P2 filter indexes are corresponding to Fill in the filter index index corresponding to the minimum of the count values filled in the unit block of the address set to the position corresponding to the length of the prefix (specially, if the bit width M=1 of the storage space, then the count value is 1 The filter index index arbitrarily selects one to fill in the position corresponding to the length of the prefix in the address set);

If at least one of the count values filled in the unit blocks corresponding to the P2 filter index indexes obtained by performing P2 hash function operations on the prefix of each length of the destination IP address is 0, then the prefix is stored in the storage space If the matching fails, the position corresponding to the length of the prefix in the result set with length L is set to 0, and the position corresponding to the length of the prefix in the address set with length L is set to 0.

A13, after combining the result sets corresponding to each storage space, the target prefix matching the target IP address is obtained.

A2, according to the filter index index of the corresponding position in the address set corresponding to the bit set in the target prefix, determine the external memory address as (2 ^M -1) × index, where M is the first storage corresponding to the counting bloom filter data structure The bit width of the space.

A3, access the external memory through the external memory address determined in step A2, and obtain the longest prefix corresponding to the destination IP address (when there are more than two external memory addresses, obtain the longest prefix corresponding to the destination IP address through comparison), the said The routing table entry information where the longest prefix is located is the routing table entry information corresponding to the finally found destination IP address.

Step S104, filling the routing entry information corresponding to the found destination IP address into the internal memory.

In the second embodiment of the present invention, a routing search device, as shown in Figure 5, includes the following components:

1) The storage operation unit 10 is configured to store routing table entry information in an external memory or a routing addressable chip based on the counting bloom filter data structure. The storage operation unit 10 specifically includes:

The first storage operation module 11 is configured to store all routing table entry information in the routing table into the external memory based on the counting bloom filter data structure, and call the second storage operation submodule when overflow occurs. The routing search device of the present invention can be realized on FPGA (Field-Programmable Gate Array, field programmable gate array) or ASIC (Application Specific Integrated Circuits, application specific integrated circuit) chip, and the external memory can be off-chip dram.

Specifically, let the counting bloom filter data structure correspond to a first storage space with a bit width of M bits and an address length of N bits. M can be an integer greater than or equal to 1, and the larger M is, the false positive will occur in the subsequent search. The lower the probability is, but limited by the storage space provided by the hardware, M can usually be up to 4 at most. The values that can be filled in each unit block of the first storage space are ⁰ , 1, .

The first storage operation module 11 performs P1 hash function operations on the prefix in each routing entry information in the routing table, and each hash calculation can obtain the filter index index of a unit block, and each filter index The number of occurrences of index is counted and accumulated, and the count value is filled into the unit block corresponding to the filter index index, and the initial value of the count value is 0.

If the count value of the filter index index obtained by the current routing table item information through a hash function operation is ^2M -1 before the accumulation, it means that overflow occurs, and the count value is no longer accumulated, and the second storage operation module 12 is called. ;

If the count value of the filter index index obtained by P1 hash function operations on the prefix in the current routing entry information does not exceed 2 ^M -1, select the filter index index with the smallest count value and offset it in the external memory The address is (2 ^M -1)×index and fill in the information of this routing entry.

The second storage operation module 12 is configured to store routing table entry information overflowed during storage into the external memory into the routing addressing chip. The routing addressing chip may be a TCAM.

2) The search operation unit 20 is configured to search the routing table entry information corresponding to the destination IP address from the stored routing table entry information based on the counting bloom filter data structure. Find the operating unit 20, specifically including:

The first search operation module 21 is used to search the routing entry information corresponding to the destination IP address in the internal memory. If found, the operation ends; if not found, the second search operation sub-module is invoked. The internal memory can be on-chip sram or on-chip edram.

The second search operation module 22 is used to search the routing table entry information corresponding to the destination IP address in the external memory based on the counting bloom filter data structure: if found, then fill the routing table entry information corresponding to the destination IP address found into the internal memory in; if not found, call the third search operation submodule. The second search operation module 22 specifically includes:

The address determination sub-module 221 is configured to match the target prefix for the destination IP address based on the counting bloom filter data structure, and determine the external memory address according to the bit set to 1 in the target prefix.

Specifically, let the length of the destination IP address be L, and the range of all prefixes of the destination IP address be from length 1 to length L; let the counting bloom filter data structure correspond to more than two storage spaces respectively, and each of the storage spaces A unit block address is represented by a filter index index, and different storage spaces are bound to different hash functions. In order to facilitate implementation, the number of hash functions bound to different storage spaces in this embodiment is the same, all of which are P2 .

In a specific storage space, P2 hash function operations are performed sequentially on all prefixes of the destination IP address, each hash calculation can obtain a filter index index of a unit block, and the number of occurrences of each filter index index is calculated The count is accumulated and the count value is filled into the unit block corresponding to the filter index index:

If the count value of the filter index index obtained by a hash function operation on the current routing entry information does not reach the upper limit of the count value before the accumulation, the count value will be increased by 1;

If the count value of the filter index index obtained by the current routing entry information through a certain hash function operation has reached the upper limit of the count value before the accumulation, the count value will not be accumulated; the unit blocks in storage spaces with different bit widths have different The upper limit of the count value of , if M1 is the bit width of the storage space, then the upper limit of the count value of the storage space is 2 ^M1 -1. Parallel matching of destination IP addresses in each storage space to obtain corresponding result sets and address sets;

After ANDing the result sets corresponding to each storage space, the target prefix matching the target IP address is obtained.

According to the filter index index of the corresponding position in the address set corresponding to the bit set in the target prefix, determine the external memory address as (2 ^M -1) × index, where M is the first storage space corresponding to the counting bloom filter data structure bit width.

The prefix determination submodule 222 is used to access the external memory through the external memory address to obtain the longest prefix corresponding to the destination IP address (when there are more than two external memory addresses, obtain the longest prefix corresponding to the destination IP address through comparison), so The routing table entry information where the longest prefix is located is the routing table entry information corresponding to the finally found destination IP address.

The third search operation module 23 is configured to start at the same time as the second search operation module 22, search in the routing addressing chip and fill in the routing entry information corresponding to the found destination IP address into the internal memory.

The comparison module 24 is used for when the second search operation module 22 and the third search operation module 23 both find the routing table entry information, use the one with the longer prefix as the routing table entry information corresponding to the destination IP address, and fill in In the internal memory, if it is different from the results filled in by the above two search modules, the result of the comparison module 24 shall prevail.

It should be noted that there are only 1) in the present invention, one of the second search operation module or the third search operation module finds the routing table entry information corresponding to the destination IP address; 2) the second search operation module and the third search operation module The search operation module finds the routing table entry information corresponding to the destination IP address, in both cases.

Compared with the existing search methods, the routing search solution provided by the present invention has the following advantages: 1) because it is based on the counting bloom filter data structure, the data structure does not increase with the increase of routing table items after initialization, and the storage consumption is very small and easy Management; 2) The process of determining the offset address of the off-chip dram in the chip only needs to consume the access time equivalent to one on-chip sram, which greatly improves the routing search rate.

The third embodiment of the present invention is a routing search device. This embodiment is substantially the same as the second embodiment. The difference is that the specific composition of the search operation unit 20 and its completed functions do not involve the search in the internal memory. Specifically, as shown in FIG. 6, the search operation unit 20 specifically includes:

The first search operation module 41 is configured to search the external memory for routing entry information corresponding to the destination IP address based on the counting bloom filter data structure.

The second search operation module 42 is configured to start simultaneously with the second search operation module 22 to find the destination IP address in the routing addressing chip.

The comparison module 24 is used for when the second search operation module 22 and the third search operation module 23 both find the routing table entry information, use the one with the longer prefix as the routing table entry information corresponding to the destination IP address, and fill in In the internal memory, if it is different from the results filled in by the above two search modules, the result of the comparison module 24 shall prevail.

Because the access speed of the internal memory is fast, but the capacity is small, in the second embodiment, the next hop information corresponding to the destination IP address that has been searched is put into the internal memory, and the internal memory can be further improved by first accessing the internal memory during the subsequent search. Therefore, the search efficiency in this embodiment is lower than that in the second embodiment.

In the fourth embodiment of the present invention, taking three specific storage spaces corresponding to the counting bloom filter data structure as an example, the process of routing storage and searching in the off-chip dram is introduced:

The bit width of the first and second storage spaces is 1, and the address length is 10. Its structure is shown in Figure 7(a). Each unit block (a box in the figure is a unit block) in these two storage spaces is 1 bit, the initial value is 0.

The bit width of the third storage space is that the bit width is 2, and the address length is 10. Its structure is shown in Figure 7(b). Each unit block in the third storage space (the upper and lower boxes in the figure are a unit block) It is 2 bits, the initial value is 00, and the binary count values that each unit block can represent are 00, 01, 10, and 11, which correspond to the decimal count values 0, 1, 2, and 3, respectively.

In order to ensure that the overall false positive of the system is 10 ^-4 , the above three storage spaces require a total of 12 hash functions, and each storage space corresponds to 4 hash functions and 32 prefix lengths. The hash function corresponding to a certain storage space can be Optional, it can be different from the other two storage spaces.

1. Insert routing table entries to form a forwarding structure:

1) Based on the counting bloom filter data structure, store all the routing table item information in the routing table into the off-chip dram, and store the routing table item information that overflows during the process of storing into the off-chip dram into the TCAM.

For the third storage space, four hash function operations are performed on the prefix in each piece of routing table information in the routing table, and each piece of routing table information includes prefix and next hop information.

Each time the hash hits the filter index index of the third storage space, the count value of the filter index index is increased by 1, and filled into the corresponding unit block. Because the initialization count value in each unit block is 0, if the filter index index corresponding to the unit block is not hit, the count value remains unchanged.

When the count value of a current filter index index is less than 3, if a certain hash hits the filter index index, the count value will be increased by 1, because each unit block of the third storage space can only mark up to 3 non-zero Count value, so that the address length of the external dram is 3 times the total length of the filter index index of the third storage space (that is, calculated by 2 ² -1), therefore, the hit filter index index×3 is used as a slice For the offset address of the external dram, insert the routing entry information of the current hash operation into the address range from index×3 to index×3+2 of the off-chip dram. The corresponding relationship between the filter index index of the third storage space and the offset address of the off-chip dram is shown in FIG. 8 .

When the count value of the current filter index index is less than 3, it means that the unit block in the third storage space is full. If a certain hash hits the filter index index, overflow occurs, and the count value is no longer accumulated, and Insert the routing table entry information (including prefix and next hop information) into the TCAM. According to experimental statistics, this part of overflow routing table entries accounts for 0.1% of the entire routing table entries.

The address redundancy of the off-chip DRAM can reduce the probability of overflow, that is, the number of TCAM insertions. At the same time, in order to reduce the interruption of the flow caused by false positives in the third storage space, the DRAM particles can be redundant, that is, add two chips outside the chip. When storing the off-chip dram with the same content, and searching for the information of two offset addresses corresponding to a prefix at the same time, it can effectively reduce the probability of interruption.

2) Based on the counting bloom filter data structure, the prefixes of all lengths in the destination IP address are subjected to four hash function operations, and inserted into the first and second storage spaces according to the hash function operation results.

The initial count value of each unit block in the first and second storage spaces is 0, and the prefixes of all lengths of the destination IP address are respectively subjected to 4 times of hash function operations to different filter indexes (4 times of hashing can ensure that the storage space The probability of false positive is 0.05):

If the count value of the filter index index obtained by the current length prefix of the destination IP address through a certain hash function operation is 0 before the accumulation, the count value is increased by 1;

If the count value of the filter index index obtained by a certain hash function operation of the current length prefix of the destination IP address is non-zero before the accumulation, the count value is no longer accumulated.

2. Find the next hop information for a given destination IP address:

1) Match the destination prefix of the destination IP address.

Search in parallel in the first and second storage spaces. In each specific storage space, each prefix (from length 1 to length 32) of the destination IP address is matched, and a 32bits result set is generated after completion. For any of the length prefixes, if the filter indexes corresponding to the 4 results obtained through 4 hash function calculations are all non-zero, it proves that the prefix is successfully matched in the storage space, and the prefix is set in the corresponding address of the result set. 1 (The result set can be regarded as an array with a length of 32 bits and subscripts starting from 0. If the prefix with a length of k is hit, the k-1th position of the result set is 1), and the filter corresponding to the 4 results Fill in the corresponding position of the prefix in the address set with the smallest count value in the index index;

If only one of the filter indexes corresponding to the 4 results is 0, the prefix is not matched, and the corresponding position of the prefix is 0 in the result set.

2) The result sets corresponding to the two storage spaces are combined to obtain the final result set, which is the target prefix.

3) Find the longest prefix and next hop information in dram according to the target prefix.

According to the filter index index of the corresponding position in the address set corresponding to the bit set to 1 in the target prefix, the off-chip dram address is determined to be 3×index (3 is calculated by 2 ² -1).

Access the off-chip dram through the address 3×index. In the first step, the overflow routing table entry is not inserted into the off-chip dram but inserted into the TCAM. At the same time, the TCAM search is performed on the destination IP address, that is, the search result may be It will appear in TCAM or off-chip dram, but since only 0.1% of the total entries are inserted in TCAM, the impact on performance is small. The longest prefix corresponding to the destination IP address is obtained through comparison, and the routing table entry information where the longest prefix is located is the routing table entry information corresponding to the finally found destination IP address.

In addition, if two off-chip drams are used to search in parallel, the probability that both the longest and the second-longest prefixes in the target prefix appear false positive is 10 ^-4 ×10 ^-4 = 10 ^-8 , that is, the probability of pipeline interruption is 10 ^-8 .

The fifth embodiment of the present invention introduces an example of inserting and searching routing entries on the basis of the above four embodiments. This example uses four storage spaces of the counting bloom filter data structure, and different storage spaces are bound to different hash function.

The format of the routing table entry is: (prefix, next hop information is the port number).

Suppose there are routing table entries: (10.10.*.*/16, 5), (10.*.*.*/8, 2), where the prefix 10.10.*.* is replaced by pre1, and the prefix 10.*.* .* replace with pre2:

The index index of the filter inserted into the first storage space by pre1 is [2(1), 4(3), 6(2), 7(2)], and the numbers in the last group of parentheses indicate the count value, then the minimum count Value principle, address 2 should be selected, then the offset address of the off-chip dram is 2×3=6, there is no overflow (the count value of address 2 is 1, indicating that only one item is inserted in the off-chip dram, a total of 3 items can be inserted, Therefore, there is no overflow), the prefix is stored at the offset address of off-chip dram at 6.

The index index of the filter inserted into the first storage space by pre2 is [3(2), 4(3), 2(2), 7(1)], and the numbers in the last group of parentheses indicate the count value, and the minimum count Value principle, address 7 should be selected, then the offset address of the off-chip dram is 7×3=21, if there is no overflow, the prefix is stored at the offset address of the off-chip dram at 21.

Suppose for the destination IP address to be matched: IP1(10.10.10.10), IP2(11.10.10.10):

The three result sets obtained after the 32 prefixes of IP1 are matched in parallel in the second to fourth storage spaces, and a 32-bit target prefix is obtained after the three result sets are combined. Assuming that there are two off-chip drams, the target is taken The higher hit in the prefix is set to 1--the count value of the 16th bit and the 8th bit in the address set is multiplied by 3 to obtain the offset address 6 and 21 of the off-chip dram, access two off-chip drams, and obtain two Prefix and next hop information, after comparison, pre1 is the real longest prefix, then the data packet carrying the destination IP address is forwarded to port 5.

Assuming a false positive occurs and IP2 hits pre2, the 8th bit of the target prefix corresponding to IP2 hits and is set to 1. It is found that the prefix obtained after accessing the off-chip dram by taking the offset address 21 does not match IP2. If it is not found in TCAM, reduce the position of the target prefix hit set bit, that is, take the hit set bit lower than the 8th bit to calculate the offset address, continue to search in the off-chip dram and TCAM, and so on, and finally The one with the longer prefix must be taken as the route lookup result.

Through the description of the specific implementation, it should be possible to gain a deeper and more specific understanding of the technical means and effects of the present invention to achieve the intended purpose. However, the attached drawings are only for reference and description, and are not used to explain the present invention. limit.

Claims (6)

1. A routing search method, characterized in that, comprising: Based on the counting bloom filter data structure, all the routing table item information in the routing table is stored in the external memory, and the routing table item information that overflows during the process of storing in the external memory is stored in the routing addressing chip; Based on the counting bloom filter data structure, look up the routing table entry information corresponding to the destination IP address in the external memory, and at the same time look up the routing table entry information corresponding to the destination IP address in the routing addressing chip; The routing table entry information corresponding to the destination IP address is searched in the external memory based on the counting bloom filter data structure, specifically including: Match the target prefix for the destination IP address based on the counting bloom filter data structure, and determine the external memory address according to the bit set to 1 in the target prefix; The external memory is accessed through the external memory address to obtain the longest prefix corresponding to the destination IP address, and the routing table entry information where the longest prefix is located is the routing table entry information corresponding to the finally found destination IP address. 2. The route lookup method according to claim 1, characterized in that, the method further comprises: If the routing table entry information is only found in the external memory or the routing addressing chip, use it as the routing table entry information corresponding to the destination IP address; If the routing table entry information is found in both the external memory and the routing addressing chip, the one with the longer prefix is used as the routing table entry information corresponding to the destination IP address. 3. The routing search method according to claim 1, wherein the matching target prefix for the destination IP address based on the countingbloom filter data structure determines the external memory address according to the bit of setting 1 in the target prefix, specifically comprising: Let the counting bloom filter data structure correspond to more than two storage spaces respectively, and match the destination IP address in parallel in each storage space to obtain the corresponding result set and address set; After ANDing the result sets corresponding to each storage space, the target prefix matching the target IP address is obtained; The external memory address is determined according to the content of the corresponding position in the address set corresponding to the bit set to 1 in the target prefix. 4. A routing search device, characterized in that, comprising: A storage operation unit, configured to store routing table entry information based on the counting bloom filter data structure; The search operation unit is used to search the routing table entry information corresponding to the destination IP address from the stored routing table entry information based on the counting bloom filter data structure; The storage operation unit specifically includes: The first storage operation module is used to store all the routing entry information in the routing table into the external memory based on the counting bloom filter data structure, and call the second storage operation submodule when overflow occurs; The second storage operation module is used to store the routing table entry information overflowed in the process of storing in the external memory into the routing addressing chip; The search operation unit specifically includes: The first search operation module is used to search the routing table entry information corresponding to the destination IP address in the external memory based on the counting bloom filter data structure; The second search operation module is used to start simultaneously with the first search operation module, and find the routing entry information corresponding to the destination IP address in the routing addressing chip; The first search operation module specifically includes: The address determination submodule is used to match the target prefix for the destination IP address based on the counting bloom filter data structure, and determine the external memory address according to the bit set to 1 in the target prefix; The prefix determination submodule is used to access the external memory through the external memory address, and obtain the longest prefix corresponding to the destination IP address, and the routing table entry information where the longest prefix is located is the routing table entry corresponding to the destination IP address that is finally found information. 5. The routing search device according to claim 4, wherein the search operation unit further comprises: The comparison module is configured to use the one with the longer prefix as the routing table entry information corresponding to the destination IP address when both the first search operation module and the second search operation module find the routing table entry information. 6. The routing search device according to claim 4, wherein the address determination submodule is specifically used for: Match the destination IP address in parallel in two or more storage spaces corresponding to the counting bloom filter data structure to obtain the corresponding result set and address set, and compare the result sets corresponding to each storage space to obtain the target prefix matching the destination IP address , determine the external memory address according to the content of the corresponding position in the address set corresponding to the bit set to 1 in the target prefix.