CN100440859C - A Recursive Flow Classification Method and System Based on Bitmap Aggregation - Google Patents

Abstract

The invention discloses a recursive stream classification method and system for bitmap aggregation. Firstly, a value is taken out from a value range of a rule field, and a set of rules is traversed to obtain a bitmap BM; the aggregate bit part and details are obtained by aggregating it. The bitmap CBM of the aggregated form of the bit part; if the CBM does not exist in the bitmap set to which the corresponding index block belongs, generate a new EqID and add it to the bitmap set, otherwise use the same EqID; create the EqID of the CBM in the index block The mapping relationship with the value of the rule field; in the same way, construct the index block of each value within the value range of each rule field, and obtain the 0th level index table; according to the recursive structure, recursively recursively follow the upper level index block , to get the next level of index block until recursively becoming an index block; after the classification system receives the data packet, it matches it to the rule with the highest priority according to the index table. The invention can reduce storage space overhead and accelerate bitmap generation and search speed.

Description

A Recursive Flow Classification Method and System Based on Bitmap Aggregation

technical field

The present invention relates to a bitmap-based recursive flow classification method and system, in particular to a method and system for distinguishing a specific data packet conforming to predetermined rules from other data packets according to multiple fields on the data packet in the field of data communication system.

Background technique

IP network has entered the development stage of "IP telecommunication network", which also brings many new technical challenges, many new services, such as: packet filtering, QoS, policy routing, NAT, flow accounting, etc., traditional based The data packet forwarding process of destination address routing matching no longer meets the requirements of network operation and management. The IP packet (flow) classification and forwarding technology based on the entire IP header and even the transport layer header has become one of the core technologies of these new services. The fast flow classification system is the basis and key of classification and forwarding technology.

The fast flow classification system is a part of the data packet processing flow of the data communication equipment. The fast flow classification system has a configurable rule set, that is, a collection of several rules with priority. Each rule describes several characteristics of a cluster of data packet headers. condition, the fast flow classification system is to find out the rule with the highest priority from several rules that the data packet meets its requirements when the data packet arrives.

The packet classification problem can be formally defined as: a classifier {Rk} with N rules, where k=1, 2, ..., N; Rk includes 2 entities:

1. A d-element range [l1k, r1k], [l2k, r2k], ... [ldk, rdk].

2. A number Pri(Rk) specifying the priority in the classifier;

For a data packet P that arrives at the classifier and is assigned a corresponding domain by a d-tuple (P1, P2, ..., Pd), the problem of a d-dimensional classifier is to find a specific value k, called k ^* , that satisfies:

For any k≠k ^* , pri(Rk ^* )＞Pri(Rk); and for any i: 1≤i≤d, lik≤Pi≤rik flow classifier cannot wait until the data packets arrive and then match them one by one , to find the highest priority rule. The fast flow classifier is usually divided into two parts, one part is the preprocessing module that constructs the classification index table according to the classification rule set at the control plane; the other part is the index module that matches the actual data packets to the highest priority rule through the classification index table at the data plane , can refer to Figure 1.

From 1999 to 2000, there was a climax of research on flow classification technology, and some achievements were made. A flow classification system based on Trie algorithm, a recursive flow classification (RFC, Recursive Flow Classification) system, and a hierarchical space segmentation (Hi-Cuts) system emerged. ) algorithm-based flow classification system, bit-vector (BV) algorithm-based flow classification system and other fast flow classification systems, these systems have their own advantages and disadvantages, and the classification speed of some classification systems increases with the increase of the number of rules in the classification rule set. Decrease; some systems need to configure a large amount of memory, and the system cost is high; some classification systems have a long response time for rule changes. These algorithms can only meet the application requirements of hundreds of classification rules. Among them, the recursive traffic classification system is the most widely used traffic classification system because of its fast classification speed and independent of the number of classification rules.

The recursive flow classification system is a multi-field packet classification system proposed by Pankaj Gupta and Nick McKeown in 1999. The core of this system includes: 1) a structure of an index table; 2) a structure constructed by a rule set A preprocessing algorithm unit of the index table; 3) an index algorithm unit. The recursive flow classification system does not have an incremental update algorithm. Once the rule set changes, the preprocessing algorithm unit needs to be re-executed.

Among them, the structure of the index table is shown in Figure 2. The index table is divided into several stages (phases), and each stage has several index blocks (Chunks). The hierarchical structure is the recursive structure adopted, and each stage of the index table contains Two fields, that is, the index value and the corresponding eqID. The index value of the first level is the field value of the data packet, and the index value of each subsequent level is the index result of the first two or several tables in the recursive structure (ie eqID weighted sum). In the Phase 0 index table, each field of the rule corresponds to an index block; while each Chunk in the Phase J (J>0) index table is obtained by merging several Chunks in the upper-level index table. The index result of each index block is called the equivalence class identification (eqId, equal-class identification). The so-called equivalence class is the subset that matches the same rule in the m-element subspace (m≤d) (regardless of priority ). The bitmap is used to indicate the matching between the equivalence class and the rules in the rule set. The bitmap is an N-bit data, where N is the number of rules in the rule set. If the equivalence class matches the i-th rule, the bitmap’s The i bit is "1", otherwise it is "0". In this way, the equivalence class index value can be mapped to a bitmap through the corresponding equivalence class identifier in the index block.

The index algorithm unit receives a data packet, searches a phase0 index table for each field corresponding to the position of the data packet (packet), and indexes the lower-level table by the calculated values (eg, weighted sum) of several upper-level index results , until the result of the last level index is obtained, the result is the identity (eqId) of the equivalence class of the packet in the d-element space, and a bitmap is matched. This bitmap indicates which rules the equivalence class matches. From this you can find the rule with the highest priority. It is worth noting that since the bitmap corresponding to each eqId is determined in the preprocessing stage, and the corresponding rule with the highest priority is also determined, most classification systems combine the eqId and the corresponding highest priority rule in the preprocessing stage The rules are associated, so as to directly obtain the highest priority rule that the data packet conforms to, and the index algorithm unit does not need to actually process the bitmap.

