内容梗概
[English | 論文 | 美濃研の研究 | 美濃研究室 ]


ピアツーピア環境におけるファイル発見を実現するネットワーク負荷を抑える転送先学習アルゴリズム


本報告書では、ネットワークにおいて互いに対等な関係で通信を行うピアツー ピア型環境において、負荷を抑えつつ、ファイル発見を実現するための転送先 学習アルゴリズムを提案し、シミュレーションによって確認した効果について 述べる。

ネットワークにつながるコンピュータの数が多くなるとともに、ネットワーク 上にあるファイルを活用したいという要求が高まってきた。 そのような要求に応えるには一般的にクライアントサーバ システムが用いられてきた。ネットワークに接続されたコンピュータは、 サーバがファイルの蓄積・検索・提供を行い、それを利用するクライアントか ら利用するという形態である。 このシステムではサーバの負荷が高い一方、技術の進歩でクライアントの性能は 飛躍的に高性能化しており、余剰能力が生じていた。

そこで、クライアントの持つ能力を活用するために2つのファイル発見プロトコ ルが提案された。 1つは蓄積・提供の機能をクライアントに持たせ、サーバがクライアントが持つファ イルのインデックスを持ち、サーバが検索を行うプロトコル、そしてもう1つは、蓄積・ 検索・提供の機能をすべてのそのネットワークに接続するコンピュータに持た せ、それらが協働することでファイル発見を実現するプロトコルである。

本稿では、後者のシステムがネットワーク全体を監視し履歴情報を収集するこ とが不可能である点、またどこに障害があったとしてもシステム全体が利用で きなくなることがない点に着目し、後者のシステムを対象とする。以下、この システムをピアツーピア型のファイル発見プロトコルと呼ぶ。

ピアツーピア型のファイル発見プロトコルとしては、Gnutellaが有名である。 Gnutellaではファイルの発見要求を伝えるQueryパケットをノード間で順に受け 渡すことによってファイル発見を行う。 ここで、Gnutellaの実装では、転送を行うときにすべての隣接ノードにQueryパ ケットをブロードキャストするため、Queryパケットの転送が行われるごとに 指数関数的にQueryパケットの数が増えてしまう問題がある。 Queryパケットの数が増えると、転送処理のため計算資源を消費し、 同時実行しているアプリケーションに悪影響を与え、 発見をしてからその結果が返ってくるまでの時間が長くなる。

そこで、本稿では「すべての隣接ノードにQueryパケットを転送 する」という処理を、「より多くより早く発見できる隣接ノードに限定して Queryパケットを転送する」という処理に変更した手法を提案する。転送先を少 することで、Queryパケットの増加を抑え、ネットワークの負荷を抑えようとす るものである。

Queryパケットの転送先を限定するために確率的な転送機構を導入する。 それによって、ファイルを多くかつ早く発見できるような隣接ノードに高い確 率で転送し、そうでない隣接ノードに転送する確率を低くする。

Queryパケットの転送確率を更新するために、転送先学習アルゴリズムを提案す る。転送先学習アルゴリズムでは、 Queryパケットをどの隣接ノードに転送してファイルを早く多く発見できたか の情報を収集するために、従来のGnutellaにおいて応答に使用 されるQueryHitパケットを活用する。 Gnutellaでは、Queryパケットの転送が順に転送され、要求されるファイルを 持つノードに到達するとそこでQueryHitパケットが生成される。 QueryHitパケットは対応するQueryパケットがそのノードに到達するまでにたどっ た経路を逆向きに転送され、Queryパケットを生成したノードまで送り返される。

本稿で提案する手法では、QueryHitパケットが送り返されていくときにQueryパ ケットの転送確率を更新する。 ノードにおいてQueryパケットを転送する際には、この転送確率を使用してQueryパケット の転送先となる隣接ノードを決定する。 転送確率を更新する処理はIPルーティングの分野に適用されて非常に優秀 な効果が得られたAntNetという学習アルゴリズムを参考にした。

この方式で実際に発見数が向上したかどうかをシミュレーションにより調べた。 その結果、同じネットワーク負荷で発見できる数を従来手法の $6$倍多く発見できることを確認した。 また、ユーザが短い時間に数多くQueryパケットを生成するような状況において、 従来のブロードキャストによる場合では各ノードのキュー(処理待ちのパケット を置く場所)で待つパケットの数が爆発的に増加するのに対して、本方式を採 用した場合ではキューで待つパケット数は安定していたことが確認された。 また、応答にかかる時間について調べたところ、本方 式の方が従来のブロードキャストの場合よりも短い時間で応答が得られること が分かった。このように、応答時間や、キューでの待ち時間、ネットワーク負 荷の観点で優れていることが確認された。


学位論文のページに戻る