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 protocolos de enrutamiento por vector distancia . Ejemplos de protocolos de enrutamiento de estado de enlace incluyen Abrir primero la ruta más corta (OSPF) y Sistema intermedio a sistema intermedio (IS-IS).
El protocolo de estado de enlace lo realizan todos los nodos 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 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 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 . Los algoritmos de estado de enlace a veces se caracterizan informalmente como que cada enrutador "le cuenta al mundo sobre sus vecinos".
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 destino posible en la red utilizando información local de la topología. La colección de los mejores siguientes saltos forma la tabla de enrutamiento.
Esto contrasta con los protocolos de enrutamiento por vector 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:
Lo que se cree que es la primera red de enrutamiento adaptativo de computadoras, que utiliza el enrutamiento de estado de enlace como núcleo, 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 por computadora para el ejército británico. [ cita necesaria ]
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. [1] [2] [3] Trabajos posteriores en BBN Technologies mostraron cómo utilizar la técnica del estado de enlace en un sistema jerárquico (es decir, uno en el que la red estaba dividida en áreas) de modo que cada nodo de conmutación no necesita un mapa. de toda la red, sólo la(s) zona(s) en la que está incluida. [ cita necesaria ]
Posteriormente, la técnica se adaptó 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", [4] 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 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 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. [5]
Más recientemente, esta técnica jerárquica se aplicó a redes de malla inalámbricas utilizando 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 de radiofrecuencia.
Esta descripción cubre sólo la configuración más simple; es decir, uno sin áreas, de modo que todos los nodos tengan un mapa de toda la red. El caso jerárquico es algo más complejo; consulte las distintas especificaciones del 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.
Primero, cada nodo necesita determinar a qué otros puertos está conectado, a través de enlaces en pleno funcionamiento; Lo hace utilizando un protocolo de accesibilidad que ejecuta periódicamente y por separado con cada uno de sus vecinos conectados directamente.
A continuación, cada nodo envía periódicamente (y en caso de cambios de conectividad) un mensaje corto, el anuncio del 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 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 del estado de enlace de cada nodo a 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 se adaptan mejor a redes más grandes.
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 del mapa de la red. El algoritmo itera sobre la recopilación de anuncios de estado de enlace; para cada uno, realiza 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 considerará correctamente informado salvo que ambos 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 se incluye en el mapa.
El mensaje de estado del enlace que proporciona información sobre los vecinos se vuelve a calcular y luego se inunda 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. Cualquier cambio de este tipo será detectado por el protocolo de accesibilidad que cada nodo ejecuta con sus vecinos.
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 nuevamente se hace con varios pasos.
Cada nodo ejecuta de forma independiente un algoritmo sobre el mapa para determinar el camino más corto 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 nodos que están "listos" 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 hace repetidamente lo siguiente:
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.
Con los caminos más cortos a mano, el siguiente paso es completar la tabla de enrutamiento. Para cualquier nodo de destino determinado, 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. Para crear la tabla de enrutamiento, sólo es necesario recorrer el árbol, recordar la identidad del nodo al principio de cada rama y completar la entrada de la tabla de enrutamiento para cada nodo que se encuentre con esa identidad.
El algoritmo descrito anteriormente se hizo lo más simple posible para facilitar la comprensión. En la práctica, se utilizan varias optimizaciones.
Siempre que ocurre 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. El trabajo de BBN Technologies [ cita necesaria ] descubrió cómo volver a calcular solo la parte del árbol que podría haberse visto afectada por un cambio determinado en el mapa. Además, la tabla de enrutamiento normalmente se completará a medida que se calcula el árbol de ruta más corta, en lugar de convertirla en una operación separada.
En algunos casos, es razonable reducir la cantidad de nodos que generan mensajes LSA. Por ejemplo, un nodo que tiene sólo una conexión al gráfico de red no necesita enviar mensajes LSA, ya que la información sobre su existencia ya podría estar 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 sólo un subconjunto de nodos de la red genera mensajes LSA. Dos enfoques ampliamente estudiados para la reducción de topología son:
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 debida a los mensajes de control. El mismo concepto se utiliza también en el protocolo de enrutamiento estatal Hazy Sighted Link .
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 dirigido a ese destino que llegue a cualquiera de los nodos circulará entre los dos, de ahí el nombre. También es posible enrutar bucles que impliquen 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 determinadas 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 del nodo de acceso simultáneo. [8]
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 se puede utilizar en otras redes inalámbricas ad hoc ). [9] OLSR es proactivo y utiliza mensajes de saludo y control de topología (TC) para descubrir y difundir información sobre el estado del enlace en la red móvil ad hoc. Mediante 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 rutas de reenvío del salto más corto.
{{cite news}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ){{citation}}: Mantenimiento CS1: nombres numéricos: lista de autores ( enlace ){{cite journal}}: Citar diario requiere |journal=( ayuda ){{cite journal}}: Citar diario requiere |journal=( ayuda )