Chord

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

アルゴリズム

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

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

ネットワークで情報じょうほうを共有きょうゆうする際さいには、共有きょうゆうしたい情報じょうほうのハッシュ値ちを$x$として$NodeID=next(x)$を満みたす$NodeID$を持もつノードが、実際じっさいに情報じょうほうを保持ほじしているノードの位置いちを示しめすIPアドレス等ひとしの情報じょうほうを保持ほじする。

また、ネットワークに参加さんかするノードは、自身じしんの$NodeID$を$MyNodeID$とした場合ばあい、

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

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

共有きょうゆうされている情報じょうほうを検索けんさくする際さいには、検索けんさくしたい情報じょうほうのハッシュ値ちを$y$としたとき、$NodeID$として$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ネットワークを構築こうちくするプロジェクト