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 バイト範囲リクエストを使用して単一のセグメントをリクエストできます。しかし、一部のサーバー管理者はこの実装を好まないかもしれません。なぜなら、単一のファイルに対して数百または数千のリクエストが彼らのログに生成されるからです。中には、これを彼らに対するサービス拒否攻撃と見なす人もいるかもしれません。

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

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

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

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

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

参考リンク#

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