Comment fonctionne la table de routage de Populating Pastry?

J'essaie d'implémenter la table de hachage distribuée de pâtisserie, mais certaines choses échappent à ma compréhension. J'espérais que quelqu'un pourrait clarifier.

Avertissement : je ne suis pas un étudiant en informatique. J'ai suivi précisément deux cours d'informatique au cours de ma vie, et ni l'un ni l'autre ne s'est occupé de quoi que ce soit de complexe à distance. Je travaille avec des logiciels depuis des années, donc je sens que je suis à la hauteur de la tâche de mise en œuvre, si je pouvais simplement tourner la tête autour des idées. Donc, je manque peut-être quelque chose d'évident.

J'ai lu l'article que les auteurs ont publié [1], et j'ai fait de bons progrès, mais je continue de me bloquer sur ce point particulier dans le fonctionnement de la table de routage:

Le document affirme que

La table de routage d'un nœud, $R$ , est organisée en $\lceil \log_{2^b} N\rceil$ lignes avec entrées chacune. Les entrées de la ligne de la table de routage se réfèrent chacune à un nœud dont nodeId partage le nodeId du nœud actuel dans les n premiers chiffres, mais dont ème chiffre a l'une des valeurs possibles autre que le ème chiffre de l'identifiant du nœud actuel.$2^b - 1$$2^b - 1$$n$$n + 1$$2^b - 1$$n + 1$

Le représente une variable spécifique à l'application, généralement 4 . Utilisons b = 4 , par souci de simplicité. Donc, ce qui précède est$b$$4$$b=4$

La table de routage d'un nœud, $R$ , est organisée en $\lceil \log_{16} N\rceil$ lignes avec $15$ entrées chacune. Les $15$ entrées de la ligne $n$ de la table de routage se réfèrent chacune à un nœud dont nodeId partage le nodeId du nœud actuel dans les n premiers chiffres, mais dont $n + 1$ ème chiffre a l'une des $2^b - 1$ valeurs possibles autres que le $n + 1$ ième chiffre dans l'ID du nœud actuel.

Je comprends ça. De plus, est le nombre de serveurs dans le cluster. Je comprends ça aussi.$N$

Ma question est la suivante: si la ligne dans laquelle une entrée est placée dépend de la longueur partagée de la clé, pourquoi la limite apparemment aléatoire du nombre de lignes? Chaque nodeId a 32 chiffres, lorsque (128 bits nodeIds divisé en chiffres de b bits). Alors, que se passe-t-il lorsque devient suffisamment haut pour ? Je me rends compte qu'il faudrait 340,282,366,920,938,463,463,374,607,431,768,211,457 serveurs (si mes calculs sont exacts) pour atteindre ce scénario, mais cela semble être une inclusion étrange, et la corrélation n'est jamais expliquée.N ⌈ log 16 N ⌉ > $b=4$$N$$\lceil\log_{16} N\rceil > 32$

De plus, que se passe-t-il si vous avez un petit nombre de serveurs? Si j'ai moins de 16 serveurs, je n'ai qu'une seule ligne dans le tableau. De plus, en aucun cas, chaque entrée de la ligne n'aurait un serveur correspondant. Les entrées doivent-elles être laissées vides? Je me rends compte que je serais en mesure de trouver le serveur dans le jeu de feuilles, peu importe quoi, étant donné que peu de serveurs, mais le même dilemme est soulevé pour la deuxième ligne - et si je n'ai pas de serveur qui a un nodeId de telle sorte que je puisse remplir toutes les permutations possibles du nième chiffre? Enfin, si j'ai, disons, quatre serveurs, et j'ai deux nœuds qui partagent, disons, 20 de leurs 32 chiffres, par un hasard aléatoire ... dois-je remplir 20 lignes de la table pour ce nœud, même si c'est beaucoup plus de rangées que je ne pourrais même en approcher?

Voici ce que j'ai trouvé, en essayant de raisonner mon chemin à travers cela:

1. Les entrées doivent être définies sur une valeur nulle s'il n'y a pas de nœud correspondant exactement à ce préfixe.
2. Des lignes vides doivent être ajoutées jusqu'à ce que suffisamment de lignes existent pour correspondre à la longueur partagée des nodeIds.
3. Si, et seulement si, il n'y a pas d'entrée correspondante pour un ID de message souhaité, retombez sur une recherche dans la table de routage pour un nodeId dont la longueur partagée est supérieure ou égale aux nodeId actuels et dont l'entrée est mathématiquement plus proche que l'actuelle nodeId est à l'ID souhaité.
4. Si aucun nœud approprié ne peut être trouvé dans # 3, supposez qu'il s'agit de la destination et remettez le message.

Ces quatre hypothèses sont-elles valables? Y a-t-il un autre endroit où je devrais chercher des informations à ce sujet?

1. Pâtisserie: localisation et routage d'objets décentralisés et évolutifs pour les systèmes peer-to-peer à grande échelle par A. Rowstrong et P. Druschel (2001) - télécharger ici

L'idée d'une table de routage en Pâtisserie (et tous les réseaux P2P structurés) est de minimiser sa taille, tout en garantissant un routage plus rapide.

L'algorithme de routage de Pastry se présente comme suit:

Étape A. Un nœud u recherche un objet A en le recherchant d'abord dans son jeu de feuilles. Étape B. Si elle n'était pas disponible, la requête est transmise à un nœud connu qui partage "un certain nombre de préfixes avec $A$ qui est au moins plus grand que ce que le nœud u partage avec A". Étape C. Si un tel enregistrement est introuvable, la requête est transmise à un noeud dans l'ensemble de la feuille qui est numériquement le plus proche de .$A$

C'est pourquoi un nœud stocke les adresses des nœuds organise sa table comme suit:$u$

Chaque enregistrement de la ligne de la table de routage du nœud u est un identifiant de nœud qui partage i bits de préfixe avec l'identifiant de u .$i$$u$$i$$u$

2.Le bit des enregistrements d'une ligne i est unique et provient de l'ensemble { 0 , … , 2 b - 1 } .$(i + 1)^{th}$$i$$\{0, …, 2^{b} – 1\}$

Exemple dans un scénario typique: si l'adresse u est 1111 et l'objet a l'identifiant 4324: alors voici ce qui se passera: (nous supposons qu'elle est de la base de 4. (ie les adresses sont de [1-4] [1- 4] [1-4] [1-4]).$A$

Noeud partage 0 préfixe avec un objet A . Par conséquent, il apparaît dans la ligne 0. Selon la règle 2 ci-dessus, le nœud u stocke les adresses des nœuds 1XXX, 2XXX, 3XXX, 4XXX, où X est une valeur "ne vous souciez pas". Le plus proche de ces nœuds à A est 4XXX. - Disons que ce 4XXX est en fait 4013. Ensuite, u transmet à u 1 avec l'adresse 4013. Maintenant, vous allez répéter la même chose au nœud u 1 avec l'adresse 4013.$u$$A$$u$$A$$u$$u _1$$u _1$

$u _1$$A$

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

Les scénarios pratiques ne sont généralement pas typiques comme ça. Il peut y avoir des situations dans lesquelles il n'y a pas beaucoup de nœuds dans le réseau. c'est pourquoi nous suivons l'étape C ci-dessus. - Cependant, ce que vous devez garantir pour que cet algorithme soit correct, c'est que chaque nœud soit connecté aux deux nœuds les plus proches (en termes d'identifiants). Cela formera un anneau de nœuds ordonnés [par exemple 1-> 3-> 4-> 9-> 10-> 11-> 1]