Granted Patent B1

US 7,904,642 · App. 11/935,286 · Granted Mar 8, 2011

Abstract

Claims (52)

1. A method of storing in a database a plurality of rules associated with one or more access control lists (ACLs), the method comprising:

providing the plurality of rules, wherein each rule includes a number of packet header fields each containing a corresponding entry;

selectively combining the plurality of rules into one or more groups depending upon similarities between the entries within each field; and

storing the groups in the database including a content addressable memory (CAM) device and a random access memory (RAM), wherein the storing comprises:

for each rule field, storing only one instance of each of its corresponding field values in the CAM device so that each field value stored in the CAM device is unique;

for each field value stored in the CAM device, storing a field label in the RAM device, wherein each field label indicates which groups the corresponding field value belongs to;

for each group, storing a concatenation of the field labels belonging to the group as a group label in the CAM device; and

for each group label stored in the CAM device, storing a group identification (ID) in the RAM device.

2. The method of claim 1 , wherein the selectively combining comprises:

(1) selecting a first rule as a reference rule;

(2) selecting a next rule as a target rule;

(3) for each of the rule fields, comparing the entries of the reference and target rules; and

(4) combining the reference and target rules into a group if their entries are different in only one field.

3. The method of claim 2 , wherein the selectively combining further comprises:

(5) selecting a next rule as the target rule;

(6) for each of the rule fields, comparing the entries of the group and the target rule;

(7) combining the target rule into the group if their entries are different in only one field; and

(8) creating a new group to include the target rule if their entries are different in more than one field.

4. The method of claim 1 , further comprising:

repeating steps (1)-(8) until each remaining group differs in more than one field entry.

5. The method of claim 2 , further comprising:

selectively eliminating one or more rules from storage in the CAM device.

6. The method of claim 5 , wherein the selectively eliminating comprises:

for each group, assigning a label to each set of unique field values;

selecting one of the fields; and

for each value in the selected field, if the value is unique and non-overlapping with other values in the selected field, removing the corresponding rule from the CAM device and storing a pointer in the RAM device.

7. A computer system configured to store a plurality of rules associated with one or more access control lists (ACLs), the computer system comprising:

means for providing the plurality of rules, wherein each rule includes a number of packet header fields each containing a corresponding entry;

means for selectively combining the plurality of rules into one or more groups depending upon similarities between the entries within each field; and

means for storing the groups in a database including a content addressable memory (CAM) device and a random access memory (RAM), wherein the means for storing is configured to:

for each rule field, store only one instance of each of its corresponding field values in the CAM device so that each field value stored in the CAM device is unique;

for each field value stored in the CAM device, store a field label in the RAM device, wherein each field label indicates which groups the corresponding field value belongs to;

for each group, store a concatenation of the field labels belonging to the group as a group label in the CAM device; and

for each group label stored in the CAM device, store a group identification (ID) in the RAM device.

8. The computer system of claim 7 , wherein the means for selectively combining is configured to:

(1) select a first rule as a reference rule;

(2) select a next rule as a target rule;

(3) for each of the rule fields, compare the entries of the reference and target rules; and

(4) combine the reference and target rules into a group if their entries are different in only one field.

9. The computer system of claim 8 , wherein the means for selectively combining is further configured to:

(5) select a next rule as the target rule;

(6) for each of the rule fields, compare the entries of the group and the target rule;

(7) combine the target rule into the group if their entries are different in only one field; and

(8) create a new group to include the target rule if their entries are different in more than one field.

10. The computer system of claim 9 , further comprising:

means for repeating steps (1)-(8) until each remaining group differs in more than one field entry.

11. The computer system of claim 8 , further comprising:

means for selectively eliminating one or more rules from storage in the CAM device.

12. The computer system of claim 11 , wherein the means for selectively eliminating is configured to:

for each group, assign a label to each set of unique field values;

select one of the fields; and

for each value in the selected field, if the value is unique and non-overlapping with other values in the selected field, remove the corresponding rule from the CAM device and storing a pointer in the RAM device.

Assignments (9)