En -peer-to-peer redes, Koorde es una tabla de dispersión distribuida del sistema (DHT) basado en el acorde de DHT y la gráfica De Bruijn ( secuencia De Bruijn ). Heredando la simplicidad de Chord, Koorde cumple O (log n) saltos por nodo (donde n es el número de nodos en el DHT) y O (log n / log log n) saltos por solicitud de búsqueda con O (log n) vecinos por nodo.
El concepto Chord se basa en una amplia gama de identificadores (por ejemplo, 2 ^ 160) en una estructura de anillo donde un identificador puede representar tanto el nodo como los datos. Node-successor es responsable de toda la gama de ID entre él y su predecesor.
Gráficos de De Bruijn
Koorde se basa en acorde sino también en la gráfica De Bruijn ( secuencia De Bruijn ). En un gráfico de Bruijn de dimensión d, hay 2 nodos d , cada uno de los cuales tiene un ID único de d-bit. 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 enrutar a cualquier destino en saltos "desplazando" sucesivamente los bits del ID de destino, pero solo si las dimensiones de la distancia entre módulo 1d y 3d son iguales.
El enrutamiento de un mensaje del nodo m al nodo k se logra tomando el número my 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 posibles resultados de cambiar un 0 o un 1 a su propia dirección. Debido a la estructura de los gráficos de Bruijn, cuando se ha desplazado el último bit de k, la consulta estará en el nodo k. El nodo k responde si existe la clave k.
Ejemplo de enrutamiento
Por ejemplo, cuando un mensaje debe 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 hacia la izquierda y coloca “1” como el bit más joven (lado derecho).
Paso 2) El Nodo # 5 enruta el mensaje al Nodo # 3 (usando su conexión a 2i + 1 mod8), desplaza los bits hacia la izquierda y coloca “1” como el bit más joven (lado derecho).
Paso 3) El Nodo # 3 enruta el mensaje al Nodo # 6 (usando su conexión a 2i mod8), desplaza los bits a la izquierda y pone “0” como el bit más joven (lado derecho).
Koorde de grado no constante
La d-dimensional de Bruijn se puede generalizar a la base k, en cuyo caso el nodo i está conectado a los nodos k * i + j módulo kd, 0 ≤ j