# US 2019/0317671 A1 · Coordinated Updating and Searching a Content-Addressable Memory Including for Packet Processing Operations

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0317671 A1
- Document ID: US20190317671A1
- Status: Published application
- Kind: A1
- Application number: 15/954,518
- Filed: 2018-04-16
- Published: 2019-10-17
- Earliest claimed: 2018-04-16
- Assignees: Cisco Technology, Inc., a corporation of California
- Applicants: Cisco Technology, Inc.
- Inventors: Doron Shoham; Gilad Hazan
- Web page: https://patentgrep.com/patent/US20190317671A1

## CPC

- G06F 3/0613: {in relation to throughput}
- G06F 3/0646: {Horizontal data movement in storage systems, i.e. moving data in between storage devices or systems}
- G06F 3/0685: {Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays}
- 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
- H04L 2012/5638: {Services, e.g. multimedia, GOS, QOS}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G11C: STATIC STORES (semiconductor memory devices H10B)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

In one embodiment, updating and searching of entries in a hardware content-addressable memory is coordinated to provide more searching bandwidth (e.g., for determining packet processing information), including, but not limited to, when vectors are moved among entries to free up desired entry positions for insertion of other vectors. A lookup operation in performed in content-addressable memory entries in a hardware content-addressable memory based on a lookup word to generate a content-addressable memory lookup result. Typically overlapping in time, a matching operation is performed in one or more transitory entries to generate a transitory matching result based on the lookup word. These transitory entries are populated with transitory vectors and have an associated index within the content-addressable memory, with these transitory vectors are subsequently inserted in the content-addressable memory at their associated index positions. A matching result is determined from the content-addressable memory lookup result and the transitory matching result.

## Claims

### Claim 1

A method, comprising:
performing a lookup operation in a plurality of content-addressable memory entries in a hardware content-addressable memory based on a lookup word to generate a content-addressable memory lookup result;
performing a matching operation in one or more transitory entries to generate a transitory matching result based on the lookup word, with each of said transitory entries populated with a corresponding transitory vector and having an associated insertion position in the hardware content-addressable memory;
determining a matching result based on the content-addressable memory lookup result and the transitory matching result; and
subsequently to performing the matching operation and for each particular transitory entry of said transitory entries, populating an insertion position entry of the hardware content-addressable memory identified based on said associated insertion position of said particular transitory entry with the corresponding transitory vector of said particular transitory entry.

### Claim 2 (depends on 1)

The method of claim 1, comprising:
retrieving a lookup result based on the matching result from a result database; and
processing a packet based on the lookup result.

### Claim 3 (depends on 2)

The method of claim 2, wherein the matching result is the associated insertion position of said transitory entry identified by the transitory matching result.

### Claim 4 (depends on 1)

The method of claim 1, comprising determining a lookup result based on the matching result from a result database.

### Claim 5 (depends on 1)

The method of claim 1, wherein said performing the lookup operation and performing the matching operation are performed overlapping in time.

### Claim 6 (depends on 1)

The method of claim 1, comprising for each particular source entry of one or more source content-addressable memory entries, moving a programmed vector populated in the particular source entry to a different position within the hardware content-addressable memory; and
wherein said source content-addressable memory entries include the associated position of each of said one or more transitory entries.

### Claim 7 (depends on 6)

The method of claim 6, wherein a content-addressable memory direct memory access (DMA) controller performs said moving the programmed vector for each of said source content-addressable memory entries.

### Claim 8 (depends on 7)

The method of claim 7, wherein the content-addressable memory DMA controller includes said one or more transitory entries, and the content-addressable memory DMA controller said performs the matching operation.

### Claim 9 (depends on 8)

The method of claim 8, comprising: in response to the content-addressable memory result said generated by the matching operation identifies a particular not yet moved entry of said source content-addressable memory entries, adjusting the content-addressable memory result to reflect the different position corresponding to the particular not yet moved entry prior to said determining the matching index.

### Claim 10 (depends on 6)

The method of claim 6, comprising: in response to the content-addressable memory result said generated by the matching operation identifies a particular not yet moved entry of said source content-addressable memory entries, adjusting the content-addressable memory result to reflect the different position corresponding to the particular not yet moved entry prior to said determining the matching index.

### Claim 11 (depends on 6)

The method of claim 6, wherein the programmed vector of each of said source content-addressable memory entries includes a data value and a mask value for masking the data value.

### Claim 12 (depends on 1)

The method of claim 1, wherein a content-addressable memory direct memory access (DMA) controller includes said one or more transitory entries; and wherein the content-addressable memory DMA controller said performs the matching operation.

### Claim 13 (depends on 12)

The method of claim 12, wherein said one or more transitory entries is a single transitory entry.

### Claim 14 (depends on 13)

The method of claim 13, wherein a control status register of the DMA includes the transitory entry; and wherein the DMA includes memory storing the transitory matching result.

### Claim 15 (depends on 1)

The method of claim 1, wherein the hardware content-addressable memory is a ternary content-addressable memory.

### Claim 16

An apparatus, comprising:
a content-addressable memory controller;
a content-addressable memory direct memory access (DMA) controller including one or more transitory entries;
a content-addressable memory including a plurality of content-addressable memory entries; and
a memory storing a result database;
wherein the content-addressable memory controller is communicatively coupled with the content-addressable DMA controller including to provide a lookup word, a transitory vector with a corresponding position index within the content-addressable memory where the transitory vector is to be added, and a move instruction, and including to receive a transitory matching result based on a comparison of the lookup word with the transitory value;
wherein the content-addressable memory controller is communicatively coupled with the content-addressable memory including to provide the lookup word, and including to receive a content-addressable memory lookup result of a lookup operation performed based on the lookup word;
wherein the content-addressable memory controller is communicatively coupled with the memory including to provide a matching result that is a higher-priority of the transitory matching result and the content-addressable memory lookup result, and including to receive a lookup result retrieved from the result database at a position corresponding to the content-addressable memory lookup result;
wherein the content-addressable memory DMA controller is communicatively coupled with the content-addressable memory controller to receive the lookup word, the transitory vector with the corresponding position index within the content-addressable memory where the transitory vector is to be added, and the move instruction, and including to provide the transitory matching result based on a comparison made by the content-addressable memory DMA controller;
wherein the content-addressable memory is communicatively coupled with the content-addressable memory controller including to receive the lookup word, and including to provide the content-addressable memory lookup result of the lookup operation performed based on the lookup word by the content-addressable memory; and
wherein the memory is communicatively coupled with the content-addressable memory controller including to receive the matching result, and including to provide the lookup result retrieved by the memory from the result database at the position corresponding to the content-addressable memory lookup result.

### Claim 17 (depends on 16)

The apparatus of claim 16, wherein the content-addressable DMA controller is communicatively coupled with the content-addressable memory including to receive the move instruction to move content-addressable memory vectors among the plurality of content-addressable memory entries including to free up a particular content-addressable memory entry at the corresponding position index, and to store the transitory vector in the particular content-addressable memory entry.

### Claim 18 (depends on 16)

The apparatus of claim 16, wherein the content-addressable memory controller is communicatively coupled with the content-addressable DMA controller including to receive progress of performing the move instruction to adjust the content-addressable memory lookup result to a moved entry position in response a specific content-addressable memory entry identified by the content-addressable memory lookup result being identified by the move instruction to be moved to the moved position which has not yet been performed.

### Claim 19

A method, comprising:
performing a lookup operation in a plurality of content-addressable memory entries in a hardware content-addressable memory based on a lookup word to generate a content-addressable memory lookup result identifying a source entry of the plurality of content-addressable memory entries and associated with a source search space priority, and adjusting the content-addressable memory lookup result to a destination search space priority of a destination entry of the plurality of content-addressable memory entries to which a particular content-addressable memory vector currently stored in source entry is to be moved;
performing a matching operation in a transitory entry to generate a transitory matching result based on the lookup word that matches the lookup word, with the transitory entry populated according to a transitory vector and having an insertion-entry search space priority of an insertion entry of the plurality of content-addressable memory entries to which the transitory vector is to be subsequently inserted;
after said adjusting the content-addressable memory lookup result, determining a lookup result to be the destination search space priority based on the content-addressable memory lookup result of the destination search space priority being a higher-priority than the insertion-entry search space priority; and
after said performing the matching operation, populating the insertion entry of the plurality of content-addressable memory entries with the transitory entry.

### Claim 20 (depends on 19)

The method of claim 19, comprising updating the hardware content-addressable memory so that the particular content-addressable memory vector is a searchable vector in the destination entry but not in source entry.
