コーデ

ピアツーピアネットワークでは、 Koorde はChord DHTとDe Bruijn グラフ( De Bruijn シーケンス)に基づく分散ハッシュテーブル(DHT) システムです。Koorde は Chord のシンプルさを継承し、ノードあたり $O$ $(log$ $n$ $)$ ホップ( $n$ は DHT 内のノード数) と、ノードあたり $O$ $(log$ $n$ $)$ の隣接ノードを持つ検索要求あたり⁠ ⁠ホップを実現します。 $O\left({\frac {\log n}{\log(\log n)}}\right)$

Chord の概念は、識別子がノードとデータの両方を表すことができるリング構造内の広範囲の識別子(例: 2 ¹⁶⁰ ) に基づいています。後続ノードは、自身とその先行ノード間の ID の全範囲を担当します。

デ・ブリュインのグラフ

Koorde は Chord に基づいていますが、 De Bruijn グラフ( De Bruijn シーケンス)にも基づいています。d $次元の de Bruijn グラフには$ $2 d 個の$ ノードがあり、各ノードには $d$ ビットの一意のIDがあります。ID $i$ を持つノードは、 $2$ $i$ $mod$ $2$ $d の$ ノードと $2$ $i$ $+ 1 mod 2$ $d$ のノードに接続されています。この特性により、ルーティングアルゴリズムは、宛先 ID のビットを連続的に「シフトイン」することで $d$ ホップで任意の宛先にルーティングできますが、 $mod 1$ $d$ と $3$ $d$ の間の距離の次元が等しい場合に限られます。

$ノードm$ からノード $k$ へのメッセージのルーティングは、数値 $m$ を取り、数値が $kに置き換えられるまで$ $k$ のビットを1 つずつシフトすることで実現されます。各シフトは、次の中間アドレスへのルーティングホップに対応します。各ノードの隣接ノードは、0 または 1 を自身のアドレスにシフトした 2 つの可能な結果であるため、ホップは有効です。de Bruijn グラフの構造により、 $k$ の最後のビットがシフトされると、クエリはノード $k$ に送信されます。ノード $k は、$ キー $k が$ 存在するかどうかを応答します。

ルーティング例

Koorde が 3 次元バイナリグラフを使用してノード 2 からノード 6 にルーティングする方法の例

たとえば、メッセージをノード 2 ( 010) からノード 6 ( 110) にルーティングする必要がある場合、手順は次のようになります。

$ノード 2 はメッセージをノード 5 にルーティングし ( 2 i + 1 mod 8$ への接続を使用)、ビットを左にシフトして、1最も若いビット (右側) として配置します。
$ノード 5 はメッセージをノード 3 にルーティングし ( 2 i + 1 mod 8$ への接続を使用)、ビットを左にシフトして、1最も若いビット (右側) として配置します。
ノード 3 はメッセージをノード 6 にルーティングし ( $2 i mod 8$ への接続を使用)、ビットを左にシフトして、0最も若いビット (右側) として配置します。

非定数次数コーデ

d次元 $のde Bruijn は、$ 基数 $k$ に一般化できます。この場合、ノード $i$ はノード $k • i + j mod kd$ に接続されます( $0 \leq j < k$ ) 。直径は $Θ (log k n)$ に縮小されます。Koord ノード $i は、$ $k$ $•$ $i$ $mod$ $kd$ の先行ノードから始まる $k 個$ の連続するノードへのポインターを維持します。各 de Bruijn ルーティングステップは、予想される定数個のメッセージでエミュレートできるため、ルーティングでは $O$ $(log$ $k$ $n$ $)$ の予想されるホップが使用されます。k = Θ(log n ) の場合 $、$ $次数$ $Θ$ $($ log n $)$ $と$ $直径$ が得られます。 $\Theta \left({\frac {\log n}{\log(\log n)}}\right)$

ルックアップアルゴリズム

関数n.lookup ( k , shift , i ) { k ∈ ( n , s ]の場合はsを返します。そうでない場合はi ∈ ( n , s ]の場合はp.lookup ( k , shift << 1 , i∘topBit ( shift ))を返します。そうでない場合はs.lookup ( k , shift , i )を返します。}

ノードにおけるKoorde検索アルゴリズムの疑似コードn:

k鍵は
Iは架空の De Bruijn ノードです
pの前身への言及である2n
sは、n

参考文献

「インターネットアルゴリズム」グレッグ・プラクストン著、2003年秋: [1]
M. Frans Kaashoek と David R. Karger による「Koorde: シンプルな次数最適分散ハッシュテーブル」: [2]
コードとコードの説明: [3]