[go: up one dir, main page]

WO2015043254A1 - 一种包分类规则的查找方法及装置 - Google Patents

一种包分类规则的查找方法及装置 Download PDF

Info

Publication number
WO2015043254A1
WO2015043254A1 PCT/CN2014/080445 CN2014080445W WO2015043254A1 WO 2015043254 A1 WO2015043254 A1 WO 2015043254A1 CN 2014080445 W CN2014080445 W CN 2014080445W WO 2015043254 A1 WO2015043254 A1 WO 2015043254A1
Authority
WO
WIPO (PCT)
Prior art keywords
rule
sub
equivalence
domain
equivalent
Prior art date
Application number
PCT/CN2014/080445
Other languages
English (en)
French (fr)
Inventor
李彧
程晨
张炜
刘衡祁
王晓明
陈伟
Original Assignee
中兴通讯股份有限公司
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 中兴通讯股份有限公司 filed Critical 中兴通讯股份有限公司
Publication of WO2015043254A1 publication Critical patent/WO2015043254A1/zh

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/903—Querying
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/901—Indexing; Data structures therefor; Storage structures
    • G06F16/9014—Indexing; Data structures therefor; Storage structures hash tables
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/903—Querying
    • G06F16/90335—Query processing
    • G06F16/90348—Query processing by searching ordered data, e.g. alpha-numerically ordered data

