Ignore:
Timestamp:
08/22/07 14:45:31 (3 years ago)
Author:
dave
Message:

Fix. DHT Protocol is now really DHT protocol.

List David and Arvid as co-editors.

Point users to communicate with .org via editor@….

Add web page with BRIEF submission instructions for porposing
protocol extensions.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • dotorg/trunk/html/Draft_DHT_protocol.html

    r4635 r7266  
    1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" 
    2         "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> 
     1<?xml version="1.0" encoding="utf-8"?> 
     2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"  
     3        "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> 
    34<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 
    45<head> 
    56<meta http-equiv="Content-type" content="text/html; charset=utf-8" /> 
    6 <title>BitTorrent.org For Developers</title> 
     7<title>BitTorrent.org » For Developers » DHT Protocol</title> 
    78<link rel="stylesheet" type="text/css" href="./css/screen.css" media="screen" /> 
    89</head> 
    … …  
    1112<div id="wrap"> 
    1213<div id="header"> 
    13 <h1><a href="./index.html">BitTorrent<span>.org</span></a></h1> 
     14<h1><a href="./index.html">BitTorrent<span>.org</a></h1> 
    1415</div> 
    1516<div id="nav"> 
    … …  
    1819<li><a href="./introduction.html">For Users</a></li> 
    1920<li><span>For Developers</span></li> 
    20 <!-- <li><a href="./blog">Blog</a></li> --> 
    21 <li><a href="./donate.html">Donate!</a></li> 
     21<!-- <li><a href="./blog.html">Blog</a></li> --> 
     22<!-- <li><a href="./donate.html">Donate!</a></li> --> 
    2223</ul> 
    2324</div> 
    2425<!-- ### Begin Content ### --> 
    2526<div id="second"> 
    26 <h1>Fast Extension</h1> 
    27 <p>The Fast Extension packages several extensions: <i>Have None/Have All</i>, 
    28 <i>Reject Requests</i>, <i>Suggestions</i> and <i>Allowed Fast.</i> 
    29 These are enabled by setting the third least significant bit of the 
    30 last reserved byte in the BitTorrent handshake: 
    31 </p> 
    32 <pre> reserved[7] |= 0x04 
    33 </pre> 
    34 <p>The extension is enabled only if both ends of the connection set this bit. 
    35 </p><p>The following proposed messages adhere to the syntax of messages found 
    36 in v1.0 of the BitTorrent protocol.  All integers are four bytes 
    37 big-endian.  All messages start with an integer message length.  All messages 
    38 but the Keep-Alive follow the message length with a single byte opcode 
    39 and zero or more opcode-dependant arguments. 
    40 </p><p>The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL 
    41 NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED",  "MAY", and 
    42 "OPTIONAL" in this document are to be interpreted as described in 
    43 IETF <a href='http://www.ietf.org/rfc/rfc2119.txt' class='external' title="http://www.ietf.org/rfc/rfc2119.txt">RFC 2119</a>. 
    44 </p> 
    45 <table id='toc' class='toc'><tr><td><div id='toctitle'><h2>Contents</h2></div> 
    46 <ul> 
    47 <li class='toclevel-1'><a href="#Modifications_to_Semantics_of_Existing_Messages"><span class="tocnumber">1</span> <span class="toctext">Modifications to Semantics of Existing Messages</span></a></li> 
    48 <li class='toclevel-1'><a href="#Have_All.2FHave_None"><span class="tocnumber">2</span> <span class="toctext">Have All/Have None</span></a></li> 
    49 <li class='toclevel-1'><a href="#Suggest_Piece"><span class="tocnumber">3</span> <span class="toctext">Suggest Piece</span></a></li> 
    50 <li class='toclevel-1'><a href="#Reject_Request"><span class="tocnumber">4</span> <span class="toctext">Reject Request</span></a></li> 
    51 <li class='toclevel-1'><a href="#Allowed_Fast_Set_Generation"><span class="tocnumber">5</span> <span class="toctext">Allowed Fast Set Generation</span></a></li> 
    52 </ul> 
    53 </td></tr></table> 
    54 <p><script type="text/javascript"> if (window.showTocToggle) { var tocShowText = "show"; var tocHideText = "hide"; showTocToggle(); } </script> 
    55 </p> 
    56 <h2 id="Modifications_to_Semantics_of_Existing_Messages"> Modifications to Semantics of Existing Messages </h2> 
    57 <p>The Fast Extension modifies the semantics of the 
    58 <i>Request</i>, <i>Choke</i>, <i>Unchoke</i>, and <i>Cancel</i> 
    59 messages, and adds a <i>Reject Request.</i>  Now, every request 
    60 is guaranteed to result in EXACTLY ONE response 
    61 which is either the corresponding reject or corresponding piece 
    62 message.  Even when a request is cancelled, the peer receiving 
    63 the cancel should respond with either the corresponding reject or 
    64 the corresponding piece: requests that are being processed are 
    65 allowed to complete. 
    66 </p><p>Choke no longer implicitly rejects all pending requests, 
    67 thus eliminating some race conditions which could cause pieces 
    68 to be needlessly requested multiple times. 
    69 </p><p>Additionally, if a peer receives a piece that was never requested, 
    70 the peer MUST close the connection. 
    71 </p> 
    72 <h2 id="Have_All.2FHave_None"> Have All/Have None </h2> 
    73 <pre> <i>Have All</i>: &lt;len=0x0001&gt;&lt;op=0x0E&gt; 
    74 </pre> 
    75 <pre> <i>Have None</i>: &lt;len=0x0001&gt;&lt;op=0x0F&gt; 
    76 </pre> 
    77 <p><i>Have All</i> and <i>Have None</i> specify that the message sender 
    78 has all or none of the pieces respectively.  When present, <i>Have All</i> 
    79 or <i>Have None</i> replace the <i>Have Bitfield.</i>  Exactly one of <i>Have All</i>, 
    80 <i>Have None</i>, or <i>Have Bitfield</i> MUST appear and only immediately after 
    81 the handshake.  The reason for these messages is to save bandwidth.  Also 
    82 slightly to remove the idiosyncrasy of sending no message when a peer 
    83 has no pieces. 
    84 </p><p>When the fast extension is disabled, if a peer receives <i>Have All</i> or 
    85 <i>Have None</i> then the peer MUST close the connection. 
    86 </p> 
    87 <h2 id="Suggest_Piece"> Suggest Piece </h2> 
    88 <pre> <i>Suggest Piece</i>: &lt;len=0x0005&gt;&lt;op=0x0D&gt;&lt;index&gt; 
    89 </pre> 
    90 <p><i>Suggest Piece</i> is an advisory message meaning "you might like to 
    91 download this piece."  The intended usage is for 'super-seeding' 
    92 without throughput reduction, to avoid redundant downloads, and so that 
    93 a seed which is disk I/O bound can upload continguous or identical 
    94 pieces to avoid excessive disk seeks.  In all cases, the seed SHOULD 
    95 operate to maintain a roughly equal number of copies of each piece in 
    96 the network.  A peer MAY send more than one <i>suggest piece</i> message at 
    97 any given time.  A peer receiving multiple <i>suggest piece</i> messages 
    98 MAY interpret this as meaning that all of the suggested pieces 
    99 are equally appropriate. 
    100 </p><p>When the fast extension is disabled, if a peer receives a 
    101 <i>Suggest Piece</i> message, the peer MUST close the connection. 
    102 </p> 
    103  
    104 <h2 id="Reject_Request"> Reject Request </h2> 
    105 <pre> <i>Reject Request</i>: &lt;len=0x000D&gt;&lt;op=0x10&gt;&lt;index&gt;&lt;begin&gt;&lt;offset&gt; 
    106 </pre> 
    107 <p><i>Reject Request</i> notifies a requesting peer that its request will not be satisfied. 
    108 </p><p>If the fast extension is disabled and a peer receives a reject 
    109 request then the peer MUST close the connection. 
    110 </p><p>When the fast extension is enabled: 
    111 </p> 
    112 <ul><li> If a peer receives a reject for a request that was never sent then the peer SHOULD close the connection. 
    113 </li><li> If a peer sends a choke, it MUST reject all requests from the peer to whom the choke was sent except it SHOULD NOT reject requests for pieces that are in the <i>allowed fast set.</i>  A peer SHOULD choke first and then reject requests so that the peer receiving the choke does not re-request the pieces. 
    114 </li><li> If a peer receives a request from a peer its choking, the peer receiving the request SHOULD send a reject unless the piece is in the <i>allowed fast set.</i> 
    115 </li> 
    116 <li>If a peer receives an excessive number of requests from a peer it is choking, the peer receiving the requests MAY close the connection rather than reject the request.  However, consider that it can take several seconds for buffers to drain and messages to propagate once a peer is choked.</li></ul> 
    117  
    118 <h2 id="Allowed_Fast">Allowed Fast</h2> 
    119 <pre><i> Allowed Fast: &lt;len=0x0005&gt;&lt;op=0x11&gt;&lt;index&gt;</i></pre> 
    120 <p>With the BitTorrent protocol specified in <a href="protocol.html">[1]</a>, new peers take several minutes to ramp up before they can effectively engage in BitTorrent's tit-for-tat. The reason is simple: starting peers have few pieces to trade.</p> 
    121 <p><i>Allowed Fast</i> is an advisory message which means "if you ask for this piece, I'll give it to you even if you're choked." <i>Allowed Fast</i> thus shortens the awkward stage during which the peer obtains occasional optimistic unchokes but cannot sufficiently reciprocate to remain unchoked.</p> 
    122 <p>The pieces that can be downloaded when choked constitute a peer's <i>allowed fast set.</i> The set is generated using a canonical algorithm that produces piece indices unique to the message receiver so that if two peers offer <i>k</i> pieces fast it will be the same <i>k</i>, and if one offers <i>k+1</i> it will be the same <i>k</i> plus one more. <i>k</i> should be small enough to avoid abuse, but large enough to ramp up tit-for-tat. We currently set <i>k</i> to 10, but peers are free to change this number, e.g., to suit load.</p> 
    123 <p>The message sender MAY list pieces that the message sender does not have. The receiver MUST NOT interpret an Allowed Fast message as meaning that the message sender has the piece. This allows peers to generate and communicate allowed fast sets at the beginning of a connection. However, a peer MAY send Allowed Fast messages at any time.</p> 
    124 <p>A peer SHOULD send Allowed Fast messages to any starting peer unless the local peer lacks sufficient resources. A peer MAY reject requests for already Allowed Fast pieces if the local peer lacks sufficient resources, if the requested piece has already been sent to the requesting peer, or if the requesting peer is not a starting peer. Our current implementation rejects requests for Allowed Fast messages whenever the requesting peer has more than <i> k </i> pieces.</p> 
    125 <p> When the fast extension is disabled, if a peer recieves an Allowed Fast message then the peer MUST close the connection.</p> 
    126  
    127 <h2 id="Allowed_Fast_Set_Generation"> Allowed Fast Set Generation </h2> 
    128 <p>The canonical algorithm for computing a peer <i>P'</i>s <i>allowed fast set</i> 
    129 follows.  All integers in this pseudocode are four bytes represented in network (big-endian) byte order.  <i>[a:b]</i> denotes the sequence of consecutive integers from <i>a</i> to <i>b</i> excluding <i>b</i>, i.e., <i>(a, a+1, a+2,..., b-1)</i>. <i>x[a:b]</i> denotes a subsequence of elements in an array <i>x</i> starting from index <i>a</i> to but not including index <i>b</i>. 
    130 </p><p>Let <i>ip</i> denote <i>P'</i>s IPv4 address.  We currently have no 
    131 provisions for IPv6. If a peer is behind a Network Address Translator 
    132 (NAT) then <i>ip</i> should be the externally facing IP address of the 
    133 NAT.  Since the node sending the <i>Allowed Fast</i> messages computes 
    134 the set, the correct <i>ip</i> is usually the <i>ip</i> address on the other 
    135 end of the connection.  The host computing the set MAY use the <i>ip</i> 
    136 address on the other end of the connection regardless 
    137 </p><p>Let <i>sz</i> denote the number of pieces in the torrent. 
    138 </p><p>Let <i>a</i> denote the allowed fast set. 
    139 </p><p>Let <i>k</i> denote the final number of pieces in the allowed fast set. 
    140 </p> 
    141 <pre> x = 0xFFFFFF00 &amp; ip                           (1) 
    142  x.append(infohash)                            (2) 
    143  while |a| &lt; k: 
    144    x = SHA1(x)                                 (3) 
    145    for i in [0:5] and |a| &lt; k:                 (4) 
    146      j = i*4                                   (5) 
    147      y = x[j:j+4]                              (6) 
    148      index = y % sz                            (7) 
    149      if index not in a:                        (8) 
    150        add index to a                          (9) 
    151 </pre> 
    152 <p>Step (1) selects the most significant octets in peer <i>P'</i>s 
    153 ip address.  We do this to prevent a user that obtains more than one 
    154 IP address on the same network from obtaining more than one 
    155 <i>allowed fast set.</i>  Use of three bytes is heuristic and 
    156 historical. 
    157 </p><p>Step (3) generates a 20-byte random number on each call.  By 
    158 performing a SHA-1 hash on the previous iteration's hash, we can 
    159 generate an arbitrarily long pseudorandom sequence. 
    160 </p><p>Steps (4) through (9) partition the 20-byte hash into piece indices 
    161 and add them to the allowed fast set. 
    162 </p> 
    163 </div><a name="Example_Implementation"></a><h2> Example Implementation </h2> 
    164 <p>The following C++ implementation was provided by CacheLogic: 
    165 </p> 
    166 <pre>void generate_fast_set( 
    167   uint32 k,     // number of pieces in set 
    168   uint32 sz,    // number of pieces in torrent 
    169   const char infohash[20], // infohash of torrent 
    170   uint32 ip, // in host byte order, ie localhost is 0x7f000001 
    171   std::vector&lt;uint32&gt; &amp;a) // generated set of piece indices 
    172 { 
    173    a.clear(); 
    174    std::string x; 
    175    char buf[4]; 
    176    *(uint32*)buf = htonl(ip &amp; 0xffffff00); 
    177    x.assign(buf, 4); 
    178    x.append(infohash, 20); // (3) 
    179    while (a.size()&lt;k) { 
    180      x = SHA1(x); // (4) 
    181      for ( int i=0&nbsp;; i&lt;5 &amp;&amp; a.size()&lt;k&nbsp;; i++ ) { // (5) 
    182        int j = i*4; // (6) 
    183        uint32 y = ntohl(*(uint32*)(x.data()+j)); // (7) 
    184        uint32 index = y % sz; // (8) 
    185        if (std::find(a.begin(), a.end(), index)==a.end()) { // (9) 
    186          a.push_back(index); // (10) 
    187        } 
    188      } 
    189    } 
    190 } 
    191 </pre> 
    192 <p>Example results generated by this function: 
    193 </p> 
    194 <pre>7 piece allowed fast set for torrent with 1313 pieces and hex infohash 
    195 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for node with IP 80.4.4.200: 
    196   1059,431,808,1217,287,376,1188 
    197 9 piece allowed fast set for torrent with 1313 pieces and hex infohash 
    198 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for node with IP 80.4.4.200: 
    199   1059,431,808,1217,287,376,1188,353,508 
    200 </pre> 
     27<h2>DHT Protocol</h2> 
     28<p>BitTorrent uses a "distributed sloppy hash table" (DHT) for storing peer contact information for "trackerless" torrents. In effect, each peer becomes a tracker. The protocol is based on Kademila and is implemented over UDP.</p> 
     29<p>Please note the terminology used in this document to avoid confusion. A "peer" is a client/server listening on a TCP port that implements the BitTorrent protocol. A "node" is a client/server listening on a UDP port implementing the distributed hash table protocol. The DHT is composed of nodes and stores the location of peers. BitTorrent clients include a DHT node, which is used to contact other nodes in the DHT to get the location of peers to download from using the BitTorrent protocol.</p> 
     30<h3>Contents</h3> 
     31<ul> 
     32<li><a href="#Overview">1 Overview</a></li> 
     33<li><a href="#Routing_Table">2 Routing Table</a></li> 
     34<li><a href="#BitTorrent_Protocol_Extension">3 BitTorrent Protocol Extension</a></li> 
     35<li><a href="#Torrent_File_Extensions">4 Torrent File Extensions</a></li> 
     36<li><a href="#KRPC_Protocol">5 KRPC Protocol</a> 
     37<ul> 
     38<li><a href="#Contact_Encoding">5.1 Contact Encoding</a></li> 
     39<li><a href="#Queries">5.2 Queries</a></li> 
     40<li><a href="#Responses">5.3 Responses</a></li> 
     41<li><a href="#Errors">5.4 Errors</a> 
     42<ul> 
     43<li><a href="#Example_Error_Packets">5.4.1 Example Error Packets</a></li> 
     44</ul> 
     45</li> 
     46</ul> 
     47</li> 
     48<li><a href="#DHT_Queries">6 DHT Queries</a> 
     49<ul> 
     50<li><a href="#ping">6.1 ping</a> 
     51<ul> 
     52<li><a href="#example_packets">6.1.1 Example Packets</a></li> 
     53</ul> 
     54</li> 
     55<li><a href="#find_node">6.2 find_node</a> 
     56<ul> 
     57<li><a href="#example_packets_2">6.2.1 Example Packets</a></li> 
     58</ul> 
     59</li> 
     60<li><a href="#get_peers">6.3 get_peers</a> 
     61<ul> 
     62<li><a href="#example_packets_3">6.3.1 Example Packets</a></li> 
     63</ul> 
     64</li> 
     65<li><a href="#announce_peer">6.4 announce_peer</a> 
     66<ul> 
     67<li><a href="#example_packets_4">6.4.1 Example Packets</a></li> 
     68</ul> 
     69</li> 
     70</ul> 
     71</li> 
     72<li><a href="#Footnotes">7 Footnotes</a></li> 
     73</ul> 
     74<a name="Overview"></a> 
     75<h3>Overview</h3> 
     76<p>Each node has a globally unique identifier known as the "node ID." 
     77Node IDs are chosen at random from the same 160-bit space as BitTorrent 
     78infohashes.  A "distance metric" is used to compare two node IDs or a node  
     79ID and an infohash for "closeness." Nodes must maintain a routing table 
     80containing the contact information for a small number of other nodes. 
     81The routing table becomes more detailed as IDs get closer to the node's 
     82own ID. Nodes know about many other nodes in the DHT that have IDs that 
     83are "close" to their own but have only a handful of contacts with IDs 
     84that are very far away from their own.</p> 
     85<p>In Kademlia, the distance metric is XOR and the result is 
     86interpreted as an unsigned integer. distance(A,B) = |A ⊗ B| Smaller 
     87values are closer.</p> 
     88<p>When a node wants to find peers for a torrent, it uses the 
     89distance metric to compare the infohash of the torrent with the IDs of 
     90the nodes in its own routing table. It then contacts the nodes it knows 
     91about with IDs closest to the infohash and asks them for the contact 
     92information of peers currently downloading the torrent. If a contacted 
     93node knows about peers for the torrent, the peer contact information is 
     94returned with the response. Otherwise, the contacted node must respond 
     95with the contact information of the nodes in its routing table that are 
     96closest to the infohash of the torrent. The original node iteratively 
     97queries nodes that are closer to the target infohash until it cannot 
     98find any closer nodes. After the search is exhausted, the client then 
     99inserts the peer contact information for itself onto the responding 
     100nodes with IDs closest to the infohash of the torrent.</p> 
     101<p>The return value for a query for peers includes an opaque value 
     102known as the "token." For a node to announce that its controlling peer 
     103is downloading a torrent, it must present the token received from the 
     104same queried node in a recent query for peers. When a node attempts to 
     105"announce" a torrent, the queried node checks the token against the 
     106querying node's IP address. This is to prevent malicious hosts from 
     107signing up other hosts for torrents. Since the token is merely returned 
     108by the querying node to the same node it received the token from, the 
     109implementation is not defined. Tokens must be accepted for a reasonable 
     110amount of time after they have been distributed. The BitTorrent 
     111implementation uses the SHA1 hash of the IP address concatenated onto a 
     112secret that changes every five minutes and tokens up to ten minutes old 
     113are accepted.</p> 
     114<a name="Routing_Table"></a> 
     115<h3>Routing Table</h3> 
     116<p>Every node maintains a routing table of known good nodes. The nodes 
     117in the routing table are used as starting points for queries in the 
     118DHT. Nodes from the routing table are returned in response to queries 
     119from other nodes.</p> 
     120<p>Not all nodes that we learn about are equal. Some are "good" 
     121and some are not. Many nodes using the DHT are able to send queries and 
     122receive responses, but are not able to respond to queries from other 
     123nodes. It is important that each node's routing table must contain only 
     124known good nodes. A good node is a node has responded to one of our 
     125queries within the last 15 minutes. A node is also good if it has ever 
     126responded to one of our queries and has sent us a query within the last 
     12715 minutes. After 15 minutes of inactivity, a node becomes 
     128questionable. Nodes become bad when they fail to respond to multiple 
     129queries in a row. Nodes that we know are good are given priority over 
     130nodes with unknown status.</p> 
     131<p>The routing table covers the entire node ID space from 0 to 2<sup>160</sup>. 
     132The routing table is subdivided into "buckets" that each cover a 
     133portion of the space. An empty table has one bucket with an ID space 
     134range of min=0, max=2<sup>160</sup>. When a node with ID "N" is 
     135inserted into the table, it is placed within the bucket that has min 
     136&lt;= N &lt; max. An empty table has only one bucket so any node must 
     137fit within it. Each bucket can only hold K nodes, currently eight, 
     138before becoming "full." When a bucket is full of known good nodes, no 
     139more nodes may be added unless our own node ID falls within the range 
     140of the bucket. In that case, the bucket is replaced by two new buckets 
     141each with half the range of the old bucket and the nodes from the old 
     142bucket are distributed among the two new ones. For a new table with 
     143only one bucket, the full bucket is always split into two new buckets 
     144covering the ranges 0..2<sup>159</sup> and 2<sup>159</sup>..2<sup>160</sup>.</p> 
     145<p>When the bucket is full of good nodes, the new node is simply 
     146discarded. If any nodes in the bucket are known to have become bad, 
     147then one is replaced by the new node. If there are any questionable 
     148nodes in the bucket have not been seen in the last 15 minutes, the 
     149least recently seen node is pinged. If the pinged node responds then 
     150the next least recently seen questionable node is pinged until one 
     151fails to respond or all of the nodes in the bucket are known to be 
     152good. If a node in the bucket fails to respond to a ping, it is 
     153suggested to try once more before discarding the node and replacing it 
     154with a new good node. In this way, the table fills with stable long 
     155running nodes.</p> 
     156<p>Each bucket should maintain a "last changed" property to 
     157indicate how "fresh" the contents are. When a node in a bucket is 
     158pinged and it responds, or a node is added to a bucket, or a node in a 
     159bucket is replaced with another node, the bucket's last changed 
     160property should be updated. Buckets that have not been changed in 15 
     161minutes should be "refreshed." This is done by picking a random ID in 
     162the range of the bucket and performing a find_nodes search on it. Nodes 
     163that are able to receive queries from other nodes usually do not need 
     164to refresh buckets often. Nodes that are not able to receive queries 
     165from other nodes usually will need to refresh all buckets periodically 
     166to ensure there are good nodes in their table when the DHT is needed. 
     167</p><p>Upon inserting the first node into it's routing table and when 
     168starting up thereafter, the node should attempt to find the closest 
     169nodes in the DHT to itself. It does this by issuing find_node messages 
     170to closer and closer nodes until it cannot find any closer. The routing 
     171table should be saved between invocations of the client software.</p> 
     172<a name="BitTorrent_Protocol_Extension"></a> 
     173<h3>BitTorrent Protocol Extension</h3> 
     174<p>The BitTorrent protocol has been extended to exchange node UDP port 
     175numbers between peers that are introduced by a tracker. In this way, 
     176clients can get their routing tables seeded automatically through the 
     177download of regular torrents. Newly installed clients who attempt to 
     178download a trackerless torrent on the first try will not have any nodes 
     179in their routing table and will need the contacts included in the 
     180torrent file.</p> 
     181<p>Peers supporting the DHT set the last bit of the 8-byte 
     182reserved flags exchanged in the BitTorrent protocol handshake. Peer 
     183receiving a handshake indicating the remote peer supports the DHT 
     184should send a PORT message. It begins with byte 0x09 and has a two byte 
     185payload containing the UDP port of the DHT node in network byte order. 
     186Peers that receive this message should attempt to ping the node on the 
     187received port and IP address of the remote peer. If a response to the 
     188ping is recieved, the node should attempt to insert the new contact 
     189information into their routing table according to the usual rules.</p> 
     190<a name="Torrent_File_Extensions"></a> 
     191<h3>Torrent File Extensions</h3> 
     192<p>A trackerless torrent dictionary does not have an "announce" key. 
     193Instead, a trackerless torrent has a "nodes" key. This key should be 
     194set to the K closest nodes in the torrent generating client's routing 
     195table. Alternatively, the key could be set to a known good node such as 
     196one operated by the person generating the torrent. Please do not 
     197automatically add "router.bittorrent.com" to torrent files or 
     198automatically add this node to clients routing tables.</p> 
     199<p><code>nodes = [["&lt;host&gt;", &lt;port&gt;], ["&lt;host&gt;", &lt;port&gt;], ...] 
     200nodes = [["127.0.0.1", 6881], ["your.router.node", 4804]]</code></p> 
     201<a name="KRPC_Protocol"></a> 
     202<h3>KRPC Protocol</h3> 
     203<p>The KRPC protocol is a simple RPC mechanism consisting of bencoded 
     204dictionaries sent over UDP. A single query packet is sent out and a 
     205single packet is sent in response. There is no retry. There are three 
     206message types: query, response, and error. For the DHT protocol, there 
     207are four queries: ping, find_node, get_peers, and announce_peer.</p> 
     208<p>A KRPC message is a single dictionary with two keys common to 
     209every message and additional keys depending on the type of message. 
     210Every message has a key "t" with a single character string value 
     211representing a transaction ID. This transaction ID is generated by the 
     212querying node and is echoed in the response, so responses may be 
     213correlated with multiple queries to the same node. The other key 
     214contained in every KRPC message is "y" with a single character value 
     215describing the type of message. The value of the "y" key is one of "q" 
     216for query, "r" for response, or "e" for error.</p> 
     217<a name="Contact_Encoding"></a> 
     218<h4>Contact Encoding</h4> 
     219<p>Contact information for peers is encoded as a 6-byte string. Also 
     220known as "Compact IP-address/port info" the 4-byte IP address is in 
     221network byte order with the 2 byte port in network byte order 
     222concatenated onto the end.</p> 
     223<p>Contact information for nodes is encoded as a 26-byte string. 
     224Also known as "Compact node info" the 20-byte Node ID in network byte 
     225order has the compact IP-address/port info concatenated to the end.</p> 
     226<a name="Queries"></a> 
     227<h4>Queries</h4> 
     228<p>Queries, or KRPC message dictionaries with a "y" value of "q", 
     229contain two additional keys; "q" and "a". Key "q" has a string value 
     230containing the method name of the query. Key "a" has a dictionary value 
     231containing named arguments to the query.</p> 
     232<a name="Responses"></a> 
     233<h4>Responses</h4> 
     234<p>Responses, or KRPC message dictionaries with a "y" value of "r", 
     235contain one additional key "r". The value of "r" is a dictionary 
     236containing named return values. Response messages are sent upon 
     237successful completion of a query.</p> 
     238<a name="Errors"></a> 
     239<h4>Errors</h4> 
     240<p>Errors, or KRPC message dictionaries with a "y" value of "e", 
     241contain one additional key "e". The value of "e" is a list. The first 
     242element is an integer representing the error code. The second element 
     243is a string containing the error message. Errors are sent when a query 
     244cannot be fulfilled. The following table describes the possible error 
     245codes:</p> 
     246<table> 
     247<tr> 
     248<td class="shade">201</td><td class="shade">Generic Error</td> 
     249</tr> 
     250<tr> 
     251<td>202</td><td>Server Error</td> 
     252</tr> 
     253<tr> 
     254<td class="shade">203</td><td class="shade">Protocol Error, such as a malformed packet,<br />invalid arguments, or bad token</td> 
     255</tr> 
     256<tr> 
     257<td>204</td><td>Method Unknown</td> 
     258</tr> 
     259</table> 
     260<a name="Example_Error_Packets"></a> 
     261<h5>Example Error Packets</h5> 
     262<p><code>generic error = {'t':0, 'y':'e', 'e':[201, "A Generic Error Ocurred"]} 
     263bencoded = d1:eli201e23:A Generic Error Ocurrede1:ti0e1:y1:ee</code></p> 
     264<a name="DHT_Queries"></a> 
     265<h3>DHT Queries</h3> 
     266<p>All queries have an "id" key and value containing the node ID of the 
     267querying node. All responses have an "id" key and value containing the 
     268node ID of the responding node.</p> 
     269<a name="ping"></a> 
     270<h4>ping</h4> 
     271<p>The most basic query is a ping. "q" = "ping" A ping query has a 
     272single argument, "id" the value is a 20-byte string containing the 
     273senders node ID in network byte order. The appropriate response to a 
     274ping has a single key "id" containing the node ID of the responding 
     275node.</p> 
     276<p><code> arguments:  {"id"&nbsp;: "&lt;querying nodes id&gt;"} 
     277 response: {"id"&nbsp;: "&lt;queried nodes id&gt;"}</code></p> 
     278<a name="example_packets"></a> 
     279<h5>Example Packets</h5> 
     280<p><code>ping Query = {"t":"0", "y":"q", "q":"ping", "a":{"id":"abcdefghij0123456789"}} 
     281 bencoded = d1:ad2:id20:abcdefghij0123456789e1:q4:ping1:t1:01:y1:qe</code></p> 
     282<p><code> Response = {"t":"0", "y":"r", "r": {"id":"mnopqrstuvwxyz123456"}} 
     283 bencoded = d1:rd2:id20:mnopqrstuvwxyz123456e1:t1:01:y1:re</code></p> 
     284<a name="find_node"></a> 
     285<h4>find_node</h4> 
     286<p>Find node is used to find the contact information for a node given 
     287its ID. "q" == "find_node" A find_node query has two arguments, "id" 
     288containing the node ID of the querying node, and "target" containing 
     289the ID of the node sought by the queryer. When a node receives a 
     290find_node query, it should respond with a key "nodes" and value of a 
     291string containing the compact node info for the target node or the K 
     292(8) closest good nodes in its own routing table.</p> 
     293<p><code>arguments:  {"id"&nbsp;: "&lt;querying nodes id&gt;", "target"&nbsp;: "&lt;id of target node&gt;"} 
     294response: {"id"&nbsp;: "&lt;queried nodes id&gt;", "nodes"&nbsp;: "&lt;compact node info&gt;"}</code></p> 
     295<a name="example_packets_2"></a> 
     296<h5>Example Packets</h5> 
     297<p><code>find_node Query = {'t':0, 'y':'q', 'q':'find_node', 'a': {'id':'abcdefghij0123456789', 'target':'mnopqrstuvwxyz123456'}} 
     298bencoded = d1:ad2:id20:abcdefghij01234567896:target20:mnopqrstuvwxyz123456e1:q9:find_node1:ti0e1:y1:qe</code></p> 
     299<p><code>Response = {'t':0, 'y':'r', 'r': {'id':'0123456789abcdefghij', 'nodes': 'def456...'}} 
     300bencoded = d1:rd2:id20:0123456789abcdefghij5:nodes9:def456...e1:ti0e1:y1:re</code></p> 
     301<a name="get_peers"></a> 
     302<h4>get_peers</h4> 
     303<p>Get peers associated with a torrent infohash. "q" = "get_peers" A 
     304get_peers query has two arguments, "id" containing the node ID of the 
     305querying node, and "info_hash" containing the infohash of the torrent. 
     306If the queried node has peers for the infohash, they are returned in a 
     307key "values" as a list with a single string containing "compact" format 
     308peer information concatenated together. If the queried node has no 
     309peers for the infohash, a key "nodes" is returned containing the K 
     310nodes in the queried nodes routing table closest to the infohash 
     311supplied in the query. In either case a "token" key is also included in 
     312the return value. The token value is a required argument for a future 
     313announce_peer query.</p> 
     314<p><code>arguments:  {"id"&nbsp;: "&lt;querying nodes id&gt;", "info_hash"&nbsp;: "&lt;20-byte infohash of target torrent&gt;"} 
     315 response: {"id"&nbsp;: "&lt;queried nodes id&gt;", "values"&nbsp;: ["&lt;compact peer info string&gt;"]} 
     316     or: {"id"&nbsp;: "&lt;queried nodes id&gt;", "nodes"&nbsp;: "&lt;compact node info&gt;"}</code></p> 
     317<a name="example_packets_3"></a> 
     318<h5>Example Packets</h5> 
     319<p><code>get_peers Query = {'t':0, 'y':'q', 'q':'get_peers', 'a': {'id':'abcdefghij0123456789', 'info_hash':'mnopqrstuvwxyz123456'}} 
     320bencoded = d1:ad2:id20:abcdefghij01234567899:info_hash20:mnopqrstuvwxyz123456e1:q9:get_peers1:ti0e1:y1:qe</code></p> 
     321<p><code>Response with peers = {'t':0, 'y':'r', 'r': {'id':'abcdefghij0123456789', 'token':'aoeusnth', 'values': ['axje.uidhtnmbrl']}} 
     322bencoded = d1:rd2:id20:abcdefghij01234567895:token8:aoeusnth6:valuesl15:axje.uidhtnmbrlee1:ti0e1:y1:re</code></p> 
     323<p><code>Response with closest nodes = {'t':0, 'y':'r', 'r': {'id':'abcdefghij0123456789', 'token':'aoeusnth', 'nodes': 'def456...'}} 
     324bencoded = d1:rd2:id20:abcdefghij01234567895:nodes9:def456...5:token8:aoeusnthe1:ti0e1:y1:re</code></p> 
     325<a name="announce_peer"></a> 
     326<h4>announce_peer</h4>  
     327<p>Announce that the peer controlling the querying node is downloading 
     328the a torrent on a port. announce_peer has four arguments: "id" containing the node ID of the 
     329querying node, "info_hash" containing the infohash of the torrent, 
     330"port" containing the port as an integer, and the "token" received in 
     331response to a previous get_peers query. The queried node must verify 
     332that the token was previously sent to the same IP address as the 
     333querying node. Then the queried node should store the IP address of the 
     334querying node and the supplied port number under the infohash in its 
     335store of peer contact information.</p> 
     336<p><code>arguments:  {"id"&nbsp;: "&lt;querying nodes id&gt;", "info_hash"&nbsp;: "&lt;20-byte infohash of target torrent&gt;", "port"&nbsp;: &lt;port number&gt;, "token"&nbsp;: "&lt;opaque token&gt;"} 
     337response: {"id"&nbsp;: "&lt;queried nodes id&gt;"}</code></p> 
     338<a name="example_packets_4"></a> 
     339<h5>Example Packets</h5> 
     340<p><code>announce_peers Query = {'t':0, 'y':'q', 'q':'announce_peers', 'a': {'id':'abcdefghij0123456789', 'info_hash':'mnopqrstuvwxyz123456', 'port'&nbsp;: 6881, 'token'&nbsp;: 'aoeusnth'}} 
     341bencoded = d1:ad2:id20:abcdefghij01234567899:info_hash20:<br /> 
     342mnopqrstuvwxyz1234564:porti6881e5:token8:aoeusnthe1:q14:announce_peers1:ti0e1:y1:qe</code></p> 
     343<p><code>Response = {"t":"0", "y":"r", "r": {"id":"mnopqrstuvwxyz123456"}} 
     344bencoded = d1:rd2:id20:mnopqrstuvwxyz123456e1:t1:01:y1:re</code></p> 
     345<a name="Footnotes"></a> 
     346<h3>Footnotes</h3> 
     347<ol> 
     348<li><a href="http://www.cs.rice.edu/Conferences/IPTPS02/109.pdf" class="external text" title="http://www.cs.rice.edu/Conferences/IPTPS02/109.pdf" rel="nofollow">"Kademlia: A Peer-to-peer Information System Based on the XOR Metric"</a>,<br />Petar Maymounkov and David Mazieres, 
     349</li> 
     350<li>Use SHA1 and plenty of entropy to ensure a unique ID</li> 
     351</ol> 
    201352</div> 
    202353<!-- ### End Content ### --> 
    … …  
    205356<div id="footer"> 
    206357<hr /> 
    207 <p>Copyright 2006 BitTorrent.org</p> 
     358<p>Copyright © 2006 BitTorrent.org</p> 
    208359</div> 
    209360</body> 
Note: See TracChangeset for help on using the changeset viewer.