2011 BitTorrent B052-1

全文

(1)2011 年度修士論文. BitTorrent における低速ピアの支援法. 提出日： 2012 年 1 月 31 日. 指導：後藤滋樹教授早稲田大学基幹理工学研究科情報理工学専攻学籍番号： 5110B052-1. 佐藤圭.

(2) 目次. 1 序論. 5. 1.1. 研究の背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 5. 1.2. 研究の目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 5. 1.3. 本論文の構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 6. 2 P2P. 7. 2.1. P2P の概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 7. 2.2. P2P の特徴 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 8. 2.3. P2P のアーキテクチャ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 9. 2.3.1. ハイブリッド P2P モデル . . . . . . . . . . . . . . . . . . . . . . . . . .. 9. 2.3.2. ピュア P2P モデル. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 9. 2.3.3. スーパーノードモデル . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 10. P2P のアプリケーション . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 11. 2.4.1. Napster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 11. 2.4.2. Gnutella . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 11. 2.4.3. KaZaA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 12. 2.4.4. WinMX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 12. 2.4.5. Winny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 12. 2.4.6. Skype . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 12. BitTorrent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 13. 2.5.1. BitTorrent の用語 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 13. 2.5.2. BitTorrent の基本動作 . . . . . . . . . . . . . . . . . . . . . . . . . . .. 14. 2.5.3. BitTorrent のピース選択アルゴリズム . . . . . . . . . . . . . . . . . . .. 15. 2.5.4. BitTorrent のチョークアルゴリズム . . . . . . . . . . . . . . . . . . . .. 16. 2.4. 2.5. 3 関連研究 3.1. 17. BitTorrent システムへの配信支援ノードの導入 . . . . . . . . . . . . . . . . . . 1. 17.

(3) 目次. 3.2. 配信支援ノードの支援対象 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 17. 3.2.1. 新規ピア . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 17. 3.2.2. 冷遇ピア . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 18. 3.3. 配信支援ノードのチョークアルゴリズム . . . . . . . . . . . . . . . . . . . . . .. 18. 3.4. 配信支援ノードの配置 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 18. 4 提案方式. 19. 4.1. 提案方式の概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 19. 4.2. 提案方式の導入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 19. 4.2.1. トラッカーの持つピアの情報 . . . . . . . . . . . . . . . . . . . . . . . .. 19. 4.2.2. 方式 (1) 配信支援シーダー . . . . . . . . . . . . . . . . . . . . . . . . .. 20. 4.2.3. 方式 (2) 高速ピアによる配信支援 . . . . . . . . . . . . . . . . . . . . . .. 21. 4.2.4. 配信支援用のピアリストの作成 . . . . . . . . . . . . . . . . . . . . . . .. 22. PlanetLab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 22. 4.3. 5 実証実験. 23. 5.1. 実証実験の概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 23. 5.2. 実証実験の環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 23. 5.3. 実証実験の結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 24. 5.3.1. 実験 1.1 と実験 1.2 の結果 . . . . . . . . . . . . . . . . . . . . . . . . . .. 24. 5.3.2. 実験 2.1 と実験 2.2 の結果 . . . . . . . . . . . . . . . . . . . . . . . . . .. 26. 考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 29. 5.4.1. 実験 1.1 と実験 1.2 の考察 . . . . . . . . . . . . . . . . . . . . . . . . . .. 29. 5.4.2. 実験 2.1 と実験 2.2 の考察 . . . . . . . . . . . . . . . . . . . . . . . . . .. 30. 5.4. 6 結論. 31. 6.1. まとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 31. 6.2. 今後の課題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 31. 謝辞. 32. 参考文献. 33. 2.

(4) 図一覧 2.1. P2P システム . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 7. 2.2. クライアントサーバシステム . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 8. 2.3. ハイブリッド P2P モデル . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 9. 2.4. ピュア P2P モデル . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 10. 2.5. スーパーノードモデル . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 11. 2.6. BitTorrent の基本動作. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 15. 4.1. 方式 (1) の構成図 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 21. 4.2. 方式 (2) の構成図 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 22. 3.

(5) 表一覧 4.1. トラッカーのデータベースに格納されるピアの情報 . . . . . . . . . . . . . . . .. 20. 5.1. 各実験に参加するノード数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 23. 5.2. 実験 1.1 と実験 1.2 における各リーチャー (1 ∼ 5 位) のダウンロード時間 (s) . .. 24. 5.3. 実験 1.1 と実験 1.2 における各リーチャー (6 ∼ 10 位) のダウンロード時間 (s). .. 24. 5.4. 実験 1.1 と実験 1.2 における各リーチャー (11 ∼ 15 位) のダウンロード時間 (s) .. 25. 5.5. 実験 1.1 と実験 1.2 における各リーチャー (16 ∼ 20 位) のダウンロード時間 (s) .. 25. 5.6. 実験 1.1 と実験 1.2 における各リーチャー (21 ∼ 25 位) のダウンロード時間 (s) .. 25. 5.7. 実験 1.1 と実験 1.2 における各リーチャー (26 ∼ 30 位) のダウンロード時間 (s) .. 26. 5.8. 実験 2.1 と実験 2.2 における各リーチャー (1 ∼ 5 位) のダウンロード時間 (s) . .. 26. 5.9. 実験 2.1 と実験 2.2 における各リーチャー (6 ∼ 10 位) のダウンロード時間 (s). .. 27. 5.10 実験 2.1 と実験 2.2 における各リーチャー (11 ∼ 15 位) のダウンロード時間 (s) .. 27. 5.11 実験 2.1 と実験 2.2 における各リーチャー (16 ∼ 20 位) のダウンロード時間 (s) .. 27. 5.12 実験 2.1 と実験 2.2 における各リーチャー (21 ∼ 25 位) のダウンロード時間 (s) .. 28. 5.13 実験 2.1 と実験 2.2 における各リーチャー (26 ∼ 30 位) のダウンロード時間 (s) .. 28. 5.14 実験 1.1 と実験 1.2 における各グループの合計ダウンロード時間 (s) と増減率 (%). 29. 5.15 実験 2.1 と実験 2.2 における各グループの合計ダウンロード時間 (s) と増減率 (%). 30. 4.

