-
- 図1 クライアントサーバシステムの仕組み
総務省の統計[1]により、インターネットの利用体系はクライアントサーバシステムが主流である。一方で、インターネットアクセス回線のブロードバンド化により、インターネットのトラフィックが年々増大している。また、インターネット上のコンテンツの大容量化やユーザーの増加に伴い、サーバへの負荷が集中して、顕著な問題となってきた。この問題の対処法として、注目を浴びているのがP2P(Peer to Peer)システムである。
P2Pシステムでは、ネットワーク上で構成するノードがクライアントにも、サーバにもなれるものである。そのノードはピアと呼ばれ、クライアントとサーバの両方の機能を持ち、同じ立場で相互接続される。このため、従来のクライアントサーバシステムと異なり、特定のサーバにのみ負荷が集中する問題が防止できる。
これまで、P2Pシステムを用いた様々なアプリケーションが開発されてきた。その中で代表的なものの一つとして、BitTorrentが挙げられる。BitTorrentはデータのダウンロードとアップロードを同時に行う形式で、ファイルを要求するユーザーが多ければ多いほどダウンロード時間が短縮されるという特徴を持つ。本論文はこれを用いてP2Pシステムについて研究である。
これから主流であろうとするP2Pシステムについては、様々な研究が行われてきた。その中では、研究手法の特性の評価方法は実際の研究手法について、独自で作成したシミュレータで実験し、評価を行った[4]。または、シミュレーション実験の大半がごく少数のノード数で行われ、規模の大きなネットワーク環境下での特性を検証するには至っていない[5][8]。
そこで、本研究ではBitTorrentの動作を詳細に模倣したシミュレータを用いて、シミュレーション実験を行っていく。このシミュレータはMicrosoft Research の BitTorrent Simulator[2] である。本研究では独自に設定した条件で、シミュレーション実験を行い、その結果の分析及び問題の発見、ひいては、発見した問題の解決策を提案するまでが本研究の目的である。
本論文は以下の章により構成される。
クライアントサーバシステムはWebの発展に伴い、Webサーバとブラウザを搭載したマシンに機能が明確に分かれた頃から主流になった。代表的なプロトコルはHTTP(HyperText Transport Protocol)/TCP(Transmission Control Protocol)がある。
HTTPはWebサーバから情報を引き出すプロトコルであるが、この通信はTCPを使用している。
TCPは1対1双方向通信で大きなファイルをやり取りするプロトコルである。
Webシステムでは、サービスを受ける側(クライアント)とサービスを提供する側(サーバ)に分かれている。具体的なイメージは、図2.1の示すように、サーバ一つに複数のクライアントが接続している様子である。
このような特徴を持つクライアントサーバシステムは利点と欠点がそれぞれいくつか持っている。
P2Pシステムの各ノードはピアと呼ばれ、クライアントにもサーバにもなれるコンピュータである。ピア同士は対等な関係で、P2Pネットワークを形成する。特定なサーバにサービスを要求しないため、負荷集中の問題が改善される。このような特徴を持つシステムは、以下の利点と欠点がある。
P2Pの通信形態はピュアP2PモデルとハイブリッドP2Pモデルとスーパーノード型ハイブリッドP2Pモデルに大きく分けられる。
ピュアP2Pとは、サーバを持たないP2P方式である。ピアがインデックス情報を少しずつ分散して保持する。つまり、欲しいファイルがある場合、自分と繋がっているピアに探索リクエストを送信し、受け取ったピアはファイルの場所を知っていれば返答し、知らなければ別のピアへメッセージを転送する。これにより、目的のファイルを持つピアからの返答を待つ仕組みである。インデックス情報が個々のピアに分散して所持しているため、ファイルの検索能力が低い。ピュアP2Pモデルを図2.2に示す。
ハイブリッドP2Pとは、各ピアがファイルを保有し、ピアで通信を行う。しかし、ピアの検索はピュアP2Pと違い、サーバに任せる方式を取る。サーバがインデックス情報を保持しており、要求に応じて、ピア検索と応答を行う。クライアントサーバシステムとP2Pシステムの両方の性質を兼ね備えているため、ハイブリッドP2Pと呼ばれる。サーバがダウンするとサービスが停止する欠点はクライアントサーバシステムと一緒だが、サーバはファイルのやり取りはしない分、負荷が軽減できる。また、サーバを用いて、ピアの情報を一括管理できるため、ピュアP2Pモデルより、検索能力が優れ、認証や課金機能も備えることができる。そのため、商用サービスには向いているモデルである。ハイブリッドP2Pモデルは図2.3に示す。
スーパーノード型ハイブリッドP2Pとは、スペックの高いピアをスーパーノードとして選定し、インデックス情報を管理させる方式である。ピュアP2PとハイブリッドP2Pを組み合わせたモデルである。スーパーノード型ハイブリッドP2Pモデルは図2.4に示す。
BitTorrent[3]は、P2Pプロトコルをベースにした情報コンテンツ流通（ファイル転送）プロトコル及びその通信を行うソフトウェアである。これはBram Cohenによって開発されたものである。ファイル共有のため、世界中で利用されており、CentOSやFedoraといったLinuxディストリビューションもBitTorrentで配布されている。
BitTorrentで使用する用語を表2.1に示す。
| 用語 | 意味 |
|---|---|
| トラッカー(Tracker) | ファイル共有ネットワークに参加しているピアのIPアドレスやピアの持つファイルの情報を管理するサーバ |
| Metainfo ファイル | トラッカーのアドレスや本体ファイルの情報が書き込まれたファイル(拡張子は.torrent)。ファイル共有ネットワークに参加するために入手する必要がある。 |
| ピース(Piece) | ファイルのサイズを一定の大きさで複数に分割したものである。ブロックとも呼ばれる。 |
| シーダー(Seeder) | 全ファイルを持ち、アプロードのみを行うピア。 |
| リーチャー(Leecher) | ダウンロード中のピア。 |
| チョーク(Choke) | 接続するピアに対し、アップロードを許可されていない状態 |
| アンチョーク(Unchoke) | 接続するピアに対し、アップロードを許可されている状態 |
BitTorrent はファイルの転送はピア同士で行うが、ピアの検索及びコンテンツの管理などはトラッカーと呼ばれるサーバに任せている。すなわち、ハイブリッドP2Pモデルに分類されている。ファイルを共有する際、そのファイルを小さなブロックに分割した複数のピースにする。複数のピアがピースをダウンロードまたはアップロードすることで、すべてのピースを揃えて組み合わせることが可能である。これにより、高速なファイル転送を可能にしている。また、人気のあるファイルほど、そのファイル共有ネットワークに参加するピアな数も多いため、その分ダウンロード速度が比較的に速くなる。
ピアとトラッカーの通信は、HTTPベースで行われる。ピアは表2.2に示す情報をトラッカーに送信することに対して、トラッカーは表2.3に示す情報をピアに送信している。
| 種類 | 内容 |
|---|---|
| info_hash | 共有したいファイルのハッシュ値 |
| peer_id | ピア(BitTorrent クライアント)のID |
| Port | ピア(BitTorrent クライアント)が使うポート番号 |
| Uploaded | アップロードした合計バイト数 |
| downloaded | ダウンロードした合計バイト数 |
| Left | ダウンロード残りバイト数 |
| 種類 | 内容 |
|---|---|
| interval | 再びトラッカーにリクエストを送るまでの時間間隔 |
| complete | シーダーの数 |
| incomplete | リーチャーの数 |
| peers | ネットワーク上ファイルを持つピアの一覧 |
BitTorrent では、ファイル共有アルゴリズムとしてTit-for-tat 戦略を用いる。この戦略は繰り返し囚人のジレンマの解として知られ、「しっぺ返し法」としても知られている。BitTorrentでは「ダウンロードをする際にはアップロードもしなければならない」という規則を指している。ファイル共有ネットワークに参加するすべてのピアにアップロードを強制することで、高速にファイルをすべてのピアに転送することを可能にしている。
BitTorrent でTit-for-tat 戦略を実現するために用いるのはチョークアルゴリズムである。このアルゴリズムを分類すると、大きく4つに分けられる。
BitTorrentでは、各ピアはアップロードを一定数のピアに対してアップロードを許可(アンチョーク状態)している。デフォルトでは、アンチョーク状態のピアの数は4つである。接続している複数のピアのうち、アンチョーク状態する4つのピアを選択することが重要になる。
アンチョーク状態するピアの選択は、基本的には現在のダウンロード速度によって決まる。ダウンロード速度は20秒間のダウンロード量の平均を使用する。チョーク状態とアンチョーク状態が頻繁に切り替わると、却って効率が悪くなるため、10秒ごとにアンチョーク状態のピアを選択する。
単純にダウンロード速度だけを元にしたチョーク判定では、もっとよい接続先を見つけ出すことができない。このため、4つのアンチョーク状態のピアのうち、一つのピアには基本的なチョークアルゴリズムではなく、楽観的なアンチョーク戦略をとる。楽観的なアンチョーク戦略では、30秒ごとに自分が持っているピアのリストから順番にアンチョーク状態にする。
ファイルが完全にダウンロードされていない時に、他のピアに貢献している（ピースをアプロードしている）にもかかわらず、接続しているすべてのピアからチョーク状態にされていることがある。一分以上アンチョーク状態のピアからピースをまったく取得できなかった場合は、そのピアをチョーク状態にして相手のピアに自分は冷遇されていると意志表示をする。すると、楽観的アンチョーク戦略が働いて、代わりのアンチョーク状態のピアを見つけ出す。
一度冷遇されたピアに対しては、それ以降のチョークアルゴリズムでアンチョーク状態にしないようになる。
全てのピースのダウンロードが終了すると、ダウンロード速度を元にアンチョーク状態のピアを選択する必要がなくなる。このため、ダウンロード速度を元にした戦略からアップロード速度が速いピアをアンチョーク状態にする戦略に変更する。
こうしたピアが増えることにより、他のピアのダウンロード効率が上昇する。
P4P(Proactive network provider participation for P2P)は、ISP(internet service provider)がP2Pシステムに協力することで、P2Pトラフィックによるネットワーク負荷を軽減し、コンテンツの転送効率を向上するために提案された技術である。P4Pでは、各ISPにiTrakerと呼ばれるポータルサーバを用意して、3つのインターフェース(表2.4参照)を提供する。P2Pクライアントや、P2Pを管理するサーバ(appTraker)はiTrackerから情報を受け取ることで、効率性を考慮したピア選択を行うことができる。
| インタフェース | 内容 |
|---|---|
| info | ISPが管理するネットワーク内に存在しているピア候補に対して、ネットワークトポロジやステータスを提供する。IPアドレスをキーとして、ISPのIDであるISPのIDであるASID(AS番号)、ノードグループに対して割り当てられるPID、仮想的または地理的な位置情報を提供する。 |
| policy | ネットワークのポリシーやガイドラインを提供する。避けてほしい回線の提示などである。 |
| capability | ISPが提供可能の機能情報を提供する。CoS(Class of Service)やネットワーク内の既設サーバを示すなどである。 |
本章で、本研究と関連する研究について紹介する。
2010年には村松による論文「P4Pを活用してトランジットを軽減するP2Pプロトコル」[4]においてP4P技術を活用するアルゴリズムが提示された。彼の論文における提案は「遠方優先アルゴリズム」と呼ばれるアルゴリズムである。このアルゴリズムは遠方にあるピアに対して、早くファイルを転送することを目的としたアルゴリズムである。BitTorrentのファイル交換ネットワーク上に偏って存在するファイルを出来るだけ遍在させようと促すアルゴリズムである。特性解析にはJavaを用いた自作シミュレータを使って行っている。このシミュレーションにより、特定のネットワークトポロジーにおいてダウンロード完了までにかかる時間、トランジット量、ともに減らすことが出来たと示されている。
本研究では、村松と同様にダウンロード完了までの終了時刻をシミュレータで測ることできた。しかし、本研究は一般的なシミュレータを用いて、他の研究と比較しやすくなった。
2012年に、早稲田大学の佐藤氏による論文「BitTorrentにおける低速ピアの支援法」が提案された[5]。この論文はBitTorrentシステムにおけるファイルの配信効率の低下問題に対し、トラッカーの機能に変更を加えることで、BitTorrentネットワークにおけるダウンロード速度が上がらないピアのダウンロード効率の向上を実現する。配信支援シーダーの配置し、トラッカーが配信支援ピアリストを生成して送ることによって、配信支援シーダー、または高速ピアに支援要請をすることで、低速のピアを支援する。この手法の検証は、PlanetLabという実際のインターネット上での評価実験を可能にする地球規模のテストベッドで評価を行った。これにより、この提案方式はBitTorrentシステムにおいて低速なピアのダウンロードを支援することでスウォーム全体のダウンロード効率を向上させる有効な手法である。
本研究は、BitTorrentの研究では同じであるが、シミュレータを用いているため、様々なシナリオの実験を試すことができる。
2015年に、鈴木による論文「ns-3によるP4P活用プロトコルの実装」が提示された[6]。この論文はP2Pについての複数の研究に対して、P4Pを活用するアルゴリズムが提案されているが、評価方法は実際に複数のコンピュータを使ったBitTorrentネットワークの構築や、Javaを用いた独自シミュレータの作成である。しかしいずれにおいても現実のネットワークに則した複雑な構造やパラメータの、そして規模の大きなネットワーク環境下での特性を検証するには至っていない。特性解析はほとんどが極めて限られた条件下に留まっている点に対して、ns-3と呼ばれるネットワークシミュレータを用いることを提案した。
この論文では、Googleのシミュレータを用い、彼はns-3上にBitTorrentを実装したところに至っているが、本研究で使用したシミュレータの方が確度は高い。
本研究で使用するシミュレータはMicrosoft Research の BitTorrent Simulator である。このシミュレータはBitTorrentの動作を詳細に模倣したシミュレータである。ファイルを分割でき、チョークアルゴリズムも実装されている。また、ノードのアップロードとダウンロード速度を正確に測定できる。このシミュレータを動作するには、LinuxではmonoとMCSがインストールされている必要がある。WindowsではVisual Studioで動作可能である。
シミュレータコードを簡単に説明する。
このシミュレータはどのようにファイルの転送を行うかを、動作環境を表4.1で表して、表4.2に示す条件で、一つのシミュレーションについての動作説明をする。
| OS | Windows 10 Home 64 bit |
| CPU | Intel(R) Core(TM) i5-3317U |
| メモリ | 4GB |
| シミュレーション環境 | Visual Studio Express 2012 |
| パラメータ | 設定条件 |
|---|---|
| ファイルサイズ | 512KB |
| ブロックサイズ | 256KB |
| シーダーの数 | 1個 |
| シーダーのアプロード速度 | 3000kbps |
| リーチャーの数 | 3個 |
| リーチャーのダウンロード/アプロード速度 | 56/56、784/128、1500/400、6000/3000、100000/100000(kbps)によりランダムに決められる。 |
シミュレータの動作を図4.1に示す。
シミュレータの動作は順を追って説明する。
以上のように、BitTorrent Simulatorは一つのファイルを一定のサイズの複数のピースに分割し、ファイル共有ネットワークを通じて、各ピアが交互に欠けているピースをやり取りすることで、すべてのピアにファイルを転送している。
シーダーのスペックがファイル共有ネットワーク環境下での重要性を実験で検証する。
シミュレーション開始時から、シーダーを1個生成し、1分後に5つのリーチャーがネットワークに同時参加する。それぞれのリーチャーのスペックは異なる。
実験の前提条件を表5.1と表5.2で示す。
| パラメータ | 設定条件 |
|---|---|
| ファイルサイズ | 10240KB |
| ブロックサイズ | 256KB |
| シーダーの数 | 1個 |
| シーダーのアプロード速度 | リーチャーのアプロード速度をそれぞれに1回シミュレーションする。 |
| リーチャーの数 | 5個 |
| リーチャー | Download speed(kbps) | Upload speed(kbps) |
|---|---|---|
| 1 | 56 | 56 |
| 2 | 784 | 128 |
| 3 | 1500 | 400 |
| 4 | 6000 | 3000 |
| 5 | 100000 | 100000 |
シミュレーション結果を表5.3と図5.1に示す。
| シーダーのスペック | リーチャー1の完了時間 | リーチャー2の完了時間 | リーチャー3の完了時間 | リーチャー4の完了時間 | リーチャー5の完了時間 |
|---|---|---|---|---|---|
| 56(kbps) | 2253.332s | 2291.234s | 2253.319s | 2253.322s | 2253.33s |
| 128(kbps) | 1566.231s | 911.811s | 911.769s | 911.785s | 911.834s |
| 400(kbps) | 1522.828s | 366.853s | 347.168s | 364.715s | 356.403s |
| 3000(kbps) | 1522.834s | 165.337s | 116.073s | 115.658s | 115.619s |
| 100000 (kbps) | 1522.834s | 165.027s | 120.427s | 101.929s | 60.888s |
上記の結果から、シーダーのスペックが良ければよいほど、いいスペックを持つリーチャーがダウンロード完了を早く完了する。シーダーのスペックが悪くても、ダウンロード速度は周りのリーチャーからサポートを受け、ダウンロード完了時間が延々と伸ばされることはないことが見て取れる。
クライアントサーバシステムと数値で比べてみる。仮にサーバが表5.3の最低スペックであるとして、全クライアントにファイルを転送する時間が10240×5÷56＝10239sである。この数値から、BitTorrent のファイル提供者のスペック要求が著しい低いことが見て取れる。
また、シーダーの低スペックによる、高スペックのリーチャーがダウンロード速度を下げられた点については、要はシーダーが如何にファイルの全ピースをリーチャーに早くばら撒くことで解決する。考えられる方法の一つとして、最初から複数のシーダーを用意することで、全ピースの転送時間を短くする。後は、ピースをもらったリーチャーがシーダーとなり、転送速度をスペック限界まで上げることである。
以上により、クライアントサーバシステムに対して、シーダーの重要性がそこまで高いとは言えない。
大規模なファイル共有ネットワーク環境下でシミュレーション実験を行う。その特性および問題を分析する。
シミュレーション実験時から、シーダーを1個生成し、1分後に5000個のリーチャーをファイル共有ネットワークに追加し、更に1分後に5000個のリーチャーをファイル共有ネットワークに追加する。シーダーの数を含め、10001のピアのある大規模なネットワーク環境を模擬する。また、データ分析のため、リーチャーのネットワークスペックを一定にする。
実験の前提条件を表5.4に示す。
| パラメータ | 設定条件 |
|---|---|
| ファイルサイズ | 10240KB |
| ブロックサイズ | 256KB |
| シーダーの数 | 1個 |
| シーダーのアプロード速度 | 3000kbps |
| リーチャーの数 | 10000個 |
| リーチャーのダウンロード/アプロード速度 | 1500/400kbps |
シミュレーション結果を図5.2に示す。
シミュレーション実験の条件から、結果を予想してみる。同時に5000個のリーチャーをファイル共有ネットワークに追加する。そして、リーチャーのスペックはすべて同じだということから、ほぼ同時にダウンロードが完了することが理想な結果だと理解できる。また、1分後に同じ数と条件のリーチャーがファイル共有ネットワークに参加する。これにより、前半のリーチャーが後半のリーチャーに対して、ファイル共有を行うため、前半の完了速度が若干遅くなることが予想できるが、後半のダウンロードしたピースも前半のリーチャーに対して送信するので、大差ないと感じる。結果的に、両方のグラフは並行でかつ、ほぼ直線的に上昇することが予想できる。図5.3に示す。
しかし、図5.2の結果を見るに、前半の完了数のグラフが最初のほうから直線的に上昇することに対し、後になるにつれて緩やかに上昇することがわかる。これに対して、後半のグラフほぼ直線的に上昇する。これにより、前半の完了速度が予想よりも遅いことが判明した。前半最後の辺のピアは延々と完了しないことが、後半のグラフが追い付いてきたことから見て取れる。また、前半に限らず後半も、最初にダウンロードが完了したピアに対し、最後にダウンロードが完了したピアが300s近く遅れていることが見て取れる。同じ条件のピアであるはずが、非常に遅いピアが存在している。
遅いピアが存在することの原因を予想する。最後に完了するピアが遅い原因は最初にすべてのファイルピースを持っているピアが少なく、全ピアに行き届かせる時間が必要である。これは、前半の最後にダウンロードが完了したピアが350s近く遅れていることに対して、後半は250s近くしか遅れてなかったことから、判断できる。また、全体的グラフでは、ほぼ直線的に上昇していることをみると、ネットワーク送信の効率が遅れていないことがわかる。これより、前半のピアの必要のピースに対して、そのピースを持っているピアが少なく、なかなかもらえない状況が考えられる。または、ピースを持っているピアに相手をされていないことも考慮できる。
本研究はMicrosoft Research の BitTorrent Simulatorを用いて、独自に設定した条件で、シミュレーション実験を行い、その結果の分析及び問題の発見、ひいては、発見した問題の解決策を提案するまでを目的として行った。
実験1はBitTorrentのP2Pシステムにおいてシーダーの役割について実験した。そして、ファイル共有により、ファイル提供者のスペックに対する要求はクライアントサーバシステムより遥かに低いことが判明した。
また、シーダーの低スペックによる、高スペックのリーチャーがダウンロード速度を下げられたことを発見した。これは、最初から複数のシーダーを用意することで、全ピースの転送時間を短くすることで、解決方法を提案した。
実験2は大規模なファイル共有ネットワーク環境下でシミュレーション実験を行い、1分挟んで全10001個のピアが参加するファイル共有ネットワーク内にどのような特性があるかを実験した。
結果的に、大規模なファイル共有ネットワーク内では、非常に遅いピアが存在する。原因は、ピースが各ピアに行き渡せることに時間が掛かることにあると考えられる。または、欠けているピースに対して持っているピアが少なく、なかなかダウンロードできないピアがあることが考慮できる。
実験2で遅いピアが存在することに対して、原因の実証実験を行っていない。また、今後ではより自然なシナリオの実験を行っていきたい。
本卒業論文を進めるにあたり、日頃よりご指導を頂いた坂本直志教授に心より感謝いたします。また、本研究を進めるにあたり、貴重な助言を頂いた後藤徹哉氏と筒井悠斗氏にも深く感謝します。そして、ともに研究に励み、協力し合うネットワーク研究室の皆様に感謝いたします。