« [音楽]指揮者なしの演奏会 | トップページ | 分散ハッシュ(DHT)入門~その6 »

2005.02.05

[P2P]分散ハッシュ(DHT)入門~その5

風邪で体調を崩してしまった。風邪がはやっているようなので、皆様も注意して下さいね。
さて、前回はなぜ、分散ハッシュテーブルという名称が使われているのか、その理由を述べた。
今回は「あいうえお」DHTを使ってルーティングの話をしたい。

そもそもルーティングとはなんだろうか?
例えば、ある人が東京から大阪に行きたいとする。今、自動車で大阪に行くとすると、首都高速に乗って高速道路に行く手もあれば、国道や一般道を使ってゆっくり安上がりに行く手もある。このように、あるところから目的にのところまでどうやって行くかを決める手段をルーティングと呼ぶ。

インターネットの場合にはIPアドレスというのがユーザのPCやサーバに割り当てられる。ルーティングはこのIPアドレスを使って、例えばある人が私のBlogをどうやって見ることができるか決める事ができる。ルーティングなしには、インターネットのどんなページも見ることができなくなってしまう。

ところで、DHTでのルーティングというのはどういうことだろうか?
例えば「あいうえおDHT」で自分がノード「あ」だとする。今、「ヤクルト」という情報を欲しい場合にはノード「あ」はノード「や」にアクセスすることになる。このノード「あ」がノード「や」にアクセスする方法がルーティングである。

ではどうやって「あいうえおDHT」はルーティングをすることができるだろうか?
簡単な例を考えてみよう。

◇ルーティング1

各ノードは隣り合った文字のノードの場所を知っているとする。例えばノード「う」はノード「い」とノード「え」を知っているし、ノード「さ」はノード「こ」とノード「し」を知っている事となる。
今、ノード「あ」がノード「「し」を知りたいとすると、 バケツリレーのようにノード「あ」⇒ノード「い」⇒ノード「う」⇒ノード「え」⇒..........⇒ノード「こ」⇒ノード「さ」⇒ノード「し」と言う風になって、通信ができることになる。
でも、この方法はとても通信するのに遅いですよね?

今、各ノードが他のノードを知っている情報の表をルーティングテーブルと呼びましょう。
例えば、ノード「う」のルーティングテーブルにはノード「い」、ノード「え」の各場所の情報(つまりIPアドレス)が入っています。この方法はとてもルーティングするのには遅いのですが、ルーティングテーブルを2つだけ持っていればどんなノードとも通信ができます。

◇ルーティング2
各ノードは自分以外のノードの情報を全て知っているとしましょう。
つまり、ノード「う」は、ノード「あ」、ノード「い」、ノード「え」、ノード「お」,,,,,,,,,,ノード「わ」、ノード「を」ということを知っている事になります。つまりルーティングテーブルの中身は49個のノードの情報が入っています。

もし、この方法であれば、ノード「あ」⇒ノード「し」の通信は、一発でできることがわかりますよね?なぜなら、ノード「あ」はノード「し」の情報を既に知っているのだから。
でもこの方法は事前に49個ものノードの情報を知らないといけないので、その収集することが結構大変そうです。

ルーティング1、ルーティング2とも長所と欠点があります。
つまり、ルーティングテーブルの中身が少ないと、ルーティングに時間がかかるし、ルーティングの中身が多いと、ルーティングの時間が少なくなると言う事です。

では、それなりにルーティングテーブルは少なくて、かつルーティング時間もそれなりに少ない方法があれば便利だと思いませんか?

◇ルーティング3
各ノードは各行の先頭ノードを知っている。また、各ノードは隣あうノードを知っている。
これはどういうことでしょうか?

たとえば、ノード「う」がいるとすれば、このノードは各行の先頭ノードを知っている必要が有りますから、ノード「あ」、ノード「か」、ノード「さ」、ノード「た」.....ノード「わ」を知っているわけです。
それだけでなく、隣接しているノード、ノード「い」とノード「え」も知っています。

今、ノード「あ」がノード「し」を知りたいとすると、ノード「あ」⇒ノード「さ」⇒ノード「し」となりますね?ルーティングテービルの中身も10個程度になり、先ほど実現した、ノードのルーティングテーブルはそれなりに少なく、ルーティングテーブルをそれなりに少ない事が実現されています。

===
ルーティング3の方法は良く考えると、とても面白い方法です。つまり、最初は「行」でざっくりとした場所を検索して、その後は近くなれば場所を詳しく検索すると言う方法です。DHTのChordやPastryなどはこのような方法を使って、ルーティング効率を高めてます。

つまり、DHTの特徴として
-最初は対象ノードについて、おおざっぱに検索して、その後だんだんきちんと検索することによって、早くルーティングができる

ということなのです。
DHTの論文を読むと、ルーティングにユニークな方法が使われているので、びっくりすると思います。興味があれば是非原論文を読んでみて下さいね。

[参考1]
ところで、今回の「あいうえお」DHTでは直接IPアドレスを使ってルーティングを使っていません。ノード「あ」、ノード「い」などの、ノードの情報(あ、い、う、え、お。。。という文字間の距離)を使ってルーティングしました。
つまり、IPアドレスという情報を隠蔽してより抽象的な層でルーティングを行っています。
このようにDHTはIPレイヤーよりも上の層でルーティングしているので、「オーバーレイネットワーク」と呼ぶことがあります。

[参考2]
さてノード間の距離(d)ってなんでしょうか?「あいうえお」DHTでは、ノード「あ」とノード「お」の距離は、どれだけ文字が離れているか、つまりd=4となります。
例えばChordの場合にはハッシュ値Xとハッシュ値Yの絶対値の差、つまりd=|X-Y|となります。これはユークリッド距離と言う物です。しかし、大学の線形代数に習ったように、距離は距離の公理に従えば、いろいろな定義ができます。例えば、DHTのKademliaではd=X xor Y を使ってルーティングしています。

そろそろDHT入門も終盤に差し掛かりました。次回はノードがDHTに参加した時どうするれば良いのか、考えてみます。

|

« [音楽]指揮者なしの演奏会 | トップページ | 分散ハッシュ(DHT)入門~その6 »

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

コメント

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

トラックバック


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

« [音楽]指揮者なしの演奏会 | トップページ | 分散ハッシュ(DHT)入門~その6 »