Descubriendo CEFEs común el hecho que tendemos a ignorar las cosas que damos por sentado, ya que asumimos su presencia como una constante en el tiempo. Esto aplica innegablemente a muchos aspectos de nuestras vidas, incluyendo el trabajo. En este artículo tengo la intención de describir la historia y las razones detrás de Cisco Express Forwarding (CEF), sus mecanismos internos, cómo lleva a cabo sus tareas y por qué no debemos darlo por sentado.

 

Ya que no podemos -o no debemos- saltar justo hacia la parte más profunda de la piscina sin mojarnos los pies primero, nivelarnos ayudará a que nos sincronicemos en la página. Comencemos calentando los motores antes de que comience la carrera.

 

Preparando el escenario: Proceso de Switching


Antes de poner a CEF bajo la lupa y explorar sus engranajes internos, es ventajoso que comencemos examinando de forma apropiada el proceso de forwarding en un router. El proceso puede ser descrito -generalmente- como en la imagen debajo.


FP8-2.png

Figura 1 - Proceso de forwarding en un router


Como se representa arriba, existen varios pasos que deben seguirse para que un router pueda reenviar un paquete. El proceso puede ser descrito de la manera siguiente:


  1. El router recibe una trama, y para asegurarse de que puede trabajar con ella, revisa el frame check sequence de la trama que recibió. Si algún error es hallado, la trama es descartada.
  2. Si el chequeo de FCS es positivo, el router entonces revisa el campo Ethernet type para saber qué tipo de paquete es y extrae el paquete.
  3. Una vez que el paquete ha sido extraído, la siguiente acción depende de la versión del paquete: si es IPv4, el header checksum es verificado; un paquete con un checksum erróneo es descartado. Si el paquete es IPv6, la revisión no se realiza debido a que el header de IPv6 no contiene un checksum.
  4. El router revisa si la dirección de destino del paquete coincide con alguna de las direcciones IP configuradas en sus interfaces que se encuentren en el estado “up, line protocol up”. Si hay alguna coincidencia, entonces el router es el destino del paquete y este es procesado de manera local.
  5. Si la dirección de destino no coincide con ninguna de las interfaces del router en modo “up, line protocol up”, entonces el juego del enrutamiento comienza. Pero para que eso suceda, el TTL del paquete debe ser mayor que 1. Si lo es, entonces puede ser enrutado; si campo TTL no contiene un valor mayor que 1, entonces es descartado y su remitente notificado con un mensaje ICMP Time Exceeded.
  6. ¡Hora de enrutar! - El router revisa su tabla de enrutamiento y busca una red -o subred- que coincida de la manera más cercana posible con la dirección de destino del paquete. Esto es llamado “Longest prefix match” en inglés, refiriéndose a una coincidencia con la mayor cantidad de bits posible entre la dirección de destino del paquete y la que se encuentre en la tabla de enrutamiento (de allí el término “longest”).
  7. Una vez que el siguiente salto y la interfaz de salida han sido encontrados en la tabla de enrutamiento, el router necesita la información data link del siguiente salto para poder construir una trama nueva y así entregar el paquete. El mismo se apoya en mecanismos como ARP -hay muchos otros- para relacionar información de capa 3 con información de capa 2.
  8. Como el paquete será enrutado, el TTL es reducido por una unidad, y como una consecuencia, el contenido del header IPv4 ha cambiado (TTL). por lo tanto, el checksum IPv4 es recalculado. En el caso de IPv6, se resta una unidad al valor “hop count” del header sin necesidad de recalcular checksum, porque el header no lo contiene.
  9. Finalmente, el router encapsula el paquete -ya procesado- dentro del header y trailer de data link recién creados... ¡ZAS! ¡Tenemos una trama nueva recién sacada del horno para entregar y estamos listos para enviarla!


