El Protocolo de enrutamiento de estado de enlace de visión nebulosa ( HSLS ) es un protocolo de enrutamiento de red de malla inalámbrica que está siendo desarrollado por la Fundación CUWiN . Este es un algoritmo que permite a las computadoras que se comunican a través de radio digital en una red de malla para reenviar mensajes a las computadoras que están fuera del alcance del contacto directo por radio. La sobrecarga de su red es teóricamente óptima, [1] utilizando tanto el estado de enlace proactivo como el reactivo .enrutamiento para limitar las actualizaciones de la 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 .
Eficiencia
HSLS se hizo para escalar bien a redes de más de mil nodos, y en redes más grandes comienza a exceder las eficiencias de los otros algoritmos de enrutamiento. Esto se logra utilizando un equilibrio cuidadosamente diseñado de frecuencia de actualización y extensión de actualización para propagar la información del estado del enlace de manera óptima. A diferencia de los métodos tradicionales, HSLS no inunda la red con información del estado del enlace para intentar hacer frente a los nodos en movimiento que cambian las conexiones con el resto de la red. Además, HSLS no requiere que cada nodo tenga la misma vista de la red.
¿Por qué un protocolo de estado de enlace?
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 [ cita requerida ] que los protocolos de enrutamiento se dividen en tres esquemas básicamente diferentes: proactivo (como OLSR ), reactivo (como AODV ) y algoritmos que aceptan enrutamientos subóptimos. Si se grafican, se vuelven menos eficientes, ya que son más puramente una estrategia única, y la red se hace más grande. Los mejores algoritmos parecen estar en un punto intermedio.
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 al siguiente.
Se dice que HSLS equilibra de manera óptima las características de los enfoques de enrutamiento proactivo, reactivo y subóptimo. Estas estrategias se combinan limitando las actualizaciones del estado de los enlaces en el tiempo y el espacio. Al limitar el tiempo de vida, se reduce la cantidad de capacidad de transmisión. Al limitar los tiempos 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, por lo que el enrutamiento es lo más óptimo posible, dada la información disponible.
- El enrutamiento subóptimo ocurre naturalmente porque los nodos distantes obtienen información con menos frecuencia.
- Minimizar las actualizaciones proactivas es la parte complicada. El esquema está adaptado de dos algoritmos de enrutamiento de estado de enlace limitados. Uno, el "Enrutamiento de estado de enlace para miopes" está limitado en el espacio, en el número de saltos de nodo que puede transmitir la información de enrutamiento. El otro algoritmo de enrutamiento, "Enrutamiento discretizado de estado de enlace" limita los tiempos en que se puede transmitir la información de enrutamiento. Dado que la atenuación de actualización óptima tanto en el espacio como en el tiempo es de aproximadamente dos, el resultado es una actualización proactiva periódica, con distancias de salto de nodo de potencia fractal 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 utilizar un enlace adyacente hace que expire el siguiente temporizador, probablemente extrayendo la información para encontrar una ruta alternativa. En cada falla sucesiva, un reintento aumenta la reacción a audiencias más amplias de nodos mallados.
Cómo funciona
Los diseñadores comenzaron a ajustar estos elementos definiendo una medida de desperdicio de red global. Esto incluye el desperdicio de la transmisión de actualizaciones de rutas y también el desperdicio de rutas de transmisión ineficientes. Su definición exacta es "La sobrecarga total se define como la cantidad de ancho de banda utilizada en exceso de la cantidad mínima de ancho de banda requerida para reenviar paquetes a la distancia más corta (en número de saltos) asumiendo que los nodos tenían información instantánea de topología completa. "
Luego hicieron algunas suposiciones razonables y utilizaron una optimización matemática para encontrar los tiempos para transmitir las actualizaciones del estado del enlace, y también la amplitud de nodos que deberían cubrir las actualizaciones del estado del enlace.
Básicamente, ambos deberían crecer a la potencia de dos a medida que aumenta el tiempo. El número óptimo teórico está muy cerca de dos, con un error de solo 0,7%. Esto es sustancialmente menor que los posibles errores de los supuestos, por lo que dos es un número 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 de la misma manera 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 cierto límite superior. Un límite superior le da a la red un tamaño global y asegura un tiempo de respuesta máximo fijo para una red sin ningún nodo en movimiento.
El algoritmo tiene algunas características especiales para hacer frente a casos que son comunes en las redes de radio, como enlaces unidireccionales y transmisión en bucle causada por tablas de enrutamiento desactualizadas . En particular, redirige todas las transmisiones a los nodos cercanos siempre que pierde un enlace a un nodo adyacente. También retransmite su adyacencia cuando esto ocurre. Esto es útil precisamente porque los enlaces de larga distancia más valiosos son también los menos confiables en una red de radio.
Ventajas
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 real es bastante simple.
La información de enrutamiento y la transferencia de datos están descentralizadas y, por lo tanto, deben tener una buena confiabilidad y rendimiento sin puntos calientes locales.
El sistema requiere nodos capaces con grandes cantidades de memoria para mantener tablas de enrutamiento. Afortunadamente, estos son cada vez menos costosos.
El sistema da una suposición muy rápida y relativamente precisa sobre si un nodo está en la red, porque en cada nodo hay información de enrutamiento completa, aunque desactualizada. Sin embargo, esto no es lo mismo que saber si un nodo está en la red. Esta suposición puede ser adecuada para la mayoría de los usos de la red de tarifas, como la telefonía, pero puede no ser adecuada para los militares o la aviónica relacionados con la seguridad .
HSLS tiene buenas propiedades de escalabilidad. La escalabilidad asintótica de su sobrecarga total es en comparación con el estado de enlace estándar que escala como , donde N es el número de nodos de la red.
Críticas
Debido a que HSLS envía actualizaciones distantes con poca frecuencia, los nodos no tienen información reciente sobre si un nodo distante todavía está presente. Este problema está presente hasta cierto punto en todos los protocolos de estado de enlace, porque la base de datos de estado de enlace aún puede contener un anuncio de un nodo fallido. Sin embargo, los protocolos como OSPF propagarán una actualización del estado del enlace de los nodos vecinos fallidos y, por lo tanto, todos los nodos se enterarán rápidamente de la desaparición (o desconexión) del nodo fallido. Con HSLS, no se puede eliminar la ambigüedad entre un nodo que todavía está presente a 10 saltos de distancia y un nodo fallido hasta que los antiguos vecinos envíen anuncios de larga distancia. Por lo tanto, HSLS puede fallar en algunas circunstancias que requieren una alta seguridad.
Si bien los artículos que describen HSLS no se centran en la seguridad, las técnicas como las firmas digitales en las actualizaciones de enrutamiento se pueden usar con HSLS (similar a OSPF con firmas digitales ), y BBN ha implementado HSLS con firmas digitales en mensajes de descubrimiento de vecinos y actualizaciones de estado de enlaces. Estos esquemas son un desafío en la práctica porque en el entorno ad hoc no se puede garantizar la accesibilidad de los servidores de infraestructura de clave pública . Como casi todos los protocolos de enrutamiento, HSLS no incluye mecanismos para proteger el tráfico de datos. (Consulte IPsec y TLS ).
Ver también
Referencias
- ^ "Enrutamiento de estado de enlace de visión nebulosa (HSLS): un algoritmo de estado de enlace escalable" (PDF) . BBN Technologies. Archivado desde el original (PDF) el 2008-07-06 . Consultado el 20 de febrero de 2008 . Cite journal requiere
|journal=
( ayuda )
enlaces externos
- Ojo de pez OLSR - OLSR de olsr.org implementó el algoritmo "ojo de pez" que es equivalente a HSLS
- Prototipo NRLOLSR : OLSR extendido para proporcionar una capacidad HSLS opcional