Chord
Chordは、分散ハッシュテーブルを実現するアルゴリ���ムの一つ。P2Pネットワークにおいて、サーバを用いることなく高速にコンテンツの検索、ルーティングを行う手法。
アルゴリズム
編集Chordでは、コンテンツのハッシュ値を求める関数にSHA-1を採用するのが一般的である。ネットワークに参加するノードは、SHA-1のハッシュ値の値域 を満たす一意な が割り当てられる。
ここで、 という関数を定義する。この関数は、ハッシュ値 が与えられたとき、値を増加させる方向で次に存在しているノードの を返す。なお、 と は接続されていると考える。
ネットワークで情報を共有する際には、共有したい情報のハッシュ値を として を満たす を持つノードが、実際に情報を保持しているノードの位置を示すIPアドレス等の情報を保持する。
また、ネットワークに参加するノードは、自身の を とした場合、
, ただし
の をもつノードのIPアドレスをルーティングテーブルとして保持する。
共有されている情報を検索する際には、検索したい情報のハッシュ値を としたとき、 として が割り当てられているノードを各ノードのルーティングテーブルを利用して検索することになる。
参考文献
編集- 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ネットワークを構築するプロジェクト