インターネットの場合にはIPアドレスというのがユーザのPCやサーバに 割り当てられる。ルーティングはこのIPアドレスを使って、例えばある人が 私のBlogをどうやって見ることができるか決める事ができる。 ルーティングなしには、インターネットのどんなページも見ることが できなくなってしまう。
ところで、DHTでのルーティングというのはどういうことだろうか？ 例えば「あいうえおDHT」で自分がノード「あ」だとする。今、「ヤクルト」と いう情報を欲しい場合にはノード「あ」はノード「や」にアクセスすることになる。 このノード「あ」がノード「や」にアクセスする方法がルーティングである。
ではどうやって「あいうえおDHT」はルーティングをすることができるだろうか？ 簡単な例を考えてみよう。
各ノードは隣り合った文字のノードの場所を知っているとする。例えばノード 「う」はノード「い」とノード「え」を知っているし、ノード「さ」はノード「こ」 とノード「し」を知っている事となる。 今、ノード「あ」がノード「「し」を知りたいとすると、バケツリレーのように ノード「あ」⇒ノード「い」⇒ノード「う」⇒ノード「え」⇒・・・・・⇒ ノード「こ」⇒ノード「さ」⇒ノード「し」と言う風になって、通信が できることになる。 でも、この方法はとても通信するのに遅いですよね？
今、各ノードが他のノードを知っている情報の表をルーティングテーブル と呼びましょう。 例えば、ノード「う」のルーティングテーブルにはノード「い」、ノード「え」の 各場所の情報（つまりIPアドレス）が入っています。ルーティング１はとても ルーティングするのには遅いのですが、ルーティングテーブルの要素を２つだけ 持っていればどんなノードとも通信ができます。
各ノードは自分以外のノードの情報を全て知っているとしましょう。 つまり、ノード「う」は、ノード「あ」、ノード「い」、ノード「え」、 ノード「お」・・・・・ノード「わ」、ノード「を」ということを知っている 事になります。つまりルーティングテーブルの中身は49個のノードの情報が 入っています。
もし、この方法であれば、ノード「あ」⇒ノード「し」の通信は、一発でできる ことがわかりますよね？なぜなら、ノード「あ」はノード「し」の情報を 既に知っているのだから。 でもこの方法は事前に49個ものノードの情報を知らないといけないので、 その情報を収集することが結構大変そうです。
では、ルーティングテーブルの中身は「それなりに」少なくて、かつルーティング 時間も「それなり」に少ない方法があれば便利だと思いませんか？ルーティング３は それを目指したルーティングテーブルの設計をしています。
各ノードは各行の先頭ノードを知っていて且つ隣あうノードも知っているとしま しょう。 これはどういうことでしょうか？
たとえば、ノード「う」がいるとしましょう。ノード「う」は各行の先頭ノードを 知っている必要が有りますから、ノード「あ」、ノード「か」、ノード「さ」、 ノード「た」・・・・・ノード「わ」を知っています。 それだけでなく、隣接しているノード、つまりノード「い」とノード「え」も 知っています。
今、ノード「あ」がノード「し」を知りたいとすると、ノード「あ」⇒ノード「さ」 ⇒ノード「し」とルーティングすることになりますね？ルーティングテーブルの 中身も10個程度になり、 先ほど実現した、ノードのルーティングテーブルはそれなりに少なく且つ ルーティング時間もそれなりに少ない事が実現されています。
つまり、DHTの特徴として
対象ノードについて、最初おおざっぱに検索して、その後詳しく
検索することによって、早くルーティングができる
ということなのです。
DHTの論文を読むと、ルーティングにユニークな方法が使われているので、びっくり
すると思います。興味があれば是非原論文を読んでみて下さいね。
[補足１]
ところで、今回の「あいうえお」DHTでは直接IPアドレスを使ってルーティングを
使っていません。ノード「あ」、ノード「い」などの、ノードの情報
（あ、い、う、え、お・・・・・という文字間の距離）を使ってルーティング
しました。
つまり、IPアドレスという情報を隠蔽してより抽象的な層でルーティングを
行っています。
このようにDHTはIPレイヤーよりも上の層でルーティングしているので、
「オーバーレイネットワーク」と呼ぶことがあります。
[補足２]
さてノード間の距離(d)とはなんでしょうか？「あいうえお」DHTでは、
ノード「あ」とノード「お」の距離は、どれだけ文字が離れているか、
つまりd=4となります。
例えばChordの場合にはハッシュ値Xとハッシュ値Yの絶対値の差、つまり
d=|X-Y|となります。これはユークリッド距離と言う物です。しかし、大学の
線形代数で習うように、距離は距離の公理に従えば、いろいろな定義ができます。
例えば、DHTのKademliaではd=X xor Y を使ってルーティングしています。
距離の公理は次のページを見ると良いでしょう。
ノルム空間
単純な例を説明するため「あいうえお」DHTでノード「う」だけが現在なく、 そこにノード「う」が参加することを考えてみよう。
まず、これからDHTに参加するノード「う」は、既にDHTに参加しているノードの 一つを少なくとも知っている必要がある。今そのノードをノード「や」としよう。
手順１：
ノード「う」は自分がノード「う」として振舞うためにはノード「い」と
ノード「え」に対して自分の存在を知らせる必要がある。そのため、
まずノード「う」はノード「や」を通して、ルーティング３を使って
ノード「い」とノード「え」のIPアドレスを知る。
手順２：
ノード「う」はノード「い」に対して自分の存在を知らせたい。
ノード「い」に対してノード「う」は自分のノードの存在を知らし、
また自分のIPアドレスを教える。このコマンドを例えば
Join（ノード「う」⇒ノード「い」）
と定義しよう。
ノード「い」のルーティングテーブルは、隣り合うノードの部分については ノード「あ」とノード「え」であったが、これが、ノード「あ」とノード「い」に 変更する必要がある。 このコマンドをRoutingTable（ノード「い」、NextNode、ノード「う」）としよう。
手順３：
ノード「う」はノード「え」に対して自分の存在を知らせたい。
ノード「え」に対してノード「う」は自分がノード「う」である事を表明し、また自分のIPアドレスを教える。
つまり、Join（ノード「う」⇒ノード「え」）
ノード「え」のルーティングテーブルは、隣り合うノードの部分については ノード「い」とノード「お」であったが、 これが、ノード「う」とノード「お」に変更する必要がある。 このコマンドをRoutingTable（ノード「え」、FrontNode、ノード「う」）としよう。
手順４：
ノード「う」はまだルーティングテーブルを完全には構築していない。
すなわち、各行の先頭ノードを知っていない。（例えば、ノード「あ」、
ノード「か」、ノード「さ」.......）そのため、
ノード「え」に対して、各先頭ノードのIPアドレスを教えて欲しいと要請する。
つまり、
RoutingTableKnown（ノード「う」、ノード「え」、各行の先頭ノード）
となる。
手順５：
各ノードは全てのルーティングテーブルに入っているノードに対して定期的にping等をしてノードが生きているかどうか調べる。
これでノード「う」がDHTに参加することができるようになった。
ところで、DHTではJoinやRoutingTable,RoutingTableKnownの方法については色々と 工夫が施され、バラエティに富んでいる。 ただ、いずれにせよDHTのあるノードに対して自分の存在を知らせ、また自分に 必要なルーティングテーブルを他の構成することはほぼ共通事項である。
実はこれだけではノード「う」はDHTに参加した事にならない。というのは、 ノード「う」が居ない状態では、ノード「い」が頭文字が「う」で始まるデータを 管理していたからである。 ということで、
手順６：ノード「い」からノード「う」が管理すべきデータを引き継ぐ
という処理を行う必要がある。 これでノードの参加処理は全て完了である。
「あいうえお」DHTで、ノード「う」がDHTに参加する場合、隣接しているノード、 すなわちノード「い」とノード「え」に自分の存在を知らせれば良かった。 そして、ノード「う」が管理すべき情報をノード「い」から引継ぎする事も 必要である。
そうなると離脱する場合には同じように隣接するノード、つまりノード「い」 とノード「え」にノード「う」が離脱するよ、と事前に連絡すれば良いことになる。
具体的には、
１.ノード「い」に対してノード「う」が離脱することを伝える。このときに、
ノード「い」の隣接ノードがノード「え」になることを確認する。
２.ノード「え」に対してノード「う」が離脱する事を伝える。このときに、
ノード「え」の隣接ノードがノード「い」になることを確認する。
これでルーティングテーブルについては受け渡しが完了した訳だが、 肝心のノード「う」が持っているデータを受け渡すことを忘れている。ということで、 ３.ノード「い」に対してノード「う」のデータを受け渡しする。 （なぜなら、ノード「い」は「い」「う」のデータを管理するようなルールに したから。）
と言う処理を忘れてはならない。
これでメデタシメデタシ。。と言いたい事だが、残念ながらそういうわけには いかない。というのは、今の離脱の処理はノードが前もって離脱する意志が あって、ノードの離脱前に離脱処理を出来た場合に相当する。実際には ネットワークやノードの関係で事前作業なしに急にノードが離脱する可能性 もある。（例えばPCの電源断、 ルータの故障など）そういう場合にはこのような処理をする事が出来ない。
ということは、ノードが急に離脱してもDHTがうまく働く処理をしないといけない。 これがDHTの実装での難関の一つである。ではどのようにすれば良いのだろうか？
例えば、今ノード「う」が急に抜けたとする。その時に隣接ノード、 ノード「い」ノード「え」は定期的に自分のルーティングテーブルのノードに pingなどの試験を行って相手のノードの確認をすれば、ノード「う」が 急に居なくなってもルーティングテーブルの更新については対応できそうだ。 つまり、先ほどの１、２の処理はなんとかなりそうな気がする。
とはいえ、３の処理であるノード「う」が持っているデータを他の ノードが引き継ぐのはとても大変そうである。 そこで一工夫する。
今、各ノードの保持しているデータは、隣接ノードにも絶えずコピー （正確には同期）することとしよう。 例えば、ノード「う」はノード「い」とノード「え」にも同じデータのコピーを 持っているとする。 すると、例えノード「う」が居なくなっても、そのノード「う」のデータは ノード「い」とノード「え」にあるので、データ自体は消去されないということ になる。後はルーティングテーブルが復旧すれば、ノード「う」にあったデータは ノード「い」でアクセスする事が出来るようになる。
実際のDHTではこのコピーを色々なノードにコピーする事によって、同時に複数の ノードがDHTから離脱しても問題なく作動するように設計されている。
これで分散ハッシュテーブルに関する説明は終わりです。他のページでＤＨＴの 実際の例 やＤＨＴの応用例について書いてありますので参考にして下さい。