root / dotorg / trunk / html / beps / bep_0006.html

Revision 11040, 15.7 kB (checked in by dave, 8 weeks ago)

All HTML docs now reference the new SVN server running at bittorrent.org

Line 
1<?xml version="1.0" encoding="utf-8" ?>
2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.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<meta name="generator" content="Docutils 0.5: http://docutils.sourceforge.net/" />
7<title></title>
8<link rel="stylesheet" href="../css/bep.css" type="text/css" />
9</head>
10<body>
11<div class="document">
12
13<div id="upper" class="clear">
14<div id="wrap">
15<div id="header">
16<h1><a href="../index.html">BitTorrent<span>.org</span></a></h1>
17</div>
18<div id="nav">
19<ul>
20<li><a href="../index.html">Home</a></li>
21<li><a href="../introduction.html">For Users</a></li>
22<li><a href="bep_0000.html"><span>For Developers</span></a></li>
23<!-- <li><a href="./blog">Blog</a></li> -->
24<li><a href="http://forum.bittorrent.org"> Forums </li>
25<li><a href="../donate.html">Donate!</a></li>
26</ul>
27</div> <!-- nav -->
28<!-- ### Begin Content ### -->
29<div id="second">
30
31
32
33<table class="rfc2822 docutils field-list" frame="void" rules="none">
34<col class="field-name" />
35<col class="field-body" />
36<tbody valign="top">
37<tr class="field"><th class="field-name">BEP:</th><td class="field-body">6</td>
38</tr>
39<tr class="field"><th class="field-name">Title:</th><td class="field-body">Fast Extension</td>
40</tr>
41<tr class="field"><th class="field-name">Version:</th><td class="field-body">11031</td>
42</tr>
43<tr class="field"><th class="field-name">Last-Modified:</th><td class="field-body"><a class="reference external" href="http://svn.bittorrent.org/trac/browser/dotorg/trunk/html/beps/bep_0006.rst">2008-02-28 16:43:58 -0800 (Thu, 28 Feb 2008)</a></td>
44</tr>
45<tr class="field"><th class="field-name">Author:</th><td class="field-body">David Harrison &lt;dave&#32;&#97;t&#32;bittorrent.com&gt;, Bram Cohen &lt;bram&#32;&#97;t&#32;bittorrent.com&gt;</td>
46</tr>
47<tr class="field"><th class="field-name">Status:</th><td class="field-body">Draft</td>
48</tr>
49<tr class="field"><th class="field-name">Type:</th><td class="field-body">Standards Track</td>
50</tr>
51<tr class="field"><th class="field-name">Created:</th><td class="field-body">01-Feb-2008</td>
52</tr>
53<tr class="field"><th class="field-name">Post-History:</th><td class="field-body"></td>
54</tr>
55</tbody>
56</table>
57<hr />
58<div class="contents topic" id="contents">
59<p class="topic-title first">Contents</p>
60<ul class="simple">
61<li><a class="reference internal" href="#modifications-to-semantics-of-existing-messages" id="id5">Modifications to Semantics of Existing Messages</a></li>
62<li><a class="reference internal" href="#have-all-have-none" id="id6">Have All/Have None</a></li>
63<li><a class="reference internal" href="#suggest-piece" id="id7">Suggest Piece</a></li>
64<li><a class="reference internal" href="#reject-request" id="id8">Reject Request</a></li>
65<li><a class="reference internal" href="#allowed-fast" id="id9">Allowed Fast</a></li>
66<li><a class="reference internal" href="#allowed-fast-set-generation" id="id10">Allowed Fast Set Generation</a></li>
67<li><a class="reference internal" href="#example-implementation" id="id11">Example Implementation</a></li>
68<li><a class="reference internal" href="#references" id="id12">References</a></li>
69<li><a class="reference internal" href="#copyright" id="id13">Copyright</a></li>
70</ul>
71</div>
72<p>The Fast Extension packages several extensions: <em>Have None/Have All</em>,
73<em>Reject Requests</em>, <em>Suggestions</em> and <em>Allowed Fast.</em>
74These are enabled by setting the third least significant bit of the
75last reserved byte in the BitTorrent handshake:</p>
76<pre class="literal-block">
77reserved[7] |= 0x04
78</pre>
79<p>The extension is enabled only if both ends of the connection set this bit.</p>
80<p>The following proposed messages adhere to the syntax of messages found
81in v1.0 of the BitTorrent protocol.  All integers are four bytes
82big-endian.  All messages start with an integer message length.  All
83messages but the Keep-Alive follow the message length with a single
84byte opcode and zero or more opcode-dependant arguments.</p>
85<p>The key words &quot;MUST&quot;, &quot;MUST NOT&quot;, &quot;REQUIRED&quot;, &quot;SHALL&quot;, &quot;SHALL
86NOT&quot;, &quot;SHOULD&quot;, &quot;SHOULD NOT&quot;, &quot;RECOMMENDED&quot;,  &quot;MAY&quot;, and
87&quot;OPTIONAL&quot; in this document are to be interpreted as described in
88IETF <a class="reference external" href="http://www.ietf.org/rfc/rfc2119.txt">RFC 2119</a> <a class="footnote-reference" href="#id1" id="id2">[1]</a>.</p>
89<div class="section" id="modifications-to-semantics-of-existing-messages">
90<h1>Modifications to Semantics of Existing Messages</h1>
91<p>The Fast Extension modifies the semantics of the
92<em>Request</em>, <em>Choke</em>, <em>Unchoke</em>, and <em>Cancel</em>
93messages, and adds a <em>Reject Request.</em>  Now, every request
94is guaranteed to result in EXACTLY ONE response
95which is either the corresponding reject or corresponding piece
96message.  Even when a request is cancelled, the peer receiving
97the cancel should respond with either the corresponding reject or
98the corresponding piece: requests that are being processed are
99allowed to complete.</p>
100<p>Choke no longer implicitly rejects all pending requests,
101thus eliminating some race conditions which could cause pieces
102to be needlessly requested multiple times.</p>
103<p>Additionally, if a peer receives a piece that was never requested,
104the peer MUST close the connection.</p>
105</div>
106<div class="section" id="have-all-have-none">
107<h1>Have All/Have None</h1>
108<pre class="literal-block">
109*Have All*: &lt;len=0x0001&gt; &lt;op=0x0E&gt;
110</pre>
111<pre class="literal-block">
112*Have None*: &lt;len=0x0001&gt;&lt;op=0x0F&gt;
113</pre>
114<p><em>Have All</em> and <em>Have None</em> specify that the message sender
115has all or none of the pieces respectively.  When present, <em>Have All</em>
116or <em>Have None</em> replace the <em>Have Bitfield.</em>  Exactly one of <em>Have All</em>,
117<em>Have None</em>, or <em>Have Bitfield</em> MUST appear and only immediately after
118the handshake.  The reason for these messages is to save bandwidth.  Also
119slightly to remove the idiosyncrasy of sending no message when a peer
120has no pieces.</p>
121<p>When the fast extension is disabled, if a peer receives <em>Have All</em> or
122<em>Have None</em> then the peer MUST close the connection.</p>
123</div>
124<div class="section" id="suggest-piece">
125<h1>Suggest Piece</h1>
126<pre class="literal-block">
127*Suggest Piece*: &lt;len=0x0005&gt;&lt;op=0x0D&gt;&lt;index&gt;
128</pre>
129<p><em>Suggest Piece</em> is an advisory message meaning &quot;you might like to
130download this piece.&quot;  The intended usage is for 'super-seeding'
131without throughput reduction, to avoid redundant downloads, and so that
132a seed which is disk I/O bound can upload continguous or identical
133pieces to avoid excessive disk seeks.  In all cases, the seed SHOULD
134operate to maintain a roughly equal number of copies of each piece in
135the network.  A peer MAY send more than one <em>suggest piece</em> message at
136any given time.  A peer receiving multiple <em>suggest piece</em> messages
137MAY interpret this as meaning that all of the suggested pieces
138are equally appropriate.</p>
139<p>When the fast extension is disabled, if a peer receives a
140<em>Suggest Piece</em> message, the peer MUST close the connection.</p>
141</div>
142<div class="section" id="reject-request">
143<h1>Reject Request</h1>
144<pre class="literal-block">
145*Reject Request*: &lt;len=0x000D&gt;&lt;op=0x10&gt;&lt;index&gt;&lt;begin&gt;&lt;offset&gt;
146</pre>
147<p><em>Reject Request</em> notifies a requesting peer that its request will not be satisfied.</p>
148<p>If the fast extension is disabled and a peer receives a reject
149request then the peer MUST close the connection.</p>
150<p>When the fast extension is enabled:</p>
151<ul class="simple">
152<li>If a peer receives a reject for a request that was never sent then
153the peer SHOULD close the connection.</li>
154<li>If a peer sends a choke, it MUST reject all requests from the peer
155to whom the choke was sent except it SHOULD NOT reject requests for
156pieces that are in the <em>allowed fast set.</em> A peer SHOULD choke first
157and then reject requests so that the peer receiving the choke does not
158re-request the pieces.</li>
159<li>If a peer receives a request from a peer its choking, the peer
160receiving the request SHOULD send a reject unless the piece is in the
161<em>allowed fast set.</em></li>
162<li>If a peer receives an excessive number of requests from a peer it is
163choking, the peer receiving the requests MAY close the connection
164rather than reject the request.  However, consider that it can take
165several seconds for buffers to drain and messages to propagate once a
166peer is choked.</li>
167</ul>
168</div>
169<div class="section" id="allowed-fast">
170<h1>Allowed Fast</h1>
171<pre class="literal-block">
172* Allowed Fast: &lt;len=0x0005&gt;&lt;op=0x11&gt;&lt;index&gt;*
173</pre>
174<p>With the BitTorrent protocol specified in <a class="reference external" href="http://www.bittorrent.org/beps/bep_0002.html">BEP 0002</a> <a class="footnote-reference" href="#id3" id="id4">[2]</a>, new peers take
175several minutes to ramp up before they can effectively engage in
176BitTorrent's tit-for-tat. The reason is simple: starting peers have
177few pieces to trade.</p>
178<p><em>Allowed Fast</em> is an advisory message which means &quot;if you ask for this
179piece, I'll give it to you even if you're choked.&quot; <em>Allowed Fast</em> thus
180shortens the awkward stage during which the peer obtains occasional
181optimistic unchokes but cannot sufficiently reciprocate to remain
182unchoked.</p>
183<p>The pieces that can be downloaded when choked constitute a peer's
184<em>allowed fast set.</em> The set is generated using a canonical algorithm
185that produces piece indices unique to the message receiver so that if
186two peers offer <em>k</em> pieces fast it will be the same <em>k</em>, and if one
187offers <em>k+1</em> it will be the same <em>k</em> plus one more. <em>k</em> should be
188small enough to avoid abuse, but large enough to ramp up
189tit-for-tat. We currently set <em>k</em> to 10, but peers are free to change
190this number, e.g., to suit load.</p>
191<p>The message sender MAY list pieces that the message sender does not
192have. The receiver MUST NOT interpret an Allowed Fast message as
193meaning that the message sender has the piece. This allows peers to
194generate and communicate allowed fast sets at the beginning of a
195connection. However, a peer MAY send Allowed Fast messages at any
196time.</p>
197<p>A peer SHOULD send Allowed Fast messages to any starting peer unless
198the local peer lacks sufficient resources. A peer MAY reject requests
199for already Allowed Fast pieces if the local peer lacks sufficient
200resources, if the requested piece has already been sent to the
201requesting peer, or if the requesting peer is not a starting peer. Our
202current implementation rejects requests for Allowed Fast messages
203whenever the requesting peer has more than * k * pieces.</p>
204<blockquote>
205When the fast extension is disabled, if a peer recieves an Allowed
206Fast message then the peer MUST close the connection.</blockquote>
207</div>
208<div class="section" id="allowed-fast-set-generation">
209<h1>Allowed Fast Set Generation</h1>
210<p>The canonical algorithm for computing a peer <em>P'*s *allowed fast set</em>
211follows.  All integers in this pseudocode are four bytes represented
212in network (big-endian) byte order.  <em>[a:b]</em> denotes the sequence of
213consecutive bytes from <em>a</em> to <em>b</em> excluding <em>b</em>, i.e., <em>(a, a+1,
214a+2,..., b-1)</em>. <em>x[a:b]</em> denotes a subsequence of elements in an array
215<em>x</em> starting from index <em>a</em> to but not including index <em>b</em>.</p>
216<p>Let <em>ip</em> denote <em>P'*s IPv4 address.  We currently have no
217provisions for IPv6. If a peer is behind a Network Address Translator
218(NAT) then *ip</em> should be the externally facing IP address of the
219NAT.  Since the node sending the <em>Allowed Fast</em> messages computes
220the set, the correct <em>ip</em> is usually the <em>ip</em> address on the other
221end of the connection.  The host computing the set MAY use the <em>ip</em>
222address on the other end of the connection regardless</p>
223<p>Let <em>sz</em> denote the number of pieces in the torrent.</p>
224<p>Let <em>a</em> denote the allowed fast set.</p>
225<p>Let <em>k</em> denote the final number of pieces in the allowed fast set.</p>
226<pre class="literal-block">
227x = 0xFFFFFF00 &amp; ip                           (1)
228x.append(infohash)                            (2)
229while |a| &lt; k:
230  x = SHA1(x)                                 (3)
231  for i in [0:5] and |a| &lt; k:                 (4)
232    j = i*4                                   (5)
233    y = x[j:j+4]                              (6)
234    index = y % sz                            (7)
235    if index not in a:                        (8)
236      add index to a                          (9)
237</pre>
238<p>Step (1) selects the most significant octets in peer <em>P'*s
239ip address.  We do this to prevent a user that obtains more than one
240IP address on the same network from obtaining more than one
241*allowed fast set.</em>  Use of three bytes is heuristic and
242historical.</p>
243<p>Step (3) generates a 20-byte random number on each call.  By
244performing a SHA-1 hash on the previous iteration's hash, we can
245generate an arbitrarily long pseudorandom sequence.</p>
246<p>Steps (4) through (9) partition the 20-byte hash into piece indices
247and add them to the allowed fast set.</p>
248</div>
249<div class="section" id="example-implementation">
250<h1>Example Implementation</h1>
251<p>The following C++ implementation was provided by CacheLogic:</p>
252<pre class="literal-block">
253void generate_fast_set(
254  uint32 k,     // number of pieces in set
255  uint32 sz,    // number of pieces in torrent
256  const char infohash[20], // infohash of torrent
257  uint32 ip, // in host byte order, ie localhost is 0x7f000001
258  std::
259vector&lt;uint32&gt; &amp;a) // generated set of piece indices
260{
261   a.clear();
262   std::string x;
263   char buf[4];
264   *(uint32*)buf = htonl(ip &amp; 0xffffff00);
265   x.assign(buf, 4);
266   x.append(infohash, 20); // (3)
267   while (a.size()&lt;k) {
268     x = SHA1(x); // (4)
269     for ( int i=0&amp;nbsp;; i&lt;5 &amp;&amp; a.size()&lt;k; i++ ) { // (5)
270       int j = i*4; // (6)
271       uint32 y = ntohl(*(uint32*)(x.data()+j)); // (7)
272       uint32 index = y % sz; // (8)
273       if (std::find(a.begin(), a.end(), index)==a.end()) { // (9)
274         a.push_back(index); // (10)
275       }
276     }
277   }
278}
279</pre>
280<p>Example results generated by this function:</p>
281<pre class="literal-block">
2827 piece allowed fast set for torrent with 1313 pieces and hex infohash
283aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for node with IP 80.4.4.200:
284  1059,431,808,1217,287,376,1188
2859 piece allowed fast set for torrent with 1313 pieces and hex infohash
286aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for node with IP 80.4.4.200:
287  1059,431,808,1217,287,376,1188,353,508
288</pre>
289</div>
290<div class="section" id="references">
291<h1>References</h1>
292<table class="docutils footnote" frame="void" id="id1" rules="none">
293<colgroup><col class="label" /><col /></colgroup>
294<tbody valign="top">
295<tr><td class="label"><a class="fn-backref" href="#id2">[1]</a></td><td><a class="reference external" href="http://www.ietf.org/rfc/rfc2119.txt">http://www.ietf.org/rfc/rfc2119.txt</a></td></tr>
296</tbody>
297</table>
298<table class="docutils footnote" frame="void" id="id3" rules="none">
299<colgroup><col class="label" /><col /></colgroup>
300<tbody valign="top">
301<tr><td class="label"><a class="fn-backref" href="#id4">[2]</a></td><td><a class="reference external" href="http://www.bittorrent.org/beps/bep_0002.html">http://www.bittorrent.org/beps/bep_0002.html</a></td></tr>
302</tbody>
303</table>
304</div>
305<div class="section" id="copyright">
306<h1>Copyright</h1>
307<p>This document has been placed in the public domain.</p>
308<!-- Local Variables:
309mode: indented-text
310indent-tabs-mode: nil
311sentence-end-double-space: t
312fill-column: 70
313coding: utf-8
314End: -->
315</div>
316
317
318</div>
319        <div id="footer">
320<hr/>
321</div>
322
323</div>
324</body>
325</html>
Note: See TracBrowser for help on using the browser.