Changeset 10528

Show
Ignore:
Timestamp:
02/04/08 16:10:30 (2 years ago)
Author:
dave
Message:

Change revision number to automatically updated $Revision$ in all .rst files.
Change last-modified date to automatically updated $Date$ in all .rst files.
Add "Local Variables" to the end of all .rst files.
Fix BEP numbers.
Make header formatting in all .rst files conform to PEP-style rst formatting requirements.

Remove some HTML markup from the bep_0003.rst, the BitTorrent? protocol standard.

Location:
dotorg/trunk_fixed/html/beps
Files:
9 modified

Legend:

Unmodified
Added
Removed

  • dotorg/trunk_fixed/html/beps/bep_0000.rst

    r10491 r10528  
    11BEP: 0 
    22Title: Index of BitTorrent Enhancement Proposals  
    3 Version: 1 
    4 Last-Modified: 11-Jan-2008 
    5 Author:  David Harrison 
     3Version: $Revision$ 
     4Last-Modified: $Date$ 
     5Author:  David Harrison <dave@bittorrent.com> 
    66Status:  Active 
    77Type:    Process 
    … …  
    1313wish of Bram Cohen that the BitTorrent mainline python implementation 
    1414remain open source and that the protocol development process be 
    15 modelled after the Python Enhancement Proposal~(PEP) process. 
     15modelled after the Python Enhancement Proposal (PEP) process. 
    1616 
    1717This document indexes all BitTorrent Enhancement Proposals (BEPs). 
    1818When a new proposal is submitted, one of the BitTorrent.org editors  
    1919assigns a BEP number and updates this index appropriately.  The process  
    20 is modelled after the PEP process used in the python community [#python].  Each  
     20is modelled after the PEP process used in the python community [#python]_.  Each  
    2121document has a number that never changes and the history of document is  
    22 maintained in subversion [#svn].   
     22maintained in subversion [#svn]_.   
    2323 
    2424 
    25 =====  =========================================   
    26 Num    Title                                      
    27 =====  ========================================= 
    28 0_     Index of BitTorrent Enhancement Proporsals 
    29 1_     The BEP Process                            
    30 2_     The BitTorrent Protocol Specification      
    31 3_     Known Number Allocations                   
    32 4_     DHT Protocol                               
    33 5_     Fast Extension                             
    34 6_     IPv6 Tracker Extension                     
    35 7_     Tracker Peer Obfuscation                   
    36 8_     Metadata Extension                         
    37 9_     Extension Protocol 
    38 =====  =========================================  
     25======     ==========================================   
     26Num        Title                                      
     27======     ========================================== 
     28|0|        Index of BitTorrent Enhancement Proporsals 
     29|1|        The BEP Process                            
     30|2|        Sample reStructured Text BEP Template 
     31|3|        The BitTorrent Protocol Specification      
     32|4|        Known Number Allocations                   
     33|5|        DHT Protocol                               
     34|6|        Fast Extension                             
     35|7|        IPv6 Tracker Extension                     
     36|8|        Tracker Peer Obfuscation                   
     37|9|        Metadata Extension                         
     38|10|       Extension Protocol 
     39|1000|     Pending Standards Track Documents 
     40======     ========================================== 
    3941 
    4042 
     43.. role:: raw-html(raw) 
     44   :format: html 
    4145 
    4246.. [#python] http://www.python.org/dev/peps/ 
    4347.. [#svn] http://svn.bittorrent.org 
    44 .. _0: bep_0000.html 
    45 .. _1: bep_0001.html 
    46 .. _2: bep_0002.html 
    47 .. _3: bep_0003.html 
    48 .. _4: bep_0004.html 
    49 .. _5: bep_0005.html 
    50 .. _6: bep_0006.html 
    51 .. _7: bep_0007.html 
    52 .. _8: bep_0008.html 
    53 .. _9: bep_0009.html 
    54 .. _10: bep_0010.html 
    55 .. _11: bep_0011.html 
     48.. |0| replace:: :raw-html:`<A HREF="bep_0000.html">0</A>` 
     49.. |1| replace:: :raw-html:`<A HREF="bep_0001.html">1</A>` 
     50.. |2| replace:: :raw-html:`<A HREF="bep_0002.html">2</A>` 
     51.. |3| replace:: :raw-html:`<A HREF="bep_0003.html">3</A>` 
     52.. |4| replace:: :raw-html:`<A HREF="bep_0004.html">4</A>` 
     53.. |5| replace:: :raw-html:`<A HREF="bep_0005.html">5</A>` 
     54.. |6| replace:: :raw-html:`<A HREF="bep_0006.html">6</A>` 
     55.. |7| replace:: :raw-html:`<A HREF="bep_0007.html">7</A>` 
     56.. |8| replace:: :raw-html:`<A HREF="bep_0008.html">8</A>` 
     57.. |9| replace:: :raw-html:`<A HREF="bep_0009.html">9</A>` 
     58.. |10| replace:: :raw-html:`<A HREF="bep_0009.html">10</A>` 
     59.. |1000| replace:: :raw-html:`<A HREF="bep_1000.html">1000</A>` 

  • dotorg/trunk_fixed/html/beps/bep_0003.rst

    r10524 r10528  
    1 BEP: 2 
     1BEP: 3 
    22Title: The BitTorrent Protocol Specification 
    3 Version: 2 
    4 Last-Modified: 11-Jan-2008 
     3Version: $Revision$ 
     4Last-Modified: $Date$ 
    55Author:  Bram Cohen <bram@bittorrent.com> 
    66Status:  Final 
    … …  
    5252------------------------------- 
    5353 
    54 - Strings are length-prefixed base ten followed by a colon and the string. For example <code>4:spam</code> corresponds to 'spam'. 
     54- Strings are length-prefixed base ten followed by a colon and the string. For example ``4:spam`` corresponds to 'spam'. 
    5555 
    5656- Integers are represented by an 'i' followed by the number in base 10 
    57   followed by an 'e'. For example <code>i3e</code> corresponds to 3 and 
    58   <code>i-3e </code>corresponds to -3. Integers have no size 
    59   limitation. <code>i-0e</code> is invalid. All encodings with a leading 
    60   zero, such as <code>i03e</code>, are invalid, other than 
    61   <code>i0e</code>, which of course corresponds to 0. 
     57  followed by an 'e'. For example ``i3e`` corresponds to 3 and 
     58  ``i-3e`` corresponds to -3. Integers have no size 
     59  limitation. ``i-0e`` is invalid. All encodings with a leading 
     60  zero, such as ``i03e``, are invalid, other than 
     61  ``i0e``, which of course corresponds to 0. 
    6262 
    6363- Lists are encoded as an 'l' followed by their elements (also 
    64   bencoded) followed by an 'e'. For example <code>l4:spam4:eggse</code> 
     64  bencoded) followed by an 'e'. For example ``l4:spam4:eggse`` 
    6565  corresponds to ['spam', 'eggs']. 
    6666 
    6767- Dictionaries are encoded as a 'd' followed by a list of alternating 
    6868  keys and their corresponding values followed by an 'e'. For example, 
    69   <code>d3:cow3:moo4:spam4:eggse</code> corresponds to {'cow': 'moo', 
    70   'spam': 'eggs'} and <code>d4:spaml1:a1:bee</code> corresponds to 
     69  ``d3:cow3:moo4:spam4:eggse`` corresponds to {'cow': 'moo', 
     70  'spam': 'eggs'} and ``d4:spaml1:a1:bee`` corresponds to 
    7171  {'spam': ['a', 'b']}. Keys must be strings and appear in sorted order 
    7272  (sorted as raw strings, not alphanumerics). 
    … …  
    8282  This maps to a dictionary, with keys described below. 
    8383 
    84   The <code>name</code> key maps to a string which is the suggested name  
     84  The ``name`` key maps to a string which is the suggested name  
    8585  to save the file (or directory) as. It is purely advisory. 
    8686 
    87   <code>piece length</code> maps to the number of bytes in each piece 
     87  ``piece length`` maps to the number of bytes in each piece 
    8888  the file is split into. For the purposes of transfer, files are 
    8989  split into fixed-size pieces which are all the same length except for 
    90   possibly the last one which may be truncated. <code>piece 
    91   length</code> is almost always a power of two, most commonly 2 18 = 
     90  possibly the last one which may be truncated. ``piece 
     91  length`` is almost always a power of two, most commonly 2 18 = 
    9292  256 K (BitTorrent prior to version 3.2 uses 2 20 = 1 M as 
    9393  default). 
    9494 
    95   <code>pieces</code> maps to a string whose length is a multiple of 
     95  ``pieces`` maps to a string whose length is a multiple of 
    9696  20. It is to be subdivided into strings of length 20, each of which is 
    9797  the SHA1 hash of the piece at the corresponding index. 
    9898 
    99   There is also a key <code>length</code> or a key <code>files</code>, 
    100   but not both or neither. If <code>length</code> is present then the 
     99  There is also a key ``length`` or a key ``files``, 
     100  but not both or neither. If ``length`` is present then the 
    101101  download represents a single file, otherwise it represents a set of 
    102102  files which go in a directory structure. 
    103103 
    104   In the single file case, <code>length</code> maps to the length of 
     104  In the single file case, ``length`` maps to the length of 
    105105  the file in bytes. 
    106106 
    … …  
    108108  only having a single file by concatenating the files in the order they 
    109109  appear in the files list. The files list is the value 
    110   <code>files</code> maps to, and is a list of dictionaries containing 
     110  ``files`` maps to, and is a list of dictionaries containing 
    111111  the following keys: 
    112112   
    113   <code>length</code> - The length of the file, in bytes. 
    114  
    115   <code>path</code> - A list of strings corresponding to subdirectory 
     113  ``length`` - The length of the file, in bytes. 
     114 
     115  ``path`` - A list of strings corresponding to subdirectory 
    116116  names, the last of which is the actual file name (a zero length list 
    117117  is an error case). 
    … …  
    157157 
    158158event 
    159   This is an optional key which maps to <code>started</code>, 
    160   <code>completed</code>, or <code>stopped</code> (or 
    161   <code>empty</code>, which is the same as not being present). If not 
     159  This is an optional key which maps to ``started``, 
     160  ``completed``, or ``stopped`` (or 
     161  ``empty``, which is the same as not being present). If not 
    162162  present, this is one of the announcements done at regular 
    163   intervals. An announcement using <code>started</code> is sent when a 
    164   download first begins, and one using <code>completed</code> is sent 
    165   when the download is complete. No <code>completed</code> is sent if 
     163  intervals. An announcement using ``started`` is sent when a 
     164  download first begins, and one using ``completed`` is sent 
     165  when the download is complete. No ``completed`` is sent if 
    166166  the file was complete when started. Downloaders send an announcement 
    167   using <code>stopped</code> when they cease downloading. 
     167  using ``stopped`` when they cease downloading. 
    168168 
    169169Tracker responses are bencoded dictionaries. If a tracker response 
    170 has a key <code>failure reason</code>, then that maps to a human 
     170has a key ``failure reason``, then that maps to a human 
    171171readable string which explains why the query failed, and no other keys 
    172 are required. Otherwise, it must have two keys: <code>interval</code>, 
     172are required. Otherwise, it must have two keys: ``interval``, 
    173173which maps to the number of seconds the downloader should wait between 
    174 regular rerequests, and <code>peers</code>. <code>peers</code> maps to 
    175 a list of dictionaries corresponding to <code>peers</code>, each of 
    176 which contains the keys <code>peer id</code>, <code>ip</code>, and 
    177 <code>port</code>, which map to the peer's self-selected ID, IP 
     174regular rerequests, and ``peers``. ``peers`` maps to 
     175a list of dictionaries corresponding to ``peers``, each of 
     176which contains the keys ``peer id``, ``ip``, and 
     177``port``, which map to the peer's self-selected ID, IP 
    178178address or dns name as a string, and port number, respectively. Note 
    179179that downloaders may rerequest on nonscheduled times if an event 
    … …  
    234234Next comes the 20 byte sha1 hash of the bencoded form of the info 
    235235value from the metainfo file. (This is the same value which is 
    236 announced as <code>info_hash</code> to the tracker, only here it's raw 
     236announced as ``info_hash`` to the tracker, only here it's raw 
    237237instead of quoted here). If both sides don't send the same value, they 
    238238sever the connection. The one possible exception is if a downloader 
    … …  
    341341are three times as likely to start as the current optimistic unchoke 
    342342as anywhere else in the rotation. 
    343  
     343 
     344.. 
     345   Local Variables: 
     346   mode: indented-text 
     347   indent-tabs-mode: nil 
     348   sentence-end-double-space: t 
     349   fill-column: 70 
     350   coding: utf-8 
     351   End: 
     352 

  • dotorg/trunk_fixed/html/beps/bep_0004.rst

    r10523 r10528  
    1 BEP: 3 
     1BEP: 4 
    22Title: Assigned Numbers 
    3 Version: 1 
    4 Last-Modified: 31-Jan-2008 
     3Version: $Revision$ 
     4Last-Modified: $Date$ 
    55Author:  David Harrison 
    66Status:  Active 
    … …  
    1010 
    1111 
    12 -------------------------------------------------- 
    13 BitTorrent.org » For Developers » Assigned Numbers 
    14 -------------------------------------------------- 
    15  
    1612This document describes the known bit allocations and message IDs for 
    1713the BitTorrent protocol.  To request a bit allocation contact 
    … …  
    2016 
    2117Reserved Bit Allocations 
    22 ------------------------ 
     18======================== 
    2319 
    2420:: 
    … …  
    3531 
    3632Reserved Message IDs 
    37 -------------------- 
     33==================== 
    3834 
    3935:: 
    … …  
    6157 Additional IDs used in deployed clients 
    6258 0x14   LTEP Handshake (implemented in libtorrent, uTorrent,...) 
     59 
     60 
     61.. 
     62   Local Variables: 
     63   mode: indented-text 
     64   indent-tabs-mode: nil 
     65   sentence-end-double-space: t 
     66   fill-column: 70 
     67   coding: utf-8 
     68   End: 

  • dotorg/trunk_fixed/html/beps/bep_0005.rst

    r10522 r10528  
    1 BEP: 4 
     1BEP: 5 
    22Title: DHT Protocol 
    3 Version: 2 
    4 Last-Modified: 11-Jan-2008 
     3Version: $Revision$ 
     4Last-Modified: $Date$ 
    55Author:  Andrew Loewenstern <drue@bittorrent.com> 
    6 Status:  Accepted 
     6Status:  Draft 
    77Type:    Standards Track 
    88Created: 31-Jan-2008 
    … …  
    1111BitTorrent uses a "distributed sloppy hash table" (DHT) for storing 
    1212peer contact information for "trackerless" torrents. In effect, each 
    13 peer becomes a tracker. The protocol is based on Kademila[Kademlia]_ and is 
     13peer becomes a tracker. The protocol is based on Kademila [#Kademlia]_ and is 
    1414implemented over UDP. 
    1515 
    … …  
    2323using the BitTorrent protocol. 
    2424 
     25 
    2526Overview 
    26 -------- 
     27======== 
    2728 
    2829Each node has a globally unique identifier known as the "node ID." 
    29 Node IDs are chosen at random from the same 160-bit space as BitTorrent 
    30 infohashes [#entropy]_.  A "distance metric" is used to compare two node IDs or a node  
    31 ID and an infohash for "closeness." Nodes must maintain a routing table 
    32 containing the contact information for a small number of other nodes. 
    33 The routing table becomes more detailed as IDs get closer to the node's 
    34 own ID. Nodes know about many other nodes in the DHT that have IDs that 
    35 are "close" to their own but have only a handful of contacts with IDs 
    36 that are very far away from their own. 
     30Node IDs are chosen at random from the same 160-bit space as 
     31BitTorrent infohashes [#entropy]_.  A "distance metric" is used to 
     32compare two node IDs or a node ID and an infohash for "closeness." 
     33Nodes must maintain a routing table containing the contact information 
     34for a small number of other nodes.  The routing table becomes more 
     35detailed as IDs get closer to the node's own ID. Nodes know about many 
     36other nodes in the DHT that have IDs that are "close" to their own but 
     37have only a handful of contacts with IDs that are very far away from 
     38their own. 
    3739 
    3840In Kademlia, the distance metric is XOR and the result is interpreted 
    … …  
    7072 
    7173Routing Table 
    72 ------------- 
     74============= 
    7375 
    7476Every node maintains a routing table of known good nodes. The nodes in 
    … …  
    137139 
    138140BitTorrent Protocol Extension 
    139 ----------------------------- 
     141============================= 
    140142 
    141143The BitTorrent protocol has been extended to exchange node UDP port 
    … …  
    159161 
    160162Torrent File Extensions 
    161 ----------------------- 
     163======================= 
    162164 
    163165A trackerless torrent dictionary does not have an "announce" key. 
    … …  
    177179 
    178180KRPC Protocol 
    179 ------------- 
     181============= 
    180182 
    181183The KRPC protocol is a simple RPC mechanism consisting of bencoded 
    … …  
    198200 
    199201Contact Encoding 
    200   Contact information for peers is encoded as a 6-byte string. Also 
    201   known as "Compact IP-address/port info" the 4-byte IP address is in 
    202   network byte order with the 2 byte port in network byte order 
    203   concatenated onto the end. 
    204  
    205   Contact information for nodes is encoded as a 26-byte string. 
    206   Also known as "Compact node info" the 20-byte Node ID in network byte 
    207   order has the compact IP-address/port info concatenated to the end. 
     202---------------- 
     203 
     204Contact information for peers is encoded as a 6-byte string. Also 
     205known as "Compact IP-address/port info" the 4-byte IP address is in 
     206network byte order with the 2 byte port in network byte order 
     207concatenated onto the end. 
     208   
     209Contact information for nodes is encoded as a 26-byte string. 
     210Also known as "Compact node info" the 20-byte Node ID in network byte 
     211order has the compact IP-address/port info concatenated to the end. 
    208212 
    209213Queries 
    210   Queries, or KRPC message dictionaries with a "y" value of "q", 
    211   contain two additional keys; "q" and "a". Key "q" has a string value 
    212   containing the method name of the query. Key "a" has a dictionary value 
    213   containing named arguments to the query. 
     214------- 
     215 
     216Queries, or KRPC message dictionaries with a "y" value of "q", 
     217contain two additional keys; "q" and "a". Key "q" has a string value 
     218containing the method name of the query. Key "a" has a dictionary value 
     219containing named arguments to the query. 
    214220 
    215221Responses 
    216   Responses, or KRPC message dictionaries with a "y" value of "r", 
    217   contain one additional key "r". The value of "r" is a dictionary 
    218   containing named return values. Response messages are sent upon 
    219   successful completion of a query. 
     222--------- 
     223 
     224Responses, or KRPC message dictionaries with a "y" value of "r", 
     225contain one additional key "r". The value of "r" is a dictionary 
     226containing named return values. Response messages are sent upon 
     227successful completion of a query. 
    220228 
    221229Errors 
    222   Errors, or KRPC message dictionaries with a "y" value of "e", 
    223   contain one additional key "e". The value of "e" is a list. The first 
    224   element is an integer representing the error code. The second element 
    225   is a string containing the error message. Errors are sent when a query 
    226   cannot be fulfilled. The following table describes the possible error 
    227   codes: 
     230------ 
     231 
     232Errors, or KRPC message dictionaries with a "y" value of "e", 
     233contain one additional key "e". The value of "e" is a list. The first 
     234element is an integer representing the error code. The second element 
     235is a string containing the error message. Errors are sent when a query 
     236cannot be fulfilled. The following table describes the possible error 
     237codes: 
    228238 
    229239+----------+------------------------------------------+ 
    … …  
    249259   
    250260DHT Queries 
    251 ----------- 
     261=========== 
    252262 
    253263All queries have an "id" key and value containing the node ID of the 
    … …  
    256266 
    257267ping 
    258   The most basic query is a ping. "q" = "ping" A ping query has a 
    259   single argument, "id" the value is a 20-byte string containing the 
    260   senders node ID in network byte order. The appropriate response to a 
    261   ping has a single key "id" containing the node ID of the responding 
    262   node. 
     268---- 
     269 
     270The most basic query is a ping. "q" = "ping" A ping query has a 
     271single argument, "id" the value is a 20-byte string containing the 
     272senders node ID in network byte order. The appropriate response to a 
     273ping has a single key "id" containing the node ID of the responding 
     274node. 
    263275 
    264276:: 
    … …  
    283295 
    284296find_node 
    285   Find node is used to find the contact information for a node given 
    286   its ID. "q" == "find_node" A find_node query has two arguments, "id" 
    287   containing the node ID of the querying node, and "target" containing 
    288   the ID of the node sought by the queryer. When a node receives a 
    289   find_node query, it should respond with a key "nodes" and value of a 
    290   string containing the compact node info for the target node or the K 
    291   (8) closest good nodes in its own routing table. 
     297--------- 
     298 
     299Find node is used to find the contact information for a node given 
     300its ID. "q" == "find_node" A find_node query has two arguments, "id" 
     301containing the node ID of the querying node, and "target" containing 
     302the ID of the node sought by the queryer. When a node receives a 
     303find_node query, it should respond with a key "nodes" and value of a 
     304string containing the compact node info for the target node or the K 
     305(8) closest good nodes in its own routing table. 
    292306 
    293307:: 
    … …  
    312326 
    313327get_peers 
    314   Get peers associated with a torrent infohash. "q" = "get_peers" A 
    315   get_peers query has two arguments, "id" containing the node ID of the 
    316   querying node, and "info_hash" containing the infohash of the torrent. 
    317   If the queried node has peers for the infohash, they are returned in a 
    318   key "values" as a list of strings. Each string containing "compact" format 
    319   peer information for a single peer. If the queried node has no 
    320   peers for the infohash, a key "nodes" is returned containing the K 
    321   nodes in the queried nodes routing table closest to the infohash 
    322   supplied in the query. In either case a "token" key is also included in 
    323   the return value. The token value is a required argument for a future 
    324   announce_peer query. The token value should be a short binary string. 
     328--------- 
     329 
     330Get peers associated with a torrent infohash. "q" = "get_peers" A 
     331get_peers query has two arguments, "id" containing the node ID of the 
     332querying node, and "info_hash" containing the infohash of the torrent. 
     333If the queried node has peers for the infohash, they are returned in a 
     334key "values" as a list of strings. Each string containing "compact" format 
     335peer information for a single peer. If the queried node has no 
     336peers for the infohash, a key "nodes" is returned containing the K 
     337nodes in the queried nodes routing table closest to the infohash 
     338supplied in the query. In either case a "token" key is also included in 
     339the return value. The token value is a required argument for a future 
     340announce_peer query. The token value should be a short binary string. 
    325341 
    326342:: 
    … …  
    353369 
    354370announce_peer 
    355   Announce that the peer, controlling the querying node, is downloading 
    356   a torrent on a port. announce_peer has four arguments: "id" containing the node ID of the 
    357   querying node, "info_hash" containing the infohash of the torrent, 
    358   "port" containing the port as an integer, and the "token" received in 
    359   response to a previous get_peers query. The queried node must verify 
    360   that the token was previously sent to the same IP address as the 
    361   querying node. Then the queried node should store the IP address of the 
    362   querying node and the supplied port number under the infohash in its 
    363   store of peer contact information. 
     371------------- 
     372 
     373Announce that the peer, controlling the querying node, is downloading 
     374a torrent on a port. announce_peer has four arguments: "id" containing the node ID of the 
     375querying node, "info_hash" containing the infohash of the torrent, 
     376"port" containing the port as an integer, and the "token" received in 
     377response to a previous get_peers query. The queried node must verify 
     378that the token was previously sent to the same IP address as the 
     379querying node. Then the queried node should store the IP address of the 
     380querying node and the supplied port number under the infohash in its 
     381store of peer contact information. 
    364382 
    365383:: 
    … …  
    383401  bencoded = d1:rd2:id20:mnopqrstuvwxyz123456e1:t2:aa1:y1:re 
    384402 
    385  
    386 Send questions, comments and corrections to editor@bittorrent.org 
    387  
    388  
    389 .. [Kademlia] Peter Maymounkov, David Mazieres, "`Kademlia: A Peer-to-peer Information System Based on the XOR Metric`_", IPTPS 2002. 
    390  
    391 .. _`Kademlia: A Peer-to-peer Information System Based on the XOR Metric`: http://www.cs.rice.edu/Conferences/IPTPS02/109.pdf 
     403References 
     404========== 
     405 
     406.. [#Kademlia] 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 
    392407 
    393408.. [#entropy] Use SHA1 and plenty of entropy to ensure a unique ID. 
    394409 
     410 
     411 
     412.. 
     413   Local Variables: 
     414   mode: indented-text 
     415   indent-tabs-mode: nil 
     416   sentence-end-double-space: t 
     417   fill-column: 70 
     418   coding: utf-8 
     419   End: 

  • dotorg/trunk_fixed/html/beps/bep_0006.rst

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

  • dotorg/trunk_fixed/html/beps/bep_0007.rst

    r10520 r10528  
    1 BEP: 4 
     1BEP: 7 
    22Title: IPv6 Tracker Extension 
    3 Version: 2 
    4 Last-Modified: 11-Jan-2008 
     3Version: $Revision$ 
     4Last-Modified: $Date$ 
    55Author:  Greg Hazel <greg@bittorrent.com>, Arvid Norberg <arvid@bittorrent.com> 
    66Status:  Draft 
    … …  
    101101 
    102102 
     103 
     104.. 
     105   Local Variables: 
     106   mode: indented-text 
     107   indent-tabs-mode: nil 
     108   sentence-end-double-space: t 
     109   fill-column: 70 
     110   coding: utf-8 
     111   End: 

  • dotorg/trunk_fixed/html/beps/bep_0008.rst

    r10519 r10528  
    1 BEP: 4 
     1BEP: 8 
    22Title: Tracker Peer Obfuscation 
    3 Version: 3 
    4 Last-Modified: 02-Feb-2008 
     3Version: $Revision$ 
     4Last-Modified: $Date$ 
    55Author:  David Harrison <dave@bittorrent.com>, Anthony Ciani <tony@ciani.phy.uic.edu>, Arvid Norberg <arvid@bittorrent.com>, Greg Hazel <greg@bittorrent.com>  
    66Status:  Draft 
    … …  
    2626 
    2727announce parameter 
    28 ------------------ 
     28================== 
    2929 
    3030When using this extension, instead of passing the ``info_hash`` parameter 
    … …  
    4646 
    4747announce response 
    48 ----------------- 
     48================= 
    4949 
    5050If the tracker supports this extension, the response should be exactly the 
    … …  
    5757 
    5858peer list obfuscation 
    59 --------------------- 
     59===================== 
    6060 
    6161We distinguish between the *tracker peer list* and the *returned peer 
    … …  
    112112 
    113113optimizations 
    114 ------------- 
     114============= 
    115115 
    116116The described optimizations are OPTIONAL for the tracker, but the 
    … …  
    143143that the tracker encrypted the tracker peer list starting from the 
    144144first byte in the pseudorandom string then *i* also corresponds to the 
    145 *i*th ip-port pair in the tracker peer list and the starting point of 
     145*ith* ip-port pair in the tracker peer list and the starting point of 
    146146the copy into the returned request.   
    147147 
    … …  
    200200 
    201201backwards compatibility 
    202 ----------------------- 
     202======================= 
    203203 
    204204Trackers that support obfuscation are identified in the .torrent file 
    … …  
    236236 
    237237rationale 
    238 --------- 
     238========= 
    239239 
    240240This extension directly addresses a known attack on the BitTorrent 
    … …  
    337337.. _`BitTorrent Protocol Encryption`: http://www.bittorrent.org/beps/bep_0013.html 
    338338 
     339 
     340.. 
     341   Local Variables: 
     342   mode: indented-text 
     343   indent-tabs-mode: nil 
     344   sentence-end-double-space: t 
     345   fill-column: 70 
     346   coding: utf-8 
     347   End: 

  • dotorg/trunk_fixed/html/beps/bep_0009.rst

    r10518 r10528  
    1 metadata extension 
    2 ================== 
     1BEP: 9 
     2Title: Metadata Extension 
     3Version: $Revision$ 
     4Last-Modified: $Date$ 
     5Author:  Greg Hazel <greg@bittorrent.com>, Arvid Norberg <arvid@bittorrent.com> 
     6Status:  Draft 
     7Type:    Standards Track 
     8Created: 31-Jan-2008 
     9Post-History: 
    310 
    411The purpose of this extension is to allow clients to join a swarm and 
    … …  
    1017 
    1118metadata 
    12 -------- 
     19======== 
    1320 
    1421This extension only transfers the info-dictionary part of the .torrent 
    … …  
    2027 
    2128extension header 
    22 ---------------- 
     29================ 
    2330 
    2431The metadata extension uses the `extension protocol`_ to advertize its 
    … …  
    3744 
    3845extension message 
    39 ----------------- 
     46================= 
    4047 
    4148The extension messages are bencoded. There are 3 different kinds of messages: 
    … …  
    5057 
    5158request 
    52 ~~~~~~~ 
     59------- 
    5360 
    5461The ``request`` message does not have any additional keys in the dictionary. 
    … …  
    7077 
    7178data 
    72 ~~~~ 
     79---- 
    7380 
    7481The ``data`` message adds another entry to the dictionary, "total_size". This 
    … …  
    9097 
    9198reject 
    92 ~~~~~~ 
     99------ 
    93100 
    94101The ``reject`` message does not have any additional keys in its message. 
    … …  
    106113 
    107114magnet URI format 
    108 ----------------- 
     115================= 
    109116 
    110117The magnet URI format is:: 
    … …  
    124131If no tracker is specified, the client SHOULD use the DHT to acquire peers. 
    125132 
    126 authors 
    127 ------- 
    128133 
    129 | `Greg Hazel`__ 
    130 | `Arvid Norberg`__ 
    131  
    132 .. __: mailto:greg@bittorrent.com 
    133 .. __: mailto:arvid@bittorrent.com 
    134  
     134 
     135.. 
     136   Local Variables: 
     137   mode: indented-text 
     138   indent-tabs-mode: nil 
     139   sentence-end-double-space: t 
     140   fill-column: 70 
     141   coding: utf-8 
     142   End: 

  • dotorg/trunk_fixed/html/beps/bep_0010.rst

    r10516 r10528  
    1 extension protocol for bittorrent 
    2 ================================= 
     1BEP: 10 
     2Title: Extension Protocol 
     3Version: $Revision$ 
     4Last-Modified: $Date$ 
     5Author:  Arvid Norberg <arvid@bittorrent.com>, Ludvig Strigeus <ludde@utorrent.com> 
     6Status:  Draft 
     7Type:    Standards Track 
     8Created: 31-Jan-2008 
     9Post-History: 
     10 
    311 
    412The intention of this protocol is to provide a simple and thin transport 
    … …  
    4654 
    4755handshake message 
    48 ----------------- 
     56================= 
    4957 
    5058The payload of the handshake message is a bencoded dictionary. All items 
    … …  
    124132| ``p``             | 6881                             | 
    125133+-------------------+----------------------------------+ 
    126 | ``v``             | "�Torrent 1.2"                   | 
     134| ``v``             | "µTorrent 1.2"                   | 
    127135+-------------------+----------------------------------+ 
    128136 
    129137and in the encoded form: 
    130138 
    131 ``d1:md11:LT_metadatai1e6:�T_PEXi2ee1:pi6881e1:v13:\xc2\xb5Torrent 1.2e`` 
     139``d1:md11:LT_metadatai1e6:µT_PEXi2ee1:pi6881e1:v13:\xc2\xb5Torrent 1.2e`` 
    132140 
    133141To make sure the extension names do not collide by mistake, they should be 
    … …  
    163171 
    164172rationale 
    165 --------- 
     173========= 
    166174 
    167175The reason why the extension messages' IDs would be defined in the handshake 
    … …  
    198206be a human readable protocol, so why bother. 
    199207 
    200 authors 
    201 ------- 
    202  
    203 | `Arvid Norberg`__ 
    204 | `Ludvig Strigeus`__ 
    205  
    206 .. __: mailto:arvid@bittorrent.com 
    207 .. __: ludde@utorrent.com 
    208  
     208 
     209 
     210.. 
     211   Local Variables: 
     212   mode: indented-text 
     213   indent-tabs-mode: nil 
     214   sentence-end-double-space: t 
     215   fill-column: 70 
     216   coding: utf-8 
     217   End: