Method and apparatus for high-speed network rule processing

A method of performing network packet filtering with an N dimensional rule set, said method comprising:

• dividing said N dimensional rule set along a first dimension into different service class ranges, said service class ranges specifying different network service classes;
• preprocessing said N dimensional rule set along said first dimension to generate a first search structure with a first set of class ranges along said first dimension and, each service class range having a subset of service class rules;
• preprocessing each subset of service class rules associated with each service class range to generate subset of rule ranges along each of said N−1 remaining dimensions;
• receiving a packet;
• initially searching said first search structure along said first dimension of said received packet to select an associated service class of said packet and to select a subset of rule ranges for said associated class of said received packet;
• subsequent to initially searching said first search structure, searching said selected subset of rule range along said N−1 dimensions in parallel to generate N−1 sets of possible rules along said N−1 dimensions;
• logically combining said N−1 sets of possible rules to generate a final set of possible rules for said associated service class;
• and
• applying said final set of possible rules.