¿Cómo funciona la tabla de enrutamiento de rellenar pasteles?

Estoy tratando de implementar la tabla Hash distribuida de pastelería, pero algunas cosas se me escapan. Esperaba que alguien pudiera aclarar.

Descargo de responsabilidad : no soy un estudiante de ciencias de la computación. He tomado dos cursos de ciencias de la computación en mi vida y ninguno de los dos ha tratado nada remotamente complejo. He trabajado con software durante años, por lo que creo que estoy preparado para la tarea de implementación, si pudiera entender las ideas. Así que puede que me falte algo obvio.

He leído el artículo que publicaron los autores [1], y he progresado bastante, pero sigo obsesionado con este punto en particular sobre cómo funciona la tabla de enrutamiento:

El documento afirma que

La tabla de enrutamiento de un nodo, , está organizada en filas con entradas cada una. Las 2 entradas b - 1 en la fila n de la tabla de enrutamiento se refieren a un nodo cuyo nodeId comparte el nodeId del nodo actual en los primeros n dígitos, pero cuyo n + 1 th dígito tiene uno de los valores posibles otros que el dígito en la identificación del nodo actual.⌈ log 2 b N ⌉ 2 b - 1 2 b - 1 n + $R$$\lceil \log_{2^b} N\rceil$$2^b - 1$$2^b - 1$$n$$n + 1$$2^b - 1$$n + 1$

La representa una variable específica de la aplicación, generalmente . Usemos , por simplicidad. Entonces lo anterior es4 b = $b$$4$$b=4$

La tabla de enrutamiento de un nodo, , se organiza en filas con entradas cada una. Las entradas en la fila de la tabla de enrutamiento se refieren a un nodo cuyo nodeId comparte el nodeId del nodo actual en los primeros n dígitos, pero cuyo dígito tiene uno de los valores posibles distintos del dígito en la identificación del nodo actual.⌈ log 16 N ⌉ 15 15 n n + 1 2 b - 1 n + $R$$\lceil \log_{16} N\rceil$$15$$15$$n$$n + 1$$2^b - 1$$n + 1$

Eso lo entiendo mucho. Además, es el número de servidores en el clúster. Yo también entiendo eso.$N$

Mi pregunta es, si la fila en la que se coloca una entrada depende de la longitud compartida de la clave, ¿por qué el límite aparentemente aleatorio en el número de filas? Cada nodeId tiene 32 dígitos, cuando (nodeIds de 128 bits divididos en dígitos de b bits). Entonces, ¿qué sucede cuando se suficiente como para que ? Me doy cuenta de que se necesitarían 340,282,366,920,938,463,463,374,607,431,768,211,457 (si mi matemática es correcta) para alcanzar este escenario, pero parece una inclusión extraña, y la correlación nunca se explica.N ⌈ log 16 N ⌉ > $b=4$$N$$\lceil\log_{16} N\rceil > 32$

Además, ¿qué sucede si tiene una pequeña cantidad de servidores? Si tengo menos de 16 servidores, solo tengo una fila en la tabla. Además, bajo ninguna circunstancia cada entrada en la fila tendría un servidor correspondiente. ¿Deben dejarse entradas vacías? Me doy cuenta de que podría encontrar el servidor en el conjunto de hojas sin importar qué, dado que hay pocos servidores, pero se genera el mismo dilema para la segunda fila: ¿qué pasa si no tengo un servidor que tenga un ID de nodo? tal que pueda llenar todas las permutaciones posibles del enésimo dígito? Finalmente, si tengo, digamos, cuatro servidores, y tengo dos nodos que comparten, digamos, 20 de sus 32 dígitos, por una casualidad aleatoria ... ¿Debería llenar 20 filas de la tabla para ese nodo, aunque eso sea ¿Hay muchas más filas de las que incluso podría llegar a llenar?

Esto es lo que se me ocurrió, tratando de razonar mi camino a través de esto:

1. Las entradas deben establecerse en un valor nulo si no hay un nodo que coincida con ese prefijo con precisión.
2. Se deben agregar filas vacías hasta que existan suficientes filas para que coincidan con la longitud compartida de los nodeIds.
3. Si, y solo si, no hay una entrada coincidente para un ID de mensaje deseado, recurra a una búsqueda en la tabla de enrutamiento para un nodeId cuya longitud compartida sea mayor o igual que la de los nodeId actuales y cuya entrada esté matemáticamente más cerca que la actual nodeId's a la ID deseada.
4. Si no se puede encontrar un nodo adecuado en el n. ° 3, suponga que este es el destino y entregue el mensaje.

¿Se cumplen los cuatro supuestos? ¿Hay algún otro lugar donde debería estar buscando información sobre esto?

1. Pastelería: ubicación de objetos escalable y descentralizada y enrutamiento para sistemas peer-to-peer a gran escala por A. Rowstrong y P. Druschel (2001) - descargue aquí

La idea de una tabla de enrutamiento en Pastry (y todas las redes P2P estructuradas) es minimizar su tamaño y garantizar un enrutamiento más rápido.

El algoritmo de enrutamiento de Pastry es el siguiente:

$A$$A$

$u$

$i$$u$$i$$u$

$(i + 1)^{th}$$i$$\{0, …, 2^{b} – 1\}$

$A$

$u$$A$$u$$A$$u$$u _1$$u _1$

$u _1$$A$

$log_{2^b}$$b$$2^b$$b$

Los escenarios prácticos generalmente no son típicos como eso. Puede haber situaciones en las que no haya muchos nodos en la red. Por eso seguimos el paso C anterior. - Sin embargo, lo que debe garantizar para que este algoritmo sea correcto es que cada nodo esté conectado a los dos nodos más cercanos (en términos de identificadores). Esto formará un anillo de nodos ordenados [por ejemplo, 1-> 3-> 4-> 9-> 10-> 11-> 1]