Changeset 11165

Timestamp:

06/25/09 11:54:14 (9 months ago)

Author:

arvid

Message:

refreshed html

Location:

dotorg/trunk/html/beps

Files:

• bep_0003.html (modified) (5 diffs)
• bep_0029.html (modified) (20 diffs)

dotorg/trunk/html/beps/bep_0003.html

@@ -41 +41 @@
 <tr class="field"><th class="field-name">Version:</th><td class="field-body">11031</td>
 </tr>
-<tr class="field"><th class="field-name">Last-Modified:</th><td class="field-body"><a class="reference external" href="http://bittorrent.org/trac/browser/dotorg/trunk/html/beps/bep_0003.rst">2008-02-28 16:43:58 -0800 (Thu, 28 Feb 2008)</a></td>
+<tr class="field"><th class="field-name">Last-Modified:</th><td class="field-body"><a class="reference" href="http://bittorrent.org/trac/browser/dotorg/trunk/html/beps/bep_0003.rst">2008-02-28 16:43:58 -0800 (Thu, 28 Feb 2008)</a></td>
 </tr>
 <tr class="field"><th class="field-name">Author:</th><td class="field-body">Bram Cohen &lt;bram&#32;&#97;t&#32;bittorrent.com&gt;</td>
@@ -51 +51 @@
 <tr class="field"><th class="field-name">Created:</th><td class="field-body">10-Jan-2008</td>
 </tr>
-<tr class="field"><th class="field-name">Post-History:</th><td class="field-body"></td>
+<tr class="field"><th class="field-name">Post-History:</th><td class="field-body">24-Jun-2009, clarified the encoding of strings in torrent files</td>
 </tr>
 </tbody>
@@ -59 +59 @@
 <p class="topic-title first">Contents</p>
 <ul class="simple">
-<li><a class="reference internal" href="#a-bittorrent-file-distribution-consists-of-these-entities" id="id2">A BitTorrent file distribution consists of these entities:</a></li>
-<li><a class="reference internal" href="#to-start-serving-a-host-goes-through-the-following-steps" id="id3">To start serving, a host goes through the following steps:</a></li>
-<li><a class="reference internal" href="#to-start-downloading-a-user-does-the-following" id="id4">To start downloading, a user does the following:</a></li>
-<li><a class="reference internal" href="#the-connectivity-is-as-follows" id="id5">The connectivity is as follows:</a></li>
-<li><a class="reference internal" href="#metainfo-files-are-bencoded-dictionaries-with-the-following-keys" id="id6">Metainfo files are bencoded dictionaries with the following keys:</a></li>
-<li><a class="reference internal" href="#tracker-get-requests-have-the-following-keys" id="id7">Tracker GET requests have the following keys:</a></li>
-<li><a class="reference internal" href="#all-non-keepalive-messages-start-with-a-single-byte-which-gives-their-type" id="id8">All non-keepalive messages start with a single byte which gives their type.</a></li>
-<li><a class="reference internal" href="#the-possible-values-are" id="id9">The possible values are:</a></li>
-<li><a class="reference internal" href="#copyright" id="id10">Copyright</a></li>
+<li><a class="reference" href="#a-bittorrent-file-distribution-consists-of-these-entities" id="id2">A BitTorrent file distribution consists of these entities:</a></li>
+<li><a class="reference" href="#to-start-serving-a-host-goes-through-the-following-steps" id="id3">To start serving, a host goes through the following steps:</a></li>
+<li><a class="reference" href="#to-start-downloading-a-user-does-the-following" id="id4">To start downloading, a user does the following:</a></li>
+<li><a class="reference" href="#the-connectivity-is-as-follows" id="id5">The connectivity is as follows:</a></li>
+<li><a class="reference" href="#metainfo-files-are-bencoded-dictionaries-with-the-following-keys" id="id6">Metainfo files are bencoded dictionaries with the following keys:</a></li>
+<li><a class="reference" href="#tracker-get-requests-have-the-following-keys" id="id7">Tracker GET requests have the following keys:</a></li>
+<li><a class="reference" href="#all-non-keepalive-messages-start-with-a-single-byte-which-gives-their-type" id="id8">All non-keepalive messages start with a single byte which gives their type.</a></li>
+<li><a class="reference" href="#the-possible-values-are" id="id9">The possible values are:</a></li>
+<li><a class="reference" href="#copyright" id="id10">Copyright</a></li>
 </ul>
 </div>
@@ -139 +139 @@
 <dt>info</dt>
 <dd><p class="first">This maps to a dictionary, with keys described below.</p>
