Patent ID: 8879550

Claim:
A method of packet classification in a network node comprising: obtaining a packet key corresponding to a data packet received by the network node; identifying a packet processing rule or rules that are possible matches for the packet key by comparing characteristic bits of the packet key to rule fingerprints in a fingerprint database serving as a compressed representation of a rules database comprising a set of packet processing rules, said rule fingerprints comprising cut-point bits corresponding to bit positions in the packet processing rules that operate as search cut-points distinguishing between the rules or subsets of them, and wherein said characteristic bits of the packet key occupy bit positions corresponding to said cut-point bits, and further wherein the fingerprint database provides exact matching between packet keys and respective individual rules in the rules database, based on said method including preprocessing of the rules database to obtain the fingerprint database by: logically ordering the packet processing rules in the rules database in binary order; obtaining the bit positions of the most-significant bits produced from application of an exclusive-or operation to pairs of the packet processing rules taken in said binary order, wherein these bit positions are said cut-point bits, based on dividing and further subdividing the set of packet processing rules according to the cut-point bits taken in descending or ascending order, said search structure embodying said fingerprint database; fetching the identified packet processing rule or rules from the rules database; comparing the packet key with the fetched rule or rules; and indicating a rule hit or miss in dependence on whether the packet key matches any of the fetched rule or rules.