In recent years, the number of classification rules has exploded. The recursive flow classification system has exposed inherent weaknesses like other flow classification systems. For a recursive flow classification system with the structure shown in Figure 2, when the number of rules in the rule set reaches 2000 extended access list rules, the equivalence class rules match The bitmap (CBM, Equal Class Bitmap) table requires more than 26M of memory, and in a system using a Pentium1.6GHz CPU, it takes 2000 seconds for the equivalence class rule to match the bitmap response rule change. Tens of megabytes of memory overhead and hundreds of seconds of rule change response time are the key factors that prevent the rapid flow classification technology with more than 2,000 rules from being practical.

Contents of the invention

The technical problem to be solved by the present invention is to propose a recursive stream classification method for bitmap aggregation, which can reduce the storage space overhead of the equivalence class rule matching bitmap and accelerate the operation speed of generating and searching the equivalence class rule matching bitmap. The present invention also provides a system capable of realizing the above method.

In order to solve the above-mentioned technical problems, the present invention provides a recursive flow classification method of bitmap aggregation, which is applied to a recursive flow classification system, comprising the following steps:

(a) First construct an initial bitmap, so that each bit corresponds to a rule of the rule set, then take a value from the value range of a rule field, traverse the rule set, and if the value satisfies the current rule, the bitmap The bit corresponding to the rule in is set to 1, otherwise it is set to 0, and a bitmap BM is obtained;

(b) Aggregate the bitmap BM with the degree of aggregation q, and obtain the aggregated form bitmap CBM including the fixed-length aggregate bit part and the variable-length detail bit part, and the i-th bit of the aggregate bit part corresponds to the bitmap BM The i-th q-tuple of , when the q-tuple is all 0, this bit is set to 0, otherwise the bit is set to 1, and its detail bit part is formed by removing the q-tuple that is all 0 from the bitmap BM;

(c) Compare the aggregated form bitmap CBM with the aggregated form bitmap in the bitmap set to which the rule field corresponds to the index block, check whether the same bitmap exists, if not, generate a new equivalence class for the bitmap CBM Identify and add it to the bitmap collection, otherwise the bitmap CBM uses the equivalence class identification corresponding to the same bitmap; then, establish the equivalence class identification of the bitmap CBM and the current rule field value in the index block Mapping relations;

(d) After each value within the value range of the rule field is processed according to steps (a) to (c), the index block corresponding to the rule field is constructed, and then each rule is constructed in the same way The index block corresponding to the field forms a complete level 0 index table;

(e) According to the set recursive structure, recurse the index block of the upper level to obtain the index block of the lower level. During the recursion, the two bitmaps are compared according to their aggregation forms. The "AND" operation is completed by the "AND" operation method of the aggregated bitmap, and it is repeated step by step until all index blocks are finally recursively become an index block;

(f) After the recursive flow classification system receives a data packet, it looks up an index table at level 0 according to each field related to the flow classification of the data packet, and calculates the index value obtained by calculating the index results of several upper levels. Index the lower-level table until the last-level index result is obtained, and then match the packet to the rule with the highest priority that satisfies the requirements.

Further, the above method can also have the following characteristics: the step (b) is further divided into the following steps:

(b1) Divide the N-bit bitmap BM into N/q q-bit groups according to the set aggregation degree q, and the i-th q-bit group corresponds to the q*i～q*i+q-1 in the bitmap Bit, i=0, 1,..., N/q-1, its corresponding aggregation form bitmap CBM includes an aggregation bit part of N/q bits and a variable-length detail bit part;

(b2) judge the i-th q-bit group of the bitmap BM one by one, i=0, 1, ..., N/q-1, for each q-bit group, judge whether each bit is all 0 , if yes, set the i-th bit of the aggregation bit part of the aggregation form bitmap to 0, otherwise set the i-th bit of the aggregation bit part to 1, and set the corresponding bit of the q bit group in the bitmap BM Append and copy to the detail bit part of the aggregate form bitmap CBM;

(b3) After the processing of all q-byte groups of the bitmap BM is completed, the construction of the corresponding aggregation form bitmap CBM is completed.

Furthermore, the above-mentioned method may also have the following characteristics: the aggregation bit part of the aggregation form bitmap adopts q-bit boundary alignment, and 0 is filled in the insufficient part.

Further, the above-mentioned method can also have the following characteristics: after the step (b3), it also includes the step of writing the variable length of the detailed bit part of the aggregated form bitmap to the front of the aggregated bit part as the The variable length portion of the aggregated form bitmap.

Further, the above method may also have the following feature: the variable length of the detail bit part is represented by the number of q-byte groups contained in the detail bit part.

Further, the above method can also have the following characteristics: the comparison algorithm of the aggregated form bitmap is: sequentially compare the variable length part, the aggregated bit part and the detail bit part of the aggregated form bitmap CBM1 and CBM2, as long as one part is different , directly return the result that the two bitmaps are different, and end; if the three parts are the same, return the result that the two bitmaps are the same.

Further, the above method can also have the following characteristics: the method of performing an AND operation on two aggregated form bitmaps CBM1 and CBM2 to obtain the aggregated form result bitmap CBM is:

Each identical bit of the aggregated bit portion of CBM1 and CBM2 is compared in turn, each time:

If at least one of the two bits involved in the comparison is 0, set the same bit of the CBM aggregation bit part to 0;