Definitions

  • the present invention relates to the field of network communications, and in particular, to a method and an apparatus for searching for packet classification rules.
  • BACKGROUND Core routers typically use packet classification to control traffic and improve network performance.
  • the network packet classification rule can be composed of: source IP protocol (IP, Internet Protocol) address, destination IP address, source media access control (MAC, Media Access Control) address, destination MAC address, and transmission control protocol (TCP) , Transmission Control Protocol) Synchronization marks, etc., can also be set for each range.
  • IP Internet Protocol
  • MAC media access control
  • TCP transmission control protocol
  • Each signature can be called a domain of packet classification rules.
  • the fields of each domain are generally prefix types (for non-prefix type fields as well Can be expanded into a prefix type by an algorithm).
  • the traditional core router implements packet classification and discovery through software. With the rapid development of the network, higher requirements are placed on network traffic and network performance in the backbone network.
  • the most popular solution at present is to use a Ternary Content Addressable Memory (TCAM) for hardware access control list (ACL) lookup.
  • TCAM Ternary Content Addressable Memory
  • ACL hardware access control list
  • the cost of TCAM itself is high, and the high power consumption of TCAM is also an urgent problem to be solved.
  • the recursive flow classification (RFC) algorithm has the fastest searching speed and is suitable for hardware implementation. In the case of parallel processing, only a few hardware clock cycles are required to complete a packet classification lookup.
  • the shortcomings of this algorithm are only applicable to scenarios with a small rule set size.
  • the technical problem to be solved by embodiments of the present invention is to provide a method and device for searching for a packet classification rule, which is suitable for hardware implementation, and can quickly find a large-scale rule set to occupy a core when occupying less memory resources. High-speed lookup requirements for routers.
  • an embodiment of the present invention provides a method for searching for a packet classification rule, which includes the following steps: dividing a packet classification rule in a rule set into a minimum range according to a domain to obtain a plurality of minimum ranges; Each of the minimum ranges is respectively assigned an equivalent ID number to obtain an equivalence rule summary table formed by the equivalence ID number; the domain is divided to obtain a plurality of sub-domains; and each sub-domain is assigned an equivalence sub-domain An ID number, obtaining an equivalence rule sub-table formed by the equivalence sub-ID number; obtaining an equivalence map according to the equivalence rule summary table and the equivalence rule sub-table; according to the equivalence map , the equivalence rule subtable and the equivalence rule summary table, find the data packet.
  • the step of dividing the data packet classification rule in the rule set into the minimum range according to the domain, and obtaining the plurality of minimum ranges includes: dividing the data packet classification rule in the rule set, and dividing the domain according to the feature value to obtain multiple domains;
  • the packet classification rule in the rule set performs a minimum range division according to each domain to obtain a plurality of minimum ranges.
  • the step of dividing the data packet classification rule in the rule set by the eigenvalue into the domain includes: obtaining the feature tag category of the packet classification rule; and dividing the packet classification rule of the same category feature tag into one domain .
  • the step of dividing the data packet classification rule in the rule set according to the minimum range of each domain to obtain multiple minimum ranges includes: The fields of each packet classification rule in each domain are prefixed; the fields indicated by the prefix classification rules of each domain are inserted into a line segment tree, and the leaf nodes of the line segment tree are passed. The minimum extent of this field divided by the line segment tree.
  • each of the minimum ranges is respectively assigned an equivalent ID number
  • the step of obtaining an equivalence rule summary table formed by the equivalence ID number includes: assigning an equivalence ID number to each minimum range; traversing the rule set Each packet classification rule obtains an ID number of a field in each domain of each packet classification rule, and an ID number of the field is obtained by an equivalent ID number of all leaf nodes corresponding to the field; The ID numbers are cross-combined to obtain a plurality of combined items; the combined items are added as hash values of the hash table to the hash table, and the rule results corresponding to each combined item are used as the result of the hash table, constitute, etc. A list of price rules.
  • the step of dividing the domain to obtain multiple sub-domains includes: dividing the domain into multiple sub-domains according to a prefix bit width when a field in each domain is represented by a prefix.
  • the step of assigning an equivalence sub-ID number to each sub-domain separately, and obtaining the equivalence rule sub-table formed by the equi-sub-ID ID number includes: inserting a field represented by a prefix of each sub-domain into a line segment tree
  • the leaf node of the line segment tree is the minimum range of the subfield divided by the line segment tree; the equivalence sub ID number is assigned to each minimum range; the field represented by the prefix of each subfield is used as the key value, and the The equivalent sub-ID number corresponding to the field is used as a search result to form an equivalence rule sub-table.
  • the step of obtaining an equivalence mapping table according to the equivalence rule summary table and the equivalence rule sub-table includes: cross-multiplying an equivalence sub-ID number corresponding to a minimum range of each sub-domain to generate a hash key Value; The equivalent ID number corresponding to each hash key value is used as a search result to form an equivalence map.
  • the step of searching for the data packet includes: dividing the search key value according to the bit width of each sub-domain to obtain each sub-domain Key value; according to the key value of each sub-domain, look up in the equivalence rule sub-table to obtain the equivalent sub-ID number; merge the obtained equivalent sub-ID numbers into the hash key value of the equivalent mapping table; The hash key value of the equivalent mapping table is searched in the equivalence mapping table to obtain an equivalent ID number; the obtained equivalent ID numbers are combined to form a hash key value of the equivalence rule summary table; The hash key value of the rule summary table is searched in the equivalence rule summary table to obtain the final search result.
  • another embodiment of the present invention further provides a device for searching for a packet classification rule, including: a first dividing module, configured to classify a data packet in a rule set, The domain performs the minimum range division to obtain a plurality of minimum ranges; the equivalence rule summary table construction module is configured to allocate an equivalent ID number for each minimum range to obtain an equivalence rule formed by the equivalent ID number.
  • a molecular domain module configured to divide the domain to obtain a plurality of sub-domains
  • an equivalence rule sub-table construction module configured to assign an equivalence sub-ID number to each sub-domain, respectively, to obtain the equivalence sub- An equivalence rule sub-form formed by the ID number
  • an equivalence map construction module configured to obtain an equivalence map according to the equivalence rule summary table and the equivalence rule sub-table
  • the packet lookup module is set to be based on The equivalence map, the equivalence rule sub-table, and the equivalence rule summary table are used to find a data packet.
  • the first dividing module includes: a domain dividing module, configured to classify data packet classification rules in the rule set, and perform domain division according to the feature value to obtain multiple domains;
  • the sub-module is configured to set a packet classification rule in the rule set, and perform a minimum range division according to each domain to obtain a plurality of minimum ranges.
  • the domain module includes: a detection module, configured to acquire a feature tag category of the packet classification rule; and a domain module configured to divide the packet classification rule of the same category feature tag into one domain.
  • the dividing submodule includes: a first field module, configured to prefix a field of each data packet rule in each domain with a prefix; a first range dividing module, configured to set each rule in each domain The corresponding field is inserted into a line segment tree, and the leaf node of the line segment tree is the minimum range of this field divided by the line segment tree.
  • the equivalence rule summary table construction module includes: an equivalence ID number allocation module, configured to allocate an equivalence ID number for each minimum range; an equivalence ID number acquisition module, configured to traverse each data in the rule set a packet classification rule obtains an ID number of a field in each domain of each packet classification rule, and an ID number of the field is obtained by an equivalent ID number of all leaf nodes corresponding to the field; an equivalent ID number combination module , set to cross-combine the obtained equivalent ID numbers of the respective domains to obtain a plurality of combined items; the first building block is set to add the hash key value of the hash table as a hash table to the hash table, and The result of the rule corresponding to each combination item is the result of the hash table, and constitutes a summary table of equivalent rules.
  • the molecular domain module includes: a bit width division module, configured to divide the domain into a plurality of sub-domains according to a prefix bit width when a field in each domain is represented by a prefix.
  • the equivalence rule sub-table construction module includes: a second range division module, configured to insert a field represented by a prefix of each sub-domain into a line segment tree, where the leaf nodes of the line segment tree are divided by a line segment tree The minimum range of this subdomain; the equivalence sub ID number assignment module, configured to assign an equivalent sub ID number to each minimum range;
  • the second building block is configured to use a field represented by a prefix of each sub-domain as a key value, and an equivalent sub-ID number corresponding to the field as a search result, and constitute an equivalence rule sub-table.
  • the equivalence mapping table construction module includes: an equivalence sub ID number combination module, configured to cross-multiply an equivalent sub-ID number corresponding to a minimum range of each sub-domain to generate a hash key value; And set the equivalent ID number corresponding to each hash key value as the search result to form an equivalence map.
  • the data packet search module includes: a first key value processing module, configured to divide the search key value according to the bit width of each sub-domain to obtain a key value of each sub-domain; an equivalence rule sub-table search module, Set to search for the equivalence rule sub-table according to the key value of each sub-domain to obtain an equivalent sub-ID number; the second key-value processing module is configured to merge the obtained equivalent sub-ID numbers into an equivalence mapping table.
  • an equivalence map lookup module configured to perform a lookup in the equivalence map according to the hash key value of the equivalence map, to obtain an equivalent ID number
  • a third key value processing module Set to combine the obtained equivalent ID numbers into a hash key value of the equivalence rule summary table
  • the equivalence rule summary table lookup module is set to a hash key value according to the equivalence rule summary table, in the equivalence rule The total table is searched to get the final search result.
  • 1 is a schematic diagram of a packet classification rule of a two-dimensional data packet
  • FIG. 2 is a table diagram showing the classification rule of the two-dimensional data packet shown in FIG. 1;
  • FIG. 3 is a schematic overall flow chart of a method for searching for a packet classification rule according to the present invention.
  • FIG. 4 A schematic diagram of a rule set table of the data classification rule shown in FIG. 4;
  • FIG. 5 is a schematic diagram showing an example of dividing a rule set shown in FIG. 4 by a line segment tree;
  • FIG. 6 is a domain A field table of the rule set in FIG. 5;
  • FIG. 8 is a rule table composed of equivalent ID numbers, and a table formed by cross-combining;
  • FIG. 9 is a schematic diagram of a summary table of equivalent rules;
  • Figure 10 is a sub-domain table of domain A
  • Figure 11 is a line segment tree corresponding to the sub-domain A_l;
  • Figure 12 is a line segment tree corresponding to the subfield A_2;
  • Figure 13 is an equivalent rule sub-table of the sub-domain A_l
  • Figure 14 is an equivalent rule sub-table of sub-domain A_2;
  • Figure 15 is a sub-domain table of domain B
  • Figure 16 is a line segment tree corresponding to the sub-domain B_l;
  • Figure 17 is a line segment tree corresponding to the subfield B_2;
  • Figure 18 is an equivalent rule sub-table of the sub-domain B_l
  • Figure 19 is an equivalent rule sub-table of sub-domain B_2;
  • Figure 20 is an equivalent mapping table of domain A
  • FIG. 21 is an equivalent mapping table of domain B;
  • Figure 22 is a block diagram showing the structure of the packet classification rule;
  • Figure 23 is a schematic diagram of a direct table;
  • Figure 24 is a schematic diagram of a parallel hash table;
  • Figure 25 is a block diagram of the packet classification rule of the present invention, the composition of each table Process schematic.
  • the RFC algorithm is only applicable to a scenario with a small rule set size in the packet classification search algorithm disclosed in the prior art, and a large-scale application scenario in which the rule set entries exceed 10000 entries.
  • the preprocessing speed is slow and the memory demand is too large, and a packet classification rule capable of quickly searching for a large-scale rule set and satisfying the high-speed search requirement of the core router while occupying less memory resources is provided.
  • the method for searching includes the following steps: Step 11, the packet classification rule in the rule set is divided into a minimum range according to the domain to obtain a plurality of minimum ranges; Step 12, each of the minimum ranges is respectively assigned an equivalent identifier (ID) , an identity number, to obtain a summary table of equivalent rules formed by the equivalent ID number; Step 13, dividing the domain to obtain a plurality of sub-domains; Step 14, assigning an equivalence sub-ID to each sub-domain Number, obtaining an equivalence rule sub-form formed by the equivalence sub-ID number; step 15, according to the equivalence rule summary table and the equivalent The sub-table, the mapping table to obtain the equivalent; step 16, the mapping table based on the equivalent, and a sub-list equivalence rules equivalence rules summary table, find the packet.
  • ID equivalent identifier
  • step 11 includes: In step 111, the packet classification rule in the rule set is divided into domains according to the feature value to obtain multiple domains. Step 112: The packet classification rule in the rule set is divided into minimum ranges according to each domain, and more The smallest range.
  • Step 111 specifically includes: Step 1111: Obtain a feature tag category of the packet classification rule.
  • Step 1112 Divide a packet classification rule of the same category feature tag into a domain.
  • the data packet usually includes: a source IP address of the data packet, a destination IP address, a source media access control (MAC, Media Access Control) address, a destination MAC address, and a TCP synchronization tag, and a packet classification rule. It may be a rule for classifying according to each feature tag of the above-mentioned data packet or any combination of each feature tag. .
  • the feature tag of the packet classification that is usually used in the core router (such as the source IP address, destination IP address, source media access control (MAC, Media Access Control) address, destination MAC address, and TCP synchronization tag, etc.) is 5 ⁇ 7 kinds, some scenes can be expanded to more than a dozen or more, each combination of feature markers or similar feature markers can be called a domain of packet classification rules.
  • a simple two-dimensional packet classification problem shown in Figure 1 as an example.
  • the processing of the packet classification problem is solved by the domain division.
  • the two rules are divided into an A domain and a B domain.
  • A2 Is a subrange of AO
  • B2 is a subrange of B0. Because of the existence of A2 and B2, the AO and B0 ranges are actually divided into three segments (Al, A2 and A3), (Bl, B2 and B3).
  • the foregoing step 112 may specifically include: Step 1121, the field of each packet classification rule in each domain is represented by a prefix; Step 1122, inserting, in each field, a field represented by a prefix of each packet in the prefix of each domain into a field In a line segment tree, the leaf node of the line segment tree is the smallest range of this field divided by the line segment tree.
  • the general domain field type is prefix type, and the domain of non-prefix type can also be expanded into prefix type processing.
  • the rule set table 401 of the data classification rule shown in FIG. 4 has three rules that can be divided into an A domain and a B domain: R1, R2, and R3 data packets, each of which can be divided into two A and B rules. Domain, represented in each domain.
  • the field of R1 in domain A is represented by a prefix of 1000, and the field in domain B is represented by a prefix of 01**; similarly, The field of R2 in domain A is prefixed with 1***, the field in domain B is prefixed with 010*; the field of R3 in domain A is prefixed with 0***, in domain B. Fields are prefixed with 00**. Then, as shown in FIG. 5, for the domain A, the domain A field of R1, R2, and R3 is inserted into a line segment tree, and the result indicated by the field A in the figure can be obtained.
  • 501 505 is the leaf node of the line segment tree, that is, the shortest line segment divided by the line segment tree.
  • the rule corresponding to each node is defined by the longest prefix match.
  • node 502 corresponds to R1 and R2 at the same time, but because the prefix field of R1 is 1000, the field prefix length of prefix field 1*** of R2 is longer, so the node 502 corresponds to rule R1, which is assigned to its equivalent ID number A1; the range of node 501 corresponds to rule R3, which is assigned to its equivalent ID number A3; node 503 505 is three short ranges, but because it corresponds to R2 The range is therefore assigned to them with the same equivalent ID number A2.
  • domain B it can be decomposed into 3 line segments, node 506 corresponds to R3, and equivalent ID number B1 is assigned; node 507 corresponds to R2, and equivalent ID number B2 is assigned; node 508 corresponds to R1, and equivalent ID number B3 is assigned.
  • the minimum range there are many ways to divide the minimum range.
  • the line segment tree as shown in FIG. 5, it can also be implemented by using a path compression Trie algorithm. In the embodiments of the present invention, the line segment tree is used to implement the minimum range division.
  • the foregoing step 12 includes: Step 121: assign an equal ID number to each minimum range; Step 122, traverse each packet classification rule in the rule set to obtain each packet classification The ID number of the field in each domain of the rule, and the ID number of the field is obtained by the equivalent ID number of all the leaf nodes corresponding to the field; Step 123, cross-combining the ID numbers of the respective domains to obtain multiple Combination item; Step 124: Add the combined item as a hash key of the hash table into the hash table, and use the rule result corresponding to each combination item as the result of the hash table to form a summary table of the equivalence rules.
  • Step 121 assign an equal ID number to each minimum range
  • Step 122 traverse each packet classification rule in the rule set to obtain each packet classification The ID number of the field in each domain of the rule, and the ID number of the field is obtained by the equivalent ID number of all the leaf nodes corresponding to the field
  • Step 123 cross-combining the ID numbers of the respective domains to obtain multiple Combination
  • table 601 gives a domain A field table of the rule set, and field A of rule R1 corresponds to node 602, which only contains the equivalent ID number A1; rule R2
  • the domain A corresponds to the node 603, which includes the equivalent ID numbers A1 and A2;
  • the domain A of the rule R3 corresponds to the node 604, and includes the equivalent ID number A3. Therefore, the ID number of the field A field of the rule R1 is (A1); the ID number of the field A field of the rule R2 is (Al, A2); the ID number of the field A field of the rule R3 is (A3).
  • 701 gives a domain B field table of the rule set, and domain B of rule R1 corresponds to node 703, which includes equivalent ID numbers B2 and B3; domain B of rule R2 corresponds to node 704. , the equivalent ID number B2 is included; the field B of the rule R3 corresponds to the node 702 containing the equivalent ID number B1.
  • the ID number of the field B field of the rule R1 is (B2, B3); the ID number of the field B field of the rule R2 is (B2); the ID number of the field B field of the rule R3 is (B1).
  • the equivalent ID numbers obtained in the above steps are formed into the rule table 801, and the equivalent ID numbers obtained in the respective fields are cross-combined to obtain a plurality of combination items.
  • the cross-combined rule table is as shown in 802.
  • the R1 rule corresponds to two combination items A1B2 and A1B3;
  • R2 corresponds to two combination items A1B2 and A2B2;
  • R3 corresponds to A3B1-one combination item. Since the key lengths of all combinations of equivalent ID numbers are the same and belong to an exact match, the equivalent ID number can be used as the key value of the Hash Algorithm, and the rule result corresponding to each equivalent ID combination Or the rule number is used as the result of the hash table, and the hash algorithm is used for storage and searching.
  • each combination item of each rule is added to the hash table as a key value of the hash table according to the table 802, and constitutes an equivalence rule summary table 901 as shown in FIG. It can be filled in the order of the combination of rule sets.
  • the equivalent ID combination items corresponding to the R1, R2, and R3 rules are sequentially filled in. The first is to add the key value A1B2, corresponding to the result R1 (or the search result of R1); then add the key value A1B3, corresponding to the result Rl.
  • the hash algorithm is a mature fast indexing algorithm suitable for hardware implementation. For example, a parallel hash algorithm can be used to implement a memory access search for the parity rule summary table.
  • the processing of the fork multiplier by the above method can only fill in the meaningful key value into the summary rule table, and does not process the redundant information involved in other cross-multiplication methods, thereby saving the update.
  • Operating time and storage space Since the entry key length of the packet classification rule is generally long, and the bit width of each domain is 16 32 bit, it is necessary to find the longest prefix matching result in each domain in the search.
  • the traditional solution is to use the search tree structure to search. For example, the Trie tree algorithm or the binary tree algorithm can be used, but the tree structure search requires multiple memory accesses, and the hardware implementation has a large search delay.
  • the method adopted by the present invention is: constructing an equivalence rule sub-table and an equivalence mapping table to perform fast indexing.
  • the constructing the equivalence rule sub-table, first performing step 13, specifically includes: Step 131, dividing the domain according to a prefix bit width when the field in each domain is represented by a prefix. Get multiple subdomains.
  • each field field is 4 bits wide and is divided into two 2-bit sub-domains.
  • 1001 is a sub-domain table generated according to each leaf node (501 505) of the domain A in FIG. 5, and is divided into sub-domain_1 and sub-domain. A_2.
  • the prefix width is represented by a prefix in each field, and the bit width can also be divided into a 1-bit, a 3-bit sub-domain equalization method, of course, for convenience and simplicity.
  • the bit width of 4 bits is preferably divided into two sub-domains of 2 bits.
  • the foregoing step 14 includes: Step 141: Insert a field represented by a prefix of each subfield into a line segment tree, where the leaf node of the line segment tree is divided by the line segment tree.
  • Step 142 assigning an equivalence sub ID number to each of the minimum ranges; Step 143, using a field represented by a prefix of each subfield as a key value, and using an equivalent sub ID number corresponding to the field as Find the result and form a sub-table of equivalence rules.
  • the entry of the subfield A_l is inserted into the line segment tree 1101 of the line segment tree generation subfield A_1, as shown in FIG.
  • the entry of the subfield A_2 is inserted into the line segment tree to generate the line segment tree 1201 of the subfield A_2; then the equivalent sub ID number is assigned to each of the minimum ranges. Finally, each sub-domain is fully expanded.
  • the 2-bit key value has four values of 00, 01, 10, and 11. Each key value is filled according to the equivalent sub-ID number corresponding to the smallest range, and the figure is as shown in the figure.
  • the equivalence rule sub-table A_l (1301) shown in Fig. 13 and the equivalence rule sub-table A_2 (1401) shown in Fig. 14.
  • the value 00 of the sub-domain A_l belongs to the minimum range 0*, corresponding to the equivalent sub-ID number al3; 01 belongs to the minimum range 0*, corresponding to al3; 10 belongs to the minimum range 10, corresponding to al l; 11 belongs to the minimum range 11, corresponding to al2 .
  • the above operation is performed on the domain B, as shown in FIG. 15, FIG. 16, and FIG. 17, and finally, the equivalence rule sub-table B_l (1801) shown in FIG. 18 and the equivalence rule shown in FIG. 19 are obtained. Table B_2 (1901).
  • the foregoing step 15 specifically includes: Step 151: Cross-multiply the equivalent sub-ID number corresponding to the minimum range of each sub-domain to generate a hash key value; Step 152, each hash key The equivalent ID number corresponding to the value, as a result of the search, constitutes an equivalence map.
  • the above example is used, as shown in FIG.
  • the equivalent ID number A1 corresponds to 10 of the sub-domain A_l and 00 of the sub-domain A_2, and the equivalent sub-ID number corresponding to the sub-domain A1 is al l , and the equivalent sub-ID number corresponding to 00 is a21 Therefore, the first entry of the equivalence map is alla21, and the corresponding result is Al.
  • the equivalent ID number A2 corresponds to the 11 of the sub-domain A_l and the ** of the sub-domain A_2, the equivalent sub-ID number corresponding to 11 is al2, and the equivalent sub-ID number corresponding to ** has a21, a22, a23, so
  • the three entries added to the equivalence map are al2a21, al2a22, and al2a23, and their corresponding results are all A2.
  • the equivalent mapping table 2001 of the domain A is completely generated.
  • the equivalent mapping table 2101 of the domain B is completely generated.
  • each equivalence rule sub-table is: each equivalence rule sub-table, each equivalence mapping table, and an equivalence rule summary table.
  • a process instance diagram is generated for the equivalence rule sub-table, the equivalence map, and the equivalence rule summary table.
  • the step 16 includes: Step 161: divide the search key value according to the bit width of each sub-domain to obtain a key value of each sub-domain; Step 162, according to each sub- The key value of the domain is searched in the equivalence rule sub-table to obtain an equivalent sub-ID number; Step 163, the obtained equivalent sub-ID numbers are merged to form a hash key value of the equivalence mapping table; Step 164, according to the The hash key value of the equivalence mapping table is searched in the equivalence mapping table to obtain an equivalent ID number; Step 165, the obtained equivalent ID numbers are combined to form a hash key value of the equivalence rule summary table; 166.
  • the foregoing embodiment of the present invention only needs to perform a lookup table for each of the equivalence sub-tables, the respective equivalence mapping tables, and the equivalence rule summary table according to the search key value, thereby obtaining the search result.
  • the invention can quickly find a large-scale rule set while occupying less memory resources, and meet the high-speed search requirement of the core router.
  • the embodiment of the present invention further provides a device for searching for a packet classification rule, including: a first dividing module, configured to divide a data packet classification rule in a rule set, and perform a minimum range division according to a domain to obtain a plurality of minimum ranges; a rule summary table construction module, configured to allocate an equivalent ID number for each minimum range to obtain an equivalence rule summary table formed by the equivalent ID number; a molecular domain module, configured to divide the domain, Get multiple subdomains; An equivalence rule sub-table construction module is configured to allocate an equivalence sub-ID number for each sub-domain to obtain an equivalence rule sub-table formed by the equivalence sub-ID number; an equivalence mapping table construction module, configured to The equivalence rule summary table and the equivalence rule sub-table obtain an equivalence map; the packet lookup module is configured to search according to the equivalence map, the equivalence rule sub-table, and the
  • the first dividing module includes: a domain dividing module, configured to classify a data packet classification rule in the rule set, and perform domain partitioning according to the feature value to obtain multiple domains; and divide the submodule, and set the data in the rule set
  • the packet classification rule divides the minimum range according to each domain to obtain multiple minimum ranges.
  • the domain module includes: a detection module, configured to acquire a feature tag category of the packet classification rule; and a domain module configured to divide the packet classification rule of the same category feature tag into one domain.
  • the dividing submodule includes: a first field module, configured to prefix a field of each data packet rule in each domain with a prefix; a first range dividing module, configured to set each rule in each domain The corresponding field is inserted into a line segment tree, and the leaf node of the line segment tree is the minimum range of this field divided by the line segment tree.
  • the equivalence rule summary table construction module includes: an equivalence ID number allocation module, configured to allocate an equivalence ID number for each minimum range; an equivalence ID number acquisition module, configured to traverse each data in the rule set a packet classification rule obtains an ID number of a field in each domain of each packet classification rule, and an ID number of the field is obtained by an equivalent ID number of all leaf nodes corresponding to the field; an equivalent ID number combination module , set to cross-combine the equivalent ID numbers of the acquired domains to obtain multiple combined items;
  • the first building block is configured to add the hash key value of the hash table as a hash table to the hash table, and the rule result corresponding to each combination item is used as a result of the hash table to form a summary table of the equivalence rules.
  • the molecular domain module includes: a bit width division module, configured to divide the domain into a plurality of sub-domains according to a prefix bit width when a field in each domain is represented by a prefix.
  • the equivalence rule sub-table construction module includes: a second range division module, configured to insert a field represented by a prefix of each sub-domain into a line segment tree, where the leaf nodes of the line segment tree are divided by a line segment tree The minimum range of the subdomain; the equivalence sub ID number assignment module is set to assign an equivalence sub ID number to each of the minimum ranges; the second building block is set to use the field represented by the prefix of each subdomain as the key value, and The equivalent sub-ID number corresponding to the field is used as a search result to form an equivalence rule sub-table.
  • the equivalence mapping table construction module includes: an equivalence sub ID number combination module, configured to cross-multiply an equivalent sub-ID number corresponding to a minimum range of each sub-domain to generate a hash key value; , set to the equivalent ID number corresponding to each hash key value, and as a result of the search, constitute an equivalence map.
  • the data packet search module includes: a first key value processing module, configured to divide the search key value according to the bit width of each sub-domain to obtain a key value of each sub-domain; an equivalence rule sub-table search module, Set to search for the equivalence rule sub-table according to the key value of each sub-domain to obtain an equivalent sub-ID number; the second key-value processing module is configured to merge the obtained equivalent sub-ID numbers into an equivalence mapping table.
  • an equivalent mapping table search module configured to perform a lookup in the equivalence mapping table according to the hash key value of the equivalence mapping table to obtain an equivalent ID number
  • the third key value processing module is configured to combine the obtained equivalent ID numbers into a hash key value of the equivalence rule summary table
  • the equivalence rule summary table search module is set to a hash key value according to the equivalence rule summary table Finding in the summary table of the equivalence rules to obtain the final search result.
  • a hardware implementation lookup module flow diagram is shown.
  • the search key value 2201 is divided into the first key value processing module 2202 according to the bit width of each sub-domain to obtain the key value 2203 of each sub-domain; then, in the equivalence rule sub-table search module, the key value of each sub-domain is 2203 input equivalence rule sub-table 2204 performs a search to obtain an equivalence sub-ID number; the second key value processing module combines each related equivalence sub-ID number to form an equivalent mapping table hash key value 2205; an equivalence map
  • the table lookup module performs a hash search by inputting the equivalent map hash key value 2205 into the equivalence map 2206 to obtain an equivalence ID number of the search result; and merging the obtained equivalent ID numbers in the third key value processing module,
  • the equivalence rule summary table hash key value 2207 is formed; the equivalence rule summary table lookup module performs a hash search on the equivalence rule total table hash
  • the equivalence rule sub-table is a direct table, and the key value is used as the direct index of the address to search;
  • the equivalence mapping table and the equivalence rule summary table are hash tables, and the hardware implementation may adopt multiple A hash table implementation manner, the present invention is described in a specific implementation manner by the disclosed parallel hash method. Since the entry of the equivalence rule sub-table has a small bit width and very few entries, although there is redundant space in the equivalence rule sub-table, as shown in the table 1801, the occupation is very limited; the embodiment of the present invention directly The table lookup mode is implemented in consideration of the small search delay and the implementation cost is small.
  • the search implementation of the equivalence rule sub-table is not limited to the direct table mode, and may be implemented by using a hash algorithm or a search tree structure.
  • the implementation of the equivalent rule summary table and the equivalent mapping table is not limited to the hash table implementation manner.
  • the implementation of the parallel hash table in the embodiment of the present invention mainly considers that the hash table has a small search delay; In the case that the search delay is not high, it can be implemented by using a search tree.
  • Figure 23 and Figure 24 show the hardware block diagrams for the two lookup methods. 2301 is a direct table, which is actually a specific piece of hardware memory.
  • the key value of the lookup table is the read request address of the memory, and the output is the storage information of the corresponding address.
  • 2401 is a parallel hash table, which is composed of N hash processing modules in parallel; after the key value is input to the parallel hash table, it is subjected to N parallel hash calculations (2402), and the calculated result is accessing the corresponding storage module. Address; read the storage information of the corresponding address (2403), obtain the search result of each hash table; the result shown in 2404 compares the aggregation module, compares each hash result with the input key value, and selects the matching result output.
  • the apparatus for searching for the packet classification rule is a device to which the search method of the packet classification rule is applied, and the implementation manner of the method for searching for the packet classification rule is also applicable to the implementation of the search device of the packet classification rule.
  • the same technical effect can also be achieved.
  • the method and apparatus for searching for packet classification rules provided by the embodiments of the present invention have the following beneficial effects: Suitable for hardware implementation, capable of performing large-scale rule sets while occupying less memory resources Quickly find, meet the high-speed lookup needs of core routers.