(6) 第 1 章序論. 1.1. 研究の背景. インターネットの利用体系は従来はクライアントサーバシステムが主流であるが，インターネット上のコンテンツの大容量化やユーザーの増加に伴い，サーバへの負荷集中という問題が顕著となってきた．この問題に対処する技術として注目を集めているのが P2P (Peer to Peer) システムである． P2P システムではネットワークを構成するノードがクライアントとサーバの両方の機能を持ち，同等で対等な立場で相互接続される．このため， P2P システムは特定のサーバのみへの負荷集中を防止でき，クライアントサーバシステムよりもスケーラビリティに優れる．これまで P2P を用いた様々なアプリケーションが開発されてきたが，その中で代表的なものの 1 つに BitTorrent がある． BitTorrent はデータのダウンロードとアップロードを同時に行う形式で，ファイルを要求するユーザーが多ければ多いほどダウンロード時間が短縮されるという特徴を有する．しかし，ファイルの配信に参加するノードの状況によっては配信効率が低下する場合も存在する．現在，この問題を解決する手法として，配信支援ノードに関する研究 [1, 2, 3] が行われている．. 1.2. 研究の目的. BitTorrent システムにおけるファイルの配信効率の低下は，完全なファイルを保持するノードの不足，あるいは他ノードからデータを受信できないノードの存在といった問題に起因する． [1,. 2, 3] で提案されている配信支援ノードは，配信効率低下の原因となるノードのダウンロードを意図的に支援することでこれらの問題を解決し，全体の配信効率の向上を実現するノードである．これまで配信支援ノードの有効性は主にシミュレーションによって検証されており，実機上に実装した研究 [3] においても単一ワークステーション上のプロセス間通信という形式のみによって評価されている．つまり，実際のネットワーク環境における検討は十分に行われていない．. 5.

(7) 第 1 章序論. そこで本研究では， BitTorrent システムにおける配信効率の低下の原因となる，ダウンロード速度が低速なノードの支援法を新たに提案するとともに， PlanetLab 上の複数の実機を用いた実証実験によってその性能を評価する．ここで新たな支援法として提案する方式はトラッカー. (2.5.1参照) の機能に変更を加えることで実現する．そして，実証実験を PlanetLab 上で実施することにより，先行研究よりも実際の BitTorrent システムに近い環境において提案方式の検証を行う．. 1.3. 本論文の構成. 本論文は以下の章により構成される．第 1章序論本研究の概要について述べる．第 2章 P2P. P2P に関する解説を行うとともに， BitTorrent について詳説する．第 3章関連研究関連研究として配信支援ノードに関する研究を紹介する．第 4章提案方式本研究で提案する方式について説明する．第 5章実証実験実証実験により提案方式の性能を明らかにする．第 6章結論本研究の結論を述べ，今後の課題を示す．. 6.

(8) 第 2 章. P2P 2.1. P2P の概要. P2P (Peer to Peer) [4, 5] とは，対等な立場で接続されたコンピュータ (ピア) 同士が分散的にデータの交換や処理を行うネットワークの利用形態のことである．図 2.1に P2P システムの構成を示す． P2P システムを構成するピアはクライアントとサーバの両方の機能を持ち，状況に応じてその役割を変化させる．そのため P2P システムではクライアントサーバシステム (図 2.2参照) で問題となるような多数のクライアントからの要求が特定のサーバのみに集中するという現象を回避することができる．. . . 図 2.1: P2P システム. 7.

(9) 第 2 章 P2P.

(10). 図 2.2: クライアントサーバシステム. 2.2. P2P の特徴. P2P システムには主に以下のような特徴がある．コスト削減サーバのみに依存しないため，機器・管理者・運用・保守といった負担が軽減される．また，資源の集中に起因するリスクや非効率性を避けることができる．スケーラビリティサーバ機能を各ピアが分散して保持する構成のため，ユーザ数が増加してもシステムを増強する必要がない．冗長性システムの分散化により，一部に障害が発生してもその他の部分に及ぼす影響は小さい．ネットワーク全体の管理や監視が困難システム全体を一元管理するような手法には不向きのため，アクセス管理・ログ取得・課金・システム全体の停止といったことを一元的に行うのは困難である，これは後述するピュア P2P モデル (2.3.2参照) で見られる特徴である．. 8.

(11) 第 2 章 P2P. 2.3. P2P のアーキテクチャ. P2P のアーキテクチャは，ハイブリッド P2P モデル，ピュア P2P モデル，スーパーノードモデルの 3 つに大別できる．以下，それぞれのアーキテクチャについて解説する．. 2.3.1. ハイブリッド P2P モデル. ハイブリッド P2P モデル (図 2.3参照) はインデックスサーバとピアから構成される．配布されるファイルのメタデータがインデックスサーバで管理され，ファイル自体は各ピアで保有される．すなわち，インデックスサーバは主にピアがアップロードするメタデータの蓄積やピアからの検索要求への応答といった役割を担い，ファイルの送受信はピア間で直接行われる．このため，インデックスサーバにかかるトラフィックや処理の負荷はクライアントサーバモデルにおけるサーバのそれよりも大きく軽減される．また，前述のようにインデックスサーバではピアやファイルの情報を集中管理しているため検索速度が速く，ユーザの制御やファイル流通の集中管理も可能である．一方で，ハイブリッド P2P モデルにはインデックスサーバが停止するとサービスそのものが停止してしまう (インデックスサーバが単一故障点となる) 問題がある．ハイブリッド P2P モデルの代表例としては， Napster (2.4.1参照) ， WinMX (2.4.4参照) ，. BitTorrent (2.5参照) などが挙げられる．. !". . .

