修士学位論文 P2Pネットワークにおけるストレージ負荷分散実現のための

修士学位論文
題目
P2P ネット ワークにおけるストレージ負荷分散実現のための
複製配置手法
指導教官
尾家 祐二 教授
報告者
丸田大輔
平成 16 年 2 月 29 日
九州工業大学大学院 情報工学研究科
情報システム専攻
平成 15 年度 修士学位論文
P2P ネットワークにおけるストレージ負荷分散実現のための
複製配置手法
丸田大輔
内容梗概
サーバを用いることなく各ホスト (ピア) が対等に接続されることで構成される Peer-to-
Peer(P2P) ネットワークでは，各ピアの持つデータに対する検索処理の性能向上や負荷分散
を目的として，各データの複製の生成が行なわれる．現在までに P2P ネットワークに適した
複製配置手法が既に提案されているが，それらは主に検索処理性能の向上に注目しており，
各計算機に発生する読み込みや書き込みによるストレージへの負荷や，検索要求メッセージ
やデータの交換によって発生するネットワーク負荷の分散に関しては考慮されていない．そ
こで本研究では P2P ネットワークの特性を考慮して，検索処理性能を一定の水準に保ちつ
つ，ストレージ負荷分散が達成可能な複製配置手法を提案し，シミュレーションによってそ
の有効性を示す．
主な用語
Peer-to-Peer(P2P)，複製配置手法，power-law ネットワーク，ストレージ負荷分散
目次
1
はじめに
1
2
Peer-to-Peer(P2P)
3
2.1
クライアントサーバモデルとその問題点 . . . . . . . . . . . . . . . . . . . .
3
2.2
P2P の概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.3
P2P のネットワーク形態 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.3.1
Hybrid P2P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.3.2
Pure P2P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.4
power-law ネットワーク . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.5
P2P 関連研究 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3
4
5
10
既存技術
3.1
検索手法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2
複製配置手法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3
複製配置手法の問題点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
20
提案手法
4.1
Path Random Replication . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2
拡張 Path Random Replication . . . . . . . . . . . . . . . . . . . . . . . . . 20
24
シミュレーションモデルと評価指標
5.1 シミュレーションモデル . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.2
6
評価指標 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
28
結果および考察
6.1
Path Random Replication の基本特性の調査 . . . . . . . . . . . . . . . . . . 28
6.1.1
検索ホップ数について . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6.1.2
ストレージに発生する負荷の分散 . . . . . . . . . . . . . . . . . . . . 29
i
6.2
7
6.1.3
最適な複製配置確率の推定 . . . . . . . . . . . . . . . . . . . . . . . . 33
6.1.4
シミュレーション条件を変化させた場合 . . . . . . . . . . . . . . . . 36
拡張 Path Random Replication による負荷分散 . . . . . . . . . . . . . . . . 45
6.2.1
基本特性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.2.2
新規データを追加した場合 . . . . . . . . . . . . . . . . . . . . . . . . 49
55
まとめ
謝辞
57
参考文献
58
ii
1
はじめに
近年，クライアントサーバモデルのようにサーバによってサービスが集中管理されることな
く，各ホストが対等に接続されそれぞれがサービスを提供し合うことが可能な Peer-to-Peer
（ P2P ）技術に注目が集まっている．一般に P2P ネットワークでは，ネットワークに参加し
ているホストはピア（ Peer ）と呼ばれ，データを公開するサーバとデータを取得するクライ
アントの両方の機能を持つ．P2P 技術を用いることによって，トラヒックの分散やネット
ワークの耐故障性の向上が可能となる．また，P2P 技術の中でも特に，P2P ネットワーク
に参加する各ピアの未使用ストレージ資源を集約し，仮想的な大容量ストレージとして利用
する分散ストレージに関心が集まっている．
P2P による分散ストレージの使用例として，インターネットラジオ配信に代表されるコ
ンテンツ配信が挙げられる．従来，個人で上記のようなコンテンツ配信を行なうためには
サーバへのアップロード やサーバの運用が必要不可欠であった．しかし，P2P による分散ス
トレージを用いることにより，サーバを用いることなく各ピアが配信したいコンテンツをイ
ンターネット上で公開可能になる．その他にも，分散ストレージ技術を用いることにより，
サーバベースのファイルストレージを使用せずに仮想的な大容量ストレージが構築可能であ
る．これにより，高価な大容量ストレージを導入することなく，各個人の計算機を P2P で
接続することによって容易にデータの共有や大容量のデータ保存が可能になる．以上で示し
たような利点から P2P による分散ストレージは個人ではコンテンツ配信に，また企業では
仮想的な大容量ストレージに対して注目が集まっている．
一方で，P2P 環境ではピアがネットワークから離脱することにより目的のデータを取得
できないという問題点があるため，クライアントサーバモデルと比較してデータの耐故障
性が低くなる．そこで，この問題を防ぐ 方法として各データの複製を P2P ネットワーク全
体に分散配置する方法が考えられる．例に挙げたコンテンツ配信では，ネットワーク内に複
製を分散配置することにより，コンテンツの配信源がネットワークから離脱した場合でもコ
ンテンツを参照することが可能になる．また，同一のコンテンツが複数のピアへ分散配置さ
れるため人気のあるコンテンツに対する集中的な負荷をネットワーク全体に分散可能とな
1
る．しかし，P2P ネットワークでは各ピアが論理的な接続の上に成立しており，隣接ピア数
（ degree ）はべき法則（ power-law ）に従うという特徴を持つ [1] ため，効率良く複製配置を
行なうためにはこれらの P2P ネットワークの特徴を考慮する必要がある．
効率良く複製を分散配置するためには，データの検索手法と複製配置手法の双方を考慮
する必要がある．ここで，検索手法とは目的のデータを保持するピアを発見するための検
索要求メッセージの転送手法を指し ，複製配置手法は検索過程で得られた情報を基に複製
配置を行なう手法を指す．そのため，これらの手法にはネットワークの特徴に適したものが
求められる．現在までに，データ検索時の検索ヒット率向上のための複製配置手法 [2] や，
power-law ネットワークに適した検索手法 [3] が提案されている．しかし，多くの研究では
検索ヒット率の向上や応答時間といった検索処理の性能に着目しており，ごく少数の degree
の高いピアと非常に多くの degree の低いピアによって構成されるという power-law ネット
ワークの特徴に起因して各ピアに発生する負荷を P2P ネットワーク全体に分散する手法に
重点を置いた研究はあまり行なわれていない．
そこで本研究では power-law ネットワークの特性を考慮した上で，複製配置手法として提
案されている既存の手法を改良し，検索に要する平均ホップ数等の検索性能を一定水準に維
持しつつ，複製の分散配置や複製へのアクセスによって各ピアに発生するストレージ負荷を
ネットワーク全体に分散可能な複製配置手法を提案し，シミュレーションによりその評価を
行なう．
本論文では，まず 2 章において P2P の概要や P2P におけるネットワークの形態，power-
law ネットワークの特徴を説明する．3 章では P2P で用いられる既存の検索手法と複製配置
手法を紹介し，既存の複製配置手法における問題点について説明する．次に 4 章でその問題
点を解決するための手法を示し，5 章では，提案手法による効果を調査するために行なうシ
ミュレーションのモデルと評価指標について説明する．そして，6 章ではシミュレーション
結果を示し考察を行ない，最後に 7 章においてまとめを行なう．
2
2
Peer-to-Peer(P2P)
本章では，現在インターネットで主に用いられているクライアントサーバモデルとその問題
点，またその問題点を解決することが可能なネットワークモデルとして注目されている P2P
の特徴やネットワーク形態，P2P ネットワークでの各計算機間の接続構成である power-law
ネットワークについて説明する．
2.1
クライアント サーバモデルとその問題点
現在，インターネットでは主に図 2.1 のようなクライアントサーバモデルでサービスが提
供されている．このモデルは，クライアントがサーバに対して処理を依頼し，サーバは依頼
された処理要求に従いサービスやリソースを提供するという主従関係によって成り立ってい
る．しかし，近年の ADSL(Asymmetric Digital Subscriber Line) や光ファイバによる急速
なブロードバンド 化により，サーバへのサービス要求によりサーバへのトラヒックが飛躍的
に増加したため，サーバがネットワークのボトルネックの 1 つとして考えられるようになっ
ている．
また，クライアントサーバモデルにおいて各自の持つデータを共有するためには，サーバ
への当該データのアップロード 等の操作が必要となる．そのような煩雑さのために，利用者
の協力が得られず情報がサーバに集まらなかったり，データの作製から情報の公開までにタ
イムラグが発生したりするという問題が発生する．さらに，サーバが何らかの理由で停止し
てしまうとサービ スの提供が完全に停止し ，ネットワーク全体に多大な影響を与えてしま
う．そのような特性からサーバはしばしば攻撃対象となりネットワークの耐故障性を損なっ
てしまう．
2.2
P2P の概要
クライアントサーバモデルの問題点を解決するネットワークモデルとして P2P が注目さ
れている．P2P とは，すべてのコンピュータが同等のサービ スを受ける権利とサービ スを
提供する責任を持ち，相互に接続することによって構成されるネットワークモデルである．
3
図 2.1: クライアントサーバモデル．
P2P ではクライアントサーバモデルと異なり，主従関係がなく全てのホストが対等な存在，
つまりピア (Peer) としてリソースやサービ スを直接やりとりすることが可能であるという
特徴を持つ．また，クライアントサーバモデルのように特定のピアが停止することでネット
ワークに影響を与えることはほとんどなく，情報の共有に関してもサーバへアクセスするこ
となく直接当該データを持つピアにアクセスすることが可能であり，アップロード 等の操作
が必要ないためデータの作成から情報共有までのタイムラグも，クライアントサーバモデル
と比較して発生しにくいという特徴を持っている．さらに，サービス要求が特定のピアに集
中する可能性が低く，クライアントサーバモデルではサーバ周辺に集中していたトラヒック
もネットワーク全体に分散可能である．しかし，P2P はクライアントサーバモデルと異なり
各ピアの参加・離脱が頻繁に発生するため，P2P ネットワーク上に存在するすべてのデータ
を確実に入手可能な環境を構築するのが困難であるという問題点を抱えている．
4
図 2.2: Hybrid P2P の例．
2.3
P2P のネット ワーク形態
前節では P2P の概要について説明した．しかし，P2P 技術を実装しているアプリケーショ
ンでは，P2P という共通の概念を持ちながら異なるネットワーク形態を適用している．そこ
で本節では，P2P 技術を用いて情報共有を実現しているアプリケーションで用いられている
ネットワーク形態として，Napster[4] に代表される Hybrid P2P と，Gnutella[5]，Freenet[6]
に代表される Pure P2P について説明する．
2.3.1
Hybrid P2P
Hybrid P2P とは，情報の検索機能や認証機能等を持ったサーバが P2P ネットワークを構
成している各ピアの状態を管理するネットワーク形態である．この形態では目的のデータを
5
持つピアの検索はサーバへ問い合わせを行ない，その後の通信はサーバを介さずにピア間で
直接行なわれる．つまり，検索や認証等の処理ではクライアントサーバモデルで処理を行な
い，実際のデータ通信では P2P で処理を行なう．このように，クライアントサーバモデル
と P2P モデルの両者の特徴を併せ持つために Hybrid P2P と呼ばれる．Hybrid P2P の問題
点は，サーバが利用停止状態になるとサーバによって提供される検索や認証などのサービス
に大きな影響を受けることである．また，クライアントサーバモデルほどではないが，負荷
がサーバに集中することも問題点として挙げられる．図 2.2 では，Hybrid P2P における目
的とするデータの検索からデータ取得までの過程を示している．図 2.2 の 1，2 では，クラ
イアントサーバモデル同様にクライアントがサーバに対して検索処理要求を出し，サーバが
検索処理結果の応答をクライアントに対して返している．これにより，クライアントは検索
対象データを持つピアを発見し，それ以降のデータ通信 (図 2.2 の 3) は，検索対象データを
持つピアとデータを要求しているピアの間で直接行なわれる．
2.3.2
Pure P2P
一部でクライアントサーバモデルを使用する Hybrid P2P に対し，全てのピアが対等に接
続されており，全くサーバを必要としないネットワーク形態を Pure P2P と呼ぶ．この接続
形態ではすべてのホストがクライアントとサーバの機能の両方を持ち，状況に応じて相互に
サービスを提供し合う．クライアントサーバモデルや Hybrid P2P のようにサーバを用いる
ことなく個々のピアがそれぞれネットワークに参加してサービスを相互提供しているため，
耐故障性が非常に高く，悪意の第三者によりサービ スを完全に停止させられる可能性が極
めて低いという特徴を持っている．しかし，サーバが存在しないため認証や課金，セキュリ
ティ等の集中的な管理を必要とするサービスを提供することが非常に困難である．
図 2.3 に，Pure P2P で検索を行う場合の例を示す．図に示しているように，Pure P2P で
は一般的にデータを要求するピアが隣接する全てのピアに対して検索要求を送信する．その
結果から，検索対象データを持つピアを特定しそのピアとの間で対象データの通信を行な
う．このような検索方法のため，Pure P2P ではユーザが増加すると検索要求メッセージに
より急激にネットワークが混雑するという問題点を抱えている．
6
図 2.3: Pure P2P の例．
2.4
power-law ネット ワーク
近年の研究によって，インターネット上にアプリケーションレベル (WWW 等) で構成さ
れる論理ネットワークの形態はべき法則 (power-law) に従うことがわかっている [7, 8]．同
様に P2P ネットワークもアプリケーションレベルで相互に接続されることで構成される論
理ネットワークであるため，power-law に従って接続されることが現在までに明らかになっ
ている [1]．power-law に従って接続されているネットワークでは，あるピアに隣接している
ピア数 (degree) を degi とすると，それぞれのピアの degree が degi = xα に従うという特徴
を持っている．また，これらのピアの接続は物理的な接続と関係なく構成されており，論理
ネットワーク上の隣接ピアが必ずしも物理的に近い位置にあるわけではない．
図 2.4 は power-law ネットワークのイメージである．図中の青い丸はピアを，丸同士を結
ぶ直線は各ピア間の接続リンクを示している．この図からもわかるように，power-law ネッ
トワークではごく少数の degree の高いピアと非常に多くの degree の低いピアによって構成
されている．このネットワークの特性上，degree が非常に高いピアが攻撃や過度の負荷に
7
図 2.4: power-law ネットワーク．
よって停止してしまうとネットワーク全体に与える影響が大きく，復旧のために多大な時間
を要する [9]．
本稿では，この P2P ネットワークの中でも非集中的なネットワーク形態である Pure P2P
に power-law ネットワークを適用した場合の問題を取り扱う．
2.5
P2P 関連研究
P-Grid[10] では，ピア同士が自発的に木構造を形成する．全てのピアは保持しているデー
タを基に，検索に最適化された場所に配置される．ピアの配置場所は全て木構造の葉の部分
となる．検索に最適化されているため，検索の際に発生する検索要求メッセージを大幅に減
らすことが可能 [11] である．このシステムを実装したアプリケーションとして Gridella[13]
がある．
また，Peer-to-Peer Grid[14] では，インターネット上の計算機資源を集約することで，仮
想的な高性能計算環境の構築が可能な Grid Computing[12] と P2P を統合することを目標と
8
している．
9
3
既存技術
本章では，power-law に従う P2P ネットワークに適した手法として現在までに提案され
ているネットワーク上に分散配置されたデータの検索手法と，検索性能向上のために行なわ
れるデータの複製配置手法についてそれぞれ説明する．そして，本研究で着目する複製配置
手法に関して，既存の手法の問題点を明確にする．
3.1
検索手法
検索手法とは，データを要求するピアが目的のデータを持つピアを特定するために送信す
る検索要求メッセージの転送手法を指す．P2P ネットワークにおいて用いられる検索手法と
して，以下のような 3 つの手法が提案されている [2]．
flooding
flooding による検索は以下のように行なわれる．
1. データを要求するピアは全ての隣接しているピアに対して検索要求メッセージを転送
する．
2. 検索要求メッセージを受信したピアは次のうちど ちらかの処理を行なう．
• 対象となるデータを保持している場合には検索要求メッセージを送信したピアに
対して応答メッセージを送信する．
• 対象となるデータを保持していない場合には，そのピアに対して検索要求メッ
セージを送信したピア以外の全ての隣接ピアに対して検索要求メッセージを転送
する．
3. すべての検索要求メッセージについて検索が成功するか，各検索要求メッセージの有
効期間を示す TTL(Time To Live) の値が 0 になるまで 2 の処理を繰り返す．
TTL は各検索要求メッセージに設定されており，ピアを一つ通過する毎に TTL の値が 1
ずつ減少させる．TTL が 0 になった場合は検索失敗と判断されメッセージは廃棄される．ま
10
た，power-law に従う P2P ネットワークでは，サービスを集中管理しているサーバが存在し
ないため，すべての検索要求メッセージのうち一つが検索対象となるデータを発見した場合
でも，まだ検索を成功していない他の検索要求メッセージがその検索成功を検知することが
できない．そのため，すべての検索要求メッセージにおいて，検索を成功するか、TTL が
0 になるまで処理が繰り返される．
flooding によるデータを発見するまでの検索手順を図 3.1 から図 3.3 までに示す．各図の
四角はピアを表し ，四角を結ぶ線は各ピア間の接続リンクを，中が斜線になっている四角
は検索要求メッセージの送信を行なうピアをそれぞれ示す．また，Query とは検索要求メッ
セージを指し，矢印方向に検索要求メッセージは転送される．まず図 3.1 では，データを要
求するピアが隣接ピアに対して検索要求メッセージを送信する．図 3.2 では，検索要求を受
け取ったピアが検索対象となるデータを保持していないため，検索要求メッセージをこのピ
アに対して送信したピア以外の全ての隣接ピアに対して送信する．図 3.3 では，図 3.2 と同
様に検索要求メッセージを受信したピアが隣接ピアに対してメッセージの送信を行ない，3
ホップ目で検索対象となるデータを発見している．
Expanding Ring
Expanding Ring とは前述の flooding を拡張した手法であり，以下の手順で検索を行なう．
1. TTL を flooding と比較して小さく設定し，flooding と同様の方法で検索を開始する．
2. ある時間待った後に応答メッセージを受信していない場合には，現在の TTL におけ
る検索を失敗したと判断し，TTL の値を増加させ再び flooding による検索を最初から
やり直す．
3. 2 の処理を繰り返し，検索に成功した場合，もしくは TTL が事前に設定した上限値に
達した場合には検索処理を終了する．
Expanding Ring の利点として，TTL の設定が容易であることが挙げられる．flooding に
よる検索を行なう場合，ネットワークの規模やデータの分布状況等に応じて適切に TTL を
設定することでネットワーク内で転送されるメッセージ数を最小限に抑えることが必要とさ
れるが，P2P ネットワークでは状況が時々刻々と変化していくため TTL を状況に応じて変
11
図 3.1: flooding による検索 (1 ホップ目)．
図 3.2: flooding による検索 (2 ホップ目)．
図 3.3: flooding による検索 (3 ホップ目)．
12
化させていくことは困難である．そのため，検索の成功の割合 (検索ヒット率) を高水準に
維持するためには flooding では TTL の値を高く設定する必要がある．Expanding Ring で
は常に最適な TTL で検索が終了するため，flooding と比較して各ピアを通過する検索要求
メッセージ数が削減可能となる．
Expanding Ring の検索手順もまた図 3.1 から図 3.3 で説明可能である．初期 TTL を 1 と
設定した場合，まず図 3.1 のように検索要求メッセージを転送し，検索結果が戻るまである
時間待つ．その間に応答メッセージがデータを要求するピアに届かなかった場合，TTL を 2
と設定して再び検索を行なう．検索要求メッセージの転送は図 3.1，3.2 のようにして行なわ
れる．同様にある時間待った後に TTL を 3 と設定して再検索を行ない，検索要求メッセー
ジは図 3.1，3.2，3.3 のように転送される．
k-walker random walk
k-walker random walk では以下のような手順で検索要求メッセージを転送する．
1. データを要求するピアは TTL がある値に設定された k 個の検索要求メッセージを隣
接するピアにランダムに送信する．そのため，同一のピアに対して複数のメッセージ
が送信される状況も発生し うる．
2. 検索要求メッセージを受け取ったピアは隣接するピアの内からランダムに 1 台を選択
してメッセージを転送する．検索要求メッセージを重複して受信したピアはそのメッ
セージ毎に対してそれぞれランダムに 1 台の隣接ピアを選択し転送処理を行なう．
3. 2 の処理を繰り返し，検索に成功した場合，もしくは TTL の値が 0 となった場合は検
索を終了する．
この手法の利点として，ネットワーク内で発生するメッセージの数が flooding や Expanding
Ring と比較して大きく削減可能 [2] であることが挙げられる．検索要求メッセージは最大で
TTL で設定された値と同じ回数の転送される．ここで TTL に設定された値を T とすると 1
回の検索要求におけるメッセージの転送回数は最大でも kT 回までに抑止することが可能で
ある．
13
図 3.4: k-waker random walk (1 ホップ目)．
図 3.5: k-walker random walk (2 ホップ目)．
図 3.6: k-walker random walk (3 ホップ目)．
14
k-walker random walk において k=2 として検索を行なう場合の検索例を図 3.4 から 3.6 に
示す．まずデータを要求するピアが検索要求メッセージを図 3.4 のように転送する．データ
を要求するピアには隣接ピアが 1 つしか存在しないため，検索要求メッセージが同一ピアに
対して重複して送信される．そこで，図 3.5 では各検索要求メッセージに対してそれぞれラ
ンダムに転送先を決定し検索要求メッセージの転送を行なう．隣接ピアの選択はランダムに
行なわれるため，複数の隣接ピアが存在する場合でも重複が発生する可能性がある．図 3.6
では，それらのメッセージを受け取ったピアがそれぞれ隣接ピアのうち一つをランダムに選
択して検索要求メッセージの転送を行なう．
k-walker random walk を power-law ネットワークの特性に合わせて改良した検索手法 [3]
が提案されている．以下にそれらの手法の概要を示す．
HDF(Higher Degree Forwarding)
検索要求メッセージの転送先を決定する際に，ランダムに選択するのではなく degree がよ
り高いピアへと優先的に検索要求メッセージを転送する．この手法では，検索に要するホッ
プ数を減少させることが可能である．しかし，degree の高いピアには複製の置き換えが頻繁
に発生するため，検索ヒット率が低下する．
LDF(Lower Degree Forwarding)
検索要求メッセージの転送先を決定する際に，ランダムに選択するのではなく degree が
より低いピアへと優先的に検索要求メッセージを転送する．この手法では，他の手法に比べ，
degree の低いピアに対して複製が配置されやすくなり，検索ヒット率の向上が可能である．
しかし，検索に要するホップ数は増加する．
3.2
複製配置手法
複製配置手法とは，前節で述べた検索手法を用いて検索を行なった過程において得られた
情報を基にして，データの複製を P2P ネットワーク全体に分散配置するための手法である．
power-law に従う P2P ネットワークに適した複製配置手法として，現在までに以下のような
手法が提案されている [2]．また，既存の複製配置手法の問題点については次節で説明する．
Owner Replication
15
Destination
Source
図 3.7: Owner Replication．
データを要求するピアのみが受信したデータを複製として保持しておく．他のピアには一
切の複製配置を行なわない．この手法は Gnutella で使用されているものである．
図 3.7 に Owner Replication の例を示す．この図のうち Source は検索対象となるデータ
を保持しているピアを，Destination はデータを要求するピアをそれぞれ指す．この図から，
データを要求するピア以外には複製を一つも配置しないことがわかる．このことから，Owner
Replication では，各データの複製がネットワーク全体へと分散の進行が他の手法と比較し
てゆるやかになる．そのため，複製配置によって P2P ネットワーク内に存在する各ピアに
発生する負荷を低く抑えることが可能である．
Path Replication
検索対象データを保持するピアからデータを要求するピア間において，検索要求メッセー
ジが通過したパス (データの転送パス) 上に存在するすべてのピア，及びデータを要求する
ピアが複製を保持する手法である．この手法は，Freenet で使用されている手法である．
Path Replication による複製配置の例を図 3.8 に示す．Path Replication では図のように
16
Destination
Source
図 3.8: Path Replication．
Source から Destination の間に存在する全てのピアに対して複製を配置する．そのため，ネッ
トワーク全体に容易に複製を分散可能である．
Random Replication
検索要求メッセージが通過した全てのピアからランダムにいくつかのピアを選択し，それ
らのピアに対してデータを転送し複製を配置する．他の手法と同様にデータを要求するピア
も複製を保持する．また，複製の配置先となるピアは k-walker random walk による検索要
求メッセージが届いたピアのうちから，Path Replication による複製配置ピア数と同じ数の
ピアを選択することで決定される．Random Replication は Path Replication と比較して，
1 回の検索でデータを広範囲に分散可能であるという特徴を持つ．
図 3.9 には Random Replication による複製配置の例を示している．図中の楕円で囲まれ
た範囲のピアを k-walker random walk によって検索要求メッセージが到達したピアとする場
合，複製配置先として選択される可能性があるのは斜線の入った 4 つのピアである．Random
Replication では Path Replication と同数のピアを選択し複製の配置を行なうため，この例
17
Source
Destination
図 3.9: Random Replication．
ではネットワーク内に 2 つの複製を配置することになる．
また，power-law に従う P2P ネットワークを想定していない P2P ネットワークにおける
複製配置手法について説明する．
各データの必要とされている複製数を計算し，ピアの存在確率や帯域幅などを基準に複製
配置先を決定する複製配置手法が提案 [15] されている．しかし ，これを実現するためには
Network Weather Service[16] のような予測機構が必要である．
ピアがネットワークに動的に参加・離脱を繰り返すランダムネットワークでの複製配置
手法として，ネットワークへの参加時間が確率的に高くなるピアに対して複製を配置する
Highly Up First やピアがサービスに与える有効性を計算し，有効性の高いピアに複製を配
置する Highly Avalilable First が提案 [17] されている．
18
3.3
複製配置手法の問題点
本節では，power-law ネットワークの特性を考慮した複製配置手法によるストレージ負荷
の分散を実現するために，既存の複製配置手法の問題点を明らかにする．本研究では複製配
置手法に着目しているため検索手法の問題点については割愛する．
Owner Replication を複製配置手法として用いる場合，ネットワーク内に配置される複製
数が他の手法と比較して緩やかに増加するため，検索に要する平均ホップ数が他の手法に比
べて大きくなってしまう．これにより，ピアを通過するメッセージ数も他の手法に比べて 3
倍から 4 倍の値を示すことが明らかになっている [2]．
Path Replication を複製配置手法として用いる場合には，power-law ネットワークの特性
によりデータの転送パス上に存在する確率が高くなるため，degree の高いピアに対してス
トレージへの書き込みや削除，読み込みの処理が degree の低いピアと比較して発生しやす
い状態となる．power-law ネットワークでは，degree の高いピアの停止はネットワークに大
きな影響を与え，ネットワーク全体が復旧するまでに多大な時間を要する事が現在までに明
らかになっている [9] ため，degree の高いピアに発生する負荷をできる限り抑制，分散させ
る必要がある．
Random Replication を適用する場合には複製の転送方法が問題になる．他の手法ではデー
タを要求するピアに対して検索対象となっているデータを転送する過程において複製配置が
行なわれている．しかし，Random Replication の場合にはランダムに選択したピアがデー
タの転送パス上に存在しないことがあるため，他の手法と比較して，より多くの転送を行な
う必要がある．そのため，ネットワーク内に必要以上のトラヒックが発生する．また，他の
手法と比べて実装の難しさがあることもこの手法の問題点である．
これらの中でも，Path Replication による degree の高いピアへの負荷の集中によって，
P2P ネットワークやサービ スの提供に大きな問題となることがわかる．そこで，degree の
高いピアに発生する負荷をネットワーク全体に分散する必要がある．
19
4
提案手法
本章では，既存の複製配置手法の中でも実装が容易で，かつ検索ヒット率の向上や検索に
要するホップ数の減少が可能な Path Replication を改良し，ストレージへの書き込みや読み
込みの負荷を P2P ネットワーク全体で分散可能な 2 種類の複製配置手法を新たに提案する．
4.1
Path Random Replication
既存の複製配置手法である Path Replication では，常に検索対象データを保持しているピ
アからデータを要求するピアまでの転送パス上に存在するすべてのピアに複製を配置するた
め，必要以上の複製配置処理が発生していると考えられる．そこで，Path Replication を改
良し転送パス上に存在する各ピアに対して，ある一定の確率で複製を配置する手法を Path
Random Replication として提案する．本稿ではこの複製を配置する確率を複製配置確率と
呼ぶ．複製配置確率は P2P ネットワーク上の全てのピアで一定とし ，時間変化は発生しな
いものとする．
複製配置確率を 100%とした場合は Path Replication と，0%とした場合には Owner Repli-
cation とそれぞれ等しくなる．最適な複製配置確率については 6 章で検証を行なう．
Path Random Replication の例を図 4.1 に示す．この例では，各ピアの複製配置確率を
50%とする．データを Source から Destination まで転送する際に，転送パス上に存在する各
ピアはそれぞれ独立して複製配置の可否を決定するため，各ピアの複製配置の判断は他のピ
アに影響を与えないものとする．そのため，50%と設定した場合でも双方のピアに複製が配
置される可能性が存在する．
4.2
拡張 Path Random Replication
前節で提案した Path Random Replication では，複製配置確率を一定として配置の決定
を行なった．しかし，負荷状態は各ピアによって異なるため，負荷状態を考慮して複製配置
確率を動的に決定することでより効果的な負荷分散が可能であると考えられる．そこで本節
では，Path Random Replication を拡張し，負荷状態によってピアごとに複製配置確率を動
20
Destination
Source
50%
50%
図 4.1: Path Random Replication．
的に決定する手法を拡張 Path Random Replication として提案し評価を行なう．
本研究では，複製配置確率は各ピアのストレージ使用率 (0 ≤ x ≤ 1) により決定する．こ
れは，他のピアが持つ情報を取得し比較する必要がなく，各自の持つストレージ使用率の情
報のみで複製配置の決定を行なうことが可能で，かつ x の値の範囲が 0 から 1 までと固定さ
れるためである．この関数は，ピアのストレージ使用率が高くなるとともに複製配置確率を
急激に低下することが望ましく，指数分布の累積分布関数である F (x) = 1 − e−λx を x = 1
で正規化した関数を使用したものを確率関数として式 (4.1) に定義する．
f (x) = 1 −
F (x)
(1 − e−λx )
=1−
.
F (1)
(1 − e−λ )
(4.1)
また，指数分布の累積分布関数と同様の特性を持つ，べき分布の確率分布関数 F (x) = xα
を用いた確率関数を式 (4.2) で定義する．
f (x) = 1 − xα .
21
(4.2)
! "
#$&%'" #
図 4.2: 拡張 Path Random Replication における確率関数の特性．
これらの確率関数を用いた際に，対象となるピアに対して複製を配置する割合を Rate(0 ≤
Rate ≤ 1) とし，式 (4.1)，(4.2) の λ，α は式 (4.3) を満たすように設定する
Z 1
0
f (x)dx = Rate.
(4.3)
指数分布，べき分布を使用した確率関数がそれぞれ示す特性は図 4.2 のようになる．図の横
軸はピアの負荷 (Peer Load)，つまり本稿ではストレージ使用率を示しており，縦軸は複製配
置確率を示している．また，ピアの負荷が上限値の場合に P eerLoad = 1 となり，逆に下限
値の場合には P eerLoad = 0 となる．図中の exponential は正規化した指数分布，power-law
はべき分布をそれぞれ使用した確率関数を示す．また，これらは Rate = 0.25 と設定した場
合を示している．この図からわかるように，指数分布の確率関数はべき分布の確率関数と比
較して，負荷が低い時に複製配置確率が高くなることがわかる．また，図の場合では負荷の
上限値の 2 割程度の負荷を境にしてこの双方の特性が入れ替わっていることもわかる．さら
に，負荷が高くなるとどちらの関数を使用しても急激に複製配置確率が低下することがわか
22
図 4.3: 拡張 Path Random Replication．
る．これらのことから，指数分布の確率関数の場合には負荷が低い状態では高い複製配置確
率を維持し，負荷が上限値の 6 割以上の値を示す時には急激に複製配置確率が 0%に近い値
となる．また，べき分布の確率関数の場合には，負荷が非常に小さい時には高い複製配置確
率を示すが，それ以上に負荷が高くなった場合には，指数分布の確率関数よりも緩やかに複
製配置確率が 0%へと近づいていくことがわかる．
図 4.3 は複製配置確率を動的に決定し複製配置を行なう例を示す．例として，転送パス上
のピアのうち Destination に近いピアの方がもう一方のピアと比較してストレージを多く使
用しているとする．例として，ここでは各ピアのストレージ使用率を考慮して各ピアで動
的に決定される複製配置確率は 20%，75%と決定する．各ピアはここで決定した値を基に，
Path Random Replication と同様にそれぞれのピアが独立に複製配置の可否を決定する．
23
5
シミュレーションモデルと評価指標
本章では，提案手法の評価を行なうために使用したシミュレーションのモデルと各条件に
ついての説明を行なう．そして，本論文において用いた検索性能の評価指標やストレージの
負荷分散の指標について解説を行なう．
5.1
シミュレーションモデル
提案した複製配置手法による負荷分散の効果を示すために，シミュレーションによって評
価を行なう．以下では，シミュレーション条件として用いた各パラメータについて説明する．
シミュレーションにおいて使用したパラメータと値を表 5.1 に示す．これらのうち，シミュ
レーションにおいて重要となるパラメータの具体的な説明は以下の通りである．
ト ポロジ
使用するトポロジは各ピアの degree が power-law に従うネットワークでとする．power-law
に従うネットワークトポロジの生成は以下の手順 [18] で行なわれる．
1. 初期状態として m0 個のピアが m0 − 1 本のリンクでそれぞれ接続されている．
2. 各時間ステップごとに以下のど ちらかの処理を行なう．
• p の確率でネットワーク内に m ≤ m0 本のリンクを追加する．この時 degree の
値が大きいほど リンクが追加される可能性が高くなる．
• 1 − p の確率で新たなピアをネットワークに追加する．この時追加されたピアは m
本のリンクを持ち，接続先は degree の高いピアほど 選択される確率が高くなる．
3. シミュレーション条件を満たすまで 2 の処理を繰り返す．
本稿ではれぞれの結果において比較が容易であることとトポロジの違いによる有意な差
が現われなかったためすべてのシミュレーションを同一のトポロジで行なう．使用したト
ポロジにおいて各ピアの degree が高い順にプロットすると図 5.1 のようになる．図の横軸
は degree 数の順位 (Rank) であり，degree が高いほど Rank は低い値となる．図の縦軸は，
24
degree を示している．また，シミュレーション中にピアがネットワークから離脱したり，新
たにピアがネットワークに参加したりというネットワークの動的な変化は発生しないものと
する．
初期データ数
各データがシミュレーション開始時にネットワーク内にいくつ存在するかを示すパラメー
タである．本研究では，シミュレーション開始時に各データがネットワーク内に 10 個ずつ
存在する状態において評価を行なう．また，各データのサイズ (保持するために必要なスト
レージ容量) は 1 とする．
ストレージ容量
ストレージ容量は，シミュレーションによって示す特性に最も大きな影響をもつパラメー
タである．本稿では基本的にストレージ容量は 20，つまりデータを 20 個まで保存可能とし
てシミュレーションを行なう．
検索手法
検索手法として k-walker random walk において 16 個の検索要求メッセージを使用する
16-walker random walk を用いる．この手法を選んだ理由として，検索に要するホップ数が
flooding や Expanding Ring に比べて大きくなるが，検索の際に発生する検索要求メッセー
ジが flooding や Expanding Ring と比べて大幅に軽減可能なためである．
複製置き換え
ストレージ容量の限界までデータを保持している場合に複製配置要求が発生した場合，現在
保持している複製を削除する必要がある．この削除手法を複製置き換え手法とし，FIFO(First
in First Out) を用いる．FIFO はピアに配置された時刻が最も古いデータから削除してい
く手法である．また，シミュレーション開始時に保持してるデータは各ピアのオリジナルの
データとして扱い，FIFO による削除の対象としない．
5.2
評価指標
本論文では検索性能を一定水準に維持しつつ，ストレージに発生する読み込みや書き込み
の負荷をネットワーク全体に分散することを目的としている．読み込み負荷とは検索対象
25
表 5.1: シミュレーション条件．
パラメータ
値
トポロジ
power-law
全ピア数
10,000
全リンク数
20,000
データ種類
100
初期データ数
10
ストレージ容量
20
検索試行回数
50,000
TTL
100
検索手法
16-walker random walk
複製置き換え
FIFO
データを保持しているピアがデータを転送する際に発生するストレージへのアクセスを指
し，書き込み負荷とはデータを要求するピアにデータが転送される過程において発生する複
製配置によるストレージへの書き込み処理を指す．また，これらを合わせた負荷を本研究で
はストレージ負荷と定義する．読み込みや書き込みの発生回数が多いピアはストレージ負荷
が高いピアであるといえる．
そこで，検索性能の評価指標として検索に要した平均ホップ数 (検索ホップ数) を指標と
して用いる．検索ホップ数とは，1 回の検索において検索成功までに検索要求メッセージが
費やしたホップ数の平均値である．
提案手法の評価ではネットワーク内に配置される複製数が，既存手法である Path Repli-
cation と比較して複製配置確率が低いために，検索に要する平均ホップ数が悪化する可能性
が高い．そこで本研究では，例として複製配置手法として Path Replication を用いた場合に
示す検索ホップ数の 120%の値を検索ホップ数の閾値とし，閾値以上の検索ホップ数を要し
た場合の結果については，検索性能が一定の水準を維持できずに大幅に劣化が見られたと判
26
1000
degree
100
10
1
1
10
100
Rank
1000
10000
図 5.1: 生成されたトポロジの degree．
断し，この検索ホップ数に対応する複製配置確率を評価の対象としない．
また，ネットワーク全体への負荷分散については各ピアの degree を横軸，ストレージの
負荷を縦軸としてグラフを作成し，それを最小二乗法を用いて線形回帰を行なう．この回帰
直線の傾きの値を負荷分散の指標とする．この傾きの値が小さいほど degree の高いピアと
低いピアの間の負荷の差が小さい状態であり，負荷がネットワーク全体に分散されていると
いえる．逆にこの値が大きい場合には，ネットワーク内の特定のピアに対して負荷が集中し
ている状態であるといえる．
27
6
結果および考察
本章では，提案手法である Path Random Replication と拡張 Path Random Replication
について基本的な特性を明らかにする．また各提案手法を用いた場合，既存の手法と比較し
てストレージに発生する負荷をどの程度分散可能であるかを調査する．
6.1
Path Random Replication の基本特性の調査
本節では，提案手法の一つである Path Random Replication において複製配置確率を変
化させることで，検索性能やストレージの負荷分散がどのような特性を示すかについて調査
する．
6.1.1
検索ホップ数について
始めに，複製配置確率の変化が検索ホップ数に与える影響について調査する．
図 6.1 は，50,000 回の検索のうち 25,000 回から 45,000 回目までの検索における複製配置
確率と検索ヒット率の関係を示す．図の横軸は複製配置確率を，縦軸には検索ホップ数をそ
れぞれ示している．また前述した通り，複製配置確率が 100%の場合には Path Replication
と，0%の場合には Owner Replication と等しい．図中の threshold は Path Replication を適
用した際の検索ホップ数を基準として算出する検索性能の閾値を示す．閾値は 5 章で示した
ように，Path Replication の際に要した検索ホップ数の 120%の値とする．この図から，複
製配置確率が高くなるにつれて検索に要する検索ホップ数は小さくなり，逆に複製配置確率
が 0%に近付くと検索ホップ数は非常に大きくなる．特に，複製配置確率を 0%から 2%の間
に設定すると，閾値以上の検索ホップ数を示しており，Owner Replication と同等となる複
製配置確率が 0%の場合には Path Replication の検索ホップ数の 2 倍に近い値を示す．
これは，複製配置確率を低く設定することでネットワーク内に配置される複製数が減少
し，検索対象データを持つピアが減少したためである．特に Owner Replication と同等であ
る複製配置確率が 0%の場合には，ネットワーク内に十分な数の複製が配置されないために
検索ホップ数は大幅に増加してしまう．また，複製配置確率が 100%の場合と 20%の場合を
28
"!#$%&')(*'+
-,'$%./,0*21 3
図 6.1: 複製配置確率と検索ホップ数の関係．
比較して検索ホップ数が大きく変わらない原因として power-law ネットワークの特性が大き
く関わっている．power-law ネットワークでは，degree の高いピアが検索等のサービスに与
える影響が大きく，多くの隣接ピアがあるために検索要求メッセージが頻繁に通過し検索対
象データを転送する際のパス上に存在する確率が degree の低いピアに比べて非常に高くな
る．そのため，複製配置確率を低く設定した場合においても，degree の高いピアには十分な
数の複製が配置され，結果として検索ヒット率を良好な値に保つことが可能となる．
今後の結果では，検索ホップ数が検索性能の閾値を超えたため，複製配置確率が 0%から
2%までの場合の負荷分散については取り扱わない．
6.1.2
ストレージに発生する負荷の分散
Path Random Replication における複製配置確率の変化とストレージに発生する読み込
み負荷，書き込み負荷の関係について示す．
まず，複製配置確率をそれぞれ 100%，80%，50%，10%と設定した場合の degree と書き
29
!" #
$%$'& ()+*& ),+-.!" #
/"10 #
2$%$'& ()+*& )3-./"10 #
/" #
2$%$'& ()+*& )3-./" #
/" ,#
2$%$'& ()+*& )3-./" ,#
図 6.2: degree と書き込み回数の関係．
込み回数の関係を図 6.2 に示す．図の横軸は各ピアの degree を，縦軸はストレージへの書
き込み回数を示している．また，図中の Rate は設定した複製配置確率を，Regression Line
は各複製配置確率における degree と書き込み回数の関係を最小二乗法を用いて線形回帰を
行なった際の回帰直線をそれぞれ示す．この直線の傾きは 5 章で説明したように負荷の分散
の程度を示す．この図から，複製配置確率を低く設定することで，ストレージへの書き込み
負荷をネットワーク全体に分散可能となることがわかる．
さらに詳しく書き込み負荷に関する特性を調べるために，図 6.3 に複製配置確率の変化と
書き込み回数の線形回帰による回帰直線の傾きの関係，つまり複製配置確率と書き込み負荷
の偏りの度合いを示す．この図の横軸は複製配置確率を，縦軸は線形回帰を行なった回帰直
線の傾きを示している．この図から複製配置確率を低く設定することで書き込み負荷の傾き
は単調に減少していくことがわかる．このような特性を示す理由として図 6.1 に示したよう
に複製配置確率を低く設定しても検索ホップ数にあまり低下がみられないため，複製配置確
率の減少がそのまま各ピアに発生する複製配置処理回数の減少に直結したことが挙げられる．
30
"!#%$'&(*) +
図 6.3: 複製配置確率と書き込み負荷の関係．
これらの結果から，ストレージへの書き込み負荷は複製配置確率が低いほどネットワーク
全体へ分散可能であることがわかる．
図 6.4 には複製配置確率を変化させた場合の degree と読み込み回数の関係を示している．
縦軸はストレージに発生した読み込みの回数を示している．この図より，複製配置確率を低
く設定すると読み込み回数の偏りが増加していることがわかる．複製配置確率が低く設定さ
れている場合でも degree の高いピアは power-law ネットワークの特性から検索対象データ
を保持しているピアからデータを要求するピアまでの転送パス上に存在する確率が degree
の低いピアと比べて非常に高くなる．そのため，degree の高いピアには複製配置確率を低く
設定した場合にも十分な数の複製が配置される．しかし ，degree の低いピアはデータの転
送パス上に存在する確率が低く，複製配置確率が低い場合には複製が配置されにくい状態と
なる．つまり，複製配置確率が低い場合には検索要求メッセージは十分に複製を持つ degree
の高いピアで検索対象データを発見する確率が，複製配置確率を高く設定した場合と比較し
て高くなるため，degree の高いピアに発生する負荷は分散されない状態となる．
31
! "
#$#&% '(*)% (+*,- ! "
.!0/ "
1#$#&% '(*)% (2,-.!0/ "
.! "
1#$#&% '(*)% (2,-.! "
.! +"
1#$#&% '(*)% (2,-.! +"
図 6.4: degree と読み込み回数の関係．
逆に複製配置確率を高く設定した場合には図中の複製配置確率が 100%の場合と 80%の場
合のように傾きに有意な差が表れないことがわかる．これは，複製配置確率が高く設定され
ると degree の高いピアだけでなく degree の低いピアにも十分な数の複製が配置されるため
である．そのため，degree の低いピアが検索対象データを持っている確率が高くなり，複製
配置確率が低く設定されている場合と比較して読み込み負荷が分散されやすい状態となる．
さらに詳しく読み込み負荷の特性を調査するために図 6.5 に複製配置確率の変化と読み込
み負荷の回帰直線の傾きを示す．図からわかるように，複製配置確率が 50%以上になると傾
きの値に大きな差が見られないことがわかる．これは，複製配置確率を 50%程度に設定する
ことで読み込みの負荷をネットワーク全体に分散可能な程度の複製の分散配置が行なわれる
ためである．また，複製配置確率を低く設定すると読み込み負荷は分散されず傾きが大きく
なることがわかる．
以上の結果より，ストレージへの書き込みによる負荷は複製配置確率を低くすることで
P2P ネットワーク全体に分散可能であるが，ストレージの読み込みによる負荷は複製配置
32
!"#$%#$
図 6.5: 複製配置確率と読み込み負荷の関係．
確率を低くすると degree の高いピアに集中してしまうことがわかる．
6.1.3
最適な複製配置確率の推定
前節では，Path Random Replication を適用し複製配置確率を変化させることによるス
トレージの読み込み，書き込みの負荷の特性を調査した．そこで本節では，前節で明らかに
なった読み込みと書き込みのそれぞれの負荷を合わせたストレージ負荷の特性を調査する．
図 6.6 には，ストレージ負荷と degree の関係を示している．この図から，複製配置確率
を低く設定することでストレージ負荷を分散可能であることがわかる．これは，図 6.3 に示
す，複製配置確率を低く設定することで負荷分散が可能となる書き込み負荷と，図 6.5 に示
す，複製配置確率を高く設定することで負荷分散が可能となる読み込み負荷の影響をそれぞ
れ比較した場合に書き込み負荷の影響が強いためである．
しかし，読み込み負荷の影響は無視できるほど小さいものではないと予想される．そこで，
複製配置確率の変化とストレージ負荷の偏りの関係を図 6.7 に示す．この図から，複製配置
33
!#" $%'&" %(')* +-, .!#" $%'&" %/)*+-, + .!#" $%'&" %/)*+ + (
.!#" $%'&" %/)*+ (
図 6.6: degree とストレージ負荷の関係．
"!#$"%
図 6.7: 複製配置確率とストレージ負荷の関係．
34
!"#%$&'
図 6.8: 複製配置確率とストレージ負荷の関係 (一部拡大)．
確率を 10%前後に設定することでストレージ負荷の分散を表す直線の傾きを最小とするこ
とが可能になる．複製配置確率を 10%より大きく設定した場合には書き込み負荷の影響か
ら傾きの値が大きくなり，逆に複製配置確率を 10%より小さくした場合には読み込み負荷の
影響によって傾きの値が大きくなる．
最適な複製配置確率を明らかにするため，図 6.8 に図 6.7 における 0%から 40%までの部
分の拡大図を示す．この図より，複製配置確率を 9%から 14%の間において，その中でも特
に複製配置確率を 12%と設定した場合にストレージ負荷の傾きの値が最も小さくなること
がわかる．
これらの結果から，提案手法である Path Random Replication において複製配置確率を
9%から 14%程度に設定することで検索性能を維持しつつストレージに発生する読み込みや
書き込みの負荷をネットワーク全体に分散可能となることがわかる．
35
"!#$&%#%#!#!
' (")*
図 6.9: 置き換え手法と検索ホップ数の関係．
6.1.4
シミュレーション条件を変化させた場合
前節までのシミュレーションではすべて表 5.1 に示したシミュレーションモデルを用いて
行ない，その結果 Path Random Replication を行なうのに最適な複製配置確率が 9%から
14%の間であることが明らかになった．そこで，本節ではシミュレーションの条件を変化さ
せた場合の特性について調査を行なう．
まず始めに，ストレージの使用率が 1 であるピアに複製配置処理が発生した場合におい
て，複製の置き換え手法についての条件を変更した場合について考える．置き換え手法とし
ては現在，作製された時刻が最も古いデータを置き換える FIFO によって行なっている．そ
こで，置き換えを行なうデータを選択する際の条件として，最もアクセス間隔が長いデータ
を選択する場合と，ランダムに置き換えを行なう場合の結果について評価を行なった．また，
ここでの評価では複製配置確率を 5%刻みで変化させて評価を行なう．
図 6.9 には各置き換え手法における複製配置確率と検索ホップ数の関係を示す．図中の Last
Access は最もアクセス間隔の長いデータを置き換える場合，Random はランダムにデータ
36
(*)"(,+
-/.0132020!.0.
45/67
"!$# %'&
図 6.10: 置き換え手法とストレージ負荷分散の関係．
を置き換える場合を示す．図から，3 つの手法の中でどの手法を用いても結果や特性にほと
んど 差がないことがわかる．
図 6.10 には各置き換え手法における複製配置確率とストレージ負荷を線形回帰した直線
の傾きの関係を示す．この図からも，3 つの置き換え手法のうちどの手法を用いた場合にも
負荷分散の特性に，有意な差がないことがわかる．これらの結果から置き換え手法はこれら
の特性にほとんど 影響を与えないことがわかる．これは，アクセス間隔や作成時刻を複製置
き換えのパラメータをとしても検索性能や負荷分散には影響を与えないことを示している．
次に，ストレージ容量を変化させた場合の特性について調査を行なう．ここではストレー
ジ容量が 5，10，20，40，80 の場合における検索ホップ数や読み込み，書き込みの各負荷に
ついて調査を行なう．
ストレージ容量を変化させた場合の検索ホップ数を図 6.11 に示す．この図から，ストレー
ジ容量が大きいほど 検索ホップ数は小さくなることがわかる．これは，ストレージ容量が大
きいほど 保持可能な複製数が多くなり，多くの種類のデータを格納可能となるためである．
37
!"#$%& '!"#$%& '!"#$%& %
'!"#$%& %
'!"#$%& %
図 6.11: ストレージ容量と検索ホップ数の関係．
!"#$%& '!"#$%& '!"#$%& %
'!"#$%& %
'!"#$%& %
図 6.12: ストレージ容量と書き込み負荷の関係．
38
! "$#%'&$( ! "$#%'&( )
! "$#%'&( ! "$#%'&( ! "$#%'&( 図 6.13: ストレージ容量と読み込み負荷の関係．
図 6.12 にはストレージ容量と書き込み負荷の傾きとの関係を示している．このような特
性を示すのは，ストレージの容量を大きく設定することで検索ホップ数が小さくなり，複製
配置の候補となるピア数が減少し，複製配置処理の発生回数が抑えられるためである．この
結果から，書き込み負荷は検索ホップ数の増減に依存することがわかる．
図 6.13 にはストレージ容量と読み込み負荷の関係を示す．この図より，ストレージ容量が
小さいほど 読み込み負荷は分散されていることがわかる．これは，ストレージ容量が大きい
場合には検索ホップ数が小さくなり，1 ホップ目か 2 ホップ目で検索対象のデータを発見す
る確率が高くなるためである．power-law ネットワークの特性からほとんどのピアは degree
の高いピアに 1 ホップか 2 ホップで接続している．検索要求は各ピアで平均的に発生するた
め，多くの検索要求メッセージは 1 ホップか 2 ホップで degree の高いピアに転送される．ス
トレージ容量を 80 と設定した場合，全データの種類が 100 でありストレージ容量を限界ま
で使用しているピアは全体の 80%のデータを保持しているため，検索対象データを持ってい
る確率は極めて高い．そのため，ストレージ容量が大きいほど 少ないホップ数で目的のデー
39
!"# $ !"# $ !"# "
$ !"# "
$ !"# "
図 6.14: ストレージ容量とストレージ負荷の関係．
タを持つピアへたどり着く確率が高くなるため，読み込み負荷の負荷分散が効果的に行なえ
ないことがわかる．
図 6.12，6.13 に示した書き込みと読み込みの負荷を合わせたストレージ負荷と複製配置
確率の関係を図 6.14 に示す．図の横軸はストレージ容量，縦軸は複製配置確率をそれぞれ
表している．この図から，最適な複製配置確率はストレージ容量によって異なることがわか
る．そこで，図 6.15 にストレージ容量を変化させた場合に，各ストレージ容量においてス
トレージ負荷の回帰直線の傾きが最小となるときの複製配置確率を示す．この図から，スト
レージ容量が小さいときは複製配置確率を低く，ストレージ容量が大きい時には複製配置確
率を高く設定することで効果的に負荷分散が可能であることがわかる．これは，ストレージ
容量が小さい場合には読み込み負荷よりも書き込み負荷の影響が大きいため，複製配置確率
が低いほど 分散され，同様にストレージ容量が大きい場合には書き込み負荷よりも読み込み
負荷の方が影響が大きいために複製配置確率が高い状態ほど 負荷分散されるためである．つ
まり，ストレージ容量を変化させることで最適な複製配置確率が変化することがわかる．
40
&(' ()+*%
!#" %$
図 6.15: ストレージ容量とストレージ負荷が最小となる複製配置確率の関係．
次に，検索試行 1,000 回ごとに検索ホップ数や書き込み，読み込みそれぞれの負荷の特性
の調査を行なった．
まず，検索試行 1,000 回ごとの検索ホップ数を図 6.16 に示す．横軸の Search は検索試行
回数を示す．この図から複製配置確率が 0%の場合，つまり Owner Replication の場合のみ
検索ホップ数が他の場合と比較して大きな値を示している．これは，Owner Replication の
場合には複製がネットワーク内に十分に分散配置されないためである．
複製配置確率が 0%以外の結果を詳し く見るために図 6.17 に図 6.16 の検索ホップ数が 2
から 4 の範囲を拡大した図を示す．この図からわかるように，検索ホップ数は複製配置確率
が 10%の場合は他の場合に比べてわずかに増加しているがその他の確率ではすべてほぼ同
等の結果を示している．これは，複製配置確率が 100%でなくでも検索試行の初期段階で検
索ホップ数に与える影響の大きな degree の高いピアに対して十分な数の複製がネットワー
ク全体に分散配置されていることを示している．
図 6.18 には検索試行 1,000 回ごとの書き込みの負荷を示す．この結果から，書き込み負荷
41
! "
#!$ "
#! "
#! "
#%! "
図 6.16: 検索試行 1,000 回ごとの検索ホップ数．
! "
#!
$ "
#! "
#! "
%! "
図 6.17: 検索試行 1,000 回ごとの検索ホップ数 (一部拡大)．
42
$ %& '
$ %
& '
$ %
& '
$ %
& '
$ %
(& '
!#"
図 6.18: 検索試行 1,000 回ごとの書き込み負荷．
は検索試行の初期段階から最後までほとんど 変化しないことがわかる．これは，検索ホップ
数にほとんど 変化がないため複製配置確率を低く抑えることでネットワーク内で発生する複
製配置処理を減らすことができるためである．Owner Replication の場合は，データを要求
したピアのみが複製を保持するために書き込み負荷が，ほぼ完全に分散されている．
図 6.19 には検索試行 1,000 回ごとの読み込みの負荷を示す．この結果から，読み込み負荷
も Owner Replication の場合のみ低い値を示していることがわかる．また，複製配置確率が
10%の場合には読み込み負荷が他の場合と比較して高くなっていることがわかる．これは，
複製配置確率が高い場合と比較して複製の多くが degree の高いピアに偏っているためであ
る．検索試行回数が増えるにつれ，ネットワーク内に複製が全体に分散されるために読み込
み負荷は低下していく．
図 6.20 には検索試行回数 1,000 回ごとのストレージ負荷を示す．ストレージ負荷は，検
索試行回数によらず複製配置確率が低いほど 分散されていることがわかる．これは，読み
込み負荷と比較して書き込み負荷の方がストレージ負荷に与える影響が大きいためである．
43
# $%& '(
# $)& (
# $)& (
# $)& (
# $)& (
"!
図 6.19: 検索試行 1,000 回ごとの読み込み負荷．
!
" !
!
!
# !
図 6.20: 検索試行 1,000 回ごとのストレージ負荷．
44
Owner Replication の場合はストレージ負荷の特性が読み込み特性とほぼ同じとなる．これ
は，Owner Replication では書き込み負荷は完全に分散されており，読み込み負荷の影響を
強く受けるためである．
6.2
拡張 Path Random Replication による負荷分散
前節では複製配置確率を静的に設定する Path Random Replication に関する調査を行なっ
た．しかし，静的に複製配置確率を設定した場合，各ピアの状態に関係なくすべてのピアが
同等として扱われる．そのため，各ピアの負荷を考慮することで Path Random Replication
以上に負荷分散が可能であると考えられる．そこで，本節では各ピアのストレージの使用率
を考慮して動的に複製配置確率を変化させることが可能な拡張 Path Random Replication
についての評価を行なう．
6.2.1
基本特性
まず，拡張 Path Random Replication を適用することにより，読み込み負荷や書き込み
負荷に与える影響について調査を行なう．複製配置確率を与えるために使用する関数はそれ
ぞれ式 (4.1)，(4.2) とする．
図 6.21 には複製配置の割合と検索ホップ数の関係を示す．ここで図の横軸は式 (4.3) にお
ける平均的な複製配置の割合である Rate を指す．複製配置の割合を決定することによって
各確率関数の λ や α が決定し ，その値とストレージ使用率を基にして複製配置確率を決定
する．例として，複製配置の割合を 20%，つまり Rate = 0.2 とするとそれぞれ λ = 4.801，
α = 0.250 となる．また図中の Expornantial は指数分布の確率関数，power-law はべき分布
の確率関数をそれぞれ用いて拡張 Path Random Replication を適用させた場合の検索に要
した検索ホップ数を示している．それぞれ，複製配置の割合を 0.01 から 0.99，つまり 1%か
ら 99%まで範囲で変化させて特性を調査した．
この図から，指数分布の確率関数の場合には複製配置の割合が 7%以下に，べき分布の確
率関数の場合には 1%にそれぞれ設定することで検索ホップ数が閾値を越えてしまうことが
わかる．これは，平均的な複製配置の割合を低く設定すると関数の特性から少数でも複製
45
"#%$&')(+*,
-/.10*324')'%5 6
0*7832:9;6 7
%$+2<=#$)*36 (
!
図 6.21: 複製配置確率と検索ホップ数の関係．
を持つピアに対して，決定される複製配置確率が 0%に近い値を示すため，新たな複製がピ
アに配置されなくなるためである．また，指数分布の確率関数の場合は複製配置の割合を
30%以上に設定した場合と 100%に近い値に設定した場合の検索ホップ数にほとんど 差がな
い．べき分布の確率関数の場合は複製配置の割合を 20%以上に設定すると 100%の時の検索
ホップ数との差がほとんどない状態となる．このことから，拡張 Path Random Replication
を適用させることにより複製配置の割合を 20%や 30%程度に設定した場合でも検索ホップ数
をある一定の水準に保つのに必要なだけの複製を配置可能であることが分かる．また Path
Random Replication を適用した場合の検索ホップ数と各確率関数で比較すると，べき分布
の関数を適用させた場合には複製配置の割合を 20%以下に設定することで他の手法よりも
検索ホップ数が低く抑えられることがわかる．それ以外の範囲では指数分布，べき分布を使
用した確率関数が，ともに Path Random Replicaiton の検索ホップ数より悪化している．
次に，拡張 Path Random Replication の読み込み負荷と書き込み負荷の特性を Path Ran-
dom Replication を適用した場合と比較して評価する．図 6.22 には複製配置確率と書き込み
46
"!#$&%(')
*,+.-'0/1$&$"2 3
-'450/7683 4
図 6.22: 複製配置確率と書き込み負荷の関係．
負荷の偏りの関係を示す．Path Random Replication を使用した場合と比較して飛躍的に書
き込み負荷を分散可能であることがわかる．これは，確率関数として使用する関数の性質に
より，ストレージの使用率が高くなると複製配置確率が 0%に近くなるため，比較的データ
の転送パス上に存在する可能性の高い，degree の高いピアに対して複製の配置があまり発
生しないためである．
図 6.23 には，複製配置の割合と読み込み負荷の偏りの関係を示す．読み込み負荷もまた，
Path Random Replication と比較して効果的に負荷分散されていることがわかる．これは，
拡張 Path Random Replication を使用することにより degree の低いピアに対しても十分に
複製が配置されることにより degree の高いピアに集中しやすい読み込み負荷が degree の低
いピアにも分散されたためである．
図 6.24 には，複製配置の割合を変化させた場合のストレージ負荷の偏りを示している．指
数分布，べき分布のどちらの確率関数を適用した場合でもストレージ負荷は読み込み負荷と
ほぼ同じ特性を示している．これは，書き込み負荷が 0.1 前後とかなり小さい値を示し複製
47
"!#$&%(')
*,+.-'0/1$&$"2 3
-'450/7683 4
図 6.23: 複製配置確率と読み込み負荷の関係．
!"$#&%'
(*),+%.-/"$" 0 1
+%23.-5461 2
図 6.24: 複製配置確率とストレージ負荷の関係．
48
配置の割合の変化にほとんど 影響されないためである．この結果から，拡張 Path Random
Replication では複製配置の割合を高い値に設定することでストレージ負荷を，より効果的
に P2P ネットワーク上へ分散可能であることがわかる．
これらの結果から，シミュレーションの初期段階で高い複製配置確率となり，ストレー
ジ使用率が高くなったピアは複製配置確率を低下させることが可能な，拡張 Path Random
Replication は Path Random Replication と比較して効果的にストレージ負荷の分散が達成
可能であるといえる．
6.2.2
新規データを追加した場合
前節では，拡張 Path Random Replication によって検索性能を維持しつつストレージ負
荷を Path Random Replication 以上に分散可能であることを示した．しかし ，前節で示し
た拡張 Path Random Replication を適用させた場合，ネットワーク内に新たな種類のデー
タが追加された時点でストレージ容量がある一定以上のピアには複製配置処理が発生しにく
い状態となる．そのため，新たに追加されたデータがネットワーク全体に分散配置されずに
検索性能が著しく低下する恐れがある．そこで，本節では新規にデータの種類を追加する場
合を想定し拡張 Path Random Replication を改良し評価を行なう．
これまでの拡張 Path Random Replication では，ストレージの使用率のみを用いて複製
配置確率を決定しており，検索対象となったデータの扱いはすべて同一としている．そのた
め，ストレージ使用率の高いピアでは新規にデータが追加された場合でも複製配置確率を低
く決定する．その結果，それらのデータがネットワーク全体に分散配置されるのを阻害して
しまう．そこで，本節では拡張 Path Random Replication で各ピアにおいて式 (4.1)，(4.2)
を用いて複製配置確率を計算する際に使用する x を以下のように定義する．
x=
ストレージ使用率 + 配置時刻による補正値
, (0 ≤ x ≤ 1)．
2
配置時刻による補正値とは，複製配置確率を決定する際に，データの配置された時刻により
補正を行なうためのパラメータであり，新しいデータほど 複製が配置されやすくなる．各ピ
アが持つすべてのデータを配置時刻順に順位付けを行ない，対象データの順位をそのピアの
49
#$&%'(*),+.0/21+435((&6 7 89;:=<?>
.0/21+435((&6 7 89;:A@CB
1,+DE3GFH7 DI89;:=<?>
1,+DE3GFH7 DI89;:A@CB
&%,3GJ$%*+47 )
"!
図 6.25: 新たにデータを追加した場合の検索ホップ数．
保持する全てのデータ数で割ることで配置時刻による補正値を算出する．例えば，検索対象
データを保持しているピアが全部で 10 個のデータを保持しており，その中で検索対象デー
タが 4 番目に新しいデータであったとする．この場合，配置時刻による補正値は 4/10 = 0.4
となる．配置時刻による補正値の計算は検索対象データを持つピアが行ない，データを転送
する際に，この補正値の情報も併せて送信する．データの転送パス上のピアは複製配置確率
を計算する際には，各自のストレージ使用率と送信された補正値の情報を用いる．本節では，
シミュレーションの条件を変更し，検索試行回数が 20,000 回の時に新たに 10 種類のデータ
をそれぞれ 10 個ずつネットワーク内に追加して評価を行なう．その他の条件はすべて表 5.1
と同じとする．
図 6.25 には，配置時刻による補正を行なった場合と行なわなかった場合の検索ホップ数を
それぞれ示している．図中の補正ありは配置時刻による補正を行なった場合の結果を示し ，
補正なしは補正を行なわずに前節と同様にストレージの使用率のみで複製配置を行なった結
果を示す．また，threshold は変更した条件下における Path Replication の検索ホップ数か
50
!#"$%'&)(*
+-,/.(102%%#3 4 5687:9<;
+-,/.(102%%#3 4 5687>=@?
.)(AB0DCE4 AF5687:9<;
.)(AB0DCE4 AF5687>=@?
#")0DG!"'(14 &
図 6.26: 追加したデータ検索のみの検索ホップ数．
ら算出した閾値を示す．これらの結果から，補正を行なった場合には複製配置の割合を低く
設定しても検索ホップ数がほとんど 劣化しないことがわかる．これは，補正を行なうことに
よってストレージの使用率のみを使用した場合では複製配置が発生しなかったピアに対して
も複製配置処理が発生するようになり，複製がネットワーク全体に分散される機会が増えた
ためである．Path Random Replication を適用した場合や，補正を行なわなかった場合は図
6.1 や図 6.21 に示した検索ホップ数と同様に複製配置の割合を高く設定することで低く抑え
ることが可能である．しかし，同じ複製配置の割合での検索ホップ数はわずかに劣化してい
る．これは，図 6.1 や図 6.21 で示した検索ホップ数と比較して，データの種類が増えたがス
トレージ容量は変化しておらず，ピアが検索対象のデータを持つ確率がわずかに低くなった
ためである．
そこで，追加したデータのみに限定した場合の検索に要した検索ホップ数を図 6.26 に示
す．この図の threshold は Path Replication において，追加したデータの検索ホップ数から
算出した閾値を示している．この図もまた検索試行回数が 25,000 回目から 45,000 回目まで
51
!#"$%'&)(*
+-,/.(102%
%
#3 4 5687:9<;
.)(=>0@?A4 =B5687:9<;
図 6.27: 補正を行なった場合の書き込み負荷．
の検索に要した検索ホップ数を示しているが 20,000 回の検索試行終了時にネットワークに
新たに追加されたデータのみを対象としている．この図から，補正を行なった場合や Path
Random Replication を適用した場合には図 6.25 に示した検索ホップ数とほぼ同等の値を示
している．これは，配置時刻による補正によって新たに追加されたデータに対してネット
ワーク内の複製の分散配置が効果的に行なわれたことを示している．つまり，補正による分
散配置は検索性能の維持に効果があることがわかる．また，補正を行なわなかった場合の検
索ホップ数は閾値以上の値を常に示している．これは，補正を行なわないため新たに追加さ
れたデータのネットワーク内での分散配置が効果的に行なわれないことが原因である．
これらの検索ホップ数の結果から，補正を行なわない場合と Path Random Replication
の複製配置確率が 14%以下の場合の結果は今後取り扱わない．
次に，補正を行なった場合の書き込みや読み込みの負荷，それらを合わせたストレージ負
荷について調査を行なう．まず図 6.27 には補正を行なった場合の複製配置確率と書き込み
負荷の偏りの関係について示している．図から，拡張 Path Random Replication の場合に
52
$%'&()+*-,.
/1032,546))'7 8 9;:=<?>A@
2-,BC4EDF8 BG9;:=<?>A@
!#"
図 6.28: 補正を行なった場合の読み込み負荷．
は，平均的な複製配置の割合によらずほぼ同程度の負荷分散となる．これは，検索ホップ数
も複製配置確率によらずほぼ一定となるためである．
同様に図 6.28 には補正を行なった場合の読み込み負荷について示す．読み込み負荷の偏
りは Path Random Replication と同様に複製配置の割合を高く設定するにつれて減少する
傾向にある．しかし ，負荷の偏りの変動幅は Path Random Replication と比較して小さく
なっている．
図 6.29 には補正を行なった場合の複製配置確率とストレージ負荷の関係を示している．
この図から，拡張 Path Random Replication で補正を行なうことによって，Path Random
Replication を行なう場合よりも負荷分散が可能であることがわかる．また，複製配置の割
合を高く設定した方が負荷分散が可能であるが，割合が低い場合でもほぼ同程度の値を示す．
そのため，補正を行なう拡張 Path Random Replication では，複製配置の割合に関係なく，
ストレージ負荷をネットワーク全体に分散可能であることがわかる．また，これらの図にお
いて指数分布とべき分布のそれぞれの確率関数を用いた場合に有意な差が表れなかった．
53
!"$#&%'
(*),+%.-/"" 0 1 2436587:9
+&%;<->=?1 ;@2436587:9
図 6.29: 補正を行なった場合のストレージ負荷．
これらの結果から，拡張 Path Random Replication を適用する際に各ピアの持つ情報の
みではなく，データの持つ情報を考慮することで，新たにネットワークにデータが追加され
る場合でも提案手法を用いて，検索性能を維持しつつストレージ負荷が分散可能であり，ま
た補正を行なう際には複製配置の割合の影響や，本研究で使用した各確率関数の特性の違い
による影響を受けにくいことが明らかになった．
54
7
まとめ
P2P 技術を用いて分散ストレージを構築する際には，ストレージに発生する読み込みや
書き込みに起因する負荷が degree の高いピアに発生しやすい傾向にある．そこで本研究で
は，目的とするデータの検索性能を損なうことなく，ストレージに発生する負荷をネット
ワーク全体に分散することが可能となる複製配置手法として，静的に複製配置確率を設定
する Path Random Replicaiton と，ピアの状態によって動的に複製配置確率を与える拡張
Path Random Replication を提案した．
複製を各ピアに配置する確率を静的に設定する手法である Path Random Replication を
用いる事によって以下のような特性が明らかになった．
• 読み込み負荷
– 複製配置確率を高く設定することで複製がネットワーク全体に分散されるために
読み込み負荷を分散可能となる．
• 書き込み負荷
– 複製配置確率を低く設定することにより，書き込み回数を削減可能でありネット
ワーク全体に負荷分散が可能となる．
• ストレージに発生する負荷
– 読み込み負荷と書き込み負荷の影響から，複製配置確率を 9%から 14%と設定す
る事でネットワーク負荷を最も効果的に分散可能になる．
また，ストレージの使用割合によって動的に複製配置手法を変化させる拡張 Path Random
Replication では以下の特性が明らかになった．
• 基本特性
– 複製配置確率を動的に決定することでストレージ負荷，その中でも特に書き込み
負荷を最大で約 20 分の 1 に削減可能となったが，新たな種類のデータの追加が
発生した場合，そのデータをネットワーク上に分散配置できない．
55
データを新たに追加する場合，拡張 Path Random Replication で使用する確率関数をス
トレージ負荷だけでなくデータの配置時刻も考慮するように改良を行ない，以下の特性が明
らかになった．
• データを新たに追加した場合の特性
– データの配置時刻を考慮することで，複製配置の割合によらずに検索性能を維持
しつつ負荷分散が可能になる．
以上のことから，提案手法の一つである拡張 Path Random Replication において，各ピ
アの状態だけでなくデータの状態を考慮する事で検索性能を Path Replication と同程度に
維持しつつ，ストレージ負荷を Path Random Replication において最も良好な場合と同程
度に分散が可能であることが明らかになった．
56
謝辞
本研究を進めるにあたり，大変多くの方から御指導，御鞭撻を頂きました．最後にこれら
の方々に感謝の意を表します．
まず最初に，本研究に限らず様々な面において御指導頂きました尾家 祐二教授に深く感
謝致します．
また，終始適切な助言を下さった池永 全志助手に心から感謝致します．
また，本研究を進めるにあたり，最初から最後まで数多くの助言を頂きました山本 寛氏
に厚くお礼申し上げます．
日頃よりお世話になりました尾家研究室，川原研究室，鶴研究室の皆様に感謝申し 上げ
ます．
さらに，研究室内の煩雑な事務処理をいつも快く引き受けてくださった竹村 眞奈美事務
補佐員，坂口 智絵事務補佐員に心から感謝申し上げます．
最後に，私をここまで育ててくれた両親に感謝致します．
57
参考文献
[1] L A. Adamic, R M. Lukose, A R. Puniyami, and B A. Huberman “Search in power-law
networks, ” Physical Review E, Vol. 64 46135-46143, 2001
[2] Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker “Search and Replication in Unstructured Peer-to-Peer Networks, ” Proc. ACM ICS, 2002
[3] 後藤 嘉宏, 阿多 信吾, 村田 正幸 “P2P ネットワークにおけるサービス安定性向上のた
めのレプリケーション配置手法, ” 電子情報通信学会技術研究報告 (NS2002-152), vol.
102, pp. 25-28, October, 2002
[4] Napster, http://www.napster.com/
[5] Gnutella, http://www.gnutella.com/
[6] Freenet, http://freenetproject.org/
[7] A. L. Barabási, R. Albert, H. Jeong, and G. Bianconi ”Power-law distribution of the
World Wide Web, ” Science, 287, 2115a, 2000
[8] M. Faloutsos, P. Faloutsos, and C. Faloutsos “On Power-Law Relationships of the
Internet Topology, ” ACM SIGCOMM, pp. 251-262, 1999
[9] P. Keyani, B. Larson, and M. Senthil “Peer Pressure: Distributed Recovery from
Attacks in Peer-to-Peer Systems, ” In IFIP Workshop on Peer-to-Peer Computing,
in conjunction with Networking 2002.
[10] K. Aberer “P-Grid: A Self-Organizing Access Structure for P2P Information Systems,
” Sixth International Conference on Cooperative Information Systems (CoopIS 2001),
Trento, Italy
[11] K. Aberer, M. Hauswirth, M. Punceva, and R. Schmidt “Improving Data Access in
P2P Systems, ” IEEE Internet Computing, 6(1), January/February 2002
58
[12] I. Foster and C. Kesselman: The GRID Blueprint for a New Computing Infrastructure, Morgan Kaufmann Publishers, 1998
[13] R. Schmidt “Gridella: an open and efficient Gnutella-compatible Peer-to-Peer System based on the P-Grid approach, ” EPFL Technical Report IC/2002/71, Master’s
Thesis at the Technical University of Vienna
[14] G. Fox, D. Gannon, S. Ko, S. Lee, S. Pallickara, M. Pierce, X. Qiu, X. Rao, A. Uyar,
M. Wang, and W. Wu: “Peer-to-Peer Grids, ” chapter in Grid Computing: Making
the Global Infrastructure a Reality John Wiley & Sons, 2003
[15] K. Ranganathan, A. Iamnitchi, and I. Foster “Improving Data Availability through
Dynamic Model-Driven Replication in Large Peer-to-Peer Communities, ” Global and
Peer-to-Peer Computing in Large-Scale Distributed Systems, 2002
[16] Network Weather Service, http://nws.cs.ucsb.edu/
[17] G. On and J. Schmitt, and R. Steinmetz “The Effectiveness of Realistic Replication
Strategies on Quality of Availability for Peer-to-Peer Systems, ” Proceedings Third
International Conference on Peer-to-Peer Computing, pp. 57-64, 2003
[18] T. Bu and D. Towsley “On Distinguishing between Internet Power Law Topology
Generators, ” Proceedings of INFOCOM, 2002
[19] A. L. Barabási and R. Albert “ Emergence of scaling in random networks, ” Science
286, pp. 509-512 1999
59