Landscapes

  • Engineering & Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Mining & Analysis (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Computational Linguistics (AREA)
  • Software Systems (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

提供一种包分类规则的査找方法及装置，涉及网络通信领域。方法包括下列步骤：将规则集中的数据包分类规则，按域进行最小范围的划分，得到多个最小范围；为每个最小范围分别分配一等价ID号，得到由所述等价ID号形成的等价规则总表；将所述域进行划分，得到多个子域；为每个子域分别分配一个等价子ID号，得到由所述等价子ID号形成的等价规则子表；根据所述等价规则总表以及所述等价规则子表，得到等价映射表；根据所述等价映射表、等价规则子表以及等价规则总表，査找数据包。解决了传统方法仅适用于规则集规模较小的场景，预处理速度慢、内存需求过大的问题。

Description

一种包分类规则的查找方法及装置 技术领域 本发明涉及网络通信领域， 特别涉及一种包分类规则的查找方法及装置。 背景技术 核心路由器通常使用包分类来控制流量及提高网络性能。 网络数据包分类规则的 组成可以为： 数据包的源互联网协议 （IP， Internet Protocol ) 地址、 目的 IP地址、 源 介质访问控制 （MAC, Media Access Control) 地址、 目的 MAC地址及传输控制协议 (TCP, Transmission Control Protocol) 同步标记等， 也可以为对各项范围的设定。 通 常在核心路由器中使用的包分类的特征标记类别有 5~7种， 每一种特征标记可以称作 包分类规则的一个域， 每个域的字段一般为前缀类型 （对于非前缀类型字段也都可以 通过算法展开成前缀类型）。 传统的核心路由器通过软件实现包分类查找， 随着网络的迅速发展， 对主干网络 中的网络流量及网络性能提出了更高的要求。 目前最流行的解决方法为使用三态内容 寻址存储器 （TCAM， Ternary Content Addressable Memory) 进行硬件访问控制列表 (ACL, Access Control List) 查找。 而 TCAM本身成本较高， 且 TCAM的高功耗也 是一个亟待解决的问题。 除了通过 TCAM实现的硬件包分类查找， 已公开的包分类查找算法中以递归流分 类 （RFC, Recursive Flow Classification) 算法的查找速度最快， 并且适合硬件实现。 在并行处理情况下， 只需要几个硬件时钟周期即可完成一次包分类查找。 但这种算法 的缺点是仅适用于规则集规模较小的场景， 对于规则集条目数超过 10000条目的大规 模应用场景， 存在着预处理速度慢、 内存需求过大的问题。 以图 1的例子， 假设 Al， A2， A3 , A4， Bl， B2， B3 都是最小格点 （可以被一步索引）， 那么需要做的叉乘时 所有这些项的乘积 （如图 1、 图 2所示）， 即 4*3项， 而实际上其中图中白色的 6个区 域是无用的范闱。在 RFC等涉及到叉乘的算法中， 这些类似的无用区域是需要填充到 查找表中的， 这样就造成了内存空间的冗余， 在大规模规则集情形下， 这些冗余信息 占用了大量的存储空间。 发明内容 本发明实施例要解决的技术问题是提供一种包分类规则的查找方法及装置， 适合 硬件实现， 能够在占用较少内存资源的情况下， 对大规模规则集进行快速查找， 满足 核心路由器的高速查找需求。 为解决上述技术问题， 本发明的一个实施例提供一种包分类规则的查找方法， 包 括下列步骤： 将规则集中的数据包分类规则， 按域进行最小范围的划分， 得到多个最小范围； 为每个最小范围分别分配一等价 ID号， 得到由所述等价 ID号形成的等价规则总 表； 将所述域进行划分， 得到多个子域； 为每个子域分别分配一个等价子 ID号， 得到由所述等价子 ID号形成的等价规则 子表； 根据所述等价规则总表以及所述等价规则子表， 得到等价映射表； 根据所述等价映射表、 等价规则子表以及等价规则总表， 查找数据包。 其中， 将规则集中的数据包分类规则， 按域进行最小范围的划分， 得到多个最小 范围的步骤包括： 将规则集中的数据包分类规则， 按特征值进行域划分， 得到多个域； 将所述规则集中的数据包分类规则， 按照每个域进行最小范围的划分， 得到多个 最小范围。 其中， 将规则集中的数据包分类规则， 按特征值进行域划分， 得到多个域的步骤 包括： 获取数据包分类规则的特征标记类别； 将同一类别特征标记的数据包分类规则划分为一个域。 其中， 将所述规则集中的数据包分类规则， 按照每个域进行最小范围的划分， 得 到多个最小范围的步骤包括： 将每条数据包分类规则在每个域中的字段用前缀表示； 将各条数据包分类规则在每个域的前缀表示的字段插入到一棵线段树中， 线段树 的叶节点即是通过线段树划分的此域的最小范围。 其中， 为每个最小范围分别分配一等价 ID号， 得到由所述等价 ID号形成的等价 规则总表的步骤包括： 为每个最小范围分配一等价 ID号； 遍历规则集中的每条数据包分类规则， 获得每条数据包分类规则在每个域中的字 段的 ID号， 所述字段的 ID号由所述字段对应的所有叶子节点的等价 ID号得到； 将各个域的 ID号进行交叉组合， 得到多个组合项； 将组合项作为哈希表的哈希键值添加进哈希表， 并将每个组合项对应的规则结果 作为哈希表的结果， 构成等价规则总表。 其中， 将所述域进行划分， 得到多个子域的步骤包括： 根据每个域中的字段用前缀表示时的前缀位宽， 将所述域划分得到多个子域。 其中， 为每个子域分别分配一个等价子 ID号， 得到由所述等价子 ID号形成的等 价规则子表的步骤包括： 将每个子域的前缀表示的字段插入到一棵线段树中， 线段树的叶节点即是通过线 段树划分的此子域的最小范围； 为每个最小范围分配等价子 ID号； 将每个子域的前缀表示的字段作为键值，以及将所述字段对应的等价子 ID号作为 查找结果， 构成等价规则子表。 其中， 根据所述等价规则总表以及所述等价规则子表， 得到等价映射表的步骤包 括： 将每个子域的最小范围对应的等价子 ID号进行叉乘， 生成哈希键值； 将每个哈希键值对应的等价 ID号， 作为查找结果， 构成等价映射表。 其中， 根据所述等价规则映射表、 等价规则子表以及等价规则总表， 查找数据包 的步骤包括： 将查找键值按照各子域的位宽进行分域， 得到各子域的键值； 将根据各子域的键值， 在等价规则子表进行查找， 得到等价子 ID号； 将获得的等价子 ID号合并组成等价映射表的哈希键值； 根据所述等价映射表的哈希键值， 在所述等价映射表进行查找， 得到等价 ID号； 将获得的等价 ID号合并组成等价规则总表的哈希键值； 根据等价规则总表的哈希键值， 在所述等价规则总表进行查找， 得到最终查找结 果。 同时为了能够满足核心路由器的高速查找需求， 本发明的的另一实施例还提供了 一种包分类规则的查找装置， 包括： 第一划分模块， 设置为将规则集中的数据包分类规则，按域进行最小范围的划分， 得到多个最小范围； 等价规则总表构建模块，设置为为每个最小范围分别分配一等价 ID号，得到由所 述等价 ID号形成的等价规则总表； 分子域模块， 设置为将所述域进行划分， 得到多个子域； 等价规则子表构建模块，设置为为每个子域分别分配一个等价子 ID号，得到由所 述等价子 ID号形成的等价规则子表； 等价映射表构建模块， 设置为根据所述等价规则总表以及所述等价规则子表， 得 到等价映射表； 数据包查找模块， 设置为根据所述等价映射表、等价规则子表以及等价规则总表， 查找数据包。 其中， 所述第一划分模块包括： 分域模块， 设置为将规则集中的数据包分类规则， 按特征值进行域划分， 得到多 个域； 划分子模块， 设置为将所述规则集中的数据包分类规则， 按照每个域进行最小范 围的划分， 得到多个最小范围。 其中， 所述分域模块包括： 检测模块， 设置为获取数据包分类规则的特征标记类别； 划域模块， 设置为将同一类别特征标记的数据包分类规则划分为一个域。 其中， 所述划分子模块包括： 第一字段模块， 设置为将每条数据包规则在每个域中的字段用前缀表示； 第一范围划分模块，设置为将各条规则在每个域的对应字段插入到一棵线段树中， 线段树的叶节点即是通过线段树划分的此域的最小范围。 其中， 所述等价规则总表构建模块包括： 等价 ID号分配模块， 设置为为每个最小范围分配一等价 ID号； 等价 ID号获取模块，设置为遍历规则集中的每条数据包分类规则，获得每条数据 包分类规则在每个域中的字段的 ID号， 所述字段的 ID号由所述字段对应的所有叶子 节点的等价 ID号得到； 等价 ID号组合模块， 设置为将获取的各个域的等价 ID号进行交叉组合， 得到多 个组合项； 第一构建模块， 设置为将组合项作为哈希表的哈希键值添加进哈希表， 并将每个 组合项对应的规则结果作为哈希表的结果， 构成等价规则总表。 其中， 所述分子域模块包括： 位宽划分模块， 设置为根据每个域中的字段用前缀表示时的前缀位宽， 将所述域 划分得到多个子域。 其中， 所述等价规则子表构建模块包括： 第二范围划分模块， 设置为将每个子域的前缀表示的字段插入到一棵线段树中， 线段树的叶节点即是通过线段树划分的此子域的最小范围； 等价子 ID号分配模块， 设置为为每个最小范围分配等价子 ID号； 第二构建模块， 设置为将每个子域的前缀表示的字段作为键值， 以及将所述字段 对应的等价子 ID号作为查找结果， 构成等价规则子表。 其中， 所述等价映射表构建模块包括： 等价子 ID号组合模块， 设置为将每个子域的最小范围对应的等价子 ID号进行叉 乘， 生成哈希键值； 第三构建模块， 设置为将每个哈希键值对应的等价 ID号， 作为查找结果， 构成等 价映射表。 其中， 所述数据包查找模块包括： 第一键值处理模块， 设置为将查找键值按照各子域的位宽进行分域， 得到各子域 的键值； 等价规则子表查找模块， 设置为根据各子域的键值， 在等价规则子表进行查找， 得到等价子 ID号； 第二键值处理模块， 设置为将获得的等价子 ID 号合并组成等价映射表的哈希键 值； 等价映射表查找模块， 设置为根据所述等价映射表的哈希键值， 在所述等价映射 表进行查找， 得到等价 ID号； 第三键值处理模块， 设置为将获得的等价 ID 号合并组成等价规则总表的哈希键 值； 等价规则总表查找模块， 设置为根据等价规则总表的哈希键值， 在所述等价规则 总表进行查找， 得到最终查找结果。 本发明实施例的上述技术方案的有益效果如下： 上述方案中， 通过构建等价规则总表、 构建等价规则子表和构建等价映射表克服 了 RFC 等涉及到叉乘的算法无法在不存储冗余信息的情况下构建完备的查找表的技 术难题， 能够在占用较少内存资源的情况下， 对大规模规则集进行快速查找， 满足核 心路由的高速查找需求。 附图说明
图 1为二维数据包的数据包分类规则示意图；
图 2为图 1所示的二维数据包分类规则的表格示意图；
图 3为本发明的包分类规则的查找方法的整体流程示意图；
图 4所示的数据分类规则的规则集表格示意图；
图 5为将图 4所示的规则集利用线段树进行最小范围划分的举例示意图; 图 6为图 5中的规则集的域 A字段表；
图 7为图 5中的规则集的域 B字段表；
图 8为等价 ID号构成的规则表， 以及进行交叉组合后形成的表格； 图 9为等价规则总表的示意图；
图 10为域 A的子域表；
图 11为子域 A_l对应的线段树；
图 12为子域 A_2对应的线段树；
图 13为子域 A_l的等价规则子表；
图 14为子域 A_2的等价规则子表；
图 15为域 B的子域表；
图 16为子域 B_l对应的线段树；
图 17为子域 B_2对应的线段树；
图 18为子域 B_l的等价规则子表；
图 19为子域 B_2的等价规则子表；
图 20为域 A的等价映射表；
图 21为域 B的等价映射表； 图 22为包分类规则的查找装置的结构框示意图; 图 23为直接表的示意图； 图 24为并行哈希表的示意图； 图 25为本发明的包分类规则的查找方法中， 各个表的构成过程示意图。 具体实施方式 为使本发明要解决的技术问题、 技术方案和优点更加清楚， 下面将结合附图及具 体实施例进行详细描述。 如图 3所示，本发明实施例针对现有技术中已公开的包分类查找算法中以 RFC算 法仅适用于规则集规模较小的场景， 对于规则集条目数超过 10000条目的大规模应用 场景， 存在着预处理速度慢、 内存需求过大的问题， 提供一种能够在占用较少内存资 源的情况下， 对大规模规则集进行快速查找， 能够满足核心路由器的高速查找需求的 包分类规则的查找方法， 包括下列步骤： 步骤 11， 将规则集中的数据包分类规则， 按域进行最小范围的划分， 得到多个最 小范围； 步骤 12， 为每个最小范围分别分配一等价标识（ID， Identity) 号， 得到由所述等 价 ID号形成的等价规则总表； 步骤 13， 将所述域进行划分， 得到多个子域； 步骤 14， 为每个子域分别分配一个等价子 ID号， 得到由所述等价子 ID号形成的 等价规则子表； 步骤 15， 根据所述等价规则总表以及所述等价规则子表， 得到等价映射表； 步骤 16， 根据所述等价映射表、 等价规则子表以及等价规则总表， 查找数据包。 该实施例通过构建等价规则总表、 构建等价规则子表和构建等价映射表克服了 RFC等涉及到叉乘的算法无法在不存储冗余信息的情况下构建完备的查找表的技术难 题， 能够在占用较少内存资源的情况下， 对大规模规则集进行快速查找， 满足核心路 由的高速查找需求。 在本发明的另一实施例中， 步骤 11包括： 步骤 111， 将规则集中的数据包分类规则， 按特征值进行域划分， 得到多个域； 步骤 112， 将所述规则集中的数据包分类规则， 按照每个域进行最小范围的划分， 得到多个最小范围。 其中， 步骤 111具体包括： 步骤 1111， 获取数据包分类规则的特征标记类别； 步骤 1112， 将同一类别特征标记的数据包分类规则划分为一个域。 在上述步骤 1111中， 数据包通常包括： 数据包的源 IP地址、 目的 IP地址、 源介 质访问控制 （MAC, Media Access Control)地址、 目的 MAC地址及 TCP同步标记等 特征标记， 数据包分类规则可以是按照上述数据包的各特征标记或各特征标记的任意 组合进行分类的规则。。通常在核心路由器中使用的数据包分类的特征标记（如上述的 源 IP地址、 目的 IP地址、 源介质访问控制 （MAC, Media Access Control) 地址、 目 的 MAC地址及 TCP同步标记等）类别有 5~7种， 有的场景下可以扩充到十几种甚至 更多， 每一种特征标记或相近特征标记的组合可以称作包分类规则的一个域。 以图 1所示的一个简单的二维包分类问题作为示例。 此二维包分类问题中有三条 规则： Rl、 R2和 R3， 其中规则 R1和 R2部分区域交叠， 规则 R3为一个独立规则， 它们各自在各域中对应的范围表示为 Rl (AO, B2), R2 (A2， BO), R3 (A4， B2)。 对包分类问题的处理通过分域来解决， 将这两条规则分为 A域和 B域， 在 A域中有 三个范围 A0、 A2和 A4， 在 B域中有范围 B0和 B2， 其中 A2是 AO的子范围， B2 是 B0的子范围。因为 A2和 B2的存在，实际上 AO和 B0范围分别被分成了 3段（Al， A2禾口 A3 )， （Bl， B2禾口 B3 )。 上述步骤 112具体可以包括： 步骤 1121， 将每条数据包分类规则在每个域中的字段用前缀表示； 步骤 1122， 将各条数据包分类规则在每个域的前缀表示的字段插入到一棵线段树 中， 线段树的叶节点即是通过线段树划分的此域的最小范围。 一般域字段类型为前缀类型，对于非前缀类型的域也都可以展开成前缀类型处理。 如图 4所示的数据分类规则的规则集表格 401，一可以分为 A域和 B域的有三条规则： Rl、 R2和 R3的数据包， 每条规则都可以分为 A和 B两个域， 每个域中来表示。 如， R1在域 A中的字段用前缀表示为 1000，在域 B中的字段用前缀表示为 01**;同样的， R2在域 A中的字段用前缀表示为 1***， 在域 B中的字段用前缀表示为 010*; R3在 域 A中的字段用前缀表示为 0***， 在域 B中的字段用前缀表示为 00**。 随后， 如图 5所示， 对于域 A， 将 Rl、 R2和 R3的域 A字段插入一棵线段树中， 可以得到如图中域 A示意的结果。 其中 501 505为线段树的叶节点， 即是通过线段树 划分的最短线段。 每个节点对应的规则按照最长前缀匹配定义， 例如节点 502同时对 应了 R1和 R2， 但因为 R1的前缀字段为 1000， 比 R2的前缀字段 1***的字段前缀长 度更长， 因此节点 502对应了规则 Rl， 分配给它等价 ID号 A1 ; 节点 501的范围对应 了规则 R3， 分配给它等价 ID号 A3 ; 节点 503 505本是三个短范围， 但是因为它都对 应了 R2的范围， 因此分配给它们同一个等价 ID号 A2。 同理， 对于域 B， 可以分解 为 3个线段， 节点 506对应 R3， 分配等价 ID号 B1 ; 节点 507对应 R2， 分配等价 ID 号 B2; 节点 508对应 Rl， 分配等价 ID号 B3。 当然， 划分最小范围的方法有很多， 除了如图 5所示利用线段树实现外还可以利 用路径压缩 Trie等算法来实现。 本发明实施例均采用线段树实现最小范围划分。 在本发明的另一实施例中， 上述步骤 12包括： 步骤 121， 为每个最小范围分配一等价 ID号； 步骤 122， 遍历规则集中的每条数据包分类规则， 获得每条数据包分类规则在每 个域中的字段的 ID号， 所述字段的 ID号由所述字段对应的所有叶子节点的等价 ID 号得到； 步骤 123， 将各个域的 ID号进行交叉组合， 得到多个组合项； 步骤 124， 将组合项作为哈希表的哈希键值添加进哈希表， 并将每个组合项对应 的规则结果作为哈希表的结果， 构成等价规则总表。 在图 5中，完成最小范围划分后为每个最小范围分配了等价 ID号。以图 5中的线 段树为例， 如图 6所示， 表 601给出规则集的域 A字段表， 规则 R1的域 A对应了节 点 602， 它只包含了等价 ID号 A1 ; 规则 R2的域 A对应了节点 603， 包含了等价 ID 号 A1和 A2; 规则 R3的域 A对应了节点 604， 包含了等价 ID号 A3。 所以， 规则 R1 的域 A字段的 ID号是 （A1 ); 规则 R2的域 A字段的 ID号是 （Al， A2); 规则 R3 的域 A字段的 ID号是（A3 )。同样方式，如图 7所示， 701给出规则集的域 B字段表，， 规则 R1的域 B对应了节点 703， 包含了等价 ID号 B2和 B3 ; 规则 R2的域 B对应了 节点 704，包含了等价 ID号 B2;规则 R3的域 B对应了节点 702包含了等价 ID号 Bl。 规则 Rl的域 B字段的 ID号是 （B2， B3 ); 规则 R2的域 B字段的 ID号是 （B2 ); 规 则 R3的域 B字段的 ID号是 （Bl )。 如图 8所示，将上述步骤得到的等价 ID号构成规则表 801并且将各域得到的等价 ID号进行交叉组合， 得到多个组合项。 经过交叉组合的规则表如 802所示， R1规则 对应了 A1B2和 A1B3两个组合项； R2对应了 A1B2和 A2B2两个组合项； R3对应了 A3B1—个组合项。 因为所有等价 ID号的组合的键值长度是一致的， 并且属于精确匹 配， 所以可以将等价 ID号作为哈希算法 （HASH Algorithm) 的键值， 每个等价 ID组 合对应的规则结果或规则号作为哈希表的结果， 采用哈希算法进行存储和查找。 再根据表 802将每条规则的每个组合项作为 Hash表的键值添加进哈希表，构成如 图 9所示等价规则总表 901。 可以按照规则集的组合项顺序进行填写， 例如图 9中依 次填写 Rl、 R2、 R3 规则对应的等价 ID组合项。 首先是添加键值 A1B2, 对应结果 R1 (或 R1的查找结果）； 接着添加键值 A1B3 , 对应结果 Rl。 然后是 R2对应的等价 ID组合项， 首先是 A1B2, 因为 A1B2已经存在于哈希表中， 因此需要将对应的结果 R1和 R2进行优先级选择， 选择高优先级的规则作为哈希查找结果； 然后是 A2B2, 对应结果 R2。 最后填写 R3对应的等价 ID组合项， A3B1对应结果 R3。 哈希算法是一种成熟的、 适合硬件实现的快速索引算法， 例如采用并行哈希算法 可以实现对等价规则总表的一次访存查找。 可以看出， 采用上述方法进行叉乘表的处 理可以仅将有意义的键值填写入等价规则总表， 而不会将其它叉乘方法涉及到的冗余 信息进行处理， 充分节省了更新操作时间和存储空间。 由于包分类规则的条目键值长度一般较长， 每个域的比特宽度为 16 32 bit, 查找 时需要在每个域中分别查找最长前缀匹配结果。 传统的方案是采用查找树结构进行查 找， 例如可以采用 Trie类树算法或者二叉树算法等等， 但是采用树结构查找需要多次 访存， 硬件实现时查找延时较大。 本发明采用方法是： 构建等价规则子表和等价映射 表的方法进行快速索引， 下面说明等价规则子表和等价映射表的构建过程。 在本发明的另一个实施例中， 构建等价规则子表， 首先就是执行步骤 13， 具体包 括： 步骤 131， 根据每个域中的字段用前缀表示时的前缀位宽， 将所述域划分得到多 个子域。 上述例子中， 每个域字段位宽 4 bit, 将其分成两个 2 bit的子域。 如图 10所示， 1001为根据图 5中域 A的各叶结点 （501 505 ) 生成的子域表， 分为子域 _1和子域 A_2。 当然， 在分域时， 按照每个域中的字段用前缀表示时的前缀位宽， 位宽也可以 分成一个 1 bit, —个 3 bit的子域等等分法， 当然为方便简单后面的步骤， 优选将 4 bit 的位宽分成两个 2 bit的子域。 在本发明的另一个实施例中， 上述步骤 14， 具体包括： 步骤 141， 将每个子域的前缀表示的字段插入到一棵线段树中， 线段树的叶节点 即是通过线段树划分的此子域的最小范围； 步骤 142， 为每个最小范围分配等价子 ID号； 步骤 143， 将每个子域的前缀表示的字段作为键值， 以及将所述字段对应的等价 子 ID号作为查找结果， 构成等价规则子表。 如图 11所示， 将子域 A_l的条目插入线段树生成子域 A_l的线段树 1101， 如图
12所示， 将子域 A_2的条目插入线段树生成子域 A_2的线段树 1201 ; 然后为每个最 小范围分配等价子 ID号。 最后将每个子域都进行完全展开， 2-bit键值存在 00、 01、 10、 11 四个值， 每个键值分别根据所在的最小范围对应的等价子 ID号进行填写， 得 到如图 13所示的等价规则子表 A_l ( 1301 )和如图 14所示的等价规则子表 A_2( 1401 )。 例如子域 A_l的值 00属于最小范围 0*， 对应了等价子 ID号 al3 ; 01属于最小范围 0*， 对应 al3 ; 10属于最小范围 10， 对应 al l ; 11属于最小范围 11， 对应 al2。 同样方法， 对域 B进行上述操作， 如图 15， 图 16， 图 17所示， 最终获得如图 18 所示的等价规则子表 B_l ( 1801 ) 和如图 19所示的等价规则子表 B_2 ( 1901 )。 其中 子域 B_l中， 数值 10和 11因为不被任何最小有效范围包含， 因此没有等价子 ID号 相对应， 因此其直接索引的查找结果为空。如果查找中出现查中这样结果为空的查找， 说明该次查找的整条规则都不存在于规则表中， 将返回未命中信息。 至此， 完成等价规则子表的构建。 在本发明的另一个实施例中上述步骤 15具体包括： 步骤 151， 将每个子域的最小范围对应的等价子 ID号进行叉乘， 生成哈希键值； 步骤 152， 每个哈希键值对应的等价 ID号， 作为查找结果， 构成等价映射表。 沿用上述例子， 如图 20所示。 域 A子域表的第一条： 等价 ID号 A1对应了子域 A_l的 10和子域 A_2的 00， 10对应的等价子 ID号为 al l , 00对应的等价子 ID号为 a21， 因此等价映射表的第一个条目为 alla21， 对应的结果为 Al。 域 A子域表的第四 条： 等价 ID号 A2对应了子域 A_l的 11和子域 A_2的 **， 11对应的等价子 ID号为 al2， **对应的等价子 ID号有 a21、 a22、 a23 , 因此向等价映射表的添加 3个条目为 al2a21、 al2a22、 al2a23 , 它们对应的结果都为 A2。 依此方法， 完全生成域 A的等价 映射表 2001。 同样方法， 如图 21所示， 完全生成域 B的等价映射表 2101。 经过上述各步骤， 生成了本发明中算法部分的所有表项， 其中用于查找的表为： 各等价规则子表、 各等价映射表和等价规则总表。 如图 25所示， 为等价规则子表、 等 价映射表和等价规则总表生成的一过程实例图。 下面， 在本发明的另一个实施例中， 上述步骤 16具体包括： 步骤 161， 将查找键值按照各子域的位宽进行分域， 得到各子域的键值； 步骤 162， 根据各子域的键值， 在等价规则子表进行查找， 得到等价子 ID号； 步骤 163， 将获得的等价子 ID号合并组成等价映射表的哈希键值； 步骤 164， 根据所述等价映射表的哈希键值， 在所述等价映射表进行查找， 得到 等价 ID号； 步骤 165， 将获得的等价 ID号合并组成等价规则总表的哈希键值； 步骤 166， 根据等价规则总表的哈希键值， 在所述等价规则总表进行查找， 得到 最终查找结果。 本发明的上述实施例进行包分类查找时， 只需要根据查找键值依次对各个等价子 表、 各个等价映射表和等价规则总表进行查表， 即可获得查找结果。 利用本发明能够 在占用较少内存资源情况下， 对大规模规则集进行快速查找， 满足核心路由器的高速 查找需求。 本发明的实施例还提供一种包分类规则的查找装置， 包括： 第一划分模块， 设置为将规则集中的数据包分类规则，按域进行最小范围的划分， 得到多个最小范围； 等价规则总表构建模块，设置为为每个最小范围分别分配一等价 ID号，得到由所 述等价 ID号形成的等价规则总表； 分子域模块， 设置为将所述域进行划分， 得到多个子域； 等价规则子表构建模块，设置为为每个子域分别分配一个等价子 ID号，得到由所 述等价子 ID号形成的等价规则子表； 等价映射表构建模块， 设置为根据所述等价规则总表以及所述等价规则子表， 得 到等价映射表； 数据包查找模块， 设置为根据所述等价映射表、等价规则子表以及等价规则总表， 查找数据包。 其中， 所述第一划分模块包括： 分域模块， 设置为将规则集中的数据包分类规则， 按特征值进行域划分， 得到多 个域； 划分子模块， 设置为将所述规则集中的数据包分类规则， 按照每个域进行最小范 围的划分， 得到多个最小范围。 其中， 所述分域模块包括： 检测模块， 设置为获取数据包分类规则的特征标记类别； 划域模块， 设置为将同一类别特征标记的数据包分类规则划分为一个域。 其中， 所述划分子模块包括： 第一字段模块， 设置为将每条数据包规则在每个域中的字段用前缀表示； 第一范围划分模块，设置为将各条规则在每个域的对应字段插入到一棵线段树中， 线段树的叶节点即是通过线段树划分的此域的最小范围。 其中， 所述等价规则总表构建模块包括： 等价 ID号分配模块， 设置为为每个最小范围分配一等价 ID号； 等价 ID号获取模块，设置为遍历规则集中的每条数据包分类规则，获得每条数据 包分类规则在每个域中的字段的 ID号， 所述字段的 ID号由所述字段对应的所有叶子 节点的等价 ID号得到； 等价 ID号组合模块， 设置为将获取的各个域的等价 ID号进行交叉组合， 得到多 个组合项； 第一构建模块， 设置为将组合项作为哈希表的哈希键值添加进哈希表， 并将每个 组合项对应的规则结果作为哈希表的结果， 构成等价规则总表。 其中， 所述分子域模块包括： 位宽划分模块， 设置为根据每个域中的字段用前缀表示时的前缀位宽， 将所述域 划分得到多个子域。 其中， 所述等价规则子表构建模块包括： 第二范围划分模块， 设置为将每个子域的前缀表示的字段插入到一棵线段树中， 线段树的叶节点即是通过线段树划分的此子域的最小范围； 等价子 ID号分配模块， 设置为为每个最小范围分配等价子 ID号； 第二构建模块， 设置为将每个子域的前缀表示的字段作为键值， 以及将所述字段 对应的等价子 ID号作为查找结果， 构成等价规则子表。 其中， 所述等价映射表构建模块包括： 等价子 ID号组合模块， 设置为将每个子域的最小范围对应的等价子 ID号进行叉 乘， 生成哈希键值； 第三构建模块， 设置为每个哈希键值对应的等价 ID号， 作为查找结果， 构成等价 映射表。 其中， 所述数据包查找模块包括： 第一键值处理模块， 设置为将查找键值按照各子域的位宽进行分域， 得到各子域 的键值； 等价规则子表查找模块， 设置为根据各子域的键值， 在等价规则子表进行查找， 得到等价子 ID号； 第二键值处理模块， 设置为将获得的等价子 ID 号合并组成等价映射表的哈希键 值； 等价映射表查找模块， 设置为根据所述等价映射表的哈希键值， 在所述等价映射 表进行查找， 得到等价 ID号； 第三键值处理模块， 设置为将获得的等价 ID 号合并组成等价规则总表的哈希键 值； 等价规则总表查找模块， 设置为根据等价规则总表的哈希键值， 在所述等价规则 总表进行查找， 得到最终查找结果。 如图 22所示， 给出了硬件实现查找模块流程图。 首先查找键值 2201在第一键值 处理模块 2202被按照各子域的位宽进行分域， 得到各子域的键值 2203 ; 然后在等价 规则子表查找模块将各子域的键值 2203输入等价规则子表 2204进行查找， 得到等价 子 ID号； 在第二键值处理模块将各相关的等价子 ID号合并， 组成等价映射表哈希键 值 2205; 等价映射表查找模块将各等价映射表哈希键值 2205输入等价映射表 2206进 行哈希查找， 获得查找结果等价 ID号； 在第三键值处理模块将获得的等价 ID号进行 合并， 组成等价规则总表哈希键值 2207; 在等价规则总表查找模块将各等价规则总表 哈希键值 2207输入等价规则总表 2208进行哈希查找， 获得最终查找结果 2209。 本发明具体实施例中， 等价规则子表为直接表， 采用键值作为地址直接索引的方 式进行查找； 等价映射表和等价规则总表为哈希表， 在硬件实现上可以采用多种哈希 表实现方式， 本发明以公开的并行哈希方法为具体实现方式进行描述。 由于等价规则子表的条目位宽很小， 条目都非常少， 因此虽然在等价规则子表中 存在冗余空间， 如 1801表中所示， 但占用非常有限； 本发明实施例以直接表查表方式 为实现方式是考虑到查找延时小、 且实现代价不大。 对于查找延时要求不高的场景， 等价规则子表的查找实现方式也不局限于直接表方式， 可以采用哈希算法、 查找树结 构等方式实现。 等价规则总表和等价映射表的实现方式也不局限于哈希表实现方式， 本发明实施例以并行哈希表为实现方式主要考虑的是哈希表的查找延时较小； 对于对 查找延时需求不高的情况下， 可以采用查找树方式实现。 图 23和图 24显示了两种查找方式的硬件模块图。 2301为直接表， 实际为一块特 定的硬件内存， 查表的键值即内存的读请求地址， 输出为相应地址的存储信息。 2401 为并行哈希表， 由 N个哈希处理模块并行组成； 键值输入到并行哈希表后， 先经过 N 次并行的哈希计算（2402)， 计算后的结果为访问对应存储模块的地址； 读取相应地址 的存储信息 （2403 )， 获得每个哈希表的查找结果； 2404 所示的结果比较聚合模块， 对每个哈希结果与输入键值比较， 选择匹配的结果输出。 需要说明的是， 该包分类规则的查找装置是应用了上述包分类规则的查找方法的 装置， 上述包分类规则的查找方法的实施例的实现方式同样适用于该包分类规则的查 找装置的实施例中， 也能达到相同的技术效果。 以上所述是本发明的优选实施方式， 应当指出， 对于本技术领域的普通技术人员 来说， 在不脱离本发明所述原理的前提下， 还可以作出若干改进和润饰， 这些改进和 润饰也应视为本发明的保护范围。 工业实用性 如上所述， 本发明实施例提供的一种包分类规则的查找方法及装置， 具有以 下有益效果： 适合硬件实现， 能够在占用较少内存资源的情况下， 对大规模规则集 进行快速查找， 满足核心路由器的高速查找需求。