-<p>The <tt class="docutils literal"><span class="pre">name</span></tt> key maps to a string which is the suggested name
-to save the file (or directory) as. It is purely advisory.</p>
+<p>The <tt class="docutils literal"><span class="pre">name</span></tt> key maps to a UTF-8 encoded string which is the
+suggested name to save the file (or directory) as. It is purely advisory.</p>
 <p><tt class="docutils literal"><span class="pre">piece</span> <span class="pre">length</span></tt> maps to the number of bytes in each piece
 the file is split into. For the purposes of transfer, files are
@@ -163 +163 @@
 the following keys:</p>
 <p><tt class="docutils literal"><span class="pre">length</span></tt> - The length of the file, in bytes.</p>
-<p><tt class="docutils literal"><span class="pre">path</span></tt> - A list of strings corresponding to subdirectory
+<p><tt class="docutils literal"><span class="pre">path</span></tt> - A list of UTF-8 encoded strings corresponding to subdirectory
 names, the last of which is the actual file name (a zero length list
 is an error case).</p>
-<p class="last">In the single file case, the name key is the name of a file, in the
+<p>In the single file case, the name key is the name of a file, in the
 muliple file case, it's the name of a directory.</p>
+<p class="last">All strings in a .torrent file that contains text must be UTF-8
+encoded.</p>
 </dd>
 </dl>

dotorg/trunk/html/beps/bep_0029.html

@@ -39 +39 @@
 <tr class="field"><th class="field-name">Title:</th><td class="field-body">uTorrent transport protocol</td>
 </tr>
-<tr class="field"><th class="field-name">Version:</th><td class="field-body">11159</td>
-</tr>
-<tr class="field"><th class="field-name">Last-Modified:</th><td class="field-body"><a class="reference" href="http://bittorrent.org/trac/browser/dotorg/trunk/html/beps/bep_0029.rst">2009-06-23 13:45:47 -0700 (Tue, 23 Jun 2009)</a></td>
+<tr class="field"><th class="field-name">Version:</th><td class="field-body">11164</td>
+</tr>
+<tr class="field"><th class="field-name">Last-Modified:</th><td class="field-body"><a class="reference" href="http://bittorrent.org/trac/browser/dotorg/trunk/html/beps/bep_0029.rst">2009-06-25 11:53:53 -0700 (Thu, 25 Jun 2009)</a></td>
 </tr>
 <tr class="field"><th class="field-name">Author:</th><td class="field-body">Arvid Norberg &lt;arvid&#32;&#97;t&#32;bittorrent.com&gt;</td>
@@ -68 +68 @@
 <li><a class="reference" href="#version" id="id7">version</a></li>
 <li><a class="reference" href="#connection-id" id="id8">connection_id</a></li>
-<li><a class="reference" href="#timestamp-seconds-timestamp-microseconds" id="id9">timestamp_seconds, timestamp_microseconds</a></li>
+<li><a class="reference" href="#timestamp-microseconds" id="id9">timestamp_microseconds</a></li>
 <li><a class="reference" href="#timestamp-difference-microseconds" id="id10">timestamp_difference_microseconds</a></li>
 <li><a class="reference" href="#wnd-size" id="id11">wnd_size</a></li>
@@ -111 +111 @@
 <p>The fact that BitTorrent uses multiple TCP connections gives it an
 unfair advantage when competing with other services for bandwidth,
-which exaggerates the effect of BitTorrent filling the upload pipe.</p>
+which exaggerates the effect of BitTorrent filling the upload pipe.
+The reason for this is because TCP distributes the available bandwidth
+evenly across connections, and the more connections one application
+uses, the larger share of the bandwidth it gets.</p>
 <p>The traditional solution to this problem is to cap the upload rate
-of the bittorrent client to 80% of the uplink capacity. 80% leaves
+of the BitTorrent client to 80% of the up-link capacity. 80% leaves
 some head room for interactive traffic.</p>
 <p>The main drawbacks with this solution are:</p>
 <ol class="arabic simple">
-<li>The user needs to configure his/her bittorrent client, it won't
+<li>The user needs to configure his/her BitTorrent client, it won't
 work out-of-the-box.</li>
 <li>The user needs to know his/her internet connection's upload
@@ -123 +126 @@
 may connect to a large number of different networks.</li>
 <li>The headroom of 20% is arbitrary and wastes bandwidth. Whenever
-there is no interactive traffic competing with bittorrent, the
+there is no interactive traffic competing with BitTorrent, the
 extra 20% are wasted. Whenever there is competing interactive
 traffic, it cannot use more than 20% of the capacity.</li>
