Por: Javier Moreno
Instructor Titular
CCAI-CCNA-CCNP
Academia Cisco Fermín Toro
Programa Cisco Networking Academy
Caracas – Venezuela

Una pequeña Introducción: Ternary Content Addressable Memory (TCAM), es un componente crítico de un router moderno. Es un motor poderoso de búsqueda rápida para prefijos IP, aunque complejo, costoso y goloso en el consumo de energía. TCAM ha sido históricamente usado en routers y switches, para realizar búsquedas en hardware, en tablas de ACL, Netflow o QoS. La mayoría de estas implementaciones de diferentes fabricantes, usan uno o más chips externos TCAM. Algunos switches modernos usan TCAM en un ASIC. Tener TCAM dentro de ASIC hace la búsqueda extraordinariamente rápida, pero consume muchos transistores. Hay un límite de transistores por ASIC, lo que agrega restricciones de ingeniería para el router y puede generar problemas si no se le presta atención. Los ASICs también usan TCAM para el envío de paquetes mediante la búsqueda del prefijo con mayor coincidencia (longest prefix match).

El resto de este artículo describe cómo trabaja TCAM en el mecanismo de envío de paquetes Cisco Express Forwarding (CEF).

Un repaso de la tabla CAM: Antes de sumergirnos en la TCAM, hagamos un repaso de la tabla CAM (Content Addressable Memory). En una memoria estándar RAM, se ingresa con una dirección de la memoria para
buscar el contenido que existe en dicha memoria. Una CAM es un tipo de memoria RAM, en la que, por contraste, se hace una búsqueda inversa: se ingresa con el contenido existente (una IP binaria, por ejemplo) en alguna parte de la memoria, para averiguar la ubicación de la memoria que precisamente posee dicho contenido; operación que se realiza de una sola vez, gracias a compuertas lógicas. Esto hace que la elaboración
de una tabla CAM sea compleja y costosa. CAM lleva a cabo el logro de coincidencias “exactas” y sobresale en búsquedas de asociaciones uno a uno, como habría en tablas IP-MAC y tablas MAC-Interfaces. Sin embargo,
CAM no es adecuada para búsqueda de prefijos, ya que solamente lleva a cabo coincidencias “exactas”, lo que produciría dolores de cabeza cuando se quiera comparar un prefijo versus una dirección IP. Un sistema
operativo de red podría expandir todos los elementos de una subred en direcciones IP individuales antes de programar la CAM. Sin embargo, entrar todas estas coincidencias exactas agotaría la capacidad limitada de la
CAM.

Qué es una TCAM: TCAM es un tipo más flexible de CAM, que permite almacenar prefijo y máscara. El término “Ternary” en TCAM se refiere al tercer estado que puede existir en una celda TCAM. Una CAM
regular (binaria) almacena dos estados “1” y “0”. Sin embargo las TCAMs pueden también almacenar un bit (X) “no importa” aunque requiere el doble de compuertas lógicas para manejar este estado más complejo, y
una decisión que involucra tres estados.

Operación TCAM: Trabajemos con un ejemplo simplificado. El ejemplo de más abajo se refiere a una tabla CAM de tres entradas (entries), en la que cada entrada almacena una palabra de 4 bits. Usamos una pseudo
dirección IP de 4 bits en este ejemplo, para simplificar la explicación, que si fuera realista debería tener 32 bits, pero no altera el objetivo de la explicación. Los bits de subred (1 y 0) son programados en la TCAM y los
bits de host se programan como “X”, pues no importa tener coincidencias con ellos. Una cuarta y última entrada tiene todos los bits “X” para representar una ruta por defecto (ningún bit importa). Recordemos que
cuando se busca coincidencia en una tabla de enrutamiento solamente interesan los bits que indica la máscara, los demás no importan.
Supongamos que estamos buscando la pseudo IP 1011 en este ejemplo.

Este diagrama de abajo muestra 4 celdas programadas con las palabras de 4 bits:

Todas las líneas de coincidencia (match) son cargadas con voltaje “high” antes de comenzar la búsqueda. El “search line driver” envía la IP buscada (1011) a todas las celdas a lo largo de cada entrada de la tabla. Simultáneamente cada celda compara su valor almacenado con el de la IP buscada, resultando coincidencia o no; cuando haya un “no importa” en la celda, siempre habrá coincidencia en dicha celda. Después de la comparación, si el voltaje “high” en la línea “match” permanece, es porque ha habido coincidencias en todas las celdas (4 en este ejemplo) con la IP buscada (línea en verde). Basta que a lo largo de una línea “match” una
sola celda no registre coincidencia, para que dicha línea pierda el voltaje “high”, siendo entonces que el resultado 0 volts signifique no coincidencia con la IP buscada (línea en rojo).

Así que el resultado, en este caso, es que hay múltiples coincidencias (varias líneas en verde). Como consecuencia, el codificador tomará la primera línea “match” (00) en este caso y producirá una versión codificada de tal número de línea. La salida del codificador puede ser usada para dirigirse a otra tabla y completar el proceso de envío. El resultado final es que el dúo TCAM/Codificador seleccionó el prefijo más largo de las tres coincidencias.
¡Magia!

Pero el codificador no sabía que 101/3 era la coincidencia del prefijo más largo. Solo sabía que era la coincidencia con la línea de menor número: la primera coincidencia. Pero si se revisan los prefijos originales, se verá que las cartas fueron servidas; en otras palabras, los prefijos habían sido ordenados, con el prefijo más largo de primero y la ruta por defecto de último. Ahí radica la magia.

Corolario: CAM todavía tiene un rol en los dispositivos de red para búsquedas de coincidencias “exactas”, pero no está bien acondicionada para búsqueda de prefijos. TCAM sobresale en búsqueda de prefijos y el
codificador juega un rol en la elección de una sola coincidencia. El punto crucial, sin embargo, es que TCAM y el codificador pueden solo llevar a cabo una “primera coincidencia” versus un prefijo dado. Pero…. si se ordena la tabla de envío por longitud de prefijo antes de programar la tabla CAM (tal como ocurre en la práctica), la búsqueda resultante se convierte en una coincidencia Longest Prefix Match (LPM).

Preparado con base en trabajos de John Harrington