Superposición de BATON
El BA lanced T ree O ver-lay N etwork ( BATON ) es una estructura de árbol distribuido para -peer-to-peer sistemas (P2P). A diferencia de otras superposiciones que utilizan una tabla hash distribuida (DHT), como en el sistema Chord , BATON organiza a los pares en un árbol distribuido para admitir la búsqueda de rango. Además, BATON intenta mantener el árbol en altura equilibrada, similar al árbol AVL . Y, por lo tanto, el costo de las consultas de rango y exacto de búsqueda está limitado , como el costo de una operación de actualización (unirse / salir).
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 posición , llenará su tabla de enrutamiento izquierda por nodos en posición para cualquier válido y completará su tabla de enrutamiento derecha por nodos en 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.
BATON está equilibrado si y solo si en cualquier nodo del árbol, la altura de sus dos subárboles difiere como máximo en uno. Si algún nodo detecta que el árbol valida la restricción de equilibrio de altura, se inicia una reestructuración .
La solicitud de incorporación del nuevo nodo siempre se reenviará al nodo hoja. El nodo hoja comprobará si la tabla de enrutamiento está llena. Si la tabla de enrutamiento está llena, este nivel está lleno de nodos y el nodo hoja puede aceptar el nuevo nodo como hijo para crear un nuevo nodo de nivel. De lo contrario, debe reenviar el nuevo nodo para que se haga cargo de una de las posiciones vacías.
Cuando un nodo quiere salir de la red, debe actualizar las tablas de enrutamiento de su nodo principal, los nodos secundarios, los nodos adyacentes y los nodos de enrutamiento. Si este nodo es un nodo hoja, puede salir de la red de forma segura. De lo contrario, debe encontrar un nodo hoja para reemplazar su posición.
En BATON, cada nodo mantiene un espacio clave continuo. Una vez que un nuevo nodo se une como hijo, divide su espacio y asigna la mitad al hijo. De esta forma de partición, si recorremos el árbol en orden, podemos buscar todo el espacio en orden ascendente. Es por eso que BATON admite consultas de rango.