Luego de examinar el proceso de reenvío, podemos reconocer que hay muchos pasos involucrados en mover un paquete entre dos puntos de una red. Es beneficioso entenderlo para que así podamos comprender qué se hizo para mejorarlo y las razones que impulsaron estas acciones.
¿Dónde comenzamos? O mejor dicho: ¿Cuándo?


Todo comenzó en un pasado no muy distante, justo a la vuelta de la esquina. Abordemos la máquina del tiempo y fijemos curso hacia finales de los años 80 y principios de los 90, donde no había routers enormes rebozando recursos, line cards lujosas ni operaciones aceleradas por hardware. Todo era un asunto de usar el poder de procesamiento sabiamente y ahorrar ciclos de CPU para momentos difíciles.

 

Process switching


A finales de los años 80, process switching era el primero y el más simple de los mecanismos usados para llevar a cabo el envío de paquetes en redes. El proceso de forwarding era ejecutado paquete por paquete por el CPU del router, desde el momento en el que el paquete era recibido por una interfaz hasta que era enviado a través de otra. En pocas palabras: process switching no era más que ejecutar el proceso de 9 pasos descrito anteriormente una y otra vez por cada paquete recibido, con este procedimiento siendo implementado como un proceso individual corriendo en el sistema operativo del router.
En el proceso descrito arriba, el router pasaria la mayoria del tiempo en un par de pasos: primero recorriendo la tabla de enrutamiento buscando la dirección de destino del paquete, encontrando el siguiente salto y la interfaz de salida (posiblemente a través de recursión), y luego buscando la dirección física del siguiente salto (mecanismos como ARP para relacionar direcciones de capa 3 con direcciones de capa 2 eran clave en este paso). Por lo tanto, mejorar el rendimiento y disminuir la latencia del enrutamiento y switching de los paquetes eran metas que apuntaban a mejorar el proceso y hacerlo lo más eficiente posible.


El proceso de enrutar un paquete involucra pequeños pero importantes cambios en la información de su header. Desde un punto de vista muy general, si miramos un paquete completamente encapsulado en una trama antes y después de ser reenviado por un router, el cambio más importante yace en el header de capa 2 (Data link). Construir un nuevo header para la trama es comúnmente llamado frame rewrite, ya que describe lo que esencialmente sucede: reescribir el header de la trama basándose en información conocida sobre el siguiente salto del paquete y como enviarlo consecuentemente. Buscar la información necesaria para realizar el frame rewrite es una de las tareas más demandantes de recursos de todo el proceso de reenvío, y tener que realizarla cada vez que un paquete era recibido era simplemente, ineficiente.
Ejecutar todos estos pasos por cada paquete recibido era una carga y se volvió un proceso difícil de mantener a lo largo del tiempo cuando el rendimiento de las redes aumentaba. El tamaño y la velocidad de las redes pasaron factura cuando las demandas fueron acelerándose y los routers se volvieron cuellos de botella incapaces de adaptarse al crecimiento.


“Felicidades, es un... “ ¿Fast switching? - ¡Nació!


Fast switching


En los sistema de computación, una de las maneras de abordar algoritmos cuya eficiencia se desea mejorar es por medio de caching: hacer uso de una solicitud calculada anteriormente y almacenándola para proporcionar información más rápido a una solicitud en el futuro con el mismo conjunto de valores de entrada (inputs). Fast Switching permitía que los paquetes siguieran el paradigma “route once, switch many times” haciendo uso de un caché on-demand, donde el primer paquete de una solicitud era “process-switched y los resultados de sus búsquedas eran almacenados en caché y luego utilizados para paquetes posteriores, reduciendo así el tiempo de cálculo y apuntando a optimizar el consumo de recursos. Cuando un paquete era recibido en una interfaz, su dirección de destino era primero buscada en el caché. Si el caché contiene alguna coincidencia, la información de envío almacenada allí sería usada para enrutar el paquete inmediatamente. Si no, el paquete será procesado, y sus resultados añadidos al caché para usos futuros.


