Using Content-Addressable Memory for Networking Applications
Content-addressable memory (CAM) turns the tables on conventional memory approaches. CAMis tailor-made for accelerating searches through massive data tables, making it a prime candidate for such things as routing tables and
policy.
By Sherri Azgomi
Most memory devices store and retrieve data by addressing specific memory locations. As a result, this path often becomes the limiting factor for systems that rely on fast memory access. The time required to find an item stored in memory can be reduced considerably if the stored data item can be identified for access by the content of the data itself rather than by its address. Memory that is accessed in this way is called content-addressable memory
(CAM). CAM provides a performance advantage over other memory search algorithms (such as binary and tree-based searches or look-aside tag buffers) by comparing the desired information against the entire list of prestored entries simultaneously, often resulting in an order-of-magnitude reduction of search time.
CAM is ideally suited for several functions, including Ethernet address lookup, data compression, pattern-recognition, cache tags, high-bandwidth address filtering, and fast lookup of routing,
high-bandwidth address filtering, user privilege, security, or encryption information on a packet-by-packet basis for high-performance data switches, firewalls, bridges, and routers. This article discusses several of these applications as well as hardware options for using CAM.
CAM basics
Since CAMs are an outgrowth of RAM technology, in order to understand a CAM, it helps to contrast it with a RAM. RAM is an integrated circuit that stores data temporarily. Data is stored in RAM at
a particular location, which is called an address. In RAM, the user supplies the address and gets the data back. The number of address lines limits the depth of a memory using RAM, but the width of the memory can be extended as far as desired. With CAM, the user supplies the data and gets the address back. The CAM searches through the memory in one-clock cycle and returns the address where the data is found. The CAM can be preloaded at device startup and rewritten during device operation.
CAM can
accelerate any application requiring fast searches of databases, lists, or patterns, such as in image or voice recognition, or computer and communication designs. For this reason, CAM is used in applications where search time is critical and must be very short. For example, the search key could be the IP address of a network user, and the associated information could be a user’s access privileges and location on the network. If the search key presented to the CAM is present in the CAM’s table, the
CAM indicates a match and returns the associated information, which consists of the user’s privileges. A CAM can thus operate as a data-parallel or single instruction/ multiple data (SIMD) processor.
CAM can be used to accelerate any application ranging from LANs, database management, file-storage management, and table look up to pattern recognition, artificial intelligence, fully associative and processor-specific cache memories, to disk cache memories. Although CAM has many applications,
it’s particularly well suited to performing search operations.
In each one of these applications the user may not know the addresses of words that have particular pieces of information stored within a specific portion of the word length.
Data Compression with CAM
Data compression removes the redundancy that resides in a given piece of information, producing an equivalent but shorter message.
CAM is well suited for data compression because the movement of
packets through a LAN requires some form of address translation. Since a good portion of a compression algorithm’s time is spent searching and maintaining these data structures, replacing the algorithms with a hardware search engine can greatly increase the throughput of the algorithm.
In a data compression application, CAM lookup is performed after each word of the original data is presented (see
Figure 1
). If the code corresponding to the word bit
pattern in the input register is found, then the appropriate symbol or token is output and the input register is flushed. If the code is not found in the CAM, then another word is shifted in. A CAM will generate a result in a single transaction regardless of table size or search list length. This property makes CAM an ideal candidate for data compression schemes that use sparsely populated tables as part of their algorithm.
Network switch
CAM is used in switch applications to extract and
process the address information from incoming data packets. In order to switch the packet to the correct outgoing port, CAM compares the destination address with a table of addresses stored within it. For example, a CAM might store an Ethernet address and switch port numbers. The CAM compares the received data against the table that has been stored within, and if the comparison yields a match, the port identification is given, and routing control forwards the packet to the correct port or address (see
Figure 2
).
IP filter
An IP filter is a security feature that restricts unauthorized access to LAN resources or restricts traffic on a WAN link (IP traffic that goes through the router). IP filters can be used to restrict the types of Internet traffic that are permitted to access a LAN, and LAN workstations can be restricted to specific Internet-based applications (such as e-mail). CAM can be used as a filter that blocks all access except for those
packets that are given explicit permission according to the rules of the IP filter. In this application, CAM compares the packet being routed to the port against the IP filter rules residing within CAM. When a match is found, the packet is either permitted or denied (as shown in
Figure 3
).
ATM switch
CAMs can be used as a translation table in ATM switching network components. Since ATM networks are connection-oriented, virtual circuits need
to be set up across them prior to any data transfer. Two kinds of ATM virtual circuits exist: Virtual Path (identified by a virtual path identifier [VPI]) and Channel Path (identified by a channel path identifier [VCI]). VPI/VCI values are localized; each segment of the total connection has unique VPI/VCI combinations. Whenever an ATM cell travels through a switch, its VPI/VCI value has to be changed into the value used for the next segment of connection. This process is called VPI/VCI translation. Because
speed is an important factor in an ATM network, the speed at which this translation occurs forms a critical part of the network’s overall performance.
CAM can act as an address translator in an ATM switch and can quickly perform the VPI/VCI translation. During the translation process, the CAM takes incoming VPI/VCI values in ATM cell headers and generates addresses that access data in RAM. A CAM/RAM combination enables the realization of multimegabit translation tables with full parallel
search capability. VPI/VCI fields from the ATM cell header are compared to a list of current connections stored in the CAM array. As a result of the comparison, CAM generates an address that is used to access an external RAM where VPI/VCI mapping data and other connection information is stored. The ATM controller modifies the cell header using the VPI/VCI data from the RAM, and the cell is sent to the switch (see
Figure 4
).
Memory mapping
In a
system that utilizes a dynamic memory map, CAM can be used to store memory addresses for quicker access. For example, in a PCI system, a single PCI device may contain up to six memory spaces allocated in system memory. The exact location of these spaces is determined on power-up, and their starting locations are written into the PCI interface’s six base address registers (BAR). When a master interface requests access to a PCI de-vice’s memory or I/O location, a CAM can be used to quickly match the
request to the address in memory (as shown in
Figure 5
).
Hardware solutions for CAM
Two types of hardware solutions exist for CAM: individual (or discrete) components and on-chip implementations. Since the late 1980s, individual CAM components have been available as relatively specialized memory devices. Whenever CAM was required, a designer would add the component to the PCB board. This approach allows a designer to take advantage of the
features of the CAM, but takes additional board space. Furthermore, the overall system performance can be reduced by on/off-chip delays of the CAM and the system device. Performance can also be affected by board delays.
On-chip implementations of CAM in the form of embedded functions have only recently been made available. One such example is the CAM capability offered in the latest high-density programmable logic devices (PLDs). The advantages of this type of CAM are the board space efficiency and
the increase in performance. This performance increase is due to the elimination of on/off-chip delay along with the smaller process of on-chip CAMs. In these CAM-capable PLDs, an on-board structure called the embedded system block (ESB) can implement CAM.
Figure 6
shows the CAM block diagram in one such PLD.
Each ESB in this device supports a 1K CAM (32k x 32). Wider or deeper CAM can be implemented by combining multiple CAMs using device logic resources.
The associated design development software automatically combines ESBs if the user desires larger CAMs. The number of ESBs in a PLD ranges from 26 to 228. In order to make a deeper or wider CAM in one of these PLDs, the output of multiple ESBs can be cascaded together (any amount of the ESBs existing in a device can be cascaded to create a bigger CAM). Both the encoded and unencoded output implementations of ESB can be used to create a deeper and wider CAM.
The CAM can be preloaded with data during
configuration of the PLD, or it can be written during system operation. In most cases, two clock cycles are required to write each word into CAM. This PLD CAM supports writing don’t-care bits into words of the memory. The don’t-care bit can be used as a mask for CAM comparisons — any bit set to don’t-care has no effect on matches. When don’t-care bits are used, a third clock cycle is required to write words into the CAM. The output of the CAM can be encoded or unencoded. When encoded,
the ESB outputs an encoded address of the data location. Encoded output is better suited for designs that ensure no duplicate output. If duplicate data is written into multiple locations, unencoded output is required. ESB uses its sixteen outputs and reads the outputs in two clock cycles.
The CAM solution
For any application that requires a fast memory search, CAM can provide a solution. Many manufacturers provide discrete CAM components. As CAM becomes more popular and
system-on-chip design becomes more common, intellectual property and embedded versions of CAM (such as that offered in the most advanced PLDs) have also become available. In the coming months, CAM will enjoy increased popularity, particularly with the growing number of communication applications that can utilize CAM’s capabilities.
Sherry Azgomi is an advanced component applications engineer at Altera Corp. She received a BSEE from San Jose State University and can be contacted at
sazgomi@altera.com
.
Return to the
Table of Contents
Puzzled by a network processing design issue?
