BitTorrent における局所性を優先したピア選択法

(1)

2011 年度修士論文

BitTorrent における

局所性を優先したピア選択法

提出日： 2012 年 1 月 31 日

指導：後藤滋樹教授

早稲田大学大学院基幹理工学研究科情報理工学専攻学籍番号： 5110B103-7

野間敬太

(2)

図一覧

1.1 各種トラフィックの予想 . . . 5

2.1 クライアントサーバモデル . . . 8

2.2 ハイブリッドP2Pモデル . . . 9

2.3 ピュアP2Pモデル . . . 10

2.4 スーパーノード型P2Pモデル . . . 11

3.1 IPアドレスの変換例 . . . 17

4.1 ピア同士の通信モデル . . . 20

4.2 本提案のトラッカーとピア間の通信シーケンス. . . 21

5.1 ノードの配置図 . . . 23

5.2 ダウンロード元とダウンロード量の関係 . . . 24

(5)

表一覧

2.1 BitTorrentで使用される用語. . . 12

2.2 ピアがトラッカーに対して送信する情報 . . . 13

2.3 トラッカーがピアに対して送信する情報 . . . 13

3.1 iTrackerが提供するインタフェース . . . 16

4.1 階級に応じたピアリスト一覧 . . . 19

5.1 提案手法における各ピアのダウンロード元とダウンロード量の関係(単位: ピース) . . . 25

5.2 ランダム手法における各ピアのダウンロード元とダウンロード量の関係(単位: ピース) . . . 25

5.3 各ピアがダウンロード完了までに要した時間(単位: 秒) . . . 26

(6)

第 1 章序論

1.1 _{研究の背景}

P2Pトラフィックのインターネット全体に占める割合は動画トラフィックの台頭により縮小傾向にある。図 1.1にCisco社[1]が2009年に発表した通信種別ごとのトラフィック予想を示す。

図 1.1: 各種トラフィックの予想

P2Pトラフィックが全体に占める割合は縮小傾向にあるにもかかわらず、依然としてISPからは疎まれがちである。その理由として、トランジットコスト問題が挙げられる。例えばGoogle など独自にAS (Autonomous System)を持つ大量のトラフィックを生み出す企業とはISPが直接ピアリングをすることでトランジットを回避することが出来るが、P2P通信に対してはこうした対策を取ることが出来ない。そのため、ISPの中にはP2P通信に対して帯域制限を実施 [2]しているところも存在する。しかし、帯域制限に対してはユーザから不評を買うことも

(7)

第 1 章序論

あり対応が難しい。こうした状況に対して、P2Pトラフィックの制御に関する研究は数多くあり、代表例としてP4P [3]が挙げられる。P4PではISPがエンドホストでは把握することが難しい情報を提供することでより効果的なピア選択を可能にしている。

1.2 研究の目的

第1.1節で述べたように、ISPにとってP2Pトラフィックを制御しトランジットを減らすことは大きな意味を持つ。本研究では世界的に広く使われているP2Pプロトコル [5]である

BitTorrent [6]を使い、P2P通信により発生するトランジットコストを削減することを目的と

する。BitTorrentのトラッカーにAS番号情報を記録する機能を持たせ、接続するピアを制限することでこれを達成する。

1.3 _{本論文の構成}

本論文は以下の章により構成される。

第1章序論

本研究の概要について述べる。

第2章 P2P

P2Pについて解説する。

第3章 P2Pトラフィックの制御に関する取り組み

P2Pトラフィックを制御する取り組みについて紹介する。

第4章提案手法

提案手法について述べる。

第5章実証実験

実験により本提案を検証する。

第6章結論

本論文の結論を述べる。

(8)

第 2 章 P2P

2.1 P2P _の概要

P2Pモデルでは、P2Pネットワークに参加するすべての端末(ピア)が対等な関係にあり、相互に直接通信を行う。クライアントサーバモデルと異なりサービスの提供が一元化されていないため、クライアントサーバモデルで問題となるサービス提供元であるサーバやネットワークの負荷集中問題を回避することができる。

2.1.1 クライアントサーバモデルの特徴

