Techniques for efficient location of free entries for TCAM inserts

• US 6,516,383 B1
• Filed: 05/30/2001
• Issued: 02/04/2003
• Est. Priority Date: 05/30/2001
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Patra, Abhijit, Sharma, Samar, Panigrahy, Rina
• Primary Examiner(s): Yoo, Do Hyun
• Assistant Examiner(s): MOAZZAMI, NASSER G
• Application Number:
  US09/871,321
• Time in Patent Office: 615 Days
• Field of Search: 711/108, 380/28, 365/49
• US Class Current: 711/108
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores

Abstract

Techniques for the efficient location of free entries for use in performing insert operations in a binary or ternary content addressable memory. As used in data communications and packet routing, such memories often rely on an organization that maintains entries of the same “length” within defined regions. The present invention keeps the free entries (holes) compacted into a contiguous subregion within each region, without requiring hole movement during deletes. These positive effects are accomplished by initially pre-filling the entire memory with a set of hole codes that each uniquely identify the holes in each region. A conventional memory write is then performed to load routing data into the memory. Typically, such routing information will not fill the entire memory, leaving unused entries (containing the region appropriate hole code) in each region. As entries need to be deleted, they are simply replaced by writing in the region-unique hole code. To insert an entry, the host processor searches for the desired region-unique hole and writes the data to its location. In instances where a region has no available holes, a mechanism is presented to move a hole from a nearby region.

Claims

1. A method of memory management comprising:

dividing a memory into a plurality of contiguous regions, each said region composed of a plurality of entries;

initializing each entry in each said region to a region-unique hole code; and

when commanded;

deleting one of said plurality of entries by overwriting said entry with said region-unique hole code;

or

inserting data into one of said plurality of entries, wherein said inserting further comprises;

if a first region containing said entry in which said data is to be inserted lacks an entry containing said region-unique hole code, expanding said first region by moving an entry containing said region-unique hole code from another of said plurality of regions and resetting said region-unique hole code to the hole code appropriate to said first region; and

overwriting the entry containing said region-unique hole code with said data.

2. The method of claim 1, wherein said memory comprises a content addressable memory (CAM).

3. The method of claim 1, wherein said memory comprises a ternary content addressable memory (TCAM).

4. The method of claim 1, wherein said expanding further comprises:

identifying a nearest one of said plurality of regions (the “

nearest region”

) containing an entry having stored therein a region-unique hole code (the “

nearest hole”

);

moving said nearest hole into said first region by iteratively;

copying the contents of the entry at the region boundary of said nearest region (hereinafter the “

boundary entry”

) into said nearest hole;

moving the region boundary of said nearest region away from said first region;

writing into the boundary entry the hole code of the next closer region to said first region;

until said boundary entry is within said first region.

5. A computer system for memory management, comprising computer instructions for:

dividing a memory into a plurality of contiguous regions, each said region composed of a plurality of entries;

initializing each entry in each said region to a region-unique hole code; and

when commanded;

deleting one of said plurality of entries by overwriting said entry with said region-unique hole code;

or

inserting data into one of said plurality of entries, wherein said inserting further comprises;

if a first region containing said entry in which said data is to be inserted lacks an entry containing said region-unique hole code, expanding said first region by moving an entry containing said region-unique hole code from another of said plurality of regions and resetting said region-unique hole code to the hole code appropriate to said first region; and

overwriting the entry containing said region-unique hole code with said data.

6. The computer system of claim 5, wherein said memory comprises a content addressable memory (CAM).

7. The computer system of claim 5, wherein said memory comprises a ternary content addressable memory (TCAM).

8. The computer system of claim 5, wherein said expanding further comprises:

identifying a nearest one of said plurality of regions (the “

nearest region”

) containing an entry having stored therein a region-unique hole code (the “

nearest hole”

);

moving said nearest hole into said first region by iteratively;

copying the contents of the entry at the region boundary of said nearest region (hereinafter the “

boundary entry”

) into said nearest hole;

moving the region boundary of said nearest region away from said first region;

writing into the boundary entry the hole code of the next closer region to said first region;

until said boundary entry is within said first region.

9. A computer system comprising a processor, a memory, and a network interface, said processor configured to perform the steps of:

dividing a memory into a plurality of contiguous regions, each said region composed of a plurality of entries;

initializing each entry in each said region to a region-unique hole code; and

when commanded;

deleting one of said plurality of entries by overwriting said entry with said region-unique hole code;

or

inserting data into one of said plurality of entries, wherein said inserting further comprises;

if a first region containing said entry in which said data is to be inserted lacks an entry containing said region-unique hole code, expanding said first region by moving an entry containing said region-unique hole code from another of said plurality of regions and resetting said region-unique hole code to the hole code appropriate to said first region; and

overwriting the entry containing said region-unique hole code with said data.

10. The computer system of claim 9, wherein said memory comprises a content addressable memory (CAM).

