Gnutellaの図 ファイルを探す人 query hit Loop検出 ファイル取得 ファイル ノードは転送したqueryのコマンドIDを記憶。 ループしたqueryは破棄。 Hitはqueryの経路を逆向きに伝播。
query Freenetの図 hit Fail Loop検出 ファイルを探す人 1 2 12 3 7 6 4 11 9 5 10 ファイル 8
DHTの概念図 ハッシュ値の数値を円状に配置した場合の概念図 同じ数値空間上にノードとファイルが、 それぞれ一様に分布 ノードは円上で近いファイルの位置を管理 (注)実際には、広大な空間(128bitや160bit)に対して、 数千から数百万のノードやファイルの数で、 非常に疎に分布します DHTの概念図
ホップごとに探索空間が1/nずつ収束した場合、探索はO(logN)で終了(Nはノード数) 探索要求の転送 ホップごとに探索空間が1/nずつ収束した場合、探索はO(logN)で終了(Nはノード数) このノードの視野 近傍の様子は知っているが、遠くはよく知らない 青枠の探索空間に関しては、そこにいるノードに探索を転送
Pastryの探索 位置情報 探索要求 ファイルのキー:a6e5 nodeid:0d64 経路表 探索要求 ファイルのキー:a6e5 a613ノードへの経路 1 2 3 nodeid:a613 ファイルの位置情報 カラムe 1 2 a6e9ノードへの経路 3 探索要求 ファイルのキー:a6e5 0d64とa6e5のprefix一致長は0 0行目のカラムaに経路があれば、 探索要求を転送する 経路表にa613があったので、転送 a613とa6e5のprefix一致長は2 2行目のカラムeに経路があれば、 探索要求を転送する 経路表にa6e9があったので、転送 ファイルの位置情報 nodeid:a6e9 ファイルの位置情報 ファイルのキー:a6e9 カラム5 1 2 3 a6e5ノードへの経路 探索要求 ファイルのキー:a6e5 nodeid:a6e5 a6e9とa6e5のprefix一致長は3 3行目のカラム5に経路があれば、 探索要求を転送する 経路表にa6e5があったので、転送 位置情報
Pastryノード参加(経路表の構築) ノードZ leaf set ハッシュ値空間上で近いノードへの経路を保持 node ハッシュ値空間上で近いノードへの経路を保持 ノードZとノードXはハッシュ値空間上で近いので、 ノードXのleaf setの初期値としてもらう join要求: key=x ノードZ 経路表の交換 n-digitのprefix長が一致している場合 *ノードXは相手ノードの経路表のn行目をもらい、経路表のn行目に使う *相手ノードは、経路表のn行目にノードXを挿入(or 無視) join要求: key=x ノードC 経路表 ノードC join要求: key=x ノードB 下位層(IP)で、近いノードへの経路を保持 ノードXはIP的に近いノードに、最初のjoin要求を出したと仮定。 ノードAのneighborhood setを初期値としてもらう neighborhood set node ノードX: nodeid=x join要求: key=x ノードA ノードB