Koorde

W sieciach peer-to-peer Koorde jest systemem rozproszonej tablicy skrótów (DHT) opartym na Chord DHT i grafie De Bruijn ( sekwencja De Bruijn ). Dziedzicząc prostotę Chorda, Koorde spełnia O (log n ) przeskoków na węzeł (gdzie n to liczba węzłów w DHT) i ${\ Displaystyle O \ lewo ({\ Frac {\ log n} {\ log (\ log n)}} \ right)}$ przeskoków na żądanie wyszukiwania z O (log n ) sąsiadami na węzeł.

Koncepcja Chord opiera się na szerokim zakresie identyfikatorów (np. 2 ¹⁶⁰ ) w strukturze pierścienia , gdzie identyfikator może oznaczać zarówno węzeł, jak i dane. Node-successor odpowiada za cały zakres identyfikatorów między sobą a swoim poprzednikiem.

Grafy De Bruijna

Trójwymiarowy wykres A de Bruijna

Koorde opiera się na akordzie, ale także na grafie De Bruijn ( sekwencja De Bruijn ). W d -wymiarowym grafie de Bruijna są 2 ^d węzłów , z których każdy ma unikalny identyfikator z d bitami . Węzeł o ID i jest połączony z węzłami 2 i mod 2 ^d oraz 2 i + 1 mod 2 ^d . Dzięki tej właściwości algorytm routingu może wyznaczać trasy do dowolnego miejsca docelowego w d przeskakuje sukcesywnie „przesuwając” bity identyfikatora celu, ale tylko wtedy, gdy wymiary odległości między mod 1 d i 3 d są równe.

Trasowanie wiadomości z węzła m do węzła k odbywa się poprzez wzięcie liczby m i przesuwanie bitów k jeden po drugim, aż liczba zostanie zastąpiona przez k . Każde przesunięcie odpowiada przeskokowi trasy do następnego adresu pośredniego; przeskok jest ważny, ponieważ sąsiedzi każdego węzła to dwa możliwe wyniki przesunięcia 0 lub 1 na jego własny adres. Ze względu na strukturę grafów de Bruijna, gdy ostatni bit k zostanie przesunięty, zapytanie będzie w węźle k . Węzeł k odpowiada, czy klucz k istnieje.

Przykład routingu

Przykład sposobu, w jaki Koorde wyznacza trasy od węzła 2 do węzła 6 przy użyciu trójwymiarowego wykresu binarnego

Na przykład, gdy wiadomość musi zostać przekierowana z węzła 2 (czyli 010 ) do 6 (czyli 110 ), należy wykonać następujące kroki:

1. Węzeł 2 kieruje wiadomość do węzła 5 (używając swojego połączenia z 2 i + 1 mod 8 ), przesuwa bity w lewo i umieszcza 1 jako najmłodszy bit (po prawej stronie).
2. Węzeł 5 kieruje wiadomość do węzła 3 (korzystając z połączenia z 2 i + 1 mod 8 ), przesuwa bity w lewo i umieszcza 1 jako najmłodszy bit (po prawej stronie).
3. 0 Węzeł 3 kieruje wiadomość do Węzła 6 (wykorzystując swoje połączenie do 2 i mod 8 ), przesuwa bity w lewo i umieszcza jako najmłodszy bit (prawa strona).

Niestały stopień Koorde

D - wymiarowy de Bruijn można uogólnić na podstawę k , w którym to przypadku węzeł i jest połączony z węzłami k • i + j mod kd , 0 ≤ j < k . Średnica Θ ( log _kn jest zredukowana do ) . Węzeł Koorde i utrzymuje wskaźniki do k kolejnych węzłów, zaczynając od poprzednika k • i mod kd . Każdy krok routingu de Bruijna może być emulowany z oczekiwaną stałą liczbą komunikatów, więc routing wykorzystuje O (log _k n ) oczekiwanych przeskoków - Dla k = Θ(log n ) , otrzymujemy Θ (log n ) stopień i ${\ Displaystyle \ Theta \ lewo ({\ Frac {\ log n} {\ log (\ log n)}} \ prawej)}$ średnica.

Algorytm wyszukiwania

   

        
         
         
                funkcja  n  .  wyszukiwanie  (  k  ,  przesunięcie  ,  i  )  {  jeśli  k  ∈  (  n  ,  s  ]  powrót  (  s  )  inaczej  jeśli  i  ∈  (  n  ,  s  ]  powrót  p  .  wyszukiwanie  (  k  ,  przesunięcie  <<  1  ,  i  ∘  topBit  (  _ 
    
           
 zmiana  ))  ;  w przeciwnym razie  zwróć  s  .  wyszukiwanie  (  k  ,  przesunięcie  ,  i  )  ;  } 

Pseudokod dla algorytmu wyszukiwania Koorde w węźle n :

• k jest kluczem
• I jest wyimaginowanym węzłem De Bruijna
• p jest odniesieniem do poprzednika 2n
• s jest odniesieniem do następcy n

• „Algorytmy internetowe” Grega Plaxtona, jesień 2003: [1]
• „Koorde: Prosta tabela mieszania o optymalnym stopniu rozproszenia” autorstwa M. Fransa Kaashoeka i Davida R. Kargera: [2]
• Opisy akordów i koorde: [3]