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 ; los otros son los protocolos de enrutamiento por vector de distancia . [1] Algunos ejemplos de protocolos de enrutamiento de estado de enlace incluyen Open Shortest Path First (OSPF) y Intermediate System to Intermediate System (IS-IS). [2]
El protocolo de estado de enlace lo realiza 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 gráfico , que muestra qué nodos están conectados a qué otros nodos. [4] Luego, cada nodo calcula de forma independiente la siguiente mejor ruta lógica desde él hasta cada destino posible en la red. [5] Cada colección de mejores rutas formará entonces la tabla de enrutamiento de cada nodo . [6]
Esto contrasta con los protocolos de enrutamiento por 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 nodos está relacionada con la conectividad . [7] Los algoritmos de estado de enlace a veces se caracterizan informalmente como cada enrutador "que le cuenta 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. Luego, cada enrutador calcula de forma independiente el mejor siguiente salto para cada posible destino en la red utilizando información local de la topología. La recopilación de los mejores siguientes saltos forma la tabla de enrutamiento.
Esto contrasta con los protocolos de enrutamiento por 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 los nodos es la información que se utiliza para construir los mapas de conectividad.
Lo que se cree que es la primera red de enrutamiento adaptativa de computadoras, que utiliza enrutamiento de estado de enlace, fue diseñada e implementada durante 1976-1977 por un equipo de Plessey Radar dirigido por Bernard J Harris; el proyecto era para "Wavell", un sistema de comando y control de computadora para el ejército británico . [ cita requerida ] 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 las condiciones de la red cambiaran y, por lo tanto, conduciría a un enrutamiento más estable. [9] [10] [11]
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 protocolo "híbrido", [12] a pesar del hecho 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 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 ha estandarizado el protocolo TRILL ( Interconexión transparente de muchos enlaces ) para lograrlo. [13]
Más recientemente, esta técnica jerárquica se aplicó a 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 utiliza en algunos protocolos de enrutamiento ad hoc que utilizan transmisión por radiofrecuencia. [ cita requerida ]
La primera etapa principal del algoritmo de estado de enlace es proporcionar un mapa de la red a cada nodo. Esto se hace con varios pasos secundarios. Primero, cada nodo debe determinar a qué otros puertos está conectado en enlaces que funcionan completamente; esto se hace mediante un protocolo de accesibilidad que ejecuta de forma periódica y por separado 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:
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 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 reciente (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 su vez 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.
El conjunto completo produce el gráfico del mapa de la red. El mensaje de estado del enlace que proporciona información sobre los vecinos se vuelve a calcular y luego se distribuye por toda la red cada vez que se produce 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 es producir tablas de enrutamiento inspeccionando los mapas. 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 . Un nodo mantiene dos estructuras de datos: un árbol que contiene los nodos que están "listos" y una lista de candidatos . El algoritmo comienza con ambas estructuras vacías; luego agrega a la primera el propio nodo. La variante de un algoritmo voraz hace entonces lo siguiente de forma repetitiva:
Los dos pasos se repiten siempre que queden nodos en la lista de candidatos (si no queda ninguno, se habrán añadido todos los nodos de la red al árbol). Este procedimiento finaliza con el árbol que contiene todos los nodos de la red. 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 ruta más corta que conduce hacia el nodo de destino deseado.
Siempre que se produce un cambio en el mapa de conectividad, es necesario volver a calcular el árbol de ruta más corta y luego recrear la tabla de enrutamiento. BBN Technologies descubrió cómo calcular solo la parte del árbol que podría haberse visto afectada por un cambio determinado en el mapa. [ cita requerida ]
En algunos casos, es razonable reducir el número de nodos que generan mensajes LSA. 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 generan mensajes LSA. Dos enfoques ampliamente estudiados para la reducción de topología son los relés multipunto que están en la base del Protocolo de enrutamiento de estado de enlace optimizado (OLSR) pero que también se han propuesto para OSPF [14] y los conjuntos dominantes conectados que nuevamente se propusieron para OSPF. [15]
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 Hazy Sighted Link State Routing .
Si todos los nodos no funcionan exactamente desde el mismo mapa, pueden formarse bucles de enrutamiento . Se trata de situaciones en las que, en su forma más simple, dos nodos vecinos piensan que cada uno de ellos es el mejor camino hacia un destino determinado. Cualquier paquete que se dirija a ese destino y llegue a cualquiera de los nodos pasará por un bucle entre los dos, de ahí el nombre. También son posibles los bucles de enrutamiento que involucran a 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 creen bucles de enrutamiento. En ciertas circunstancias, se pueden habilitar bucles diferenciales dentro de un entorno de múltiples nubes. 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. [16]
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 utilizar en otras redes ad hoc inalámbricas ). [17] OLSR es proactivo y utiliza mensajes de saludo y control de topología para difundir información de estado de enlace en la red ad hoc móvil. Mediante mensajes de saludo, cada nodo descubre información de vecino de dos saltos y elige un conjunto de relés multipunto (MPR). Los MPR hacen que OLSR sea distinto 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 utilizando rutas de reenvío de salto más corto.
{{citation}}: CS1 maint: numeric names: authors list (link){{cite journal}}: Requiere citar revista |journal=( ayuda ){{cite journal}}: Requiere citar revista |journal=( ayuda )