WebSeed – HTTP/FTP に基づく BitTorrent 技術

概要#

ダウンロード中に HTTP または FTP サーバーを使用してノードに追加データを送信することで、ダウンロード速度を向上させ、BitTorrent ダウンロードで発生する可能性のあるダウンロードの停滞を減少させます。

原理#

多くの BitTorrent ダウンロードリンクを提供するウェブサイトは、同じファイルの HTTP または FTP URL も提供しています。これらの URL が指すファイルは完全に同一です。WebSeeding 技術を利用した BitTorrent クライアントは、任意のソース（つまり BitTorrent と HTTP または FTP）からファイルをダウンロードし、ダウンロードしたデータブロックを組み立てて完全なファイルを作成します。HTTP または FTP サーバーは、常に制限なしでファイルのデータブロックを提供できる「シード」として機能し、ファイルのダウンロードを加速します。

利点#

各 BitTorrent ダウンロードには、オープンなダウンロードポートを持つソース、つまりシードがあり、誰でもこれらのソースからダウンロードを開始できます。

メタデータ追加を認識できないクライアントに対して、この新しい方法は何も破壊したり変更したりしません。

HTTP/FTP シードをサポートしていない BitTorrent クライアントでも、他の HTTP/FTP をサポートするピアを介してデータブロックを共有できます。

メタデータを変更する必要はありません。ダウンロード管理ツールは通常、1 つのファイルに複数の HTTP/FTP ミラー URL を追加でき、ユーザーはウェブページ上の複数のリンクをクリックして同じファイル名を識別するだけで済みます。

皆さんは HTTP/FTP サーバーとそのプロトコルに非常に精通しています。

この新しい方法は、IMFile、GetRight、Mainline、uTorrent、Azureus、libTorrent など、複数の BitTorrent クライアントに実装されています。

BitTorrent クライアントで少しの変更を行うだけで、Tracker、HTTP、または FTP サーバーを変更する必要はありません。HTTP または FTP サーバー上でスクリプトを使用する必要もありません。

多くの一般的なクライアントがこの機能をサポートしているため（特に IMFile クライアント）、企業や個人の既存の HTTP/FTP サーバーを使用して BitTorrent ダウンロードのシードを公開することが完全に可能です。

メタデータ拡張#

BitTorrent メタデータファイルの主要な領域には、「info」部分の一部ではなく、新しいキー「url-list」が追加されます。このキーは、1 つ以上の URL アドレスのリストを参照し、シードデータを取得できる URL のリストを含みます。クライアントがこのキーを使用できない場合は、安全に無視できます。
例：

d 8:announce27:http:tracker.com/announce
      8:url-list26:http:mirror.com/file.exe
      4:info…

「url-list」URL がスラッシュ「/」で終わる場合、クライアントはシードファイル名を追加して完全な URL を生成する必要があります。これにより、.torrent ジェネレーターはこのフィールドを単一ファイルと複数ファイルのシードと同等に扱います。

複数ファイルシード#

複数ファイルシードをダウンロードする際、BitTorrent クライアントは通常、シードファイルの「info」部分の「name」フィールドをルートディレクトリとして使用し、「path/file」フィールドを使用してそのルートディレクトリ内のファイルパスと名前を指定します。しかし、この例では、シードファイルの「url-list」フィールドがルートディレクトリとして使用されるため、クライアントは「name」と「path/file」をそのルートディレクトリに追加して、要求された URL を作成する必要があります。
例えば、

... 8:url-list22:http://mirror.com/pub/ 4:infod5:filesld6:lengthi949e4:pathl10:Readme.txte e4:name7:michael

この例では、クライアントは「name」を「michael」に設定し、「path/file」の「Readme.txt」ファイルをhttp://mirror.com/pub/ ルートディレクトリに追加して、ダウンロード要求の URL を生成します。クライアントは、上記の手順で生成されたルートディレクトリ、ファイルパス、ファイル名を使用して、それらを結合し、完全なダウンロード要求 URL を生成します：http://mirror.com/pub/michael/Readme.txt 。

クライアント実装の概要#

まず、クライアントは認識できないプロトコルを無視する必要があります。なぜなら、そのようなプロトコルに接続しようとするとエラーが発生する可能性があるからです。例えば、あるクライアントは HTTP のみをサポートし、FTP をサポートしない場合や、その逆もあります。

次に、HTTP と FTP プロトコルはストリーミングプロトコルであり、BitTorrent におけるデータブロックの概念はありません。これは、HTTP または FTP を使用してダウンロードする際に、多くのデータの空隙が発生することを意味します。なぜなら、BitTorrent のようにファイルをブロック単位でダウンロードできないからです。

