Protocolo de enrutamiento de estado de enlace con visión borrosa

El Protocolo de Enrutamiento de Estado de Enlace con Visión Difusa ( HSLS ) es un protocolo de enrutamiento de red mallada inalámbrica desarrollado por la Fundación CUWiN . Este algoritmo permite que las computadoras que se comunican mediante radio digital en una red mallada reenvíen mensajes a computadoras que están fuera del alcance del contacto de radio directo. Su sobrecarga de red es teóricamente óptima, ^{[ 1 ]} utilizando enrutamiento de estado de enlace tanto proactivo como reactivo para limitar las actualizaciones de red en el espacio y el tiempo. Sus inventores creen que también es un protocolo más eficiente para enrutar redes cableadas. HSLS fue inventado por investigadores de BBN Technologies .

HSLS se diseñó para escalar bien a redes de más de mil nodos, y en redes más grandes comienza a superar la eficiencia de otros algoritmos de enrutamiento. Esto se logra mediante un equilibrio cuidadosamente diseñado entre la frecuencia y la extensión de las actualizaciones para propagar la información del estado de los enlaces de manera óptima. A diferencia de los métodos tradicionales, HSLS no satura la red con información del estado de los enlaces para intentar gestionar los nodos móviles que modifican sus conexiones con el resto de la red. Además, HSLS no requiere que cada nodo tenga la misma visión de la red.

Los algoritmos de estado de enlace son teóricamente atractivos porque encuentran rutas óptimas, reduciendo el desperdicio de capacidad de transmisión. Los inventores de HSLS afirman que los protocolos de enrutamiento se dividen en tres esquemas fundamentalmente distintos: proactivos (como OLSR ), reactivos (como AODV ) y algoritmos que aceptan enrutamientos subóptimos. Si se representan gráficamente, se vuelven menos eficientes a medida que se aproximan a una única estrategia, y la red crece. Los mejores algoritmos parecen encontrarse en un punto intermedio óptimo.

La información de enrutamiento se denomina "actualización del estado del enlace". La distancia a la que se copia un estado de enlace es el " tiempo de vida " y es un recuento del número de veces que se puede copiar de un nodo a otro.

Se dice que HSLS equilibra de forma óptima las características de los enfoques de enrutamiento proactivo, reactivo y subóptimo. Estas estrategias se combinan limitando las actualizaciones del estado del enlace en el tiempo y el espacio. Al limitar el tiempo de vida, se reduce la capacidad de transmisión. Al limitar los momentos en que se transmite una actualización de enrutamiento proactiva, se pueden recopilar y transmitir varias actualizaciones a la vez, lo que también ahorra capacidad de transmisión.

• Por definición, un algoritmo de estado de enlace utiliza la información disponible para producir la mejor ruta, de modo que el enrutamiento sea lo más óptimo posible, dada la información disponible.
• El enrutamiento subóptimo se produce de forma natural porque los nodos distantes reciben información con menos frecuencia.
• Minimizar las actualizaciones proactivas es la parte más compleja. El esquema se basa en dos algoritmos de enrutamiento de estado de enlace limitados. Uno de ellos, el "Enrutamiento de estado de enlace de visión cercana", tiene limitaciones espaciales, es decir, en el número de saltos de nodo que se pueden transmitir para la información de enrutamiento. El otro algoritmo, el "Enrutamiento de estado de enlace discretizado", limita la frecuencia de transmisión de dicha información. Dado que la atenuación óptima de las actualizaciones, tanto en espacio como en tiempo, es aproximadamente dos, el resultado es una actualización proactiva periódica, con distancias de salto de nodo fractales que son potencias de dos para los datos (por ejemplo, distancias de salto de 1, 2, 1, 4, 1, 2, 1, 8...).
• El enrutamiento reactivo se produce porque un intento fallido de usar un enlace adyacente provoca que expire el siguiente temporizador, lo que probablemente requiere información para encontrar una ruta alternativa. Ante cada fallo sucesivo, un nuevo intento intensifica la reacción a un mayor número de nodos conectados.

Los diseñadores comenzaron el ajuste de estos elementos definiendo una medida del desperdicio global de la red. Esto incluye el desperdicio derivado de la transmisión de actualizaciones de ruta, así como el desperdicio causado por rutas de transmisión ineficientes. Su definición exacta es: «La sobrecarga total se define como la cantidad de ancho de banda utilizada que excede la cantidad mínima de ancho de banda requerida para reenviar paquetes a través de la distancia más corta (en número de saltos), suponiendo que los nodos disponen de información instantánea de la topología completa».

A continuación, hicieron algunas suposiciones razonables y utilizaron una optimización matemática para determinar los tiempos de transmisión de las actualizaciones del estado del enlace, así como la amplitud de nodos que debían abarcar dichas actualizaciones.