クライアントサーバモデルはWebの発展に伴い、Webサーバとブラウザを搭載したマシンに機能が明確に別れた頃から主流になった。 [7]

クライアントサーバモデルでは、サービス提供側とサービス享受側が明確に分かれているため、以下のような利点と欠点がある。

利点

• サーバ側でクライアントの一括管理が可能

• 課金サービスモデルの構築が容易

• クライアントに対して要求される性能を抑えることが出来る欠点

• サービス要求数の増加に伴い、サーバおよびネットワーク負荷が集中してしまう

• 負荷の集中に対しサーバの処理能力を向上させるなどの対策を取るためにコストがかかる

• サーバがダウンすることで、サービスの提供が停止してしまうクライアントサーバモデルの仕組みを図 2.1に示す。

(9)

第 2 章 P2P

図 2.1: クライアントサーバモデル 2.1.2 P2Pモデルの特徴

P2Pモデルは個々のピアが相互に直接接続する水平分散システムであり、以下のような利点と欠点がある。

利点

• P2Pネットワークに参加するピア数が増加しても、各ピアで負荷が分散される

• ピアに要求されるマシンの仕様が低く敷居が低い

• 一部のピアがダウンした場合においても、他のピアに接続することでサービスの提供を受けることが出来る

欠点

• 各ピアが相互に接続するため、管理が困難である

• P2Pネットワークが悪意のあるウイルスに感染すると感染活動を止めることが困難

2.2 P2P の通信形態

P2Pの通信形態は大きく分けて以下の4つに分類される。

2.2.1 ハイブリッドP2P

ハイブリッドP2Pでは、各種ファイルのメタデータを中央サーバで管理し、ファイル自体は各ピアが保有する。共有するファイルデータのやり取りは各ピア同士で行うが、ピア検索と応

(10)

第 2 章 P2P

答は中央管理サーバが行う。クライアントサーバモデルとP2Pモデルの両方の特徴を持つためハイブリッド型と呼ばれている。中央管理サーバがダウンするとサービスが停止してしまうが、中央管理サーバの役割は、ピアがアップロードしたメタデータの蓄積、ピアからの検索要求によるメタデータの検索、メタデータのピアへの提供に限られるため、サーバにかかる負荷は低い。また、中央管理サーバでピアの情報を管理しているため、認証や課金機能を備えることが可能であり、商用サービスとしての利用に向いている。BitTorrent、Napster、放送型P2P はこの方式を利用している。

ハイブリッドP2Pモデルを図 2.2に示す。

図 2.2: ハイブリッドP2Pモデル

2.2.2 ピュアP2P

サーバを持たない形態であり、インデックス情報を各ピアが少しずつ保持している。そのため、目的のファイルを持つピアを検索する場合には、つながっているピアから順々に他のピアに検索を転送してもらうことで、目的のファイルを持つピアからの返答を待つ仕組みである。

インデックス情報を個々のピアが分散して所持しているため、ファイル検索能力が低いという欠点がある。Gnutella,Winnyなどはこの方式を利用している。ピュアP2Pモデルを図 2.3に示す。

2.2.3 スーパーノード型P2P

中央管理サーバが存在しない場合において、処理能力の高いピアがサーバの役割を担うことでハイブリッド型とピュア型のメリットを併せ持ち、スケーラビリティや耐障害性を高めた形

(11)

第 2 章 P2P

図 2.3: ピュアP2Pモデル

態である。KaZaAやSkypeがこの方式を利用 [8]している。スーパーノード型P2Pモデルを図 2.4に示す。

2.3 代表的な P2P ソフトウェア

ここでは代表的なP2Pソフトウェアを紹介する。BitTorrentに関しては別途 2.4節で紹介する。

2.3.1 Winny

Winnyは日本国内で開発されたピュアP2P型のファイル共有ソフトウェアである。Winny

の登場は日本国内の通信トラフィックの流れに大きな影響を与え、上りトラフィックが急増した。これは、P2P通信モデルの特徴であるギブ・アンド・テイクの考えに従ったものである。

Winnyの主な特徴として、通信の暗号化、キャッシュ拡散による転送効率の向上、回線速度に