If the two bits involved in the comparison are both 1, perform a bitwise "AND" operation on the q-bit group corresponding to the two bits in the detail bit part of the respective bitmap to obtain the q-bit group Q. If Q is all 0, the The same bit of the CBM aggregation bit part is set to 0, otherwise the same bit of the CBM aggregation bit part is set to 1, and the q bit group corresponding to the bit of the CBM detail bit part and its aggregation bit part is assigned as Q.

Further, the above-mentioned method can also have the following characteristics: in the step (b3), the variable length of the detail bit part of the aggregated form bitmap is also written in front of the aggregated bit part, as the aggregated form bitmap variable length part; and when carrying out the "AND" operation of bitmaps CBM1 and CBM2, after all the bits of the aggregated bit part of the two have been compared and processed, the variable length of the CBM detail bit part obtained will also be written into The variable length part is obtained to obtain the result bitmap CBM comprising three parts.

Further, the above method can also have the following characteristics: when the step (e) recursively obtains the next-level index block Chunk 3 from the two upper-level index blocks Chunk 1 and Chunk 2, the pair belongs to two index blocks The two equivalence classes of Chunk 1 and Chunk 2 identify EqID1 and EqID2, perform the following steps:

(e1) performing an "AND" operation on the aggregation form bitmaps corresponding to EqID1 and EqID2 to generate an aggregation form bitmap CBM3 belonging to the next-level index block Chunk 3;

(e2) Check whether the aggregation form bitmap CBM3 exists in the bitmap set to which Chunk 3 belongs, if not, generate a new equivalence class identifier for it, and add it to the bitmap set to which Chunk 3 belongs; if it exists , the bitmap CBM3 uses the equivalence class identifier of the same bitmap;

(e3) Calculate EqID1×(number of equivalence classes of Chunk 2)+EqID2 as the index value corresponding to bitmap CBM3 in Chunk 3, and then fill in the equivalence class identifier of bitmap CBM3 into the corresponding index value in Chunk3 to form a mapping relationship from the field value to the equivalence class identifier;

For any two equivalence class identifiers in Chunk 1 and Chunk 2, after processing according to the above method, the final recursive result Chunk 3 is obtained.

Further, the above method may also have the following characteristics: the degree of polymerization q is 8, 16, 32, 64 or 128.

The recursive flow classification system for bitmap aggregation provided by the present invention includes a preprocessing module for constructing a classification index table according to a classification rule set and an index module for matching actual data packets to the rule with the highest priority through the classification index table. The processing module includes a preprocessing master control unit, a zero-level index table construction unit, and a J-level index table construction unit. The index module includes an index table, a bitmap storage unit, and an index algorithm unit. Its characteristics are:

The 0-level index table construction unit includes an aggregation operation subunit and a bitmap comparison subunit. When constructing the index block corresponding to each rule field, the aggregation operation subunit is used to aggregate the unaggregated bitmap BM Aggregation with a degree of q to obtain an aggregate bitmap CBM including a fixed-length aggregation bit part and a variable-length detail bit part, the i-th bit of the aggregation bit part corresponds to the i-th q-tuple of the bitmap BM, the When the q tuple is all 0, this bit is set to 0, otherwise this bit is set to 1, and its detail bit part is formed after removing the q tuple that is all 0 from the bitmap BM; and the bitmap comparison subunit is divided into two The aggregation form of the bitmap completes the comparison of the two bitmaps;

The J-level index table construction unit includes a bitmap comparison subunit and an "AND" operation subunit. When recursing the upper-level index block to obtain the next-level index block according to the set recursive structure, the bitmap The graph is expressed in an aggregated form, the bitmap comparison subunit completes the comparison of the two bitmaps in the aggregated form of the two bitmaps, and the "AND" operation subunit performs the "AND" operation on the aggregated bitmaps method to complete the "AND" operation of two bitmaps;

The index table storage unit is used to store the constructed index tables of all levels.

Further, the above-mentioned system may also have the following characteristics: the aggregation operation subunit completes the aggregation operation on the bitmap in the following manner:

(1) Divide the N-bit bitmap BM into N/q q-bit groups according to the set aggregation degree q, and the i-th q-bit group corresponds to the q*i～q*i+q-1 in the bitmap Bit, i=0, 1,..., N/q-1, its corresponding aggregation form bitmap CBM includes an aggregation bit part of N/q bits and a variable-length detail bit part;

(II) judge the i-th q-bit group of the bitmap BM one by one, i=0, 1, ..., N/q-1, for each q-bit group, judge whether its each bit is all 0 , if yes, set the i-th bit of the aggregation bit part of the aggregation form bitmap to 0, otherwise set the i-th bit of the aggregation bit part to 1, and set the corresponding bit of the q bit group in the bitmap BM Append and copy to the detail bit part of the aggregate form bitmap CBM;

(III) After the processing of all q-byte groups of the bitmap BM is completed, the construction of the corresponding aggregation form bitmap CBM is completed.

Further, the above-mentioned system can also have the following characteristics: when the aggregation operation subunit performs the aggregation operation of the bitmap, in the step (III), it also changes the detail bit part of the aggregation form bitmap CBM The long length is written in front of its aggregated bit portion as the variable length portion of the aggregated form bitmap CBM.

Further, the above-mentioned system may also have the following characteristics: when the bitmap comparing subunit compares two bitmaps in aggregate form, it sequentially compares the variable length part, the aggregate bit part and the detail bit part of the two bitmaps , as long as one part is different, it will directly return the result that the two bitmaps are different, and end; if all three parts are the same, return the result that the two bitmaps are the same.

Further, the above-mentioned system may also have the following characteristics: the method for the "AND" operation subunit to perform "AND" operation on two aggregated bitmaps CBM1 and CBM2 to obtain the aggregated result bitmap CBM is:

