Patent ID: 7535906

Claim:
A method for classifying data packets in a data processing device according to a set of processing rules, the method comprising: receiving a data packet comprising a plurality of data items, each data item comprising a field value; parsing the data packet to identify a plurality of data items used to classify said data packet according to a plurality of context-specific rule sets; wherein each rule in a rule set defines a rule range indicating a range of possible values for the corresponding data item for which that rule applies; wherein a different rule set is defined for each context, and each data packet must be classified according to a particular context-specific rule set which corresponds to a context identifier associated with that data packet; performing a preliminary test of each field value of the identified data items for a match with any of a predetermined set of frequently-occurring values for that data item stored in appropriate register sets, each frequently-occurring value being associated with a predetermined range identifier, and, if a match is obtained, selecting for the data item the range identifier associated with the matching frequently-occurring value; excluding any data item for which a match is obtained from subsequent field searches for the packet; accessing a look-up table stored in memory to obtain, for each of the plurality of non-excluded data items, a start address of a field search structure associated with the context identifier for the data packet; accessing the field search structure at the appropriate start address in memory; performing field searches for each non-excluded data item in order to select a range identifier corresponding to the value of the data item from a predetermined set of range identifiers for that data item, the set of range identifiers indicating, for all possible values of the data item, which of the rule ranges corresponding to the data item in the rule set a value intersects; combining the range identifiers from the preliminary test and the range identifiers from the field searches to generate a search key comprising a bit string; accessing the look-up table to retrieve a start address for a final search structure associated with the context identifier; performing a final search using the search key and the appropriate final search structure; identifying, based on the search key, a rule identifier for a highest priority rule in the appropriate rule set for the packet context; and outputting the rule identifier so that the packet can be processed according to the applicable rule.