« 早春の網走 | トップページ | 年度末という季節 »

2004.03.21

[P2P]分散ハッシュChordと匿名性

最近、P2P(というかオーバレイネットワーク)では分散ハッシュの話題で持ちきりなので、私もその代表格のChordの文献を見てみた。詳しくはタネンバウム著「コンピュータネットワーク」日経BP社を見て欲しいのだが、まずはChordの概略とその後匿名性について簡単に議論してみたい。
※次の文献もなかなかわかりやすく書いてあります。
http://portal.acm.org/citation.cfm?id=606299&coll=portal&dl=ACM&CFID=18822239&CFTOKEN=86987481&ret=1#Fulltext


Chordは2^m(これで2のm乗を表わすことにする。)のハッシュ値の「円状」集合Sである。 x mod 2^m の時計回りで隣にはx+1 mod 2^m、逆時計回りで隣には x-1 mod 2^mがいる。あるハッシュ関数をHashとする。今、ノードAのIPアドレスをip、適当な乱数等をrとしてノードAのハッシュ値はkey_A=Hash(ip,r)で表現できる。このようなハッシュ関数を使うと円状集合にそれぞれのノードを配置することができる。ここで、必ずしも全てのハッシュ値にノードが配置されているとは限らない事に注意。

さて、Sに含まれる任意のxが仮に(x+1,x+2,...x+y)というハッシュ値についてのIP情報を持っていれば、xは任意のハッシュ値z(ただし、zに対応するノードがあるとする)のIP情報は得られそうである。これはバケツリレーでひたすら右回り(すなわちハッシュ値が増える方向)のノードにハッシュ値zはないか聞いていくということである。(ただし、この方法では連続してyだけノードが存在しないとzにたどり着かない事がある)しかし、この方法では非常にzに対応するノードにたどり着くまで遅くなる。

そこでChordは工夫をしている。あるxが知るIPアドレスのノードのハッシュ値はsuccessor(x+2^i) mod 2^mとする。(iは0以上m-1以下の全ての整数)ただし、q=successor(p)とは、p以上で一番pに近いハッシュ値で実際にノードがあるハッシュ値qを表わす。これを知ればあるハッシュ値zに対応するIPを知るまでにmのオーダーで可能となる。ハッシュ値zに対するIPアドレスの検索方法であるが、ハッシュ値zに一番自分がIPを知っているハッシュ値の近いノードに検索を依頼する。これをひたすら続けるということである。

さて、各ノードはコンテンツ名nameについてsuccessor(hash(name))に記録させておく。ただし、(name、ノードのIPアドレス)という対を記録される。こうすれば、各ノードのコンテンツ情報は分散されて配置されていく。

図がないだけにわかりにくいと思うが、詳しくは先ほど挙げた文献に丁寧にかいてある。このようにChordではNapsterのように中央サーバを使わず、Gnutellaのようにブロードキャストも使わず巨大なコンテンツ名空間、IPアドレス空間を管理する事ができる。今後はファイル共有等のP2Pアプリに分散ハッシュ値が使われる可能性は非常に高い。

ではChordの匿名性はどうだろう?あるハッシュ値xのIPアドレスを知りたいとすると、だれもがそのIPアドレスを知りうると言う事に問題がある。つまり、コンテンツ名nameを管理しているsuccesor(hash(name))のノードを調査すれば、だれがそのコンテンツを持っているかわかってしまう。

もう一つは通信方法である。通常に考えれば、ハッシュ値から対象のIPアドレスを得て、ファイルを有しているノードとファイルを要求しているノード間で直接通信する。しかし、これは匿名性を著しく落とす事になる。そこで考えられるのは、Winnyのようにあるノードをかます方法である。例えば、Chordであればzというハッシュ値を得るまでに何個ものノードを介する必要があるので、ファイル送信でもそれを使えないか?と考える事ができる。とはいっても、先ほど言ったようにsuccessor(hash(name))のIPアドレスを各ノードが知りうるのであまり効果はなさそうだ。

ハッシュ値zのIPアドレスは「わざと」返さずヒットしたことだけ返し、検索ノード間で数珠繋ぎで通信する事も考えたが、これを実現すると、新規にネットワークに参加するノードに対し、ルーティング情報を渡す事ができなくなる。
もうちょっと匿名性については考えてみたい。

Gnutellaのようなブロードキャスト方式による検索はサイズの限界が簡単に来るので、P2Pアプリでも本格的に分散ハッシュの導入を検討することもあるだろう。

|

« 早春の網走 | トップページ | 年度末という季節 »

P2P」カテゴリの記事

コメント

この記事へのコメントは終了しました。

トラックバック


この記事へのトラックバック一覧です: [P2P]分散ハッシュChordと匿名性:

» Bug/Bug40 [PukiWiki/TrackBack 0.1]
Chord Tomo's HotLine: [P2P]分散ハッシュChordと匿名性 http://toremoro.tea-nifty.com/tomos_hotline/2004/03/p2pchord.html [続きを読む]

受信: 2004.11.30 18:25

« 早春の網走 | トップページ | 年度末という季節 »