¿Qué contendría este caché? La información almacenada en el caché incluiría la dirección IP de destino, información del siguiente salto e información del header de capa 2, la cual sería escrita en la trama antes de enviarla a través de la correspondiente interfaz de salida. Cualquier paquete subsecuente hacia el mismo destino tendría la información lista y presta, sin necesidad de procesar nuevamente los paquetes.


Aunque Fast Switching fue una mejora indiscutible, también tuvo desventajas significativas: Si la cantidad de paquetes que el router recibiese sufriera un aumento súbito y estos paquetes fuesen dirigidos a destinos que aún no estaban en el caché, el mismo tendría que ser construido para todas ellas. El router regresaría en el tiempo y ejecutaría process-switching para todos los paquetes, disminuyendo así las ventajas que Fast Switching podría brindar. Más allá de eso, donde quiera que la tabla de enrutamiento, o las tablas de mapeo entre direcciones de capa 3 y capa 2 fueran actualizadas, las entradas que estuviesen en el caché tendrían que ser removidas, ya que estarían desactualizadas. Los paquetes iniciales a esos destinos afectados serían procesados nuevamente. Adicionalmente, load sharing en Fast Switching era muy limitado: cuando una entrada para un nuevo destino era creada en el caché, el router recordaba exactamente la interfaz de salida para ese paquete. Todos los otros paquetes hacia el mismo destino coincidirían con la misma entrada en el caché, y por lo tanto, serían enviados a través de la misma interfaz que fue terminada cuando el primer paquete fue procesado.
Eventualmente, se hizo evidente que aunque Fast Switching fue una mejora para la situación previa, aún no era capaz de mantener el ritmo en el que las redes estaban evolucionando en esos días. En 1996, un nuevo mecanismo fue creado para superar las limitaciones de Fast Switching y brindar mejoras a las redes.


Cisco Express Forwarding


Almacenando caché y reutilizando resultados calculados anteriormente es una forma muy efectiva para mejorar inmediatamente el rendimiento de un algoritmo. Sin embargo, crear las entradas en el caché aún podría ser intensivo de computar, y ese era uno de los puntos débiles de Fast Switching. Eventualmente, para exprimir aún más el rendimiento de routers basados en software, e incluso hacer este proceso más simple de implementar en hardware, era necesario pensar nuevamente el proceso de enrutar paquetes de forma íntegra. Para entender cómo las limitaciones fueron superadas, debemos comprender dónde había espacio para mejorar en la forma en la que el proceso era ejecutado. Entre todas las tareas, las más intensas a nivel de recursos son: encontrar el mejor camino para llegar a una cierta red destino -incluyendo interfaz de salida- y construir el nuevo data link header, mejor conocido como frame rewrite.


Búsqueda en la tabla de enrutamiento


Revisemos nuevamente las características de Process Switching. Para encontrar el mejor camino a una red destino de un paquete, el router tenía que recorrer su tabla de enrutamiento, también llamada Routing Information Base (RIB), y encontrar la ruta que mejor coincidiese con la dirección de destino del paquete. La regla para la búsqueda era el longest prefix match - encontrar la entrada en la RIB que, comparada con otras entradas, coincidiría con la dirección del paquete en una línea de bits más larga, comenzando por el bit más alto. Sin embargo, una barrida de la RIB podría no ser suficiente. Si la RIB solo contenía el siguiente salto pero no la interfaz de salida, el barrido tendría que repetirse - esta vez buscando la dirección del siguiente salto. Este proceso tenía que ser repetido hasta que el router encontrase una entrada en la RIB que apuntase a una red directamente conectada. Este proceso de búsqueda podría tomar muchas iteraciones para poder completarse, y aun cuando el siguiente salto y la interfaz de salida por fin eran encontrados, la tabla de enrutamiento no contendría la información para ejecutar el frame rewrite de ese paquete. Solo luego de construir el nuevo header de la trama usando la tabla de ARP, o cualquier otro tipo de tabla que relacionase la dirección del siguiente salto con su dirección de capa 2, el paquete - finalmente - podía ser enviado. Es importante recordar que este proceso debía ser repetido por todos y cada uno de los paquetes.


