シーダを保証する Location Based クラスタリングによる P2P 動画配信
提出日： 2012 年 1 月 31 日
指導：後藤滋樹教授
早稲田大学 基幹理工学研究科 情報理工学専攻 学籍番号： 5110B074-7
高田 和也
第1章 序論 5
1.1 研究の背景 . . . . 5
1.2 研究の目的 . . . . 5
1.3 本論文の構成 . . . . 6
第2章 P2P 7 2.1 P2Pの概要 . . . . 7
2.1.1 P2Pのメリット . . . . 8
2.1.2 P2Pのデメリット. . . . 8
2.2 P2Pの通信形態 . . . . 9
2.2.1 ハイブリッド型 . . . . 10
2.2.2 ピュア型 . . . . 10
2.2.3 スーパー・ノード型 . . . . 12
2.3 BitTorrent . . . . 13
2.3.1 用語 . . . . 13
2.3.2 トラッカー . . . . 14
2.3.3 BitTorrentのアルゴリズム . . . . 15
2.3.4 動作概要 . . . . 16
2.4 通信局所性を高めたP2P . . . . 17
2.4.1 P4P . . . . 17
2.4.2 国情報，AS情報，IPアドレスを利用する手法 . . . . 18
2.5 P2Pを利用した動画配信 . . . . 18
第3章 クラスタリング 19 3.1 クラスタリングの概要 . . . . 19
3.2 ハードクラスタリング . . . . 20
3.2.1 k-means法. . . . 20
3.2.2 スペクトラルクラスタリング . . . . 21
3.3 ソフトクラスタリング . . . . 21
3.3.1 Fuzzy c-means法 . . . . 21
3.3.2 その他の手法 . . . . 22
第4章 提案手法 23 4.1 既存手法 . . . . 23
4.1.1 地理情報 . . . . 24
4.1.2 クラスタリング手法 . . . . 24
4.1.3 ピース選択手法 . . . . 25
4.2 提案手法 . . . . 26
第5章 提案手法の検証 28 5.1 実験環境 . . . . 28
5.2 実証実験 . . . . 28
5.2.1 クラスタリング実験 . . . . 29
5.2.2 動画データ配信実験 . . . . 34
5.2.3 ピアの近接性測定 . . . . 35
第6章 まとめ 40 6.1 結論 . . . . 40
6.2 今後の課題 . . . . 40
2.1 ハイブリッド型P2Pの動作例 . . . . 10
2.2 ピュア型P2Pの動作例 . . . . 11
2.3 スーパー・ノード型P2Pの動作例 . . . . 12
2.4 トラッカーの動作例 . . . . 14
4.1 インテリジェント・トラッカー動作例 . . . . 24
4.2 参加ノード数に応じたクラスタ数 . . . . 25
5.1 クラスタリング結果 ノード数30. . . . 30
5.2 クラスタリング結果 ノード数200 . . . . 31
5.3 クラスタリング結果 ノード数400 . . . . 32
5.4 クラスタリング結果 ノード数600 . . . . 33
5.5 各クラスタ内で最も遅いノードの平均ダウンロード速度. . . . 35
5.6 クラスタ内通信とクラスタ外通信の平均ホップ数の比較. . . . 37
5.7 クラスタ内通信とクラスタ外通信の平均RTTの比較 . . . . 37
5.8 既存手法と提案手法の平均ホップ数の比較 . . . . 39
5.9 既存手法と提案手法の平均RTTの比較 . . . . 39
2.1 BitTorrentで用いられる用語一覧 . . . . 13
3.1 ハードクラスタリングとソフトクラスタリングの分類 . . . . 19
5.1 参加ノード数に対するクラスタ数・シーダ数．. . . . 29
5.2 各クラスタ内で最も遅いノードの平均ダウンロード速度. . . . 34
5.3 クラスタ内通信コスト . . . . 36
5.4 クラスタ外通信コスト . . . . 36
5.5 既存手法の通信コスト . . . . 38
5.6 提案手法の通信コスト . . . . 38
序論
1.1 研究の背景
インターネットのブロードバンド回線の契約数が増加する中で動画コンテンツなどの大容量 データ配信が盛んになっている．それによって，ユーザはインターネットを利用して多くの情 報を得ることができるが，ネットワークやサーバを維持，管理する立場からすると課題がある．
年々増加の一途を辿っているトラヒックに対応するため，設備増強や利用制限を設ける等の対 策を講じなければならない．そのような状況を踏まえて活用されている技術がCDN (Contents Delivery Network)やP2P (Peer to Peer)である．CDN，P2Pは多量・大容量の情報・コンテ ンツを効率よく配信できるため，コンテンツ配信ビジネスでの利用が増加しており，今後もそ の傾向は続くと考えられる．特にP2Pはスケーラビリティの点で優れており，ユーザ数の増 加に伴う設備増強の負担が少ない．
1.2 研究の目的
P2Pによる配信が注目されている中で，配信方式に関する研究が数多くされている．その中 でも，本研究はP2Pの通信コストを抑える点に着目する．単純なP2Pプロトコルではピア同 士の近接性を考慮することなくピアを選択するために遠距離のトラフィックが発生する．トラ フィックの問題を解決するためには地理情報クラスタリングを用いるのが有効である．ただし 地理情報に頼るだけではシーダが存在しないクラスタが生じる場合がある．本研究は従来の方 法を改善するために，クラスタリング手法にソフトクラスタリングを導入する．そして提案手 法を実証するためにPlanetLab [1]を用いて検証する．
1.3 本論文の構成
本論文は以下の章により構成される．
第1章 序論
本研究の背景，目的，本論文の構成について述べる．
第2章 P2P: Peer to Peer
P2Pの概要，通信形態，BitTorrent，通信局所性を高める取り組みや動画配信について 解説する．
第3章 クラスタリング
クラスタリングの概要，ハードクラスタリング，ソフトクラスタリングについて説明する．
第4章 提案手法
本研究の提案手法を説明する．
第5章 提案手法の検証
提案手法の検証のために実証実験を行う．
第6章 まとめ
本研究の結論を述べるとともに，今後の課題を示す．
P2P
本章では，本研究で利用する技術であるP2Pについて説明する．
2.1 P2P の概要
インターネット上の多くの通信はクライアント–サーバ方式である．この方式では，特定の サーバに複数のクライアントが接続する．すなわち，クライアント–サーバ方式では，サーバ に対して何台も接続されたクライアントが様々な処理を依頼することになる．この依頼に対し て，サーバは集中的に処理し，その処理結果をクライアントに返す．そのため，クライアント が増加したり，処理する情報量が増加したりするとサーバへの負荷は大きくなり，ダウンして サービスの提供ができなくなってしまう事態に陥ることもある．
一方，P2Pはクライアント–サーバ方式と異なり，専用のサーバに依存しない．サーバに依 存しない環境で，クライアント同士が分散的にデータの交換や処理を行う．これによって多数 のクライアントからの処理の要求や，サービスの要求が特定のサーバに集中することが避けら れる．クライアント–サーバ方式でも，クライアントとサーバのコンピュータの１対１通信と 解釈できるが，P2Pの”Peer”とは「対等の立場でネットワークを介して接続されるコンピュー タ」という意味である [2]．従ってP2Pシステムを構成するコンピュータは，すべてクライア ントとサーバを区別することなく，すべてのコンピュータがサーバとしても，クライアントと しても動作するという定義ができる．
2.1.1 P2P のメリット
以下にP2Pのメリットを挙げる [2]．
コスト削減
特定のサーバに依存しないため，機器・管理者・保守・運用の負担が少なくなる．
スケーラビリティ
サーバの機能を各ノードが分散して負担するため，ノード数が増加しても，要求を処理する ノードも増加していくためスケーラビリティに優れる．システムの特定の部分に負荷が集中し ないため，処理の負荷分散につながる．
冗長性/耐障害性
複数のピアでサーバの機能を負担しているため，１つのピアに障害が起きても，他のピアに 及ぼす影響が少ない．分散化されることによって，パケットの紛失・損傷リスクが軽減される．
2.1.2 P2P のデメリット
以下にP2Pのデメリットを挙げる[2]．
無駄なトラフィックの生成
音楽や動画コンテンツ等の共有（ファイル共有）におけるP2P型システムの非効率性は，イ ンターネット上を流れるトラフィックの分析からも顕在化しており，改善の意識が広まってい る．つまり，明らかに無駄なコピー経路になっていたり，通信コストが大きな経路を選択して いることが観測されている．このため，P2P技術を用いたビジネス・アプリケーションにおい ては，制御されたノードを配置することによって，無駄なトラフィックを抑制する動きが出て きている．本研究でもこの点に着目をして，通信局所性を高める手法を採用する．
トランザクションの把握
クライアント–サーバ方式ではサーバ側で情報のやり取り（トランザクション）を把握でき るが，P2Pシステムではピア間でこれを把握することは困難である．企業網や政府ネットにお いてシステム内のトランザクションを正確に把握したいという要求があるため，このような要 求への対応が課題となっている．
セキュリティ
P2Pではノードが情報を発信することができるため，WinnyのウィルスであるAntinnyの ように一度ウィルスにかかると，ウィルスのコピーやPC内のファイルがP2Pネットワークに 発信され情報流出が起きてしまう事例がある．またユーザ側のポート開放により悪意あるユー ザからの情報の盗聴や改ざんされる可能性が高まる．このようにP2Pソフトウェアを利用す る場合には，通常のインターネット利用時よりも注意を払う必要がある．
著作権侵害
他人の著作物を公衆に対して送信する行為は「公衆送信権の侵害」にあたる．P2Pファイル 共有で，音楽や映画のコンテンツデータを共有することにより発生する著作権の権利者の損害 は重大な問題である．P2Pの通信形態によってはP2Pネットワークを管理することが難しく，
一度流出したコンテンツを完全にネットワークから削除することは困難である．
2.2 P2P の通信形態
P2Pの通信形態はインデックス情報の管理方法によって大きく３つに分類できる．インデッ クス情報とはキーとデータの対応表であり，データのやり取りの際に必ず参照されるものであ る．それぞれの通信形態について説明する [2]．
2.2.1 ハイブリッド型
中央に管理サーバ（インデックス・サーバ）が存在するタイプである．このインデックス・
サーバとは，各ノードの保持しているコンテンツの一覧を格納しており，P2Pネットワークに 参加するピアは自分のデータ保持状況をインデックス・サーバに定期的に送信し，取得したい データを持つピアの情報もインデックス・サーバに問い合わせる．それによってピア同士の通 信を開始することができる．この方式は，すべてのノードの情報をインデックス・サーバが一 元管理しているため，検索速度が早いのが特徴である．ただし，インデックス・サーバが故障 するとサービスの提供ができなくなってしまうため，耐障害性はピュア型に劣る．また，シス テムの管理・制御が可能であることも特徴である．この方式を採用している例としては，本研 究で着目するBitTorrent [3]をはじめ，Napster，WinMXが挙げられる．図2.1にハイブリッ ド型の動作例を示す．
図 2.1: ハイブリッド型P2Pの動作例
2.2.2 ピュア型
インデックス・サーバが存在せず，すべての処理はノード間の通信のみで実現するP2P方 式．図2.2にピュア型の動作例を示す．ハイブリッド型の欠点であるインデックス・サーバが 単一故障点となる問題点は本方式では解決している．しかし，各ノードがインデックス情報を
分散して持ち合うため，情報の探索が遅いというデメリットを持つ．各ノードがインデックス 情報を問い合わせる際のメッセージ転送の方式により，非構造化型と構造化型の2つに分類で きる．
非構造化型
インデックス情報を検索するために，手当たり次第に自分が知っているノードに対してメッ セージを送り，情報を保持するノードは返答をし，保持していなければ他のノードにメッセー ジを転送する方式．フラッディング方式とも呼ばれ，動作はシンプルであるがメッセージが増え すぎないように転送回数や生存時間に制限を設ける必要がある．例としてGnutella，Freenet，
Winny，Shareが挙げられる．
構造化型
インデックス情報を検索する際，あらかじめ転送先を構造的に決めておき，キーに対応する 相手が確実にわかるようにした方式．これにより，検索に伴うトラフィックの負荷を極めて軽く することができる．有名な方式として分散ハッシュテーブル (DHT)がある．例としてChord，
CAN，Pastry，Tapestry，Kademlia，OpenDHT，Overlay Weaverが挙げられる．
図 2.2: ピュア型P2Pの動作例
2.2.3 スーパー・ノード型
ピュア型同様，インデックス・サーバが存在せず，すべての処理はノード間の通信のみで実 現するP2P方式．ピュア型と異なるのはスーパー・ノードが存在する点．スーパー・ノードと はP2P通信を行う場合に，一時的にインデックス・サーバの役割を担うノードのことである．
P2Pネットワーク内に複数のスーパー・ノードが存在し，データの所在を探索したり保持した りする．一般に処理能力の高いノードがスーパー・ノードとなる．この方式はハイブリッド型 とピュア型のメリットを併せもち，スケーラビリティや耐障害性があることが特徴．例として
KaZaA，Skypeが挙げられる．図2.3にスーパー・ノード型の動作例を示す．
図 2.3: スーパー・ノード型P2Pの動作例
2.3 BitTorrent
BitTorrentは2001年にBram Cohenによって開発された大容量コンテンツ配信向けファイ ル転送用プロトコル及びその通信を行うソフトウェアである．コンテンツはピースと呼ばれる 小さなデータ単位に分割され，ピース単位でファイル転送を行う．BitTorrentが他のP2Pに比 べ優れている点は以下の３点である [2]．
• ファイルをピース単位に分割し，ピースをハッシュ値で管理するため改竄を防げる
• torrentファイルが信用できるものであれば，ファイル自体も信用できる
• ピース単位でダウンロード後にすぐアップロードを開始するため効率が良い
本論文では先行研究[4]と同様にBitTorrentを用いてシーダを保証するLocation Based Clus- teringによるP2P動画配信手法を提案する．以下，BitTorrentについて説明する．
2.3.1 用語
BitTorrentを説明する上で必要な用語一覧を表2.1に示す [5]．
表 2.1: BitTorrentで用いられる用語一覧
用語 意味
シーダ ダウンロードが完了しているピア リーチャ ダウンロード中のピア
トラッカー ピアのIPアドレスや各ピアのファイル保持状況を管理するサーバ
torrentファイル トラッカーのIPアドレスや本体ファイルの情報が書き込まれたファイル
チョーク状態 アップロードを許可されていない状態 アンチョーク状態 アップロードを許可された状態
スウォーム 同一コンテンツを扱うピアのネットワーク
2.3.2 トラッカー
トラッカーはハイブリッド型P2Pのインデックス・サーバに相当し，ピアはインデックス 情報の検索をトラッカーに委託する．トラッカーはピアの状態を管理する機能を備えたサーバ であり，トラッカーがピアのリクエストを処理してピアリストを返すことでP2P通信が成立 する．ピアリストは，トラッカー側でピア数の上限の数が設定され，ランダムにピアが選択さ れる．トラッカーと各ピアの通信はHTTPを用いてクライアント–サーバ方式で動作する．一 方，ピア同士の通信ではBitTorrent独自のプロトコルで動作し，TCP/IPセッション上で双方 向にバイナリ形式で直接データのやり取りをする．図2.4にトラッカーの動作例を示す．
図 2.4: トラッカーの動作例
1. ファイルのSHA1ハッシュ値を元にピアリストの要求と開始通知を送る 2. ファイルを保持するピアのリスト（ピアリスト）を送る
3. ピア同士の通信開始
4. クライアントのステータスを定期的にトラッカーへ通知 5. ダウンロードが完了すると完了(complete)通知を送信 6. クライアントを終了すると終了通知を送信
2.3.3 BitTorrent のアルゴリズム
BitTorrentの高効率なファイル配信を支える，ピア選択アルゴリズムとピース選択アルゴリ
ズムについて説明する．
ピア選択アルゴリズム
P2Pシステムではファイルの供給者と利用者は各ピアに分散され，各ピアはファイルの利用 者であると同時にファイルの供給者でもある．そこで，どのピアと通信するかが効率の良し悪 しに影響する．BitTorrentではチョークアルゴリズムを利用することでファイル配信効率の向 上を狙っている．
BitTorrentにおいてファイルのダウンロード要求をするのは表2.1に示したようにリーチャ
である．リーチャはトラッカーから受け取ったピアリストから複数のダウンロード先を決める．
ダウンロード速度は20秒間のダウンロード量の平均を使用する．チョーク状態とアンチョー ク状態が頻繁に切り替わると効率が悪くなるため，10秒ごとにアンチョーク状態のピアを選 択する．しかし，このようにダウンロード速度だけを元にしたチョーク判定では，他の接続先 を新たに発見することができない．そのため，４つのアンチョーク状態のピアのうち，一つの ピアには基本的なチョークアルゴリズム（ダウンロード速度を用いる方法）ではなく，楽観的 なアンチョーク戦略をとる．楽観的なアンチョーク戦略では，30秒ごとに自分が持っているピ アのリストから順番にアンチョーク状態にする [6]．
ピース選択アルゴリズム
ダウンロードするファイルピースの順番は，ダウンロード効率に大きく影響する．例えば，
各ピアに行き渡っていないピースを最後に一斉にダウンロードしようとするとファイル転送効 率が落ちる可能性がある．そのためピース選択アルゴリズムは重要である．標準のBitTorrent では以下の４つのピース選択アルゴリズムでダウンロード順が決定される [6]．
Strict Priority ダウンロード中のピースを完成させるのを優先する戦略．転送はサブピース
(16kB)単位で，並列に複数のピアからダウンロードすることで完全なピースにすること
を目指す．BitTorrentは，完全なピースが取得できるとSHA1ハッシュにより，そのピー スの完全性をチェックする．ピースの完全性を保証するとそのピースははシード（種）と なって他のピアからのダウンロード対象になる．
Rarest First 各ピアが保持するピースのうち最も少ないピースをダウンロードしようとする 戦略．希少ピースは保持しているピアが少ないということなので，ピアの離脱によって そのピースを取得できなくなる可能性が高いピースである．そのため，P2Pネットワー ク内にピースを分散させることでそのリスクを避けることが目的である．
Random First Piece 最初のピースはランダムに選ぶ戦略．ピアがダウンロードを開始する とき，まずは，ひとつのピースを完成させることを優先する必要がある．なぜならば，早 くアップロードを開始できるようになる必要があり，希少ピースを優先すると効率が悪 いためである．
endgame mode 最後のサブピース群の要求は接続する全ピアに送信する．要求に対してどこ かのピアから完全なサブピースを受け取ると，ダウンロード要求を送信した相手のピア にダウンロードのキャンセル要求を送信して終了する．一時的に大きなネットワーク帯 域を消費するが，完全なデータの完成を早めることができる．
2.3.4 動作概要
BitTorrentにおける，コンテンツの公開からユーザがダウンロードするまでの一連の動作を
示す[5]．
1. コンテンツ提供者は配信したいコンテンツとトラッカーの情報を元にtorrentファイルを 作成する．
2. コンテンツ提供者は完全なコンテンツを持つマシンをシーダとしてスウォーム上で稼動 させる．
3. コンテンツ提供者は適当なインデックスサイトでtorrentファイルを配布する．
4. 各ユーザはそれぞれtorrentファイルを取得する．
5. BitTorrentクライアントソフトを利用してtorrentファイルに記述されているトラッカー に対しピアリストの要求をする．
6. トラッカーはユーザからのリクエストに対し，そのコンテンツのスウォームに参加して いるピアをランダムに選択したピアリストをユーザに送る．
7. ピアリストを受け取ったユーザはピアとしてスウォームに参加し，コンテンツのダウン ロードを開始する．
2.4 通信局所性を高めた P2P
通信局所性を高める取り組みとしてP4Pがあり，国情報，AS情報，IPアドレスを利用する 手法も提案されている．以下，それらについて説明する．
2.4.1 P4P
P4PはDCIA [7]内のP4P WGにて議論されている，ISP情報を用いたP2Pトラヒック制 御の枠組みである [8]．P4Pとは「Proactive network Provider Participation for P2P」または
「Provider Portal for P2P」の略称[9]．P4Pの目的は，ネットワークリソースの公平かつ効率 の良い利用とネットワークプロバイダが保守・運用する資源を効果的に活用し，コストを削減 し，収益を増大することである．
P4PはiTrackerと呼ばれるポータルを用意することで目的達成を目指す． 各ネットワーク
(ISPや大学ネットワークなど)は，各々iTrackerを用意する．P2Pクライアントは，各自のネッ トワーク内でのiTrackerのIPアドレスをDNSに問い合わせる．DNSへの問い合わせには新 しい「P4P」レコードタイプが利用される．情報提供用のiTrackerは補助的な情報を提供する だけなのでiTrackerがダウンしてもP2Pは通常の動作で稼働できる利点がある．iTrackerは XMLで記述されたinfo，policy，capabilityの3つの情報を提供する．以下，それら3つの情 報について説明する [9]．
info プロバイダ内に存在するピア候補となるノードの情報．ネットワークプロバイダIDであ
るASID，ネットワークノードグループに割り当てられるPID，仮想的または物理的位
置情報を表すLOCの情報を含む．
policy 希望するネットワークの利用方法の情報．inbound/outboundのトラフィックの割合，
利用を避けて欲しい大まかな時間帯の提示，リンクの利用量に関するポリシーの情報を 含む．
capability ネットワークプロバイダが提供可能な機能の情報．プロバイダが提供できる複数 のサービスクラスを示したり，ネットワーク内の既設サーバを示したりできる．
P4Pの課題として効率化の目標が個々のISP内トラヒックとなっており，バックボーントラ ヒックの効率化が困難な点が挙げられる．現状ではISP毎にiTracker（トポロジ情報サーバ）
を提供しており，今のところ合成方法はスコープ外となっている[8]．
2.4.2 国情報， AS 情報， IP アドレスを利用する手法
BitTorrentのトラッカーを利用したBitTorrentネットワークの制御法として先行研究の地理 情報を利用するもの以外に， [10]や [11]がある． [10]の手法はピアの国情報とAS情報を利 用する．この情報を利用することにより，トラフィックを国内・AS内に閉じ込めようとするも のである．[11]ではIPアドレスを2進数の数値として捉え，近似度を利用する．これにより，
ピアが属するネットワーク・プレフィックスまで考慮でき，さらに狭いネットワーク内でトラ フィックを閉じ込めることができる．これらの研究はトラフィックの制御を主な目的としてお り，提案している手法を用いることで通信局所性を高められることを示している．
2.5 P2P を利用した動画配信
従来のサーバによる配信におけるサーバの負担軽減のために注目を集めているのがP2Pを 利用した動画配信である． [12]や [13]をはじめとして多くの研究がなされている．P2Pを利 用した動画配信で有名なものとしてBitTorrentDNA [14]，Joost [15]がある．以下，それぞれ の概要を説明する．
BitTorrentDNAは2007年に登場したBitTorrentプロトコルを利用するフリーのコンテンツ 配信用ソフトウエアである．BitTorrentベースのためトラッカーがトレントファイルを扱うが，
通常と異なるのは動画配信サーバが存在する点である．動画配信サーバから各ピアに対しオリ ジナルデータのピースが拡散されるため，通常のBitTorrentで発生しうる特定のピースが欠け る問題はない．また，ユーザは専用のクライアントソフトを利用することでトレントファイル やポート開放を意識する必要がなくなるというメリットがある．
JoostはNiklas ZennstromとJanus Friisによって開発されたインターネット・テレビサービ スである．Joostの特徴は配信サーバとP2Pのハイブリッド構成である．配信サーバからのみ 新規コンテンツの配信が始まり，配信経路上のデータストリームはAESで暗号化されるため 著作権保護の観点で信頼性が高い．そのような形態をとるため，配信サーバ群を中心にP2P ネットワークが広がるというトポロジになる．コンテンツのコーデックはH.264を利用してお り，クライアントは最大で1時間に320MBのデータを受信する．ビットレートに換算すると
728kbpsとなる．アップロードのついては1時間に最大105MBで，こちらもビットレートに
換算すると238kbpsとなる[16]．
クラスタリング
本章では，本研究で利用するクラスタリングについて説明する．
3.1 クラスタリングの概要
クラスタリングとは，データの集合を類似度（または非類似度）によって複数のクラスタ
（グループ）に分類するものである．
クラスタリング手法を分類する際，通常，二つの観点に着目する．一つ目は，手法が階層的 か，非階層的かという観点である．本研究においては非階層的手法のみ着目する．二つ目は，
ハードクラスタリングであるか，ソフトクラスタリングであるかという観点である．先行研 究 [4]では前者を利用しており、本研究では後者を利用するため，両者について説明する．代 表的な非階層的クラスタリング手法をハードクラスタリングとソフトクラスタリングに分類し たものを表3.1に示す [17]．
表 3.1: ハードクラスタリングとソフトクラスタリングの分類
分類 手法
ハードクラスタリング k-means，スペクトラルクラスタリング
ソフトクラスタリング Fuzzy c-means，混合分布モデル，pLSI，NMF
3.2 ハードクラスタリング
ハードクラスタリングは各データが属するクラスタを一意に決定する手法であり，一般にク ラスタリングといえば，ハードクラスタリングを指す．ここではハードクラスタリングの代表 的な例としてk-means法（k平均法）とスペクトラルクラスタリングについて説明する．
3.2.1 k-means 法
k-means法は現実のクラスタリングの問題で使われることが多く，実用的な手法である．k-
means法は分類する対象のデータセットとクラスタ数Kを用意する必要がある．それらを入
力とし，以下の手順で処理を実行する [17]．
1. K個のクラスタにおける代表点c1,c2,・・・,cKを適当に作成する．通常，代表点はデータ セットの中からランダムにK個選ぶ．
2. 代表点を重心として，各代表点に近い各データxiを同一グループとしてまとめる．
3. 代表点を各クラスタの重心に更新する．
4. クラスタが変化しなくなるまでグループ分けと重心変更を繰り返し行い，結果が収束し たらクラスタリング終了．
以上のプロセスを数式で示すと，式 (3.1)の評価関数を最小化することに対応する．
∑K
i=1
∑
x∈Ci
||x−ci||2 (3.1)
k-means法の課題として，最初の代表点の選択に結果が大きく依存するために，一度のクラ
スタリングでは最良の結果が得られるとは限らない点が挙げられる．また，式 (3.1)の値は単 調に減少していくが，その値が最小解（大域解）であるとは限らない．式 (3.1)の最小解を求 める問題は, NP困難な問題のため，大域解を求めることは非常に困難である．k-means法によ るアルゴリズムで求められる解は局所解である[17]．しかし，今回の地理情報クラスタリング ではある程度のグループ分けができればよく，高度な分類精度は求めていないため，これらの 問題は大きな影響ではない．
3.2.2 スペクトラルクラスタリング
この手法はクラスタリングをグラフの分割問題として捉える．最適なグラフの分割が，ある 固有値問題の解から得られることを利用する．
スペクトラルクラスタリングでは，最初にデータをグラフのノードとして扱い，ノード間の エッジ（辺）に両端のノードの類似度を重みとして割り当てる．類似度が0の場合はエッジを 張らないようにし，グラフを作成する．ここで評価関数を用いてカットすべき最適なエッジを カットしていきグラフを複数のサブグラフに分割することでクラスタリングできる．評価関数 はMcutやNcut (Min-max cut)，(Normalized cut )といった手法が提案されている [17]．
3.3 ソフトクラスタリング
ソフトクラスタリングでは，ハードクラスタリングが各データの属するクラスタを一意に決 定するのに対し，各データが各クラスタに属する帰属度を求める．通常，帰属度は正規化され るため，クラスタに属する確率とみなせる．ここではソフトクラスタリングの代表的な例であ り、本研究でも利用するFuzzy c-means法について説明し，混合分布モデル，pLSI，NMFに ついて簡単に触れる．
3.3.1 Fuzzy c-means 法
ファジィクラスタリングとはソフトクラスタリングと同義である．ファジィクラスタリング といえば，k-means法を拡張したFuzzy c-means法が有名である．
Fuzzy c-means法の評価関数はk-means法の評価関数である式 (3.1)を拡張する．ここでgic をN 個のデータ (x1,x2,・・・,xN)の任意のデータxiがc番目のクラスタに属したら1，属さな い場合は0とする．この時，式 (3.1)は式(3.2)においてm=1とした場合と同義となる．
J =
∑N
i=1
∑K
k=1
(gik)m||xi−ck||2 (3.2) Fuzzy c-means法は上記のgikを[0,1]の連続値にし，m >1としたものである．ファジィク ラスタリングではクラスタとデータの間に，データがそのクラスタに属する度合（重み）gik
を設定し，評価関数では重みを考慮することで重心の移動を決定する．そのため，データxが クラスタC1とC2のどちらかに属するかを決定してしまう場合に比べて重心の移動が大きくな ることを防ぎ，他のデータの分類への影響も小さくできる．
実際のFuzzy c-means法のクラスタリング処理は以下の2.と3.を収束するまで繰り返す．gik とckを求めることで各データxiがどのクラスタに属するかを判定できる．
1. 初期値c(0)k を設定する．
2. 式 (3.2)において，ckをc(t)k に固定したときに，Jを最小化するg(t)ik を求める．
3. 式 (3.2)において，gikをgik(t)に固定したときに，Jを最小化するc(t+1)k を求める．
Fuzzy c-means法でもk-means法と同様に初期値c(0)k に結果が依存する [17]．
3.3.2 その他の手法
混合分布モデルはクラスタリングの問題を確率モデルで処理するものである．データの発生 が確率モデルに従う場合は有効な手法である．
pLSI (Probabilistic Latent Semantic Indexing)は次元縮約の手法である．次元縮約を行うこ とで，高次元データの次元を下げて妥当な結果を得易くする．縮約する対象としては文書ベク トルが想定されている．pLSIはAspectモデルという文書と単語を結びつける潜在的なクラス を想定したモデルを利用する．
NMF (Non-negative Matrix Factorization)も次元縮約を利用した手法である．想定されてい るデータはベクトル空間モデルで表現された文書データ．NMFではn次元のデータを列ベク トルで表す．データがm個あるとき，データセットはn行m列の行列で表す．ベクトル空間 モデルで表現された文書データの場合，この行列は索引語文書行列と呼ばれる [17]．
提案手法
本研究は先行研究の課題を解決することを目的としている．そのため，先に先行研究の手法 を説明した後に提案手法を説明する．
4.1 既存手法
先行研究[4]は遠距離のトラフィックを削減するために地理情報クラスタリングを用いて通信 局所性を高めている．これを実現させるために用いているのがインテリジェント・トラッカー と呼ばれるBitTorrentトラッカーである．通常のトラッカーは2.3.2節で述べたように，ピア リスト要求に対して応答を作成する際にはスウォームに属するピアをランダムで選択する．一 方，インテリジェント・トラッカーはピアリストを作成する際にピアのIPアドレスから緯度・
経度情報を取得して，その値を利用してクラスタリングをすることでクラスタ内のピアのみ記 す．動作例を図4.1に示す．
インテリジェント・トラッカーによって同一クラスタ内のノード同士のみP2P通信が可能と なるため，地理的に近いピア同士が通信することになり，遠距離のトラフィックを削減する可 能性を高める．可能性と述べたのは，地理的な距離とネットワーク上の距離は一致しないから である．そのため，本研究では，地理情報クラスタリングの有用性を示すために実験を行う．
実験の内容・結果については5.2.3章で述べる．
これから既存手法で用いる手法の詳細を説明する．通信局所性を高めるために用いる地理情 報とクラスタリング手法，ストリーミング動画配信に適したピース選択手法の順に説明する．
図 4.1: インテリジェント・トラッカー動作例
4.1.1 地理情報
各ノードの地理情報の取得にはMaxMind社の提供しているGeoIP [19]を利用する．GeoIP
のGeoLiteCountryデータベースを利用することによりIPアドレスから緯度・経度情報の取得
が可能となる．このデータベースは国，領域，都市，緯度・経度の取得をサポートしている．
GeoIPの最大のメリットはIPアドレスだけでノードの地理情報を取得できる点である．ただ
し，すべてのノードの情報は取得できず，地理情報が得られないノードも存在する．
4.1.2 クラスタリング手法
既存手法ではクラスタリング手法にハードクラスタリングを用いている．ハードクラスタリ ングの中でも3.2.1節で代表的な手法として説明したk-means法ではなく，PAM (Partitioning adound Medoids) [20]という手法を用いている．
PAMはk-medoids法として知られており，k-means法がセントロイドを利用することに対
して，k-medoids法ではメドイドと呼ばれるクラスタの代表要素を利用する．k-means法では 式(3.1)を最小化するデータのクラスタへの割り当てを求める．k-medoids法では式(4.1)が評 価式となる．d(x, bc)は2要素間の非類似度を表し，この非類似度の総和を最小化する方法が
k-medoids法である．ユークリッド平方距離の総和の代わりに非類似度の総和を使うことによ
り，k-means法よりもロバストである．k-medoids法の計算量はO(N2k)と多くなってしまう が外れ値に強いというメリットがある．k-medoids法を採用することにより安定したクラスタ
リング結果を得ることを可能としている[5]．
∑K
i=1
∑
x∈Ci
d(x, bc) (4.1)
また，クラスタリングを行う際に必要となるクラスタ数は，ノード数に応じて設定する．参 加ノード数に応じたクラスタ数を図4.2に示す．これはノード数30の時にクラスタ数4，ノー ド数618の時にクラスタ数15が最適だったために2つの値を基準として設定したものである．
図 4.2: 参加ノード数に応じたクラスタ数
4.1.3 ピース選択手法
通常のBitTorrentクライアントは2.3.3節で示したようにピース選択アルゴリズムとして
Rarest Firstを代表とする，いくつかのピース選択アルゴリズムを採用している．しかし，そ
れらはストリーミング再生を考慮したものではなく，そのままでは動画再生中にピース不在の ため動画が再生できなくなる可能性がある．そこで既存手法で提案されたものがEarliest First である．Earliest Firstはピースを先頭から順番に取得することでスムーズな動画再生を可能と したアルゴリズムである．
4.2 提案手法
本手法の目的は先行研究 [4]において，クラスタリングの際にシーダを含まないクラスタが 生成される場合があるという課題を解決することである．インテリジェント・トラッカーが地 理的に近いピア同士をグループ化するために，先行研究ではハードクラスタリングを用いて いる．ハードクラスタリングでは，要素が一意にクラスタに属するため，地理的な距離が近い ノード同士を一意にグループ化できる．しかし，クラスタ内にシーダが含まれない場合はその クラスタ内のノードは完全なデータを取得できない．そこで，提案手法ではクラスタ内に必ず シーダが含まれるようにするため，クラスタリング手法にソフトクラスタリングであるFuzzy
c-means法（3.3.1節で説明）を用いる．ソフトクラスタリングでは，要素が各クラスタへ属す
る度合（帰属度）が出力となる．以下ではソフトクラスタリングを用いたシーダを保証する地 理情報クラスタリング手法について述べる．
シーダを保証するクラスタリング手法 ピアの群（スウォーム）に属する各ピアがシーダか否 かの判定はトラッカーのアクセスログ情報に含まれるleftの値を用いる．パラメータleftは各 ピアのダウンロード完了までの残りピース数を示しており，シーダの場合はleft=0となる．ま た，地理情報を得るにはMaxMind社の提供しているGeoLiteCountry [19]を利用する．この ライブラリを利用することによりIPアドレスから緯度・経度情報の取得が可能となる．本手 法ではこの緯度・経度情報を利用し，Fuzzy c-means法でクラスタリングを行う．具体的には 以下のようにクラスタへの割り当てを行う．
1. ピアのIPアドレスから緯度・経度の値を取得．
2. 緯度・経度をデータとしクラスタリングを行う．
3. 各ピアを帰属度が最も高いクラスタへ割り当てる．
4. 生成されたクラスタにシーダが含まれるかを判定．
5. シーダが含まれる場合は割り当て完了．
含まれない場合は次に帰属度の高いクラスタへ割り当て，4へ戻る．
また4.1.1節で，GeoIPはすべてのノードの情報を取得できず，地理情報が得られないノード
も存在すると述べたが，提案手法では情報が取得できなかったノードはニューヨーク市の緯度:
40°，経度: 73°に設定する．ニューヨーク市に設定したのは，米国のインターネットユーザ
数が世界屈指であるためである [21]．米国は第２位で，第１位は中国であったが，Planet Lab でノードを利用した時に中国のノードは回線が不安定なものがいくつかあったため，今回は相 対的に信頼性の高いノードの多かった米国の情報を採用する．これによって，地理情報が得ら れないノードはニューヨーク市を含むクラスタに属することとなる．
提案手法の検証
提案手法を検証するために実証実験を行う．実験環境，実証実験の詳細の順に説明する．
5.1 実験環境
提案手法はBitTorrentを採用しているため実験にはトラッカーと複数のピアが必要である．
トラッカーは実機のマシンに実装する．今回はOpenTracker [22]を用いる．OpenTrackerは最 小のリソース利用で動くオープンソースのBitTorrentトラッカーである．また，提案手法で利 用するFuzzy c-means法の実装にはオープンソースのpythonスクリプト [23]を利用する．
一方，実験に用いるピアはPlanetLab [1]のノードを利用する．PlanetLabは世界規模の大規模 分散テストベッドであり，2011年1月の時点で532拠点1089ノードが稼働している．PlanetLab のノードはFedora 8をベースとしたOSを採用しており，通常のLinuxマシンとして操作可能な ため，実験に使うノードとしては最適である．本実験ではこのPlanetLabのノードにBitTorrent のクライアントソフト（今回はBitTornado [24]を利用）をインストールして利用する．
5.2 実証実験
5.2.1節では提案手法のクラスタリング手法を検証し，5.2.2節では提案手法で生成されたク
ラスタ内でのP2P動画配信の検証を行う．さらに，5.2.3節では地理情報クラスタリングの有 用性を示し，提案手法の通信局所性の検証を行う．
5.2.1 クラスタリング実験
この実験の目的は，提案手法によってシーダが保証されているかを確認することである．ク ラスタリングを行う際に参加ノード数に応じて適切なクラスタ数を設定する必要があるが，今 回は，4.1.2章で説明した先行研究 [4]で示された線形関数を利用する．また，適切なシーダの 数は，実環境では状況によって異なるため今回の実験では評価のために全ノード数の20%に設 定して行う．表5.1に実験を行ったノード数，クラスタ数，シーダ数を示す．比較対象として 用いる既存手法にはハードクラスタリングを用いる．本実験で利用するハードクラスタリング
とはFuzzy c-means法によって算出された各ノードの各クラスタへの帰属度が最も高いクラス
タへ割り当てたものを利用する．Fuzzy c-means法はソフトクラスタリングであるが，最も帰 属度が高いクラスタに割り当てることでハードクラスタリングと同様となる [17]．
表 5.1: 参加ノード数に対するクラスタ数・シーダ数．
ノード数 シーダ数 クラスタ数
Case 1 30 6 4
Case 2 200 40 7
Case 3 400 80 10
Case 4 600 120 14
以下にCase 1–Case 4の実験結果を図に示す．
Case 1
図 5.1: クラスタリング結果 ノード数30
シーダに着目すると，オセアニアにシーダが存在しない．しかし，ハードクラスタリングで はオセアニアのノードのみでクラスタを形成している．一方，提案手法では，オセアニアの ノードはクラスタ内にシーダが存在しないため次に帰属度の高いクラスタに割り当てられるこ とになる．その結果，シーダの存在するアジアのクラスタと同一クラスタを形成する．提案手 法における全クラスタ数は既存手法の4に対し3になる．すべてのクラスタ内にシーダが存在 するため，各ノードは完全なデータをダウンロードすることが可能となる．
Case 2
図 5.2: クラスタリング結果 ノード数200
シーダに着目すると，南米にシーダが存在しない．しかし，ハードクラスタリングでは南米 のノードのみで構成されるクラスタが２つある．一方，提案手法では，南米のノードはクラス タ内にシーダが存在しないため次に帰属度の高いクラスタに割り当てられることになる．その 結果，シーダの存在する北米東海岸のクラスタと同一クラスタを形成する．提案手法における 全クラスタ数は既存手法の7に対し5になる．すべてのクラスタ内にシーダが存在するため，
各ノードは完全なデータをダウンロードすることが可能となる．
Case 3
図 5.3: クラスタリング結果 ノード数400
シーダに着目すると，Case 1と同様にオセアニアにシーダが存在しない．しかし，ハードク ラスタリングではオセアニアのノードのみでクラスタを形成している．一方，提案手法では，
オセアニアのノードはクラスタ内にシーダが存在しないため次に帰属度の高いクラスタに割り 当てられる．その結果，Case 3はCase 1よりも多くのノード数で多くのクラスタ数になってい るため，オセアニアクラスタに属していたノードは経度の違いから別々のクラスタへ割り当て られる．オーストラリアのノードは東南アジアのノードを中心とするクラスタに属し，ニュー ジーランドのノードは東アジアのノードを中心とするクラスタに属する．提案手法における全 クラスタ数は既存手法の10に対し9になる．すべてのクラスタ内にシーダが存在するため，各 ノードは完全なデータをダウンロードすることが可能となる．
Case 4
図 5.4: クラスタリング結果 ノード数600
シーダに着目すると，イタリア，ギリシャの付近にはシーダが存在しない．既存手法ではそ の付近のノードで構成されるDのマーカーで記されたクラスタ（クラスタD）が独立してい る．一方，提案手法では，クラスタDのノードはクラスタ内にシーダが存在しないため次に帰 属度の高いクラスタに割り当てられる．その結果，シーダの存在するクラスタC，ポーランド 周辺のクラスタ，ギリシャ・トルコ・エジプト周辺のクラスタへそれぞれ割り当てられる．提 案手法では全クラスタ数は既存手法の14に対し13になる．すべてのクラスタ内にシーダが存 在するため，各ノードは完全なデータをダウンロードすることが可能となる．
実験を行った結果Case1-Case4すべての状況において提案手法を用いることでシーダが保証 できていることを確認した．
5.2.2 動画データ配信実験
提案手法によって生成されたクラスタ内でダウンロード実験を行う．本実験は，P2P動画配 信を想定しているためピアのピース選択アルゴリズムに4.1.3章で述べたEarliest Firsttを実 装したクライアントソフトを使用する．本実験では，標準のBitTorrentにおいてファイル転 送効率を最適化するために採用されているピース選択アルゴリズムを変更するため，ファイル のダウンロード速度低下が考えられる．さらに，クラスタリングによって通信できるピアの選 択肢が減少するため，これによる速度低下も考えられる．そこで，本実験ではクラスタ内P2P 動画配信においてダウンロード速度が配信レートを上回るか検証する．ここで配信レートは
2Mbpsを想定する．この値はYouTubeのHD画質モードの最高画質配信レートである．最も
遅いノードが条件を満たしていれば動画配信には問題のないダウンロード速度であることが示 せる．本実験では実験5.2.1において検証したノード数30の場合のノードを用いてダウンロー ド実験を行う．用いるコンテンツのサイズは200MBのテキストファイルで，ピースサイズは
256kBに設定．256kB=2Mbitであるため，想定した配信レートでは1ピースあたり1秒のコ
ンテンツとなり，約13分の動画コンテンツとして見立てることができる．
表5.2に各クラスタ内で最も平均ダウンロード速度が遅かったノードの結果を示す．表5.2 の結果をグラフで表したものを図5.5に示す．
表 5.2: 各クラスタ内で最も遅いノードの平均ダウンロード速度 アジア・オセアニア 南北アメリカ 欧州 ダウンロード速度
(Mbps) 2.30 7.84 3.60
表5.2の結果より，すべてのクラスタで最も平均ダウンロード速度が遅いピアでも条件とし て設定した配信レート2Mbpsを上回ることが示せた．
図 5.5: 各クラスタ内で最も遅いノードの平均ダウンロード速度
5.2.3 ピアの近接性測定
本実験は，通信局所性を高める手法としての地理情報クラスタリングの有用性を示すために 行う．4.1章で述べたように地理的な距離とネットワーク上の距離は一致しないため，クラス タ内通信とクラスタ外通信のコストを比較することで地理情報の有用性を示す．また，提案手 法を施した際の通信局所性への影響も検証するために既存手法との比較も行う．提案手法では シーダが存在しないクラスタを解体し，そのクラスタに属するノードは最も近いシーダを含む クラスタに割り当てられる．そのため，既存手法よりも通信局所性の面では劣ることが予想さ れるため検証を行う．
今回の実験では通信コストの尺度としてルータホップ数とRTT (Round Trip Time)を用い る．ホップ数はパケットが送信元から受信元まで送られる際に経由するルータの数を示し，RTT はパケットが送信元と受信元の往復に要する時間であり，これらはネットワーク距離を示すも のとして扱われている [25]．本実験でも，実験5.2.2と同様に実験5.2.1において検証したノー ド数30の場合のノードを用いて検証を行う．クラスタは実験5.2.1によって得られた結果を利 用する．
クラスタ内通信とクラスタ外通信の比較
本実験で用いるクラスタリング結果は実験5.2.1における既存手法（ハードクラスタリング）
のものである．クラスタ内通信の通信コスト測定では，クラスタ内の全ノード間でpingコマ ンドを実行し，結果を取得する．一方のクラスタ外通信では，自分の属するクラスタ以外の全 ノードに対してpingコマンドを実行し，結果を取得する．クラスタ内通信コスト測定結果を 表5.3に示し，クラスタ外通信コスト測定結果を表5.4に示す．また，平均ホップ数の比較を グラフで表したものを図5.6に示し，平均RTTの比較をグラフで表したものを図5.7に示す．
測定結果より，すべてのクラスタにおいてホップ数，RTT共に平均値はクラスタ内通信の方 がクラスタ外通信よりも通信コストが小さいことがわかる．特にRTTはクラスタ内通信がク ラスタ外通信の半分以下の値であることからパケットの転送時間が大幅に削減できることがわ かる．この結果より，地理情報を用いたクラスタリング内における通信は通信局所性が高く，
遠距離トラフィックの削減にも貢献できることが分かった．
表 5.3: クラスタ内通信コスト
クラスタ 1（アジア） 2（南北アメリカ） 3（オセアニア） 4（欧州）
平均ホップ数 16.2 12.0 13.5 13.2
平均RTT 145.946 91.351 54.278 59.195
表 5.4: クラスタ外通信コスト
クラスタ 1（アジア） 2（南北アメリカ） 3（オセアニア） 4（欧州）
平均ホップ数 16.9 15.8 17.9 16.8
平均RTT 313.553 256.043 313.539 288.1
図 5.6: クラスタ内通信とクラスタ外通信の平均ホップ数の比較
図 5.7: クラスタ内通信とクラスタ外通信の平均RTTの比較
既存手法と提案手法の比較
クラスタリング結果は実験5.2.1のものを利用し，既存手法と提案手法のクラスタ内通信コ ストを比較する．測定結果は各クラスタ内の全ノード間でpingコマンドを実行し，取得する．
既存手法の通信コスト測定結果を表5.5に示し，提案手法の結果を表5.6に示す．また平均ホッ プ数をグラフで表したものを図5.8に示し，平均RTTを図5.9に示す．なお，グラフ内のクラ スタ番号は，１：アジア，２：南北アメリカ，３：オセアニア，４：欧州，１’：アジア・オセ アニアとなっている．
提案手法のクラスタリングではアジアとオセアニアが一つのクラスタを形成している．既存 手法の１（アジア：７ノード）と３（オセアニア：３ノード）が１’（アジア・オセアニア：１ ０ノード）にまとまっているため，クラスタ１とクラスタ１’の差を比較することで提案手法 の影響を確認する．
まず，ホップ数に着目するとクラスタ１’の方がクラスタ１よりも0.6ホップ小さい．予想に 反してクラスタ１’の方が平均値が小さくなった要因として，クラスタ１よりもクラスタ３の 方がクラスタ内通信の平均ホップ数が小さかったことに加え，クラスタ１とクラスタ３のノー ド同士の通信経路上のホップ数が大きくなかったことが挙げられる．
一方，平均RTTはクラスタ１’の方が99.582[ms]多い結果となった．しかし，5.2.3章で示 したクラスタ１のクラスタ外通信のRTTがクラスタ内通信の2.1倍であることと比べるとク ラスタ１’内通信の1.7倍は，それより小さい．以上の結果より，提案手法クラスタリングは シーダを保証する際，クラスタ数を削減するために通信局所性が低下するクラスタが生じるこ とがあるが，その影響は大きなものではないことがわかる．
表 5.5: 既存手法の通信コスト
クラスタ 1（アジア） 2（南北アメリカ） 3（オセアニア） 4（欧州）
平均ホップ数 16.2 12.0 13.5 13.2
平均RTT 145.946 91.351 54.278 59.195
表 5.6: 提案手法の通信コスト
クラスタ 1 （アジア・オセアニア） 2（南北アメリカ） 3（欧州）
平均ホップ数 15.6 12.0 13.2
平均RTT 245.528 91.351 59.195
図 5.8: 既存手法と提案手法の平均ホップ数の比較
図 5.9: 既存手法と提案手法の平均RTTの比較
まとめ
6.1 結論
本研究では，通信局所性を高めるために有効な手法である地理情報クラスタリングによる P2P動画配信において，クラスタ内にシーダを保証する手法を提案した．参加ノード数が30，
200，400，600の状況で検証した結果，いずれの場合でもシーダを保証できることを示した．
また，提案手法によって生成されたクラスタ内でのP2P動画配信実験においても十分なダウ ンロード速度を確保できることを示した．
6.2 今後の課題
今回の実験では評価のためにスウォームに属するノード数に対するシーダ数を20％に設定 し，シーダとなるノードもランダムに選択した．今後は，シーダの数や配置が異なる状況での 検証も行う必要がある．また，参加ノード数に対するクラスタ数は，先行研究 [4]で採用して いる線形関数をそのまま利用しているが，ノードの分布の偏りによる最適化も今後の課題であ る．そして，本手法を実際のP2P動画配信サービス向けのシステムに実装し，実サービスを 提供する環境において遠距離トラフィックの削減効果を検証する必要がある．
本修士論文の作成にあたり，日頃より御指導を頂いた早稲田大学基幹理工学部の後藤滋樹教 授に深く感謝致します．
昨年度，本研究の先行研究を共に取り組ませて頂いた大村淳己氏に深く感謝いたします．ま た，本研究を進めるにあたって議論したり，協力したりしてくださった野間敬太氏，片山雄介 氏に深く感謝いたします．そして，研究室で共に助け合い，励ましあった研究室の仲間にも感 謝いたします．
[1] PlanetLabhttp://www.planet-lab.org/
[2] 江崎浩監修，P2P教科書, インプレス，2007.
[3] BitTorrent - Delivering the World’s Content http://www.bittorrent.com/intl/ja/
[4] 大村淳己，高田和也，後藤滋樹，Location Based Clusteringを用いたP2Pストリーミン グ，電子情報通信学会技術研究報告, vol. 110, no. 373, IN2010-124, pp.37–42, 2011年1月.
[5] 大村淳己，地理情報を考慮したP2Pストリーミング，早稲田大学大学院基幹理工学研究 科2010年度修士論文, 2010.
[6] Emerge Technology BitTorrentのファイル配信メカニズム http://wiki.liris.org/article/bittorrent
[7] Distributed Computing Industry Association (DCIA) http://www.dcia.info/
[8] 亀井聡，P2P技術とインフラの融和を目指して : P2Pネットワーク実験協議会・P4P等 の取り組み解説，信学技報, vol. 108, no. 392, NS2008-130, pp. 27–32, 2009年1月.
[9] Geekなぺーじ:P4P : P2Pの進化系？http://www.geekpage.jp/blog/?id=2008/4/28/1 [10] 魏元, P2Pトラフィックの効率的制御法, 早稲田大学大学院基幹理工学研究科2008年度修
士論文, 2008.
[11] 出井勝弘, BitTorrentにおける効率的なピア選択法, 早稲田大学大学院基幹理工学研究科 2009年度修士論文, 2009.
[12] Shah, P. Paris, J.-F, Peer-to-Peer Multimedia Streaming Using BitTorrent, Performance, Computing, and Communications Conference, 2007. IPCCC 2007. IEEE Internationa, pp.340–347, April 2007.
[13] 鈴木慧, 川原崎雅敏, P2P映像配信における連携ピア選択方式の提案と評価,電子情報通信 学会技術研究報告. IN, 情報ネットワーク 109(37), pp.55–60, 2009-05-14.
[14] Reduce content delivery bills — BitTorrent http://www2.bittorrent.com/dna [15] Joost http://www.joost.com/
[16] P2P テレビの「Joost」を試してみた − ＠ IT http://www.atmarkit.co.jp/news/
200705/24/joost.html
[17] 新納浩幸 著，Rで学ぶクラスタ解析, オーム社，2007.
[18] 金明哲 著，Rによるデータサイエンス,森北出版，2007.
[19] MaxMind - GeoIP — IP Address Location Technology http://www.maxmind.com/app/
ip-location
[20] Leonard Kaufman and Peter J. Rousseeuw, Finding groups in data : an introduction to cluster analysis，1990.
[21] Webで学ぶ情報処理概論 インターネットの国別利用者数表http://www.infonet.co.jp/
ueyama/ip/internet/inet_pop_tbl.html
[22] OpenTracker http://www.whitsoftdev.com/opentracker/
[23] peach Computational Intelligence in Python http://code.google.com/p/peach/
source/browse/peach/fuzzy/cmeans.py
[24] BitTornado http://www.bittornado.com/
[25] 黒宮佑介, LinkPoint: ネットワーク負荷軽減のためにDNSによる近接性を取り入れたP2P システム, 慶應義塾大学環境情報学部2008年度卒業論文, 2008.
