Fast Extension is enabled by setting a specific binary bit in the BitTorrent handshake protocol. The third least significant bit of the reserved byte in the BitTorrent handshake protocol is set to 1, which is done by performing a bitwise OR operation with 0x04 to enable Fast Extension. For example:
reserved[7] |= 0x04
If both ends of the connection set this bit, then Fast Extension will be enabled, allowing the use of its four extension features: Have None/Have All, Reject Requests, Suggestions, and Allowed Fast.
It is important to note that Fast Extension only takes effect when a connection is established between two BitTorrent clients that support this protocol extension. Otherwise, even if this bit is set, Fast Extension cannot be enabled.
The syntax for messages in the BitTorrent protocol specifies that all integers are in four-byte big-endian format, and all messages begin with an integer message length. Additionally, it specifies that all messages, except for Keep-Alive, will have a single byte opcode and zero or more parameters depending on the opcode. Certain keywords (such as MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT, SHOULD, SHOULD NOT, RECOMMENDED, MAY, and OPTIONAL) should be interpreted as described in IETF RFC 2119. This means these words have specific meanings defined in the RFC, indicating the level of requirement or recommendation for specific actions or behaviors. For example, "MUST" means a requirement must be followed, while "SHOULD" indicates a recommendation that should be followed unless there is a compelling reason not to.
Modification of Existing Message Semantics#
Fast Extension modifies the semantics of Request, Choke, Unchoke, and Cancel messages and adds a Reject Request message. Now, each request guarantees to receive only one response, either the corresponding rejection or the corresponding piece message. Even if a request is canceled, the node receiving the cancel request should still send the corresponding rejection or piece: ongoing requests are still allowed to complete. Choking no longer implicitly rejects all pending requests, eliminating some race conditions that could lead to unnecessary duplicate requests for pieces. Additionally, if a node receives a piece that was never requested, it must close the connection.
Have All/Have None#
*Have All*: <len=0x0001> <op=0x0E>
*Have None*: <len=0x0001><op=0x0F>
Both messages contain a 1-byte integer and an opcode, where the opcode for "Have All" is 0x0E and for "Have None" is 0x0F. When these two messages are present, they replace the "Have Bitfield" message. After the handshake, exactly one of "Have All," "Have None," or "Have Bitfield" must appear.
"Have All" and "Have None" are message types in the BitTorrent protocol indicating that the sender has either all or none of the pieces. When these two messages are present, they replace the "Have Bitfield" message. After the handshake, exactly one of "Have All," "Have None," or "Have Bitfield" must appear.
The purpose of these messages is to save bandwidth and avoid the special case of not sending any messages when there are no pieces. When Fast Extension is disabled, if a node receives a "Have All" or "Have None" message, it must close the connection.
Suggest Piece#
*Suggest Piece*: <len=0x0005><op=0x0D><index>
"Suggest Piece" is a suggestive message meaning "You might want to download this piece." Its intended use is for super-seeding without reducing throughput to avoid duplicate downloads, allowing disk I/O-constrained seeds to upload contiguous or identical blocks to avoid excessive disk lookups. In all cases, seeds should operate to maintain roughly equal numbers of copies of each block in the network.
At any given time, a node can send multiple "Suggest Piece" messages. If the receiver receives multiple "Suggest Piece" messages, it may interpret them as indicating that all suggested blocks are equally suitable for download.
When Fast Extension is disabled, if a node receives a "Suggest Piece" message, it must close the connection.
Reject Request#
*Reject Request*: <len=0x000D><op=0x10><index><begin><length>
By sending this message, a peer can inform other peers that it cannot provide the requested data block. Upon receiving this message, the receiver will remove the corresponding request from the queue and attempt to request the same data block from other peers.
Reject Request is used to notify the requester that the requested data block cannot be fulfilled.
If Fast Extension is not enabled and a node receives a Reject Request message, that node must close the connection with the requester.
When Fast Extension is enabled, the normative behavior of nodes when processing Reject Request messages is as follows:
- If a node receives a Reject Request message for a request it never sent, it should close the connection with the node that sent the message.
- When a node sends a Choke message to another node, it must reject all requests from that node unless those requests involve pieces in the allowed fast set. The node should choke first and then reject the request, so that the node receiving the Choke message does not re-request the choked pieces.
- If a node receives a request from a choked node, it will reject that request unless the requested piece is in the allowed fast set.
- If a node receives too many requests from a choked node, it may choose to close the connection instead of rejecting those requests. However, it should consider that once a node is choked, the buffer may take several seconds to drain and message propagation to complete. Therefore, careful consideration is needed before deciding to close the connection.
Allowed Fast#
*Allowed Fast*: <len=0x0005><op=0x11><index>
Using the specified BitTorrent protocol, newly joined nodes may need to wait for a period of time to effectively share files with other nodes due to a lack of data pieces. During this process, nodes may continuously be choked, leading to reduced sharing efficiency.
To address this issue, the BitTorrent protocol introduces the "Allowed Fast" message. This message informs other nodes that they can request certain data pieces from it, even if it is in a choked state, and guarantees an immediate response. This way, other nodes can obtain the needed data more quickly, and newly joined nodes can start participating in the tit-for-tat exchange process more rapidly, thereby improving the overall file sharing efficiency of the network.
In this protocol, when a node has a part of a file, it can share these pieces with other nodes. When other nodes need to download this file, they can request these pieces from that node to complete the download more quickly.
The "Allowed Fast set" refers to a collection of pieces that each node is allowed to request. To ensure that data requests among all nodes are fair, a verified generation algorithm is used to generate this set. This algorithm generates a unique piece index for each receiving message node, ensuring that when two nodes provide k pieces, the number of pieces they can request is the same; if one node provides k+1 pieces, the request count will increase by one accordingly. The value of k should be small enough to prevent abuse but large enough to implement a tit-for-tat strategy. The author currently sets the default value of k to 10, but nodes can freely change this number to accommodate different load conditions.
The sender can list pieces it does not yet actually own in the Allowed Fast message, and the receiver cannot assume that the sender actually owns these pieces based on the Allowed Fast message. This is done to allow nodes to generate and communicate the allowed fast set at the start of the connection. However, the sender can send Allowed Fast messages at any time.
A node with sufficient resources should send Allowed Fast messages to any starting node to improve the speed of other nodes downloading file pieces. However, in certain cases, a node may refuse requests for Allowed Fast pieces, such as insufficient local node resources, the requested pieces have already been sent to the requesting node, or the requesting node is not a starting node. Additionally, the current implementation rules specify a situation where requests are denied if the requesting node has already downloaded more than k pieces.
When Fast Extension is disabled, if a node receives an Allowed Fast message, it has no capability to process this message and must disconnect from the sender. This rule is intended to ensure protocol compatibility and correctness, ensuring that all nodes can communicate under the same rules, thereby achieving effective downloading and transmission of file pieces.
Allowed Fast Set Mechanism#
In the standard algorithm for calculating the fast list of peer nodes, all integers are in four-byte (32-bit) network byte order (big-endian). [a] represents a continuous byte sequence from a to b, excluding b, i.e., (a, a+1, a+2,…, b-1). x[a] represents the subsequence of array x starting from index a to index b (but not including b).
The method for calculating network addresses. Here, "ip" represents P’*s IPv4 address. This method currently does not support IPv6 addresses. If the peer is behind NAT, "ip" should be the external IP address of the NAT. Since the node sending the "Allowed Fast" message calculates the set, the correct "ip" is usually the "ip" address of the other end of the connection. The host calculating the set can use the "ip" address of the other end of the connection as needed. In short, this means that when calculating the set, it is possible to choose to use the IP address of the other end of the connection as the IP address in the calculation, rather than necessarily using its own IP address.
Let "sz" represent the number of pieces in the seed file. "a" represents the allowed fast download set, which contains some pieces that are not in the normal download order. Finally, "k" represents the number of pieces allowed to be downloaded quickly, i.e., the number of pieces included in the allowed fast download 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)
In the first step (1), the most significant eight bits of node P’*s IP address are selected. This prevents users on the same network from obtaining multiple Allowed Fast Sets. The use of three bytes is based on empirical and historical reasons.
In the third step (3), a 20-byte random number is generated on each call. By performing a SHA-1 hash on the previous iteration's hash, we can generate a pseudo-random sequence of arbitrary length.
Steps (4) to (9) divide the 20-byte hash into several segment indices and add them to the allowed fast set. In simple terms, this process divides the random number into 5 segments of 4 bytes each, treating each segment as an index in the set representing different parts of the content. If the index has not yet been added to the allowed fast set, it is added to the set. This ensures that only nodes possessing specific indices can be selected into the "allowed fast" node set.
Example Implementation#
The following C++ implementation is 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; 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
Summary#
The Fast Extension of BitTorrent (abbreviated as FAST) is a protocol extension that accelerates downloads and can significantly improve file download speeds. FAST utilizes various techniques to optimize the download process, such as multi-threaded downloading, data block prefetching, and request reordering.
Specifically, FAST speeds up downloads by requesting multiple data blocks and sorting them before they arrive to reduce latency. Additionally, FAST leverages multi-threaded downloading to obtain data blocks simultaneously from different uploaders, further enhancing download speed.
It is important to note that FAST is only applicable for communication between BitTorrent clients that support this protocol extension. Therefore, if the client you are using does not support FAST, even if other clients support this protocol extension, it will not accelerate your downloads.