Patent ID: 7325074
Filing Date: 2008-01-29
Classification: H04L

Abstract:
1. 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 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 a 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 (C) constructing 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 (D) constructing each of said third-level tables as a set of table 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, the equivalence ID's of the other of the second-level tables indicating the depths of the entries in the table fragments.