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

応答転送状況に基づく P2P ネッ
トワークトポロジ変更手法の改善
Improvement of Topology Alteration
Algorithm for P2P Networks Based on
Response Statistics

片山 肇♥
春本 要♠

中野 宏一
西尾 章治郎♦△Hajime KATAYAMA Hirokazu NAKANO
Kaname HARUMOTO Shojiro NISHIO

近年，P2P ネットワークを利用したアプリケーションが普及している．Gnutella に代表されるフラッディングベースの P2P ネットワークはトラフィックの増大が大きな問題である．また，ピアがもつ情報を考慮せずに論理ネットワークを形成するため，検索精度が低下する．
そこで本論文では，P2P 論理ネットワークのリンク入れ換えアルゴリズムを提案する．提案するアルゴリズムは，ピアの要求する情報を保持するピアが近くに配置されるよう，リンクを接続し，不必要なピアとのリンクを切断してリンクの入れ換えを行う．これによりフラッディングする範囲を抑え，検索精度の高い検索を実現できるだけでなく，ネットワークトポロジが変化してもピアの保持するリンク数は変化しないため，トラフィックの増大を抑制できる．また本論文ではシミュレーション実験によって，提案アルゴリズムを適用することで検索精度が向上することを示すとともに，解決すべき課題について述べる．
Recently, Peer-to-Peer (P2P) applications are becoming
popular. The flooding-based P2P networks such as
Gnutella have a problem that they generate a large
amount of network traffic. Moreover, their recall ratio isgenerally not good because they are constructed
regardless of which peer has which information. In thispaper, we describe an improvement of the network
topology alteration algorithm for flooding-based P2P
networks. The proposed algorithm alters the topology of aP2P network so that a peer can be allocated near thepeers that have information the peer often requests. The
proposed algorithm solves the network traffic problem bykeeping the number of links that each peer has asconstant as possible. By simulation experiments, we showthat the proposed algorithm improves the recall ratio♥学生会員 大阪大学大学院情報科学研究科博士前期課程
katayama.hajime@ist.osaka-u.ac.jp△学生会員 大阪大学大学院情報科学研究科博士前期課程
nakano.hirokazu@ist.osaka-u.ac.jp♠正会員 大阪大学大学院工学研究科
harumoto@eng.osaka-u.ac.jp♦
正会員 大阪大学大学院情報科学研究科
nishio@ist.osaka-u.ac.jp

1

while keeping the network traffic low. Finally, we discuss
the remaining issues to be solved.

1. はじめに
近年，Gnutella，NapsterをはじめとするP2Pネットワークを利用したアプリケーションが数多く普及している．
P2Pネットワークにおける代表的な検索手法として，クエリのフラッディングがある．フラッディングでは，ピアが情報を検索する場合，TTL (Time To Live)を定めたクエリを全ての隣接ピアに転送する．クエリを受け取ったピアがクエリにマッチする情報を保持している場合，その情報をレスポンスとしてクエリを転送してきたピアへ返信する．また，クエリを発行したピアからの論理ネットワーク上のホップ数がTTLの値を超えない限り，そのクエリはさらに隣接ピアへ転送される．しかしフラッディングでは，TTLを大きな値に設定するほどトラフィックが指数関数的に増加し，ネットワーク全体のパフォーマンスが低下するという問題がある．逆に，TTLを小さな値に設定すると，クエリがフラッディングされる範囲外にある情報を取得できない．つまり，TTLの値とレスポンス数の間にトレードオフが存在する．
TTLの値を小さく抑えながら多くのレスポンス得るためには，何らかの基準によってP2Pネットワークのリンク構造を動的に変化させ，クエリが届く範囲内にできるだけ多くの該当情報をもつピアが存在するように構成させるアルゴリズムが必要である．
我々は，レスポンスによるトラフィック量の増減を考慮してリンクを繋ぎ換える手法として，ネットワーク繋ぎ換えアルゴリズムを提案した．これによって情報検索精度は向上した．しかし，ピアの保持するリンク数を考慮していないため，繋ぎ換えられることによって一部のピアが多くのリンクをもち，クエリがこれらのピアを経由することによってトラフィックの増大を招いていた．
そこで本研究では，トラフィックの増大を抑制し，より小さなTTL値の設定でより多くのレスポンスを得ることができるような論理ネットワークのリンク入れ換えアルゴリズムを提案し，シミュレーションによる提案アルゴリズムを評価する．

