Shulou(Shulou.com)06/01 Report--

After writing two propositional compositions, it got out of hand. If you want to go on a business trip to Beijing, do two more articles before you leave! (written on the evening of 2015-03-21 and arrived in Beijing the next day)

When I describe the Dimension Tree structure of packet classification, I use a lot of binary tree structure, which means that I have to keep turning left and right, and where I turn, it is inevitable to compare. I need to be exempt from the comparison operation. How is that possible? Of course there is. Space for time. Moreover, the space occupation can not be too large, in order to facilitate the utilization of Cache. So I thought of indexes, which are similar to MMU page tables. Inevitably, I encountered the problem of space complexity again.

Convert interval / rule to bitmap

If the interval can be indexed directly, then the interval can be represented by an array, and the rules covered on the interval can be a bitmap. For 16bit fields, direct indexing is only 2 ^ 16 index items, and each index entry points to an index, that is, the subscript of the interval array. The entire structure is shown in the following figure:

This is almost the internal implementation of the Dimension Tree parallel pattern, and is particularly suitable for hardware implementation, which is regular and simple enough.

It is so intuitive that there is no need to explain anything! But how is this structure constructed? The construction of bitmap is very simple, needless to say, the key is the construction of index tables, and it is not difficult to fill 65535 table items one by one according to interval segmentation, just like building page catalogs and page tables. However, it is worth explaining that there is only 16bit for each matching domain here, and if there is more, the memory footprint will soar! For example, how to match the IP address of 32bit! This is indeed a problem.

Matching of 32-bit IP addresses

This is a question that I have been thinking about, and recently, I have found a solution! This is due to the fact that I found the index / bitmap matching structure above.

Although this structure can only match the domain of 16bit larger than 16bit will result in a huge memory footprint.), but it contains a lot of ideas. The most important of these is how to compress the data through the third table, that is, to achieve data sharing, which seems to be the category of the database, but the idea is universal. If I solve this problem, I can almost design a new structure of the IPv4 routing lookup table. I really designed it, but this is the content of the next article.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.