[Lugro-mesh] Traduccion- Como trabaja el algoritmo de batman
Gustavo Lindberg
gus.lindberg en gmail.com
Jue Sep 18 12:15:09 ART 2008
El algoritmo de deteccion de ruta, en terminos generales trabaja de la
siguiente manera:
Cada nodo propaga su propia existencia en la malla simplemente inundandola
con mensajes de originador. ( OGM )
Cada OGM puede ser identificado univocamente por un numero de secuencia y la
direccion IP del nodo que inicio el mensaje.
Los mensaje OGM enviados a traves de enlaces pobres o muy congestionados
sufriran retados y paquetes perdidos. Los OGM inundados via enlaces buenos y
descongestionados se propagaran mejor, mas rapido y en forma mas fiable.
Cada nodo seleciona uno de sus vecinos como el mejor vecino y pasarela hacia
un cierto y especifico nodo. Este proceso de identificar el mejor vecino
hacia un nodo distante se denomina Node Ranking. Al vecino seleccionado se
lo refiere como el vecino mejor "rankeado".
Cada nodo mantiene un vecino mejor rankeado para cada otro nodo de la red.
El algoritmo del "nodo mejor rankeado" simplemente seleciona al vecino via
el cual recibio y acepto el OGM mas reciente desde el nodo que inicio el
OGM.
La propagacion de los OGM a traves de la red se basa en el camino entre
nodos intermediarios que repiten un OGM recibido. Una regla general de
algoritmo es: Cada nodo repite solo aquellos OGMs recibidos via el
correspondiente vecino mejor rankeado. De esta manera, el camino que probo
ser el mas rapido y el mas fiable, establecera una ruta continua y
unidireccional desde el receptor al originador del mensage OGM.
No aceptando deliberadamente un OGM para el ranking de vecinos, cada nodo (
a lo largo del camino de propagacion de un OGM ) tiene la posibilidad de
contrarestar la propagacion via un link especifico. De esta manera, cada
nodo puede influenciar en el establecimiento de la ruta resultante entre dos
puntos de la malla.
En batman-experimental la decision de cuando aceptar o no aceptar un cierto
OGM para el ranking de vecinos, se hace a traves de una funcion configurable
llamada "acceptance-function" ( funcion de aceptacion ). Existen parametros
para controlar la funcion de aceptacion, sobre cuando aceptar o no un OGM
recibido para integrar el ranking de nodos, dependiendo de observaciones
locales. Dichas observaciones pueden ser la calidad del link con el vecino
via el cual se recibio el OGM, la latencia del OGM o el numero de saltos que
ha pasado el OGM.
La idea es que cada nodo a lo largo del camino de propagacion de un OGM
exprese sus observaciones negativas acerca del enlace via el cual se recibio
un OGM, simplemente reduciendo la probabilidad de que se acepte y propague
mas lejos.
Asi, los OGMS inundados selectivamente sobre rutas buenas, se propagaran
mas, mas rapido y en forma mas fiable. El calculo del mejor vecino hacia un
nodo distante, queda reducido a tener en cuenta observaciones locales de la
realidad.
Queda eliminada la necesidad de conocer y calcular el camino completo de
punta a punta hacia un determinado nodo. En cambio, esto se divide entre
tdos los nodos participantes de la malla. Cada nodo percibe y mantiene solo
la informacion acerca del mejor proximo salto hacia todos y cada uno de los
otros nodos.
Batman usa un algoritmo distribuido.
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: http://www.lugro.org.ar/pipermail/lugro-mesh/attachments/20080918/1ae72cf0/attachment.htm
Más información sobre la lista de distribución Lugro-mesh