Packet classification method through hierarchical rulebase partitioning
AssigneesSamsung Electronics Co., Ltd., Korea University Industry and Academy Corporation Foundation
InventorLynn Choi
Life of this patent
Estimating the term…
Abstract
A packet classification method through hierarchical rulebase partitioning. The packet classification method for searching for a rule having a highest priority and matching among a plurality of rules included in a specified rulebase with respect to a packet input from an external network and processing the packet according to the searched rule. The method includes: a preprocessing step of partitioning the rulebase into a plurality of independent sub-rulebases based on a specified condition and producing a hash table on the basis of the sub-rulebases; and a classification step of classifying the packet by searching the hash table using a hash key extracted from a packet header of the inputted packet and mapping the packet on the sub-rulebase corresponding to the packet.
Claims13
A packet classification method for searching for a rule having a highest priority and matching among a plurality of rules included in a specified rulebase with respect to a packet input from an external network and processing the packet according to the searched rule, the method comprising:
- preprocessing by partitioning the rulebase into a plurality of independent sub-rulebases based on a specified condition and producing a hash table on the basis of the sub-rulebases;
- and
- classifying the packet by searching the hash table using a hash key extracted from a packet header of the inputted packet and mapping the packet on the sub-rulebase corresponding to the packet,
- wherein the preprocessing includes a first partitioning of the rulebase into the plurality of sub-rulebases based on a specified protocol and a specified port number and producing the hash table on the basis of the sub-rulebases,
- wherein the preprocessing includes a second partitioning re-partitioning a specified sub-rulebase among the plurality of sub-rulebases using the hash key extracted by a specified method from departure and destination IP addresses, and producing the hash table on the basis of the sub-rulebases when the number of rules on the specified sub-rulebases exceeds a specified threshold value,
- wherein the specified method is an MSB pattern, an exponential growing pattern, a mask distribution pattern or an entropy-maximizing pattern, and
- wherein the mask distribution pattern method calculates accumulated values at respective bit positions bi by adding the number of bits which are not a dummy bit in all defined rules belonging to the rulebase, calculates the total accumulated value by adding the accumulated values from the most significant bit to the least significant bit, and then selects the specified bit position whenever the accumulated value at the specified bit position becomes a multiple of a value obtained by dividing the total accumulated value by K which is a bit value of the hash key to be generated.
A method of reducing a search time for packet classification of an input packet, comprising:
- hierarchally partitioning a rulebase into sub-rulebases by hashing bit fields selected from a classification field;
- extracting a hash key from a header of the input packet;
- and
- searching a hash table using the hash key to match the input packet to a corresponding sub-rulebase,
- wherein the hierarchally partitioning includes a first partitioning of the rulebase into the plurality of sub-rulebases based on a specified protocol and a specified port number and producing the hash table on the basis of the sub-rulebases,
- wherein the hierarchally partitioning includes a second partitioning re-partitioning a specified sub-rulebase among the plurality of sub-rulebases using the hash key extracted by a specified method from departure and destination IP addresses, and producing the hash table on the basis of the sub-rulebases when the number of rules in the specified sub-rulebase exceeds a specified threshold value,
- wherein the specified method is an MSB pattern, an exponential growing pattern, a mask distribution pattern or an entropy-maximizing pattern, and
- wherein the mask distribution pattern method calculates accumulated values at respective bit positions bi by adding the number of bits which are not a dummy bit in all defined rules belonging to the rulebase, calculates the total accumulated value by adding the accumulated values from the most significant bit to the least significant bit, and then selects the specified bit position whenever the accumulated value at the specified bit position becomes a multiple of a value obtained by dividing the total accumulated value by K which is a bit value of the hash key to be generated.
A packet classification method of searching for a rule having a highest priority in a rulebase with respect to an input packet and, comprising:
- partitioning the rulebase into a plurality of sub-rulebases based on a specified condition and producing a hash table on the basis of the sub-rulebases;
- extracting a hash key from a packet header of packet;
- and
- classifying the packet by searching the hash table using the hash key;
- and
- mapping the packet on the sub-rulebase corresponding to the packet,
- wherein the partitioning includes a first partitioning of the rulebase into the plurality of sub-rulebases based on a specified protocol and a specified port number and producing the hash table on the basis of the sub-rulebases,
- wherein the partitioning includes a second partitioning re-partitioning a specified sub-rulebase among the plurality of sub-rulebases using the hash key extracted by a specified method from departure and destination IP addresses, and producing the hash table on the basis of the sub-rulebases when the number of rules in the specified sub-rulebase exceeds a specified threshold value,
- wherein the specified method is an MSB pattern, an exponential growing pattern, a mask distribution pattern or an entropy-maximizing pattern, and
- wherein the mask distribution pattern method calculates accumulated values at respective bit positions bi by adding the number of bits which are not a dummy bit in all defined rules belonging to the rulebase, calculates the total accumulated value by adding the accumulated values from the most significant bit to the least significant bit, and then selects the specified bit position whenever the accumulated value at the specified bit position becomes a multiple of a value obtained by dividing the total accumulated value by K which is a bit value of the hash key to be generated.
Dependencies are inferred from the claim text.