@@ -137 +140 @@
 <p>This document assumes some knowledge of how TCP and window based
 congestion control works.</p>
-<p>The main addition compared to TCP is the delay based congestion
+<p>uTP is a transport protocol layered on top of UDP. As such, it must
+(and has the ability to) implement its own congestion control.</p>
+<p>The main difference compared to TCP is the delay based congestion
 control. See the <a class="reference" href="#congestion-control">congestion control</a> section.</p>
 <p>Like TCP, uTP uses window based congestion control. Each socket
@@ -186 +191 @@
 <div class="section" id="version">
 <h3>version</h3>
-<p>This is the protcol version. The current version is 1.</p>
+<p>This is the protocol version. The current version is 1.</p>
 </div>
 <div class="section" id="connection-id">
@@ -195 +200 @@
 connection decides which ID to use, and the return path has the same ID + 1.</p>
 </div>
-<div class="section" id="timestamp-seconds-timestamp-microseconds">
-<h3>timestamp_seconds, timestamp_microseconds</h3>
-<p>This is the 'seconds' and 'microseconds' parts of the timestamp of when this
-packet was sent. This is set using gettimeofday() on posix and QueryPerformanceTimer()
-on windows. The higher resultion this timstamp has, the better.</p>
+<div class="section" id="timestamp-microseconds">
+<h3>timestamp_microseconds</h3>
+<p>This is the 'microseconds' parts of the timestamp of when this packet was sent.
+This is set using gettimeofday() on posix and QueryPerformanceTimer()
+on windows. The higher resolution this timestamp has, the better. The closer
+to the actual transmit time it is set, the better.</p>
 </div>
 <div class="section" id="timestamp-difference-microseconds">
@@ -238 +244 @@
 <div class="section" id="selective-ack">
 <h4>Selective ACK</h4>
-<p>Selective ack is an extension that can selectively ACK packets non-sequentially.
-Its payload is a bitmask of 32 bits, representing the first 32 packets in the
-send window. A set bit specifies that packet has been received, a cleared bit
+<p>Selective ACK is an extension that can selectively ACK packets non-sequentially.
+Its payload is a bitmask of at least 32 bits, in multiples of 32 bits. Each bit
+represents one packet in the send window. Bits that are outside of the send window
+are ignored. A set bit specifies that packet has been received, a cleared bit
 specifies that the packet has not been received. The header looks like this:</p>
 <pre class="literal-block">
@@ -250 +257 @@
 +---------------+---------------+
 </pre>
-<p>The selective ack is only sent when at least one sequence number was skipped in
+<p>Note that the len field of extensions refer to bytes, which in this extension
+must be at least 4, and in multiples of 4.</p>
+<p>The selective ACK is only sent when at least one sequence number was skipped in
 the received stream. The first bit in the mask therefore represents ack_nr + 2.
-ack_nr +1 is assumed to have been dropped or be missing when this packet was sent.
+ack_nr + 1 is assumed to have been dropped or be missing when this packet was sent.
 A set bit represents a packet that has been received, a cleared bit represents
 a packet that has not yet been received.</p>