応じた階層化機能と検索ファイルによるクラスタリング機能が挙げられる。これら機能の実装により、高い匿名性とキャッシュを利用した効率の良いファイル共有を実現している。以上の特徴から日本国内において非常に高い人気があったが、違法ファイルの蔓延、度重なる情報漏えい事件やユーザの逮捕などを背景に社会から問題視され、利用者は減少傾向にある。

(12)

第 2 章 P2P

図 2.4: スーパーノード型P2Pモデル 2.3.2 BBブロードキャスト

ハイブリッドP2P型オーバーレイマルチキャスト技術を利用したTVバンク社の大規模動画配信サービスである。動画配信はライブストリーミング形式で行われ、ファイルはメモリ上のみで展開されるため、コンテンツファイルがユーザのディスク領域に一切残らず、コンテンツのコピー対策となっている。IPマルチキャストとは異なり、サーバから送信されたデータをアプリケーションレイヤで他のクライアントに転送するため、複数の異なるISP網を経由して利用することができる。ユニキャスト時に必要な配信コストに比べて約5分の1のコストで最大同時視聴者数25,302人 [9]を実現している。

2.3.3 Skype

Skypeはスーパーノード型P2PモデルのIP電話ソフトウェアであり、2010年6月時点で登

録ユーザ数は約5億6000万人である。スーパーノードはグローバルIPアドレスを持つ、CPU 性能が高い、大容量メモリを持つなどの条件を満たすクライアントから自動的に選択され、管轄するグループに属するユーザ情報を保持する。また、スーパーノードの負荷が高まると自動的に新しいスーパーノードが生まれ負荷が分散される仕組みになっている。Skype同士のインターネット通話は無料であり、利用可能な端末も豊富で世界中で人気[10]がある。

(13)

第 2 章 P2P

2.4 BitTorrent

BitTorrentは、ブラム・コーヘン (Bram Cohen) により開発されたP2Pを用いたファイル

転送用のプロトコル及びそのソフトウェアである。全世界的に人気があり、2009年のipoque 社の調査 [5]によると一部地域を除いてBitTorrentが最も利用されているP2Pプロトコルである。多くのインデックスサイトが存在し、検索が容易であることも人気の理由のひとつであり、

CentOSやFedoraといったLinuxディストリビューションはBitTorrentで配布されている。

2.4.1 BitTorrentの用語

BitTorrentで使用される用語を表2.1に示す。

表 2.1: BitTorrentで使用される用語

用語意味

TorrentファイルトラッカーのIPアドレスや本体ファイルのメタ情報を保持する

拡張子.torrentの小さなファイル

トラッカー(Tracker) P2Pネットワークに参加している各ピアのIPアドレスやダウンロード状況を管理するサーバ

シーダー(Seeder) 完全なファイルを持ちファイルを配布するピア

リーチャー(Leecher) ファイルをダウンロード中のピア

チョーク(Choke) 接続しているピアに対するアップロードを禁止すること

アンチョーク(Unchoke) 接続しているピアに対してアップロードを許可すること

2.4.2 BitTorrentの特徴

BitTorrentはハイブリッドP2Pモデルに分類され、トラッカーと呼ばれるサーバがファイ

ル共有に参加しているピアやコンテンツを管理する。配布されるコンテンツ自体は小さなピースに分割され、ピア同士のファイル共有はピース単位で行われる。そのため、あるファイルを共有する際、分割されたピースを複数のピアからダウンロードした後に合わせることが可能であり、高速なダウンロードを実現している。また、人気のあるファイルほどファイル共有に参加しているピア数が多いためダウンロード速度は早くなる。

ピアとトラッカーの通信

ピアとトラッカーの通信はHTTPベースで行われ、ピアは表 2.2に示す情報をトラッカーに対して送信し、これに対してトラッカーは表2.3に示す情報をピアに返す。ピアとトラッカー

(14)

第 2 章 P2P

の情報更新間隔はintervalで指定され、ピアはこれに従いリクエストを送信する。

表 2.2: ピアがトラッカーに対して送信する情報

種類内容

TorrentファイルトラッカーのIPアドレスや本体ファイルのメタ情報を保持する

拡張子.torrentの小さなファイル

info hash 共有したいファイルのハッシュ値

