Chord

この項目では、アルゴリズムについて説明しています。その他の用法については「コード」をご覧ください。

Chordは、分散ハッシュテーブルを実現するアルゴリズムの一つ。P2Pネットワークにおいて、サーバを用いることなく高速にコンテンツの検索、ルーティングを行う手法。

アルゴリズム

Chordでは、コンテンツのハッシュ値を求める関数にSHA-1を採用するのが一般的である。ネットワークに参加するノードは、SHA-1のハッシュ値の値域${\displaystyle 0\leq NodeID\leq 2^{160}-1}$を満たす一意な${\displaystyle NodeID}$が割り当てられる。

ここで、${\displaystyle next(x)}$という関数を定義する。この関数は、ハッシュ値${\displaystyle x}$が与えられたとき、値を増加させる方向で次に存在しているノードの${\displaystyle NodeID}$を返す。なお、${\displaystyle 2^{160}-1}$と${\displaystyle 0}$は接続されていると考える。

ネットワークで情報を共有する際には、共有したい情報のハッシュ値を${\displaystyle x}$として${\displaystyle NodeID=next(x)}$を満たす${\displaystyle NodeID}$を持つノードが、実際に情報を保持しているノードの位置を示すIPアドレス等の情報を保持する。

また、ネットワークに参加するノードは、自身の${\displaystyle NodeID}$を${\displaystyle MyNodeID}$とした場合、

${\displaystyle next(Z)}$, ただし${\displaystyle Z=MyNodeID+2^{i}mod2^{160}(0\leq i<160)}$

の${\displaystyle NodeID}$をもつノードのIPアドレスをルーティングテーブルとして保持する。

共有されている情報を検索する際には、検索したい情報のハッシュ値を${\displaystyle y}$としたとき、${\displaystyle NodeID}$として${\displaystyle next(y)}$が割り当てられているノードを各ノードのルーティングテーブルを利用して検索することになる。

参考文献

• Ion Stoica; Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan (2001). “Chord: A scalable peer-to-peer lookup service for internet applications”. ACM SIGCOMM Computer Communication Review (New York, NY, USA: ACM Press) 31 (4): 149 - 160. doi:10.1145/964723.383071.

外部リンク

• Chord project Chord を使ってP2Pネットワークを構築するプロジェクト