Patent ID: 7480302

Claim:
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.