All path/Arp path

All-path es una nueva familia de puentes (bridges) transparentes Ethernet que encuentra caminos óptimos entre hosts, o entre puentes, por exploración instantánea de la red mediante la inundación y carrera entre las réplicas de una trama de difusión (broadcast) . ARP-path es el primer protocolo de la familia de puentes All-path y aprovecha los paquetes estándar ARP-Request y ARP-Reply para ello. En lugar de calcular las rutas sobre el grafo de la red mediante un algoritmo de camino mínimo como el de Djikstra, explora directamente la red real.

Path set up in a data center network of ARP Path switches

Introducción

All-path utiliza un mecanismo de prevención de bucles basado en el aprendizaje de la dirección MAC origen de la trama recibida asociándola al primer puerto del puente por el que se recibe el mensaje. La peculiaridad de esta tecnología es que únicamente realiza el aprendizaje en el primer puerto que recibe el mensaje, bloqueando el aprendizaje de esa dirección durante un tiempo, siendo por ello descartadas desde ese momento las tramas con esa misma dirección origen recibidas en los demás puertos, durante un corto periodo de tiempo, lo que permite explorar simultáneamente todos los enlaces de la red y construir caminos de latencia mínima.

Antecedentes^[1]​

Los protocolos actuales de encaminamiento en capa dos enlace del modelo modelo OSI, son los siguientes:

Shortest Path Bridges ha conseguido superar las limitaciones del protocolo Spanning tree en redes conmutadas (switched networks), las cuales evitaban la formación de bucles creando una topología en árbol a costa de inhabilitar enlaces todos los enlaces redundantes de la red. Para ello utilizan un protocolo de enrutamiento de estado de enlaces como IS-IS de nivel 2 para conseguir calcular los caminos más cortos (de menor coste) entre puentes, por lo tanto el descubrimiento de nuevos caminos se realiza mediante computación.

Un problema clásico de las redes conmutadas mediante algoritmos de enrutamiento es la saturación de ciertos enlaces, mientras que enlaces secundarios se encuentran infrautilizados. Esto se debe a que la asignación de caminos se basa en parámetros orientados a escoger el camino más corto o con menor coste, sin contar con la carga del enlace. Es por ello, que necesitamos un mecanismo de equilibrado de carga que nos permita equilibrar la carga entre enlaces, evitando la saturación de estos. Debido a que un mismo camino puede estar compartido por un gran número de hosts, utilizando los algoritmos de enrutamiento anteriores tenemos una gran carga computacional.

El protocolo que tratamos en esta entrada presenta un mecanismo de descubriendo de caminos óptimos mediante la transmisión de una trama arp request (u otra trama de difusión broadcast). De tal manera que el puente bridge, únicamente aprenderá la dirección MAC origen y puerto por el que ha sido recibida la primera trama, bloqueando el aprendizaje de esa dirección MAC en el resto de puertos y descartando cualquier trama recibida de esa dirección origen durante un corto intervalo de tiempo, evitando la aparición de tormentas de tramas producidas por los bucles de reenvío de tramas.

Exploración de caminos frente a cálculo de caminos^[2]​

Short Path Bridges (SPB)^[3]​ y Routing Bridges (TRILL)^[4]​ son dos estándares aprobados en 2012, que buscan conseguir la construcción de redes conmutadas de gran tamaño organizadas como una única subred ip, pero evitando la gestión de direcciones ip. Además tratan de conseguir una plena utilización de la infraestructura de enlaces para obtener los caminos óptimos, en contraposición con el protocolo de árbol de expansión, el cual habilita un árbol dentro de la topología de la red y bloquea todos los enlaces restantes (redundantes) para evitar la formación de bucles de tramas.

El enrutamiento básico de ambas redes (diferenciándose en algunos aspectos) se basa en la creación de bridges transparentes e híbridos que permiten calcular los caminos óptimos apoyándose en un protocolo de enrutamiento de caminos mínimos. SPB y TRILL usan una variante del protocolo de enrutamiento de estado de enlaces IS-IS a nivel 2. Esta forma de enrutamiento presenta ciertos problemas, en términos de computación e intercambio de mensajes de control, debido a la alta carga computacional que han de soportar los bridges para realizar los cálculos de caminos óptimos y la necesidad de mecanismos de control adicionales que garanticen la consistencia en las bases de datos de todos los puentes.

Una alternativa que tratar de solventar los problemas anteriores es all-path.

All-path ofrece un enfoque distinto, fundamentándose en la simplicidad y en la compatibilidad con las arquitecturas ya implementadas y basándose en el establecimiento de caminos óptimos, sin implementar protocolos de encaminamiento externo. Se basa en el descubrimiento mediante difusión broadcast, aprendiendo únicamente la dirección MAC origen de la trama que recibe primero el bridge y descartando posibles tramas duplicadas. Es por esto que se establece el camino entre bridges que son alcanzados primeros por la trama, esto es, se forma el camino con menor latencia entre nodos.

Una gran ventaja que ofrece all-path es que basa la asignación de caminos en función de la latencia entre nodos, por lo que se adapta perfectamente a situaciones de equilibrado de carga, o fallos en un bridge o enlaces. Al igual que los mecanismos anteriores permite utilizar toda la infraestructura de enlaces de la red, no precisa de protocolos de configuración y es adecuado para redes campus, empresariales y de centros de datos.

Por lo tanto, los beneficios que presenta all-path son:^[5]​

• Simplicidad.
• Baja latencia.
• Cero configuración.
• No utiliza cómputo de rutas sobre el grafo de la red
• Equilibra la carga de forma nativa entre caminos alternativos de latencias similares si los caminos se establecen bajo demanda (p.e.: protocolo ARP-Path)

Puentes All-path y puentes estándar

Los All-path bridges son, en esencia, puentes estándar que permiten el reenvío de las tramas de difusión por todos los enlaces modificando el aprendize de direcciones MAC para evitar los bucles de tramas.

Existen 3 diferencias básicas entre all-path bridges y los bridges transparentes:

1. El aprendizaje de la dirección MAC origen de una trama únicamente se produce solamente mediante los paquetes arp request, arp reply o path repair.
2. El aprendizaje de la dirección MAC origen en un puerto bloquea durante un intervalo de tiempo el aprendizaje de dicha dirección MAC en los demás puertos. Por eso, solamente se aprenderá la dirección MAC origen en el puerto que primero reciba la trama ARP Request, las tramas ARP duplicadas recibidas por los otros puertos algo más tarde se descartan por llegar por un puerto distinto al aprendido. Con ello, conseguimos obtener el camino de menor latencia y evitar la formación de bucles.
3. Las tramas unicast desconocidas (cuando el puente no tiene ningún puerto asociado a la dirección MAC destino de la trama recibida) no son reenviadas por todos los puertos como hacen los puentes estándar.

All-path puede interoperar junto a VLANs y demás protocolos basados en etiquetas de capa dos, ya que es totalmente independiente de las VLAN y transparente a ellas.

ARP-path

ARP-path es el primer protocolo de la nueva familia de puentes transparentes definida como all-path bridges. La idea principal es explorar simultáneamente todos los caminos de la red con el paquete ARP-Request estándar, aprendiendo únicamente los de menor latencia. Para evitar la aparición de bucles y asegurar el camino con menor latencia, el puente debe bloquear el aprendizaje en el resto de sus puertos para las tramas que llegan repetidas durante un cierto intervalo de tiempo. ARP-Path pues realiza la selección de caminos a nivel de host y bajo demanda, el camino para cada host se busca cuando es necesario, no antes, aunque una vez seleccionado el camino persiste mediante mecanismos de refresco como en los puentes transparentes estándar. Se adapta bien a redes campus y centros de datos de tamaño medio y pequeño, existiendo otras variedades en esta familia de bridges que se adaptan a las necesidades de redes de mayor tamaño.

Path discovery

En esta sección vamos a estudiar el proceso de formación de caminos óptimos de arp-path. Para ello, se basa en dos mensajes, un mensaje broadcast, arp request, enviado por el nodo que desea crear el camino y un mensaje unicast, arp reply, enviado por el nodo destino del camino.

ARP request

 

Arp Request All-Path

El host S quiere comunicarse con el host D, pero no conoce su dirección ip, por ello difunde un arp request encapsulado sobre una trama broadcast. El bridge 2 recibe la trama y asocia la dirección MAC origen con el puerto por donde ha recibido la trama, bloqueando temporalmente el aprendizaje de la misma dirección MAC en el resto de puertos. Además bloquea el reenvío de tramas repetidas para evitar bucles. Una vez realizada la asociación, transmite la trama por todas las interfaces menos por la interfaz de llegada de la misma.

El bridge 1 y el bridge 3 asocian la dirección origen con el puerto de llegada de la primera trama, reenviándola por el resto de interfaces como en el caso del bridge 2. Por lo que conseguimos aprender una entrada de la dirección MAC origen S en los bridges 1 y 3, descartando las tramas recibidas posteriormente a la primera.

Iterando este proceso conseguimos que la trama arp request enviada por S llegue al host D, creando entradas sobre la base de dirección MAC y puerto en todos los bridges de la figura.

ARP reply

 

Arp Reply All-Path

El host D procesa la petición arp request, y una vez procesada, envía mediante unicast, un mensaje arp reply al host S. El bridge 5 recibe la trama enviada por el host D, y aprende el puerto y la dirección MAC origen de D. Dado que es una trama unicast sólo se reenvía por el puerto asociado a la dirección MAC destino, por lo que sólo se envía hacia el host 3 por el puerto asociado.

El host 3 aprende la dirección MAC origen de D y transmite la trama hacia el bridge 2.

El bridge 2 aprende la dirección MAC origen de D, y reenvía la trama hacia el host S.

De esta forma, el host S ya es capaz de poder comunicarse con el host D, ya que posee su dirección ip, y un camino sin bucles, óptimo y de mínima latencia proporcionado por arp-path.

Las entradas creadas en este apartado han sido la dirección MAC origen del host D en los bridges 2, 3 y 5.

En este punto ya tenemos el camino óptimo creado entre los hosts S y D, en este caso a través de los bridges 2, 3 y 5.

Un aspecto a considerar es que los registros de la dirección MAC origen y el puerto de los bridges, necesitan ser refrescados para poder mantenerlos en memoria. Por lo tanto si no se utiliza un enlace o camino durante un periodo de tiempo fijado, los bridges borrarán los registros de sus direcciones MAC, obligando a la creación de otro camino para una posterior comunicación entre nodos. Es por este motivo que los registros de los bridges 1 y 4 que contienen la dirección MAC origen del host S, al no formar parte del camino asignado terminarán por expirar borrando los correspondientes registros.

La figura muestra la operación del protocolo ARP Path en una red de centro de datos

 

Path set up in a data center network of ARP Path switches

Reparación de camino

Como hemos visto en el apartado anterior un camino establecido puede eliminarse si este no es usado o debido a un fallo o inicialización de un enlace o bridge. Si un enlace que conecta dos bridges falla, todas las direcciones MAC almacenadas en los registros de ambos bridges son borradas ya que no se pueden refrescar sus registros. Una situación similar puede ser que un bridge se reinicie o falle. Por lo tanto se ha de contemplar como poder reconstruir un camino óptimo en estos casos. Cuando un bridge recibe una trama unicast y no es capaz de reenviarla, ya que no tiene la dirección MAC destino en su registro, existen dos posibles soluciones planteadas por arp-path. El camino puede ser reconstruido desde el bridge origen, es decir el bridge frontera que primero recibe la trama desde el nodo emisor, o desde el bridge actual que no es capaz de reenviar la trama. Comenzamos con el primer supuesto.

En este método el bridge encapsula dentro de la trama un mensaje path_fail y retorna la trama al bridge origen. Este mensaje es procesado por cada bridge del camino, hasta que esta llega al bridge origen. Cada bridge del camino debe comprobar si es el origen viendo, por ejemplo, si el nodo está directamente conectado a él. En el caso de ser el bridge origen, realiza una petición arp request en nombre del host origen, reconstruyendo el camino óptimo por los métodos anteriormente expuestos.

Respecto al segundo supuesto.