¿Como se mejora esto? Tengamos en cuenta que las búsquedas en la RIB son ineficientes: la tabla de enrutamiento debía ser ordenada de acuerdo al largo de los prefijos, para que todas las redes con prefijos /32 de largo estuviesen siempre en el tope, luego todas las redes con prefijos /31, seguidas de todas las redes con prefijos /30 y así, hasta que finalmente, la ruta por defecto (la única posible con longitud de prefijo /0) sería colocada al fondo de la tabla. Realizar una búsqueda en la tabla significaba recorrerla desde arriba, entrada por entrada, calculando el AND binario entre la dirección de destino del paquete y la máscara de red en la entrada de la RIB, y comparando el resultado con la dirección de red en la entrada, deteniéndose al encontrar la primera coincidencia. Ya que se asume que la tabla estaba ordenada desde las redes más específicas hasta las menos específicas, la primera coincidencia al recorrer la tabla de arriba a abajo era automáticamente el “longest prefix match”. En el peor de los casos, el router necesita inspeccionar cada una de las entradas en la tabla de enrutamiento antes de encontrar una coincidencia - solo imaginen tener 500.000 entradas en la RIB, y recibir un paquete cuya única coincidencia es la ruta por defecto en el fondo de la tabla. Como si eso no fuese suficiente, si la entrada que mejor coincidiese con la red no tuviese información de la interfaz de salida, solo el siguiente salto (un caso típico con rutas estáticas o redes aprendidas por BGP), la búsqueda debía repetirse recursivamente, esta vez con la dirección del siguiente salto y así encontrar la interfaz de salida. La tabla de enrutamiento es un componente hecho para construir y almacenar información de redes, no está realmente optimizado para búsquedas. Para optimizarlo, debemos cambiar su estructura lineal a algo más eficiente para realizar búsquedas más rápido, y deshacernos de la recursión. Una estructura que satisfaciendo estos requerimientos, está verdaderamente optimizada para búsquedas, está separada de la RIB a pesar de estar poblada con sus contenidos, y se llama Forwarding Information Base (FIB).


La FIB es una base de datos creada dinámicamente usando la información contenida en la tabla de enrutamiento: prefijos o direcciones de destino son copiados y sus siguientes saltos resueltos de forma recursiva. ¿Por qué esto tiene sentido? La meta es encontrar toda la información para reenviar el paquete en una sola búsqueda.


Pero, ¿qué hace a la FIB diferente de la RIB? A diferencia de la RIB, cuyo propósito es construir y almacenar información sobre redes, la FIB está construida y ordenada en una manera que le permite optimizar la búsqueda rápida de información y el longest prefix match. Esta estructura es llamada trie, una estructura de datos similar a un árbol, lista para ser recorrida, compuesta de nodos y hojas, y se concentra en obtención rápida de datos.



Trie.png
Figura 2 - Ejemplo de un Trie


Un trie está compuesto de un nodo raíz o root, nodos hijos o child nodes y llaves o keys. El root es el punto de entrada donde comenzamos a recorrer el árbol, este nodo tiene apuntadores o enlaces a otros nodos, los child nodes. A diferencia de los árboles comunes en los cuales un nodo particular almacena la llave completa, un trie almacena una llave (una palabra o un número) dividiéndola en letras o dígitos, y creando un nodo para cada letra o dígito en niveles inferiores del árbol de forma progresiva. La llave completa es, por lo tanto, buscada letra por letra, o dígito por dígito - ¡Tengamos en cuenta el procedimiento orientado a los prefijos (bit por bit)!


