# US 2019/0379770 A1 · Directed graph traversal using content-addressable memory

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

- Number: US 2019/0379770 A1
- Document ID: US20190379770A1
- Status: Published application
- Kind: A1
- Application number: 16/434,983
- Filed: 2019-06-07
- Published: 2019-12-12
- Earliest claimed: 2018-06-08
- Assignees: Fungible, Inc.
- Applicants: Fungible, Inc.
- Inventors: Hariharan Lakshminarayanan Thantry; Rohit Sunkam Ramanujam; John David Huber; Deepak Goel; Vikas Minglani
- Web page: https://patentgrep.com/patent/US20190379770A1

## CPC

- H04L 69/22: Parsing or analysis of headers
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 16/903: Querying (for retrieval from the web G06F16/953)
- G06F 16/90339: {by using parallel associative memories or content-addressable memories}
- G06N 5/025: Extracting rules from data
- H04L 45/74591: {using content-addressable memories [CAM]}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

This disclosure describes techniques that include representing, traversing, and processing directed graphs using one or more content-addressable memory devices. In one example, this disclosure describes a method that includes presenting query data to one or more ternary content-addressable memory (TCAM) devices, wherein the query data includes state data and key data; receiving, from the TCAM devices, information about a matching address identified by the TCAM devices; accessing, based on the information about the matching address, information in one or more storage devices; performing, based on the information in the one or more storage devices, at least one operation on data included within the one or more storage devices to generate processed data; outputting the processed data; determining, based on the information in the one or more storage devices, new state data and a new key value; and presenting new query data to the TCAM devices.

## Claims

### Claim 1

An apparatus comprising:
ternary content-addressable memory (TCAM) storing a plurality of entries, each entry including a state value and a key value, wherein at least a portion of the key value is capable of being masked when the TCAM is queried by query data, and wherein the TCAM identifies a matching entry in response to being queried by the query data;
one or more storage devices storing operation information for each of the plurality of entries stored in the TCAM, wherein the operation information specifies operations associated with each respective entry in the plurality of entries stored in the TCAM; and
logic connected to the TCAM and the one or more storage devices, wherein the logic is configured perform the operations associated with the matching entry.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein to perform the operations associated with the matching entry, the logic is further configured to:
present the query data to the TCAM, wherein the query data includes state data and key data;
receive, from the TCAM, information about the matching entry identified by the TCAM;
generate processed data by performing, based on the information about the matching entry, at least one operation on data stored within the one or more storage devices;
output the processed data;
determine, based on the information about the matching entry, new state data;
determine, based on the information about the matching entry, a new key value; and
present new query data to the TCAM, wherein the new query data includes the new state data and the new key value.

### Claim 3 (depends on 2)

The apparatus of claim 2, wherein the one or more storage devices include a packet buffer that stores information about incoming packets, and wherein to generate processed data, the logic is further configured to:
perform network packet header parsing operations on network packet headers stored within the packet buffer, wherein the network packet headers include at least one of an Ethernet packet header, a VLAN packet header, and an IP version 4 packet header.

### Claim 4 (depends on 3)

The apparatus of claim 3, wherein to generate processed data, the logic is further configured to:
extract data from the packet buffer.

### Claim 5 (depends on 3)

The apparatus of claim 3, wherein to generate processed data, the logic is further configured to:
perform one or more arithmetic operations on data stored within the one or more storage devices.

### Claim 6 (depends on 3)

The apparatus of claim 3, wherein the one or more storage devices include an array of registers, and wherein to generate processed data, the logic is further configured to:
store additional data within the array of registers, wherein the additional data includes data not included within the incoming packets.

### Claim 7 (depends on 3)

The apparatus of claim 3, wherein to generate processed data, the logic is further configured to:
shift data out of the packet buffer.

### Claim 8 (depends on 3)

The apparatus of claim 3, wherein the one or more storage devices include a parsed result vector bus, and wherein to output the processed data, the logic is further configured to:
write data to the parsed result vector bus.

### Claim 9 (depends on 3)

The apparatus of claim 3, wherein to determine the new key data, the logic is further configured to:
access data from the packet buffer.

### Claim 10 (depends on 2)

The apparatus of claim 2, wherein to determine the new key data, the logic is further configured to:
determine, further based on information included within the one or more storage devices, the new key data.

### Claim 11 (depends on 2)

The apparatus of claim 2, wherein the one or more storage devices include an array of registers, and wherein to determine the new key data, the logic is further configured to:
access data from the array of registers.

### Claim 12 (depends on 2)

The apparatus of claim 2, wherein the logic is further configured to:
determine an initial value for the state data;
determine an initial value for the key data;
initialize the TCAM with TCAM entry data;
initialize the one or more storage devices with initial storage device values;
identify an end state; and
determine if the state data matches the end state.

### Claim 13 (depends on 12)

The apparatus of claim 12, further comprising:
an assembler module configured to generate, based on a source code listing, the initial value for the state data, the initial value for the key data, the TCAM entry data, and the initial storage device values.

### Claim 14

A method comprising:
presenting, by logic connected to ternary content-addressable memory (TCAM), query data to the TCAM, wherein the query data includes state data and key data;
receiving, by the logic and from the TCAM, information about a matching address identified by the TCAM;
generating processed data by performing, by the logic and based on the information about the matching address, at least one operation on data stored within one or more storage devices,
outputting, by the logic, the processed data;
determining, by the logic and based on the information in the one or more storage devices, new state data;
determining, by the logic and based on the information in the one or more storage devices, a new key value; and
presenting, by the logic, new query data to the TCAM, wherein the new query data includes the new state data and the new key value.

### Claim 15 (depends on 14)

The method of claim 14, wherein the one or more storage devices include a packet buffer that stores information about incoming packets, and wherein generating the processed data includes:
performing network packet header parsing operations on network packet headers stored within the packet buffer, wherein the network packet headers include at least one of an Ethernet packet header, a VLAN packet header, and an IP version 4 packet header.

### Claim 16 (depends on 15)

The method of claim 15, wherein generating processed data includes:
extracting data from the packet buffer.

### Claim 17 (depends on 15)

The method of claim 15, wherein generating processed data includes:
performing one or more arithmetic operations on data stored within the one or more storage devices.

### Claim 18 (depends on 15)

The method of claim 15, wherein the one or more storage devices include an array of registers, and wherein generating processed data includes:
storing additional data within the array of registers, wherein the additional data includes data not included within the incoming packets.

### Claim 19 (depends on 15)

The method of claim 15, wherein generating processed data includes:
shifting data out of the packet buffer.

### Claim 20

A device for parsing network packet headers, comprising:
ternary content-addressable memory (TCAM);
one or more storage devices including an array of registers;
a packet buffer that stores information about incoming packets; and
logic connected to the TCAM, the one or more storage devices, and the packet buffer, wherein the logic is configured to:
present query data to the TCAM, wherein the query data includes state data and key data,
receive, from the TCAM, information about a matching address identified by the TCAM,
generate processed data by performing, based on the information about the matching address, at least one operation on data stored within the one or more storage devices, wherein the at least one operation includes at least one of extracting data from the packet buffer, performing an arithmetic operation, storing data within the array of registers, and writing data to an output bus,
output the processed data,
determine, based on the information about the matching address, new state data,
determine, based on the information about the matching address, a new key value, and
present new query data to the TCAM, wherein the new query data includes the new state data and the new key value.