Patent ID: 7646771

Claim:
A method of organizing classification tables for use in a packet classification algorithm in which incoming packets are matched with rules contained in access control data base, said method comprising the steps of: (A) constructing, by one or more processors of a network device, a set of top-level equivalence tables, each of which contains bit vectors identifying the rules specifying a value or values in a field in the packet headers, each table entry containing a unique bit vector and a equivalence ID specifying the bit vector; (B) constructing, by the one or more processors, a set of second-level of equivalence tables whose entries are indexed by a pair of equivalence ID's in a pair of top-leveled tables, each entry in the second level containing (1) a bit vector resulting from the intersection of the bit vectors in the corresponding top-level equivalence ID's, and (2) an equivalence ID specifying the bit vector; (C) constructing, by the one or more processors, a third-level set of equivalence tables whose entries are indexed by pairs of equivalence ID's in pairs of second-level tables, each entry in a third-level table containing (1) a bit vector resulting from the intersection of the bit vectors corresponding to the second-level equivalence ID's, and (2) an equivalence ID specifying the bit vector; (D) constructing, by the one or more processors, each of said third-level tables as a set of fragments, constructing a pointer array derived from the equivalence ID's in a second-level table, the contents of the pointer array pointing to the respective third-level table fragments, and the equivalence ID's of another of the second-level tables indicating depths of the entries in the table fragments; (E) recording a time when at least some tables of the set of top-level equivalence tables, second-level of equivalence tables or third-level equivalence tables were last rebuilt in order to classify a new type of packet; (F) accessing a minimum rebuild interval; and (C) timing a new rebuilding of the at least some tables to occur only after the minimum rebuild interval has elapsed since the last rebuild.