Koorde

I peer-to-peer- nätverk är Koorde ett distribuerat hashtabellsystem (DHT) baserat på Chord DHT och De Bruijn-grafen ( De Bruijn-sekvensen ). Koorde ärver enkelheten hos Chord och möter $O (log n)$ hopp per nod (där $n$ är antalet noder i DHT), och $O\left( {\frac {\log n}{\log(\log n)}}\right)$ hopp per uppslagsbegäran med $O (log n)$ grannar per nod.

Chord-konceptet är baserat på ett brett spektrum av identifierare (t.ex. 2 ¹⁶⁰ ) i en struktur av en ring där en identifierare kan stå för både nod och data. Nod-efterträdare är ansvarig för hela skalan av ID:n mellan sig själv och sin föregångare.

De Bruijns grafer

A de Bruijns 3-dimensionella graf

Koorde är baserad på Chord men också på De Bruijn-grafen ( De Bruijn-sekvensen) . I en $d$ -dimensionell de Bruijn-graf finns det $2 d-$ noder , som var och en har ett unikt ID med $d-$ bitar . Noden med ID $i är$ $2 i mod 2d kopplad$ till noderna och $2 i + 1 mod 2d$ . Tack vare denna egenskap routingalgoritmen dirigera till vilken destination som helst i $d$ -hopp genom att successivt "skifta in" bitarna i destinations-ID:t men bara om dimensionerna på avståndet mellan $mod 1 d$ och $3 d$ är lika.

Att dirigera ett meddelande från nod $m$ till nod $k$ åstadkoms genom att ta talet $m$ och skifta in bitarna av $k$ en i taget tills talet har ersatts av $k$ . Varje skift motsvarar ett dirigeringshopp till nästa mellanliggande adress; hoppet är giltigt eftersom varje nods grannar är de två möjliga resultaten av att flytta en 0 eller 1 till sin egen adress. På grund av strukturen hos de Bruijn-grafer, när den sista biten av $k$ har flyttats, kommer frågan att vara vid nod $k$ . Nod $k$ svarar om nyckel $k$ existerar.

Exempel på routing

Exempel på hur Koorde färdas från nod 2 till nod 6 med hjälp av en 3-dimensionell, binär graf

Till exempel, när ett meddelande måste dirigeras från nod 2 (som är 010 ) till 6 (vilket är 110 ), är stegen följande:

Nod 2 dirigerar meddelandet till Nod 5 (med dess anslutning till $2 i + 1 mod 8$ ), flyttar bitarna åt vänster och sätter 1 som den yngsta biten (höger sida).
Nod 5 dirigerar meddelandet till Nod 3 (med dess anslutning till $2 i + 1 mod 8$ ), flyttar bitarna åt vänster och sätter 1 som den yngsta biten (höger sida).
0 Nod 3 dirigerar meddelandet till Nod 6 (med dess anslutning till $2 i mod 8$ ), flyttar bitarna åt vänster och lägger som den yngsta biten (höger sida).

Icke-konstant grad Koorde

Den $d$ -dimensionella de Bruijn kan generaliseras till basen $k$ , i vilket fall nod $i$ är ansluten till noderna $k • i + j mod kd$ , $0 \leq j < k$ . Diametern reduceras till $Θ ( log k n$ ) . Koordnod $i$ upprätthåller pekare till $k$ på varandra följande noder som börjar vid föregångaren till $k • i mod kd$ . Varje de Bruijn routingsteg kan emuleras med ett förväntat konstant antal meddelanden, så routing använder $Θ(log n ) O$ $(log k n)$ förväntade hopp- För $k = Θ(log n)$ får vi grad och $\Theta \left({\frac {\log n}{\log(\log n)}}\right)$ diameter.

Uppslagsalgoritm

   

        
         
         
               
    
           
 funktion  n  .  lookup  (  k  ,  shift  ,  i  )  {  if  k  ∈  (  n  ,  s  ]  return  (  s  )  ;  else  if  i  ∈  (  n  ,  s  ]  return  p  .  lookup  (  k  ,  shift  <<  1  ,  i  ∘  topBit  (  shift  ))  ;  else  return  s  .  lookup  (  k  ,  shift  ,  i  )  ;  }

Pseudokod för Koorde-uppslagsalgoritmen vid nod n :

k är nyckeln
Jag är den imaginära De Bruijn-noden
p är referensen till föregångaren till 2n
s är hänvisningen till efterträdaren till n

"Internet Algorithms" av Greg Plaxton, hösten 2003: [1]
"Koorde: A simple degree-optimal distributed hash table" av M. Frans Kaashoek och David R. Karger: [2]
Ackord och Koorde beskrivningar: [3]