[P2P]分散ハッシュPastry

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

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

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

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

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

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

Topology-aware routing in stuctured peer to peer overlay networks

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