peer id ピア(BitTorrentクライアント) のID

port ピア(BitTorrentクライアント) が利用するポート番号

uploaded ファイル共有を開始してからアップロードした合計バイト数

downloaded ファイル共有を開始してからダウンロードした合計バイト数

left ダウンロード残りバイト数

表 2.3: トラッカーがピアに対して送信する情報種類内容

interval 再びトラッカーにリクエストを送るまでの送信間隔

complete シーダーの数

incomplete リーチャーの数

peers ファイル共有に参加しているピアの一覧

ファイル共有アルゴリズム

BitTorrentではファイル共有アルゴリズムとして、「ダウンロードする代わりにアップロード

をしなければならない」という規則(Tit-for-tat戦略)を採用している。これにより貧弱なネットワークを持つものもファイル配布に貢献することになり、すべてのピアが強制的に平等な立場でファイル共有を行うことになる。アップロードをするピアが増えることにより、結果として全体のダウンロード速度が向上する。Tit-for-tat戦略を実現するためのアルゴリズム(チョークアルゴリズム)について説明する。

基本的なチョークアルゴリズム各ピアは、一定数のピアに対してアンチョーク状態にする。

アンチョークするピアの数はデフォルトで4つである。アンチョークするピアの選択は、直近 20秒の平均ダウンロード速度によって決まる。チョーク状態とアンチョーク状態の切り替えは頻繁に行われると効率が悪いため、10秒ごとに設定されている。

(15)

第 2 章 P2P

楽観的アンチョーク戦略単純にダウンロード速度だけを元にしたチョーク判定では、より有効なピアの発見を妨げることに繋がる。そこで、アンチョークしている4つのピアのうち1つを30秒ごとに楽観的アンチョーク戦略に基づき決定する。楽観的アンチョーク戦略によって選ばれるピアは、その時点でピアが保持しているピアのリストから順々に選ばれる。

反冷遇主義戦略ファイルが完全にダウンロードされていないときに、他のピアにピースをアップロードしているにもかかわらず、接続しているピアからチョーク状態にされることがある。1分以上、アンチョーク状態のピアからピースをダウンロード出来なかった場合には「自分は冷遇されている」と判断し、そのピアをチョークした上で今後一切アンチョークしないようにする。

アップロードオンリーすべてのピースをダウンロードし終わると、ダウンロード速度を元にしたチョークアルゴリズムに従う必要がなくなり、アップロード速度が速いピアをアンチョーク状態にする戦略に変更する。これにより、他のピアのダウンロード効率が上がり、全体にファイルが行き渡る速度が早くなることになる。

(16)

第 3 章

P2P トラフィックの制御に関する取り組み

3.1 トランジットとピアリング

各ISPは自立したネットワークを抱えており、各ネットワークはAS (Autonomous System) と呼ばれる。AS番号は各ASに割り振られる番号でありネットワークの識別に使用される。各 ISPが管理するネットワークを他のISP等が抱えているネットワークと接続する方法は、トランジットかピアリングの2通りである。トランジットはトラフィック交換を行なっていないAS への到達性を確保するために上位ISPに接続することであるが有償接続である。一方、ピアリングはプライベートピアリングとIX (Internet eXchange)によるピアリングの2通りに分類できる。プライベートピアリングはISP同士がトラフィック交換を目的として互いに接続することで無償接続が一般的である。IXによるピアリングとは、IXが持つL2あるいはL3のスイッチに対して接続し、他のISPとのトラフィック交換を可能にするサービスであり、接続料をIX に対して支払うことで利用できる。第 1.1節で述べたように、トラフィックの増大により中小 ISPはトランジットコストの増加という問題を抱えており、トランジットコストを抑えるために、通信は各ISPが抱えるネットワーク内で完結することが望まれる。

3.2 P4P

P4P (Provider Portal for P2P)は、ISPがP2Pに協力することでP2Pトラフィックによるネットワーク負荷を軽減する取り組みである。2007年にDCIA (Distributed Computing Industry Association) [11]において発足したP4P Working Groupで最初の検討が行われた。尚、P4P WGのメンバーにはAT&T, BitTorrent, Cisco Systems, Verizon, Yale Universityなど多くの団体が参加している。P4Pでは、エンドホストでは得ることの出来ない情報をISP側が提供することによって、効率の良いP2P通信を可能にする。ISPの情報提供はiTrackerと呼ばれるポータルサーバを介して行われる。iTrackerはXMLで記述された3つのインタフェース

(17)

第 3章 P2Pトラフィックの制御に関する取り組み

(info/policy/capability)を提供する。各インタフェースに関しては表 3.1にまとめる。P2Pクライアントや、P2Pクライアントを管理するサーバ(appTracker) はiTrackerから情報を受け取ることで、効率性を考慮したピア選択を行うことができる。文献[3]によると、P4Pを用いることで従来のP2Pに比べて転送速度とリンク利用率を約50〜70％改善できたとしている。

表 3.1: iTrackerが提供するインタフェースインタフェース内容

info ISPが管理するネットワーク内に存在しているピア候補に対して、ネットワークトポロジやステータスを提供する。IPアドレスをキーとして、ISPのIDであるISPのIDであるASID (例えばAS番号)、ノードグループに対して割り当てられる曖昧なPID、仮想的または地理的な位置情報であるLOCが提供される。

policy ネットワークのポリシーやガイドラインを提供する。上りトラフィッ

クと下りトラフィックのバランスに関するポリシーや、ピーク時間を避けて利用してもらうといったリンク利用時間に関するポリシーなどである。

capability ISPが提供可能な機能を提供する。CoS (Class of Service)やネットワーク内の既設サーバを示す等である。

3.3 Region Tracker

リージョントラッカー[12] は一定の範囲ごとにトラッカーを配置し、接続要求を出したピアが近くのピアと優先的に接続される手法であり、効果的なピア選択を実現している。リージョントラッカーでは、プライベートドメイン名を用いており、ネットワーク管理者はプライベートドメイン名からリージョントラッカーを名前解決できる。クライアントはダウンロードを開始する前にアドレスが、プライベートドメイン名であるリージョントラッカーをトラッカーリストに追加する必要があるが約10行程度のコードを追加するだけで良い。リージョントラッカー利用時のクライアントの動作シーケンスは以下のとおりである。

1. プライベートドメイン名のクエリメッセージをリージョンDNSに送る

2. DNSからリージョントラッカーのアドレスが返される

3. リージョントラッカーと通常のトラッカー双方に接続する

(18)

第 3章 P2Pトラフィックの制御に関する取り組み

3.4 IP アドレスの比較によるピア選択法

早稲田大学の出井勝弘の2009年度修士論文「BitTorrentにおける効率的なピア選択法」[13]

では、先行研究 [14]を改良し、BitTorrentにおけるピア選択の指標に国情報、AS番号情報、

ネットワークプレフィックスを利用している。さらに、サブネットワーク内にトラフィックを閉じ込めるために、IPアドレス同士の近傍性を予測することでより狭い範囲にトラフィックを閉じ込めることを実現している。IPアドレスの近傍性予測にはIPアドレスを2進数に変換した後に、IPアドレス同士のロンゲストマッチを取っている。IPアドレスの2進数への変換例を図3.1に示す。

図 3.1: IPアドレスの変換例

トラッカーのピア検索範囲は狭い範囲から順々に広げていくよう実装されているため、シーダーが存在する最小範囲で通信を閉じることが出来る。逆にシーダーが近くに存在しなかった場合には、ピア検索範囲が広くなってしまうため通信局所性を高めることが出来ない。

(19)

第 4 章提案手法

4.1 _{通信の局所性}

BitTorrentを用いた研究ではシーダーの存在が非常に重要であり、第3章で紹介した通信局

所性を求める研究の中にはシーダーが存在する範囲で局所性を実現しているものがある。しかし、シーダーが存在する範囲までピア検索範囲を広げてしまってはトラフィックをローカルに閉じ込める効果は薄い。そこで、本研究ではシーダーの所在に左右されずに通信局所性を高める手法を提案する。また、本提案はクライアントに変更を加えることなく、トラッカーの実装のみで実現可能であり、導入が容易であるという利点を持つ。

本提案では、2.4.2で紹介したトラッカーの基本機能に加え以下の機能を付加した。

• トラッカーに接続してきたピアのIPアドレスからAS番号を取得する

• AS内に存在するピアの数によりピアリストに含まれるピア候補を制限する

4.2 ピアの所属する AS 番号の取得方法

AS番号の取得にはASLOOKUP[19]を利用した。トラッカーは接続要求を受けたピアのIP アドレスを引数にしてASLOOKUPを実行することでAS番号を得る。コマンドの使用例を以下に示す。オプションとして r をつけることにより、IPアドレスを引数にJPNIC [20]、

APNICのwhois databaseを検索し、該当したネットワーク情報とAS番号情報を出力する。

¶ ³

# aslookup -r 133.9.81.1 Target Address : 133.9.81.1

133.9.0.0/16: AS17956:WASEDA University

µ ´

(20)

第 4章提案手法

4.3 ピアリストの決定方法

通常、クライアントからピアリストの要求を受けたトラッカーは、保持しているデータベースからランダムにピアを選択しピアリストとして返す。含まれるピア数はクライアントからの指定数もしくは50である。今後、これをランダム手法と呼ぶことにする。

本提案では、ピアに対してトラッカーから渡されるピアリストを制限する。この制限は、各ピアが所属するAS内に存在するピア数、および各ピアに対して設ける階級によって決定される。ピアの階級は、各AS内で最初にファイル共有に参加した1つのピアだけを上位ピアとし、

後から参加した他のピアをすべて下位ピアとする。ただし、上位ピアに設定されたピアがファイル共有から離脱した場合には、離脱したピアが所属していたAS内における下位ピアがランダムに1つ選ばれ、上位ピアに昇格する。階級ごとに返されるピアリストを表4.1に示す。

表 4.1: 階級に応じたピアリスト一覧リストの種類リストに含まれるピアの候補

上位のピアに対して渡すリスト階級が上位である他のASに属するピア、

および同一AS内に属する下位ピア下位のピアに対して渡すリスト同一AS内に存在するすべてのピア本提案手法により、制限されたピア同士の通信モデルを図 4.1に示す。

(21)

図 4.1: ピア同士の通信モデル

(22)

4.4 通信シーケンス

本提案の通信シーケンスを図 4.2に示す。

図 4.2: 本提案のトラッカーとピア間の通信シーケンス

1. ファイルを共有したいピアはトラッカーがデータベースに保持している他のピアのIPアドレス情報を要求する。

2. トラッカーは接続要求のあったピアが所属しているAS番号を確認し、そのAS内に存在するピアの数を確認する。ピアの数が1つ、つまり接続要求のあったピアがAS内で最初に参加したピアであるならば、そのピアを上位ピアとし、それ以外であれば下位ピアとし、階級に応じたピアリスト(表 4.1)をピアに返す。

3. ピアはトラッカーから返された情報を元に他のピアと通信を行う。

4. その後ピアはトラッカーに対して定期的に通信状況を報告し、トラッカーはデータベースを更新する。

(23)

第 5 章実証実験

本実験では、提案手法を実装することによりAS間通信量が削減されることを示す。

5.1 実験の環境

実験は以下の環境で行った。

• トラッカー1台 (CentOS 5.6)

• シーダー1台、リーチャー17台 (すべてPlanetlab[21]上のノード)

• 500MBの共有ファイル、ピースサイズ256KB

BitTorrentトラッカーとして、Opentracker[22]を構築した。OpentrackerはPHPおよびMySQL で動作するトラッカーである。Planetlabは世界中の大学、研究機関、企業が参加する大規模テストベッドであり、本実験では適切な5つのASを選択し、そこに所属する18個のノードを利用した。本研究で利用したノードの配置を図 5.1に示す。

5.2 実験の結果

実験は提案手法を実装した場合と、OpenTrackerのデフォルト設定であるランダム手法の場合の2通りを行った。実験の結果を以下に示す。

5.2.1 通信局所性

各リーチャーがどこからどれだけデータをダウンロードしたのかを表に示す。提案手法の結果を表 5.1に、ランダム手法の結果を表 5.2に示す。表のピア番号は各ピアが所属しているAS

(24)

第 5章実証実験