Cada nodo en el trie podría contener un flag indicando si la palabra creada siguiendo el camino hacia abajo desde el root e incluyendo este nodo representa una palabra completa. Este flag es llamado terminal flag, si el mismo está habilitado, el nodo es llamado terminal node. Un terminal node no es necesariamente una hoja o leaf localizada al final de una rama del árbol - podría ser un nodo interno también. Como ejemplo, en la Figura 2, en la rama representando la palabra SHELLS, hay tres palabras válidas y por lo tanto tres nodos terminales: SHE, SHELL, SHELLS, con sus nodos terminales resaltados. Observen como los terminal nodes en la rama SHELLS definen los prefijos de esta palabra como palabras completas en sí mismas - SHE, SHELL, SHELLS. Cada terminal node en la Figura 2 tiene un número distinto de cero asignado; discutiremos el significado de este número en un momento.
Realizar una búsqueda en un trie sigue un algoritmo simple, usando el término current node o nodo actual para denotar el nodo al que acabamos de llegar durante nuestro recorrido en el trie:


  1. Definir el nodo actual en el root node.
  2. Si el nodo actual es un terminal node, recordarlo, olvidando cualquier otro terminal node encontrado previamente.
  3. Intentar descender desde el nodo actual hasta el child node que coincida con la siguiente letra o dígito de la llave que buscamos.
  4. Si no existe tal child node, DETÉNGASE. El terminal node más reciente encontrado representa el longest prefix match para la llave. En caso contrario, de existir el child node, definirlo como el current node o nodo actual, y regresar al paso número 2.


Trie3.png
Figura 3 - Buscando un string en un trie


  • Comenzamos en el root node (paso 1). El root node no es un terminal node (no tiene un valor distinto de cero), así que no mantenemos algún registro del mismo (paso 2). Tomando la primera letra sin procesar de la palabra SHELTER, intentamos encontrar un child node del nodo actual para la letra S (paso 3), y como el child node existe, descendemos hacia él y lo definimos como nuestro nuevo nodo actual o current node. (paso 4, retornando al paso 2).
  • El nodo actual (letra S) no es un terminal node, así que no mantenemos algún registro del mismo (paso 2). Tomando la primera letra sin procesar de la palabra SHELTER, intentamos encontrar un child node del nodo actual para la letra H (paso 3), y como el child node existe, descendemos hacia él y lo definimos como nuestro nuevo nodo actual o current node. (paso 4, retornando al paso 2).
  • El nodo actual (letra H) no es un terminal node, así que no mantenemos algún registro del mismo (paso 2). Tomando la primera letra sin procesar de la palabra SHELTER, intentamos encontrar un child node del nodo actual para la letra E (paso 3), y como el child node existe, descendemos hacia él y lo definimos como nuestro nuevo nodo actual o current node. (paso 4, retornando al paso 2).
  • El nodo actual (letra E) es un terminal node, asi que lo recordamos (paso 2). Tomando la primera letra sin procesar de la palabra SHELTER, intentamos encontrar un child node del nodo actual para la letra L (paso 3),  y como el child node existe, descendemos hacia él y lo definimos como nuestro nuevo nodo actual o current node. (paso 4, retornando al paso 2).
  • El nodo actual (letra L) no es un terminal node, así que no mantenemos algún registro del mismo (paso 2). Tomando la primera letra sin procesar de la palabra SHELTER, intentamos encontrar un child node del nodo actual para la letra T (paso 3). Sin embargo, el child node no existe. La búsqueda termina aquí (paso 4), y el longest prefix match producido por esta búsqueda es la palabra SHE que termina en el terminal node más reciente que hemos encontrado.


Trie9.png

Figura 4 - Encontrando un terminal node


Hasta ahora, no hemos mencionado el significado de los números indicados en los terminal nodes. La verdad es, que pueden ser cualquier cosa - son los valores que estamos tratando de accesar por medio de la búsqueda que realizamos usando las llaves. Para nuestros propósitos, ellos representarán apuntadores o pointers a objetos (valores) almacenados en algún sitio en la memoria que se encuentra indexada por las llaves en el trie. De hecho, algunos documentos insisten en que un trie no debe contener los valores asociados con las llaves en los nodos mismos, sino que solo deben apuntar hacia ellos. Esta no es una descripción correcta de un trie; sin embargo, muchas implementaciones de tries solo usan pointers hacia los valores dentro de los nodos, en lugar de colocar los valores mismos en los nodos, ya que esto tiene muchas ventajas desde la perspectiva del desarrollo de software.


