Fast Extension

:Post-History:

The Fast Extension packages several extensions: Have None/Have All,

Reject Requests, Suggestions and Allowed Fast.

These are enabled by setting the third least significant bit of the

last reserved byte in the BitTorrent handshake:

  reserved[7] |= 0x04

The extension is enabled only if both ends of the connection set this bit.

The following proposed messages adhere to the syntax of messages found

in v1.0 of the BitTorrent protocol. All integers are four bytes

big-endian. All messages start with an integer message length. All

messages but the Keep-Alive follow the message length with a single

byte opcode and zero or more opcode-dependant arguments.

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL

NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and

"OPTIONAL" in this document are to be interpreted as described in

IETF RFC 2119.

Modifications to Semantics of Existing Messages

The Fast Extension modifies the semantics of the

Request, Choke, Unchoke, and Cancel

messages, and adds a Reject Request. Now, every request

is guaranteed to result in EXACTLY ONE response

which is either the corresponding reject or corresponding piece

message. Even when a request is cancelled, the peer receiving

the cancel should respond with either the corresponding reject or

the corresponding piece: requests that are being processed are

allowed to complete.

Choke no longer implicitly rejects all pending requests,

thus eliminating some race conditions which could cause pieces

to be needlessly requested multiple times.

Additionally, if a peer receives a piece that was never requested,

the peer MUST close the connection.

Have All/Have None

  *Have All*: <len=0x0001> <op=0x0E>

  *Have None*: <len=0x0001><op=0x0F>

Have All and Have None specify that the message sender

has all or none of the pieces respectively. When present, Have All

or Have None replace the Have Bitfield. Exactly one of Have All,

Have None, or Have Bitfield MUST appear and only immediately after

the handshake. The reason for these messages is to save bandwidth. Also

slightly to remove the idiosyncrasy of sending no message when a peer

has no pieces.

When the fast extension is disabled, if a peer receives Have All or

Have None then the peer MUST close the connection.

Suggest Piece

  *Suggest Piece*: <len=0x0005><op=0x0D><index>

Suggest Piece is an advisory message meaning "you might like to

download this piece." The intended usage is for 'super-seeding'

without throughput reduction, to avoid redundant downloads, and so that

a seed which is disk I/O bound can upload continguous or identical

pieces to avoid excessive disk seeks. In all cases, the seed SHOULD

operate to maintain a roughly equal number of copies of each piece in

the network. A peer MAY send more than one suggest piece message at

any given time. A peer receiving multiple suggest piece messages

MAY interpret this as meaning that all of the suggested pieces

are equally appropriate.

When the fast extension is disabled, if a peer receives a

Suggest Piece message, the peer MUST close the connection.

Reject Request

  *Reject Request*: <len=0x000D><op=0x10><index><begin><length>

Reject Request notifies a requesting peer that its request will not be satisfied.

If the fast extension is disabled and a peer receives a reject

request then the peer MUST close the connection.

When the fast extension is enabled:

If a peer receives a reject for a request that was never sent then

the peer SHOULD close the connection.

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 allowed fast set. A peer SHOULD choke first

and then reject requests so that the peer receiving the choke does not

re-request the pieces.

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

allowed fast set.

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.

Allowed Fast

*Allowed Fast*: <len=0x0005><op=0x11><index>

With the BitTorrent protocol specified in BEP 0003, 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.

Allowed Fast is an advisory message which means "if you ask for this

piece, I'll give it to you even if you're choked." Allowed Fast thus

shortens the awkward stage during which the peer obtains occasional

optimistic unchokes but cannot sufficiently reciprocate to remain

unchoked.

The pieces that can be downloaded when choked constitute a peer's

allowed fast set. The set is generated using a canonical algorithm

that produces piece indices unique to the message receiver so that if

two peers offer k pieces fast it will be the same k, and if one

offers k+1 it will be the same k plus one more. k should be

small enough to avoid abuse, but large enough to ramp up

tit-for-tat. We currently set k to 10, but peers are free to change

this number, e.g., to suit load.

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.

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 k pieces.

When the fast extension is disabled, if a peer recieves an Allowed

Fast message then the peer MUST close the connection.

Allowed Fast Set Generation

The canonical algorithm for computing a peer P's allowed fast set

follows. All integers in this pseudocode are four bytes represented

in network (big-endian) byte order. [a:b] denotes the sequence of

consecutive bytes from a to b excluding b, i.e., *(a, a+1,

a+2,..., b-1). x[a:b]* denotes a subsequence of elements in an array

x starting from index a to but not including index b.

Let ip denote P's IPv4 address. We currently have no

provisions for IPv6. If a peer is behind a Network Address Translator

(NAT) then ip should be the externally facing IP address of the

NAT. Since the node sending the Allowed Fast messages computes

the set, the correct ip is usually the ip address on the other

end of the connection. The host computing the set MAY use the ip

address on the other end of the connection regardless

Let sz denote the number of pieces in the torrent.

Let a denote the allowed fast set.

Let k denote the final number of pieces in the allowed fast set.

 x = 0xFFFFFF00 & ip                           (1)
 x.append(infohash)                            (2)
 while |a| < k:
   x = SHA1(x)                                 (3)
   for i in [0:5] and |a| < k:                 (4)
     j = i*4                                   (5)
     y = x[j:j+4]                              (6)
     index = y % sz                            (7)
     if index not in a:                        (8)
       add index to a                          (9)

Step (1) selects the most significant octets in peer P's

ip address. We do this to prevent a user that obtains more than one

IP address on the same network from obtaining more than one

allowed fast set. Use of three bytes is heuristic and

historical.

Step (3) generates a 20-byte random number on each call. By

performing a SHA-1 hash on the previous iteration's hash, we can

generate an arbitrarily long pseudorandom sequence.

Steps (4) through (9) partition the 20-byte hash into piece indices

and add them to the allowed fast set.

Example Implementation

The following C++ implementation was provided by CacheLogic:

  void generate_fast_set(
    uint32 k,     // number of pieces in set
    uint32 sz,    // number of pieces in torrent
    const char infohash[20], // infohash of torrent
    uint32 ip, // in host byte order, ie localhost is 0x7f000001
    std::
  vector<uint32> &a) // generated set of piece indices
  {
     a.clear();
     std::string x;
     char buf[4];
     *(uint32*)buf = htonl(ip & 0xffffff00);
     x.assign(buf, 4);
     x.append(infohash, 20); // (3)
     while (a.size()<k) {
       x = SHA1(x); // (4)
       for ( int i=0&nbsp;; i<5 && a.size()<k; i++ ) { // (5)
         int j = i*4; // (6)
         uint32 y = ntohl(*(uint32*)(x.data()+j)); // (7)
         uint32 index = y % sz; // (8)
         if (std::find(a.begin(), a.end(), index)==a.end()) { // (9)
           a.push_back(index); // (10)
         }
       }
     }
  }

Example results generated by this function:

 7 piece allowed fast set for torrent with 1313 pieces and hex infohash
 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for node with IP 80.4.4.200:
   1059,431,808,1217,287,376,1188
 9 piece allowed fast set for torrent with 1313 pieces and hex infohash
 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for node with IP 80.4.4.200:
   1059,431,808,1217,287,376,1188,353,508

References

Copyright

This document has been placed in the public domain.

..

Local Variables:

mode: indented-text

indent-tabs-mode: nil

sentence-end-double-space: t

fill-column: 70

coding: utf-8

End: