# US 12,184,544 B1 · Data compression for LPM in TCAM

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

- Number: US 12,184,544 B1
- Document ID: US12184544B1
- Status: Granted
- Kind: B1
- Application number: 17/710,629
- Filed: 2022-03-31
- Granted: 2024-12-31
- Earliest claimed: 2021-03-31
- Assignees: DreamBig Semiconductor, Inc.
- Applicants: DreamBig Semiconductor Inc.
- Inventors: Sohail A Syed; Hillel Gazit; Hon Luu; Pranab Ghosh
- Web page: https://patentgrep.com/patent/US12184544B1

## CPC

- H03K 19/1776: for memories
- G06F 3/0604: {Improving or facilitating administration, e.g. storage management}
- G06F 3/0622: {in relation to access}
- G06F 3/0634: {by changing the state or mode of one or more devices}
- G06F 3/0656: {Data buffering arrangements}
- G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling}
- G06F 3/0664: {at device level, e.g. emulation of a storage device or system}
- G06F 3/0673: {Single storage device}
- G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]}
- G06F 9/45558: {Hypervisor-specific management and integration aspects}
- G06F 12/0646: {Configuration or reconfiguration}
- G06F 16/90339: {by using parallel associative memories or content-addressable memories}
- G11C 8/08: Word line control circuits, e.g. drivers, boosters, pull-up circuits, pull-down circuits, precharging circuits, for word lines
- G11C 15/04: using semiconductor elements
- H03K 5/2472: {using field effect transistors (H03K5/2436 takes precedence)}
- H03K 19/20: characterised by logic function, e.g. AND, OR, NOR, NOT circuits (H03K19/003 - H03K19/01 take precedence)
- H04L 45/42: Centralised routing
- H04L 45/586: of virtual routers
- H04L 45/745: Address table lookup; Address filtering
- H04L 63/0435: {wherein the sending and receiving network entities apply symmetric encryption, i.e. same key used for encryption and decryption (cryptographic mechanisms or cryptographic arrangements for symmetric key encryption H04L9/06)}
- G06F 11/1064: {in cache or content addressable memories}
- G06F 2009/45583: {Memory management, e.g. access or allocation}
- G06F 2212/251: Local memory within processor subsystem
- G06F 2212/401: Compressed data
- H03K: PULSE TECHNIQUE (measuring pulse characteristics G01R; modulating sinusoidal oscillations with pulses H03C; transmission of digital information H04L; discriminator circuits detecting phase difference between two signals by counting or integrating cycles of oscillation H03D3/04; automatic control, starting, synchronisation or stabilisation of generators of electronic oscillations or pulses where the type of generator is irrelevant or unspecified H03L; coding, decoding or code conversion, in general H03M)
- 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

a content addressable memory circuit is provided that includes a memory array that includes multiple memory devices that include memory locations that share a memory address and are coupled for simultaneous access. Hash logic is operative to use modulo math to determine a memory address based upon non-X values within an IP address key. Memory controller logic is operative to cause a memory device in the memory array to store the received IP address key in a memory location at the determined memory address, in a format that includes a field-size value indicative of a number of non-X values within a received IP address key and that includes non-X values within the received IP address key.

## Claims

### Claim 1

A content addressable memory circuit comprising:
an interface to receive an IP address key;
a random access memory device that includes a plurality of worldlines, each wordline operable to store multiple data bits and each wordline having a corresponding wordline address;
hash logic operative to use modulo math to determine a wordline address within the memory device, based upon non-X values within a received IP address key; and
memory controller logic to cause the memory device to store within the memory device at a wordline that corresponds to the determined wordline address, the non-X values within the received IP address key and a field-size value that indicates how many non-X values are within the received IP address key.

### Claim 2 (depends on 1)

The content addressable memory circuit of claim 1,
wherein the memory controller logic is operable to cause the memory device to store a priority value at the wordline that corresponds to the determined wordline address.

### Claim 3 (depends on 1)

The content addressable memory circuit of claim 1 further including
a storage device operable for use as a dynamic hash table;
wherein the memory controller logic is operable to cause the storage device to store a virtual routing function value that corresponds to the received IP address key.

### Claim 4 (depends on 1)

The content addressable memory circuit of claim 1,
wherein the hash logic is operative to use modulo math to determine a wordline address within the memory device, based upon the non-X values within a received IP address key and a modulus based upon a number of memory locations within the memory array.

### Claim 5

A method to store an IP address key in a memory array that includes multiple memory devices that include memory locations that share a common address and are coupled for simultaneous access, the method comprising:
using modulo math to determine a memory address within the memory array based upon non-X values within the IP address key and a modulus based upon a number of memory locations within the memory array; and
storing non-X values of the IP address key in a memory location at the determined memory address, in a format that includes a field-size value indicative of a number of non-X values within the IP address key.

### Claim 6 (depends on 5)

The method of claim 5,
wherein the format includes no X-values of the IP address key.

### Claim 7 (depends on 5)

The method of claim 5 further including:
storing a priority value in the memory location with the IP address key at the determined memory address.

### Claim 8 (depends on 5)

The method of claim 5 further including:
storing a virtual routing function value that corresponds to the IP address key in a storage device that is operable for use as a dynamic hash table.

### Claim 9 (depends on 5)

The method of claim 5,
wherein using modulo math includes using modulo math to determine a memory address within the memory array based upon non-X values within the IP address key and a modulus based upon a number of memory locations within the memory array.

### Claim 10

A content addressable memory circuit comprising:
an interface to receive an IP address key;
a memory array that includes multiple respective memory devices that include memory locations that share a common address and are coupled for simultaneous access;
hash logic operative to use modulo math to determine a shared common memory address within the memory array based upon non-X values within a received IP address key;
wherein a plurality of memory locations within memory devices of the memory array each stores non-X values of a different IP address key in a format that includes a field-size value indicative of how many non-X IP values are stored at the memory location;
multiple respective selector logic circuits, each operatively coupled to receive a field-size value output from a corresponding memory device;
multiple respective comparator circuits, each operatively coupled to a receive non-X address key values output from a corresponding memory device; and
memory control logic operative during a read operation in response to the received IP address key, to cause multiple respective memory devices to output stored field-size values and non-X IP address key values from memory locations at the determined shared common memory address;
wherein each selector logic circuit is operative in response to the read operation to determine a respective number of non-X value comparisons that a corresponding comparator circuit is to make based upon a respective field size value output from a corresponding memory device; and
wherein each comparator circuit is operative in response to the read operation to compare the determined respective number of non-X values in the received IP address key with non-X values output from a corresponding memory device and to provide a respective comparison result.

### Claim 11 (depends on 10)

The content addressable memory circuit of claim 10,
wherein the format includes no X-values.

### Claim 12 (depends on 10)

The content addressable memory circuit of claim 10,
wherein the memory locations that share a memory address include wordlines that that share a wordline address.

### Claim 13 (depends on 10)

The content addressable memory circuit of claim 10,
wherein the plurality of memory locations within memory devices of the memory array store priority with the field-size values and non-X IP address key values.

### Claim 14 (depends on 10)

The content addressable memory circuit of claim 10,
wherein the memory control logic is operative during a read operation in response to the received IP address key, to cause multiple respective memory devices to simultaneously output stored field-size values and non-X IP address key values from memory locations at the determined shared common memory address.

### Claim 15 (depends on 10)

The content addressable memory circuit of claim 10,
wherein each comparator circuit is operative during the read operation to compare the determined respective number of non-X values in the received IP address key with a corresponding number of non-X values output from a corresponding memory device in parallel and to provide a respective comparison result.

### Claim 16 (depends on 10)

The content addressable memory circuit of claim 10,
wherein the hash logic is operative to use modulo math to determine a shared common memory address within the memory array based upon non-X values within a received IP address key and a modulus based upon a number of memory locations within the memory array.

### Claim 17

A method to control a content addressable memory circuit that includes a memory array that includes multiple respective memory devices that include memory locations that share a common address and are coupled for simultaneous access, the method comprising:
receiving an IP address key;
using modulo math to determine a shared common memory address within the memory array based upon non-X values within a received IP address key and a modulus based upon a number of memory locations within the memory array;
storing non-X values of different IP address keys at different memory locations in a format that includes at each different memory location a field-size value indicative of how many non-X values are stored at the different memory location;
outputting stored field-size values and non-X IP address key values from memory locations in the memory array at the determined shared common memory address;
for each memory address location that outputs a stored field-size value and non-X IP address key values, determining a respective number of non-X IP address key values of the received IP address key to compare based upon the outputted field size value; and
for each memory address location that outputs a stored field-size value and non-X IP address key values, comparing the determined respective number of non-X IP address key values of the received IP address key with the outputted non-X IP address key value, and providing respective a comparison result.

### Claim 18

The method of 17,
wherein outputting includes simultaneously outputting stored field-size values and non-X IP address key values from memory locations in the memory array at the determined shared common memory address.

### Claim 19

The method of 17,
wherein comparing includes comparing, in parallel, the determined respective number of non-X IP address key values of the received IP address key with the outputted non-X IP address key value and providing a comparison result.