Each identical bit of the aggregated bit portion of CBM1 and CBM2 is compared in turn, each time:

If at least one of the two bits involved in the comparison is 0, set the same bit of the CBM aggregation bit part to 0;

If the two bits involved in the comparison are both 1, perform a bitwise "AND" operation on the q-bit group corresponding to the two bits in the detail bit part of the respective bitmap to obtain the q-bit group Q. If Q is all 0, the The same bit of the CBM aggregation bit part is set to 0, otherwise the same bit of the CBM aggregation bit part is set to 1, and the q bit group corresponding to the bit of the CBM detail bit part and its aggregation bit part is assigned as Q.

Further, the above-mentioned system can also have the following characteristics: when the bitmap comparison subunit compares the bitmaps represented in the aggregated form, in step (III), it will also change the detail bit part of the aggregated form bitmap CBM The long length is written in front of its aggregation bit part as its variable length part; correspondingly, when the "AND" operation subunit performs the "AND" operation of the bitmap in the aggregated form, when the bitmaps CBM1 and CBM2 are aggregated After all the bits in the bit part are compared and processed, the variable length of the detail bit part of the aggregated form bitmap CBM is written into the variable length part of the CBM.

As can be seen from the above, the present invention reduces the storage space overhead of the equivalence rule matching bitmap in the recursive flow classification system at the stage of rule set preprocessing to generate an index table by aggregating the equivalence class rule matching bitmap in the recursive flow classification algorithm , and also reduces the CPU time overhead of equivalence class rule matching bitmap generation operation (bitwise AND operation) and equivalence class rule matching bitmap search, thereby shortening preprocessing time and speeding up the response speed of rule changes.

Description of drawings

Fig. 1 is the structural block diagram of the recursive flow classification system of the bitmap aggregation of the embodiment of the present invention;

Fig. 2 is a recursive structural diagram of a typical recursive IP flow classification system;

Fig. 3 is a schematic diagram of bitmap aggregation according to an embodiment of the present invention;

Fig. 4 is the construction flowchart of the recursive flow classification system Phase 0 index table of the embodiment of the present invention bitmap aggregation;

Fig. 5 is the flow chart of the bitmap "AND" operation of the aggregation form of the embodiment of the present invention;

Fig. 6 is a flow chart of the bitmap comparison operation in the form of aggregation according to an embodiment of the present invention;

Fig. 7 is a flow chart of construction of a phase J (J>0) index table of the recursive stream classification system for bitmap aggregation according to an embodiment of the present invention.

Detailed ways

The bitmap is N-bit data, and a large number of bitmaps are stored in the preprocessing module, and the "AND" and "comparison" operations of the bitmaps are performed most of the time. Through a lot of research and analysis, the inventors found that, in fact, there are very few "1" bits in the bitmap, and an equivalence class often only matches very few rules. That is to say, the bitmap is sparse. Therefore, the present invention uses shorter data to express the information carried by the bitmap by aggregating the sparse bitmap items, thereby reducing the memory occupied by the storage of the bitmap information. Space, and reduce the time it takes for bitmap "AND" and "Compare" operations, that is, response time.

As shown in Figure 1, the recursive flow classification system for bitmap aggregation described in this embodiment is mainly composed of the following two parts: the control plane and the data plane:

The control plane is a preprocessing module for constructing a classification index table according to the classification rule set, which further includes:

The preprocessing master control unit is used to control the Phase 0 index table construction module to construct each index block (chunk) of Phase 0, and then control the Phase J (J>0) index table construction module to recursively construct PhaseJ (J>0) in turn Each chunk.

Phase 0 index table construction unit, used to construct index blocks corresponding to each rule field. It includes an aggregation operation subunit and a bitmap comparison subunit (each subunit is not shown in the figure), and when constructed, the aggregation operation subunit is used to perform an aggregation degree of q on the unaggregated bitmap BM Aggregate to obtain the aggregated form bitmap CBM including the fixed-length aggregation bit part and the variable-length detail bit part, the i-th bit of the aggregation bit part corresponds to the i-th q-tuple of the bitmap BM, and the q-tuple is all When it is 0, this bit is set to 0, otherwise this bit is set to 1, and its detail bit part is formed after removing the q tuples that are all 0 from the bitmap BM; and the bitmap comparison subunit compares two bitmaps , are compared as aggregates of the two bitmaps.

Phase J (J>0) index table construction unit is used to recursively calculate the upper-level Chunk to obtain the next-level Chunk according to the set recursive structure, and so on until finally a Chunk is obtained. It includes a bitmap comparison subunit and an "AND" operation subunit. During recursion, the bitmap is expressed in an aggregated form, and the bitmap comparison subunit completes the two bitmaps in the form of aggregation of the two bitmaps The "AND" operation sub-unit completes the "AND" operation of two bitmaps by using the "AND" operation method of aggregated bitmaps.

The data plane is an index module that matches the actual data packet to the highest priority rule through the classification index table. This unit includes the index table and bitmap storage unit, and the index algorithm unit, where:

The index table and bitmap storage unit stores the constructed index blocks of various levels, and each index block includes an index table and a corresponding bitmap expressed in an aggregated form. In another embodiment, the aggregated bitmap can be generated only in the index table construction stage, and the aggregated bitmap may not be saved, as long as there is an index table. Of course, it is necessary to directly map the last level of EqID to to the highest priority rule.

After the index algorithm unit receives a data packet, each field of the data packet (packet) is used to search an index table of phase 0, and according to the same recursive structure, the weighted sum of the upper-level index results (ie EqID) Use the index value to index the next-level table until the result of the last-level index is obtained, which is the identifier (eqId) of the equivalence class of the packet in the d-element space, and finally find the rule with the highest priority corresponding to the identifier, which can be found in The preprocessing phase directly associates the eqId with the corresponding highest priority rule.

