# US 2006/0155926 A1 · Efficient content addressable memory array for classless inter-domain routing

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

- Number: US 2006/0155926 A1
- Document ID: US20060155926A1
- Status: Published application
- Kind: A1
- Application number: 11/321,794
- Filed: 2005-12-29
- Published: 2006-07-13
- Earliest claimed: 2004-12-29
- Assignees: STMicroelectronics Pvt.Ltd.
- Inventors: Danish Syed; Rajiv Yadav; Anoop Khurana
- Web page: https://patentgrep.com/patent/US20060155926A1

## CPC

- 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 45/00: Routing or path finding of packets in data switching networks (routing or path finding in wireless networks H04W40/00)
- H04L 45/54: {Organization of routing tables}
- H04L 45/7453: using hashing
- H04L 45/74591: {using content-addressable memories [CAM]}
- 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

An efficient Content Addressable Memory array for Classless Inter-Domain Routing with each CAM cell including an additional storage unit for storing the prefix length associated with the contents of the cell. An enabling logic connects the prefix length value to a wired OR plane common to all CAM cells, and a sequential bit wise comparison unit has its inputs connected to the wired OR plane and the additional storage unit with its output controlling the enabling logic.

## Claims

### Claim at position 1

1-8. (canceled)

### Claim 9

A Content Addressable Memory (CAM) array for Classless Inter-Domain Routing (CIDR), the CAM array comprising:
a plurality of CAM cells; and
a wired OR plane connecting the plurality of CAM cells;
a prefix length memory associated with each CAM cell to store a prefix length value associated with contents of the CAM cell;
an enabling circuit connecting the prefix length memory to the wired OR plane common to all CAM cells; and
a sequential bit-wise comparison unit having inputs connected to the wired OR plane and the prefix length memory, and an output controlling the enabling circuit.

### Claim 10 (depends on 9)

The CAM array as claimed in claim 9 wherein the prefix length memory includes a respective output tap for each bit of the prefix length value; and wherein the enabling circuit comprises:
a first logic gate receiving control signals; and
plurality of buffers receiving an enable signal from the first logic gate, each buffer being connected to a corresponding output tap of the prefix length memory.

### Claim 11 (depends on 9)

The CAM array as claimed in claim 9 wherein the sequential bit wise comparison unit comprises:
a plurality of comparators connected to the output of the wired OR plane and output taps of the prefix length memory;
a shift register for generating a walking one pattern;
a plurality of logic gates, each logic gate connected to an output of the shift register and an output of a corresponding comparator;
a second logic gate receiving an output of the plurality of logic gates;
a third logic gate receiving an output of the second logic gate; and
a multiplexer connected to the output of the third logic gate and providing a feedback to the third logic gate.

### Claim 12 (depends on 10)

The CAM as claimed in claim 10 wherein the first logic gate comprises an AND gate.

### Claim 13 (depends on 11)

The CAM as claimed in claim 11 wherein the second logic gate comprises an OR gate.

### Claim 14 (depends on 11)

The CAM as claimed in claim 11 wherein the third logic gate comprises an AND gate.

### Claim 15 (depends on 11)

The CAM as claimed in claim 11 wherein the plurality of logic gates are AND gates.

### Claim 16

A Content Addressable Memory (CAM) array comprising:
a plurality of CAM cells; and
a logic device connecting the plurality of CAM cells;
a prefix length memory associated with each CAM cell to store a prefix length value associated with contents of the CAM cell;
an enabling circuit connecting the prefix length memory to the logic device; and
a comparison unit having inputs connected to the logic device and the prefix length memory, and an output controlling the enabling circuit.

### Claim 17 (depends on 16)

The CAM array as claimed in claim 16 wherein the prefix length memory includes a respective output tap for each bit of the prefix length value; and wherein the enabling circuit comprises:
a first logic gate receiving control signals; and
plurality of buffers receiving an enable signal from the first logic gate, each buffer being connected to a corresponding output tap of the prefix length memory.

### Claim 18 (depends on 16)

The CAM array as claimed in claim 16 wherein the comparison unit comprises:
a plurality of comparators connected to the output of the logic device and output taps of the prefix length memory;
a shift register;
a plurality of logic gates, each logic gate connected to an output of the shift register and an output of a corresponding comparator;
a second logic gate receiving an output of the plurality of logic gates;
a third logic gate receiving an output of the second logic gate; and
a multiplexer connected to the output of the third logic gate and providing a feedback to the third logic gate.

### Claim 19

A method for detecting a largest prefix length value among hit locations in a Content Addressable Memory (CAM) array including a plurality of CAM cells connected together via a logic device, the method comprising:
storing, in a prefix length memory, the prefix length value associated with the contents of a respective CAM cell;
selectively connecting the prefix length memory to the logic device common to all CAM cells; and
comparing the stored prefix length value with a value on the logic device beginning from a most significant bit and disconnecting the prefix length memory based upon the comparison to provide the largest prefix length value.

### Claim 20 (depends on 19)

The method as claimed in claim 19, wherein the logic device comprises a wired OR plane.

### Claim 21 (depends on 19)

The method as claimed in claim 19, wherein an enabling circuit selectively connects the prefix length memory to the logic device; and a comparison unit having inputs connected to the logic device and the prefix length memory, and an output controlling the enabling circuit, compares the stored prefix length value with the value on the logic device.

### Claim 22 (depends on 21)

The method as claimed in claim 21 wherein the prefix length memory includes a respective output tap for each bit of the prefix length value; and wherein the enabling circuit comprises:
a first logic gate receiving control signals; and
plurality of buffers receiving an enable signal from the first logic gate, each buffer being connected to a corresponding output tap of the prefix length memory.

### Claim 23 (depends on 21)

The method as claimed in claim 21 wherein the comparison unit comprises:
a plurality of comparators connected to the output of the logic device and output taps of the prefix length memory;
a shift register;
a plurality of logic gates, each logic gate connected to an output of the shift register and an output of a corresponding comparator;
a second logic gate receiving an output of the plurality of logic gates;
a third logic gate receiving an output of the second logic gate; and
a multiplexer connected to the output of the third logic gate and providing a feedback to the third logic gate.
