« [P2P]ネットワーク負荷を意識したファイル共有 | トップページ | P2P勉強会について »

2004.04.23

[P2P]分散ハッシュPastry

さて、昨日のBlogでは分散ハッシュを使ってファイル共有にネットワーク近さの概念を取り入れる事を試みた。今回は分散ハッシュにネットワークの近さの概念を取り入れているPastryを紹介していきたい。
Pastryについては以下のページ、文献が参考になる。

Pastryについて
http://freepastry.rice.edu/
http://freepastry.rice.edu/PAST/overview.pdf

PastryはルーティングにPlaxtonアルゴリズムという面白い方法を取り入れている。例えばNode_ID=123456というノードのルーティングテーブルは、1番上の数字(つまり上から1桁目)が1以外であるノードの集合(これを集合1とする)、1番目の数字が1だが2番目の数字が2以外であるノードの集合(これを集合2とする)、1番目の数字が1で2番目の数字が2だが3番目の数字が3以外であるノードの集合(これを集合3とする),,,,というもので構成されている。上から最長一致したノードへ検索が転送されるわけである。

さて、上記の文献ではネットワークの近さを取り入れた方法について書いていない。これは以下の文献を見て欲しい。
Pastry

これを見ると、ノードが参加するときにルーティングテーブルを構築する方法が上手い。今、AとB、BとC、CとDがそれぞれネットワーク的に近いとしよう。そのときにZと言うネットワークが参加する。ただし、ZはAと近いとする。今、ZのNode_IDがDのNode_IDと近いとしよう。検索はZ⇒A⇒B⇒C⇒Dといくとする。このとき、ZはAからルーティングテーブル集合1を得る。次にZはBから集合2、Cから集合3...と得ることにする。ZとA、AとBが近いからといって必ずしもZとBがお互い近いとは言えないが、論文では結果的にZとBは近い関係であることを示している。そのため、このようなルーティングテーブルを持てば、ノードのネットワークに近い順に検索が行われる事が期待できる。

もっとこのことに知りたい方は次の論文を見て欲しい。

Topology-aware routing in stuctured peer to peer overlay networks

このような手法はP2Pマルチキャストを分散ハッシュで構築する時に活かされるはずだ。

|

« [P2P]ネットワーク負荷を意識したファイル共有 | トップページ | P2P勉強会について »

P2P」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/18781/483117

この記事へのトラックバック一覧です: [P2P]分散ハッシュPastry:

« [P2P]ネットワーク負荷を意識したファイル共有 | トップページ | P2P勉強会について »