この問題を解決するために、実装内の「最も希少な優先」ブロック選択方法が修正され、ダウンロードされたファイルにより多くのデータの空隙が存在するようになり、HTTP および FTP スレッドはこれらの空隙からダウンロードを開始し、全体の空隙を埋めることができます。HTTP のバイト範囲リクエスト機能を使用して単一のブロックをリクエストできますが、これはサーバーに記録され、DoS 攻撃と誤解される可能性があります。

クライアント実装の注意事項#

HTTP および FTP 接続がファイル内の多くの連続ブロックをよりよく埋めるために、BitTorrent の標準アルゴリズムにいくつかの変更が加えられました。

空隙の定義#

空隙とは、クライアントが持っていない複数の隣接ブロックで構成されるスペースを指します。この例では、ビットフィールド「YYnnnnYnnY」があると仮定し、Y はクライアントが持っているブロック、n はクライアントが持っていないブロックを表します。したがって、このビットフィールドには、長さ 4 と長さ 2 の隣接未ダウンロードブロックで構成される 2 つの空隙があります。

ダウンロードブロックの選択#

最も重要な変更は、ダウンロードブロックの選択です。すべての欠落ブロックの希少度が類似している場合、ブロックをリクエストする際には、長さ 2 の空隙から 1 つのブロックを選択してダウンロードを開始するのが最善です。そして、任意の空隙では、最後から埋めるのが最善です（つまり、最高番号のブロックを優先的に選択します）。したがって、与えられたビットフィールド「YYnnnnYnnY」において、欠落ブロックの希少度が類似している場合、最適な選択は「# pieces YYnnnnY##Y」の中の 1 つのブロックを選択することです。その中で最適な選択はブロック「$ YYnnnnYn$Y」です。

これらのブロック選択戦略は、HTTP/FTP 接続の連続データダウンロードを最大限に活用できます。これにより、HTTP/FTP 接続は空隙の先頭からダウンロードを開始し、クライアントがすでに持っているブロックに接続する前にできるだけ多くのデータをダウンロードできます。

ブロック選択戦略の変更#

ダウンロードブロック選択戦略を元の「最も希少なものを優先的に選択する」から「完了したブロックから最も遠く、相対的に希少なものを優先的に選択する」に変更します。

最も希少で最大の間隔のブロック#

まず、現在のすべての未ダウンロードブロックの中で出現頻度が最も少ないブロック、すなわち PRWBG（Pretty Rare With Biggest Gap - 最も希少で最大の間隔のブロック）を見つけます。これが、すでにダウンロードされた別のブロックとの距離 D であると仮定します。

他の未ダウンロードブロックが、ダウンロード済みブロックとの距離が D より小さい場合、それらは PRWBG よりも希少であると見なされ、「希少 - X」とマークされます（ここで X は「ピアの数から 1 を引いた平方根」と等しい定数です）。

逆に、ある未ダウンロードブロックがダウンロード済みブロックとの距離が D より大きい場合、それは PRWBG よりも入手しやすい可能性があると見なされ、「希少 + X」とマークされ、次のダウンロードブロックとして選択される可能性があります。

現在の最も希少なブロックが 3 つのノードにしか存在しない場合、通常のアルゴリズムは他の 2 つのノードにもあるブロックを選択します。しかし、修正されたアルゴリズムを使用すると、ブロックが完全なファイルとの距離が現在の最も希少なブロックの間隔より小さい場合、1 つのノードがこのブロックを持っているだけで選択できます。

間隔が大きく、そのブロックの「希少度」が通常の「希少 - 1」と同じであれば、そのブロックを選択します（したがって、間隔が大きい場合、2 または 3 つのノードが持っているブロックが選択されます）。

したがって、与えられた「YYnnn1Yn2Y」の状況では、1 が 2 よりも希少でない限り、2 を選択するのが最善です。
擬似コードのロジック：

X = sqrt(Peers) - 1;
      Gap = 0;
      CurGap = 0;
      CurRarest = MaxPieces+1;
      for (i=0; i<MaxPieces; i++) {
          if (IDoNotHavePiece(i)) {
              Gap++;
              if (PeerHasPiece(i)) {
                  PieceRareness = NumberOfPeersWithThePiece();
                  if (PieceRareness<(CurRarest-X) ||
                      (PieceRareness<=(CurRarest+X) && Gap>CurGap)) {
                      CurRarest = PieceRareness;
                      CurGap = Gap;
                      NextPiece = i;
                  }
              }
          } else {
              Gap = 0;
          }
      }

空隙を埋める#

ファイルが 50％以上完了した場合、異なる方法でランダムにダウンロードブロックを選択します。（50％以上の場合、他のノードがダウンロードしたいブロックが大量にあるはずです。）