Claims

权 利 要 求 书
1. 一种包分类规则的查找方法， 包括下列步骤： 将规则集中的数据包分类规则， 按域进行最小范围的划分， 得到多个最小 范围；
为每个最小范围分别分配一等价 ID号， 得到由所述等价 ID号形成的等价 规则总表；
将所述域进行划分， 得到多个子域；
为每个子域分别分配一个等价子 ID号， 得到由所述等价子 ID号形成的等 价规则子表； 根据所述等价规则总表以及所述等价规则子表， 得到等价映射表； 根据所述等价映射表、 等价规则子表以及等价规则总表， 查找数据包。
2. 根据权利要求 1所述的包分类规则的查找方法， 其中， 将规则集中的数据包分 类规则， 按域进行最小范围的划分， 得到多个最小范围的步骤包括：
将规则集中的数据包分类规则， 按特征值进行域划分， 得到多个域； 将所述规则集中的数据包分类规则， 按照每个域进行最小范围的划分， 得 到多个最小范围。
3. 根据权利要求 2所述的包分类规则的查找方法， 其中， 将规则集中的数据包分 类规则， 按特征值进行域划分， 得到多个域的步骤包括：
获取数据包分类规则的特征标记类别； 将同一类别特征标记的数据包分类规则划分为一个域。
4. 根据权利要求 2所述的包分类规则的查找方法， 其中， 将所述规则集中的数据 包分类规则，按照每个域进行最小范围的划分，得到多个最小范围的步骤包括: 将每条数据包分类规则在每个域中的字段用前缀表示； 将各条数据包分类规则在每个域的前缀表示的字段插入到一棵线段树中， 线段树的叶节点即是通过线段树划分的此域的最小范围。
5. 根据权利要求 1所述的包分类规则的查找方法， 其中， 为每个最小范围分别分 配一等价 ID号， 得到由所述等价 ID号形成的等价规则总表的步骤包括： 为每个最小范围分配一等价 ID号； 遍历规则集中的每条数据包分类规则， 获得每条数据包分类规则在每个域 中的字段的 ID号，所述字段的 ID号由所述字段对应的所有叶子节点的等价 ID 号得到；
将各个域的 ID号进行交叉组合， 得到多个组合项； 将组合项作为哈希表的哈希键值添加进哈希表， 并将每个组合项对应的规 则结果作为哈希表的结果， 构成等价规则总表。
6. 根据权利要求 4所述的包分类规则的查找方法， 其中， 将所述域进行划分， 得 到多个子域的步骤包括： 根据每个域中的字段用前缀表示时的前缀位宽， 将所述域划分得到多个子 域。
7. 根据权利要求 6所述的包分类规则的查找方法， 其中， 为每个子域分别分配一 个等价子 ID号， 得到由所述等价子 ID号形成的等价规则子表的步骤包括： 将每个子域的前缀表示的字段插入到一棵线段树中， 线段树的叶节点即是 通过线段树划分的此子域的最小范围；
为每个最小范围分配等价子 ID号；
将每个子域的前缀表示的字段作为键值， 以及将所述字段对应的等价子 ID 号作为查找结果， 构成等价规则子表。
8. 根据权利要求 1所述的包分类规则的查找方法， 其中， 根据所述等价规则总表 以及所述等价规则子表， 得到等价映射表的歩骤包括：
将每个子域的最小范围对应的等价子 ID号进行叉乘， 生成哈希键值； 将每个哈希键值对应的等价 ID号， 作为查找结果， 构成等价映射表。
9. 根据权利要求 1所述的包分类规则的查找方法， 其中， 根据所述等价规则映射 表、 等价规则子表以及等价规则总表， 查找数据包的步骤包括： 将查找键值按照各子域的位宽进行分域， 得到各子域的键值； 根据各子域的键值， 在等价规则子表进行查找， 得到等价子 ID号； 将获得的等价子 ID号合并组成等价映射表的哈希键值； 根据所述等价映射表的哈希键值， 在所述等价映射表进行查找， 得到等价 ID号； 将获得的等价 ID号合并组成等价规则总表的哈希键值； 根据等价规则总表的哈希键值， 在所述等价规则总表进行查找， 得到最终 查找结果。
10. 一种包分类规则的查找装置 ， 包括： 第一划分模块， 设置为将规则集中的数据包分类规则， 按域进行最小范围 的划分， 得到多个最小范围； 等价规则总表构建模块， 设置为为每个最小范围分别分配一等价 ID 号， 得到由所述等价 ID号形成的等价规则总表； 分子域模块， 设置为将所述域进行划分， 得到多个子域； 等价规则子表构建模块， 设置为为每个子域分别分配一个等价子 ID 号， 得到由所述等价子 ID号形成的等价规则子表； 等价映射表构建模块， 设置为根据所述等价规则总表以及所述等价规则子 表， 得到等价映射表； 数据包查找模块， 设置为根据所述等价映射表、 等价规则子表以及等价规 则总表， 查找数据包。
11. 根据权利要求 10所述的包分类规则的查找装置，其中，所述第一划分模块包括: 分域模块， 设置为将规则集中的数据包分类规则， 按特征值进行域划分， 得到多个域； 划分子模块， 设置为将所述规则集中的数据包分类规则， 按照每个域进行 最小范围的划分， 得到多个最小范围。
12. 根据权利要求 11所述的包分类规则的查找装置， 其中， 所述分域模块包括： 检测模块， 设置为获取数据包分类规则的特征标记类别；
划域模块， 设置为将同一类别特征标记的数据包分类规则划分为一个域。
13. 根据权利要求 11所述的包分类规则的查找装置， 其中， 所述划分子模块包括： 第一字段模块， 设置为将每条数据包规则在每个域中的字段用前缀表示； 第一范围划分模块， 设置为将各条规则在每个域的对应字段插入到一棵线 段树中， 线段树的叶节点即是通过线段树划分的此域的最小范围。
14. 根据权利要求 10所述的包分类规则的查找装置，其中，所述等价规则总表构建 模块包括：
等价 ID号分配模块， 设置为为每个最小范围分配一等价 ID号； 等价 ID 号获取模块， 设置为遍历规则集中的每条数据包分类规则， 获得 每条数据包分类规则在每个域中的字段的 ID号， 所述字段的 ID号由所述字段 对应的所有叶子节点的等价 ID号得到；
等价 ID号组合模块， 设置为将获取的各个域的等价 ID号进行交叉组合， 得到多个组合项； 第一构建模块， 设置为将组合项作为哈希表的哈希键值添加进哈希表， 并 将每个组合项对应的规则结果作为哈希表的结果， 构成等价规则总表。
15. 根据权利要求 13所述的包分类规则的查找装置， 其中， 所述分子域模块包括： 位宽划分模块， 设置为根据每个域中的字段用前缀表示时的前缀位宽， 将 所述域划分得到多个子域。
16. 根据权利要求 15所述的包分类规则的查找装置，其中，所述等价规则子表构建 模块包括：
第二范围划分模块， 设置为将每个子域的前缀表示的字段插入到一棵线段 树中， 线段树的叶节点即是通过线段树划分的此子域的最小范围；
等价子 ID号分配模块， 设置为为每个最小范围分配等价子 ID号； 第二构建模块， 设置为将每个子域的前缀表示的字段作为键值， 以及将所 述字段对应的等价子 ID号作为查找结果， 构成等价规则子表。
17. 根据权利要求 10所述的包分类规则的查找装置，其中，所述等价映射表构建模 块包括：
等价子 ID号组合模块， 设置为将每个子域的最小范围对应的等价子 ID号 进行叉乘， 生成哈希键值；
第三构建模块， 设置为将每个哈希键值对应的等价 ID号， 作为查找结果， 构成等价映射表。
8. 根据权利要求 10所述的包分类规则的查找装置，其中，所述数据包查找模块包 括： 第一键值处理模块， 设置为将查找键值按照各子域的位宽进行分域， 得到 各子域的键值；
等价规则子表查找模块， 设置为根据各子域的键值， 在等价规则子表进行 查找， 得到等价子 ID号； 第二键值处理模块， 设置为将获得的等价子 ID 号合并组成等价映射表的 哈希键值；
等价映射表查找模块， 设置为根据所述等价映射表的哈希键值， 在所述等 价映射表进行查找， 得到等价 ID号； 第三键值处理模块， 设置为将获得的等价 ID 号合并组成等价规则总表的 哈希键值； 等价规则总表查找模块， 设置为根据等价规则总表的哈希键值， 在所述等 价规则总表进行查找， 得到最终查找结果。
PCT/CN2014/080445 2013-09-24 2014-06-20 一种包分类规则的查找方法及装置 WO2015043254A1 (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
CN201310439994.2 2013-09-24
CN201310439994.2A CN104462144B (zh) 2013-09-24 2013-09-24 一种包分类规则的查找方法及装置

Publications (1)

Publication Number Publication Date
WO2015043254A1 true WO2015043254A1 (zh) 2015-04-02

Family

ID=52741981

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CN2014/080445 WO2015043254A1 (zh) 2013-09-24 2014-06-20 一种包分类规则的查找方法及装置

Country Status (2)

Country Link
CN (1) CN104462144B (zh)
WO (1) WO2015043254A1 (zh)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111177198A (zh) * 2019-12-27 2020-05-19 芯启源（南京）半导体科技有限公司 一种用于芯片的内容查找方法
CN115022225A (zh) * 2022-05-31 2022-09-06 东风电驱动系统有限公司 报文转发方法、装置、设备及可读存储介质

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN106326234A (zh) * 2015-06-18 2017-01-11 深圳市中兴微电子技术有限公司 流分类方法及装置
CN109754021B (zh) * 2019-01-11 2022-03-18 湖南大学 基于范围元组搜索的在线包分类方法
CN111817978B (zh) * 2019-04-12 2022-10-04 华为技术有限公司 一种流分类方法及装置
CN113642594A (zh) * 2020-04-27 2021-11-12 深圳市中兴微电子技术有限公司 报文分类方法及装置、电子设备、可读介质
CN111736982B (zh) * 2020-05-12 2023-12-08 深圳震有科技股份有限公司 一种5g数据转发平面的数据转发处理方法和服务器

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1477494A (zh) * 2002-08-20 2004-02-25 深圳市中兴通讯股份有限公司上海第二 一种数据包递归流分类方法
CN101594303A (zh) * 2009-07-10 2009-12-02 清华大学 基于网络流量统计信息的快速网包分类方法
CN101714948A (zh) * 2009-10-27 2010-05-26 清华大学 一种多域的网包的分类方法和装置
CN101753445A (zh) * 2009-12-23 2010-06-23 重庆邮电大学 基于关键字分解Hash算法的快速流分类方法
CN102420831A (zh) * 2011-12-16 2012-04-18 清华大学 一种多域网包分类方法

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9110936B2 (en) * 2010-12-28 2015-08-18 Microsoft Technology Licensing, Llc Using index partitioning and reconciliation for data deduplication
US8500026B2 (en) * 2011-12-06 2013-08-06 Xerox Corporation Dual resolution two-dimensional barcode

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1477494A (zh) * 2002-08-20 2004-02-25 深圳市中兴通讯股份有限公司上海第二 一种数据包递归流分类方法
CN101594303A (zh) * 2009-07-10 2009-12-02 清华大学 基于网络流量统计信息的快速网包分类方法
CN101714948A (zh) * 2009-10-27 2010-05-26 清华大学 一种多域的网包的分类方法和装置
CN101753445A (zh) * 2009-12-23 2010-06-23 重庆邮电大学 基于关键字分解Hash算法的快速流分类方法
CN102420831A (zh) * 2011-12-16 2012-04-18 清华大学 一种多域网包分类方法

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111177198A (zh) * 2019-12-27 2020-05-19 芯启源（南京）半导体科技有限公司 一种用于芯片的内容查找方法
CN111177198B (zh) * 2019-12-27 2023-06-16 芯启源（南京）半导体科技有限公司 一种用于芯片的内容查找方法
CN115022225A (zh) * 2022-05-31 2022-09-06 东风电驱动系统有限公司 报文转发方法、装置、设备及可读存储介质
CN115022225B (zh) * 2022-05-31 2023-11-10 东风电驱动系统有限公司 报文转发方法、装置、设备及可读存储介质

Also Published As

Publication number Publication date
CN104462144A (zh) 2015-03-25
CN104462144B (zh) 2019-06-14

Similar Documents

Publication Publication Date Title
US11102120B2 (en) Storing keys with variable sizes in a multi-bank database
WO2015043254A1 (zh) 一种包分类规则的查找方法及装置
CN104468381B (zh) 一种多域流规则匹配的实现方法
US9098601B2 (en) Ternary content-addressable memory assisted packet classification
TW498650B (en) Flexible and highly efficient packet classification method
CN101827137B (zh) 一种基于哈希表和扩展存储器的高性能IPv6地址查找方法
EP3276501B1 (en) Traffic classification method and device, and storage medium
EP3661153B1 (en) Building decision tree for packet classification
CN101621502A (zh) 存储、查找路由表的方法及装置
US10771386B2 (en) IP routing search
WO2011124030A1 (zh) 路由表项的存储方法和装置
CN101222434B (zh) 存储策略控制列表、策略搜索方法和三态寻址存储器
CN106789727B (zh) 报文分类方法和装置
CN103457855B (zh) 无类域间路由表建立、以及报文转发的方法和装置
Hsieh et al. A classified multisuffix trie for IP lookup and update
CN116319555B (zh) 一种面向虚拟专用网络的路由转发方法
US10476785B2 (en) IP routing search
Chang et al. LayeredTrees: Most specific prefix-based pipelined design for on-chip IP address lookups
CN102739550B (zh) 基于随机副本分配的多存储器流水路由体系结构
CN101645852B (zh) 一种网络包分类的设备和方法
CN110995876A (zh) 一种ip存储与查找的方法及装置
Lin et al. TCAM-Based Packet Classification Using Multi-stage Scheme
Puš Packet Classification Algorithms.
Pus Packet Classification Algorithms
KR20050043035A (ko) 복수의 해슁 함수를 이용한 ｉｐ 어드레스 검색 방법 및하드웨어 구조

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 14847181

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 14847181

Country of ref document: EP

Kind code of ref document: A1