論文
DBSJ Letters Vol.4, No.4――――――――――――――――――――――――――――――――――――

P2Pネットワーク上のデータアクセス頻度を考慮した確率的な複製配置方式
A Probabilistic Replication Strategy Basedon Data Access Frequencies in P2P
Networks

木戸 裕樹♥
Yuki KIDO

原 隆浩♠

西尾 章治郎♠Takahiro HARA Shojiro NISHIO

近年，計算機の高性能化とネットワークのブロードバンド化に伴い，Peer-to-Peer(P2P)ネットワークを用いたデータ共有に関する研究が注目されている．本論文では，ピュアP2P型ネットワークを用いたデータ共有サービスにおいて，各ピアの検索効率の向上を目的とした複製配置方式を提案する．
提案方式では，検索クエリが要求データを保持するピアを発見した経路上のピアにおいて，各データに対するアクセス頻度の順位に応じて，複製を作成するか否かを決定する．さらに本論文では，シミュレーション実験により，提案方式の有効性を検証する．
Recently, there has been increasing interest in researchof data sharing with peer-to-peer networks. In this paper,
assuming a data sharing service, we propose a new
replication strategy that achieves improvement of search
performance. The proposed strategy creates replicas ateach peer on the path along which a query is successfullyforwarded, depending on the peer's rank of accessfrequency to the data. Moreover, we verify theeffectiveness of the proposed strategy by simulation
experiments.

1. はじめに
近年，計算機の高性能化とネットワークのブロードバンド化に伴い，Peer-to-Peer(P2P)モデルを用いたネットワークサービスに注目が集まっている．P2Pモデルでは，サーバやクライアントといった明確な区別はなく，端末（ピア）同士が対等な接続形態を取り，互いにサービスを提供しあう．このようなP2Pモデルは，サービス提供における負荷が分散されるため，スケーラビリティや耐障害性の面で優れているという特徴をもつ．P2Pモデルを用いたネットワークサービスの形態は，サービス提供者の検索機構によって，クライアント・サーバシステムを融合させたハイブリッドP2P型と，完全な分散環境であるピュアP2P型に分類される．
ピュアP2P型のネットワークサービスでは，物理ネットワークとは独立した論理的な検索ネットワークを構成し，各ピ♥学生会員 大阪大学大学院情報科学研究科博士前期課程
kido.yuki@ist.osaka-u.ac.jp♠
正会員 大阪大学大学院情報科学研究科{hara, nishio}@ist.osaka-u.ac.jp

1

アは自律分散的にサービス要求（クエリ）を伝搬し，サービス検索を行う．また，システム全体が完全な分散システムとなるため，クライアント数に対するスケーラビリティ，高い耐障害性を実現することができる．
本研究では，P2Pネットワークのサービス利用者が急速に増加していることを考慮して，数千もしくは数万規模のユーザが参加するような大規模なデータ共有サービスを想定する．そのため，クライアント数に対するスケーラビリティの高いピュアP2P型のデータ共有を想定する．
ピュアP2P型ネットワークを用いたデータ共有では，各ピアがデータ検索におけるクエリの転送や，データ提供の役割を担う．したがって，検索における負荷分散，検索効率およびデータの可用性向上のために，ネットワーク上の複数のピアにデータの複製を配置することが一般的である．Cohenら
はピュアP2P型ネットワークにおいて，各データに対するアクセス頻度が与えられた場合の，ネットワーク全体に配置すべき各データの複製数について議論している[1]．その中で，ピアが保持すべき各データの複製数の比を，ピアの各データに対するアクセス頻度の平方根の比と等しくすることで，ネットワークトラフィックや各ピアの負荷分散，検索効率において最も良い性能が得られることを証明している．またCohenらが証明した理想的な数の複製を配置するための複製配置方式に関する研究も行われている[2]．文献[2]では，クエリがヒットした際に，クエリを発行したピアから要求データを持つピアまでにクエリが経由した全てのピアに複製を配置する“パス複製法”を用いることで，理想数に近い数の複製を配置できることを確認している．しかし，3章で示す
ように，パス複製法によって作成される複製数は理想値に十分近いとは言えず，改善の余地がある．
そこで，本論文では，P2Pネットワークにおける検索効率の向上を目的とした複製配置方式を提案する．提案方式では，複製の配置対象となる各ピアにおいて，データに対するアクセス頻度の順位を考慮して，複製を作成するか否かを決定することで，パス複製法よりもさらに理想値に近い数の複製をネットワーク上に配置する．