数ブロックごとに、完全なファイルに最も近いブロックを選択し、すべての希少度を無視します。例えば、ビットフィールド「YYnnnnYnnY」では、ブロック「#YYnnnnYn#Y」を選択します。これは小さな隙間を埋めるのに役立ちます。

クライアントはこのステップを実行するかどうかを選択できます。この機能を実装する場合、別のファイルの完了パーセンテージを使用することもできます。

擬似コードのロジック：

Gap = 0;
      Piece = -1;
      CurGap = MaxPieces+1;
      for (i=0; i<MaxPieces; i++) {
          if (IDoNotHavePiece(i)) {
              Gap++;
              if (PeerHasPiece(i)) {
                  Piece = i;
              }
          } else {----
              if (Gap<CurGap && Gap>0 && Piece!=-1) {
                  CurGap = Gap;
                  NextPiece = Piece;
              }
              Gap = 0;
              Piece = -1;
          }
      }

HTTP および FTP の最適化#

HTTP/FTP プロトコルやサーバー自体を変更する必要はありません。

クライアントが HTTP/FTP ダウンロードが BitTorrent ダウンロードの一部であることを知っている場合、最初の接続時にファイル内の任意の位置からダウンロードを開始するのが最善です。これにより、最初に取得した HTTP データブロックが BitTorrent ノードと共有される可能性が高くなります。

HTTP/FTP 接続を開始する際にすでに進行中の BitTorrent ダウンロードがある場合、HTTP/FTP は最大の空隙の先頭から開始する必要があります。ビットフィールド「YYnnnnYnnY」では、# から開始する必要があります：「YY＃nnnYnnY」。

HTTP/FTP サーバーからデータブロックを正常にダウンロードしたが、SHA チェックサムが一致しない場合、接続を閉じてその URL を破棄する必要があります。

クライアントが「ビジー」という応答を受け取った場合、HTTP または FTP サーバーの URL を放棄する必要はありません。

複数ファイルシード#

HTTP/FTP サーバーを使用して複数ファイルシードをダウンロードする場合、ダウンロード効率を最適化するために追加の選択アルゴリズムが必要です。

大きなファイルの場合、クライアントは BitTorrent ブロックを選択してダウンロード速度を最適化し、HTTP/FTP サーバーからファイル全体を完全にダウンロードできるようにします。

小さなファイルを含むシードの場合、1 つのブロックのダウンロードを完了するために複数の HTTP/FTP 転送が必要になる可能性があります。この場合、BitTorrent を使用して転送する方が適切かもしれません。例えば、100 個の 1KB ファイルがある場合、ブロックサイズが 32KB だと仮定すると、ファイルのダウンロードを完了するために 100 回の HTTP/FTP 転送が必要ですが、4 回の BitTorrent ブロックリクエストで済みます。

したがって、小さなファイルには BitTorrent ブロック選択を優先し、大きなファイルには HTTP/FTP を優先することで、ダウンロード効率を効果的に向上させることができます。

別の可能なクライアント実装#

クライアントが HTTP のみをサポートし、FTP をサポートしない場合、HTTP のバイト範囲リクエスト機能を利用できますが、毎回複数のブロックをリクエストします。

複数のブロックを単一のセットとして扱い、HTTP サーバーに単一のバイト範囲リクエストを送信します。これにより、HTTP 接続の数が減少し、クライアントにとって良い結果が得られる可能性があります。

ブロックを 10、50、または 100 個として扱うことができます。この方法で処理する場合、「ブロックあたりのピース数」を MaxPieces/20 として選択できるため、毎回リクエストするのはファイルの約 5％です。

推奨されないクライアント実装#

クライアントは単純に HTTP バイト範囲リクエストを使用して単一のピースをリクエストできます。しかし、一部のサーバー管理者はこの実装を好まないかもしれません。なぜなら、単一のファイルに対して数百または数千のリクエストが彼らのログに生成されるからです。中には、これを彼らへの DoS 攻撃と見なす人もいるかもしれません。

その他のプロトコル内容#

データをダウンロードするために使用できるプロトコル。上記では HTTP/FTP をシード共有のためのプロトコルとして挙げましたが、クライアントはデータのダウンロードを許可する任意のプロトコルを使用できます。例えば、HTTPS、FTPS、SFTP などのプロトコルも使用できますが、すべてのクライアントがサポートしているわけではありません。

RTSP や MMS などのプロトコルも使用される可能性があります。さらには、Usenet の NNTP プロトコルを使用してダウンロードすることもできます。

他のプロトコルには、ファイルの任意の位置からのダウンロードを許可しないなど、他の問題がある可能性があります。

クライアントは、HTTP または FTP プロトコルのいずれか一方のみを実装することを選択できます。

参考リンク#

http://www.bittorrent.org/beps/bep_0019.html