Patent ID: 7688761

Claim:
A method for improving packet classification in a network device, the method comprising: performing single dimensional lookups for each header field based on a plurality of packet-classification rules, by a network device, wherein performing the single dimensional lookups comprises obtaining a Bit Vector (BV) for each header field; merging results from the single dimensional lookups and merging a plurality of equivalence classes to obtain a Resultant Bit Vector (RBV); processing the RBV based on the plurality of packet-classification rules to determine a packet classification; dividing each bit vector in each equivalence class into sections; representing each section by a bit in an Aggregate Bit Vector (ABV); assigning a non-zero bit in the ABV corresponding to the section, if a value of at least one bit in the section is not zero; assigning a zero bit in the ABV corresponding to the section, if a value of each bit in the section is zero; performing a logical OR operation on ABV corresponding to each equivalence class to obtain a Resultant Aggregate Bit Vector (RABV); determining a section of the RBV by logically ORing corresponding sections of equivalence classes, if a value of a bit of the RABV corresponding to the section is not zero; and assigning zeros to the section of the RBV, if a value of the bit of the RABV corresponding to the section is zero.