Usuario:DistribuidosW3/Taller

Koorde

Koorde es una implementación de tabla hash distribuida (DHT) utilizado en redes peer-to-peer (P2P).

El sistema está basado en el Chord DHT y el gráfico De Bruijn (secuencia De Bruijn). Debido a ello, Koorde cumple que los saltos por nodo en notación Big-O es de orden logaritmo de n (donde n es la cantidad de nodos en DHT) y O (log n / log log n) saltos por solicitud de búsqueda con O (log n) vecinos por nodo.

Grafico de De Bruijn

Ejemplo de gráfico de De Bruijn

En un gráfico d-dimensional de Bruijn, hay $2^{d}$ nodos, cada uno de los cuales tiene una ID de d-bit única. El nodo con ID i está conectado a los nodos 2i módulo $2^{d}$ y 2i+1 módulo $2^{d}$. Gracias a esta propiedad, el algoritmo de enrutamiento puede encaminar a cualquier destino en d pasos al sucesivamente "desplazar" los bits de la ID de destino, pero solo si las dimensiones de la distancia entre el módulo 1d y 3d son iguales. El encaminamiento de un mensaje desde el nodo m al nodo k se realiza tomando el número m y desplazando los bits de k uno a la vez hasta que el número haya sido reemplazado por k. Cada turno corresponde a un salto de enrutamiento a la siguiente dirección intermedia; el salto es válido porque los vecinos de cada nodo son los dos resultados posibles de desplazar un 0 o 1 a su propia dirección. Debido a la estructura de los gráficos de Bruijn, cuando el último bit de k ha sido desplazado, la consulta estará en el nodo k. El nodo k responde si la clave k existe.

Ejemplo de enrutamiento con De Bruijn

Ejemplo de enrutamiento de De Bruijn

Un mensaje necesita enrutarse desde el nodo "2" (que es "010") a "6" (que es "110"), los pasos son los siguientes:

• Paso 1: El nodo 2 enruta el mensaje al Nodo 5 (usando su conexión a 2i + 1 mod8), desplaza los bits a la izquierda e inserta "1" por el lado derecho
• Paso 2: El nodo 5 enruta el mensaje al Nodo 3 (usando su conexión a 2i + 1 mod8), desplaza los bits a la izquierda e inserta "1" por el lado derecho
• Paso 3: El nodo 3 enruta el mensaje al Nodo 6 (usando su conexión a 2i mod8), desplaza los bits restantes e inserta "0" por el lado derecho.

Grado no constante de Koorde

La d-dimensional de Bruijn se puede generalizar a base k, en cuyo caso el nodo i se conecta a los nodos k * i + j módulo kd, 0 ≤ j <k. El diámetro se reduce a Θ (logk n). El nodo Koorde i mantiene los punteros en k nodos consecutivos que comienzan en el predecesor de k * i módulo kd. Cada paso de enrutamiento de Bruijn se puede emular con un número constante esperado de mensajes, por lo que el enrutamiento utiliza O (logk n) saltos esperados- Para k = Θ (log n), obtenemos Θ (log n) grado y Θ (log n / log log n) diámetro.