Compilation of access control lists
First Claim
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, 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.
1 Assignment
0 Petitions
Accused Products
Abstract
An improvement in the compilation of classification tables from across control lists increases the efficiency of memory utilization by fragments in the lower level tables and using the classification ID'"'"'s from a pair of higher-level tables as pointers to the fragments and as indicators of the depth of the entries in the fragments. A further improvement makes use of aggregate bit vectors, thereby simplifying construction of the lower-level tables. The bit-vector sections preferably coincide with the cache lines of the processing, thereby maximizing the speed with which the relevant bits in the bit vector can be identified from the aggregate bit vectors.
-
Citations
26 Claims
-
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, 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. - View Dependent Claims (2, 3, 4, 5)
-
-
6. An apparatus for organizing classification tables for use in a packet classification algorithm in which incoming packets are matched with rules contained in an access control database, said apparatus comprising:
-
(A) means for 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 an equivalence ID specifying the bit vector; (B) means for constructing 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 resultant 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 resultant bit vector; (C) means for 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 (1) a next resultant bit vector resulting in from the intersection of the bit vectors corresponding to the second-level equivalence ID'"'"'s, and (2) an equivalence ID specifying the next resultant bit vector; and (D) means for; (1) constructing each of said third-level tables as a set of fragments, (2) 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. - View Dependent Claims (7, 8)
-
-
9. A method comprising:
-
constructing, by one or more processors of a network device, a set of top-level tables associated with a top-level in a hierarchy of tables for use in a packet classification of incoming packets, each top-level table containing one or more top-level table entries, each top-level table entry associating a value, or values, of a section of a packet header with an equivalence-set index and a bit vector indicating one or more rules for classifying the incoming packets; constructing, by the one or more processors, one or more successive-level tables associated with a successive-level in the hierarchy of tables, at least some of the one or more successive-level tables arranged as a set of table fragments; recording a time at least some the tables in the hierarchy of tables were last rebuilt; accessing a minimum rebuild interval; and rebuilding, by the one or more processors, the at least some the tables in the hierarchy of tables only after the minimum rebuild interval has elapsed after the time the at least some of the tables in the hierarchy of tables were last rebuilt. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. An apparatus comprising:
-
a processor to construct a set of top-level tables associated with a top-level in a hierarchy of tables for use in a packet classification of incoming packets, each top-level table containing one or more top-level table entries, each top-level table entry arranged to associate a value, or values, of a section of a packet header with an equivalence-set index and a bit vector that indicates one or more rules for classifying the incoming packets, the processor further to construct one or more successive-level tables associated with a successive-level in the hierarchy of tables, at least some of the one or more successive-level tables arranged as a set of table fragments; and a memory to hold the hierarchy of tables, wherein the processor is further to record a time at least some the tables in the hierarchy of tables were last rebuilt, access a minimum rebuild interval, and rebuild the at least some the tables in the hierarchy of tables only after the minimum rebuild interval has elapsed after the time the at least some of the tables in the hierarchy of tables were last rebuilt. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26)
-
Specification