« [P2P]分散ハッシュ(DHT)入門~その5 | トップページ | [ネットワーキング]分散ハッシュ(DHT)と6次の繋がり »

2005.02.06

分散ハッシュ(DHT)入門~その6

さて、前回はDHTでのルーティングについて説明した。今回はノードがDHTに参加する場合、どうすれば良いのか説明したい。

「あいうえお」DHTで説明しよう。
このときに、ルーティングの方法は前回説明したルーティング3を用いる事にする。
つまり、
ルーティング3:
◇各ノードは各行の先頭ノードを知っている。また、各ノードは隣あうノードを知っている。

これはノード「う」であれば、
・各行の先頭ノード:ノード「あ」、ノード「か」、ノード「さ」.....ノード「わ」
・自分と隣あうノード:ノード「い」、ノード「え」

を知っている事を意味する。

単純な例を説明するため「あいうえお」DHTでノード「う」だけが現在なく、そこにノード「う」が参加することを考えてみよう。

まず、これからDHTに参加するノード「う」は、既にDHTに参加しているノードの一つを少なくとも知っている必要がある。今そのノードをノード「や」としよう。

手順1:
ノード「う」は自分がノード「う」として振舞うためにはノード「い」とノード「え」に対して自分の存在を知らせる必要がある。そのため、まずノード「う」はノード「や」を通して、ルーティング3を使ってノード「い」とノード「え」のIPアドレスを知る。

手順2:
ノード「う」はノード「い」に対して自分の存在を知らせたい。
ノード「い」に対してノード「う」は自分がノード「う」である事を表明し、また自分のIPアドレスを教える。このコマンドを例えば
Join(ノード「う」⇒ノード「い」)
と定義しよう。

ノード「い」のルーティングテーブルは、隣り合うノードの部分についてはノード「あ」とノード「え」であったが、
これが、ノード「あ」とノード「い」に変更する必要がある。
このコマンドをRoutingTable(ノード「い」、NextNode、ノード「う」)としよう。

手順3:
ノード「う」はノード「え」に対して自分の存在を知らせたい。
ノード「え」に対してノード「う」は自分がノード「う」である事を表明し、また自分のIPアドレスを教える。
つまり、Join(ノード「う」⇒ノード「え」)

ノード「え」のルーティングテーブルは、隣り合うノードの部分についてはノード「い」とノード「お」であったが、
これが、ノード「う」とノード「お」に変更する必要がある。
このコマンドをRoutingTable(ノード「え」、FrontNode、ノード「う」)としよう。

手順4:
ノード「う」はまだルーティングテーブルを完全には構築していない。
すなわち、各行の先頭ノードを知っていない。(例えば、ノード「あ」、ノード「か」、ノード「さ」.......)そのため、
ノード「え」に対して、各先頭ノードのIPアドレスを教えて欲しいと要請する。
つまり、
RoutingTableKnown(ノード「う」、ノード「え」、各行の先頭ノード)
となる。

手順5:
各ノードは全てのルーティングテーブルに入っているノードに対して定期的にping等をしてノードが生きているかどうか調べる。

これでノード「う」がDHTに参加することができるようになった。

ところで、DHTではJoinやRoutingTable,RoutingTableKnownの方法については色々と工夫が施され、バラエティに富んでいる。
ただ、いずれにせよDHTのあるノードに対して自分の存在を知らせ、また自分に必要なルーティングテーブルを他の構成することはほぼ共通事項である。

実はこれだけではノード「う」はDHTに参加した事にならない。というのは、ノード「う」が居ない状態では、ノード「い」が頭文字が「う」で始まるデータを管理していたからである。
ということで、

手順6:ノード「い」からノード「う」が管理すべきデータを引き継ぐ

という処理を行う必要がある。
これでノードの参加処理は全て完了である。

次回はDHTからのノードの離脱とそれに対する工夫について説明したい。


|

« [P2P]分散ハッシュ(DHT)入門~その5 | トップページ | [ネットワーキング]分散ハッシュ(DHT)と6次の繋がり »

パソコン・インターネット」カテゴリの記事

コメント

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

トラックバック


この記事へのトラックバック一覧です: 分散ハッシュ(DHT)入門~その6:

« [P2P]分散ハッシュ(DHT)入門~その5 | トップページ | [ネットワーキング]分散ハッシュ(DHT)と6次の繋がり »