Mecanismos Avanzados de Búsqueda de Rutas IP: De Classful a TCAM

Búsqueda de Rutas (Route Lookup)

La operación de Búsqueda de Rutas es fundamental en el procesamiento de cabecera a la entrada de un router. Para cada paquete que ingresa, el dispositivo debe decidir a dónde enviarlo (encaminamiento). Es una operación de búsqueda (*lookup*).

En routers de altas prestaciones, la tabla de encaminamiento se encuentra implementada directamente en la tarjeta de línea para maximizar la velocidad.

Desafíos en la Búsqueda de Rutas

Direccionamiento Classful y sus Dificultades

En el direccionamiento classful, la longitud del prefijo estaba codificada en los bits más significativos de una dirección IP, lo que generaba ineficiencias y dificultades en la búsqueda.

Determinación de la Clase de la Dirección

1. Si la dirección está en formato binario, los bits más significativos definen la clase.
2. Si la dirección está en formato decimal, el primer número determina la clase.

Determinación del NetID y HostID

Una vez determinada la clase de la dirección IP, se establecen los identificadores de red y de host:

• Clase A: El primer byte es el NetID y los tres siguientes son el HostID.
• Clase B: Los dos primeros bytes son el NetID y los dos siguientes son el HostID.
• Clase C: Los tres primeros bytes son el NetID y el último es el HostID.
• Clase D: No hay HostID ni NetID. Todas las direcciones se reservan para multicast.
• Clase E: No hay HostID ni NetID. Se reservan para usos especiales.

CIDR (Classless Inter-Domain Routing)

CIDR se introdujo para permitir un uso más eficiente del espacio de direcciones IP y reducir el tamaño de las tablas de encaminamiento. Permite el uso de prefijos con longitud arbitraria.

Cada ruta se escribe en el formato: prefijo_ruta/longitud_prefijo.

Técnicas de Búsqueda de Alto Rendimiento

Tries Multibit en Hardware

Los Tries Multibit se implementan en hardware para reducir los tiempos de búsqueda, siendo esenciales en routers troncales.

En estos routers, la mayoría de las entradas de sus tablas tienen una longitud de prefijo de 24 bits o menos, lo que permite que el longest prefix match se encuentre en un acceso a memoria.

Estructura de Dos Niveles

• Primer Nivel: Contiene $2^{24}$ nodos.
• Segundo Nivel: El número de sub-tries en el segundo nivel depende de los prefijos más largos que 24 bits. Este nivel es de 8 bits.

El tamaño de la memoria del segundo banco depende de la distribución de la longitud de prefijo esperada en el peor caso. El máximo para la búsqueda es de dos accesos a memoria. Dado que el primer paso es de 24 bits, las actualizaciones pueden tardar.

TCAM (Ternary Content Addressable Memory)

La TCAM es una forma innovadora de búsqueda de direcciones IP diseñada para ser más eficiente y rápida. Utiliza hardware para realizar las búsquedas en un solo ciclo, logrando una complejidad de $O(1)$. Esto se consigue mediante circuitos de comparación en cada celda de memoria, lo que resulta en un alto rendimiento de búsqueda.

Tipos de CAM

1. CAMs Binarias: Soportan la búsqueda y el almacenamiento de bits binarios (cero o uno).
2. CAMs Ternarias (TCAM): Soportan 0, 1 y el estado "no importa" (X). Se utilizan preferentemente para el encaminamiento del prefijo más largo.

Arquitectura de la TCAM

Las celdas de la CAM se organizan en palabras horizontales de W bits de longitud. Las celdas contienen circuitería de almacenamiento y comparación.

• Las líneas de búsqueda corren verticalmente, difundiendo los datos de búsqueda a las celdas de memoria.
• Las líneas horizontales son para la comparación e indican si los datos de búsqueda coinciden con la palabra fila.
• Una línea de comparación activada indica coincidencia.
• Las líneas de comparación son entradas para un codificador de prioridad que genera la dirección de la coincidencia.

Consideraciones sobre el Consumo de TCAM

El consumo de energía es una limitación significativa en la tecnología TCAM:

• El proceso de búsqueda es de "fuerza bruta" (comparación paralela).
• Cada celda consiste en un valor, una máscara y lógica de coincidencia.
• El consumo es lineal con el tamaño.
• La potencia está limitada por los POPs (Puntos de Presencia).
• Es crucial tener en cuenta la densidad de puertos.
• Para mitigar el consumo, los bloques se dividen y se agrupan en subtablas, restringiendo así la búsqueda a la subtabla relevante.