Enrutamiento de estado ojo de pez

El enrutamiento de estado ojo de pez (FSR) es una propuesta para un protocolo de enrutamiento jerárquico implícito dirigido a redes ad hoc . ^{[ 1 ]} Los principios básicos de FSR son compartidos con otros protocolos de enrutamiento proactivos de estado de enlace . El enrutamiento de estado ojo de pez, junto con el enrutamiento de estado jerárquico , fue introducido y sus rendimientos relativos modelados mediante simulación por Iwata et al. (1999). ^{[ 2 ]} En los protocolos proactivos de estado de enlace, cada nodo de la red actualiza constantemente un mapa de topología que permite calcular la ruta más corta (y por lo tanto el siguiente salto) a cualquier destino en la red. La originalidad de FSR está inspirada en la técnica del " ojo de pez " para reducir el tamaño de la información necesaria para representar los datos del grafo de la red: el ojo de un pez captura con gran detalle los píxeles cerca del punto focal, mientras que el detalle disminuye a medida que aumenta la distancia desde el punto focal.

En el enrutamiento, el enfoque ojo de pez se traduce en mantener un conjunto de información actualizado sobre la distancia y la calidad de la ruta en el entorno inmediato de un nodo, en contraposición a una información cada vez menos actualizada a medida que aumenta la distancia. El ojo de pez representa un equilibrio válido entre la precisión de la función de enrutamiento y la sobrecarga debida a la generación de mensajes de control por parte del protocolo de enrutamiento.

FSR nunca se lanzó al público como un protocolo de enrutamiento independiente, y su especificación nunca se finalizó. ^{[ 3 ]} El principio básico se incluyó en el ampliamente utilizado demonio OLSRd (una implementación de código abierto del protocolo de enrutamiento OLSR ^{[ 4 ]} ).

FSR es un protocolo de enrutamiento de estado de enlace, por lo que consta de tres tareas:

1. Descubrimiento de vecinos: cada nodo envía un HELLOmensaje cada δ segundos a sus vecinos de un salto, con el fin de establecer y mantener relaciones de vecindad.
2. Difusión de información: cada nodo difunde mensajes de anuncios de estado de enlace (LSA) cada Δ segundos (con Δ > δ), que contienen información de enlace de vecinos, a todos los demás nodos de la red.
3. Cálculo de rutas: a partir de la información contenida en los mensajes LSA, el nodo puede reconstruir toda la topología de la red y utilizar el algoritmo de Dijkstra para calcular las rutas a cualquier nodo de la red.

La particularidad de FSR radica en que los mensajes LSA se generan cada Δ segundos utilizando una secuencia de valores de Tiempo de Vida (TTL) distintos. Por ejemplo, con la secuencia 1, 3, 8, 64, los vecinos a un salto reciben el LSA cada Δ segundos, por lo que disponen de la información más actualizada. Los vecinos a dos saltos reciben el LSA con TTL 3, 8, 24. Los nodos situados entre 4 y 8 saltos reciben únicamente el LSA con TTL 8 y 64. Todos los demás reciben solo el LSA con TTL 64. En consecuencia, cada nodo dispone de información progresivamente menos actualizada sobre la topología de la red a medida que aumenta la distancia.

El protocolo aprovecha el hecho de que, cuando un paquete se mueve desde un origen a un destino, los nodos encontrados en la ruta más corta tienen información topológica cada vez más precisa sobre la posición topológica del destino (a medida que disminuye su distancia al destino), por lo que la pérdida de precisión en el cálculo de la ruta más corta desde el nodo de origen se compensa a lo largo de la ruta hacia el destino.

De este modo, FSR disminuye la cantidad total de información que se difunde en la red, ya que los LSA no se envían con un TTL máximo fijo.

Uno de los problemas típicos de los protocolos de estado de enlace es que, cuando un nodo o enlace falla, pueden crearse bucles temporales. Esto se debe a que HELLOlos mensajes se envían con mayor frecuencia que los mensajes LSA, por lo que, si un nodo falla, sus vecinos detectan la rotura del enlace mucho antes que los demás nodos. Inmediatamente recalculan sus tablas de enrutamiento, lo que puede generar conflictos con las tablas de enrutamiento de los otros nodos, creando así un bucle . Esto puede ocurrir cuando dos nodos tienen información con una antigüedad diferente y, por lo tanto, calculan sus tablas de enrutamiento en dos topologías de red distintas. FSR lo hace por diseño, ya que introduce áreas en la red con conjuntos de información potencialmente diferentes, lo que aumenta la probabilidad de crear bucles temporales. ^{[ 5 ]}

• Lista de protocolos de enrutamiento ad hoc