Jak działa wypełnianie tabeli routingu ciasta?

Próbuję wdrożyć tabelę rozproszonego mieszania ciasta, ale niektóre rzeczy wymykają mi się z zrozumienia. Miałem nadzieję, że ktoś to wyjaśni.

Oświadczenie : Nie jestem studentem informatyki. W życiu wziąłem dokładnie dwa kursy informatyki i żadne z nich nie dotyczyło niczego skomplikowanego. Pracuję z oprogramowaniem od lat, więc czuję, że jestem gotowa do wykonania zadania, gdybym mógł po prostu ominąć pomysły. Więc może po prostu brakuje mi czegoś oczywistego.

Przeczytałem artykuł opublikowany przez autorów [1] i poczyniłem pewne postępy, ale wciąż jestem zawieszony na tym jednym punkcie, w którym działa tabela routingu:

Artykuł twierdzi, że

Tabela routingu węzła, , jest zorganizowana w z których zawiera wpisy. Do wpisy w wierszu tabeli trasowania każdego odniesieniu do węzła, który nodeid akcje obecnego węzła nodeid w fi RST N cyfr, ale których p cyfra jest jednym z możliwych wartościach inna niż cyfra w identyfikatorze bieżącego węzła.⌈ log 2 b N ⌉ 2 b - 1 2 b - 1 n n + 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$

oznacza zmienną specyficznych dla aplikacji, zazwyczaj . Dla uproszczenia zastosujmy . Więc powyższe jest4 b = $b$$4$$b=4$

Tabela routingu węzła, , jest zorganizowana w każdy z pozycjami. Do wpisów w wierszu tabeli trasowania każdego odniesieniu do węzła, który nodeid akcje obecnego węzła nodeid w fi RST N cyfr, ale których p cyfra jest jednym z możliwych wartości inny niż cyfra w identyfikatorze obecnego węzła.⌈ 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$

Tyle rozumiem Ponadto oznacza liczbę serwerów w klastrze. Też to rozumiem.$N$

Moje pytanie brzmi: jeśli wiersz, w którym znajduje się wpis, zależy od wspólnej długości klucza, dlaczego pozornie losowy limit liczby wierszy? Każdy identyfikator węzła ma 32 cyfry, gdy (128-bitowy identyfikator węzła podzielony na cyfry bitów). Co się stanie, gdy wystarczająco wysoką wartość, aby ? Zdaję sobie sprawę, że zajęłoby to 340 282 366,920,938,463,463,374,607,431,768,211,457 (jeśli moja matematyka ma rację) serwerów, aby przejść do tego scenariusza, ale wydaje się to dziwnym włączeniem, a korelacja nigdy nie jest wyjaśniona.N ⌈ log 16 N ⌉ > $b=4$$N$$\lceil\log_{16} N\rceil > 32$

Co się stanie, jeśli masz niewielką liczbę serwerów? Jeśli mam mniej niż 16 serwerów, mam tylko jeden wiersz w tabeli. Ponadto pod żadnym pozorem nie każdy wpis w wierszu miałby odpowiedni serwer. Czy wpisy powinny być puste? Zdaję sobie sprawę, że będę w stanie znaleźć serwer w zestawie liści bez względu na wszystko, biorąc pod uwagę, że niewiele serwerów, ale ten sam problem jest generowany w drugim rzędzie - co jeśli nie mam serwera, który ma nodeId tak, że mogę wypełnić każdą możliwą permutację n-tej cyfry? Wreszcie, jeśli mam, powiedzmy, cztery serwery i mam dwa węzły, które dzielą, powiedzmy, 20 z ich 32 cyfr, przez jakiś losowy przypadek ... czy powinienem wypełnić 20 wierszy tabeli dla tego węzła, nawet jeśli jest to znacznie więcej rzędów, niż mogłem nawet zbliżyć się do wypełnienia?

Oto, co wymyśliłem, próbując uzasadnić moją drogę przez to:

1. Wpisy należy ustawić na wartość zerową, jeśli nie ma węzła dokładnie pasującego do tego prefiksu.
2. Puste wiersze należy dodawać, dopóki nie będzie wystarczającej liczby wierszy, aby dopasować długość współdzieloną nodeIds.
3. Jeśli i tylko wtedy, gdy nie ma pasującego wpisu dla żądanego identyfikatora wiadomości, wróć do wyszukiwania w tablicy routingu dla identyfikatora nodeId, którego wspólna długość jest większa lub równa bieżącemu identyfikatorowi nodeID i którego wpis jest matematycznie bliższy niż bieżący nodeId's do żądanego identyfikatora.
4. Jeśli w punkcie 3 nie można znaleźć odpowiedniego węzła, załóż, że jest to miejsce docelowe i dostarcz wiadomość.

Czy wszystkie cztery z tych założeń się utrzymują? Czy jest gdzieś indziej powinienem szukać informacji na ten temat?

1. Ciasto: Skalowalna, zdecentralizowana lokalizacja i routing obiektów dla dużych systemów peer-to-peer autorstwa A. Rowstronga i P. Druschela (2001) - pobierz tutaj

Ideą tabeli routingu w cukiernictwie (i wszystkich strukturowanych sieciach P2P) jest zminimalizowanie jej rozmiaru, przy jednoczesnym zagwarantowaniu szybszego routingu.

Algorytm routingu Pastry wygląda następująco:

$A$$A$

$u$

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

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

Przykład w typowym scenariuszu: jeśli adres u to 1111, a obiekt ma identyfikator 4324: oto, co się stanie: (zakładamy, że jest on podstawą 4. (tzn. Adresy pochodzą z [1-4] [1- 4] [1-4] [1-4]).$A$

Węzeł Dzieli 0 prefiks z obiektu . Dlatego wygląda na wiersz 0. Zgodnie z powyższą regułą 2, węzeł przechowuje adresy węzłów 1XXX, 2XXX, 3XXX, 4XXX, gdzie X jest wartością „nietraktowaną”. Najbliższym z tych węzłów do jest 4XXX. - Powiedzmy, że to jest rzeczywiście 4XXX 4013. Wtedy do przodu, aby o adresie 4013. Teraz masz zamiar powtórzyć to samo ponownie w węźle o adresie 4013.U u U 1 U $u$$A$$u$$A$$u$$u _1$$u _1$

Aby uprościć, oto kolejny przykład tego, jak pójdzie w 4013. najpierw poszuka wspólnego prefiksu rozmiaru między 4013 a 4324, który wynosi 1. Więc przechodzi do wiersza 1, który zawiera wartości takie jak 41XX, 42XX, 43XX, 44XX. Zamknięcie wśród nich do to 43XX. - jeśli było to 4331, to będzie do przodu.$u _1$$A$

Maksymalna liczba chmielów tutaj wynosi 4 chmiel (XXXX)! w kategoriach cukierniczych jest to . Tak więc zmniejsza się wraz ze wzrostem . Ale wielkość rzędów, które są , wzrośnie! - więc autorzy powiedzieli, że = 4 to dobra równowaga! b 2 b$log_{2^b}$$b$$2^b$$b$

Praktyczne scenariusze zwykle nie są typowe. Mogą występować sytuacje, w których nie ma wielu węzłów w sieci. dlatego wykonujemy krok C powyżej. - Jednak, aby upewnić się, że ten algorytm jest poprawny, należy podłączyć każdy węzeł do najbliższych dwóch węzłów (pod względem identyfikatorów). To utworzy pierścień uporządkowanych węzłów [np. 1-> 3-> 4-> 9-> 10-> 11-> 1]