P2P ネットワークにおけるファイル消失を防ぐ複製配置手法 Replication

DEIM Forum 2009 C9-3
P2P ネットワークにおけるファイル消失を防ぐ複製配置手法
影山 潤†
渋沢 進‡
†茨城大学大学院理工学研究科 〒316-8511 茨城県日立市中成沢町 4-12-1
‡茨城大学工学部 〒316-8511 茨城県日立市中成沢町 4-12-1
E-mail: †[email protected], ‡[email protected]
あらまし 近年，ネットワークモデルとして P2P サービスが注目されている．P2P サービスのネットワークには
様々な需要を持つファイルが存在する．特に，需要が低いファイルは所有するノードが少ないため，ユーザによ
る削除等の理由で，P2P ネットワークから消失してしまう可能性が高い．ファイルの消失は P2P サービスからの
ユーザ離れを引き起こす原因となり，サービスの品質の低下に繋がる．P2P サービスの質を保つ解決法として複
製配置法があるが，ファイルの消失には対応していない．そこで本研究では，低需要ファイルの消失を防ぐ複製
配置手法を提案する．ファイルの需要予測値に基づいてファイルの複製配置数を決定し，P2P サービスを頻繁か
つ継続的に利用するノードに複製を配置することで低需要ファイルの消失を防ぐ．シミュレーション実験により，
ファイル数の推移とストレージ使用量について提案手法と基本的な複製配置手法との比較を行った．実験結果か
ら，時間が経過した後も本提案手法のみ低需要ファイルが存続し，提案手法を用いることで消費されるノードの
ストレージリソースは有効なものであることを確認した．これにより，ファイル消失を防止していることを確認
し，また，有効性を示した.
キーワード P2P，複製配置，需要予測，ストレージ
Replication that Prevents Low-Demand Files
from Disappearing in P2P Network
Jun KAGEYAMA†
Susumu SHIBUSAWA‡
†Graduate School of Science and Engineering, Ibaraki University 4-12-1 Nakanarusawa, Hitachi, Ibaraki, 316-8511
Japan
‡Faculty of Engineering, Ibaraki University 4-12-1 Nakanaruwana, Hitachi, Ibaraki, 316-8511 Japan
Abstract Recently, peer-to-peer (P2P) service is attracting increasing attention as a network model. There are enormous
demands for P2P service files. It is feared that the low-demand files disappear from the P2P network in various reasons, such
as the deletion by owners. The disappearance of files causes the users’ departing from the P2P service, and leads to
decreasing the quality of service. Although many replication methods are used to keep the quality of P2P service, it does not
solve the disappearance of files. In this study, we propose a replication method that prevents low-demand files from
disappearing in P2P network. In this method, the number of replica files is computed based on the forecast demand of files,
and the replicas are arranged in nodes that use the P2P service frequently and continuously. In simulation experiments, we
compared the proposed method with several basic replications on change of the number of files and the necessary storage
amount. The results show that low-demand files continue to exist and the prevention of the file disappearance is achieved
and that the necessary storage amount of proposed method is effective.
Keyword P2P，Replication，Demand Forecasting，File Storage
1. は じ め に
等 の 理 由 で ， P2P ネ ッ ト ワ ー ク か ら 消 失 し て し ま う 可
インターネットにおけるネットワークモデルとし
能性が高い．ファイルの消失はユーザの不満を招き，
て ， P2P サ ー ビ ス が 注 目 さ れ て い る ． P2P サ ー ビ ス で
P2P サ ー ビ ス か ら の ユ ー ザ 離 れ を 引 き 起 こ す 原 因 と な
はファイルに対する需要が一様ではなく，需要が高い
り，サービスの品質の低下に繋がる．
フ ァ イ ル は 多 く の ノ ー ド 間 で や り 取 り さ れ ， P2P ネ ッ
P2P ネ ッ ト ワ ー ク の 品 質 を 保 つ 解 決 法 と し て ， フ ァ
トワークに広く行き渡る．一方で，需要が低いファイ
イルの複製を別のノードに作成する複製配置法と呼ば
ルは所有するノードが少ないため，ユーザによる削除
れる方法がある．しかし，多くの複製配置手法は需要
が高いファイルを効率よく配信するということに注目
2.3 Random Replication
し て お り ，フ ァ イ ル の 消 失 に は 対 応 し て い な い [1], [2],
Random Replication[1]は 検 索 パ ス 上 の ノ ー ド 数 と 同
[3], [4]． 複 製 配 置 に よ っ て フ ァ イ ル の 消 失 を 防 ぐ た め
数 の 複 製 を ， P2P ネ ッ ト ワ ー ク 上 か ら ラ ン ダ ム に 選 出
には，予めネットワーク内のファイルの数を多く確保
したノードに対して配置する方式である．配置ノード
しておき，ファイルを所有するノードがネットワーク
をランダムに選出するためのアルゴリズムの詳細が定
から離脱，あるいはユーザによってファイルが削除さ
められておらず，余分なコストをかけずにノードの選
れたとしても，ネットワーク中のファイル数が零にな
出 が で き る か は 定 か で は な い ． Random Replication に
らないよう対策する必要がある．
よ る 複 製 配 置 の 例 を 図 1(d)に 示 す ．
そ こ で 本 研 究 で は ，需 要 予 測 を 用 い て P2P ネ ッ ト ワ
ークにおける低需要ファイルの消失を防ぐ複製配置手
法を提案する．本手法では，ファイルの需要予測を行
い，その予測値に合わせてファイルの複製配置数を決
定 す る ． ま た ， P2P サ ー ビ ス を 頻 繁 か つ 継 続 的 に 利 用
するノードに複製を配置することで低需要ファイルの
消失を防ぐ．提案手法実現のために，シミュレーショ
ンシステムの実装を行った．シミュレーションの内部
ネ ッ ト ワ ー ク と し て ス ー パ ー ノ ー ド 型 P2P モ デ ル を 採
用している．
提案手法評価のために，シミュレーション実験を行
図 1 検索要求と複製配置の例
い ，基 本 的 な 複 製 配 置 手 法 と の 比 較 を 行 っ た ．約 1500
時間相当の比較実験では，提案手法を用いるとファイ
ルが存続し，他複製配置手法ではファイルが消失する
という結果が確認できた．また，提案手法を用いるこ
とで消費されるノードのストレージリソースが有効な
ものであることを確認した．これにより低需要ファイ
ルの消失を防止し，また，その有効性を確認した．
本 稿 で は 2.で 基 本 的 な 複 製 配 置 手 法 ，3.で 提 案 手 法 ，
3. 提 案 手 法
低需要ファイルの消失を防ぐために，以下の 2 つの
方法で複製配置を行う．
需要予測に基づく複製配置
複製配置先ノードの選出
まず，各ファイルについて需要予測を行い，低需要
ファイルを判定する．その後，その低需要ファイルに
4.で シ ミ ュ レ ー シ ョ ン シ ス テ ム の 実 装 ， 5.に シ ミ ュ レ
ついて複製配置処理を行う．複製配置処理の際には後
ー シ ョ ン 実 験 ， そ し て 6.で ま と め を 述 べ る ．
述の基準に従って複製配置先を選出する．
2. 基 本 的 な 複 製 配 置 手 法
2.1 Owner Replication
Owner Replication[1]は Gnutella[9]な ど に 用 い ら れ る
手法であり，検索がヒットしたときに，検索要求者に
3.1 需 要 予 測 に基 づく複 製 配 置
3.1.1 複 製 配 置 方 式
複製配置方式はダウンロード要求の有無とファイ
ルへの需要により２つの方式を使い分ける．
ダウンロード要求がある場合
だけ複製を配置する方式である．検索１回あたりに配
Owner Replication と 同 様 の 複 製 配 置 を 行 う ．
置される複製が高々１個であるため，単純で，かつネ
Owner Replication は ダ ウ ン ロ ー ド 要 求 1 回 に つ
ットワーク負荷などのコストが最小ではあるが，複製
き複製が 1 個作成される複製配置手法である．
がネットワーク内に広まるのに十分な時間を要する．
そのため，あまり数量を確保しなくともよい低
検 索 要 求 と Owner Replication に よ る 複 製 配 置 の 例 を そ
需要ファイルの複製配置に向いている．
れ ぞ れ 図 1(a)， (b)に 示 す ．
ダウンロード要求がない場合
2.2 Path Replication
Path Replication[1]は Freenet[10]な ど に 用 い ら れ る 手
法であり，検索要求者から所有者に至る検索パス上の
各ファイルに対して需要予測を行い，低需要
ファイルかどうかを判定し，ファイルの数が一
定数を下回れば複製配置処理を行う．
全てのノードに複製を配置する方式である．一度に複
Owner Replication で は ， ダ ウ ン ロ ー ド 要 求 が
数の複製が配置されるため，コンテンツは広まりやす
発生しない限り複製配置処理が実行されないた
いが，必要なストレージやネットワーク資源が大きく
め，ユーザによるファイル削除やノードの離脱
な る ． Path Replication に よ る 複 製 配 置 の 例 を 図 1(c)に
による低需要ファイル消失のリスクに対応でき
示す．
な い ．こ の た め ，ダ ウ ン ロ ー ド 要 求 が な く と も ，
事前にファイルの複製を配置する複製配置処理
生存率という２つの基準によって決定する．この２つ
が必要となる．そこでファイルの需要判定を行
の値が大きいノードに低需要ファイルの複製を配置す
い，低需要ファイルについてのみ事前に複製配
ることで，検索によってファイルが見つかる機会が増
置処理を実行する．
え，ファイルの消失防止に繋がる．
3.1.2 需 要 予 測 方 法
3.2.1 貢 献 度
本稿ではダウンロード要求数を需要とし，需要変動
貢献度はファイルのやり取りにどれだけ貢献して
はポアソン過程に従うと仮定する．このとき，ある時
いるのかを示す度合いである．本稿ではファイルの
刻 t に お け る 需 要 d(t)は 次 の よ う に 表 わ さ れ る ． λ は
upload(UL)回 数 及 び download(DL)回 数 ， 平 均 稼 働 時 間
単位時間中の平均ダウンロード要求数を示す．
から貢献度を決定し，以下のように表わす．
t
e
d (t )
貢献度
t!
UL回数
平均稼働時間
UL回数＋DL回数
3.2.2 生 存 率
ここで，低需要ファイルの複製配置処理のために，
生存率はユーザがサービスを利用する頻度を推定
低需要ファイルの判定を行う．あるファイルがポアソ
するものである．生存率が高ければサービスを利用す
ン 過 程 に 従 う 需 要 変 動 を す る と き ，需 要 数 が 全 体 の 5%
る頻度が高くなる．本稿では３つの仮定を利用し生存
を下回る場合には低需要ファイルとして扱うこととし，
率を決定する．
その時 刻を ty と する．
[仮 定 1] ユ ー ザ の 生 存 期 間 は 指 数 分 布 に 従 う ．
t
d ( t ) dt
生存期間はユーザがサービスを受ける意思のある
0 . 05
期間を示す．ユーザのサービスからの離脱は過去の生
y
この式より，任意の時刻にあるファイルについて実測
存期間に関わらずランダムに発生するとする．生存期
し た 需 要 が d(t y )を 下 回 れ ば ，そ の フ ァ イ ル を 低 需 要 フ
間 を τ と す る と ，ユ ー ザ の 生 存 期 間 f(τ )の 確 率 分 布 は
ァイルとして扱う．
以下のようになる．
次に単位時間毎にファイルへの需要を計測し，指数
f( )
平滑法に基づく需要予測を行う．予測には過去の需要
e
の実測値と予測値を使用する．ここで時刻 t における
μは指数分布のパラメータであり，ユーザのサービス
需 要 の 実 測 値 と 予 測 値 を そ れ ぞ れ Md t ，Fd t と 表 す ．こ
からの離脱率とする．
の と き ， 需 要 予 測 値 Fd t + 1 は 次 の よ う に 表 わ す こ と が
[仮 定 2] DL 及 び UL は ポ ア ソ ン 過 程 に 従 う ．
できる．
Fd t
DL と UL は 過 去 に い つ 起 き た か に 関 わ ら ず ラ ン ダ ム
Md t
1
1
Fd t
上 式 に お い て ，α は 平 滑 係 数 で あ り ，本 研 究 で は 0.5
に発生すると仮定する．τ期間以上生存したユーザの
T 期 間 の DL と UL の 回 数 x の 確 率 は 以 下 の よ う に 表 わ
される．
と す る ． 本 研 究 で は ， Fd t +1 <d(t y )と な る 場 合 は 低 需 要
ファイルの複製配置処理を行う．
x
P x| ,
T
3.1.3 低 需 要 フ ァ イ ル の 複 製配 置
低需要ファイルの複製配置を行う際には複製の配
T
e
x!
T
νはポアソン過程のパラメータであり，単位時間あた
置個数を決定する必要がある．ファイルの消失防止に
り の DL と UL の 頻 度 を 表 す ．
必要なファイルの個数を安全数とし，これを現在のフ
[仮 定 3] 生 存 期 間 の 分 布 μ と DL と UL 頻 度 の 分 布 ν
ァイル数と需要の予測値及び実測値の比から求める．
はユーザ毎に異なる．
この安全数を上回るように複製を配置することでファ
ここで，ある計測期間において，1 人のユーザが 4
イルの消失を防止する．時刻 t でのファイル数，安全
回 DL ま た は UL を 行 っ た 例 を 図 2 に 示 す ．t は 初 回 か
数 を そ れ ぞ れ Nt ， St と す る と ， 安 全 数 は 以 下 の よ う に
ら 最 後 の DL ま た は UL ま で の 期 間 ，T は 初 回 の DL ま
表わすことができる．
た は UL か ら 計 測 終 了 ま で の 期 間 ， そ し て x は 計 測 期
St
Nt
Fd t 1
Md t
間 中 の DL と UL の 回 数 を 示 す ．
以 上 ３ つ の 仮 定 よ り ，生 存 期 間 τ が T よ り 大 き く な
上 式 に お い て ， β は 安 全 係 数 で あ り ， 1.65 と す る [8 ]．
る確率，すなわち計測終了時点でユーザが生存してい
3.2 複 製 配 置 先の選 出
る こ と を 表 す 生 存 率 は 次 の よ う に 表 わ せ る [6]．
低需要ファイルの複製配置先のノードを貢献度と
1
p( , , , T , t )
1
e
T t
1
図 3 シミュレーション開始までの手順
シミュレータの内部ネットワーク構造として，スー
パ ー ノ ー ド 型 P2P モ デ ル を 採 用 し て い る ．こ の ネ ッ ト
図 2 あ る 計 測 期 間 に お け る t と T の 関 係 (x=4 の と き )
ワークモデルはインデックス型の効率的な検索方式と
ネットワーク内の情報収集能力に優れているという特
3.2.3 複 製 配 置 先 の 決 定
以上の貢献度と生存率が高いノードを低需要ファ
イルの複製配置先とする．貢献度及び生存率が高いノ
徴 を 持 つ [11]，[12]．こ の 特 徴 に よ り ，低 需 要 フ ァ イ ル
の検索と需要予測や貢献度，生存率の導出のための情
報収集を効率的に行うことができる．
ー ド は 継 続 的 か つ 頻 繁 に P2P ネ ッ ト ワ ー ク を 利 用 す る
シミュレーションネットワークはスーパーノード
ノードであるため，このノードに低需要ファイルを配
と一般ノードから構成される．ネットワーク構成を図
置することで，ファイルを長く存続させ，ファイルの
4 に示す．スーパーノードは自身とその配下の一般ノ
検索を行った際に発見できる機会が増え，低需要ファ
ードを 1 グループとし，グループ内のノードの所有フ
イルの消失防止に繋がる．
ァイル情報と需要予測，及び複製配置先選出の際に必
要な情報を収集している．検索方式はグループの代表
4. シ ミ ュ レ ー シ ョ ン シ ステ ム の 実 装
であるスーパーノード内にあるファイルリストを利用
提案手法の評価のために，オーバーレイ構築ツール
するインデックス型である．スーパーノード同士でネ
キ ッ ト Overlay Weaver[13]，[14]を 用 い て ，シ ミ ュ レ ー
ットワークを形成し，それぞれが持つファイルリスト
ションシステムを実装した．システムは以下の３つか
を参照し合うことで，数が少ない低需要ファイルを効
ら構成される．
率よく発見することができる．また，需要予測や複製
シミュレータ
配置先選出の際にもスーパーノード同士のやり取りに
シナリオファイル生成器
よって，効率的な複製配置処理が可能である．スーパ
シナリオファイル
ーノードは一般ノードの中から選出し，スーパーノー
まずシナリオファイル生成器に初期パラメータを
ド 自 身 も フ ァ イ ル の DL と UL が 可 能 で あ る ．
入力して，そのパラメータに沿ったシナリオファイル
を生成する．そのシナリオファイルをシミュレータに
読み込ませることでシミュレーションを開始する．シ
ミュレーション開始までの手順を図 3 に示す．
図 4 ス ー パ ー ノ ー ド 型 P2P モ デ ル の 構 成 図
5. シ ミ ュ レ ー シ ョ ン 実 験
提案手法の動作確認と評価を行うため，シミュレー
ション実験を行った．複製配置処理の動作を確認し，
提案手法と基本的な複製配置手法とを比較することで
評価を行う．
5.1 実 験 環 境
実験に使用したシミュレーション環境を以下に示
す．
ノ ー ド 2000 台
(ス ー パ ー ノ ー ド 20 台 ,一 般 ノ ー ド 1980 台 )
各スーパーノード配下にほぼ均等に一般ノー
ドを配置
フ ァ イ ル 50 種
表 1 UL さ れ た period と 複 製 配 置 処 理 開 始 period
複製配置処理
UL さ れ た
ファイル名
period
開 始 period
file1
0
122
file2
0
104
file3
40
170
file4
65
205
file5
100
174
file6
145
310
file7
190
330
file8
245
335
file9
320
420
file10
350
385
情 報 計 測 間 隔 (period)3 時 間 に 1 回
500period 分 の シ ナ リ オ
ま ず ノ ー ド を 2000 台 用 意 し ， そ の う ち 20 台 を ス ー
5.3 ファイル個 数 推 移の比較
file1， file6， file10 の フ ァ イ ル 個 数 の 推 移 に つ い て ，
パーノードとし，残りを一般ノードとする．次に各ス
他の複製配置手法と比較したものを図 6 に示す．図の
ーパーノードの配下に一般ノードを均等に配置する．
表し方は図 5 と同様である． 3 つの複製配置手法の全
初 期 パ ラ メ ー タ の 異 な る フ ァ イ ル を 50 種 用 意 す る ．ま
てにおいて，ファイルの個数が一時上昇し，その後
た，シミュレーションネットワーク内の情報の取得及
period の 経 過 と と も に 減 少 す る ． ま た ， 提 案 手 法 と
び 情 報 更 新 の 間 隔 (period)を 3 時 間 に 1 回 に 設 定 し た ．
Owner Replication は ，file1，file6，file10 に つ い て ，そ
実 験 に 用 い る 複 製 配 置 手 法 と し て ，提 案 手 法 ，Owner
れ ぞ れ 122period， 310period， 385period ま で ほ ぼ 同 様
Replication， Path Replication を 使 用 す る ． こ れ ら 3 つ
の フ ァ イ ル 個 数 の 推 移 を 示 す ． ま た ， Path Replication
の手法についてファイル数の推移とストレージの使用
の フ ァ イ ル の 最 大 配 置 個 数 は 提 案 手 法 及 び Owner
量を比較する．
Replication の 約 2.5 倍 と な る ． 各 フ ァ イ ル に つ い て
5.2 ファイル個 数 推 移の確認
500period 時 点 の フ ァ イ ル 数 に 注 目 す る と ，提 案 手 法 で
提案手法における複製配置処理の動作確認を行っ
は 2∼ 3 個 の フ ァ イ ル が 存 続 し ，Owner Replication 及 び
た ． 50 種 の フ ァ イ ル の 中 か ら 10 種 選 び ， そ の 推 移 を
Path Replication で は 0 と な っ て い る ． こ れ に よ り ， 提
図 5 に 示 す ．図 の 縦 軸 は フ ァ イ ル の 個 数 ，横 軸 は period
案 手 法 に よ っ て file1， file6， file10 の 消 失 を 防 止 で き
を 示 す ．ま た ，10 種 の フ ァ イ ル が UL さ れ た period を
た こ と が わ か る ．実 験 に 用 い た 50 種 の フ ァ イ ル に つ い
表 1 の第 2 列に示す．
て，同様にファイルの消失の防止を確認した．
全 て の フ ァ イ ル で 個 数 が 一 時 上 昇 し ， そ の 後 period
の経過とともに減少していく．これはファイルへの需
要がポアソン分布に従い変動したこと，及び時間の経
過によりファイルが削除されたことによるものである．
ま た ，各 フ ァ イ ル が そ れ ぞ れ 表 1 の 第 3 列 に 示 す period
付近からファイル数がほぼ一定に保たれており，低需
要と判定されたファイルの複製配置が行われているこ
とが推測される．
個数
45
40
35
30
25
20
15
10
5
0
0
個数
100
90
80
70
60
50
40
30
20
10
0
0
50
100 150 200 250 300 350 400 450 500
period
file1提案手法
file1 Owner
file1 Path
file6提案手法
file6 Owner
file6 Path
file10提案手法
file10 Owner
file10 Path
図 6 ファイル数推移比較
50 100 150 200 250 300 350 400 450 500
period
file1
file2
file3
file4
file5
file6
file7
file8
file9
file10
図 5 提案手法によるファイル数の推移
5.4 ストレージ使 用 量 比 較
あ る period ま で の フ ァ イ ル 数 の 積 算 を ス ト レ ー ジ 使
用量と呼ぶ．ストレージ使用量はネットワーク内の全
ノードのストレージリソースの消費量を表す．提案手
法 ， Owner Replication， Path Replication に よ る period
毎 の file1， file6， file10 の ス ト レ ー ジ 使 用 量 の 合 計 を
認 で き た ．提 案 手 法 と Owner Replication に よ る フ ァ
図 7 に 示 す ． 図 の 縦 軸 は file1， file6， file10 の 合 計 ス
イ ル の 個 数 推 移 に 注 目 す る と ，あ る period 付 近 ま で
ト レ ー ジ 使 用 量 ，横 軸 は period を 示 す ．ま た ，500period
は同様の推移を示し，それ以降差が出ていることが
時 点 で の ３ つ の 複 製 配 置 手 法 に よ る file1，file6，file10
わかる．これは本提案手法の複製配置アルゴリズム
についてのストレージ使用量の合計を表 2 に示す．ス
に起因するもので，提案手法では対象とするファイ
ト レ ー ジ 使 用 量 は Path Replication が 最 大 と な り ，
ル が 低 需 要 フ ァ イ ル と 判 断 さ れ な い 限 り ， Owner
Owner Replication が 最 小 と な る ． Path Replication 及 び
Replication と 同 様 の 複 製 配 置 動 作 を す る た め ， こ の
Owner Replication に よ る ス ト レ ー ジ 使 用 量 は あ る
よ う な 個 数 推 移 を 示 す ． 500period の 実 験 に お い て ，
period を 過 ぎ る と 一 定 の 値 を 保 つ ． 一 方 ， 提 案 手 法 に
提 案 手 法 で は フ ァ イ ル が 存 続 し ， Owner Replication
よ る ス ト レ ー ジ 使 用 量 は 新 し い フ ァ イ ル の UL が な い
及 び Path Replication で は フ ァ イ ル の 個 数 が 0 に な る
限り，線形的に増加し続ける特徴があることが確認で
ということから，低需要ファイルの消失防止が実現
きる．
できたと言える．
(2) ス ト レ ー ジ 使 用 量 に つ い て
表 2 file1， file6， file10 の ス ト レ ー ジ 使 用 量 の 合 計
ス ト レ ー ジ 使 用 量 (個 )
手法
file1
file6
file10
合計
2463
2851
548
5862
提案手法
Owner
1212
1973
253
3438
Path
5831
9341
1105
16277
ス ト レ ー ジ 使 用 量 の 比 較 で は ， Path Replication に
よ る ス ト レ ー ジ 使 用 量 が 最 大 と な り ， Owner
Replication に よ る ス ト レ ー ジ 使 用 量 が 最 小 と な り ，
また，提案手法によるストレージ使用量は線形的に
増 加 し 続 け る と い う 結 果 が 得 ら れ た ． Path
Replication は 一 度 の DL で 複 数 の 複 製 を 配 置 す る た
め，他の 2 手法に比べてストレージ使用量が大きく
使用量
18000
16000
14000
12000
10000
8000
6000
4000
2000
0
な る ． 一 方 ， Owner Replication は DL 要 求 １ 回 あ た
りに配置される複製が１個であるため，ストレージ
使 用 量 が 少 な い ． 提 案 手 法 の 複 製 配 置 方 式 は Owner
Replication 方 式 に 加 え て ， 低 需 要 フ ァ イ ル の 複 製 配
置 方 式 を 使 用 す る た め ， ス ト レ ー ジ 使 用 量 は Owner
Replication よ り も 大 き く な る が ． 低 需 要 フ ァ イ ル の
複製配置処理によって生成される複製は少ないた
め ，Path Replication の よ う に ス ト レ ー ジ を 多 く 消 費
0
50 100 150 200 250 300 350 400 450 500
period
提案手法
Owner
Path
することはない．
提案手法を用いることで低需要ファイルの消失を
防ぐことが可能であるが，ファイルが存続すること
図 7 file1,file6,file10 に よ る 合 計 ス ト レ ー ジ 使 用 量
で，ノードのストレージリソースを消費し続けるこ
とになる．１つのファイルによるストレージ使用量
5.5 考 察
(1) 低 需 要 フ ァ イ ル の 消 失 防 止 に つ い て
に注目すると，そのファイルがアップロードされ，
時間が経過するにつれて，提案手法によるストレー
本提案の複製配置処理によるファイルの個数は，
ジ 使 用 量 が 増 加 し ，Path Replication に よ る ス ト レ ー
全てのファイルにおいて，実験開始から一定時間経
ジ 使 用 量 を 上 回 る こ と に な る ．例 え ば ，500period 時
過後にほぼ一定数に保たれるという推移を示すこ
点 で の file6 の Path Replication に よ る ス ト レ ー ジ 使
と が 確 認 で き た ．こ れ は ，各 フ ァ イ ル が 表 1 の period
用 量 は 9341 と な り ， 提 案 手 法 に よ る ス ト レ ー ジ 使
付近で低需要ファイルと判断され，ダウンロードが
用 量 は 2851 と な る ． 500period 以 降 に ， 提 案 手 法 に
ない場合の低需要ファイルの複製配置処理が行わ
よ っ て file6 が 1period 毎 に 2.5 個 保 持 さ れ 続 け る と
れたことを示している．この処理により，ファイル
し た 場 合 の file6 の ス ト レ ー ジ 使 用 量 の 推 移 予 測 を
を一定数以上確保し続けることで，低需要ファイル
図 8 に示す．図の表し方は図 7 と同様である．
の消失を防止している．
また，ファイルの個数推移の比較から，実験終了
時点での全てのファイルについて，提案手法ではフ
ァ イ ル が 存 続 し ， Owner Replication 及 び Path
Replication で は フ ァ イ ル が 消 失 す る と い う 結 果 が 確
質を保つ１つの方法の複製配置法が存在するが，基本
使用量
14000
12000
10000
8000
6000
4000
2000
0
的な複製配置手法は高需要ファイルの効率的な配信を
目的としており，低需要ファイルのネットワークから
の消失には対応していない．そこで本研究では，低需
要ファイルの消失を防ぐために，需要予測に基づく複
製配置と複製配置先の選出方法を考案した．ファイル
0
500 1000 1500 2000 2500 3000 3500 4000
period
file6提案手法
file6Path
図 8 file6 の ス ト レ ー ジ 使 用 量 の 予 測
の需要を予測し，予めファイルの複製を配置しておく
ことでファイルの消失に対応している．また，低需要
ファイルの複製配置先として，貢献度及び生存率が高
いノードを選ぶことで，ファイルを長く存続させてい
る．提案手法の評価のため，シミュレーションシステ
3096period 時 点 で 提 案 手 法 に よ る ス ト レ ー ジ 使 用
ムの実装を行った．シミュレーションの内部ネットワ
量 が 9341 と な り ， Path Replication に よ る ス ト レ ー
ークには高い情報収集能力と検索効率の良さからスー
ジ使用量を上回ると予測できる．しかし，ネットワ
パ ー ノ ー ド 型 P2P モ デ ル を 採 用 し た ．評 価 実 験 で は 提
ーク中の全てのファイルによる総ストレージ使用
案 手 法 と Owner Replication 及 び Path Replication と の フ
量に注目すると，時間の経過と共に新しいファイル
ァイルの個数推移を比較し，また，複製配置によって
がアップロードされるため，提案手法使用時のスト
消費されるノードのストレージリソース量を調査した．
レ ー ジ 使 用 量 よ り も ，Path Replication 使 用 時 の ス ト
実験終了時点で，提案手法ではファイルが存続し，
レージ使用量が上回る．提案手法によるファイル消
Owner Replication 及 び Path Replication で は フ ァ イ ル の
失防止のためにファイルを確保し続けるストレー
個数が 0 になるということが確認でき，低需要ファイ
ジ コ ス ト よ り も ，Path Replication に よ る 複 製 配 置 に
ルの消失防止が実現できた．また，提案手法を用いる
よるストレージコストの方が大きいと言える．これ
こ と で 生 じ る ス ト レ ー ジ コ ス ト は ， Owner Replication
によりストレージコスト面で本提案手法が有効で
よ り 大 き く ，Path Replication よ り 小 さ い と い う こ と が
あると言える．
確認できた．
(3) ス ト レ ー ジ シ ス テ ム の 応 用 に つ い て
今後の課題として，ストレージ使用量の考慮と需要
本 提 案 手 法 を P2P 分 散 ス ト レ ー ジ シ ス テ ム へ 応 用
変動の仮定の検討が挙げられる．本提案手法では低需
することにより，ノードのストレージ資源を有効に
要ファイルを一定数以上確保し続ける処理を行ってい
利用して，様々な需要のファイルを共有することが
るため，低需要と判断されるファイルが増えればノー
できる．ファイルの消失を防止することが可能であ
ドのストレージ使用量も増加する．そのため，需要が
るため，ファイルの不足によるユーザの不満を解消
全く無いファイルは削除してストレージ使用量を抑え
でき，ストレージサービスからのユーザ離れを防ぐ
る仕組みを考える必要がある．また，本研究では，フ
ことができる．その結果，ネットワークに参加する
ァイルの需要はポアソン分布に従うと仮定したが，需
ノ ー ド の 減 少 を 抑 え ， P2P ネ ッ ト ワ ー ク に 必 要 な ノ
要の変動が正規分布等の他の確率分布に従うと仮定す
ードのリソースを確保し，サービスの品質を維持で
ることもできる．今後，ファイルのダウンロードとい
きると期待できる．一方で，低需要ファイルをネッ
うユーザの行動のモデル化に適当な確率分布の検討を
トワークに保持し続けるという特徴から，長期間ダ
行う．
ウンロード要求がないファイルによってノードの
ストレージリソースが消費され続けるという問題
がある．この問題を解決するためには，長期間需要
が全く無いファイルは削除してノードのストレー
ジ使用量を抑える仕組みが必要となる．
6. ま と め
本研究では，低需要ファイルの消失を防ぎ，ネット
ワークの複製配置手法を提案した．低需要ファイルの
消 失 を 防 ぐ こ と で ， P2P サ ー ビ ス か ら の ユ ー ザ 離 れ を
防 ぎ ， リ ソ ー ス を 確 保 す る こ と で ， P2P サ ー ビ ス の 品
質 を 維 持 ， 向 上 す る こ と が で き る ． P2P サ ー ビ ス の 品
文
献
[1] Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker,
“Search and Replication in Unstrctured Peer-to-Peer
Networks”, Proc. 16th ACM Int’l Conf. on
Supercomputing, 2002.
[2] E. Cohen and S. Shenker, “Replication Strategies in
Unstructured Peer-to-Peer Networks,” Proc. of ACM
SIGCOMM 2002, pp.177–190, Aug. 2002.
[3] 川 崎 陽 平 , 佐 藤 崇 , 吉 田 紀 彦 , "P2P ネ ッ ト ワ ー
クにおけるコンテンツの人気度を反映した複製
配 置 ", イ ン タ ー ネ ッ ト コ ン フ ァ レ ン ス 2005 論 文
集 , pp.106-113, 東 京 , Oct. 2005.
[4] 後 藤 嘉 宏 , 阿 多 信 吾 , 村 田 正 幸“ P2P ネ ッ ト ワ ー ク
におけるサービス安定性向上のためのレプリケ
ーション配置手法” 電子情報通信学会技術研究
報 告 (NS2002-152), vol.102, pp.25-28, Oct. 2002.
[5] 宗 形 聡 ，齋 藤 邦 夫 ，樋 地 正 浩 , ”推 定 マ ー ケ ッ ト
データを使用した消費財系新製品の需要予測手
法 ”, 情 報 処 理 学 会 研 究 報 告 , Vol.2004,
No.116(20041117), pp.1-8, 2004.
[6] 阿 部 誠 ： CRM の デ ー タ 分 析 に 理 論 と モ デ ル を 組
み 込 む 消 費 者 行 動 理 論 に も と づ い た RF 分 析 ，
http://www.e.u-tok yo.ac.jp/cirje/research/03research
02dp_j.html
[7] 尾 崎 俊 治 ， 確 率 モ デ ル 入 門 ， 朝 倉 書 店 ， 1996.
[8] 在 庫 管 理 の 概 要 ,
http://www.kogures.com/hitoshi/webtext/zk-intro/ind
ex.html
[9] Gnutella, http://gnutella.wego.com/
[10] Freenet, http://freenetproject.org/
[11] Skype, http://www.skype.com
[12] KaZaA, http://www.kazaa.com/
[13] 首 藤 一 幸 ，田 中 良 夫 ， 関 口 智 嗣 , “オ ー バ ー レ イ 構
築 ツ ー ル キ ッ ト Overlay Weaver”, 情 報 処 理 学 会 論
文 誌 : コ ン ピ ュ ー テ ィ ン グ シ ス テ ム , Vol.47,
No.SIG12 (ACS 15), pp.358-367, Sept. 2006.
[14] Overlay Weaver,
http://overla yweaver.sourceforge.net/index-j.html