Básicamente, ambos valores deberían aumentar al cuadrado con el paso del tiempo. El valor óptimo teórico es muy cercano a dos, con un margen de error de tan solo el 0,7 %. Este margen es considerablemente menor que los posibles errores derivados de las suposiciones, por lo que dos es un valor perfectamente razonable.

Se fuerza una actualización de enrutamiento local cada vez que se pierde una conexión. Esta es la parte reactiva del algoritmo. Una actualización de enrutamiento local se comporta exactamente igual que la expiración de un temporizador.

De lo contrario, cada vez que se duplica el retraso desde la última actualización, el nodo transmite información de enrutamiento que duplica el número de saltos de red que considera. Esto continúa hasta alcanzar un límite superior. Dicho límite superior define el tamaño global de la red y garantiza un tiempo de respuesta máximo fijo para una red sin nodos móviles.

El algoritmo cuenta con algunas características especiales para gestionar situaciones comunes en redes de radio, como enlaces unidireccionales y transmisiones en bucle causadas por tablas de enrutamiento desactualizadas . En concreto, redirige todas las transmisiones a nodos cercanos cuando pierde un enlace con un nodo adyacente. También retransmite su adyacencia cuando esto ocurre. Esto resulta útil precisamente porque los enlaces de larga distancia más valiosos son también los menos fiables en una red de radio.

La red establece rutas bastante buenas en tiempo real y reduce sustancialmente la cantidad y el tamaño de los mensajes enviados para mantener la red conectada, en comparación con muchos otros protocolos. Muchos de los protocolos de enrutamiento de malla más simples simplemente inundan toda la red con información de enrutamiento cada vez que cambia un enlace.

El algoritmo en sí es bastante simple.

La información de enrutamiento y la transferencia de datos están descentralizadas, por lo que deberían tener una buena fiabilidad y rendimiento sin puntos críticos locales.

El sistema requiere nodos potentes con gran cantidad de memoria para mantener las tablas de enrutamiento. Afortunadamente, estos nodos son cada vez más económicos.

El sistema proporciona una estimación muy rápida y relativamente precisa sobre si un nodo está en la red, ya que cada nodo contiene información de enrutamiento completa, aunque desactualizada. Sin embargo, esto no equivale a saber con certeza si un nodo está en la red. Esta estimación puede ser suficiente para la mayoría de los usos de la red, como la telefonía, pero podría no serlo para aplicaciones militares o de aviónica relacionadas con la seguridad .

HSLS tiene buenas propiedades de escalabilidad. La escalabilidad asintótica de su sobrecarga total es ${\displaystyle O(N^{1.5})}$en comparación con el estado de enlace estándar que escala como${\displaystyle O(N^{2})}$donde N es el número de nodos en la red.

Debido a que HSLS envía actualizaciones de estado de enlace con poca frecuencia, los nodos no tienen información reciente sobre si un nodo distante sigue presente. Este problema está presente en cierta medida en todos los protocolos de estado de enlace, ya que la base de datos de estado de enlace aún puede contener un anuncio de un nodo que ha fallado. Sin embargo, protocolos como OSPF propagan una actualización de estado de enlace desde los vecinos del nodo que ha fallado, por lo que todos los nodos se enteran rápidamente de su desaparición (o desconexión). Con HSLS, no se puede distinguir entre un nodo que sigue presente a 10 saltos de distancia y un nodo que ha fallado hasta que los antiguos vecinos envían anuncios de larga distancia. Por lo tanto, HSLS puede fallar en algunas circunstancias que requieren una alta fiabilidad.

Aunque los documentos que describen HSLS no se centran en la seguridad, se pueden utilizar técnicas como firmas digitales en las actualizaciones de enrutamiento (de forma similar a OSPF con firmas digitales ), y BBN ha implementado HSLS con firmas digitales en los mensajes de descubrimiento de vecinos y en las actualizaciones del estado de los enlaces. Estos esquemas presentan dificultades en la práctica, ya que en un entorno ad hoc no se puede garantizar la accesibilidad a los servidores de infraestructura de clave pública . Al igual que casi todos los protocolos de enrutamiento, HSLS no incluye mecanismos para proteger el tráfico de datos. (Véase IPsec y TLS ).

• AODV
• Red inalámbrica comunitaria de Champaign-Urbana
• DSR
• ExOR (protocolo de red inalámbrica)
• Lista de protocolos de enrutamiento ad hoc
• OLSR

• OLSR fisheye Archivado el 8 de abril de 2015 en Wayback Machine - OLSR de olsr.org implementó el algoritmo "fisheye", que es equivalente a HSLS.
• Prototipo NRLOLSR : OLSR extendido para proporcionar capacidad HSLS opcional.