FindNodeでネットワークの構築

• FindNodeクエリでネットワークを構築する

• リスポンスを受けたらRootingTableを更新する

前章で、kBucketとRootingTableについては説明しました。このRootinhTableを更新しながら、実際にDHTのネットワークを組んでみましょう。

FindNodeクエリでネットワークを構築する

Mainline DHT こと、KademliaではUDPを利用してPeerどうしが通信を行います。

DHRのネットワークを構築は、FindNodeクエリとFindNodeレスポンスのみで実現しています。

本章では、FindNodeクエリについて解説していきます。

指定したKIDに近い距離にあるPeerを紹介してもらう事ができる

FindNodeクエリを利用すると事で、指定したKIDともっとも距離が近いNodeを教えてもらう事ができます。

以下のようなBencodeで表現できます。

arguments:  
{
 "t":"aa",
 "y":"q",
 "q":"find_node", 
 "a":{
  "id" : "<nodes id>", 
  "target" : "<id of target node>"
 }
}

response: 
{
 "t":"aa",
 "y":"r",
 "r":{
  "id" : "<nodes id>",
  "nodes" : "<compact node info>"
 }
}

"t" は送信側が任意に決める事ができる値です。レスポンスには、送信時に指定した値が渡されます。この値を元にどのクエリのレスポンスかを判断する事がてきます。

"id"には、クエリを送信するPeerのKIDがして入ります。 "target"に指定したKIDと距離が近いPeerが帰りまする "nodes" は、26byteのbyteデータの集まりで、20byteのPeer IDとIPとPort番号が格納されています。

ネッワークへの参加/構築

ネットワークの構築はFindNodeクエリを利用します。我々は、自分に近いKIDを持つPeerについて詳しくなる必要があるのでした。

"id" に自分自信のPeer ID を指定して、 Node の一覧を取得します。 Rooting Table の中の上位 K個について、 FindNode を行います。この上位K個が固定されまで、 FindNod eを繰り返します。

なんども、この操作を繰り返しているうちに、DHT上でもっとも自分自信に近いPeerを発見できまます。

実際に1000個のPeerを生成して、試してみると以下の分布を得ることができました。 Kは8としました。

Rooting Table index	Peerの数	コメント
0	1	自分自信です
147	1	..
154	1	..
155	4	..
156	4	..
157	6	..
158	8	..
159	8	..
160	8	..

TorrentのDHTネットワークに接続した場合も同じような結果になります。自分自信に近いNodeは、Rooting Tabe index の、l130-150くらいのところに集まります。

実際にグラフに直してみると、150の付近で相当近くにあPeerである事がわかります。

ref http://www.bittorrent.org/beps/bep_0005.html

Kyorohiro work

http://kyorohiro.strikingly.com