2. 関連研究
ピュアP2Pネットワークにおけるネットワークトポロジは，構造(Structured)型と非構造(Unstructured)型の2種類に分類される．本章では，非構造型トポロジを用いたP2Pシステ
ムにおける検索方式，複製の配置方式について説明する．
非構造型トポロジを用いたP2Pシステムは，ネットワークのトポロジ及びデータの配置に明確な方針が規定されていない．そのため，データ検索の際には，フラッディングなどの無作為な方法が用いられる．このような無作為な検索は，トラフィックや検索にかかる遅延が大きい．しかし，任意の論理ネットワークを構築できるため，システムを運用しやすいといった利点がある．
Cohenらは，文献[1]において，非構造型トポロジを用いたP2Pネットワークを想定し，ネットワーク全体に配置すべき各データの複製数について議論している．非構造型トポロジを用いたP2Pネットワークの場合，フラッディングなどの無作為な検索を行う必要があるため，クエリはヒットするか，もしくはホップ数が定められたTTLを超えない限り，隣接ピアに転送され続ける．したがって，複製数が少ないデータに対して要求が頻繁に行われる場合，クエリがヒットする確率が少なくなるため，トラフィックは増加してしまう．そこで，

日本データベース学会 Letters Vol.4, No.4

論文
DBSJ Letters Vol.4, No.4――――――――――――――――――――――――――――――――――――
一度の検索でクエリが伝播する範囲を平均探索サイズ（ESS）と定義し，ネットワーク全体における各データの複製数の比を，データに対するアクセス確率の平方根の比と等しくする平方根配置モデルにより，ESSが最も小さくなることを証明している．つまり，複製数の比を平方根配置モデルに近づけることで，ネットワークやピアの負荷を軽減することができ，検索効率も向上できる．
Lvらは文献[2]において，オーナー複製法，パス複製法，ランダム複製法に関する考察を行っている．これらの複製配置方式は，検索クエリがヒットした場合に複製を作成する．
各ピアにおいて，複製を作成できる上限数を超えてしまった場合は，保持する複製の中からFIFO(First In First Out)もしくはランダムに一つを選択して削除する．
・オーナー複製法：Gnutellaで用いられる方式であり，クエリの発行元ピアがデータを受信した際に，その複製を配置する．
・パス複製法：Freenetで用いられる方式であり，クエリの発行元ピアから，要求データを保持するピアまでに，クエリが経由したパス上にある全てのピアにその複製を配置する．
・ランダム複製法：クエリが，要求データを保持するピアを発見するまでに経由したパス上にあるピア数と同じ数の複製を，検索によりクエリが伝搬した全てのピアの中から，ランダムに選んで配置する．ネットワーク上に配置される複製の数はパス複製法と同じになる．
文献[2]では，パス複製法を用いることにより，各データの複製数の比を平方根配置モデルに近づけることができることを示している．しかし，パス複製法によって作成される複製数は，平方根配置モデルに基づいた複製数に十分近いとは言い難い．詳しくは，後述の3.2節で議論する．

3. 準備実験
本章では，各データの複製数を平方根配置モデルに近づけることによる，検索性能への影響を調査するために行った準備実験とその結果を示す．

3.1

シミュレーション環境

