Algunos de los posts ya publicados sobre este tema son:
- El reenvío de paquetes IP (I)
- El reenvío de paquetes IP (II)
- Process Switching
- Cisco Express Forwarding
Los mecanismos precedentes (process switching, fast switching) son mecanismos intensivos en recursos de cómputo con lo que requieren un mecanismo que permita aumentar su eficiencia y mejorar el aprovechamiento de los recursos de cómputo.
Para dar respuesta a estas necesidades CEF optimiza las dos tareas más complejas y demandantes de recursos que incluye el proceso de enrutamiento de un paquete IP:
- La selección de la mejor ruta (lookup de la tabla de enrutamiento) para alcanzar el destino, incluyendo la interfaz de salida a utilizar para reenviar el paquete.
A esto busca responder con la implementación de una FIB. - La construcción del encabezado de capa de enlace de datos que se debe utilizar, lo que también se conoce como la reescritura de la trama (frame rewrite).
Para esto implementa la tabla de adyacencias.
En el esquema tradicional de operación, para encontrar la mejor ruta a un destino específico para un paquete concreto, es necesario revisar la tabla de enrutamiento (RIB) completa, entrada por entrada, y encontrar la ruta con mejor coincidencia con la dirección IP destino.
La regla primaria de esta búsqueda es encontrar la ruta con la coincidencia más extensa (longer prefix match) que surge de la comparación entre las diversas entradas posibles en la tabla de enrutamiento. Una revisión de la tabla completa debiera ser suficiente para lograr esta respuesta.
Pero si la ruta seleccionada como la más precisa sólo contiene la dirección IP del próximo salto y no la interfaz de salida (a través de la cual se debe sacar el paquete), esta búsqueda no será suficiente y se deberá repetir el proceso hasta localizar una red directamente conectada a través de la cual se puede alcanzar la dirección IP del próximo salto para entonces tener una interfaz de salida.
Esta tarea requiere generalmente entre 2 y 3 revisiones (lookups) de la tabla de enrutamiento.
El lookup de la tabla de enrutamiento es ineficiente.
Para hacer más eficiente el proceso CEF aplica varios criterios:
- Ordena la tabla de enrutamiento en función de la longitud de los prefijos partiendo por los prefijos /32, siguiendo por los /31 y así en forma decreciente hasta llegar a la ruta por defecto (0.0.0.0/0) al final de la tabla.
- La tabla se revisa desde su primer entrada, entrada por entrada, realizando una operación AND entre la dirección IP destino del paquete y la longitud de los prefijos; el resultado se compara con la dirección de red de cada entrada y se detiene al alcanzar la primer coincidencia.
Dado que la tabla está organizada desde lo más específico a lo más general, la primer coincidencia es automáticamente el prefijo más largo (longest prefix). - La información de la ruta proporciona la interfaz de salida para evitar realizar búsquedas recursivas.
- Esto no es la tabla de enrutamiento, es una tabla diferentes que se almacena como una tabla independiente construida a partir de la información contenida en la tabla de enrutamiento.
Esta tabla es la Forwarding Information Base (FIB).
La idea básica es guardar los prefijos que corresponden a todas las redes destino conocidas de la RIB en la FIB.
Pero esta base de datos, no sólo almacena las decisiones de reenvío ya resueltas sino que también las ordena de modo de optimizar la velocidad y el uso de procesamiento en la búsqueda de la coincidencia más larga.
Para esto la tabla tiene una estructura lógica de árbol de decisiones en la que la dirección de destino es analizada dígito a dígito (bit a bit, nodo a nodo) hasta encontrar la mejor coincidencia.
Dado que las direcciones IPv4 tienen 32 bits de longitud, estos registros tienen una profundidad máxima de 32 nodos o bits (33 si contamos el nodo root).
Consecuentemente, para realizar un lookup:
- Parte de un nodo raíz como "current node".
- Se intenta avanzar buscando un nodo del siguiente nivel que coincida con el siguiente dígito.
- Si no hay una siguiente coincidencia , la búsqueda se detiene y la última coincidencia alcanzada representa la mayor longitud de prefijo encontrada.
- Si hay una siguiente coincidencia, se define esta nueva posición como current node y se repite el proceso hasta completar la búsqueda o hasta que no haya nuevas coincidencias.
Si tomamos como ejemplo una dirección destino (para simplificar consideraré un solo octeto) de un octeto con valor 112 (01110000).
- Current node inicial: el nodo raíz.
- Revisa el primer bit no procesado de la dirección destino, un cero (0).
- Se busca en el siguiente nivel de la tabla (A) un bit en cero (0) y como existe, este es ahora el current node.
- Revisa el siguiente bit no procesado, es un uno (1).
- Se busca en el nivel B de la tabla un bit en uno derivado del 0 en el nivel A, y como existe, este será el nuevo current node.
- Nuevamente se toma el siguiente bit sin procesar, en este caso un uno (1).
- Se busca nuevamente en la tabla si hay un bit en uno (1) en el nivel C asociado al 1 del nivel B, y como existe, se toma este como siguiente current node.
- El siguiente bit no procesado es otro uno (1).
- Se revisa la tabla para verificar la presencia de un bit en uno (1) en el nivel D asociado al 1 del nivel C. Existe y por lo tanto se toma este como current node.
- El siguiente bit no procesado es ahora un cero (0).
- Busca entonces en la tabla, en el nivel E, un 0 como asociado al 1 del nivel D. Existe y este pasa a ser ahora el current node.
- Así se continúa hasta completar el análisis del prefijo y definir cuál es la entrada de la tabla FIB que da respuesta al requerimiento de definir un destino para alcanzar la dirección IP destino del paquete.
De esta manera se localiza la ruta con mejor correspondencia (longest matching prefix) con la dirección IP destino del paquete, y con ella la interfaz a través de la cual debe ser reenviado hacia el próximo salto.
El próximo paso es obtener la información necesaria para reescribir el encabezado de la trama, y para eso necesitamos la tabla de adyacencias.
La tabla de adyacencias
La FIB sólo proporciona la información referida a la interfaz a través de la cual se debe reenviar el paquete, pero no cuenta aún con la información necesaria para construir el nuevo encabezado de la trama o completar el frame rewrite.
Encapsular el paquete con el encabezado de trama correcto es un requisito para poder finalmente enviar el paquete hacia su próximo salto y esto debe repetirse para cada paquete que se envía al mismo próximo salto o vecino.
El dispositivo puede conocer cientos de miles de rutas a diferentes destino, pero en general está conectado a un número reducido de dispositivos vecinos que ofician como próximos saltos de cada ruta.
Por este motivo múltiples entradas de la FIB utilizan el mismo próximo salto, la misma interfaz de salida y por lo tanto el mismo encabezado de la trama para el reenvío de los paquetes.
Esto hace que lo más eficiente sea que la información necesaria para concretar el envío del paquete se complete aún antes de que haya algún flujo de datos.
Los próximos saltos se conocer a partir de la RIB y sus direcciones de capa 2 se pueden obtener de mecanismos como ARP.
Esta información se almacena en otra base de datos conocida como tabla de adyacencias.
La tabla de adyacencias es una base de datos que contiene la lista de todos los dispositivos adyacentes conocidos por nuestro router y la información correspondiente.
Una adyacencia es la información completa necesaria para reenviar el paquete a otro dispositivo que está directamente conectado: la interfaz de salida junto con el encabezado de trama que se puede utilizar para enviar los paquetes a ese vecino.
Supongamos un router conectado a otros routers vecinos a través de interfaces GigabitEthernet.
Para revisar su tabla de adyacencias debemos utilizar el comando show adjacency detail
Router# show adjacency detail
Protocol Interface Address
...
IP GigabitEthernet0/2 192.168.3.3(7)
0 packets, 0 bytes
epoch 0
sourced in sev-epoch 0
Encap length 14
005079666802CA0320A4003D0800
ARP
Lo que se muestra es la información necesaria para prefabricar el encabezado Ethernet.
En particular el encabezado completo:
005079666802CA0320A4003D0800
005079666802 Dirección MAC destino
CA0320A4003D Dirección MAC origen
0800 Ethertype del paquete que se encapsula
El contenido es semejantes cuando se trata de subinterfaces 802.1Q ya que incluye el valor del campo clase de servicio y el ID de VLAN.
Router# show adjacency detail
Protocol Interface Address
...
IP GigabitEthernet0/2.100 192.168.3.3(7)
0 packets, 0 bytes
epoch 0
sourced in sev-epoch 0
Encap length 14
005079666802CA0320A4003D81000064
0800
ARP
005079666802CA0320A4003D81000064
005079666802 Dirección MAC destino
CA0320A4003D Dirección MAC origen
8100 Ethertype para un encabezado 802.1Q
0 Clase de servicio (0)
064 Etiqueta de VLAN 100 (64 en hexadecimal)
0800 Campo Ethertype original de la trama antes del etiquetado
La FIB y la tabla de adyacencia son 2 componentes clave de CEF.
La FIB contiene los prefijos IPv4 que identifican todas las redes destino conocidas y los organiza de modo de acelerar el proceso de lookup. El resultado de la búsqueda en la FIB apunta a una entrada en la tabla de adyacencias.
La tabla de adyacencias contienen los encabezados de trama a utilizar con cada uno de los próximos saltos de modo de aplicarlos inmediatamente a los paquetes para su envío a los dispositivos adyacentes.
Podés participar de nuestro grupo en Facebook:
https://www.facebook.com/groups/librosnetworking/
O seguir las principales novedades en el grupo de Telegram:
https://t.me/LibrosNetworking
Las abreviaturas y siglas utilizadas en este post puede encontrarlas desarrolladas en
que está disponible en la Librería en Línea de EduBooks.