(12) . . 図 2.3: ハイブリッド P2P モデル. 2.3.2. ピュア P2P モデル. ピュア P2P モデル (図 2.4参照) ではサーバを用いずにピアとピアが直接通信を行い，ファイルとメタデータの両方を各ピアで保有する．ファイルの探索は検索クエリを伝播させることによ. 9.

(13) 第 2 章 P2P. りピア同士で協力して行われるため， 2.3.1で述べた単一故障点の問題は解決されている．しかし，ピアやファイルの情報が分散して保持されているため探索速度が遅く，第三者が集中管理することが難しい．ピュア P2P モデルの代表例には， Gnutella (2.4.2参照) や Winny (2.4.5参照) がある．. .

(14) . 図 2.4: ピュア P2P モデル. 2.3.3. スーパーノードモデル. スーパーノードモデル (図 2.5参照) はピュア P2P モデルを改良したモデルで，一時的にインデックスサーバの役割を担うノードを有し，これをスーパーノードと呼ぶ．通常，複数のスーパーノード同士が特別なネットワークを構成し，このスーパーノード群がインデックスサーバと同等の機能を提供する．このため，ハイブリッド P2P モデルとピュア P2P モデルの両方の利点があり，スケーラビリティや耐障害性に優れる．なお，スーパーノードになるには CPU やメモリの観点から高い処理性能があること，グローバル IP アドレスを有することといった条件があり，これらを満たすピアが自律的に選ばれる．スーパーノードモデルには， KaZaA (2.4.3参照) や Skype (2.4.6参照) が該当する．. 10.

(15) 第 2 章 P2P.

(16)

(17)

(18) . . . . . 図 2.5: スーパーノードモデル. 2.4. P2P のアプリケーション. P2P を用いた主なアプリケーションを紹介する．本論文で注目する BitTorrent については 2.5で詳説する．. 2.4.1. Napster. Napster はハイブリッド P2P モデルを採用したファイル交換ソフトである． 1999 年の発表以降， MP3 形式の音楽ファイルの交換を主な用途として高い利便性を実現しユーザー数を伸ばしたが，著作権の侵害やトラフィックの増大が問題視された．結局，合法的なサービスの提供には至らず， 2001 年にサービスが停止された． OpenNap と呼ばれる互換サーバが存在する．. 2.4.2. Gnutella. Gnutella はピュア P2P モデルを採用したファイル交換ソフトで，あらゆる形式のファイルの共有を可能とし， 2000 年 3 月に公開された．インデックスサーバを置かずピア間のみでファイル交換を行うため，耐障害性には優れるが大きな帯域幅が必要とされた．また， Napster と同様に多数の不正ユーザーを生み出すこととなり，著作物の不正流通被害が蔓延した．サービスの主体者を特定しにくいピュア P2P モデルを採用した Gnutella の存在は監視や規制の難しさを示すこととなった．. 11.

(19) 第 2 章 P2P. 2.4.3. KaZaA. KaZaA[6] はスーパーノードの概念を導入したファイル交換ソフトである．開発者はニコラス・ゼンストロムとヤヌス・フリス (彼らは後に P2P 型 IP 電話の Skype や P2P 型映像配信サービスの Joost[7] の開発も行っている) で，公開は 2000 年 7 月である． 2003 年 5 月にはダウンロード数が世界一と報道されるなど人気を博す一方で， KaZaA をめぐって各国で著作権侵害の訴訟が行われた．. 2.4.4. WinMX. WinMX[8] は Napster をベースに Windows 上で動作する P2P クライアントである． 2000 年 10 月にリリースされた最初のバージョンでは Napster や OpenNap への接続に対応していたが，その後はハイブリッド型 P2P モデルとピュア P2P モデルの両方を兼ね備えたシステムへと変化した．様々なファイルを扱えること，検索の効率性，多言語対応などの理由で普及し，日本語化パッチの存在で日本でも人気が出た．しかし，日本において世界で初めてユーザーに逮捕者が出たり，個人情報の流出や違法ファイルの公開で訴訟が起きたりといった問題も発生した．. 2.4.5. Winny. Winny[9] は日本で開発されたピュア P2P モデルのファイル交換ソフトである．一次配布者の特定を困難にする中継機能，コンテンツの複製であるキャッシュの作成，回線速度に応じた階層化，ユーザーのクラスタリングなどにより，匿名性と効率性の高いファイル共有を実現している．国内発，利用が容易といった理由で日本において非常に流行したが， Winny でも著作権問題が浮き彫りとなり，ついには開発者の逮捕と裁判という世界的にも異例な事態に発展した．その後もウイルス感染による情報漏洩事件が相次いでおり， P2P ソフトをめぐる社会問題は終息していない．. 2.4.6. Skype. Skype[10] はインターネット上で電話機能を利用できるソフトウェアである． IP 電話相当の機能に加えてテレビ電話や文字チャットなどが可能であり，ユーザーによる新しいサービスの提供も行える．また， Skype 間だけでなく Skype と固定電話などの間でも発着信をすることができる． Skype のサービスを利用する際は加入時に付与される ID が用いられ， Skype 同士で通信する場合にはこの ID と IP アドレスのマッチングがスーパーノードによって行われる．この点で，多くの場合に SIP サーバに依存する IP 電話とは異なる．インストールするだけで利用を開始できる，高音質である， Skype 間での通話と文字チャットが無料であるといった要因から多数のユーザーの支持を集めている．. 12.