P2Pネットワークに参加するピア数は3,000とし，ネットワークトポロジは，べき法則に従って各ピアの隣接ピア数を決定し，ピア同士をランダムに接続したPLRG(Power-Law RandomGraph)とした．検索対象となる総データ数は500とし，全ピアの中から各データのオリジナルデータを所持するピアを1つ選択した．本シミュレーション環境では，オリジナルデータの更新は発生しないものとし，複製は常にオリジナルデータと同じ内容であるとした．さらに，各データのサイズは全て等しく，各ピアがオリジナルデータおよび複製を保持可能な数を5とした．初期状態では，複製領域にアクセス頻度の平方根に比例した割合の複製を配置した．また，オリジナルデータは削除されないものとした．ピアの参加・退出は考慮しない．各ピアが，あるデータに対してクエリを発行する確率は全てのピアで等しいものとし，各タイムスロットで0.1とした．検索クエリの伝搬にはフラッディングを用い，TTLは10とした．
また，各ピアがデータjに対してクエリを発行する確率qjは，以下のようなZipf法則[3]に従うものとする．
j −αqj = k… (1)−α∑ m =1 m2

図1Fig.1

パス複製法における複製の分布

Replica allocation by path replication

ここでkは総データ数を表すものである．また，αはアクセス確率を決定するためのZipf係数と呼ばれるものであり，この値が大きいほど一部のデータが頻繁に要求される．
以上のようなシステム環境において，4,000タイムスロットのシミュレーション実験を行った．

3.2

複製数が検索に与える影響の調査

パス複製法を用いた場合のネットワーク全体の複製数の分布を調べた結果を図1に示す．ここで，Zipf係数αを1.0とした．また，グラフの縦軸が総複製数に対する各データの複製数の割合，横軸がデータの識別子を表す．両者共に対数表示している．さらに，平方根配置モデルに基づく理想値を“square-root”とし，パス複製法にもとづいた結果を“path”と示している．
図1から，パス複製法は平方根配置モデルに対して，50よりも小さい識別子のデータの複製が多く配置されている．特に，識別子が小さくなるにつれてその差は大きくなっている．
反対に，50よりも大きい識別子のデータに関しては，識別子が大きくなるにつれて，平方根配置モデルよりも複製数が少なくなっている．これは，人気のあるデータに対して，クエリが頻繁に発行されるため，パス複製法を用いた場合，それらの複製が非常に多くネットワーク上に配置されるためである．つまり，クエリの発行頻度の低いデータは，その影響を受け，削除される確率が高くなる．
複製数を平方根配置モデルに近づけるためには，アクセス頻度の高いデータの複製を作成することによって，アクセス頻度の低いデータの複製が削除されすぎないようにする必要がある．そこで，検索対象となる各データのアクセス頻度の順位に応じて複製を配置する確率を変化させることが有効と考えた．この考えに基づき，いくつかの試行を行い，最終的にデータjに対する複製配置確率Rjを次の式で与えた．
1

j… (2)
R j = 0.05 + 0.95 × ( ) 2k
式(2)を用いて，ネットワーク全体の複製数の分布を調べた
結果を図2に示す．結果から，式(2)を用いた場合には，より平方根配置モデルに近づいていることが分かる．
次に，平方根配置モデルに近づけたときのデータ検索性能への影響を調べるために，パス複製法および式(2)を用いた複製法における検索成功率を図 3 に示す．グラフの縦軸は，各データに対するクエリがヒットした割合（検索成功率）を

日本データベース学会 Letters Vol.4, No.4

論文
DBSJ Letters Vol.4, No.4――――――――――――――――――――――――――――――――――――

式(2)を用いた場合の複製の分布

図3

各データの検索成功率

Replica distribution when using formula(2)Fig.3

Query success ratio

図2
Fig.2

4.2

性能評価表し，横軸はデータの識別子を表す．この結果より，アクセス頻度が高いデータの検索成功率は両者に大きな差は見られないが，パス複製法を用いた場合，アクセス頻度が低いデータに検索成功率の低いものが目立つ．一方，式(2)を用いた複製法では，全てのデータに対して高い検索成功率を示している．このように，式(2)を用いた複製法は，パス複製法と比べて，アクセス頻度が高いデータの複製配置確率を低くすることで，アクセス頻度の低いデータの検索成功率を向上させている．また，全体としての検索成功率も向上する．

本論文では，提案方式において，各データの複製数の比が平方根配置モデルにどれだけ近いかを表す指標として，次式で表される評価値Vを用いる．
1 k | rj − s j |V = ∑… (4)k j =1 s j

以上の結果から，ネットワーク全体における複製数の比を平方根配置モデルに近づけたとき，アクセス頻度の順位が下位のものに対する検索成功率が向上することが分かる．

アクセス確率の分布を決定するパラメータ α を変化させたときに，評価値Vが最も小さくなるaとcの値をシミュレーション実験によって調べた．ここで，αを0.0から1.2 (0.1刻み)，aを0.00から1.00 (0.05刻み)，cを0.00から1.00 (0.05刻み)に変化させた．
実験結果を表1に示す．この結果から，アクセス頻度の分布を決定するαと，aおよびcには相関性があることが分かる．
αが小さい場合，aは比較的大きい値の方が平方根配置モデルに近くなり，逆にαが大きくなるにつれてaは小さい値の方が近くなる．またcについては，αが小さいときは小さく，αが大きくなるにつれてcも大きくすることで平方根配置モデルに近くなることが分かる．

4. アクセス頻度を考慮した複製配置方式
本章では，複製数の比を平方根配置モデルに近づけることを目的とし，検索対象データのアクセス頻度の順位を考慮した複製配置方式を提案する．

4.1

提案方式

提案方式では，パス複製法と同様に，検索クエリがヒットした場合に複製を作成する．複製配置の対象となるピアは，クエリの発行元ピアから，要求データを保持するピアまでクエリが経由した全てのピアとなる．配置対象の各ピアでは，データに対するアクセス頻度の順位に基づいた確率を用いて，複製を作成するか否かを決定する．アクセス頻度の順位がjであるデータの複製配置確率Rjは，3章の準備実験の結果を参考にして，次式で与える．
j
R j = a + (1.00 − a ) × ( )c… (3)k
ここで a と c は，アクセス頻度が高いデータと低いデータの複製配置確率の差を決定するパラメータであり，0 から 1 の間の値をとるものとする．a や c の最適な値は，システム環境に依存して変化するものと考えられる．複製を作成することが決定したピアでは，自身のキャッシュ領域にデータの複製を作成し，次のピアに転送する．複製を作成しないピアでは，次のピアにデータを転送するのみである．この動作をクエリ発行元のピアまで繰り返す．

3

ここで，データjの複製数の比をrj，平方根配置モデルにおける複製数の比をsjとしている．評価値Vが小さいほど，複製数の比が平方根配置モデルに近いことを示す．

4.2.1

アクセス分布と複製配置確率の関係

表1

各αにおける最適な a，c と評価値 V

Table 1

Optimal a and c varyingα

αacV

0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.91.0
1.1
1.2

0.85
0.55
0.40
0.05
0.00
0.05
0.00
0.05
0.05
0.00
0.05
0.00
0.00

0.05
0.15
0.20
0.15
0.20
0.25
0.30
0.35
0.45
0.45
0.55
0.55
0.60

0.046
0.048
0.049
0.049
0.052
0.057
0.057
0.063
0.069
0.075
0.091
0.102
0.120

日本データベース学会 Letters Vol.4, No.4

論文
DBSJ Letters Vol.4, No.4――――――――――――――――――――――――――――――――――――

図4
Fig.4

αと評価値 V（パス複製法）

ここで，参考のために，パス複製法を用いた場合の，評価値Vに対するαの影響を図4に示す．この結果より，αが小さいときは，平方根配置モデルに近い数の複製を配置しており，αが大きくなるにつれて，平方根配置モデルから遠ざかることが分かる．提案方式を用いた場合には，αが大きいときは，アクセス頻度の高いデータと低いデータの複製配置確率の差が大きくなるように a と cを調整した方が良い結果を示している．

4.2.2

提案方式の優位性の検証