The bitmap aggregation of the present invention does not change the form of the index block of the recursive classification system, so the index module of the present invention is the same as the traditional recursive classification system, except that the bitmap is expressed in an aggregated form. However, due to the aggregation of bitmaps, the construction process of Phase 0 index table construction unit and Phase J (J>0) index table construction unit needs to be improved accordingly.

The method for the Phase 0 index table construction module to construct a Chunk corresponding to a rule field (generally 8-16 bits) is shown in Figure 4, including the following steps:

Step 110, constructing an initial bitmap whose length is equal to the number of rules in the rule set, and each bit in the bitmap is set to 0, corresponding to a rule;

Step 120, take out a value sequentially from the value range (1, 2B-1) of the rule field, where B is the width of a certain field in the rule;

Step 130, traversing the rule set in sequence, if the value satisfies the current rule, then set the bit corresponding to the rule in the bitmap to 1, otherwise set it to 0, and obtain the current bitmap BM;

Step 140, aggregate the bitmap BM with an aggregation degree of q, and obtain the aggregated form of the bitmap to represent CBM, which is also referred to as the aggregated form bitmap CBM hereinafter, and the i-th bit of the aggregated bit part corresponds to the bitmap BM's i q-tuples, when the q-tuples are all 0, the bit is set to 0, otherwise the bit is set to 1, and the detail bits are formed by removing the q-tuples that are all 0 from the bitmap BM;

Step 150, compare the aggregated form bitmap CBM with the bitmap (also in aggregated form) in the bitmap set to which the index block corresponding to the rule field belongs, check whether there is the same bitmap, if not, generate the bitmap CBM New EqID (equivalence class identifier) and add it to the bitmap collection, otherwise, the bitmap CBM uses the EqID corresponding to the same bitmap;

Step 160, fill in the EqID of the bitmap CBM into the corresponding position of the current rule field value in the Chunk, forming a mapping relationship from the field value to the EqID;

Step 170, judge whether all the values within the value range of the rule field have been processed, if not, return to step 120, if the processing is completed, the Chunk corresponding to the rule field is constructed.

By constructing the Chunk corresponding to each rule field in the same way, the Phase 0 index table construction module finally constructs a complete Phase 0 index table.

The bitmap aggregation operation method will be discussed in detail below with an example.

We aggregate and compress q Bits of sparse bitmaps of N Bits. q is called the degree of aggregation, and can take values such as 8, 16, 32, 64, and 128 to facilitate CPU processing. Figure 3 is an example of bitmap aggregation with an aggregation degree of 8.

The aggregated bitmap is composed of three parts: the first part is the variable length part, which is used to indicate the variable length of the detail part of the aggregated bitmap, that is, the number of q-tuples it contains. The variable length part is redundant information, but this field contains rich bitmap information, which is the overall feature of the information, which helps to speed up the comparison and further improve system performance; the second part is the aggregation of N/q bits The bit part (q bit boundary is aligned, and the insufficient part is filled with 0). The i-th bit of the aggregated bit part is the result of the "or" operation of the i*q~i*q+1 bits in the unaggregated bitmap. This bit is 0 means that its corresponding q-bit group is all 0, and this bit is 1 means that its corresponding q-bit group has at least one "1" bit; the third part is the variable-length detail bit part, which is equal to 0 after being removed from the unaggregated bitmap The k-th q-bit group (k*q～k*q+q-1 bit) of the detail bit part corresponds to the k-th "1" bit of the aggregation bit part, if the aggregation bit part The k-th "1" bit of the k-th "1" appears on the i-bit, then the k-th q-bit group of the detail bit part and the i-th q-bit group of the unaggregated bitmap (i*q～i*q+q -1 bit) are equal.

The aggregation method is as follows: sequentially process the i-th q-bit group of the unaggregated bitmap (that is, the q*i～q*i+q-1 bits, i=0, 1, ...), if The q bit group is not all 0, then the i-th bit of the second part of the aggregated bitmap is set to 1, and the non-zero part of the unaggregated bitmap (q*i～q*i+q -1 bit) append copied to the third part (detail part) of the aggregated bitmap. Otherwise, the i-th bit of the second part of the aggregated form bitmap (the aggregated bits part) is set to zero. The third part is equivalent to the form after the unaggregated bitmap ignores the q bits of all 0s. After the processing of all q-bytes of the unaggregated bitmap is completed, the first part (variable length part) of the aggregated bitmap is adjusted to the number of q-bytes written in the third part (detail part).

FIG. 3 is a schematic diagram of aggregation of bitmaps corresponding to an equivalence class in a 30-rule classifier. The equivalence class matches the rules {0, 1, 2, 20}, and the aggregation degree q=8. Because there are "1" bits in bits 0-8 and bits 16-23 of the unaggregated bitmap, the first and third bits of the aggregate bit part of the aggregated bitmap are "1", and the other bits are "0". , the detail bit part includes non-all 0 q-bit groups in the unaggregated bitmap, that is, bits 0-8 and bits 16-23.

In the recursive flow classification system of bitmap aggregation, two operations need to be performed on the aggregated bitmap. The first one is the "AND" operation of two aggregated bitmaps to obtain the intersection of two equivalence classes (new etc. valence class) bitmap (aggregation form), its process is shown in Figure 5. The second is a comparison operation of two aggregated bitmaps, which is used to judge whether two equivalence classes can be merged. The process is shown in FIG. 6 .

The process in Figure 5 is used to perform an AND operation on two aggregated bitmaps CBM1 and CBM2 to obtain an aggregated result bitmap CBM, including the following steps:

Step 210, sequentially read an identical bit (usually starting from the 0th bit) of the "aggregation bit part" of CBM1 and CBM2;

Step 220, judging whether at least one of the two bit positions participating in the comparison is 0, if yes, perform the next step, otherwise, perform step 240;

Step 230, the corresponding bit of the aggregation bit part of the result CBM is set to 0, and step 270 is performed;

Step 240, performing a bitwise "AND" operation on the two q-bit groups corresponding to the respective bits in the "detail bit part" of CBM1 and CBM2 to obtain the q-bit group Q;

Step 250, judge whether the q bit group Q is all 0, if yes, execute step 230, otherwise, execute the next step;

Step 260, the corresponding bit of the aggregation bit part of the result bitmap CBM is set to 1, and the q bit group corresponding to the bit in the detail bit part of the result bitmap CBM (as the bit is the kth bit of the aggregation bit part) "1" bits, then the q bit group is the kth q bit group of the detail bit part) is assigned Q;

Step 270, judging whether all bits of the "aggregation bit part" of CBM1 and CBM2 have been processed, if yes, perform the next step, otherwise, return to step 210;

Step 280, adjusting the variable length part of the CBM to the number of q-bytes in the detail bit part to obtain the final result bitmap CBM.

Fig. 6 shows the process of comparing two aggregated form bitmaps CBM1 and CBM2, including the following steps:

Step 310, comparing whether the variable length parts of the aggregated form bitmaps CBM1 and CBM2 are the same, if not, execute step 350, otherwise continue to the next step;

Step 320, compare whether the aggregation bit parts of the aggregation form bitmap CBM1 and CBM2 are the same, if not, execute step 350, otherwise continue to the next step;

Step 330, compare whether the detail bits of the aggregated form bitmaps CBM1 and CBM2 are the same, if not, execute step 350, otherwise continue to the next step;

Step 340, return the same result of both, end;

Step 350, return different results, and end.

It can be seen that compared with the bitmap "AND" and "comparison" operations in the traditional recursive stream classification system, the length of the aggregated bitmap data is shorter, and the "AND" and "comparison" operations take less time, so the bitmap The preprocessing module of the recursive stream classification system for graph aggregation has short processing time and reduced response time.

The Phase J (J>0) index table construction module obtains the next-level index table by recursively calculating the Chunk generated by the previous level. This process continues (J keeps increasing) until all the Chunks are finally handed over Push becomes a Chunk.

The method of recursing two Chunk 1 and Chunk 2 to obtain the recursive result Chunk 3 is shown in Figure 7, including the following steps:

Step 410, take out the two equivalence class identifiers EqID1 and EqID2 belonging to Chunk 1 and Chunk 2, and perform "AND" operation on their corresponding aggregation form bitmaps CBM1 and CBM2 to generate an aggregation form result bit belonging to Chunk 3 Figure CBM3;

Step 420, check whether the aggregated form bitmap CBM3 exists in the bitmap set to which Chunk 3 belongs, if not, execute the next step, and if exist, execute step 440;

Step 430, generate a new EqID for the bitmap CBM3, and add it to the bitmap collection to which Chunk 3 belongs, and execute step 450;

Step 440, the bitmap CBM3 uses the EqID corresponding to the same bitmap;

Step 450, calculate the number of equivalence classes + EqID2 of EqID1 × Chunk 2, and use the result as the index value corresponding to bitmap CBM3 in Chunk3;

Step 460, fill the EqID of the bitmap CBM3 into the position corresponding to the index value in Chunk 3, forming a mapping relationship from the field value to the EqID;

Step 470, judge whether the combination of any two equivalence class identifiers in Chunk 1 and Chunk 2 has been processed, if not, return to step 410, if the processing is completed, the recursive result Chunk 3 is obtained, and end.

For the classification system with Fig. 2 recursive structure, traditional recursive classification system and the recursive classification system that adopts bitmap aggregation of the present invention compare as follows on Pentium M1.6GHz computer emulation:

1. The classifier of 1000 standard ACL classification rules, the traditional recursive classifier algorithm and the recursive classifier of bitmap aggregation (aggregation degree 32) are compared in Table 1.

Table 1: Comparison of classifiers for 1000 standard ACL rules

memory usage Response time traditional recursive classification system 13,173,102 <1s A Recursive Classification System for Bitmap Aggregations 1,654,800 <1s

Second, the classifier with 1000 extended ACL classification rules, the comparison between the traditional recursive classifier algorithm and the recursive classifier (aggregation degree 32) of bitmap aggregation is shown in Table 2.

Table 2: Comparison of classifiers for 1000 extended ACL rules

memory usage Response time traditional recursive classification system 13,173,102 157s A Recursive Classification System for Bitmap Aggregations 7,526,704 <1s

Three, the classifier with 2000 extended ACL classification rules, the comparison of traditional recursive classifier algorithm and bitmap aggregation recursive classifier (aggregation degree 32) is shown in Table 3.

Table 3: Comparison of classifiers for 2000 extended ACL rules

memory usage Response time traditional recursive classification system 26,728,467 2,052s A Recursive Classification System for Bitmap Aggregations 18,032,924 4s

Practice has proved that the improved rule change response time is optimized by 10 to 100 times, and the space overhead is optimized by 2 to 10 times. It can be seen that the improvement has achieved quite good results, and its memory and response time overhead can fully meet the requirements of a classifier with more than 2000 extended ACL rules.

Claims (15)

1, a kind of bit-map aggregated recursive stream sorting method is applied to the recursive stream sorting system, may further comprise the steps:

(a) at first construct an initial bitmap, make its each rule corresponding to regular collection, in a rule field span, take out a value then, the traversal rule set, if this value satisfies current rule, position that should the rule correspondence in the bitmap is set to 1, otherwise puts 0, obtains a bitmap BM;

(b) bitmap BM is carried out the polymerization that the degree of polymerization is q, obtain comprising the polymerization bit position of fixed length and the polymerized form bitmap CBM of elongated details bit position, the i position of its polymerization bit position is corresponding to i the q tuple of bitmap BM, this q tuple is that 0 o'clock this position is set to 0 entirely, otherwise this position is set to 1, and it is to constitute after 0 the q tuple entirely that its details bit position is removed by bitmap BM;

(c) the polymerized form bitmap during relatively the affiliated bitmap of polymerized form bitmap CBM and this rule field manipulative indexing piece is gathered, check and whether have identical bitmap, if do not have, for bitmap CBM generates new equivalence class sign and it is joined this bitmap set, otherwise bitmap CBM uses the equivalence class sign of its identical bitmap correspondence; Then, in described index block, set up the equivalence class sign of bitmap CBM and the mapping relations of current rule field value;

(d) to each value in this rule field span, after (a) finishes dealing with to the method for (c) set by step, the index block structure of this rule field correspondence is finished, and goes out the index block of each rule field correspondence again by same method construct, forms the 0th grade of complete concordance list;

(e) according to the recursion structure of setting, index block to upper level carries out recursion, obtain the index block of its next stage, two bitmaps compare by its polymerized form during recursion, the AND operation of two bitmaps is finished with the AND operation method of polymerized form bitmap, so increase by degrees, become an index block until the last recursion of all index blocks;

(f) after a packet is received by the recursive stream sorting system, search a concordance list of the 0th grade according to this packet each field relevant with traffic classification, the index value that is obtained by the indexed results computing of some upper levels comes index next stage table, up to obtaining the afterbody indexed results, then will this data packet matched the highest rule of priority that meets the demands to it.

2, the method for claim 1 is characterized in that, described step (b) is further divided into following steps:

(b1) by the degree of polymerization q that sets the bitmap BM of N position is divided into N/q q hyte, i q hyte is corresponding to the q*i in the bitmap～q*i+q-1 position, i=0,1, ..., N/q-1, its corresponding polymerized form bitmap CBM comprises the polymerization bit position of N/q position and elongated details bit position;

(b2) judge i the q hyte of bitmap BM one by one, i=0,1 ..., N/q-1, to each q hyte, judge whether its each position is 0 entirely, if the polymerization bit position i position of described polymerized form bitmap is set to 0, otherwise the i position of this polymerization bit position is set to 1, and the details bit position that copies polymerized form bitmap CBM to is appended in the corresponding position of this q hyte in bitmap BM;

(b3) all q hytes of bitmap BM are finished dealing with after, its corresponding polymerized form bitmap CBM structure is finished.

3, method as claimed in claim 2 is characterized in that, the polymerization bit position of described polymerized form bitmap adopts the alignment of q bit boundary, and insufficient section mends 0.

4, method as claimed in claim 2, it is characterized in that, also comprise step after the described step (b3): again the q hyte number of described polymerized form bitmap details bit position is written to the front of its polymerization bit position, as the elongated length part of described polymerized form bitmap.

5, method as claimed in claim 4, it is characterized in that, the comparison algorithm of described polymerized form bitmap is: the elongated length part, polymerization bit position and the details bit position that compare polymerized form bitmap CBM1 and CBM2 successively, as long as there is a part different, directly return two results that bitmap is different, finish; If three parts are all identical, then return two results that bitmap is identical.

6, method as claimed in claim 2 is characterized in that, the method for two polymerized form bitmap CBM1 and CBM2 being carried out obtaining with computing the CBM of bitmap as a result of polymerized form is:

Each identical bits that compares the polymerization bit position of CBM1 and CBM2 successively, when comparing at every turn:

Have at least one to be 0 if participate in two positions relatively, then the identical bits of CBM polymerization bit position is set to 0;

Be 1 if participate in two positions relatively, the step-by-step AND-operation is carried out in the q hyte of the details bit position correspondence of bitmap separately in these two positions, obtain q hyte Q, if Q is 0 entirely, the identical bits of CBM polymerization bit position is set to 0, otherwise the identical bits of CBM polymerization bit position is set to 1, and is Q with this corresponding q hyte assignment of CBM details bit position and its polymerization bit position.

7, method as claimed in claim 6 is characterized in that, in the described step (b3), also the q hyte number of described polymerized form bitmap details bit position is write the front of its polymerization bit position, as the elongated length part of this polymerized form bitmap; And when carrying out the AND operation of bitmap CBM1 and CBM2, after all bit comparisons of both polymerization bit positions and handling, also the elongated length with the CBM details bit position that obtains is written to its elongated length part, obtains comprising the CBM of bitmap as a result of three parts.

8, as the described method of arbitrary claim in the claim 1 to 7, it is characterized in that, when described step (e) obtains next stage index block Chunk3 to two index block Chunk1 of upper level and Chunk2 recursion, two equivalence classes that adhere to two index block Chunk1 and Chunk2 separately are identified EqID1 and EqID2, carry out following steps:

(e1) the polymerized form bitmap with EqID1 and EqID2 correspondence carries out AND-operation, generates the bitmap CBM3 of a polymerized form that belongs to next stage index block Chunk3;

(e2) checking in the bitmap set of polymerized form bitmap CBM3 under Chunk3 whether exist, if do not exist, is that it generates new equivalence class sign, and it is joined under the Chunk3 in the bitmap set; If exist, then bitmap CBM3 uses the equivalence class sign of the bitmap identical with it;

