Memory - TCAM Lookups

Ternary Content-Addressable Memory (TCAM) is a type of special computer memory used in various very-high-speed searching applications. It is especially useful for comparing input search data against a table of stored data, which returns matching data.

Cisco devices such as switches, routers, and firewalls use this type of hardware memory for particular purposes, such as ACL lookups and Routing Table lookups.

TCAM does not require an exact match, and is queried using 0s, 1s, and Xs, where X essentially means “anything” (that is, either 0 or 1). It’s kind of like a wildcard state. The name "ternary" CAM comes from the fact that you use three states rather than two.

Basics of the TCAM Lookup process

Unlike regular RAM, where you provide an address and get data, in TCAM, you provide data, and it searches for the address where this data is stored. Let's use an example where we are looking for the 192.168.1.1 address in a routing table or an ACL.

The Three Possible Results: 1, 0, and X

1 (Match):
- The result is 1 when the search key (e.g., 192.168.1.1) exactly matches an entry in the TCAM.
- For example, if you have an entry for 192.168.1.1 in your forwarding table, querying TCAM with 192.168.1.1 will return 1, indicating a match.
0 (No Match):
- The result is 0 when the search key does not match any entry in the TCAM.
- If there is no entry for 192.168.1.1 in the forwarding table, querying TCAM with this address will return 0, indicating no match found.
X (Don't Care):
- "X" is a wildcard character used in TCAM entries that represents a "don't care" or "anything" condition. This means that for certain bits in the entry, any value (0 or 1) can be considered a match.
- For instance, if you have a TCAM entry for 192.168.1.X (where X is a wildcard), the TCAM will match any IP address in the range 192.168.1.0 to 192.168.1.255.
- When checking 192.168.1.1, if there is an entry like 192.168.1.X in the TCAM, it will return 1 because 192.168.1.1 matches the "don't care" condition.

Example Scenario

Let's consider a few example entries in the TCAM:

Entry: 192.168.1.1 (Exact match)
Entry: 192.168.1.X (Wild card match)
Entry: 192.168.X.X (Broader wild card match)

If you query for 192.168.1.1:

The TCAM will first check for an exact match. It finds entry 1 and returns 1 (Match).
If entry 1 were not present, it would then check for less specific matches. It finds entry 2 and returns 1.
If neither entry 1 nor entry 2 were present, it would check entry 3, which would still return 1 because of the wildcard.
If no matching entries are found at all, it returns 0.

Understanding "Don't Care" (X)

Don't Care (X): This character allows flexibility in matching entries. It tells the TCAM to ignore certain bits.
- For example, an entry like 192.168.1.X can match any IP address from 192.168.1.0 to 192.168.1.255. Here, X means the last octet can be anything.
- An entry like 192.168.X.X can match any IP address from 192.168.0.0 to 192.168.255.255. Here, both the third and fourth octets can be anything.

Summary

1 is returned when there's an exact or wildcard match.
0 is returned when no matching entries are found.
X in TCAM entries indicates positions that can match any bit, allowing flexible and broad matches.

Understanding these results and the role of "don't care" conditions helps in designing efficient and flexible network routing and filtering mechanisms using TCAM.

Links: