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 que se utilizan en las redes de conmutación de paquetes para las comunicaciones informáticas; los otros son protocolos de enrutamiento de vector de distancia. Los ejemplos de protocolos de enrutamiento de estado de enlace incluyen Open Shortest Path First (OSPF) y Sistema intermedio a sistema intermedio (IS-IS).

El protocolo de estado de enlace lo realiza cada nodo de conmutación de la red (es decir, nodos que están preparados para reenviar paquetes; en Internet, se denominan enrutadores). 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 gráfico, que muestra qué nodos están conectados a qué otros nodos. Luego, cada nodo calcula de forma independiente la siguiente mejor ruta lógica desde él hasta cada destino posible en la red. Cada colección de mejores rutas formará la tabla de enrutamiento de cada nodo.

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 pasa entre los nodos está relacionada con la conectividad. Los algoritmos de estado de enlace a veces se caracterizan informalmente como cada enrutador, "indicándole al mundo sobre sus vecinos".

Resumen

En los protocolos de enrutamiento de estado de enlace, cada enrutador posee información sobre la topología de red completa. Luego, cada enrutador calcula de forma independiente el mejor siguiente salto para cada destino posible en la red utilizando información local de la topología. La colección de mejores próximos saltos forma la tabla de enrutamiento.

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 pasa entre los nodos es la información utilizada para construir los mapas de conectividad.

Ejemplos de protocolos de enrutamiento de estado de enlace:

• Camino más corto abierto Primero (OSPF)
• Sistema Intermedio al Sistema Intermedio (IS-IS)

Historia

Lo que se cree que es la primera red de enrutamiento adaptativo de computadoras, utilizando el enrutamiento de estado de enlace como núcleo, fue diseñado e implementado durante 1976-1977 por un equipo de Plessey Radar dirigido 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 las rutas más rápidamente cuando cambiaran las condiciones de la red y, por lo tanto, conduciría a un enrutamiento más estable.

Un trabajo posterior en BBN Technologies mostró cómo usar la técnica de estado de enlace en un sistema jerárquico (es decir, uno en el que la red se dividía en áreas) para que cada nodo de conmutación no necesite un mapa de toda la red, solo la(s) zona(s) en que se incluye.

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 literatura de Cisco se refiere al Protocolo de enrutamiento de puerta de enlace interior mejorado (EIGRP) como un "híbrido" protocolo, a pesar de que distribuye tablas de enrutamiento en lugar de mapas de topología. Sin embargo, sincroniza las tablas de enrutamiento al inicio como lo hace OSPF y envía actualizaciones específicas solo cuando ocurren cambios en la topología.

En 2004, Radia Perlman propuso usar el enrutamiento de estado de enlace para el reenvío de tramas de capa 2 con dispositivos llamados puentes de enrutamiento o Rbridges. El Grupo de trabajo de ingeniería de Internet ha estandarizado el protocolo de interconexión transparente de muchos enlaces (TRILL) para lograr esto.

Más recientemente, esta técnica jerárquica se aplicó a las redes de malla inalámbricas mediante el protocolo de enrutamiento de estado de enlace optimizado (OLSR). Cuando una conexión puede tener una calidad variable, la calidad de una conexión se puede utilizar para seleccionar mejores conexiones. Esto se usa en algunos protocolos de enrutamiento ad hoc que usan transmisión de radiofrecuencia.

En 2012, el IEEE completó y aprobó la estandarización del uso de IS-IS para controlar el reenvío de Ethernet con el puente de ruta más corta (SPB) IEEE 802.1aq.

Distribución de mapas

Esta descripción cubre solo la configuración más simple; es decir, uno sin áreas, para que todos los nodos tengan un mapa de toda la red. El caso jerárquico es algo más complejo; ver las diversas especificaciones de protocolo.

Como se mencionó anteriormente, la primera etapa principal en el algoritmo de estado de enlace es proporcionar un mapa de la red a cada nodo. Esto se hace con varios pasos subsidiarios.

Determinación de las vecinas de cada nodo

Primero, cada nodo necesita determinar a qué otros puertos está conectado, a través de enlaces completamente operativos; lo hace usando un protocolo de accesibilidad que se ejecuta periódicamente y por separado con cada uno de sus vecinos conectados directamente.

Distribuir la información para el mapa

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

• Identifica el nodo que lo está produciendo.
• Identifica todos los otros nodos (ya sean routers o redes) a los que está directamente conectado.
• Incluye un 'número de secuencia', que aumenta cada vez que el nodo fuente compone una nueva versión del mensaje.

Este mensaje se envía a todos los nodos de una red. Como precursor necesario, cada nodo de la red recuerda, para cada uno de sus sus vecinos, el número de secuencia del último mensaje de estado de enlace que recibió de ese nodo. Cuando se recibe un anuncio de estado de enlace en un nodo, el nodo busca el número de secuencia que ha almacenado para la fuente de ese mensaje de estado de enlace: si este mensaje es más nuevo (es decir, tiene un número de secuencia más alto), se guarda, el número de secuencia se actualiza y se envía una copia a cada uno de los vecinos de ese nodo. Este procedimiento obtiene rápidamente una copia de la última versión del anuncio de estado de enlace de cada nodo para cada nodo de la red.

Las redes que ejecutan algoritmos de estado de enlace también se pueden segmentar en jerarquías que limitan el alcance de los cambios de ruta. Estas características significan que los algoritmos de estado de enlace escalan mejor a redes más grandes.

Creando el mapa

Finalmente, con el conjunto completo de anuncios de estado de enlace (uno de cada nodo de la red) en la mano, cada nodo produce el gráfico para el mapa de la red. El algoritmo itera sobre la colección de anuncios de estado de enlace; para cada uno, hace enlaces en el mapa de la red, desde el nodo que envió ese mensaje, a todos los nodos que ese mensaje indica que son vecinos del nodo emisor.

Ningún enlace se considera correctamente informado a menos que los dos extremos estén de acuerdo; es decir, si un nodo informa que está conectado a otro, pero el otro nodo no informa que está conectado al primero, hay un problema y el enlace no está incluido en el mapa.

Notas sobre esta etapa

El mensaje de estado de enlace que brinda información sobre los vecinos se vuelve a calcular y luego se inunda en toda la red, cada vez que hay un cambio en la conectividad entre el nodo y sus vecinos; por ejemplo, cuando falla un enlace. Cualquier cambio de este tipo será detectado por el protocolo de accesibilidad que cada nodo ejecuta con sus vecinos.

Cálculo de la tabla de enrutamiento

Como se mencionó inicialmente, la segunda etapa principal en el algoritmo de estado de enlace es producir tablas de enrutamiento mediante la inspección de los mapas. Esto se hace de nuevo con varios pasos.

Calcular los caminos más cortos

Cada nodo ejecuta de forma independiente un algoritmo sobre el mapa para determinar la ruta más corta desde sí mismo hasta todos los demás nodos de la red; generalmente se utiliza alguna variante del algoritmo de Dijkstra. Esto se basa en un costo de enlace en cada ruta que incluye el ancho de banda disponible, entre otras cosas.

Un nodo mantiene dos estructuras de datos: un árbol que contiene los nodos que están "terminados" y una lista de candidatos. El algoritmo comienza con ambas estructuras vacías; luego agrega al primero el propio nodo. La variante de un algoritmo codicioso luego hace lo siguiente repetitivamente:

• Todos los nodos vecinos que están directamente conectados al nodo se acaban de añadir al árbol (salvo los nodos que ya están en el árbol o en la lista de candidatos). El resto se añade a la segunda lista (candidato).
• Cada nodo en la lista de candidatos se compara con cada uno de los nodos ya en el árbol. El nodo candidato que está más cerca de cualquiera de los nodos ya en el árbol se mueve en sí mismo al árbol y se une al nodo vecino apropiado. Cuando un nodo se mueve de la lista de candidatos al árbol, se elimina de la lista de candidatos y no se considera en posteriores iteraciones del algoritmo.

Los dos pasos anteriores se repiten siempre que queden nodos en la lista de candidatos. (Cuando no hay ninguno, todos los nodos de la red se habrán agregado al árbol). Este procedimiento finaliza con el árbol que contiene todos los nodos de la red, con el nodo en el que se ejecuta el algoritmo como raíz del árbol. El camino más corto desde ese nodo a cualquier otro nodo está indicado por la lista de nodos que uno atraviesa para llegar desde la raíz del árbol hasta el nodo deseado en el árbol.

Llenar la tabla de enrutamiento

Con las rutas más cortas disponibles, el siguiente paso es completar la tabla de enrutamiento. Para cualquier nodo de destino dado, la mejor ruta para ese destino es el nodo que es el primer paso desde el nodo raíz, hacia abajo en la rama del árbol de la ruta más corta que conduce hacia el nodo de destino deseado. Para crear la tabla de enrutamiento, solo es necesario recorrer el árbol, recordar la identidad del nodo en la cabecera de cada rama y completar la entrada de la tabla de enrutamiento para cada nodo que se encuentre con esa identidad.

Optimizaciones al algoritmo

El algoritmo descrito anteriormente se hizo lo más simple posible, para facilitar la comprensión. En la práctica, hay una serie de optimizaciones que se utilizan.

Recalculo parcial

Siempre que ocurre un cambio en el mapa de conectividad, es necesario volver a calcular el árbol de la ruta más corta y luego volver a crear la tabla de enrutamiento. El trabajo de BBN Technologies descubrió cómo volver a calcular solo la parte del árbol que podría haberse visto afectada por un cambio dado en el mapa. Además, la tabla de enrutamiento normalmente se completaría a medida que se calcula el árbol de la ruta más corta, en lugar de convertirlo en una operación separada.

Reducción de topología

En algunos casos, es razonable reducir la cantidad de nodos que generan mensajes LSA. Por ejemplo, un nodo que solo tiene una conexión con el grafo de la red no necesita enviar mensajes LSA, ya que la información sobre su existencia podría estar ya incluida en el mensaje LSA de su único vecino. Por esta razón, se puede aplicar una estrategia de reducción de topología, en la que solo un subconjunto de los nodos de la red genera mensajes LSA. Dos enfoques ampliamente estudiados para la reducción de topología son:

1. Relés multipuntos que están en la base del Protocolo de Routing de Estado de Enlace Optimizado (OLSR) pero también se han propuesto para OSPF
2. Conjuntos dominantes conectados que se han propuesto de nuevo para OSPF

Enrutamiento de estado de ojo de pez

Con Fisheye State Routing (FSR), los LSA se envían con diferentes valores de tiempo de vida para restringir su difusión y limitar la sobrecarga debido a los mensajes de control. El mismo concepto se utiliza también en el protocolo de enrutamiento de estado de enlace Hazy Sighted.

Modos de falla

Si todos los nodos no funcionan exactamente desde el mismo mapa, se pueden formar bucles de enrutamiento. Estas son situaciones en las que, en la forma más simple, dos nodos vecinos piensan que el otro es el mejor camino hacia un destino determinado. Cualquier paquete que se dirija a ese destino y llegue a cualquiera de los nodos hará un bucle entre los dos, de ahí el nombre. También son posibles bucles de enrutamiento que involucran más de dos nodos.

Esto puede ocurrir porque cada nodo calcula su árbol de ruta más corta y su tabla de enrutamiento sin interactuar de ninguna manera con ningún otro nodo. Si dos nodos comienzan con mapas diferentes, es posible tener escenarios en los que se crean bucles de enrutamiento. En determinadas circunstancias, los bucles diferenciales pueden habilitarse dentro de un entorno de varias nubes. Los nodos de acceso variable a través del protocolo de interfaz también pueden eludir el problema del nodo de acceso simultáneo.

Protocolo de enrutamiento de estado de enlace optimizado

El protocolo de enrutamiento de estado de enlace optimizado (OLSR) es un protocolo de enrutamiento de estado de enlace optimizado para redes ad hoc móviles (que también se puede usar en otras redes ad hoc inalámbricas). OLSR es proactivo y utiliza mensajes de control de topología (TC) y saludo para descubrir y difundir información de estado de enlace en la red móvil ad hoc. Usando mensajes de saludo, cada nodo descubre información de vecinos de dos saltos y elige un conjunto de retransmisiones 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 las rutas del siguiente salto con respecto a todos los nodos de la red que utilizan las rutas de reenvío del salto más corto.