Fast Extension プロトコル拡張の有効化方法は、BitTorrent ハンドシェイクプロトコル内で特定のバイナリビットを設定する必要があります。BitTorrent ハンドシェイクプロトコルの予約バイト（reserved byte）の第 3 の最下位ビット（third least significant bit）を 1 に設定し、0x04 とビット単位で OR 演算を行うことで Fast Extension を有効にします。例えば：
reserved[7] |= 0x04
接続の両端がこのビットを設定した場合、Fast Extension が有効になり、次の 4 つの拡張機能を使用できます：Have None/Have All、Reject Requests、Suggestions、Allowed Fast。
注意が必要なのは、Fast Extension はこのプロトコル拡張をサポートする 2 つの BitTorrent クライアント間で接続が確立された場合にのみ有効になることです。それ以外の場合、このビットが設定されていても Fast Extension は有効になりません。
BitTorrent プロトコルのメッセージの構文は、すべての整数が 4 バイトのビッグエンディアンであることを指定し、すべてのメッセージは整数のメッセージ長で始まります。さらに、Keep-Alive を除くすべてのメッセージは、1 バイトのオペコードと、オペコードに依存する 0 個以上のパラメータを持つことを指定しています。特定のキーワード（MUST、MUST NOT、REQUIRED、SHALL、SHALL NOT、SHOULD、SHOULD NOT、RECOMMENDED、MAY、OPTIONAL）の解釈は、IETF RFC 2119 に従って行われるべきです。これは、これらの単語が RFC で定義された特定の意味を持ち、特定の行動や行為に対する要求や提案のレベルを示すために使用されることを意味します。例えば、「MUST」は特定の要求に従う必要があることを示し、「SHOULD」は十分な理由がない限り従うべきであることを示します。
既存メッセージの意味の変更#
Fast Extension は、リクエスト（Request）、ブロック（Choke）、アンブロック（Unchoke）、およびリクエストのキャンセル（Cancel）メッセージの意味を変更し、拒否リクエスト（Reject Request）メッセージを追加しました。現在、各リクエストは必ず 1 つの応答を受け取ることが保証されており、それは対応する拒否または対応する piece メッセージです。リクエストがキャンセルされても、キャンセルリクエストを受け取ったノードは、対応する拒否または対応する piece を送信する必要があります：処理中のリクエストは完了することが許可されています。ブロックはもはやすべての保留中のリクエストを暗黙的に拒否することはなく、不要な piece の重複リクエストを引き起こす可能性のある競合条件を排除します。さらに、ノードが未要求の piece を受け取った場合、そのノードは接続を閉じる必要があります。
Have All/Have None#
*Have All*: <len=0x0001> <op=0x0E>
*Have None*: <len=0x0001><op=0x0F>
この 2 つのメッセージは、1 バイトの整数とオペコードを含み、"Have All" のオペコードは 0x0E、"Have None" のオペコードは 0x0F です。これらの 2 つのメッセージが存在する場合、"Have Bitfield" メッセージの代わりになります。ハンドシェイクの後、"Have All"、"Have None"、または "Have Bitfield" のいずれかが必ず 1 つ現れなければなりません。
"Have All" と "Have None" は BitTorrent プロトコルのメッセージタイプであり、送信者がすべての piece を持っているか、まったく持っていないことを示します。これらの 2 つのメッセージが存在する場合、"Have Bitfield" メッセージの代わりになります。ハンドシェイクの後、"Have All"、"Have None"、または "Have Bitfield" のいずれかが必ず 1 つ現れなければなりません。
これらのメッセージの目的は、帯域幅を節約し、piece がない場合にメッセージを送信しない特別な状況を回避することです。Fast Extension が無効になっている場合、ノードが "Have All" または "Have None" メッセージを受け取った場合、そのノードは接続を閉じる必要があります。
提案された Piece#
*Suggest Piece*: <len=0x0005><op=0x0D><index>
"Suggest Piece" は提案メッセージであり、「この piece をダウンロードすることをお勧めします」という意味です。これは、スーパシーディング（super-seeding1）を行う際にスループットを低下させずに、重複ダウンロードを避け、ディスク I/O が制限されたシーダーが連続または同じデータブロックをアップロードできるようにするために使用されます。すべての状況において、シーダーはネットワーク内で各ブロックのほぼ同じ数のコピーを維持するように操作する必要があります。
任意の時点で、ノードは複数の "Suggest Piece" メッセージを送信できます。受信者が複数の "Suggest Piece" メッセージを受け取った場合、それはすべての提案されたブロックが同様にダウンロードに適していることを示すものとして解釈される可能性があります。
Fast Extension が無効になっている場合、ノードが "Suggest Piece" メッセージを受け取った場合、そのノードは接続を閉じる必要があります。
Reject Request 拒否リクエスト#
*Reject Request*: <len=0x000D><op=0x10><index><begin><length>
このメッセージを送信することで、Peer は他の Peer に対して要求されたデータブロックを提供できないことを伝えることができます。受信者はこのメッセージを受け取った後、対応するリクエストをキューから削除し、他の Peer に同じデータブロックを要求しようとします。
Reject Request は、リクエスト元に対して、要求されたデータブロックが満たされないことを通知するために使用されます。
Fast Extension が無効になっている場合、ノードが Reject Request メッセージを受け取った場合、そのノードはリクエスト元との接続を閉じる必要があります。
Fast Extension が有効になっている場合、ノードは Reject Request メッセージを処理する際の規範的な動作は次のとおりです：
- ノードが未送信のリクエストの Reject Request メッセージを受け取った場合、そのノードはそのメッセージを送信したノードとの接続を閉じるべきです。
- ノードが他のノードに Choke メッセージを送信する場合、そのノードが発信したすべてのリクエストを拒否しなければなりません。ただし、これらのリクエストが許可されたファストセットのデータブロックに関連している場合は除きます。ノードは最初に choke し、その後リクエストを拒否する必要があります。これにより、Choke メッセージを受け取ったノードは、choke されたデータブロックを再リクエストしません。
- ノードが choke されたノードからリクエストを受け取った場合、そのリクエストを拒否します。ただし、要求されたデータブロックが許可されたファストセットに含まれている場合は除きます。
- ノードが choke されたノードからのリクエストを過剰に受け取った場合、それらのリクエストを拒否するのではなく接続を閉じることを選択できます。ただし、ノードが choke された場合、バッファが空になるまで数秒かかる可能性があるため、メッセージの伝播が完了するまで考慮する必要があります。このため、接続を閉じる前に慎重に検討する必要があります。
Allowed Fast#
*Allowed Fast*: <len=0x0005><op=0x11><index>
指定された BitTorrent プロトコル において、新しく参加したノードはデータ片が不足しているため、他のノードと有効なファイル共有を行うためにしばらく待つ必要があります。この過程で、ノードは頻繁に choke（アップロードをブロックされる）され、共有効率が低下します。
この問題を解決するために、BitTorrent プロトコルに "Allowed Fast" メッセージが導入されました。このメッセージは、他のノードに対して、自分が choke 状態であっても特定のデータ片を要求でき、即座に応答することを保証します。これにより、他のノードは必要なデータをより早く取得でき、新しく参加したノードも tit-for-tat の交換プロセスにより早く参加できるようになり、ネットワーク全体のファイル共有効率が向上します。
このプロトコルでは、ノードがファイルの一部を所有している場合、それらの piece を他のノードと共有できます。他のノードがこのファイルをダウンロードする必要がある場合、それらはそのノードからこれらの piece を要求し、ファイルのダウンロードをより早く完了させることができます。
"Allowed Fast セット" は、各ノードが要求できる piece の集合を指します。すべてのノード間のデータ要求が公平であることを保証するために、プロトコルでは検証された生成アルゴリズムを使用してこの集合を生成します。このアルゴリズムは、各受信メッセージのノードに対してユニークな piece インデックスを生成し、2 つのノードが k 個の piece を提供する場合、それらが要求できる piece の数も同じになるようにします。もし一方のノードが k+1 個の piece を提供した場合、要求数も 1 つ増加します。k の値は、乱用を避けるために十分小さく、しかし "以牙还牙" の戦略を実現するためには十分大きくする必要があります。著者は現在、k のデフォルト値を 10 に設定していますが、ノードは異なる負荷状況に応じてこの数字を自由に変更できます。
送信者は Allowed Fast メッセージ内に、まだ実際に所有していない pieces を列挙できます。受信者は Allowed Fast メッセージに基づいて、送信者がこれらの pieces を実際に所有していると考えることはできません。これは、ノードが接続開始時に許可されたファストセットを生成および通信できるようにするためです。ただし、送信者はいつでも Allowed Fast メッセージを送信できます。
ノードが十分なリソースを持っている場合、任意の起始ノードに Allowed Fast メッセージを送信して、他のノードのファイルブロックのダウンロード速度を向上させるべきです。ただし、特定の状況では、ノードはすでに Allowed Fast pieces を送信したリクエストを拒否することがあります。例えば、ローカルノードのリソースが不足している場合、要求された pieces がすでにリクエストノードに送信されている場合、またはリクエストノードが起始ノードでない場合です。さらに、現在の実装ルールでは、リクエストノードが k 個以上の pieces をすでにダウンロードしている場合、リクエストが拒否されることが規定されています。
Fast Extension が無効になっている場合、ノードが Allowed Fast メッセージを受け取った場合、そのノードはこのメッセージを処理する能力がないため、送信者との接続を切断する必要があります。このルールの目的は、プロトコルの互換性と正確性を確保し、すべてのノードが同じルールに従って通信できるようにし、ファイルブロックの効率的なダウンロードと転送を実現することです。
Allowed Fast Set メカニズム#
ピアノードのファストリストを計算する標準アルゴリズムでは、すべての整数は 4 バイト（32 ビット）のネットワークバイトオーダー（ビッグエンディアン）です。[a] は a から b までの連続したバイトシーケンスを示し、b は含まれません。つまり、(a, a+1, a+2,…, b-1) です。x [a] は配列 x のインデックス a からインデックス b（b を含まない）の部分列を示します。
ネットワークアドレスを計算する方法です。この場合、「ip」は P’*s の IPv4 アドレスを表します。この方法は現在、IPv6 アドレスをサポートしていません。ピアが NAT の背後にある場合、「ip」は NAT の外部 IP アドレスである必要があります。Allowed Fast メッセージを送信するノードが集合を計算するため、通常正しい「ip」は接続の反対側の「ip」アドレスです。集合を計算するホストは、必要に応じて接続の反対側の「ip」アドレスを使用できます。簡単に言えば、集合を計算する際に、接続の反対側の IP アドレスを計算に使用することができ、自分の IP アドレスである必要はありません。
「sz」はシードファイル内の分片の数を表します。「a」は許可されたファストダウンロードの集合であり、通常のダウンロード順序にないいくつかの分片を含みます。最後に、「k」は許可された方法でダウンロードされる分片の数を表し、許可されたファストダウンロードの集合に含まれる分片の数です。
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)
最初のステップ（1）では、ノード P’*s の IP アドレスの最上位 8 ビットを選択します。これにより、同じネットワーク上のユーザーが複数の Allowed Fast Set を取得するのを防ぎます。3 バイトを使用するのは、経験的および歴史的な理由に基づいています。
3 番目のステップ（3）では、各呼び出しで 20 バイトのランダム数を生成します。前回の反復のハッシュに SHA-1 ハッシュを実行することで、任意の長さの擬似ランダムシーケンスを生成できます。
ステップ（4）から（9）では、20 バイトのハッシュをいくつかのセグメントインデックスに分割し、それを許可されたファスト集合に追加します。簡単に言えば、このプロセスはランダム数を 5 つの 4 バイトのセグメントに分割し、それぞれのセグメントを異なる部分を表すインデックス集合のインデックスとして使用します。インデックスがまだ許可されたファスト集合に追加されていない場合、それを集合に追加します。これにより、特定のインデックスを持つノードのみが「許可されたファスト」ノード集合に選ばれることが保証されます。
例の実装#
以下の C++ 実装は CacheLogic によって提供されています。
void generate_fast_set(
uint32 k, // セット内のピース数
uint32 sz, // トレント内のピース数
const char infohash[20], // トレントの infohash
uint32 ip, // ホストバイトオーダーで、つまり localhost は 0x7f000001
std::
vector<uint32> &a) // 生成されたピースインデックスのセット
{
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)
}
}
}
}
この関数が生成する例の結果：
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
まとめ#
BitTorrent の Fast Extension（略称 FAST）は、ダウンロードを加速するためのプロトコル拡張であり、ファイルダウンロード速度を大幅に向上させることができます。FAST は、マルチスレッドダウンロード、データブロックのプリフェッチ、リクエストの再配置など、ダウンロードプロセスを最適化するためのいくつかの技術手段を利用しています。
具体的には、FAST は複数のデータブロックを要求し、これらのデータブロックが到着する前にそれらを並べ替えて遅延を減少させることで、ダウンロードをより速くします。さらに、FAST はマルチスレッドダウンロード技術を利用し、異なるアップローダーからデータブロックを同時に取得することで、ダウンロード速度をさらに向上させます。
注意が必要なのは、FAST はこのプロトコル拡張をサポートする BitTorrent クライアント間の通信にのみ適用されるため、使用しているクライアントが FAST をサポートしていない場合、他のクライアントがこのプロトコル拡張をサポートしていても、ダウンロードを加速することはできません。