11. The computer system of claim 9, wherein said memory comprises a ternary content addressable memory (TCAM).

12. The computer system of claim 9, wherein said expanding further comprises:

identifying a nearest one of said plurality of regions (the “

nearest region”

) containing an entry having stored therein a region-unique hole code (the “

nearest hole”

);

moving said nearest hole into said first region by iteratively;

copying the contents of the entry at the region boundary of said nearest region (hereinafter the “

boundary entry”

) into said nearest hole;

moving the region boundary of said nearest region away from said first region;

writing into the boundary entry the hole code of the next closer region to said first region;

until said boundary entry is within said first region.

13. A computer-readable storage medium, comprising computer instructions for:

dividing a memory into a plurality of contiguous regions, each said region composed of a plurality of entries;

initializing each entry in each said region to a region-unique hole code; and

when commanded;

deleting one of said plurality of entries by overwriting said entry with said region-unique hole code;

or

inserting data into one of said plurality of entries, wherein said inserting further comprises;

if a first region containing said entry in which said data is to be inserted lacks an entry containing said region-unique hole code, expanding said first region by moving an entry containing said region-unique hole code from another of said plurality of regions and resetting said region-unique hole code to the hole code appropriate to said first region; and

overwriting the entry containing said region-unique hole code with said data.

14. The computer-readable storage medium of claim 13, wherein said memory comprises a content addressable memory (CAM).

15. The computer-readable storage medium of claim 13, wherein said memory comprises a ternary content addressable memory (TCAM).

16. The computer-readable storage medium of claim 13, wherein said expanding further comprises:

identifying a nearest one of said plurality of regions (the “

nearest region”

) containing an entry having stored therein a region-unique hole code (the “

nearest hole”

);

moving said nearest hole into said first region by iteratively;

copying the contents of the entry at the region boundary of said nearest region (hereinafter the “

boundary entry”

) into said nearest hole;

moving the region boundary of said nearest region away from said first region;

writing into the boundary entry the hole code of the next closer region to said first region;

until said boundary entry is within said first region.

17. A computer data signal embodied in a carrier wave, comprising computer instructions for:

dividing a memory into a plurality of contiguous regions, each said region composed of a plurality of entries;

initializing each entry in each said region to a region-unique hole code; and

when commanded;

deleting one of said plurality of entries by overwriting said entry with said region-unique hole code;

or

inserting data into one of said plurality of entries, wherein said inserting further comprises;

if a first region containing said entry in which said data is to be inserted lacks an entry containing said region-unique hole code, expanding said first region by moving an entry containing said region-unique hole code from another of said plurality of regions and resetting said region-unique hole code to the hole code appropriate to said first region; and

overwriting the entry containing said region-unique hole code with said data.

18. The computer data signal of claim 17, wherein said memory comprises a content addressable memory (CAM).

19. The computer data signal of claim 17, wherein said memory comprises a ternary content addressable memory (TCAM).

20. The computer data signal of claim 17, wherein said expanding further comprises:

identifying a nearest one of said plurality of regions (the “

nearest region”

) containing an entry having stored therein a region-unique hole code (the “

nearest hole”

);

moving said nearest hole into said first region by iteratively;

copying the contents of the entry at the region boundary of said nearest region (hereinafter the “

boundary entry”

) into said nearest hole;

moving the region boundary of said nearest region away from said first region;

writing into the boundary entry the hole code of the next closer region to said first region;

until said boundary entry is within said first region.

21. A computer system for memory management, comprising:

means for dividing a memory into a plurality of contiguous regions, each said region composed of a plurality of entries;

means for initializing each entry in each said region to a region-unique hole code; and

when commanded;

means for deleting one of said plurality of entries by overwriting said entry with said region-unique hole code;

or

means for inserting data into one of said plurality of entries, wherein said inserting further comprises;

if a first region containing said entry in which said data is to be inserted lacks an entry containing said region-unique hole code, means for expanding said first region by moving an entry containing said region-unique hole code from another of said plurality of regions and resetting said region-unique hole code to the hole code appropriate to said first region; and

means for overwriting the entry containing said region-unique hole code with said data.

22. The computer system of claim 21, wherein said memory comprises a content addressable memory (CAM).

23. The computer system of claim 21, wherein said memory comprises a ternary content addressable memory (TCAM).

24. The computer system of claim 21, wherein said means for expanding further comprises:

means for identifying a nearest one of said plurality of regions (the “

nearest region”

) containing an entry having stored therein a region-unique hole code (the “

nearest hole”

);

means for moving said nearest hole into said first region by iteratively;

copying the contents of the entry at the region boundary of said nearest region (hereinafter the “

boundary entry”

) into said nearest hole;

moving the region boundary of said nearest region away from said first region;

writing into the boundary entry the hole code of the next closer region to said first region;

until said boundary entry is within said first region.