(20) 第 2 章 P2P. 2.5. BitTorrent. BitTorrent[11, 12] は 2001 年にブラム・コーエンによって開発されたファイル交換プロトコルおよびそのアプリケーションである．大容量のファイルを高速に低コストで配信することを目的に開発され，オープンソースの OS などの配信に利用されている．各ユーザーがデータのダウンロードと同時にアップロードも行う形式によって，ユーザーからの要求が多いファイルほど短時間でダウンロードが完了するというのが大きな特徴である．. BitTorrent でも他の P2P ファイル交換ソフトと同様に著作権問題が表面化したが，非合法なユーザーやファイルの撲滅が積極的に行われたことにより，次第に合法的な利用が中心となってきた． P2P のファイル交換システムに対して訴訟を起こしてきたコンテンツ業界との提携も進み，映画・テレビ番組・ゲーム・音楽といったコンテンツについても BitTorrent による合法的な配信が実現している．. 2.5.1. BitTorrent の用語. BitTorrent で使用される主な用語を以下に示す．トラッカーピアやファイルの情報を管理するサーバ．. torrent ファイルトラッカーの情報やファイルのメタデータが記述されたファイル．シーダー完全なファイルを保持し，アップロードに専念するピア．リーチャーファイルのダウンロードが完了していないピア．スウォーム同一ファイルを扱うピアの集合が構成するネットワーク．ピアリストダウンロード対象となるファイルを持つピアの一覧．ピースダウンロードされるファイルを構成する一単位．ファイルはダウンロード時にこの単位に分割される．. 13.

(21) 第 2 章 P2P. チョーク他ピアによるダウンロードを許可しないこと．アンチョーク他ピアによるダウンロードを許可すること．. 2.5.2. BitTorrent の基本動作. BitTorrent の基本動作 (図 2.6参照) は次のとおりである． 1. ファイルをダウンロードしたいピアがトラッカーへ接続するために， Web サーバなどから torrent ファイルを入手する． 2. torrent ファイルを取得したピアはその情報をもとにトラッカーに接続し，処理の開始を通知する．. 3. ピアから通知を受けたトラッカーはそのピアに対してピアリストを提供する． 4. ピアリストを受け取ったピアはそこから適切なピアを選択する．選択したピアとの接続が確立されると，以降はピア同士がピースを交換することでダウンロードが進行する．. 5. ファイルのダウンロードが完了したピアはシーダーとなり，他ピアへのアップロードだけを行うようになる．上記で説明したファイルのダウンロードはピース単位で行われる．ファイルをピースに分割することによる利点は次のとおりである．. • 一つのピースをダウンロードするたびにハッシュ値を用いて完全性を検証することで，ファイルの改ざんを防止できる．. • 検証が終了したピースから他ピアへのアップロードが可能となる．すなわち，ファイル全体のダウンロード完了を待たずにアップロードが始まるため，高い転送効率が得られる．. • ネットワーク上でのピースの紛失やファイルの改ざんが発生した場合には，ピース単位で再試行が行える．. 14.

(22) 第 2 章 P2P .

