BATON ( Balanced Tree Overlay Network ) es una estructura de árbol distribuida diseñada para sistemas peer -to-peer (P2P). A diferencia de otras superposiciones que emplean una tabla hash distribuida , BATON organiza a los pares en un árbol distribuido para facilitar la búsqueda de rangos. BATON tiene como objetivo mantener una altura de árbol equilibrada, similar al árbol AVL , lo que da como resultado una búsqueda limitada para consultas exactas y de rango, así como para operaciones de actualización (unirse/salir).
BATON es un árbol binario. En cada nivel del árbol, el nodo se nombra según su posición en el árbol.
Cada nodo de BATON mantiene cuatro tipos de enlaces:
El nivel de cualquier nodo es uno mayor que el nivel de su padre. La raíz está en el nivel 0. Para un nodo en la posición , llenará su tabla de enrutamiento izquierda con nodos en la posición para cualquier válido y llenará su tabla de enrutamiento derecha con nodos en la posición para cualquier válido . La construcción de la tabla de enrutamiento tiene un ligero parecido con las tablas de dedos en Chord.
Entonces, de acuerdo con la estructura del ejemplo, el nodo 2:1 mantendría los enlaces a
Equilibrado en altura
BATON se considera equilibrado si y solo si la altura de sus dos subárboles en cualquier nodo del árbol difiere en, como máximo, uno. Si algún nodo detecta que se viola la restricción de equilibrio de altura, se inicia un proceso de reestructuración para garantizar que el árbol permanezca equilibrado.
Cuando un nuevo nodo desea unirse a la red en BATON, su solicitud de unión siempre se reenvía al nodo hoja. El nodo hoja luego verifica si su tabla de enrutamiento está llena. Si la tabla está llena, significa que el nivel está lleno de nodos y el nodo hoja puede aceptar el nuevo nodo como su hijo para crear un nuevo nodo de nivel. Si la tabla no está llena, el nodo hoja debe reenviar el nuevo nodo para que ocupe una de las posiciones vacías.
Por otro lado, cuando un nodo desea abandonar la red, debe actualizar las tablas de enrutamiento de su nodo padre, nodos secundarios , nodos adyacentes y nodos de enrutamiento. Si el nodo que abandona es un nodo hoja, puede abandonar la red de manera segura. Sin embargo, si no es un nodo hoja, debe encontrar un nodo hoja que reemplace su posición.
En BATON, cada nodo mantiene un espacio de claves continuo. Cuando un nuevo nodo se une como su hijo, el nodo divide su espacio y le asigna la mitad al hijo. Este método de partición permite recorrer el árbol en orden ascendente si recorremos el árbol en orden. Por eso BATON admite consultas de rango.
Para ejecutar una consulta de rango q, BATON primero localiza su límite izquierdo, q.low. Luego, el proceso de búsqueda recorre el árbol en orden (por vínculo adyacente) hasta que alcanza el límite superior, q.up. Para localizar una sola clave, BATON utiliza una estrategia de enrutamiento similar a la de Chord . La solicitud se enruta primero al nodo de enrutamiento más lejano que no sobrepasa la clave. Si no existen tales nodos de enrutamiento, se utiliza el vínculo principal, el vínculo secundario o el vínculo adyacente.
Cuando un nodo x acepta un nodo de unión y como su hijo y detecta que se viola el equilibrio del árbol, inicia el proceso de reestructuración. Sin pérdida de generalidad, supongamos que esta reestructuración es hacia la derecha. Supongamos que y se une como hijo izquierdo de x. Para reequilibrar el sistema, x notifica a y que reemplace su posición y notifica a su nodo adyacente derecho z que x reemplazará la posición de z. Z luego verifica su nodo adyacente derecho t para ver si su hijo izquierdo está vacío. Si lo está, y agregar un hijo a t no afecta el equilibrio del árbol, z toma la posición del hijo izquierdo de t como su nueva posición, y el proceso de reestructuración se detiene. Si el hijo izquierdo de t está lleno o t no puede aceptar a x como su hijo izquierdo sin violar la propiedad de equilibrio, z ocupa la posición de t, mientras que t necesita encontrar una nueva posición para sí mismo continuando hacia su nodo adyacente derecho.
BATON adopta dos tipos de estrategia de equilibrio de carga. Una vez que un nodo n detecta que está sobrecargado,
