Protocolo de enrutamiento de estado de enlace

Los protocolos de enrutamiento de estado de enlace son una de las dos clases principales de protocolos de enrutamiento utilizados en redes de conmutación de paquetes para comunicaciones informáticas , siendo los otros los protocolos de enrutamiento de vector distancia . ^{[ 1 ]} Ejemplos de protocolos de enrutamiento de estado de enlace incluyen Open Shortest Path First (OSPF) e Intermediate System to Intermediate System (IS-IS). ^{[ 2 ]}

El protocolo de estado de enlace es implementado por cada nodo de conmutación en la red (es decir, nodos que están preparados para reenviar paquetes; en Internet , estos se denominan enrutadores ). ^{[ 3 ]} El concepto básico del enrutamiento de estado de enlace es que cada nodo construye un mapa de la conectividad a la red en forma de grafo , que muestra qué nodos están conectados a qué otros nodos. ^{[ 4 ]} Cada nodo calcula de forma independiente la siguiente mejor ruta lógica desde él a cada posible destino en la red. ^{[ 5 ]} Cada conjunto de mejores rutas formará la tabla de enrutamiento de cada nodo . ^{[ 6 ]}

Esto contrasta con los protocolos de enrutamiento de vector de distancia, que funcionan haciendo que cada nodo comparta su tabla de enrutamiento con sus vecinos. En un protocolo de estado de enlace, la única información que se transmite entre nodos está relacionada con la conectividad . ^{[ 7 ]} Los algoritmos de estado de enlace a veces se caracterizan informalmente como cada enrutador "informando al mundo sobre sus vecinos". ^{[ 8 ]}

En los protocolos de enrutamiento de estado de enlace, cada enrutador posee información sobre la topología completa de la red . A continuación, cada enrutador calcula de forma independiente el mejor siguiente salto desde su ubicación para cada posible destino en la red, utilizando información local de la topología. El conjunto de los mejores siguientes saltos conforma la tabla de enrutamiento.

Esto contrasta con los protocolos de enrutamiento de vector distancia , que funcionan mediante la compartición de la tabla de enrutamiento de cada nodo con sus vecinos. En un protocolo de estado de enlace, la única información que se transmite entre los nodos es la utilizada para construir los mapas de conectividad.

Lo que se cree que fue la primera red de enrutamiento adaptativo de computadoras, que utilizaba enrutamiento de estado de enlace, fue diseñada e implementada entre 1976 y 1977 por un equipo de Plessey Radar liderado por Bernard J. Harris; el proyecto era para "Wavell" , un sistema de mando y control informático para el Ejército Británico . El primer concepto de enrutamiento de estado de enlace fue publicado en 1979 por John M. McQuillan (entonces en Bolt, Beranek y Newman ) como un mecanismo que calcularía rutas más rápidamente cuando cambiaran las condiciones de la red y, por lo tanto, conduciría a un enrutamiento más estable. ^{[ 9 ] [ 10 ]} 

La técnica se adaptó posteriormente para su uso en los protocolos de enrutamiento de estado de enlace contemporáneos IS-IS y OSPF. La documentación de Cisco se refiere al Protocolo de Enrutamiento de Puerta de Enlace Interior Mejorado (EIGRP) como un protocolo "híbrido" ^{[ 11 ]} , a pesar de que distribuye tablas de enrutamiento en lugar de mapas de topología. Sin embargo, sí sincroniza las tablas de enrutamiento al inicio, al igual que OSPF, y envía actualizaciones específicas solo cuando se producen cambios en la topología.

En 2004, Radia Perlman propuso utilizar el enrutamiento de estado de enlace para el reenvío de tramas de capa 2 con dispositivos denominados puentes de enrutamiento o Rbridges. El Grupo de Trabajo de Ingeniería de Internet (IETF) estandarizó el protocolo TRILL ( Interconexión Transparente de Muchos Enlaces ) para lograr esto. ^{[ 12 ]}

Más recientemente, esta técnica jerárquica se aplicó a redes malladas inalámbricas mediante el Protocolo de Enrutamiento de Estado de Enlace Optimizado (OLSR). Cuando una conexión puede tener calidad variable, esta calidad se puede utilizar para seleccionar las mejores conexiones. Esto se emplea en algunos protocolos de enrutamiento ad hoc que utilizan transmisión por radiofrecuencia.

La primera etapa principal del algoritmo de estado de enlace consiste en asignar un mapa de la red a cada nodo. Esto se realiza mediante varios pasos secundarios. En primer lugar, cada nodo debe determinar a qué otros puertos está conectado a través de enlaces que funcionan correctamente; para ello, utiliza un protocolo de accesibilidad que ejecuta periódicamente y de forma independiente con cada uno de sus vecinos conectados directamente.

Cada nodo envía periódicamente (y en caso de cambios de conectividad) un mensaje corto, el anuncio de estado del enlace , que:

• Identifica el nodo que lo está produciendo.
• Identifica todos los demás nodos (ya sean enrutadores o redes) a los que está conectado directamente.
• Incluye un "número de secuencia", que aumenta cada vez que el nodo de origen crea una nueva versión del mensaje .

Este mensaje se envía a todos los nodos de la red. Como paso previo necesario, cada nodo de la red recuerda, para cada uno de sus vecinos, el número de secuencia del último mensaje de estado de enlace que recibió de ese nodo. Cuando un nodo recibe un anuncio de estado de enlace, busca el número de secuencia que tiene almacenado para el origen de dicho mensaje; si este mensaje es más reciente (es decir, tiene un número de secuencia mayor), se guarda, se actualiza el número de secuencia y se envía una copia a cada uno de los vecinos de ese nodo. Este procedimiento permite que todos los nodos de la red reciban rápidamente una copia de la versión más reciente del anuncio de estado de enlace de cada nodo.

El conjunto completo genera el grafo para el mapa de la red. El mensaje de estado de enlace que proporciona información sobre los vecinos se recalcula y luego se difunde por toda la red cada vez que hay un cambio en la conectividad entre el nodo y sus vecinos, por ejemplo, cuando falla un enlace.

La segunda etapa principal del algoritmo de estado de enlace consiste en generar tablas de enrutamiento mediante la inspección de los mapas. Cada nodo ejecuta de forma independiente un algoritmo sobre el mapa para determinar la ruta más corta desde sí mismo a todos los demás nodos de la red; generalmente, se utiliza alguna variante del algoritmo de Dijkstra . Un nodo mantiene dos estructuras de datos: una estructura de datos de árbol que contiene los nodos que han sido "terminados" y una lista de candidatos . El algoritmo comienza con ambas estructuras vacías; luego agrega el propio nodo a la primera. La variante de un algoritmo voraz realiza entonces repetidamente lo siguiente:

• Todos los nodos vecinos conectados directamente al nodo se añaden al árbol (excepto aquellos que ya se encuentran en el árbol o en la lista de candidatos ). El resto se añade a la segunda lista ( de candidatos ).
• Cada nodo de la lista de candidatos se compara con cada uno de los nodos que ya se encuentran en el árbol. El nodo candidato más cercano a cualquiera de los nodos existentes se incorpora al árbol y se conecta al nodo vecino correspondiente. Cuando un nodo se incorpora al árbol desde la lista de candidatos, se elimina de dicha lista y no se considera en las iteraciones posteriores del algoritmo.

Los dos pasos se repiten mientras queden nodos en la lista de candidatos. (Cuando no queden nodos, todos los nodos de la red se habrán añadido al árbol). Este procedimiento finaliza cuando el árbol contiene todos los nodos de la red. Para cualquier nodo de destino, la mejor ruta es el nodo que se encuentra al inicio de la rama del árbol de ruta más corta que parte del nodo raíz y que conduce al nodo de destino deseado.

Siempre que se produce un cambio en el mapa de conectividad, es necesario recalcular el árbol de rutas más cortas y, a continuación, recrear la tabla de enrutamiento. BBN Technologies descubrió cómo calcular únicamente la parte del árbol que podría haberse visto afectada por un cambio determinado en el mapa.

Si todos los nodos no trabajan con el mismo mapa de enrutamiento, pueden formarse bucles de enrutamiento . En su forma más simple, dos nodos vecinos creen que el otro es la mejor ruta hacia un destino determinado. Cualquier paquete que llegue a cualquiera de los dos nodos con destino a dicho destino entrará en un bucle entre ellos, de ahí su nombre. También son posibles los bucles de enrutamiento que involucran a más de dos nodos.

Esto puede ocurrir dado que cada nodo calcula su árbol de ruta más corta y su tabla de enrutamiento sin interactuar de ninguna manera con otros nodos. Si dos nodos parten de mapas diferentes, es posible que se produzcan escenarios en los que se creen bucles de enrutamiento. En ciertas circunstancias, se pueden habilitar bucles diferenciales en un entorno multi-nube. Los nodos de acceso variable a través del protocolo de interfaz también pueden evitar el problema de los nodos de acceso simultáneo. ^{[ 15 ]}

El protocolo de enrutamiento de estado de enlace optimizado (OLSR) es un protocolo de enrutamiento de estado de enlace optimizado para redes móviles ad hoc (que también puede utilizarse en otras redes inalámbricas ad hoc ). ^{[ 16 ]} OLSR es proactivo y utiliza mensajes hello y de control de topología para difundir información de estado de enlace en la red móvil ad hoc. Mediante mensajes hello, cada nodo descubre información de vecinos de dos saltos y elige un conjunto de relés multipunto (MPR). Los MPR distinguen a OLSR de otros protocolos de enrutamiento de estado de enlace. Los nodos individuales utilizan la información de topología para calcular rutas de siguiente salto con respecto a todos los nodos de la red utilizando rutas de reenvío de salto más corto.

• 802.1aq Conexión de ruta más corta

• Sección "Enlace-estado versus vector de distancia" en el capítulo "Conceptos básicos de enrutamiento" del "Manual de tecnología de interconexión de redes" de Cisco .