En este caso el bridge que no es capaz de reenviar la trama unicast se encarga de realizar una petición arp request en nombre del host origen o un mensaje path_request direccionado a la dirección multicast all_fastpath_bridges. En el primer caso la petición arp request es replicada por el host destino con un arp reply, creando un nuevo camino óptimo desde el bridge afectado. En el otro caso, el mensaje path_request contiene la dirección MAC origen y destino, y las direcciones ip, por lo que se transmite hacia delante al resto de bridges transversales, calculando un nuevo camino a partir del bridge afectado.

Coexistencia con standard bridges IEEE 802.1 y 802.1Q

All-path switches deben estar conectados con bridges standard en modo core-island, ya que islas all-path bridges han de estar interconectadas con islas de bridges estándar funcionando con el protocolo Spanning Tree. La autoconfiguración de las islas de bridges standard es la siguiente. Bridges all-path se conectan a bridges standard recibiendo la BPDU (bridge protocol data unit) Rapid Spanning Tree standard en los puertos conectados a estos. Se ejecuta el protocolo RSTP en sus puertos, transmitiendo BPDUs que anuncian el bridge all-path como si tuviera una conexión directa a un bridge root virtual con prioridad máxima. De esta forma se consigue que los bridges all-path sean seleccionados como bridges root por los bridges standard convirtiéndose en el bridge root de los árboles de su entorno.

Una gran ventaja que presenta all-path bridges es que es totalmente independiente de las VLANS, por el contrario de SPB. Dado que arp-path incluye un mecanismo de prevención de bucles, facilita que no sea necesario asignar VLANs para separar dominios de encaminamiento por bridge. Por lo tanto la implementación de las VLANS se realiza de la misma forma que los bridges standard permitiéndonos crear dominios de encaminamientos independientes. Con arp-path podemos lograr mediante VLANs crear una topología virtual completamente independiente y coexistiendo con los protocolos standard en dominios broadcast separados.

Implementaciones de ARP Path

El protocolo básico ARP Path ha sido implementado con éxito en Linux, en Openflow (validado sobre switches SDN) y en las tarjetas NetFPGA.

Recientemente, se ha implementado en el lenguaje P4, ^[6]​ lenguaje que especifica de forma independiente del equipo en que se implemente, cómo un switch o router procesa los paquetes. Esto permite la implementación en dispositivos diversos, desde un ASIC a un switch software. ^[7]​

Evolución y variantes

La primera variante del protocolo arp-path asigna los caminos a nivel de host. Se adapta bien a redes campus y redes de centros de datos de tamaño mediano o pequeño, existiendo otras variantes en la nueva categoría de bridges que nos permitan satisfacer las necesidades de redes de mayor tamaño.

Una segunda variante de esta familia es flow-path. Conceptualmente se diferencia respecto a arp-path en que en lugar de asociar dirección MAC de origen y el puerto en los all-path bridges, en este caso se va a asociar dirección MAC origen, dirección MAC destino y el puerto para de esta forma poder crear caminos sobre la base de flujos. Esta variante está encaminada para garantizar la congruencia de caminos en todo tipo de situaciones y conseguir un granularidad suficiente para mejorar la distribución de carga en servidores.

La tercera variante es path-moose una variante simple y escalable que combina el descubrimiento de caminos con arp-path, a nivel de bridge, con el direccionamiento jerárquico de bridges de la forma bridgeID:hostID. Cada host es asignado una dirección jerárquica privada por los bridges frontera. Estos llevan a cabo un NAT de direcciones MAC de los hosts conectados directamente al bridge a una dirección jerárquica. Path-moose bridges utiliza el mecanismo de arp request únicamente para conocer el bridgeID, evitando tener que conocer todas las direcciones de los host. De esta manera se crea una estructura en árbol, uno por cada bridge frontera. Estos árboles sirven como camino con destino unicast para todos los hosts conectados bajos un mismo árbol.

Por último vamos a comentar una última variante, MAC in MAC all-path. Esta variante es especialmente útil para redes donde la simplicidad y la capacidad de recuperación son más importantes que una asignación de caminos predecibles, ya que basamos los caminos en la latencia. Mac in Mac all-path es capaz de asignar árboles instantáneamente mediante el envío de una trama multicast B_Set_Tree. Los bridges backbone confirmarán esta trama mediante el envío de un mensaje ack en cada salto para garantizar la simetría en el camino.

Protocolos posteriores inspirados en ARP-Path

El empleo de tramas de difusión se ha aplicado recientemente al descubrimiento de caminos múltiples disjuntos ^[8]​ mediante descubrimiento iterativo de caminos disjuntos entre dos nodos inundando tramas multidifusión. Una versión más sofisticada y optimizada ^[9]​ realiza este descubrimiento de caminos múltiples disjuntos mediante una sola exploración. Hay que destacar que el cálculo de estos caminos si se realiza de forma convencional, por cálculo sobre el grafo de la red, es de una gran complejidad computacional.

Conclusiones

All-path muestra los beneficios que podemos conseguir implantando mecanismos de descubrimiento de rutas mediante inundación de tramas broadcast. De esta manera evitamos tener que recurrir a mecanismos de enrutamiento externos. Gracias a la asignación de caminos en función de la latencia, evita la retroalimentación de cuellos de botella en los enlaces, y por lo tanto aumentar la eficiencia de estos. Como contrapartida, dado que la latencia depende de la carga del enlace y esta es variable, no se adapta tan bien como otras tecnologías en la toma de caminos predecibles.

El mecanismo de inundación de tramas para descubrir rutas es de aplicación general para descubrir caminos múltiples disjuntos mediante exploración de la red, en vez de complejos.

Referencias

1. Ibañez, G., Carral, J.A., Arco, J.M., Rivera, D., Montalvo, A. ARP-Path: ARP-based, Shortest Path Bridges. http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=5871399&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F4234%2F5952297%2F05871399.pdf%3Farnumber%3D5871399
2. Ibañez, G., Rojas, E.(2013). All-path Bridging: Path Exploration as an Efficient Alternative to Path Computation in Bridging Standards. http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=6649434&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D6649434
3. http://www.ieee802.org/1/pages/802.1aq.html
4. https://ietf.org/wg/trill/ (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).
5. Ibañez, G., Naous, J., Rojas, E., Rivera D., Carral, J.A., Arco, J.M. A Simple, Zero-configuration, Low Latency, Bridging Protocol. http://dspace.uah.es/dspace/bitstream/handle/10017/6770/10-A%20Simple%2c%20Zero-Configuration%2c%20Low%20Latency%2c%20Bridging%20Protocol%20LCN3gif.pdf?sequence=1 el 14 de febrero de 2012 en Wayback Machine.
6. [1]
7. ARP-P4: A hybrid ARP-Path/P4 Runtime Switch https://www.researchgate.net/deref/http%3A%2F%2Fdx.doi.org%2F10.1109%2FICNP.2018.00062?_sg%5B0%5D=XMjTHFFudJYBQxdYw4zQuDPEhb79vzanghV9WeeVei7NBztSzYjbEIaC7Lk0OUyfK5DyvUDos3AaAfuOcrrZATkF-w.GDaF6MFJWaTBe2bNa9BOZkiU3cT_1b0OCKFETx3PkjYx-ZyCHUnMrmR7i8sBFuFt3i7ZLNRBVx8HVOzZt4Zpkw]
8. D. López-Pajares, J. Álvarez-Horcajo, E. Rojas, J. Carral and G. Ibanez, "Iterative Discovery of Multiple Disjoint Paths in Switched Networks with Multicast Frames," in 2018 IEEE 43rd Conference on Local Computer Networks (LCN), Chicago, IL, USA, 2018 pp. 409-412
9. D. López-Pajares, J. Álvarez-Horcajo, E. Rojas, J. A. Carral and I. Martínez-Yelmo, "One-Shot Multiple Disjoint Path Discovery Protocol (1S-MDP)," in IEEE Communications Letters, vol. 24, no. 8, pp. 1660-1663, Aug. 2020, doi: 10.1109/LCOMM.2020.2990885.

Enlaces externos

• Video Arp-path
• Video Implementación Linux
• Video Implementación OpenFlow/NetFPGA/NOX
• Github: código NetFPGA ARP Path switch

•   Datos: Q17620763