¿Cómo se aplica esto a las redes y a la búsqueda de prefijos? Con direcciones IP de destino en los paquetes y una tabla de enrutamiento clásica, siempre estamos tratando de encontrar en nuestra tabla la ruta que mejor coincida con la dirección de destino, haciendo uso de la regla del longest prefix match. Con un trie, la idea es almacenar el prefijo de cada destino conocido de la RIB en la FIB de una manera que nos permita enfocarnos en cada bit, un nivel en el trie por cada bit del prefijo. Ya que un prefijo IPv4 tiene como máximo 32 bits de largo, la profundidad del trie será, cuando mucho, de 32 niveles (33 si contamos el root node). Como resultado de ésto, realizar la búsqueda del longest prefix match con la red IP destino de algún paquete tomaría cuando mucho 32 comparaciones en el trie, sin importar cuantos prefijos diferentes sean almacenados en el mismo. Esto es una mejora enorme sobre una tabla de enrutamiento lineal donde el número de comparaciones era proporcional al número de prefijos almacenados. La búsqueda en el trie sería realizada exactamente de la misma manera: seguimos el camino hacia abajo desde el root hasta el fondo como lo hicimos antes, pero esta vez, usaremos números binarios en lugar de letras, comparando un bit a la vez. ¿Cómo luciría si estamos revisando los bits de un octeto? Haciendo los arreglos necesarios obtenemos la estructura representada en la Figura 5.


En aras de brevedad la figura representa la comparación de bits entre el primer y cuarto bit de un octeto. La llave que buscamos sería la expresión binaria 11100001. Si la transformamos en una expresión decimal, nuestro número sería 225. En la Figura 5, asumimos que el trie contiene una coincidencia perfecta para los 8 bits; sin embargo, sería más simple imaginar como la búsqueda se realizará si el trie contuviese un prefijo más corto, por ejemplo, sólo los bits del comienzo 1110.

 

Trie5-2.png

Figura 5 - Buscando bits en un trie


Pero, ¿qué sucede si la red no existe en el trie y no encontramos un terminal node al buscar? La respuesta astuta es: el root tambien puede ser un terminal node, en tal caso, representaría una ruta por defecto. Todas las búsquedas de redes de destino comenzarán por el root. Si no hay algun terminal node al cual podamos descender en el trie, el terminal node más reciente que habíamos encontrado sería el root - ¡en cuyo caso sería la ruta por defecto! Astuto, ¿verdad?  


Ahora que hemos encontrado el longest prefix match en nuestro trie, exactamente ¿qué sucede ahora? Recordemos que nuestra meta era encontrar la ruta que mejor coincidiera con la red destino del paquete para saber cómo reenviarlo. Saber cómo reenviar el paquete significa que sabemos cual es la interfaz de salida y la dirección de capa 2 (Data link) del siguiente salto - el frame rewrite mencionado anteriormente. Esta información de reenvío es el valor que estamos tratando de buscar en el trie, usando el longest matching prefix como nuestra llave de búsqueda. Dicha información puede ser almacenada en los terminal nodes del trie, pero debido a varias ventajas, es mejor almacenar esta información en una tabla separada. Y hacer que los terminal nodes simplemente apunten a los elementos de esta tabla.


Damas y caballeros, abramos paso a nuestro invitado de hoy - Adjacency table hace su aparición!

 

Adjacency table


Un router puede saber sobre miles o cientos de miles de destinos en su RIB/FIB, pero solo tendrá un número pequeño de vecinos. Necesariamente, muchas entradas de la RIB/FIB usarán la misma información de reenvío (forwarding information) - el mismo siguiente salto, la misma interfaz de salida, el mismo frame rewrite. En mecanismos previos de switching, el forwarding information o no se almacenaba, y por lo tanto debía ser recolectada para cada paquete enrutado, o era cacheada (para cada destino).


