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」は、送信者がすべての piece を持っているか、何も持っていないことを示す BitTorrent プロトコルのメッセージタイプです。これらの 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 拡張が無効になっている場合、ノードが 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 をサポートしていない場合、他のクライアントがこのプロトコル拡張をサポートしていても、ダウンロードを加速することはできません。