Overview

Ternary Content Addressable Memory, or TCAM,  is a critical component of a modern router. It is a powerful and fast hardware lookup engine for IP Prefixes.  It is also complex, expensive and power hungry.  Not surprisingly, there never seems to be never enough on whatever system you use.

TCAM has historically been used to perform hardware-table lookups of Access-list, Netflow or QoS tables in routers and switches.   Most of these implementations from your favorite brand-name vendors use one or more external TCAM chips to perform these lookups.

Modern switch-on-chip ASICS such as the Broadcom Trident or Trident+ also use TCAM but normally the TCAM space is on-chip.   Having TCAM internal to the ASIC makes lookup exceedingly fast, but burns a lot of transistors.

There is an overall transistor limit per ASIC, so TCAM size is limited.  This introduces engineering constraints for the router which can catch you out if you don’t pay attention.

Commodity ASICs also use TCAM within the forwarding engine for Longest Prefix Match routing lookups.  This rest of this post will describe how TCAM works and the operation of TCAM in the forwarding engine.

A quick look at CAM

Before we dive into TCAM, let’s take a look at how CAM works.  Content Addressable Memory (CAM) allows you to input a search ‘word’ (or binary IP address  in our example) and search the entire memory in a single operation returning one (or more) matches.

In contrast, standard RAM takes a memory location as an input and returns the contents of the memory cells at those addresses.

CAM a special type of RAM which combines both storage cells and the comparison logic-gates.  This makes CAM much more complex and expensive to produce than standard RAM.  CAM performs ‘exact’ matches of input words and excels at performing lookups for one-to-one mappings, like IP-to-MAC and MAC-to-Interface lookup tables.

However, CAM isn’t well suited to prefix lookups, as it can only perform exact matches.  This causes headaches when you want to lookup an ip address against a prefix.  Your network OS could expand all elements of a subnet into individual IP addresses before programming your CAM.

However entering all these exact matches would quickly exhaust your limited CAM capacity, and would negate many of the benefits of resource conservation.

TCAM overview

Ternary Content Addressable Memory (TCAM) is a more flexible type of CAM and allows you to store a full prefix/mask.

The ‘Ternary’ in TCAM refers to the third state which can exist in a TCAM cell.  Regular (akay binary) CAM stores two states ‘1’ and ‘0’.  However TCAMs can also store a ‘don’t-care’ bit and require twice the number of logic gates to handle this more complex state and the 3-way decision.

TCAM Operation

Let’s work through a simplified example.   The example below is for a 4 entry TCAM, with each entry storing a 4-bit word. We’ll use 4-bit pseudo-IP addresses in this example.  The subnet bits are programmed into TCAM and the host-bits get programmed as ‘X’ as we ‘don’t-care’ about matching them. The last entry is all X’s to represent a default route.

We’ll pretend we’re looking to lookup pseudo-IP 1011 for routing in this example.

101/3             101X
111/3             111X
10/2               10XX
0/0                 XXXX

The diagram below shows 4 cells programmed with the 4-bit words:

Takeaway

CAM still has a role in network devices for fast exact-match lookups, but isn’t well suited to prefix-lookups.   TCAM excels at prefix lookups and the encoder plays an important role in choosing a single match.

The crucial point however is that TCAM and the encoder can only perform a ‘first-match’ against a given prefix. But… if you pre-sort the forwarding table by prefix-length before TCAM programming, the resultant lookup becomes a Longest Prefix Match (LPM).

Open Question

I want to learn more about how the sorting requirement impacts router performance.  Does the Router OS pack all the sorted prefixes tightly in the table with no slots free?

What would happen if there was a flapping /30 in your network.  Would that would mean that all prefixes from /30 and shorter have to be constantly sorted and re-inserted into the TCAM? That seems a little inefficient to me, but carving the TCAM into banks based on TCAM size seems inflexible also.

Does any reader know how this forwarding-table TCAM sorting/programming problem is sorted in the real world?

[amazon_link asins=’0471360902,1482207117,0471330361,1441963081′ template=’ProductCarousel’ store=’seamlnetwo-20′ marketplace=’US’ link_id=’d8240af3-f3f4-11e7-a1c4-b1421334aa32′]