(e3) calculate EqID1 * (the equivalence class number of Chunk2)+EqID2, as among the Chunk3 corresponding to the index value of bitmap CBM3, then the equivalence class sign of bitmap CBM3 is inserted the position of this index value correspondence among the Chunk3, formed the mapping relations of field value to this equivalence class sign;

Any two equivalence classes sign among Chunk1 and the Chunk2 after finishing dealing with as stated above, obtains final recursion Chunk3 as a result.

9, the method for claim 1 is characterized in that, described degree of polymerization q is 8,16,32,64 or 128.

10, a kind of bit-map aggregated recursive stream sorting system, comprise and be used for matching the priority index module of high rule by the classified index table according to the pretreatment module of classifying rules collection structural classification concordance list with actual data packet, described pretreatment module comprises preliminary treatment Master Control Unit, the 0th grade of concordance list structural unit and J level concordance list structural unit, described index module comprises concordance list and bitmap memory cell, Index Algorithm unit, it is characterized in that:

Described preliminary treatment Master Control Unit is used to control each index block that the 0th grade of concordance list structural unit constructed the 0th grade, control then J level concordance list structural unit successively recursion construct each index block of J level;

Described the 0th grade of concordance list structural unit comprises polymerization operator unit and bitmap compares subelement, when the index block of each rule field correspondence of structure, described polymerization operator unit is used for the bitmap BM without polymerization is carried out the polymerization that the degree of polymerization is q, obtain comprising the polymerization bit position of fixed length and the polymerized form bitmap CBM of elongated details bit position, the i position of its polymerization bit position is corresponding to i the q tuple of bitmap BM, this q tuple is that 0 o'clock this position is set to 0 entirely, otherwise this position is set to 1, and it is to constitute after 0 the q tuple entirely that its details bit position is removed by bitmap BM; And described bitmap comparison subelement is finished the comparison of these two bitmaps by the polymerized form of two bitmaps;

Described J level concordance list structural unit comprises bitmap relatively subelement and AND operation subelement, in recursion structure according to setting, the upper level index block is carried out recursion when obtaining the next stage index block, the form of bitmap after with polymerization represented, described bitmap comparison subelement is finished the comparison of these two bitmaps by the polymerized form of two bitmaps, and described AND operation subelement is finished the AND operation of two bitmaps with the AND operation method of polymerized form bitmap;

Described concordance list and bitmap memory cell are used to preserve the concordance lists at different levels that structure obtains;

After described Index Algorithm unit is used to receive a packet, each field by packet, search a concordance list of the 0th grade, according to identical recursion structure, weighted sum by the indexed results of upper level is come index next stage table as index value, up to the result who obtains the afterbody index, find the corresponding the highest rule of priority of this sign at last, at pretreatment stage this sign and the corresponding the highest regular direct correlation of priority are got up.

11, system as claimed in claim 10 is characterized in that, described polymerization operator unit is done in such a manner the polymerization computing to bitmap:

(I) by the degree of polymerization q that sets the bitmap BM of N position is divided into N/q q hyte, i q hyte is corresponding to the q*i in the bitmap～q*i+q-1 position, i=0,1, ..., N/q-1, its corresponding polymerized form bitmap CBM comprises the polymerization bit position of N/q position and elongated details bit position;

(II) judge i the q hyte of bitmap BM one by one, i=0,1 ..., N/q-1, to each q hyte, judge whether its each position is 0 entirely, if the polymerization bit position i position of described polymerized form bitmap is set to 0, otherwise the i position of this polymerization bit position is set to 1, and the details bit position that copies polymerized form bitmap CBM to is appended in the corresponding position of this q hyte in bitmap BM;

(III) all q hytes of bitmap BM are finished dealing with after, its corresponding polymerized form bitmap CBM structure is finished.

12, system as claimed in claim 11, it is characterized in that, described polymerization operator unit is when the polymerization computing of carrying out bitmap, in described step (III), also the q hyte number of the details bit position of described polymerized form bitmap CBM is written to the front of its polymerization bit position, as the elongated length part of described polymerized form bitmap CBM.

13, system as claimed in claim 12, it is characterized in that, when described bitmap comparison subelement compares the bitmap of two polymerized forms, the elongated length part, polymerization bit position and the details bit position that compare these two bitmaps successively, as long as there is a part different, just directly return two results that bitmap is different, finish; If three parts are all identical, then return two results that bitmap is identical.

14, system as claimed in claim 10 is characterized in that, described AND operation subelement carries out the method that AND operation obtains the CBM of bitmap as a result of polymerized form to two polymerized form bitmap CBM1 and CBM2 and is:

Each identical bits that compares the polymerization bit position of CBM1 and CBM2 successively, when comparing at every turn:

Have at least one to be 0 if participate in two positions relatively, then the identical bits of CBM polymerization bit position is set to 0;

Be 1 if participate in two positions relatively, the step-by-step AND-operation is carried out in the q hyte of the details bit position correspondence of bitmap separately in these two positions, obtain q hyte Q, if Q is 0 entirely, the identical bits of CBM polymerization bit position is set to 0, otherwise the identical bits of CBM polymerization bit position is set to 1, and is Q with this corresponding q hyte assignment of CBM details bit position and its polymerization bit position.

15, system as claimed in claim 14, it is characterized in that, when described bitmap comparison subelement carries out the comparison of the bitmap represented with polymerized form, in step (III), also the elongated length of the details bit position of polymerized form bitmap CBM is write the front of its polymerization bit position, as its elongated length part; Correspondingly, when described AND operation subelement carries out with the AND operation of polymerized form bitmap, with after all bit comparisons of bitmap CBM1 and CBM2 polymerization bit position and handling, also the elongated length of the details bit position of polymerized form bitmap CBM is written to the elongated length part of this CBM.

Images