Granted Patent B1

US 7,392,349 · App. 11/045,575 · Granted Jun 24, 2008

Abstract

Claims (37)

1. A method of controlling a content addressable memory (CAM) device:

generating a data structure that specifies (i) a prioritized set of rules and (ii) addresses within the CAM device for one or more match clauses of each of the rules;

recording a new rule having a specified priority in the data structure;

identifying candidate addresses within the CAM device for the one or more match clauses of each of the rules having a lower priority than the new rule;

comparing the candidate addresses with the addresses specified by the data structure;

storing, in the CAM device, each of the match clauses for which the candidate address does not match the address specified by the data structure; and

wherein identifying candidate addresses for the match clauses of each of the rules having a lower priority than the new rule comprises allocating respective CAM addresses to the match clauses, including obtaining each of the CAM addresses from either (i) a list of CAM addresses that correspond to unoccupied storage locations within the CAM device or (ii) a record of CAM addresses that correspond to storage locations already occupied by the match clauses of the rules having a lower priority than the new rule.

2. The method of claim 1 wherein generating the data structure comprises executing programmed instructions in a host processor, including instructions to write the data structure to a memory device coupled to the host processor.

3. The method of claim 2 wherein the memory device is distinct from the CAM device.

4. The method of claim 1 wherein the data structure comprises a list of rules ordered by priority and wherein recording a new rule having a specified priority in the data structure comprises inserting the new rule into the list of rules ahead of rules of lower priority.

5. The method of claim 1 wherein obtaining each of the CAM addresses comprises comparing a CAM address from the list of CAM addresses with a CAM address from the record of CAM addresses to determine which of the CAM addresses has a higher priority.

6. The method of claim 5 wherein allocating respective CAM addresses to the match clauses comprises, for each of the match clauses, allocating either the CAM address from the list of CAM addresses or the CAM address from the record of CAM addresses according to which of the CAM addresses has the higher priority.

7. The method of claim 1 further comprising constructing the record of CAM addresses that correspond to occupied storage locations based on the data structure.

8. The method of claim 1 wherein the data structure comprises the record of CAM addresses that correspond to occupied storage locations.

9. The method of claim 1 further comprising identifying a respective candidate storage location for each match clause of the new rule.

10. The method of claim 9 further comprising writing each match clause of the new rule to the CAM device at its respective candidate storage location.

11. The method of claim 1 wherein storing, in the CAM device, each match clause for which the candidate storage location does not match the specified storage location comprises writing each such match clause to the CAM device at its respective candidate storage location.

12. The method of claim 11 wherein writing each such match clause to the CAM device comprises writing each such match clause of the lowest priority rule before writing any such match clause of a rule having a higher priority than the lowest priority rule.

13. A system comprising:

a content addressable memory (CAM) device;

a storage device to store a data structure that specifies (i) a prioritized set of rules and (ii) addresses within the CAM device for one or more match clauses of each of the rules; and

a host processor coupled to the CAM device and the storage device, the host processor being programmed with one or more sequences of instructions which, when executed by the host processor, cause the host processor to:

record a new rule having a specified priority in the data structure;

identify candidate addresses within the CAM device for the one or more match clauses of each of the rules having a lower priority than the new rule;

compare the candidate addresses with the storage addresses specified by the data structure; and

store, in the CAM device, each match clause for which the candidate address does not match the specified address; and

wherein the instructions which cause the host processor to identify candidate storage locations for the match clauses of each of the rules having a lower priority than the new rule comprise instructions which, when executed by the host processor, cause the host processor to allocate respective CAM addresses to the match clauses, including obtaining each of the CAM addresses from either (i) a list of CAM addresses that correspond to unoccupied storage locations within the CAM device or (ii) a record of CAM addresses that correspond to storage locations already occupied by the match clauses of the rules having a lower priority than the new rule.

14. The system of claim 13 wherein the instructions which cause the host processor to obtain each of the CAM addresses comprise instructions which, when executed by the host processor, cause the host processor to compare a CAM address from the list of CAM addresses with a CAM address from the record of CAM addresses to determine which of the CAM addresses has a higher priority.

15. The system of claim 14 wherein the instructions which cause the processor to allocate respective CAM addresses to the match clauses comprise instructions which, when executed by the host processor, cause the host processor to allocate, for each of the match clauses, either the CAM address from the list of CAM addresses or the CAM address from the record of CAM addresses according to which of the CAM addresses has the higher priority.

16. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by a processing entity, causes the processing entity to:

generate a data structure that specifies (i) a prioritized set of rules and (ii) addresses within the CAM device for one or more match clauses of each of the rules;

record a new rule having a specified priority in the data structure;

identify candidate addresses within the CAM device for the one or more match clauses of each of the rules having a lower priority than the new rule;

compare the candidate storage addresses with the addresses specified by the data structure;

store, in the CAM device, each match clause for which the candidate address does not match the specified address; and

wherein the instructions which cause the processing entity to identify candidate storage locations for the match clauses of each of the rules having a lower priority than the new rule comprise instructions which, when executed by the processing entity, cause the processing entity to allocate respective CAM addresses to the match clauses, including obtaining each of the CAM addresses from either (i) a list of CAM addresses that correspond to unoccupied storage locations within the CAM device or (ii) a record of CAM addresses that correspond to storage locations already occupied by the match clauses of the rules having a lower priority than the new rule.

17. The computer readable storage medium of claim 16 wherein the instructions which cause the processing entity to obtain each of the CAM addresses comprise instructions which, when executed by the processing entity, cause the processing entity to compare a CAM address from the list of CAM addresses with a CAM address from the record of CAM addresses to determine which of the CAM addresses has a higher priority.

Assignments (11)