Ternary content addressable memory device

Abstract

A ternary content addressable memory device. The device includes a ternary CAM array segmented into a plurality of array groups, each of which includes a number of rows of ternary CAM cells. Each array group is assigned to a particular priority by storing the priority number for each array group in an associated storage element. Data entries are then stored in array groups according to priority.

Description

CROSS-REFERENCE TO RELATED APPLICATION[0001]This application is a continuation-in-part, and claims the benefit under 35 USC §120, of co-pending and commonly owned U.S. patent application Ser. No. 09 / 829,355 entitled “CLASSLESS INTERDOMAIN ROUTING USING BINARY CONTENT ADDRESSABLE MEMORY” filed Apr. 9, 2001, incorporated by reference herein.BACKGROUND[0002]1. Field of Invention[0003]This invention relates generally to semiconductor memories and specifically to content addressable memories.[0004]2. Description of Related Art[0005]Packets of data are relayed across the Internet according to an Internet Protocol (IP) addressing scheme. One commonly used IP addressing scheme is known as IPv4. An IPv4 address is a 32-bit binary address segmented into Network and Host address fields. IPv4 addresses are typically grouped into classes depending upon how many bits are in the Network field. For example, Class A, B, and C IPv4 addresses have 8-bit, 16-bit, and 24-bit Network fields, respectively...

AI Technical Summary

Benefits of technology

The present invention provides a method and apparatus for implementing CIDR addressing schemes using binary CAM cells without a multitude of compare operations per search key. By segmenting a binary CAM array into multiple array groups, each containing a specific number of rows of binary CAM cells and an associated global mask, CIDR address entries can be stored only in the appropriate array group. This reduces the processing required for searching for CIDR addresses and improves efficiency. In some embodiments, a ternary CAM array can also be segmented into multiple array groups based on priority, with data entries being stored based on priority. This further improves efficiency and speed in searching for CIDR addresses.

Problems solved by technology

Due to static field boundaries, the classfull IPv4 addressing scheme generally results in inefficient use of address space.

However, binary CAM devices are not well suited for CIDR addressing schemes in which the CAM data entries may have different prefix lengths, and thus require individual masks of different lengths.

Performing multiple compare operations per search key to determine the LPM requires considerable time, and therefore may limit performance.

The re-ordering of entries in the ternary CAM can add significant overhead to the associated router (e.g., delay and additional hardware and software) and may limit performance.

Because each row of CAM cells in a ternary CAM array includes an additional row of mask cells to store the local mask, ternary CAM devices are generally not able to store as many unique CIDR addresses as binary CAMs.

Images