Method and system for packet classification with reduced memory space and enhanced access speed

Claim 1

A packet classification method applicable to a packet classification system for packet classification on a networking device having an embedded memory unit and associated with a user-predefined original rule database at least having a source IP address field, a destination IP address field, a source port field, a destination port field, and a protocol field, the packet classification system having a preprocessing unit and a packet processing unit, the preprocessing unit including a rule rearrangement module and a classification lookup data building module, the packet processing unit including a protocol range retrieving module, an ABV-FBV lookup module, a probable bit vector generating module and a rule search module, the packet classification method comprising: a preprocessing stage and a packet processing stage; wherein the preprocessing stage includes: utilizing the rule rearrangement module to perform a protocol-oriented rule rearrangement process on the user-predefined original rule database based on user-preset values in the protocol field of the user-predefined original rule database, wherein the user-predefined original rule database is rearranged in such a manner that a DON'T-CARE protocol value is rearranged to a topmost position and all protocol-specific values are arranged in an ascending order following the DON'T-CARE protocol value; utilizing the classification lookup data building module to build a classification lookup database file which at least includes an ABV-FBV index table dataset and a protocol range dataset based on the rearranged rule database, the ABV-FBV index table dataset having a split full-tree schema; and storing the classification lookup database file into the embedded memory unit of the networking device; and wherein the packet processing stage is performed in response to an incoming packet to the networking device during active operation of the networking device, and which includes: utilizing the protocol range retrieving module to check the protocol of the incoming packet and use the protocol value of the incoming packet as an index to retrieve a corresponding packet-specific protocol range from the protocol range dataset prestored in the embedded memory unit of the networking device; utilizing the ABV-FBV lookup module to check a source IP address and destination IP address of the incoming packet and use the source IP address and destination IP address as indexes to retrieve corresponding sets of aggregated bit vectors and folded bit vectors from the ABV-FBV index table dataset prestored in the embedded memory unit of the networking device; utilizing the probable bit vector generating module to generate a probable bit vector based on each retrieved pair of aggregated bit vector and folded bit vector from the ABV-FBV index table dataset; and utilizing the rule search module to perform a search through the probable bit vector within a don't-care protocol range and the packet-specific protocol range to find every rule in the user-predefined original rule database that is matched to the incoming packet, and then return a higher-prioritized rule as the end result of the packet classification.