2. 関連研究
Pure型P2Pネットワークにおける検索手法の代表的なものとして，分散ハッシュテーブル(DHT: Distributed HashTable)による方法とフラッディングによる方法がある．DHTによる方法では非常に少ないメッセージ数で検索を行うことができる．しかし検索時に単一のキー値しか指定できないため，一般的な条件比較などによる情報検索は不可能である．
一方，フラッディングによる検索手法には，検索トラフィッ
クの増大の問題がある．これを解決する手法として，RI(Routing Indices)[1]やSONs(Semantic Overlay Networks)[2]などの手法が提案されている．また我々はレスポンスによるトラフィック量の増減を考慮し，P2Pネットワークのリンク構造を動的に変化させるアルゴリズムとしてネットワーク繋ぎ換えアルゴリズム[3]を提案した．

2.1

RI

RIはクエリをフラッディングするかわりに，隣接するピアのもつ情報を考慮し，応答の期待できるピアへのみクエリを転送する方式である．ピアは隣接するピアのもつ情報を管理する．クエリを受信すると，ピアは管理する情報をもとにし日本データベース学会 Letters Vol.4, No.2

論文
DBSJ Letters Vol.4, No.2――――――――――――――――――――――――――――――――――――て，隣接する各ピアから得られる応答の期待値を算出し，期待値の一番大きいピアへクエリを転送する．これを繰り返すことにより，要求される情報を保持するピアへクエリを転送することができる．この手法では応答の期待できるピアにのみクエリを転送するため，不必要なクエリの発生を抑えることができる．しかしRIにおいて論理ネットワークは静的である．これにより情報を保持するピアが論理ネットワーク上の離れたところに存在する場合，ピアは情報を取得できない可能性がある．

2.2

SONs

SONs ではピアのもつ情報を考慮し，情報のジャンル別にネットワークを形成する．SONs では情報のファイル名とその情報に対応するジャンル名を格納するデータベースが存在する．このデータベースを参照することにより，情報に対応するジャンルを一意に決定できる．ジャンルは root，style，substyle の順に階層化されている．ピアは，自身が持つファイルのジャンルに該当するネットワーク(SON)に参加し，その SON 内に属する他のピアとリンクする．検索の際は，情報の分類と同様にクエリをジャンルに分類し，該当する SON へ転送する．SONs では情報のジャンルごとにネットワークを形成するため，検索精度が非常に高い．ただしこの手法は情報が明確にジャンルに分類できる場合に限る．また，一つの SON内においてクエリはフラッディングされるため，トラフィック増大の問題は部分的にしか解決できていない．

2.3

繋ぎ換えアルゴリズム

ネットワーク繋ぎ換えアルゴリズムでは，ピアがレスポンスの転送履歴を利用することによって，ピアが要求する情報を保持するピアが近くに配置されるようにリンクを繋ぎ換える(図 1)．ネットワーク繋ぎ換えアルゴリズムでは，ピアは自身を経由するレスポンスの転送状況を監視する．そして転送の頻度が閾値に達したレスポンスを発見した場合，そのレスポンスの転送先のピアに，リンクを繋ぎ換えるように促す．繋ぎ換えを促されたピアは，リンクを繋ぎ換えることによって生じる，レスポンスによるトラフィック量の増減をネットワークへの影響として算出する．
P2

P4P1P0

P3

Fig.1

P4P1P5

図1P2P0

入れ換えるリンク
切断するリンク

P3P5

繋ぎ換えアルゴリズム

し，情報検索時にクエリをフラッディングすると，保持するリンク数の多いピアをクエリが経由した際にトラフィックが増大する．提案アルゴリズムではリンクの入れ換えによってピアの保持するリンク数が増減することはない．

3. 提案アルゴリズム
3.1

想定環境

ピアは必ず 1 つ以上のピアとリンクをもつものとし，リンク先のピアを隣接ピアとする．ピアは全体で 1 つの論理ネットワークを形成し，ピアのネットワークへの参加，ネットワークからの脱退，ピアの故障については考慮せず，論理ネットワークが分断することはないものとする．

3.2

転送履歴

ピアは自身と隣接ピアを経由するレスポンスの転送履歴を保持する．保持する転送履歴の情報は，転送元，転送先とする．ここでは簡単のため，ピアへレスポンスを転送してきた隣接ピアを転送元とし，ピアがレスポンスを転送した先の隣接ピアを転送先とする．

3.3

入れ換えアルゴリズム

ピアは転送履歴チェックによって，転送した数の一番多いレスポンスに関して繋ぎ換えのアルゴリズムを実行する．以
下図 2 を例に挙げてアルゴリズムの実行手順を説明する．
(1) P1は，転送頻度の高いP0P2を経由するレスポンスについて，レスポンスの転送先P2とのリンクを切断する．
またリンクP0P2を接続するよう転送頻度の高いレスポンスの転送元であるP0に促す．
(2) P2とのリンク接続を促されたP0は，P2とリンク接続後もリンク数を一定に保つために，P0のもつリンクのうちレスポンスの転送頻度の低いリンクを不必要なリンクとして選択し切断する．その際P0はそれぞれの隣接ピアとのリンクを入れ換えるリンクと仮定し，リンク入れ換え後におけるレスポンスによる予想トラフィッ
クを評価値として算出し，評価値が最小であるリンクを不必要なリンクとして選択する．P0 P3のリンクにおける評価値が最小である場合，P0はこのリンクを不必要なリンクとして選択する．評価値の算出方法は次節で述べる．
(3) P0はP3とのリンクを切断し，P1P3間のリンクを接続するようP1に促す．
(4) P1はP3とリンク接続し，リンク入れ換えアルゴリズムは完了する．
P2

P4

P1

トラフィック量が減少する場合は良い影響を与えると判断し，閾値を超えたレスポンスについてその転送先のピアに繋ぎ換えを促し，繋ぎ換えを促されたピアは同様に評価値を算出する．悪い影響を与えると判断した場合は，繋ぎ換えを促したピアに対して繋ぎ換えを拒否する．最終的に拒否を受けたピアが繋ぎ換え先のピアにリンクを繋ぎ換える．これにより情報を要求するピアとその情報を保持するピアが論理ネットワーク上の近い位置に再配置され，フラッディングする範囲を抑え，検索精度の高い検索を実現できる．
しかしネットワーク繋ぎ換えアルゴリズムでは，ピアはリンクを繋ぎ換える際に自身の保持するリンク数を考慮してない．そのため繋ぎ換えによって一部のピアにリンクが集中

2

P2

P4

Topology alternation algorithm
P0

P3

P1P5

図2
Fig.2

3.4

P0P3

入れ換えるリンク
切断するリンク

P5

入れ換えアルゴリズム

Network-topology replacement algorithm

評価値

リンクの入れ換えが行われると論理ネットワークのトポロジが変化する．ネットワークトポロジの変化によって，ホップ数が短縮される経路においては，小さいホップ数で検索できるが，ホップ数が延長される経路においては．検索時に日本データベース学会 Letters Vol.4, No.2

論文
DBSJ Letters Vol.4, No.2――――――――――――――――――――――――――――――――――――
大きなホップ数が必要となる．そこでリンクを入れ換える相手のピアを決定するために，ピア P とリンクを入れ換えると仮定した場合におけるレスポンスによるトラフィック量をピア P の評価値として算出する．ピアはリンクを入れ換える際にそれぞれの評価値を比較し，リンクを入れ換えるピアを決定する．
評価値は∑Q(Nij×Hij)の式を用いて計算する． Qは経路を表す．i，jは評価値を算出するピアPから 2 ホップ以内に存在するピアを表し，Nijは経路ijを流れたレスポンス数を表す．
Hijは経路ij間のホップ数を表す．そしてNijとHijの積をとることで，レスポンスが経路ij間を流れることによって発生するトラフィック量を得る．最後に全経路での総和をとることでリンク先入れ換え後におけるレスポンスによる予想トラフィック量を得て，この値を評価値とする．評価値が小さい値であることは，レスポンスによるトラフィックが小さいことを意味する．
例えば図 3 のように，P2とP0が接続し，P0がP2とリンクを入れ換えるピアを選択する場合を考える．まずP2とP1と入れ換えたと仮定し，転送履歴をもとにして評価値を算出すると，5×2＋10×1＋…＋3×2＝300 となり，またP2とP3と入れ換えたと仮定し，同様に評価値を算出すると，5×1＋10×2＋…＋3×2＝200 となるとする．よってこの場合P0はリンクをP2と入れ換えるピアとしてP3を選択する．
P2

P4

レスポンスによるトラフィック
P2とP1を入換
5×2＋10×1＋…＋3×2＝300

P1P0P3

接続するリンク切断するリンク

P5

図3Fig.3

P2とP3を入換
5×1＋10×2＋…＋3×2＝200

アはそのレスポンスに対応するクエリを発行したピアへレスポンスを直接転送する．ピアは，レスポンスの情報を転送履歴として管理する．ピアは履歴として転送元，転送先，情報の種類を管理する．
以下，評価項目をピアの保持するリンク数，1 レスポンスあたりに必要なメッセージ数，1 検索あたりの平均被覆率とし，シミュレーション評価の結果を示し，考察を行う．
表 1 評価環境
Table 1 Simulation Parameters
評価パラメータ値
10000
ピア数
400
情報の種類
20
情報のグループ数10
保有可能な情報の種類数
0.003
クエリの発行確率TTL
5~7100
管理するレスポンスの転送履歴数
0.003
レスポンス転送履歴のチェック確率20000
シミュレーション時間

4.2

提案アルゴリズムの性能

まずアルゴリズムを適用して 20000 タイムスロット経過した後における，ピアの保持するリンク数の分布を図 4 に示す．評価対象 1 では 20 以上のリンク数をもつピアが 127 個あるのに対し，評価対象 2 では 10 以上のピアが 3 個であり，リンク入れ換えアルゴリズムの適用によって特定のピアへのリンクの集中を回避することを確認した．

評価値の算出10000

Calculation of Evaluation value

適用前
適用後(評価対象1)
適用後(評価対象2)

4. 評価
4.1

評価環境

提案アルゴリズムについて性能評価を行う．評価する対象は以下に示すとおりである．
評価1. ネットワーク繋ぎ換えアルゴリズムを適用するネットワーク
評価2. 提案アルゴリズムを適用するネットワーク
上記の評価対象における主な評価環境を表 1 に示す．
まずピアおよびピアの保持する情報についての評価環境を述べる．ピアの保持する情報や検索する情報に偏りをもたせるために，ピアおよび情報を 20 のグループに分類した．
各グループに属する情報数は 25 とし，グループ i に属する情報のうち 5 つはグループ i+1 にも属する．ピアの保持する情報は次のようにして決定する．ピアは 20 のグループの 1つをランダムに選択する．ピアが保有可能な情報の種類数を10 種類とし，そのうち 80%をピアの属するグループからランダムに選択する．残りは他のグループからランダムに選択する．ネットワーク内では，ピアは必ず一つ以上の隣接ピアをもち，予めピアが一つの大きな論理ネットワークをランダムに形成しているものとする．またピアのネットワークへの参加，ネットワークからの退出，ピアの故障は考慮しない．
ピアは検索の際，検索するグループを選択し，そのグループからランダムに検索する情報を決定する．検索手法にはフラッディングを用いる．またピアがレスポンスを転送する際に，レスポンス転送先へのリンクが切断されていた場合，ピ3

ピア数

1000

100

101024681012141618リンク数

図4

ピアの保持するリンク数

Fig.4

The number of links

次に 1 レスポンスあたりに必要なメッセージ数を図 5 に示
す．1 レスポンスあたりに必要なメッセージ数はレスポンスを 1 つ得るために必要なメッセージ数を表し，クエリの総数とレスポンスの総数の和を，レスポンスの総数で割ることによって得られる．TTL=5 と設定し，提案アルゴリズムを適用した際，1 レスポンス辺りに必要なメッセージ数が減少している．そして図４と合わせて考察すると，よりリンク数の多いピアが減少し，ネットワーク繋ぎ換えアルゴリズムを適用した場合に比べてトラフィックが削減されたといえる．
また 1 検索あたりの平均被覆率の変化についての評価結果を図 6 に示す．1 検索あたりの平均被覆率は，ピアが 1 度の検索で得たレスポンス数と，検索に該当するネットワーク

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

20