(23). &('. 45. "!$#%. 3 . )+*-,.(/. . . 45 3 . "!$#%(021. 457698 :<;= >. 3 . 45. AB. C2DFEHG"IJKML. *FNPO G"IJ. ? @<. 図 2.6: BitTorrent の基本動作. 2.5.3. BitTorrent のピース選択アルゴリズム. ピース選択アルゴリズムは BitTorrent のファイル転送アルゴリズムの 1 つである．これはダウンロードするピースを選択する順番を決定するもので，ダウンロードの効率に大きく影響する．. BitTorrent には主に 4 つのピース選択アルゴリズムが存在する．取得中のピースに集中する戦略ピース選択アルゴリズムの中で最優先される戦略である． 1 つのピースは複数のサブピースに分割されてダウンロードされる．本戦略では，現在ダウンロードしているピースが完全に取得されるまで当該ピースを構成するサブピースのダウンロードに集中する．希少ピースを優先する戦略. Rarest First 戦略と呼ばれる． 1 つのピースのダウンロードが完了し，新たに別のピースのダウンロードを開始する際には，各ピアが保持するピースのうち最も少ないものを選択する．これによって希少なピースを分散させることができる．ランダム戦略. BitTorrent クライアントの起動直後に適用される戦略である．ダウンロードするピースが無作為に選択される．. 15.

(24) 第 2 章 P2P. エンドゲーム戦略ファイルのダウンロードの最終段階で採用される戦略である．本戦略により最後のサブピースは複数のピアから同時にダウンロードされる．. 2.5.4. BitTorrent のチョークアルゴリズム. チョークアルゴリズム (ピア選択アルゴリズム) はピース選択アルゴリズムと並ぶ BitTorrent の重要なファイル転送アルゴリズムである． BitTorrent では自律的なダウンロードの効率化のため，各ピアにおいて他ピアに対するチョーク，アンチョークが決定される．その決定法がチョークアルゴリズムであり，複数のチョークアルゴリズムが用意されている．基本的なチョークアルゴリズム各ピアは一定数 (デフォルトでは 4) のピアに対してアンチョークを行う．アンチョークされるピアは、現在のダウンロード速度によって決定される．楽観的なアンチョーク戦略ダウンロード速度のみによるチョーク判定では，局所最適化される恐れがある．これを避けるために 4 つのアンチョーク状態のピアのうちの 1 つには楽観的なアンチョーク戦略を適用する．これはピアリスト中のピアを 30 秒ごとに順々にアンチョークする戦略である．反冷遇主義戦略リーチャーとして動作している際に，他ピアへのアップロード行っているにもかかわらず，接続しているピアからチョークされる (このような状況を冷遇されるという) ことがある．アンチョークしているピアから 1 分以上にわたってピースを取得できない場合は，自分が冷遇されていると判断し，そのピアをチョーク状態にする．その後，楽観的アンチョーク戦略によって代わりにアンチョークするピアを決定する．なお，一度自分を冷遇したピアに対しては，それ以降のチョーク判定でアンチョークすることはない．アップロードオンリーリーチャーからシーダーに移行したピアは，ダウンロード速度に基づいた戦略からアップロード速度が高速なピアをアンチョークする戦略に切り替える．この戦略を適用するピア. (シーダー) が増加すると，全体のダウンロード効率が向上する．. 16.

(25) 第 3 章関連研究本章では関連研究として，戸出らによって提案されている配信支援ノード [1, 2, 3] について解説する．. 3.1. BitTorrent システムへの配信支援ノードの導入. 配信支援ノードとは， BitTorrent システムに組み込まれて一般ユーザー間のファイル交換を支援するノードであり，その設置は ISP のようなサービスの提供者側で行うことが想定されている．配信支援ノードは独自のアルゴリズムに基づいて動作し，スウォーム内で特にダウンロード効率の低いピアを支援することを目的としている．配信支援ノードを導入することで，低速なピアのダウンロード効率が底上げされ，結果としてスウォーム全体のファイル転送効率の上昇が期待できる．. 3.2. 配信支援ノードの支援対象. 配信支援ノードがダウンロードを支援するのは以下の 2 種類のピアである．. 3.2.1. 新規ピア. 新規ピアとは，スウォームに参加したばかりで受信可能な接続先が少ないピアのことである．接続先の少ない新規ピアはダウンロード速度が十分に上がっておらず，ダウンロード速度を判断基準とする基本的なチョークアルゴリズム (2.5.4参照) によってチョークされてしまうため，ダウロード効率が特に悪くなる．. 17.

(26) 第 3 章関連研究. 3.2.2. 冷遇ピア. 冷遇ピアとは，リーチャーとしての動作中に一定量のアップロードを行っているにもかかわらず，他ピアからチョークされてしまうピアのことを意味する．したがって，冷遇ピアは他ピアからダウンロードすることを禁止された状態になるため，著しくダウンロード効率が悪化する．. 3.3. 配信支援ノードのチョークアルゴリズム. 配信支援ノードは以下の 2 つの指標を用いて，独自のチョークアルゴリズムを実現している．. A1 (i) =. ni di × N D. (3.1). A2 (i) =. ni ri × N R. (3.2). ここで， ni と di はそれぞれピア i をアンチョークしているピア数とピア i の総ダウンロード量を表す．また， ri = di /ui であり， ui はピア i の総アップロード量である．そして， N ， D，. R はそれぞれ ni ， di ， ri の基準値を意味する． A1 (i) の値が小さいほど，ピア i はアンチョークされる接続先が少なく，かつダウンロード量が少ないと判断され，新規ピアである可能性が高まる．一方， A2 (i) の値が小さい場合は，ピア. i はアンチョークされる接続先が少なく，かつ一定のアップロードを行っているとみなされ，冷遇ピアである可能性が高い．最終的に配信支援ノードは以下に示す Amin (i) を算出し， Amin (i) の値が小さいものから順に k 個のピアをアンチョークする．. Amin (i) = min(A1 (i), A2 (i)). 3.4. (3.3). 配信支援ノードの配置. 配信支援ノードのスウォームへの参加あるいはスウォームからの離脱は，専用の管理サーバにおいて処理される．管理サーバは，スウォーム内のシーダーの割合と全体のピース取得状況の 2 つを指標として，配信支援ノードの配置を決定する．管理サーバの導入により，複数のスウォームが存在する状況でも各スウォーム内の配信支援ノード数の動的な調整が可能となる．. 18.

(27) 第 4 章提案方式. 4.1. 提案方式の概要. 本研究では，トラッカーの機能に変更を加えることで， BitTorrent ネットワークにおけるダウンロード速度が上がらないピアのダウンロード効率の向上を実現する．また，提案方式の評価に PlanetLab 上の実機を用いることによって，実ネットワークの環境で検証を行う．. 4.2 4.2.1. 提案方式の導入トラッカーの持つピアの情報. トラッカーはピアから送信される情報をデータベースに格納して保持する．表 4.1にトラッカーのデータベースに格納されるピアの情報を示す．提案方式ではこのデータベース上の情報を利用して， BitTorrent ネットワークにおけるファイル転送効率の向上を実現する．. 19.

(28) 第 4 章提案方式. 表 4.1: トラッカーのデータベースに格納されるピアの情報項目. 4.2.2. 格納される情報. info hash. ダウンロード対象となるファイルのハッシュ値. ip. ピアの IP アドレス. port. ピアが通信時に使用するポート番号. peer id. ピアに固有の ID. uploaded. ピアの総アップロード量 (B). downloaded. ピアの総ダウンロード量 (B). left. ダウンロード完了までの残りデータ量 (B). update time. データベースの更新が行われた時点のタイムスタンプ. expire time. ピアの有効期限を示すタイムスタンプ. 方式 (1) 配信支援シーダー. 配信支援シーダーとは，低速なピアのダウンロードを支援するためのシーダーであり，第 3章で解説した配信支援ノードと同様の形式である．しかし，この配信支援シーダーはクライアントソフトには変更を加えずにトラッカーのみの制御によって実現される点が先行研究とは異なる．本方式の構成図を図 4.1に示す．配信支援シーダーはトラッカーにおいて IP アドレスを判別することにより，一般のシーダーやリーチャーと区別する．配信支援シーダーの IP アドレスはトラッカーにあらかじめ設定しておくものとする．トラッカーでは配信支援シーダーからのアクセスに対して配信支援用のピアリストを提供する．配信支援用のピアリストとは，通常のピアリストからダウンロード速度が高速と判断されたピアの情報を除いたものである．このピアリストの作成方法は 4.2.4で説明する．なお，本方式では配信支援シーダーとトラッカーの両方をサービスの提供者が設置することを想定している．. 20.

(29) 第 4 章提案方式. . ! "$#&%(') . . *,+-. #0/2143657.

(30) . 図 4.1: 方式 (1) の構成図. 4.2.3. 方式 (2) 高速ピアによる配信支援. 高速ピアによる配信支援とは，ダウンロード速度が高速なピアに対して，ダウンロード効率の低いピアを支援させる方式である．本方式の構成図は図 4.2に示すとおりである．トラッカーにアクセスしてきた各ピアについて高速ピアであるか否かを判定し，高速ピアと判断されたピアに対して配信支援用のピアリスト (4.2.4参照) を提供する．高速ピアであるか否かの判定には，. 4.2.1で述べたトラッカーの保持する情報のうち， uploaded と downloaded を用いる．そして，以下のどちらかの条件を満たすピアを高速ピアと判定する．. uploaded > U1. (4.1). downloaded > D. (4.2). ここで， U1 と D はそれぞれ uploaded と downloaded の基準値であり，トラッカーにおいてあらかじめ設定しておく必要がある．. 21.

(31) 第 4 章提案方式. . !. . . . "#$% '&)( *,+-.

(32) . 図 4.2: 方式 (2) の構成図. 4.2.4. 配信支援用のピアリストの作成. 配信支援用のピアリストは通常のピアリストを生成する際の条件に以下の数式を追加することで作成する．. uploaded < U2. (4.3). ここで， uploaded は 4.2.1で述べたトラッカーが保持する情報の 1 つである．また， U2 は. uploaded の基準値であり，式 4.1の U1 とは別に設定するものとする．. 4.3. PlanetLab. PlanetLab[13] とは，実際のインターネット上での評価実験を可能とする地球規模のテストベッドであり， 2012 年 1 月の時点で 1103 のノードと 537 のサイトが参加している．研究コミュニティに自らノードを提供することで，コミュニティに参加する他ノードのリソースを用いた実験を行うことができる．これはスライスと呼ばれる， Linux マシン上に実装された仮想マシンを用いることで実現される．本研究ではこの PlanetLab を利用して提案方式の評価を行う．. 22.

(33) 第 5 章実証実験. 5.1. 実証実験の概要. 実証実験では，第 4章で提案した「方式 (1) 配信支援シーダー」と「方式 (2) 高速ピアによる配信支援」のそれぞれを BitTorrent システムに導入した際の，スウォームに参加する各ピアのファイル取得に要する時間を検証する．比較対象は通常の OpenTracker[14] を用いた場合の Bit-. Torrent システムとする．. 5.2. 実証実験の環境. 実証実験として，方式 (1) を評価するための実験 1.1 と実験 1.2，および方式 (2) を評価する実験 2.1 と実験 2.2 を行う．いずれの実験でも形成するスウォーム数は 1 とし，配布するファイルのサイズは 300 MB とする．各実験に参加するノード数は表 5.1に示すとおりである．ここで，それぞれ比較対象となる実験 1.1 と実験 1.2 および実験 2.1 と実験 2.2 では配信支援シーダーと一般のシーダーの合計数を一致させている．使用するクライアントソフトは ctorrent-1.3.4-4.dnh. 3.2[15, 16] とし，トラッカー以外のノードには 4.3で述べた PlanetLab 上に存在する実機を利用する．. 表 5.1: 各実験に参加するノード数トラッカー. 配信支援シーダー. シーダー. リーチャー. 実験 1.1. 1. 0. 2. 30. 実験 1.2. 1. 1. 1. 30. 実験 2.1. 1. 0. 1. 30. 実験 2.2. 1. 0. 1. 30. 23.

(34) 第 5 章実証実験. 5.3. 実証実験の結果. 5.3.1. 実験 1.1 と実験 1.2 の結果. 方式 (1) の評価を実験 1.1 と実験 1.2 によって行う．実験 1.1 で通常の OpenTracker を利用した BitTorrent システムにおける各リーチャーのダウンロード完了に要する時間を測定し，実験. 1.2 では方式 (1) を導入した場合について測定する．ただし，実験 1.2 における U2 (4.2.4参照) は， U2 = 100 [MB] として実験を行った．実験の結果を表 5.2∼ 5.7に示す．評価の都合上，各リーチャーに対してダウンロードが早く完了した順に順位を付け，その順位に従い 5 台ごとのグループに分けて表示している．表 5.2: 実験 1.1 と実験 1.2 における各リーチャー (1 ∼ 5 位) のダウンロード時間 (s) 実験 1.1. 実験 1.2. 1. 124. 110. 2. 135. 123. 3. 138. 130. 4. 140. 142. 5. 140. 146. 1 ∼ 5 位の合計. 677. 651. 順位. 表 5.3: 実験 1.1 と実験 1.2 における各リーチャー (6 ∼ 10 位) のダウンロード時間 (s) 実験 1.1. 実験 1 .2. 6. 142. 148. 7. 147. 153. 8. 152. 154. 9. 153. 159. 10. 157. 161. 6 ∼ 10 位の合計. 751. 775. 順位. 24.

(35) 第 5 章実証実験. 表 5.4: 実験 1.1 と実験 1.2 における各リーチャー (11 ∼ 15 位) のダウンロード時間 (s) 実験 1.1. 実験 1 .2. 11. 162. 163. 12. 180. 178. 13. 195. 192. 14. 195. 195. 15. 200. 195. 11 ∼ 15 位の合計. 932. 923. 順位. 表 5.5: 実験 1.1 と実験 1.2 における各リーチャー (16 ∼ 20 位) のダウンロード時間 (s) 実験 1.1. 実験 1 .2. 16. 205. 198. 17. 207. 207. 18. 218. 210. 19. 219. 212. 20. 220. 219. 16 ∼ 20 位の合計. 1069. 1046. 順位. 表 5.6: 実験 1.1 と実験 1.2 における各リーチャー (21 ∼ 25 位) のダウンロード時間 (s) 実験 1.1. 実験 1.2. 21. 223. 223. 22. 230. 228. 23. 236. 228. 24. 265. 286. 25. 286. 286. 21 ∼ 25 位の合計. 1240. 1251. 順位. 25.

(36) 第 5 章実証実験. 表 5.7: 実験 1.1 と実験 1.2 における各リーチャー (26 ∼ 30 位) のダウンロード時間 (s) 実験 1.1. 実験 1 .2. 26. 335. 287. 27. 369. 317. 28. 380. 380. 29. 392. 396. 30. 612. 514. 26 ∼ 30 位の合計. 2088. 1894. 順位. 5.3.2. 実験 2.1 と実験 2.2 の結果. 方式 (2) の評価は実験 2.1 と実験 2.2 によって行い，実験 2.1 では通常の OpenTracker による. BitTorrent システムを，実験 2.2 では方式 (2) を導入した BitTorrent システムにおける各リーチャーのダウンロード完了時間をそれぞれ測定する．ただし，実験 2.2 における U1 , D (4.2.3参照) および U2 (4.2.4参照) はそれぞれ U1 = 200 [MB], D = 300 [MB], U2 = 50 [MB] として実験を行った．実験の結果を表 5.8∼ 5.13に示す．ここでの結果の表示方法は 5.3.1と同様の形式である．表 5.8: 実験 2.1 と実験 2.2 における各リーチャー (1 ∼ 5 位) のダウンロード時間 (s) 実験 2.1. 実験 2 .2. 1. 119. 37. 2. 140. 121. 3. 140. 146. 4. 148. 146. 5. 150. 147. 1 ∼ 5 位の合計. 697. 597. 順位. 26.

(37) 第 5 章実証実験. 表 5.9: 実験 2.1 と実験 2.2 における各リーチャー (6 ∼ 10 位) のダウンロード時間 (s) 順位. 実験 2.1. 実験 2. .2. 6. 160. 147. 7. 165. 147. 8. 170. 151. 9. 174. 156. 10. 194. 156. 6 ∼ 10 位の合計. 863. 757. 表 5.10: 実験 2.1 と実験 2.2 における各リーチャー (11 ∼ 15 位) のダウンロード時間 (s) 実験 2.1. 実験 2 .2. 11. 195. 195. 12. 195. 196. 13. 199. 197. 14. 199. 197. 15. 203. 197. 11 ∼ 15 位の合計. 991. 982. 順位. 表 5.11: 実験 2.1 と実験 2.2 における各リーチャー (16 ∼ 20 位) のダウンロード時間 (s) 実験 2.1. 実験 2 .2. 16. 203. 199. 17. 204. 202. 18. 207. 207. 19. 208. 218. 20. 210. 222. 16 ∼ 20 位の合計. 1032. 1048. 順位. 27.

(38) 第 5 章実証実験. 表 5.12: 実験 2.1 と実験 2.2 における各リーチャー (21 ∼ 25 位) のダウンロード時間 (s) 実験 2.1. 実験 2 .2. 21. 211. 224. 22. 226. 224. 23. 285. 227. 24. 311. 293. 25. 347. 327. 21 ∼ 25 位の合計. 1380. 1295. 順位. 表 5.13: 実験 2.1 と実験 2.2 における各リーチャー (26 ∼ 30 位) のダウンロード時間 (s) 実験 2.1. 実験 2 .2. 26. 358. 354. 27. 360. 359. 28. 434. 394. 29. 585. 405. 30. 667. 576. 26 ∼ 30 位の合計. 2404. 2088. 順位. 28.

(39) 第 5 章実証実験. 5.4 5.4.1. 考察実験 1.1 と実験 1.2 の考察. 表 5.2∼ 5.7のそれぞれの最終行で示した各グループの合計のダウンロード時間をまとめると表. 5.14のようになる．ここで，増減率は実験 1.2 における合計ダウンロード時間が実験 1.1 比でどれだけ増減したかを表す．表 5.14: 実験 1.1 と実験 1.2 における各グループの合計ダウンロード時間 (s) と増減率 (%) グループ. 実験 1.1. 実験 1.2. 増減率. 1∼5位. 677. 651. −3.84. 6 ∼ 10 位. 751. 775. 3.20. 11 ∼ 15 位. 932. 923. −0.966. 16 ∼ 20 位. 1069. 1046. −2.15. 21 ∼ 25 位. 1240. 1251. 26 ∼ 30 位. 2088. 1894. 0.887 −9.29. 表 5.14より，方式 (1) を導入した場合の合計ダウンロード時間は， 6 ∼ 10 位と 21 ∼ 25 位のグループで微増しているものの，低速ピアの集団である 26 ∼ 30 位のグループでは −9.29% と大きく短縮されている．さらに表 5.7より，ダウンロード所要時間が最下位だったピアでは， 612 s から 514 s へと 16.0% の短縮に成功していることが確認できる．以上より，実験 1.2 で導入した「方式 (1) 配信支援シーダー」は，低速なピアのダウンロード効率を向上させ，それ以外のピアには大きな影響を与えない方式であることがわかった．. 29.

(40) 第 5 章実証実験. 5.4.2. 実験 2.1 と実験 2.2 の考察. 5.4.1と同様に実験 2.1 と実験 2.2 における各グループの合計ダウンロード時間をまとめると表 5.15のようになる．表 5.15: 実験 2.1 と実験 2.2 における各グループの合計ダウンロード時間 (s) と増減率 (%) グループ. 実験 2.1. 実験 2.2. 1∼5位. 697. 597 −14.4. 6 ∼ 10 位. 863. 757 −12.3. 11 ∼ 15 位. 991. 982. −0.908. 16 ∼ 20 位. 1032. 1048. 1.55. 21 ∼ 25 位. 1380. 1295. −6.16. 26 ∼ 30 位. 2404. 2088 −13.1. 増減率. 表 5.15より， 16 ∼ 20 位のグループで合計ダウンロード時間の微増が見られるが，それ以外のグループでは合計ダウンロード時間は減少しており，特に低速ピアの集団である 26 ∼ 30 位のグループでは −13.1% と大幅な短縮が確認できる．また表 5.13 から，ダウンロード所要時間が最下位のピアでは， 667 s から 576 s へと 13.6% の短縮が達成されていることがわかる．以上より，実験 2.2 で導入した「方式 (2) 高速なピアによる配信支援」は，低速なピアのダウンロード効率の向上を他のピアに悪影響を与えることなく実現する方式であることが示された．. 30.

(41) 第 6 章結論. 6.1. まとめ. 本研究は，ダウンロード速度が低速なピアの存在により BitTorrent システムにおいてダウンロード効率が低下する現象の改善を目的として行った．「方式 (1) 配信支援シーダー」と「方式. (2) 高速なピアによる配信支援」の 2 つの方式を提案し， PlanetLab 上での実証実験によってそれらの性能を検証した．その結果，どちらの方式も低速なピアのダウンロード速度を底上げし，かつそれ以外のピアへはほとんど悪影響を与えないということがわかった．したがって， 2 つの提案方式は， BitTorrent システムにおいて低速なピアのダウンロードを支援することでスウォーム全体のダウンロード効率を向上させる有効な手法である．. 6.2. 今後の課題. 今後取り組むべき課題は以下のとおりである．高速ピアと低速ピアのより汎用的な判定今回は実装の容易さから，ダウンロード速度が高速なピアおよび低速なピアの判定を各ピアが保有する uploaded と downloaded の情報を用いて行った．より汎用性を高めるためには，アップロード速度やダウンロード速度を算出し，それらを指標とした判定を行う必要がある．多様な環境での実証実験本研究では， PlanetLab を用いることで実際のネットワーク環境を想定した実証実験を行った．さらなる詳細な評価のためには，複数のスウォームが存在する場合やピアの参加と離脱がランダムに発生する場合といった様々な環境における検証が必要である．. 31.

(42) 謝辞本修士論文の作成にあたり，日ごろよりご指導をいただいた後藤滋樹教授に心より感謝いたします．また， BitTorrent に関する研究を進める中で多くの貴重な助言をいただいた高田和也氏と野間敬太氏に深く感謝いたします．そして，ともに研究に励み，多大なご協力をいただいた後藤滋樹研究室諸氏に感謝いたします．. 32.

(43) 参考文献 [1] 平石武, 戸出英樹, “配信支援ノードを有する P2P ネットワーク構成法”, 信学技報, NS200927, pp.61–66, May 2009. [2] 伊藤大要, 谷川陽祐, 戸出英樹, “マルチスウォーム P2P 環境における配信支援ノードの適応的分配法”, 信学技報, NS2010-22, pp.37–42, May 2010.. [3] 横畠誠也, 谷川陽祐, 戸出英樹, “配信支援ノードを有するマルチスウォーム BitTorrent システムの実装と評価”, 信学技報, NS2010-269, pp.597–602, March 2011.. [4] Eng Keong Lua, Jon Crowcroft, Marcelo Pias, Ravi Sharma, Steven Lim, “A Survey and Comparison of Peer-to-Peer Overlay Network Schemes”, IEEE Communications Survey and Tutorial, March 2004. [5] 江崎浩監修, “P2P 教科書”, インプレス R&D, 2008. [6] KaZaA http://www.kazaa.com/ [7] Joost http://www.joost.com/ [8] WinMX http://www.winmxworld.com/ [9] 金子勇, “Winny の技術”, アスキー, 2005. [10] Skype http://www.skype.com/ [11] BitTorrent http://www.bittorrent.com/. 33.

(44) 参考文献. [12] Bram Cohen, “Incentives Build Robustness in BitTorrent”, Workshop on Economics of Peer-to-Peer Systems, 2003. [13] PlanetLab http://www.planet-lab.org/ [14] OpenTracker http://www.whitsoftdev.com/opentracker/ [15] Enhanced CTorrent http://www.rahul.net/dholmes/ctorrent/ [16] CTorrent | Free Communications software downloads at SourceForge.net http://sourceforge.net/projects/ctorrent/ [17] 魏元, “P2P トラフィックの効率的制御法”, 早稲田大学基幹理工学研究科情報理工学専攻 2008 年度修士論文, February 2009. [18] 出井勝弘, “BitTorrent における効率的なピア選択法”, 早稲田大学基幹理工学研究科情報理工学専攻 2009 年度修士論文, February 2010.. [19] 大村淳己, “地理情報を考慮した P2P ストリーミング”, 早稲田大学基幹理工学研究科情報理工学専攻 2010 年度修士論文, February 2011.. 34.

(45)