Como a tabela de roteamento de preenchimento de pastelaria funciona?

Estou tentando implementar a tabela de hash distribuído de pastelaria, mas algumas coisas estão escapando do meu entendimento. Eu esperava que alguém pudesse esclarecer.

Disclaimer : Eu não sou um estudante de ciência da computação. Fiz exatamente dois cursos de ciência da computação em minha vida e nem lidei com nada remotamente complexo. Eu trabalho com software há anos, então sinto que estou pronto para a tarefa de implementação, se eu pudesse entender as idéias. Então, posso estar perdendo algo óbvio.

Eu li o artigo que os autores publicaram [1], e fiz alguns bons progressos, mas continuo me prendendo a esse ponto específico de como a tabela de roteamento funciona:

O artigo afirma que

A tabela de roteamento de um nó, , é organizada em linhas ⌈ log 2 b N with com 2 entradas b - 1 cada. As entradas 2 b - 1 na linha n da tabela de roteamento referem-se a um nó cujo nodeId compartilha o nodeId do nó atual nos primeiros n dígitos, mas cujo n + 1 o dígito possui um dos 2 valores possíveis b - 1 diferentes de o n + 1 º dígito no ID do nó atual.$R$$\lceil \log_{2^b} N\rceil$$2^b - 1$$2^b - 1$$n$$n + 1$$2^b - 1$$n + 1$

O representa uma variável específica da aplicação, normalmente quatro . Vamos usar b = 4 , por uma questão de simplicidade. Então, o acima é$b$$4$$b=4$

A tabela de roteamento de um nó, , é organizada em ⌈ log 16 N ⌉ linhas com 15 entradas cada. As 15 entradas na linha n da tabela de roteamento referem-se a um nó cujo nodeId compartilha o nodeId do nó atual nos primeiros n dígitos, mas cujo n + 1 o dígito possui um dos 2 valores possíveis b - 1 diferentes de n + 1º dígito no ID do nó atual.$R$$\lceil \log_{16} N\rceil$$15$$15$$n$$n + 1$$2^b - 1$$n + 1$

Eu entendo isso. Além disso, é o número de servidores no cluster. Eu também entendo.$N$

Minha pergunta é: se a linha em que uma entrada é colocada depende do tamanho compartilhado da chave, por que o limite aparentemente aleatório do número de linhas? Cada nodeId possui 32 dígitos, quando (nodeIds de 128 bits dividido em dígitos de b bits). Então, o que acontece quando N fica alto o suficiente para que $b=4$$N$ ? Sei que seriam necessários 340.282.366.920.938.463.463.374.607.431.768.211.457 servidores (se minha matemática estiver correta) para atingir esse cenário, mas parece uma inclusão estranha e a correlação nunca é explicada.$\lceil\log_{16} N\rceil > 32$

Além disso, o que acontece se você tiver um pequeno número de servidores? Se eu tiver menos de 16 servidores, tenho apenas uma linha na tabela. Além disso, em nenhuma circunstância todas as entradas na linha teriam um servidor correspondente. As entradas devem ser deixadas em branco? Percebo que eu seria capaz de encontrar o servidor no conjunto folha, não importa o que aconteça, considerando que poucos servidores, mas o mesmo dilema é aumentado para a segunda linha - e se eu não tiver um servidor com um nodeId tal que eu possa preencher todas as permutações possíveis do enésimo dígito? Finalmente, se eu tiver, digamos, quatro servidores, e tiver dois nós que compartilhem, digamos, 20 de seus 32 dígitos, por algum acaso aleatório ... devo preencher 20 linhas da tabela para esse nó, mesmo que seja muito mais linhas do que eu poderia chegar perto de preencher?

Aqui está o que eu inventei, tentando explicar o meu caminho através disso:

1. As entradas devem ser configuradas para um valor nulo se não houver um nó que corresponda exatamente a esse prefixo.
2. Linhas vazias devem ser adicionadas até que existam linhas suficientes para corresponder ao comprimento compartilhado dos nodeIds.
3. Se, e somente se, não houver uma entrada correspondente para um ID de mensagem desejado, faça uma busca na tabela de roteamento por um nodeId cujo comprimento compartilhado seja maior ou igual ao nodeId atual e cuja entrada seja matematicamente mais próxima que a atual nodeId para o ID desejado.
4. Se nenhum nó adequado puder ser encontrado no item 3, assuma que este é o destino e entregue a mensagem.

Todas essas quatro suposições se sustentam? Existe algum outro lugar que eu deveria estar procurando informações sobre isso?

1. Pastelaria: localização e roteamento descentralizado e descentralizado de objetos para sistemas ponto a ponto em larga escala por A. Rowstrong e P. Druschel (2001) - download aqui

A idéia de uma tabela de roteamento no Pastry (e todas as redes P2P estruturadas) é minimizar seu tamanho, garantindo um roteamento mais rápido.

O algoritmo de roteamento do Pastry é o seguinte:

$A$$A$ .

$u$

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

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

$A$ tiver o identificador 4324: eis o que acontecerá: (presumimos que seja da base de 4.) (ou seja, os endereços são de [1-4] [1- 4] [1-4] [1-4]).

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

$u _1$$A$ é 43XX. - se este foi 4331, será encaminhado em sua direção.

$log_{2^b}$$b$$2^b$$b$ = 4 é um bom equilíbrio!

Cenários práticos geralmente não são típicos assim. Pode haver situações em que não há muitos nós na rede. é por isso que seguimos a etapa C acima. - No entanto, o que você precisa garantir para corrigir esse algoritmo é que cada nó seja conectado aos dois nós mais próximos (em termos de identificadores). Isso formará um anel de nós ordenados [por exemplo, 1-> 3-> 4-> 9-> 10-> 11-> 1]