検索における提案方式の実質的な優位性を検証するために，αを0.0から1.2に変化させたときの検索成功率をシミュレーション実験により調べた．検索クエリのTTLは，αに関わらず6とした．また，提案方式のパラメータであるa，cは，4.2.1節と同様の過程で得られた最適値に設定した．実験結果を図5に示す．パス複製法を用いた場合の結果を“path”，提案方式を用いた場合の結果を“rank”と表している．
図5から，αの値に関わらず，提案方式の方が検索成功率が高いことが分かる．さらに，αが大きくなるにつれて，パス複製法に対する性能の差が大きくなることが確認できる．
パス複製法では，データのアクセス頻度に関係なく，複製の配置が行われるため，データアクセスが一部のデータに集中すると，アクセス頻度の高いデータの複製が多く作成され，アクセス頻度の低いデータの複製が削除されてしまう．それに対し提案方式では，データのアクセス頻度を考慮して複製の配置を行うため，常に平方根配置モデルに近い数の複製が配置できている．このため，αが大きくなり，アクセスが一部のデータに集中するにしたがって，提案方式のパス複製法に対する性能差が大きくなると考えられる．

5. まとめと今後の課題
本論文では，各ピアにおける複製配置確率を，各データに対するアクセス頻度の順位を考慮して決定することにより，パス複製法よりも最適値により近い数の複製を作成する複製配置方式を提案した．また，シミュレーション実験により，提案方式の優位性を検証し，アクセスが一部のデータに集中するにつれて，性能の差が大きくなることを確認した．
今後は，システム環境と複製配置確率の関係をさらに詳細に検討し，適切なパラメータを設定できるように検討する必要がある．また提案方式は，各データに対するアクセス確率の分布を既知のものとしているが，実環境では，これらの情報を取得することは容易ではない．そこで今後は，周辺のピ4

図5

V varying α(path replication)
Fig.5

αと検索成功率(TTL = 10)

Search success ratio and α(TTL = 10)アから送信される検索クエリを監視し，アクセス確率の分布やネットワークトポロジを推測することで，自律的に複製配置確率を決定する方式についても検討する予定である．

[文献］[1]Cohen, E. and Shenker, S.: Replication Strategies in
Unstructured Peer-to-Peer Networks, Proc. ACM
SIGCOMM'02, pp.177-190 (2002).
[2]Lv, Q., Cao, P., Cohen, E., Li, K. and Shenker, S.:
Search and Replication in Unstructured Peer-to-Peer
Network, Proc. Int'l Conf. on Supercomputing, pp.84-95(2002).
[3] Zipf, G. K.: Human Behavior and the Principle of Least
Effort, Addison-Wesley (1949).

木戸 裕樹

Yuki KIDO

2004 年電気通信大学電気通信学部情報工学科卒業．現在，大阪大学大学院情報科学研究科博士前期課程在学中．日本データベース学会学生会員．

原 隆浩

Takahiro HARA

1995 年大阪大学工学部情報システム工学科卒業．1997 年同大学院工学研究科博士前期課程修了．同年，同大学院工学研
究科情報システム工学専攻助手，2002 年より同大学院情報科学研究科マルチメディア工学専攻助手，2004 年より同大学院情報科学研究科マルチメディア工学専攻助教授となり，現在に至る．工学博士．ACM，IEEE，電子情報通信学会，日本データベース学会の各会員．

西尾 章治郎Shojiro NISHIO

1975 年京都大学工学部数理工学科卒業．1980 年同大学院工学研究科博士後期課程修了．工学博士．京都大学工学部助手，
大阪大学基礎工学部および情報処理教育センター助教授，同大学大学院工学研究科情報システム工学専攻教授を経て，2002 年より同大学院情報科学研究科マルチメディア工学専
攻教授となり，現在に至る．2000 年より大阪大学サイバーメディアセンター長，2003 年より大阪大学大学院情報科学研究科長を併任．この間，カナダ・ウォータールー大学，ビクトリア大学客員．データベース，マルチメディアシステムの研究に従事．現在，Data & Knowledge Engineering, Data
Mining and Knowledge Discovery などの論文誌編集委員．
情報処理学会フェローを含め，ACM，IEEE など 9 学会の会員．

日本データベース学会 Letters Vol.4, No.4