図 5.1: ノードの配置図

を分かりやすくするために、「A-1, B-1」のように「AS-ピア番号」の形で表記してある。また、

すべてのピアがダウンロードを完了するまでのAS間通信量の合計を図5.2に示す。結果から、

通信局所性に関しては提案手法が優れていることがわかる。本実験ではランダム手法に比べて AS間通信量を60％程度削減することができている。尚、ダウンロードした合計ピース数が各ピアで異なっているが、これは同一ピースを別々のピアからダウンロードすることがあるためである。

(25)

図 5.2: ダウンロード元とダウンロード量の関係

(26)

表 5.1: 提案手法における各ピアのダウンロード元とダウンロード量の関係(単位: ピース)

ピア番号 AS内 AS外

A-1 2,012 0

A-2 0 2,001

A-3 2,017 0

B-1 2,012 0

B-2 2,011 0

B-3 2,018 0

B-4 2,027 0

B-5 2,014 0

B-6 2,010 0

B-7 0 2,008

C-1 2,000 0

C-2 0 2,002

D-1 2,007 0

D-2 2,007 0

D-3 0 2,000

E-1 2,000 0

E-2 - -

E-3 2,000 0

表 5.2: ランダム手法における各ピアのダウンロード元とダウンロード量の関係(単位: ピース)

ピア番号 AS内 AS外

A-1 239 1,777

A-2 986 1,040

A-3 261 1,758

B-1 749 1,269

B-2 1,059 961

B-3 1,279 744

B-4 1,204 823

B-5 939 1,083

B-6 1,245 782

B-7 1,353 676

C-1 205 1,811

C-2 171 1,845

D-1 416 1,592

D-2 120 1,885

D-3 334 1,700

E-1 1,931 69

E-2 - -

E-3 1,919 81

(27)

5.2.2 ダウンロード速度

各ピアがダウンロード完了までに要した時間を表 5.3に示す。この結果から、提案手法はランダム手法に比べて数倍の時間がかかっていることがわかる。特に、ピアA-1〜A-3に関しては、上位ピアがボトルネックとなったためにランダム手法の場合に比べて大幅に時間がかかっている。このことから、通信局所性だけを求める場合であれば提案手法で問題は無いが、ダウンロード速度の向上を求めるならばダウンロード速度に応じて上位ピアを変更するといった工夫が必要である。

表 5.3: 各ピアがダウンロード完了までに要した時間(単位: 秒) ピア番号提案手法ランダム手法

A-1 1,764 215

A-2 1,768 267

A-3 1,764 158

B-1 605 191

B-2 628 189

B-3 579 228

B-4 635 255

B-5 594 178

B-6 655 236

B-7 631 355

C-1 641 226

C-2 296 190

D-1 307 109

D-2 266 48

D-3 276 293

E-1 16 17

E-2 0 0

E-3 16 15

(28)

第 6 章結論

6.1 _まとめ

本研究では、BitTorrentのトラッカーが保持する情報にピアのAS番号情報を付加し、各ピアに階級を設けピアの接続先を制御することでBitTorrentのファイル共有によるAS間通信量を削減する方法を提案した。実証実験において通信局所性およびダウンロード速度について評価を行った結果、AS間通信量を60％程度削減することが出来た一方で、ダウンロード時間は最も悪化したピアの場合には数倍長くかかってしまう結果となった。これらのことから、利用されるシーンによりピア接続範囲の制限を緩めるなど柔軟な対応が必要である。

6.2 今後の課題

今後の課題を以下に挙げる。

• 今回は局所性を重視したが、ダウンロード速度も向上させたい場合には、ダウンロード速度に応じてピアの接続範囲を広げる等の工夫が必要である。

• 他のASと接続するピアを制限しているため、外部と接続するピアのスペックが低い場合にはボトルネックとなってしまう可能性があり、ダウンロード速度などに閾値を設けるなどして外部と接続するピアを柔軟に変更するなどの工夫が必要である。

• ピア数が増加した場合のトラッカーの負荷を検討する必要がある。特に本提案の中でピアのAS番号取得の際に発生する遅延が及ぼす影響を考察する必要がある。