### Claim 20 (depends on 17)

The method of claim 17, wherein using modulo math includes using modulo math to determine a shared common memory address within the memory array based upon non-X values within a received IP address key and a modulus based upon a number of memory locations within the memory array.

### Claim 21

A content addressable memory circuit comprising:
an interface to receive IP address keys for use with a write operation or for use with a read operation;
multiple random access memory devices that each includes a plurality of worldlines, each wordline of each random access memory device operable to store multiple data bits, wherein each wordline of each random access memory device corresponds to at least one wordline of each of the other random access memory devices, and wherein corresponding wordlines of different random access devices have shared wordline addresses and are coupled to permit simultaneous access;
hash logic operative to use modulo math to determine shared wordline addresses within the random access memory devices, based upon non-X values within the received IP address keys;
memory controller logic;
wherein the memory controller logic is operative during a write operation to cause a random access memory device, from among the multiple random access memory devices, to store at a wordline having a shared address determined for an IP address key received for use with the write operation, non-X values of the IP address key received for use with the write operation and a corresponding field-size value that indicates how many non-X values are within the IP address key received for use with the write operation; and
wherein the memory controller logic is operative during a read operation to cause each respective random access memory device, that stores respective non-X values of a respective IP address key previously received for use with the write operation and that stores a corresponding respective field size value at a respective wordline of the respective random access memory device having a shared memory address determined for an IP address key received for use with the read operation, to output the stored respective non-X values and the stored corresponding respective field size value from the respective wordline of the respective random access memory device having the shared memory address determined for the IP address key received at the interface for use with the read operation.

### Claim 22 (depends on 21)

The content addressable memory circuit of claim 21,
wherein the hash logic operative to use modulo math to determine shared wordline addresses within the random access memory devices, based upon non-X values within the received IP address keys and a modulus based upon a number of memory locations within the memory array.

### Claim 23 (depends on 21)

The content addressable memory circuit of claim 21, further including:
multiple respective selector logic circuits, each operatively coupled to receive a field-size value output from a corresponding random access memory device during an occurrence of the read operation of the memory controller logic; and
multiple respective comparator circuits, each operatively coupled to a receive non-X address key values output from a corresponding random access memory device during the occurrence of the read operation of the memory controller logic;
wherein each selector logic circuit is operative in response to the occurrence of the read operation to determine a respective number of non-X value comparisons that a corresponding comparator circuit is to make based upon a respective field size value output from a corresponding random access memory device; and
wherein each comparator circuit is operative in response to the occurrence of the read operation to compare the determined respective number of non-X values, in the IP address key received for use with the occurrence of the read operation, with non-X values output from a corresponding random access memory device and to provide a respective comparison result.

### Claim 24

A method to access an IP address key in a memory array that includes multiple memory devices that each includes a plurality of memory locations, wherein each memory location has a memory address, and wherein corresponding memory locations of different memory devices have shared memory addresses and are coupled to permit simultaneous access, the method comprising:
receiving one or more IP address keys at an interface for use with a write operation or with a read operation;
using modulo math to determine shared memory addresses within the memory array, based upon non-X values within the IP address keys;
during a write operation of the memory array, storing non-x values of an IP address key received for use with the write operation in a memory device, from among the multiple memory devices, at a memory location having a shared memory address determined for the IP address key received for use in the write operation, in a format that includes a corresponding field-size value indicative of a number of non-X values within the IP address key received for use in the write operation; and
during a read operation of the memory array, causing memory devices from the memory array, that store non-X values of IP address keys previously received for use with the write operation and corresponding field size values at memory locations having a shared memory address determined for an IP address key received at the interface for use with the read operation, to output the stored non-X values of IP address keys and the stored corresponding field size values from memory locations having the shared memory address determined for the IP address key received at the interface for use with the read operation.

### Claim 25 (depends on 24)

The method of claim 24,
wherein using modulo math includes using modulo math to determine shared memory addresses within the memory array, based upon non-X values within the IP address keys and a modulus based upon a number of memory locations within the memory array.

### Claim 26 (depends on 24)

The method of claim 24, further including:
for each respective memory address location that outputs non-X IP address key values and a stored corresponding field-size value, determining a respective number of non-X IP address key values of the IP address key received for use with the read operation to compare based upon the outputted field size value; and
for each respective memory address location that outputs respective non-X IP address key values and a respective stored corresponding field-size value, comparing the determined respective number of non-X IP address key values of the IP address key received for use with the read operation with the outputted respective non-X IP address key value, and providing respective a comparison result.