| BEP: | 5 |
|---|---|
| Title: | DHT Protocol |
| Version: | 11031 |
| Last-Modified: | 2008-02-28 16:43:58 -0800 (Thu, 28 Feb 2008) |
| Author: | Andrew Loewenstern <drue at bittorrent.com> |
| Status: | Draft |
| Type: | Standards Track |
| Created: | 31-Jan-2008 |
| Post-History: |
Contents
- Overview
- Routing Table
- BitTorrent Protocol Extension
- Torrent File Extensions
- KRPC Protocol
- Contact Encoding
- Queries
- Responses
- Errors
- DHT Queries
- ping
- find_node
- get_peers
- announce_peer
- References
- Copyright
混乱を避けるためにこのドキュメントで使用されている用語に注意して下さい。"ピア"とはBitTorrentプロトコルを実現するTCPポートをlistenしているクライアントもしくはサーバです。"ノード"とはdistributed hash tableを実現するUDPポートをlistenしているクライアントもしくはサーバです。DHTはノードから成り、ピアの一を保存します。BitTorrentクライアントはDHTノードを含んでおり、そのノードは、BitTorrentプロトコルを使ってダウンロードするピアの位置を得るために、DHT内のほかのノードにコンタクトするために使用されます。
Overview
各ノードは全体でユニークなIDを"ノードID"として持ちます。ノードIDはBitTorrent infohash [2]と同じ160-bit空間からランダムで生成されます。"距離メトリック"は、二つのノードIDか、ノードIDと"closeness"のためのinfohashを比較するために使用されます。ノードは少数の他のノードのコンタクト情報を含むルーティングテーブルを維持しなければなりません。ルーティングテーブルは、ID群がノード自身のIDに近くなるにつれて、より詳細になります。ノードは自身に"近い"IDを持っているDHT内の多くのノードについて知っていますが、自身からとても離れているIDに対しては僅かなコンタクト情報しか持っていません。Kademuriaの距離メトリックはXORです。そして、その結果は符号なし整数として解釈されます。distance(A,B) = |A xor B|です。小さい値がより近いことを意味します。
ノードがあるtorrentへのピアを見つけたいとき、そのノードは、そのtorrentのinfohashと自身のルーティングテーブルないのノードのID群を比較するために、その距離メトリックを使用します。そしてそのノードはinfohashにもっとも近いIDを持つと知っているノードへコンタクトし、そのtorrentを現在ダウンロードしているピアのコンタクト情報を求めます。もしコンタクトされたノードがtorrentのピアを知っているならば、ピアのコンタクト情報がレスポンスで返されます。そうでなければ、コンタクトされたノードはtorrentのinfohashにもっとも近い自身のルーティングテーブル内のノードのコンタクト情報を返します。元のノードは、より近いノードが発見できなくなるまで、目的のinfohashに最も近いノードを繰り返し問い合わせます。検索の後、そのクライアントはそれ自身のピアコンタクト情報をtorrentのinfohashにもっとも近いIDを返したノードに挿入します。
ピアの問い合わせで返された値は"トークン"として知られる曖昧な値を含みます。制御しているピアがtorrentをダウンロードしていることをアナウンスするノードは、ピアへの新しい問い合わせにおいて、以前問い合わせたのと同じノードから受信したトークンを提示しなければなりません。ノードがtorrentを"アナウンス"しようとするとき、問い合わせ先のノードはとあわせをしているノードのIPアドレスに対してトークンをチェックします。トークンはトークンの発信元と同じノードに対して問い合わせノードによって返されるだけなので、その実現は定義されません。トークンは、それが配布された後、ある程度の間受け付けられなければなりません。BitTorrentの実装は、5分毎に変化する秘密情報に連結されるIPアドレスのSHA1ハッシュを使用し、10分までの古いトークンが受理されます。
Routing Table
各ノードは良いと知られるノードのルーティングテーブルを維持します。ルーティングテーブル内のノードはDHTの問い合わせのための起点ノードとして使用されます。ルーティングテーブルからのノードは他のノードからの問い合わせへの返信で返されます。私たちが知りうるすべてのノード等しいわけではありません。いくつかのノードは"良い"ですが、いくつかはそうではありません。DHTを使っている多くのノードは問い合わせを送信し返信を受理することができますが、他のノードからの問い合わせに反応できません。各ノードのルーティングテーブルが良いと知られているノードのみを含まなければならないことが重要です。良いノードは最近の15分以内に私たちの問い合わせの一つに反応しているノードです。また、もしノードが私たちの問い合わせにかつて反応したことがあり、最近の15分以内に私たちに問い合わせをしているならば、そのノードも良いと言えます。15分の活動停止ののち、ノードは疑わしくなります。ノードは、続けて複数の問い合わせに反応することに失敗した場合、悪いノードとなります。私たちが良いノードだと知っているノードは状態が確認できていないノードよりも高い優先を与えられます。
ルーティングテーブルは0から2160に広がる全体のノードID空間をカバーします。ルーティングテーブルは、空間の一部をそれぞれカバーする"バケツ"に再分割されます。空のテーブルは最小0最大2160のID空間を持つ一つのバケツを持っています。IDがNであるノードがルーティングテーブルに挿入されるとき、最小値 <= N < 最大値を持つバケツの中に置かれます。空のテーブルはバケツを一つだけ持っているので、すべてのノードはそのバケツに当てはまります。各バケツは、それがいっぱいになるまで、K個(現在K=8)のノードだけを保持することができます。バケツが良いと知られているノードでいっぱいになるとき、私たち自身のノードIDがバケツの範囲に入っていないならば、これ以上のノードは追加されないかもしれません。この場合、バケツは古いバケツの半分ずつの範囲を持つ二つの新しいバケツによって取って替わられ、古いバケツのノードは二つの新しいバケツに分散させられます。バケツを一つだけ持つ新しいテーブルでは、満杯のバケツは常に、0...2159と2159...2160の範囲をカバーする二つの新しいバケツに分割されます。
もしバケツが良いノードでいっぱいであるならば、新しいノードは単に捨てられます。バケツの中のノードが既に悪いノードになっていると知られているならば、それは新しいノードと取り替えられます。もし最近の15分以内に現れていないバケツの中の疑わしいノードがあるならば、もっとも現れないノードに対してping(生存確認)を行います。生存確認が行われているノードが反応するならば、次に現れない疑わしいノードに対して生存確認を行います。それは、ある一つが反応しないときまでか、バケツのすべてのノードが良いノードであるとわかるまで行われます。もしバケツの中のあるノードが生存確認への反応に失敗する場合、そのノードをしてて新しい良いノードと取り替える前に、一回以上再び生存確認をすることが薦められます。このように、テーブルは安定して長く生きているノードで埋められます。
各バケツはその中身がどのくらい新鮮かを示す"最終更新"属性を維持しています。バケツのノードに生存確認をしてそれが反応したとき、あるいはノードがバケツに加えられたとき、あるいはバケツのノードが他のノードに取り替えられたとき、バケツの最終更新属性は更新されるべきです。15分間変更されていないバケツは"更新"されるべきです。これは、バケツの範囲内でランダムなIDを抽出し、それに対してfind_nodeを実行することで行われます。他のノードからの問い合わせを受理することができないノードは通常、DHTが必要とされるときにそれらのテーブルに良いノードがあることを保証するために、定期的にすべてのバケツを更新する必要があるでしょう
初めのノードをルーティングテーブルに挿入する際、そしてそれから先を開始するとき、ノードはDHT内でそれ自身にもっとも近いノードを探すことを試みるべきです。ノードは、それ以上近いノードが発見できなくなるまで、より近いノードからノードへとfind_nodeメッセージを発行することで、このことを行います。ルーティングテーブルはクライアントソフトウェアの実行の合間に保存されるべきです。
BitTorrent Protocol Extension
BitTorrentプロトコルはとラッカーによって紹介されたピア間でUDPポート番号を交換するように拡張されました。このように、クライアントはいつものtorrentのダウンロードを通じて自動的にルーティングテーブルに種を蒔くことができます。新しくインストールされたクライアントで、全くの初期段階段階でトラッカーレスtorrentをダウンロードしようとするクライアントは、ルーティングテーブルにノードを一つも持っておらず、torrentファイルに含まれるコンタクトを必要とするでしょう。DHTをサポートするピアはBitTorrentプロトコルのハンドシェイクにて交換される8バイトの予約フラグの最後のビットをセットします。リモートピアがDHTをサポートすることを示すハンドシェイクを受信したピアはPORTメッセージを送ります。そのメッセージはバイトデータ0x09で始まり、DHTノードのUDPポートを含むネットワークバイトオーダの二バイトのペイロードを持ちます。このメッセージを受信するピアは受信したポート番号とリモートピアのIPアドレスのノードに対して生存確認を試みるべきです。もしその生存確認への反応が受信された場合、そのノードは通常の規則にしたがって、ルーティングテーブルに新しいコンタクト情報を挿入することを試みるべきです。
Torrent File Extensions
トラッカーレスtorrentディクショナリは"announce"キーを持っていません。代わりに、トラッカーレスtorrentは"nodes"キーを持ちます。このキーはtorrentを生成するクライアントのルーティングテーブルにおけるK個のもっとも近いノードにセットされるべきです。あるいは、そのキーはtorrentを生成する人によって操作されるノードのような良いノードにセットされうるべきです。torrentファイルに"router.bittorrent.com"を自動的に加えたり、クライアントのルーティングテーブルにこのノードを自動的に加えたりしないで下さい。| nodes = [["<host>", <port>], ["<host>", <port>], ...] |
| nodes = [["127.0.0.1", 6881], ["your.router.node", 4804]] |
KRPC Protocol
KRPCプロトコルはUDP経由で送信されるbencodeされたディクショナリからなる簡潔なRPCメカニズムです。一つの問い合わせパケットが送信され、一つのパケットが返信として送られます。再送はありません。query、response、そしてerrorの3つのメッセージがあります。DHTプロトコルでは、ping、find_node、get_peersそしてannounce_peerの4つの問い合わせがあります。KRPCメッセージは、すべてのメッセージに共通な二つのキーとメッセージの種類に依存する追加のキー群を伴う一つのディクショナリです。すべてのメッセージは、トランザクションIDをあらわす文字列を値として伴うキー"t"を持ちます。このトランザクションIDは問い合わせノードによって生成され、返信でそのまま返されるため、複数の返信が同じノードへの複数の問い合わせと相互関係を築くかもしれません。トランザクションIDはバイナリ数値の短い文字列としてエンコードされるべきで、通常、216の発行可能な問い合わせをカバーできる二文字で十分です。全てのKRPCメッセージに含まれる他のキーはメッセージのタイプを示す一文字の値を伴う"y"です。キー"y"の値は、queryメッセージに対しては"q"であり、responseメッセージに対しては"r"であり、errorメッセージに対しては"e"となります。
Contact Encoding
ピアへのコンタクト情報は6バイト長の文字列としてエンコードされます。"Compact IP-address/port infoquot;としても知られ、ネットワークバイトオーダの4バイトのIPアドレスがその後ろにネットワークバイトオーダの2バイトのポート番号を伴っています。ノードへのコンタクト情報は26バイト長の文字列としてエンコードされます。"Compact node info"としても知られ、ネットワークバイトオーダの20バイトのノードIDがその後ろに連結されるcompact IP-address/port infoを持っています。
Queries
問い合わせ、あるいは、"y"の値"q"を伴うKRPCメッセージディクショナリは二つの追加のキー"q"と"a"を含みます。キー"q"はその問い合わせのメソッド名を含む文字列値を持っています。キー"a"はその問い合わせに指定された引数を含むディクショナリを値として持ちます。Responses
返信、あるいは、"y"の値"r"を伴うKRPCメッセージディクショナリは一つの追加のキー"r"を含みます。"r"の値は指定された返り値を含むディクショナリです。responseメッセージは問い合わせの正常終了時に送られます。Errors
エラー、あるいは、"y"の値"e"を伴うKRPCメッセージディクショナリは人っツの追加のキー"e"を含みます。"e"の値はリストです。最初の要素は、エラーコードをあらわす整数値です。二つ目の要素は、エラーメッセージを含む文字列です。エラーコードは問い合わせが完了しなかったときに送られます。下記のテーブルは起こりうるエラーコードです:| Code | Description |
| 201 | Generic Error |
| 202 | Server Error |
| 203 | Protocol Error, such as a malformed packet, invalid arguments, or bad token |
| 204 | Method Unknown |
| generic error = {"t":"aa", "y":"e", "e":[201, "A Generic Error Ocurred"]} |
| bencoded = d1:eli201e23:A Generic Error Ocurrede1:t2:aa1:y1:ee |
DHT Queries
全ての問い合わせはキー"id"と問い合わせノードのノードIDを含む値を持っています。全ての返信はキー"id"と返信ノードのノードIDを含む値を持っています。ping
もっとも基本的な問い合わせはpingです。"q"="ping"です。問い合わせpingは一つの引数"id"を採ります。その値は送信ノードのIDをネットワークバイトオーダで含む20バイトの文字列です。pingへの適切な返信は、一つのキー"id"と返信ノードのノードIDを含む値です。| arguments: {"id" : "<querying nodes id>"} |
| response: {"id" : "<queried nodes id>"} |
パケットの例
| ping Query = {"t":"aa", "y":"q", "q":"ping", "a":{"id":"abcdefghij0123456789"}} |
| bencoded = d1:ad2:id20:abcdefghij0123456789e1:q4:ping1:t2:aa1:y1:qe |
| Response = {"t":"aa", "y":"r", "r": {"id":"mnopqrstuvwxyz123456"}} |
| bencoded = d1:rd2:id20:mnopqrstuvwxyz123456e1:t2:aa1:y1:re |
find_node
find_nodeはIDが与えられたあるノードのコンタクト情報を見つけるために使用されます。"q"="find_node"です。問い合わせfind_nodeは二つの引数を採ります。"id"は問い合わせノードのノードIDを含み、"target"は問い合わせ元が探しているノードのIDを含みます。問い合わせfind_nodeを受信したとき、ノードは、キー"nodes"と、目的のノードか自身のルーティングテーブル内にあるK(8)個の近い良いノードかのcompact node infoを含む文字列値を返すべきです。| arguments: {"id" : "<querying nodes id>", "target" : "<id of target node>"} |
| response: {"id" : "<queried nodes id>", "nodes" : "<compact node info>"} |
パケットの例
| find_node Query = {"t":"aa", "y":"q", "q":"find_node", "a": {"id":"abcdefghij0123456789", "target":"mnopqrstuvwxyz123456"}} |
| bencoded = d1:ad2:id20:abcdefghij01234567896:target20:mnopqrstuvwxyz123456e1:q9:find_node1:t2:aa1:y1:qe |
| Response = {"t":"aa", "y":"r", "r": {"id":"0123456789abcdefghij", "nodes": "def456..."}} |
| bencoded = d1:rd2:id20:0123456789abcdefghij5:nodes9:def456...e1:t2:aa1:y1:re |
get_peers
get_peersはtorrentのinfohashに関連付けられます。"q"="get_peers"です。問い合わせget_peersは二つの引数を採ります。"id"は問い合わせノードのノードIDを含み、"info_hash"はtorrentのinfohashを含みます。もし問い合わせを受けたノードがinfohashのピアを持っているならば、キー"value"の文字列のリスト値としてそのピアが返されます。もし問い合わせを受けたノードがinfohashのピアを持っていないならば、キー"nodes"が、問い合わせで指定されたinfohashに対して、問い合わせされたノードが持つルーティングテーブルでもっとも近いK個のノードを含んで返されます。どちらの場合も、キー"token"が返り値に含まれます。値"token"は将来の問い合わせannounce_peerで必要な引数となります。値"token"は短いバイナリ文字列であるべきです。| arguments: {"id" : "<querying nodes id>", "info_hash" : "<20-byte infohash of target torrent>"} |
| response: {"id" : "<queried nodes id>", "token" :"<opaque write token>", "values" : ["<peer 1 info string>", "<peer 2 info string>"]} or : {"id" : "<queried nodes id>", "token" :"<opaque write token>", "nodes" : "<compact node info>"} |
パケットの例
| get_peers Query = {"t":"aa", "y":"q", "q":"get_peers", "a": {"id":"abcdefghij0123456789", "info_hash":"mnopqrstuvwxyz123456"}} |
| bencoded = d1:ad2:id20:abcdefghij01234567899:info_hash20:mnopqrstuvwxyz123456e1:q9:get_peers1:t2:aa1:y1:qe |
| Response with peers = {"t":"aa", "y":"r", "r": {"id":"abcdefghij0123456789", "token":"aoeusnth", "values": ["axje.u", "idhtnm"]}} |
| bencoded = d1:rd2:id20:abcdefghij01234567895:token8:aoeusnth6:valuesl6:axje.u6:idhtnmee1:t2:aa1:y1:re |
| Response with closest nodes = {"t":"aa", "y":"r", "r": {"id":"abcdefghij0123456789", "token":"aoeusnth", "nodes": "def456..."}} |
| bencoded = d1:rd2:id20:abcdefghij01234567895:nodes9:def456...5:token8:aoeusnthe1:t2:aa1:y1:re |
announce_peer
問い合わせノードを制御しているピアがtorrentをあるポートでダウンロードしていることをアナウンスします。announce_peerは４つの引数を採ります。"id"は問い合わせノードのノードIDを含み、"info_hash"はtorrentのinfo_hashを含み、portはポート番号の整数値を含み、"token"は事前に行われている問い合わせget_peersに対する返信で受信した値です。問い合わせを受けたノードは、"token"の値が問い合わせをしたノードと同じIPアドレスに事前に送られたものであることを検証しなければなりません。その後、問い合わせを受けたノードはピアコンタクト情報を保持している場所でそのinfo_hashの元に問い合わせノードのIPアドレスと提供されたポート番号を保存するべきです。| arguments: {"id" : "<querying nodes id>", "info_hash" : "<20-byte infohash of target torrent>", "port" : <port number>, "token" : "<opaque token>"} |
| response: {"id" : "<queried nodes id>"} |
パケットの例
| announce_peers Query = {"t":"aa", "y":"q", "q":"announce_peer", "a": {"id":"abcdefghij0123456789", "info_hash":"mnopqrstuvwxyz123456", "port": 6881, "token": "aoeusnth"}} |
| bencoded = d1:ad2:id20:abcdefghij01234567899:info_hash20:mnopqrstuvwxyz1234564:porti6881e5:token8:aoeusnthe1:q13:announce_peer1:t2:aa1:y1:qe |
References
| [1] | Peter Maymounkov, David Mazieres, "Kademlia: A Peer-to-peer Information System Based on the XOR Metric", IPTPS 2002. http://www.cs.rice.edu/Conferences/IPTPS02/109.pdf |
| [2] | Use SHA1 and plenty of entropy to ensure a unique ID. |
0 件のコメント:
コメントを投稿