• 厳密にトランジットコストを削減することを考える場合、AS間の接続形態がピアリングであるかトランジットであるかを判別する必要がある。

(29)

謝辞

本修士論文の作成にあたり日頃より御指導を頂いた早稲田大学理工学部の後藤滋樹教授に深く感謝致します。そして、BitTorrentに関する研究を進めるに上で貴重なアドバイスを頂いた出井勝弘氏、佐藤圭氏、高田和也氏に心より感謝致します。最後に、研究室で共に助け合い励ましあった同期である石井翔氏、川口敬氏、高野弘子氏、高田綾香氏、戸部和洋氏、劉亦晨氏、

多大なる御協力を頂いた後藤研究室の諸氏に感謝致します。

(30)

参考文献

[1] Cisco社, The Cisco Visual Networking Index

http://www.cisco.com/en/US/netsol/ns827/networking_solutions_sub_solution.html [2] ISP規制情報

http://isp.oshietekun.net/

[3] Xie, H., Yang, Y.R., Krishnamurthy, A., Liu, Y., and Silberschatz, A.,

P4P: Provider Portal for Applications , ACM SIGCOMM 2008, pp.351-362.

[4] Xie, H., Yang, Y.R., Krishnamurthy, A., Liu, Y., and Silberschatz, A., P4P: Explicit Communications for Cooperative Control Between P2P and Network Providers

www.dcia.info/documents/P4P_Overview.pdf

[5] ipoque社, Internet Study 2008/2009

http://www.ipoque.com/resources/internet-studies/internet-study-2008_2009 [6] BitTorrent

http://www.bittorrent.com

[7] 江崎浩, 『P2P教科書』, インプレスR&D, 2007.

[8] 池嶋俊,『入門Skypeの仕組み無料IP電話を支えるピアツーピア技術』,日経BP社, 2005.

[9] BBブロードキャストの特長

http://www.tv-bank.com/jp/enterprise/bbbroadcast/features.html

[10] Skype、収益20%増の$860Mに。有料ユーザー数19%増 (TechCrunch) http://jp.techcrunch.com/archives/20110307skype-revenue-up- 20-percent-to-860m-in-2010-paid-users-up-19-percent/

[11] DCIA

http://www.dcia.info/

(31)

参考文献

[12] Gong, C., Chunming, W., Ming, J., Region Tracker: An eﬀective way to localize Bittor- rent traﬃc , Wireless Communications Networking and Mobile Computing (WiCOM), Sept. 2010, pp.1-4.

[13] 出井勝弘, BitTorrentにおける効果的なピア選択法 , 早稲田大学大学院基幹理工学研究科情報理工学専攻2009年度修士論文, 2010.

[14] 魏元, P2Pトラフィックの効率的制御法 ,

早稲田大学大学院基幹理工学研究科情報理工学専攻2008年度修士論文, 2009.

[15] Liu, B., Cui, Y., Lu, Y., and Xue, Y., Locality-Awareness in BitTorrent-Like P2P Applications , IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 11, NO. 3, APRIL 2009, pp.361–371.

[16] David R. Choﬀnes and Fabian E. Bustamante, A Practical Approach to Reducing Cross- ISP Traﬃc in Peer-to-Peer Systems , ACM SIGCOMM Computer Communication Re- view, Volume 38 Issue 4, October 2008.

[17] Pouwelse, J., Garbacki, P., Epema, D., and Sips, H., The Bittorrent P2P File-Sharing System: Measurements and Analysis , International Workshop on Peer-to-Peer Systems (IPTPS), 2005.

[18] 松田一仁, 長谷川剛, オーバレイルーティングに起因するISP間トランジットコスト削減手法の提案および評価 , 電子情報通信学会技術研究報告. NS, ネットワークシステム 110(39), pp.7–12, 2010-05-13.

[19] AS Number Lookup Utility http://aslookup.bgpview.org/

[20] JPNIC, JPIRR 登録者・利用者向けページ

http://www.nic.ad.jp/ja/ip/irr/

[21] PlanetLab

http://www.planet-lab.org/

[22] OpenTracker

http://www.whitsoftdev.com/opentracker/

BitTorrent における局所性を優先したピア選択法

2011 年度 修士論文