-<p>The bitmask has reverse byteorder. The first byte represents packets [ack_nr + 2,
+<p>The bitmask has reverse byte order. The first byte represents packets [ack_nr + 2,
 ack_nr + 2 + 7] in reverse order. The least significant bit in the byte represents
 ack_nr + 2, the most significant bit in the byte represents ack_nr + 2 + 7. The
 next byte in the mask represents [ack_nr + 2 + 8, ack_nr + 2 + 15] in reverse order,
 and so on. The bitmask is not limited to 32 bits but can be of any size.</p>
+<p>Here is the layout of a bitmask representing the first 32 packet acks
+represented in a selective ACK bitfield:</p>
+<pre class="literal-block">
+0               8               16
++---------------+---------------+---------------+---------------+
+| 9 8 ...   3 2 | 17   ...   10 | 25   ...   18 | 33   ...   26 |
++---------------+---------------+---------------+---------------+
+</pre>
+<p>The number in the diagram maps the bit in the bitmask to the offset to add to
+<tt class="docutils literal"><span class="pre">ack_nr</span></tt> in order to calculate the sequence number that the bit is ACKing.</p>
 </div>
 <div class="section" id="extension-bits">
@@ -295 +314 @@
 the ST_FIN packet.</dd>
 <dt>ST_STATE = 2</dt>
-<dd>State packet. Used to transmit an ACK with no data.</dd>
+<dd>State packet. Used to transmit an ACK with no data. Packets that don't
+include any payload do not increase the <tt class="docutils literal"><span class="pre">seq_nr</span></tt>.</dd>
 <dt>ST_RESET = 3</dt>
 <dd>Terminate connection forcefully. Similar to TCP RST flag. The remote
@@ -304 +324 @@
 The sequence number is initialized to 1. The connection ID is initialized
 to a random number. The syn packet is special, all subsequent packets sent
-on this connection (except for resends of the ST_SYN) are sent with the
+on this connection (except for re-sends of the ST_SYN) are sent with the
 connection ID + 1. The connection ID is what the other end is expected to
 use in its responses.</p>
@@ -310 +330 @@
 ID in the packet header. The send ID for the socket should be initialized
 to the ID + 1. The sequence number for the return channel is initialized
-to a random number. The other end expects an ST_STATE packet (only an ack)
+to a random number. The other end expects an ST_STATE packet (only an ACK)
 in response.</p>
 </dd>
@@ -329 +349 @@
 <div class="section" id="connection-setup">
 <h2>connection setup</h2>
-<p><em>describe the initial connection setup sequence</em></p>
+<p>Here is a diagram illustrating the exchanges and states to initiate
+a connection. The c.* refers to a state in the socket itself, pkt.*
+refers to a field in the packet header.</p>
+<pre class="literal-block">
+initiating endpoint                           accepting endpoint
+
+          | c.state = CS_SYN_SENT                         |
+          | c.seq_nr = 1                                  |
+          | c.conn_id_recv = rand()                       |
+          | c.conn_id_send = c.conn_id_recv + 1           |
+          |                                               |
+          |                                               |
+          | ST_SYN                                        |
+          |   seq_nr=c.seq_nr++                           |
+          |   ack_nr=*                                    |
+          |   conn_id=c.rcv_conn_id                       |
+          | &gt;-------------------------------------------&gt; |
+          |             c.receive_conn_id = pkt.conn_id+1 |
+          |             c.send_conn_id = pkt.conn_id      |
+          |             c.seq_nr = rand()                 |
+          |             c.ack_nr = pkt.seq_nr             |
+          |             c.state = CS_CONNECTED            |
+          |                                               |
+          |                                               |
+          |                                               |
+          |                                               |
+          |                     ST_STATE                  |
+          |                       seq_nr=c.seq_nr++       |
+          |                       ack_nr=c.ack_nr         |
+          |                       conn_id=c.send_conn_id  |
+          | &lt;------------------------------------------&lt;  |
+          | c.state = CS_CONNECTED                        |
+          | c.ack_nr = pkt.seq_nr                         |
+          |                                               |
+          |                                               | connection established
+     .. ..|.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..|.. ..
+          |                                               |
+          |                                               |
+          | ST_DATA                                       |
+          |   seq_nr=c.seq_nr++                           |
+          |   ack_nr=c.ack_nr                             |
+          |   conn_id=c.conn_id_send                      |
+          | &gt;-------------------------------------------&gt; |
+          |                         c.ack_nr = pkt.seq_nr |
+          |                                               |
+          |                                               |
+          |                                               |
+          |                     ST_DATA                   |
+          |                       seq_nr=c.seq_nr++       |
+          |                       ack_nr=c.ack_nr         |
+          |                       conn_id=c.send_conn_id  |
+          | &lt;------------------------------------------&lt;  |
+          | c.ack_nr = pkt.seq_nr                         |
+          |                                               |
+          |                                               |
+          V                                               V
+</pre>
+<p>Connections are identified by their <tt class="docutils literal"><span class="pre">conn_id</span></tt> header. If the connection ID of a new
+connection collides with an existing connection, the connection attempt will fails, since
+the ST_SYN packet will be unexpected in the existing stream, and ignored.</p>
 </div>
 <div class="section" id="packet-loss">
@@ -335 +414 @@
 <p>If the packet with sequence number (<tt class="docutils literal"><span class="pre">seq_nr</span></tt> - <tt class="docutils literal"><span class="pre">cur_window</span></tt>) has not been acked
 (this is the oldest packet in the send buffer, and the next one expected to be acked)
-has not been acked, but 3 or more packets have been acked passed it (through Selective
+has not been acked, but 3 or more packets have been acked past it (through Selective
 ACK), the packet is assumed to have been lost. Similarly, when receiving 3 duplicate
 acks, <tt class="docutils literal"><span class="pre">ack_nr</span></tt> + 1 is assumed to have been lost (if a packet with that sequence number
 has been sent).</p>
-<p>When a packet is lost, the <tt class="docutils literal"><span class="pre">max_window</span></tt> is multiplied by 0.78.</p>
+<p>When a packet is lost, the <tt class="docutils literal"><span class="pre">max_window</span></tt> is multiplied by 0.78. TCP multiplies by
+0.5, but since this is a much less likely event in uTP, and since the uTP ramp-up
+is slower than TCP, this is a reasonable optimization.</p>
 </div>
 <div class="section" id="timeouts">
@@ -348 +429 @@
 last_ack_nr here is the last ack_nr received on the socket before the current packet,
 and ack_nr is the field in the currently received packet.</p>
-<p>The <tt class="docutils literal"><span class="pre">rtt</span></tt> and <tt class="docutils literal"><span class="pre">rtt_var</span></tt> is only updated for packets that where sent only once.
+<p>The <tt class="docutils literal"><span class="pre">rtt</span></tt> and <tt class="docutils literal"><span class="pre">rtt_var</span></tt> is only updated for packets that were sent only once.
 This avoids problems with figuring out which packet was acked, the first or the
 second one.</p>
@@ -372 +453 @@
 goes down to zero.</p>
 <p>The initial timeout is set to 1000 milliseconds, and later updated according to
-the formula above. For each packet that times out in a row, the timeout is
-doubled.</p>
+the formula above. For every packet consecutive subsequent packet that times out,
+the timeout is doubled.</p>
 </div>
 <div class="section" id="packet-sizes">
@@ -379 +460 @@
 <p>In order to have as little impact as possible on slow congested links, uTP adjusts
 its packet size down to as small as 150 bytes per packet. Using packets that small
-has the benefit of not clogging up a slow uplink, with long serialization delay.
+has the benefit of not clogging a slow up-link, with long serialization delay.
 The cost of using packets that small is that the overhead from the packet headers
 become significant. At high rates, large packet sizes are used, at slow rates,
@@ -388 +469 @@
 <p>The overall goal of the uTP congestion control is to use one way buffer delay as the
 main congestion measurement, as well as packet loss, like TCP. The point is to avoid
-running at full send buffers whenever data is being sent. This is specifically a
+running with full send buffers whenever data is being sent. This is specifically a
 problem for DSL/Cable modems, where the send buffer in the modem often has room for
 multiple seconds worth of data. The ideal buffer utilization for uTP (or any background
@@ -401 +482 @@
 original sender of the packet (timestamp_difference_microseconds). This value is not meaningful
 as an absolute value. The clocks in the machines are most likely not synchronized,
-especially not down to micorsecond resolution, and the time the packet is in transit is
+especially not down to microsecond resolution, and the time the packet is in transit is
 also included in the difference of these timestamps. However, the value is useful in
 comparison to previous values.</p>
 <p>Each socket keeps a sliding minimum of the lowest value for the last two minutes. This value
-is called <em>base_delay</em>, and is used as a baseline, the minumum delay between the hosts.
+is called <em>base_delay</em>, and is used as a baseline, the minimum delay between the hosts.
 When subtracting the base_delay from the timestamp difference in each packet you get a
 measurement of the current buffering delay on the socket. This measurement is called <em>our_delay</em>.
 It has a lot of noise it it, but is used as the driver to determine whether to increase or
 decrease the send window (which controls the send rate).</p>
-<p>The <em>CCONTROL_TARGET</em> is the buffering delay that the uTP accepts on the uplink. Currently the
+<p>The <em>CCONTROL_TARGET</em> is the buffering delay that the uTP accepts on the up-link. Currently the
 delay target is set to 100 ms. <em>off_target</em> is how far the actual measured delay is from the
 target delay (calculated from CCONTROL_TARGET - our_delay).</p>
@@ -418 +499 @@
 <tt class="docutils literal"><span class="pre">max_window</span></tt>. Its size is controlled, roughly, by the following expression:</p>
 <pre class="literal-block">
-scaled_gain = (off_target / CCONTROL_TARGET)
-        * (outstanding_packet * MAX_CWND_INCREASE_PACKETS_PER_RTT / max_window);
+delay_factor = off_target / CCONTROL_TARGET;
+window_factor = outstanding_packet / max_window;
+scaled_gain = MAX_CWND_INCREASE_PACKETS_PER_RTT * delay_factor * window_factor;
 </pre>
 <p>Where the first factor scales the <em>off_target</em> to units of target delays.</p>