Changeset 4635 for dotorg/trunk/html/Draft_DHT_protocol.html
- Timestamp:
- 04/19/2007 02:29:22 PM (21 months ago)
- Files:
-
- 1 modified
-
dotorg/trunk/html/Draft_DHT_protocol.html (modified) (12 diffs)
Legend:
- Unmodified
- Added
- Removed
-
dotorg/trunk/html/Draft_DHT_protocol.html
r4460 r4635 1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" 2 1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" 2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> 3 3 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 4 4 <head> … … 19 19 <li><span>For Developers</span></li> 20 20 <!-- <li><a href="./blog">Blog</a></li> --> 21 < !-- <li><a href="./donate.html">Donate!</a></li> -->21 <li><a href="./donate.html">Donate!</a></li> 22 22 </ul> 23 23 </div> … … 25 25 <div id="second"> 26 26 <h1>Fast Extension</h1> 27 <p>The Fast Extension packages several extensions: <i>Have None/Have All</i>, 27 <p>The Fast Extension packages several extensions: <i>Have None/Have All</i>, 28 28 <i>Reject Requests</i>, <i>Suggestions</i> and <i>Allowed Fast.</i> 29 29 These are enabled by setting the third least significant bit of the … … 55 55 </p> 56 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 57 <p>The Fast Extension modifies the semantics of the 58 58 <i>Request</i>, <i>Choke</i>, <i>Unchoke</i>, and <i>Cancel</i> 59 messages, and adds a <i>Reject Request.</i> Now, every request 59 messages, and adds a <i>Reject Request.</i> Now, every request 60 60 is guaranteed to result in EXACTLY ONE response 61 which is either the corresponding reject or corresponding piece 61 which is either the corresponding reject or corresponding piece 62 62 message. Even when a request is cancelled, the peer receiving 63 63 the cancel should respond with either the corresponding reject or 64 64 the corresponding piece: requests that are being processed are 65 65 allowed to complete. 66 </p><p>Choke no longer implicitly rejects all pending requests, 67 thus eliminating some race conditions which could cause pieces 66 </p><p>Choke no longer implicitly rejects all pending requests, 67 thus eliminating some race conditions which could cause pieces 68 68 to be needlessly requested multiple times. 69 </p><p>Additionally, if a peer receives a piece that was never requested, 69 </p><p>Additionally, if a peer receives a piece that was never requested, 70 70 the peer MUST close the connection. 71 71 </p> 72 <h2 id="Have_All.2FHave_None"> Have All/Have None </h2> 72 <h2 id="Have_All.2FHave_None"> Have All/Have None </h2> 73 73 <pre> <i>Have All</i>: <len=0x0001><op=0x0E> 74 74 </pre> … … 78 78 has all or none of the pieces respectively. When present, <i>Have All</i> 79 79 or <i>Have None</i> replace the <i>Have Bitfield.</i> Exactly one of <i>Have All</i>, 80 <i>Have None</i>, or <i>Have Bitfield</i> MUST appear and only immediately after 80 <i>Have None</i>, or <i>Have Bitfield</i> MUST appear and only immediately after 81 81 the handshake. The reason for these messages is to save bandwidth. Also 82 82 slightly to remove the idiosyncrasy of sending no message when a peer 83 83 has no pieces. 84 </p><p>When the fast extension is disabled, if a peer receives <i>Have All</i> or 84 </p><p>When the fast extension is disabled, if a peer receives <i>Have All</i> or 85 85 <i>Have None</i> then the peer MUST close the connection. 86 86 </p> 87 <h2 id="Suggest_Piece"> Suggest Piece </h2> 87 <h2 id="Suggest_Piece"> Suggest Piece </h2> 88 88 <pre> <i>Suggest Piece</i>: <len=0x0005><op=0x0D><index> 89 89 </pre> … … 97 97 any given time. A peer receiving multiple <i>suggest piece</i> messages 98 98 MAY interpret this as meaning that all of the suggested pieces 99 are equally appropriate. 100 </p><p>When the fast extension is disabled, if a peer receives a 99 are equally appropriate. 100 </p><p>When the fast extension is disabled, if a peer receives a 101 101 <i>Suggest Piece</i> message, the peer MUST close the connection. 102 102 </p> … … 106 106 </pre> 107 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 108 </p><p>If the fast extension is disabled and a peer receives a reject 109 109 request then the peer MUST close the connection. 110 110 </p><p>When the fast extension is enabled: … … 126 126 127 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> 128 <p>The canonical algorithm for computing a peer <i>P'</i>s <i>allowed fast set</i> 129 129 follows. All integers in this pseudocode are four bytes represented in network (big-endian) byte order. <i>[a:b]</i> denotes the sequence of consecutive integers from <i>a</i> to <i>b</i> excluding <i>b</i>, i.e., <i>(a, a+1, a+2,..., b-1)</i>. <i>x[a:b]</i> denotes a subsequence of elements in an array <i>x</i> starting from index <i>a</i> to but not including index <i>b</i>. 130 130 </p><p>Let <i>ip</i> denote <i>P'</i>s IPv4 address. We currently have no … … 132 132 (NAT) then <i>ip</i> should be the externally facing IP address of the 133 133 NAT. Since the node sending the <i>Allowed Fast</i> messages computes 134 the set, the correct <i>ip</i> is usually the <i>ip</i> address on the other 135 end of the connection. The host computing the set MAY use the <i>ip</i> 134 the set, the correct <i>ip</i> is usually the <i>ip</i> address on the other 135 end of the connection. The host computing the set MAY use the <i>ip</i> 136 136 address on the other end of the connection regardless 137 137 </p><p>Let <i>sz</i> denote the number of pieces in the torrent. … … 141 141 <pre> x = 0xFFFFFF00 & ip (1) 142 142 x.append(infohash) (2) 143 while |a| < k: 143 while |a| < k: 144 144 x = SHA1(x) (3) 145 145 for i in [0:5] and |a| < k: (4) … … 152 152 <p>Step (1) selects the most significant octets in peer <i>P'</i>s 153 153 ip address. We do this to prevent a user that obtains more than one 154 IP address on the same network from obtaining more than one 154 IP address on the same network from obtaining more than one 155 155 <i>allowed fast set.</i> Use of three bytes is heuristic and 156 historical. 156 historical. 157 157 </p><p>Step (3) generates a 20-byte random number on each call. By 158 158 performing a SHA-1 hash on the previous iteration's hash, we can … … 192 192 <p>Example results generated by this function: 193 193 </p> 194 <pre>7 piece allowed fast set for torrent with 1313 pieces and hex infohash 194 <pre>7 piece allowed fast set for torrent with 1313 pieces and hex infohash 195 195 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for node with IP 80.4.4.200: 196 196 1059,431,808,1217,287,376,1188 197 9 piece allowed fast set for torrent with 1313 pieces and hex infohash 197 9 piece allowed fast set for torrent with 1313 pieces and hex infohash 198 198 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for node with IP 80.4.4.200: 199 199 1059,431,808,1217,287,376,1188,353,508
