Ternary Content-Addressable Memory (TCAM)

What Is Ternary Content-Addressable Memory (TCAM)?

Ternary content-addressable memory (TCAM) is a specialized, high-speed memory capable of searching its entire contents within a single clock cycle. The term "ternary" highlights the memory's capacity to store and query data using three different inputs: 0, 1, and X. TCAM is predominantly utilized in network routers to store address lookup tables.

Essentially, TCAM is a more versatile version of content-addressable memory (CAM). Content-addressable memory is a unique type of computer memory that stores data, similar to random-access memory (RAM). In RAM, the central processing unit (CPU) can access data only by specifying the memory address and then reading the data stored there. CAM, however, can function in the reverse manner; the CPU determines the data it is seeking—the key—and the memory returns the corresponding memory location that matches the search key. CAM can only search for exact matches of binary strings.

TCAM, on the other hand, extends the functionality of CAM by allowing searches using a mask to denote "don't care" or wildcard bits. This introduces three possible states: 0, 1, and X (a wildcard). The use of mask bits significantly enhances the flexibility of search operations.

How Is TCAM Used?

Benefits of TCAM

TCAM is capable of searching with each clock cycle, making it significantly faster than traditional RAM, which requires multiple clock cycles to query and check each memory location.

To demonstrate the efficiency of TCAM in comparison to traditional RAM, consider the scenario of searching for a specific sentence in a book. Using traditional RAM is akin to flipping through each page sequentially until you find the sentence. CAM, on the other hand, would be similar to a book with an index or concordance, allowing you to quickly locate the page where a particular word appears.

Drawbacks of TCAM

Despite their advantages, both CAM and TCAM come with certain drawbacks. These memory cells need additional transistors to support the search feature, making them more expensive and less dense than traditional RAM. Furthermore, each memory cell must be active during every clock cycle to perform the search, resulting in higher power consumption and increased heat production.

Specialized Applications of TCAM

Due to these trade-offs, CAM and TCAM are primarily used as supplementary memory for specialized applications that require rapid, frequent searches of relatively small data sets. The most common application is in network routers, where they are used to store rule lookup tables. Other applications include use within a CPU's translation lookaside buffer, in database systems, or artificial neural networks.

TCAM in Networks

Large network routers can process millions of packets every second, requiring millions of small searches to match packets to the routing table. TCAM allows the router to search and find results in just one cycle.

For example, a rule could be designed to match all IP addresses in the 10.0.0.0/8 subnet. This could be recorded in TCAM as 00001010, XXXXXXXX, XXXXXXXX, XXXXXXXX. If the IP address 10.100.20.5 arrives, it will be translated into the binary string 00001010, 01100100, 00010100, 00000101, which will match the rule.

Routing tables often contain rules for media access control addresses (MAC addresses), IP addresses, network protocols, or ports. These elements are directly encoded as binary data in a packet header, making them easy to search with TCAM.

In a router, the TCAM is usually much smaller than the general RAM because of its specialized use. A smaller enterprise router might only have about 20 megabytes of TCAM storage. Large internet routers used by backbone internet service providers (ISPs) might need to store the entire Border Gateway Protocol (BGP) table in TCAM, which is quickly approaching a million entries. These routers often use dedicated application-specific integrated circuits (ASICs) and can have separate TCAM storage for different purposes. If a router cannot store all its routing entries in TCAM, it will fall back to slower memory, resulting in high CPU usage and dropped packets.

The administrator often does not directly manage TCAM storage. When programming the router, the software will translate the rules into TCAM format. The administrator can define how TCAM storage is partitioned. For example, IPv4 rules use less memory space than IPv6 rules, so configuring the router to primarily store IPv4 rules will allow for more saved rules.

TCAM can also be used in network intrusion detection. These devices can store known malicious fingerprints or hashes and quickly compare observed traffic with the malicious data stored in TCAM.