root / dotorg / v3 / html / fast_extensions.html

Revision 10160, 12.9 kB (checked in by dave, 12 months ago)

one place where "integer" should be "byte"

Line 
1<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
2        "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
3<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
4<head>
5<meta http-equiv="Content-type" content="text/html; charset=utf-8" />
6<title>BitTorrent.org For Developers</title>
7<link rel="stylesheet" type="text/css" href="./css/screen.css" media="screen" />
8</head>
9<body id="www-bittorrent-org">
10<div id="upper" class="clear">
11<div id="wrap">
12<div id="header">
13<h1><a href="./index.html">BitTorrent<span>.org</span></a></h1>
14</div>
15<div id="nav">
16<ul>
17<li><a href="./index.html">Home</a></li>
18<li><a href="./introduction.html">For Users</a></li>
19<li><span>For Developers</span></li>
20<!-- <li><a href="./blog">Blog</a></li> -->
21<li><a href="./donate.html">Donate!</a></li>
22</ul>
23</div>
24<!-- ### Begin Content ### -->
25<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>
29These are enabled by setting the third least significant bit of the
30last 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
36in v1.0 of the BitTorrent protocol.  All integers are four bytes
37big-endian.  All messages start with an integer message length.  All messages
38but the Keep-Alive follow the message length with a single byte opcode
39and zero or more opcode-dependant arguments.
40</p><p>The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL
41NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED",  "MAY", and
42"OPTIONAL" in this document are to be interpreted as described in
43IETF <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>
59messages, and adds a <i>Reject Request.</i>  Now, every request
60is guaranteed to result in EXACTLY ONE response
61which is either the corresponding reject or corresponding piece
62message.  Even when a request is cancelled, the peer receiving
63the cancel should respond with either the corresponding reject or
64the corresponding piece: requests that are being processed are
65allowed to complete.
66</p><p>Choke no longer implicitly rejects all pending requests,
67thus eliminating some race conditions which could cause pieces
68to be needlessly requested multiple times.
69</p><p>Additionally, if a peer receives a piece that was never requested,
70the 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
78has all or none of the pieces respectively.  When present, <i>Have All</i>
79or <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
81the handshake.  The reason for these messages is to save bandwidth.  Also
82slightly to remove the idiosyncrasy of sending no message when a peer
83has 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
91download this piece."  The intended usage is for 'super-seeding'
92without throughput reduction, to avoid redundant downloads, and so that
93a seed which is disk I/O bound can upload continguous or identical
94pieces to avoid excessive disk seeks.  In all cases, the seed SHOULD
95operate to maintain a roughly equal number of copies of each piece in
96the network.  A peer MAY send more than one <i>suggest piece</i> message at
97any given time.  A peer receiving multiple <i>suggest piece</i> messages
98MAY interpret this as meaning that all of the suggested pieces
99are 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
109request 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>
129follows.  All integers in this pseudocode are four bytes represented in network (big-endian) byte order.  <i>[a:b]</i> denotes the sequence of consecutive bytes 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
131provisions 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
133NAT.  Since the node sending the <i>Allowed Fast</i> messages computes
134the set, the correct <i>ip</i> is usually the <i>ip</i> address on the other
135end of the connection.  The host computing the set MAY use the <i>ip</i>
136address 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
153ip address.  We do this to prevent a user that obtains more than one
154IP address on the same network from obtaining more than one
155<i>allowed fast set.</i>  Use of three bytes is heuristic and
156historical.
157</p><p>Step (3) generates a 20-byte random number on each call.  By
158performing a SHA-1 hash on the previous iteration's hash, we can
159generate an arbitrarily long pseudorandom sequence.
160</p><p>Steps (4) through (9) partition the 20-byte hash into piece indices
161and 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
195aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for node with IP 80.4.4.200:
196  1059,431,808,1217,287,376,1188
1979 piece allowed fast set for torrent with 1313 pieces and hex infohash
198aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for node with IP 80.4.4.200:
199  1059,431,808,1217,287,376,1188,353,508
200</pre>
201</div>
202
203<div class="section">
204 <h2><a id="authors" name="authors">authors</a></h2>
205 <div class="line-block">
206   <div class="line"><a class="reference" href="mailto:dave&#37;&#52;&#48;bittorrent&#46;com">David Harrison</a></div>
207   <div class="line"><a class="reference" href="mailto:bram&#37;&#52;&#48;bittorrent&#46;com">Bram Cohen</a></div>
208 </div>
209</div>
210<!-- ### End Content ### -->
211</div>
212</div>
213<div id="footer">
214<hr />
215<p>Copyright 2008 BitTorrent.org</p>
216</div>
217</body>
218</html>
Note: See TracBrowser for help on using the browser.