Sin embargo, un router inteligente puede pensar con antelación. Con la RIB poblada, el router ya sabe las direcciones IP de cada siguiente salto. Puede comenzar a preparar la información de reenvío completa - interfaz de salida, frame rewrite - incluso antes de que los paquetes empiecen a fluir. Toda la información necesaria ya se encuentra disponible: los siguientes altos son conocidos por la RIB, y sus direcciones de capa 2 (Data link) pueden ser obtenidas a través de mecanismos que relacionan direcciones de capa 3 con direcciones de capa 2 (ARP y otras tablas similares). La información completa para el reenvío puede ser compilada y luego colocada en una base de datos separada llamada adjacency table.


La Adjacency table es una tabla que mantiene, como era de esperarse, la lista de todas las adjacencies conocidas por el router. En este sentido, una adyacencia es la información de reenvío completa para un vecino directamente conectado: la interfaz de salida hacia el vecino, y la información completa del header de capa 2 que puede ser usado para enviar paquetes a ese vecino. Podría haber otras informaciones adicionales o de administración incluidas, pero la interfaz de salida y el frame rewrite son la mínima información disponible.


Para ilustrar lo que la adjacency table contiene, consideremos la siguiente topología: los routers R1, R2 y R3 son adyacentes entre ellos, y R3 también es adyacente con 3 computadores de usuarios finales. Hay una subinterfaz entre R2 y R3 y una interfaz sin sin etiquetar (untagged) entre R3 y los usuarios finales.

ADJ2.png

Vamos a enfocarnos solo en R3 en aras de brevedad. Como fue explicado anteriormente, la tabla de adyacencias podría contener información ya preparada de otras tablas para que los paquetes puedan ser reenviados rápidamente.

 

Identificando las interfaces de R3 podemos obtener sus direcciones MAC:


R3# show int Ethernet2/5 | in address

  Hardware is AmdP2, address is ca03.20a4.003d (bia ca03.20a4.003d)

  Internet address is 192.168.3.254/24

R3# show int Ethernet1/3 | in address

  Hardware is AmdP2, address is ca03.20a4.001f (bia ca03.20a4.001f)

  Internet address is 10.10.13.3/24

R3# show int Ethernet2/3 | in address

  Hardware is AmdP2, address is ca03.20a4.003b (bia ca03.20a4.003b)

  Internet address is 10.10.23.3/24


Revisando la tabla ARP:


R3# show ip arp | ex -

Protocol  Address Age (min) Hardware Addr  Type Interface

Internet  10.10.13.1    12  ca01.4a40.001f  ARPA  Ethernet1/3

Internet  10.10.23.2    12  ca02.2904.003b  ARPA  Ethernet2/3

Internet  192.168.3.1  183  0050.7966.6800  ARPA  Ethernet2/5

Internet  192.168.3.2  192  0050.7966.6801  ARPA  Ethernet2/5

Internet  192.168.3.3  216  0050.7966.6802  ARPA  Ethernet2/5

Internet  192.168.23.2  19  ca02.2904.003b  ARPA  Ethernet2/3.100


Las entradas marcadas en rojo son routers, y las marcadas en azul son los usuarios finales. ¿Qué contendrá la adjacency table si fuésemos a enrutar paquetes desde R3 hacia alguno de los usuarios finales?


R3# show adjacency detail

Protocol Interface          Address

<omitted for brevity>

...

IP      Ethernet2/5        192.168.3.3(7)

                            0 packets, 0 bytes

                            epoch 0

                            sourced in sev-epoch 0

                            Encap length 14

                            005079666802CA0320A4003D0800

                          ARP


La información proporcionada arriba corresponde con una información de capa 2 preconstruida, dispuesta para el router y lista para usar.


Descompongamos el grupo de números para entenderlos mejor:


005079666802 - Dirección MAC de destino - dirección MAC de PC3

CA0320A4003D - Dirección MAC de origen - dirección MAC de la interfaz Eth2/5

0800 - Ethertype del paquete


Genial ¿verdad?


Ahora, ¿Qué sucedería si la comunicación fuese a través de una subinterfaz? ¿Qué estaría disponible para nosotros en la tabla?


Buenas noticias: ¡Podríamos ver incluso el VLAN tag! ¡Revisémoslo!


R3#show adjacency detail

Protocol Interface              Address

<omitted for brevity>

...

IP      Ethernet2/3.100        192.168.23.2(7)

                                0 packets, 0 bytes

                                epoch 0

                                sourced in sev-epoch 0

                                Encap length 18

                                CA022904003BCA0320A4003B81000064

                                0800

                                ARP


CA022904003B -  Dirección MAC de destino - dirección MAC de la interfaz Ethernet 2/3 de R2

CA0320A4003B - Dirección MAC de origen - dirección MAC de la interfaz Ethernet 2/3 de R3

8100 - Ethertype del header 802.1Q

0 - Class of Service (0) y Discard Eligibility Indicator (0)

064 - VLAN Tag - 100 (064 en Hexadecimal = 100 en decimal)

0800 - Ethertype del header original de capa 2


Como fue mostrado anteriormente, la adjacency table contendrá lo que el router necesita para poder reenviar paquetes. Los casos anteriores cubrieron interfaces con tag y sin él y sus tramas preconstruidas listas para usar en la tabla. ¿Qué estaría preparado para el router si hay una interfaz túnel habilitada? ¡Parece que tenemos tarea que hacer!


La FIB y la adjacency table son los componentes claves de Cisco Express Forwarding, y ahora sabemos su propósito. La FIB contiene todos los prefijos IP conocidos por la RIB, organizados para búsquedas rápidas. Una búsqueda en la FIB usando la dirección IP destino del paquete como una llave nos proporciona un pointer hacia la adjacency table, la misma contiene headers de tramas preconstruidos para cada siguiente salto, con la intención de ser usados de manera instantánea en el paquete, y así ¡el paquete está listo para volar!


Como una observación final: La FIB puede ser implementada tanto en hardware como en software. En software la FIB es implementada utilizando la estructura de datos (trie) que hemos discutido. En hardware, la FIB es implementada utilizando Ternary Content Addressable Memory ASICs (TCAM) - pero eso será quizá tema para otro artículo

 

Conclusión


A lo largo de este artículo, hemos aprendido sobre CEF, un mecanismo creado para mejorar el reenvío de paquetes, dirigido a optimizar tareas que son demandantes de recursos dentro del proceso de reenvío. CEF está compuesto por dos elementos: la FIB ya la adjacency table. Este blog se escribió para explorar su esencia y mecanismos internos, y para develar su lógica y beneficios sin caer en bombos y platillos. Sin embargo, hay mucho más que visitar y detallar sobre ello. Artículos en futuro pueden abarcar métodos de optimización y características para mejorar el rendimiento y exprimir el máximo de CEF. Cualquier opinión,comentario o feedback es bienvenido!



Referencias


Cisco CCIE Routing and Switching v5.0 Official Cert Guide, Volume 1

Paluch Peter, Kocharians Narbik - Chapter 6 , pp. 267-282.


Cisco Express Forwarding - Cisco Press

    Stringfield Nakia , White Russ, McKee Stacia - Chapters 2 and 3 , pp. 51-101.


https://brilliant.org/wiki/tries/


https://www.cs.cmu.edu/~avrim/451f11/recitations/rec0921.pdf


https://algs4.cs.princeton.edu/lectures/52Tries.pdf


http://ellard.org/dan/www/libsq/cb_1998/c06.pdf


https://www.geeksforgeeks.org/trie-insert-and-search/

https://patents.google.com/patent/US6308219B1/en

https://null.53bits.co.uk/index.php?page=tree-trie

 

Versión en inglés: Demystifying CEF