Methods for performing packet classification

A method comprising:

• defining dimensions comprising whole or partial fields in a packet header to be used for packet classification;
• generating a set of rule bit vectors for each dimension, each bit in a rule bit vector identifying a rule in a rule database for handling packets based on a corresponding dimension value or range, each set of rule bit vectors defining a zeroth phase-chunk;
• selecting split criteria used to partition the rule database;
• defining a partitioned reduction tree configuration defining how a sequence of downstream chunks are to be generated for each partition in the rule database;
• and
• in a recursive manner, for each partition, generating downstream chunks by cross-producting the rule bit vectors of upstream chunks associated with respective groups in view of the partitioned reduction tree configuration, beginning with the zeroth phase chunks, until a final chunk is generated for each partition.

A machine readable medium, to store instructions that if executed perform operations comprising:

• retrieving a set of original rule bit vectors for each of multiple dimensions comprising a whole or partial field in a packet header to be used for packet classification, each bit in an original rule bit vector identifying a rule for handling packets based on a corresponding dimension value or range, each set of original rule bit vectors defining an original chunk;
• reading grouping information defining a group to which each original chunk is associated;
• optimizing rule bit vectors in at least one original chunk to produce an optimized chunk by zeroing out selected set bits such that rule bit vectors generated by cross-producting each of the original rule bit vectors and the optimized rule bit vectors of an original chunk with rule bit vectors for a chunk or chunks in an associated group will have the same highest priority bit set;
• and
• for each optimized chunk, cross-producting the optimized rule bit vectors with original or optimized rule bit vectors in the chunk or chunks of the optimized chunk's associated group to produce a cross-producted chunk.

A network line card, comprising:

• a network processor, a plurality of input/output (I/O) ports, communicatively-coupled to the network processor;
• memory, communicatively-coupled to the network processor;
• and
• a storage device, communicatively-coupled to the network processor, having instructions stored therein that if executed perform operations comprising:
• extracting header data from a packet;
• identifying a set of partitioned recursive flow classification (RFC) data structures used to identify a rule for forwarding the packet defined in a rule database based on at least one header data value for which partitioning of the rule database is defined;
• performing a sequence of lookups via the set of RFC data structures to identify the rule to be employed for forwarding the packet.