Patent ID: 7747553

Claim:
A method for generating a partitioned rule set for use in classifying a packet for a communications network, the method comprising executing the following steps: obtaining a rule set comprising a plurality of rules, the plurality of rules being used to classify a packet for the communications network; partitioning the rule set into a plurality of horizontal subsets in accordance with a classification operation and a field associated with the rule set, a given horizontal subset comprising one or more rule layers, each of the one or more rule layers comprising one or more of the plurality of rules; partitioning at least a first and a second of the plurality of horizontal subsets into a plurality of vertical subsets, wherein, within a given one of the plurality of horizontal subsets, a first vertical subset range interval of a given one of the plurality of vertical subsets is non-overlapping with a second vertical subset range interval of another given one of the plurality of vertical subsets; creating a plurality of non-overlapping partitions across a range interval of the rule set, a given one of the non-overlapping partitions corresponding to values which are within each of a set of vertical subset range intervals comprising one vertical subset within at least the first and the second of the horizontal subsets; and generating a hash table that indexes the plurality of vertical subsets in accordance with the plurality of non-overlapping partitions, wherein a given vertical subset is grouped together with a given partition in accordance with a corresponding range interval of the given vertical subset.