論文
DBSJ Letters Vol.4, No.2――――――――――――――――――――――――――――――――――――
リズムへの拡張を行う予定である．

全体の情報数との商の平均によって得ることができ，検索に該当する情報の取得率を表す．図 6 より評価対象 1 と比較して，提案アルゴリズムを適用することにより平均被覆率は低下した．平均被覆率が低下した要因としては，リンクを入れ換えることによってリンク数をほぼ一定に保つことがあげられる．一度リンクを接続すると繋ぎ換え以外でリンクは切断されないネットワーク繋ぎ換えアルゴリズムと比較すると，提案アルゴリズムではネットワーク全体の直径，つまりネットワークトポロジは明らかに大きくなってしまう．

[謝辞]
本研究の一部は，平成 15 年度総務省「ユビキタスネットワーク認証・エージェント技術の研究開発」の研究助成によるものである．また，本研究の一部は，文部科学省 21 世紀
COE プログラム「ネットワーク共生環境を築く情報技術の創出」（研究拠点形成費補助金）の研究助成によるものである．ここに記して謝意を表す．

50

１レスポンス辺りのメッセージ数[文献］[1] A. Crespo and H. Garcia-Molina: Routing indices forpeer-to-peer systems, In ICDCS, 2002, pp. 23-33.
[2] A. Crespo and H. Garcia-Molina: Semantic overlay
networks for p2p systems, Technical report, Computer
Science Department, Stanford University, 2002.
[3] 片山 肇, 中野 宏一, 春本 要, 西尾 章治郎: 応答転送
状況を用いた P2P ネットワークの繋ぎ換えアルゴリズムの評価, 日本データベース学会 Letters, Vol.4, No.1, June
2005

4030
TTL=7 (評価対象1)
TTL=5 (評価対象1)
TTL=7 (評価対象2)
TTL=5 (評価対象2)

20

10

片山 肇

005000

10000
タイムスロット

15000

20000

図5

1 レスポンスあたりに必要なメッセージ数

Fig.5

The number of message per a response

Hajime KATAYAMA

大阪大学大学院情報科学研究科博士前期課程在学中．2003
大阪大学工学部電子情報エネルギー工学科卒業．データベー
スシステム，マルチメディア情報システムなどの研究に従事．
日本データベース学会学生会員．

中野 宏一
1

TTL=7 (評価対象2)
TTL=6 (評価対象2)
TTL=7 (評価対象1)
TTL=6 (評価対象1)

0.9
0.8

春本 要平均被覆率

Kaname HARUMOTO

1992 年大阪大学基礎工学部情報工学科卒業．1994 年同大学
院基礎工学研究科博士前期課程修了．同年大阪大学大学院工学研究科情報システム工学専攻助手．1999 年大阪大学大型計算機センター講師，2000 年同大学サイバーメディアセン
ター講師を経て，2004 年同大学大学院工学研究科助教授となり，現在に至る．博士 (工学)．データベースシステム，マルチメディア情報システムなどの研究に従事．電子情報通信学会，情報処理学会会員，IEEE 各会員．

0.7
0.6
0.5
0.4
0.3
0.2
0.1

西尾 章治郎

00

2000

4000

図66000

8000

10000
12000
タイムスロット

14000

16000

18000

20000

1 検索あたりの平均被覆率

Fig.6

Average cover rate

5. まとめと今後の課題
レスポンスの転送状況を監視し，転送頻度の高いレスポンスを発見した場合に，そのレスポンスの経路に関して論理ネットワークを入れ換えるアルゴリズムを提案し，シミュレーションによる評価を行った．その結果から，提案アルゴリズ
ムを適用することにより，ネットワーク繋ぎ換えアルゴリズ
ムを適用した場合と比較してトラフィックを抑制することを確認した．しかし検索時に得られる情報数は減少した．な
お提案アルゴリズムはまだ初期的なアルゴリズムであり，今後はピアの参加，退出，故障時のアルゴリズム，リンク接続･切断アルゴリズムなどを考慮し，検索精度を改善したアルゴ

4

Hirokazu NAKANO

大阪大学大学院情報科学研究科博士前期課程在学中．2004
大阪大学工学部電子情報エネルギー工学科卒業．データベー
スシステム，マルチメディア情報システムなどの研究に従事．

Shojiro NISHIO

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

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