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

応答転送状況を用いた P2P ネッ
トワークの繋ぎ換えアルゴリズムの評価
A Topology Alteration Algorithm for P2P
Networks Based on Response Statistics

片山 肇♥
中野 宏一
金子 雄
春本 要♠
西尾 章治郎♦△◆Hajime KATAYAMA Hirokazu NAKANO
Yu KANEKO 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 propose a topology alteration algorithm forflooding-based P2P networks. The proposed algorithm
alters the topology of a P2P network so that a peer can beallocated near the peers that have information the peer
often requests. By simulation experiments, we show thatthe proposed algorithm improves the recall ratio. Finally,
we discuss the remaining issues to be solved.
♥

学生会員 大阪大学大学院情報科学研究科博士前期課程
katayama.hajime@ist.osaka-u.ac.jp△
学生会員 大阪大学大学院情報科学研究科博士前期課程
nakano.hirokazu@ist.osaka-u.ac.jp♠
学生会員 大阪大学大学院情報科学研究科博士前期課程
yu@nishio-mail.ise.eng.osaka-u.ac.jp♠正会員 大阪大学大学院工学研究科
harumoto@eng.osaka-u.ac.jp♦正会員 大阪大学大学院情報科学研究科
nishio@ist.osaka-u.ac.jp

1

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]などの手法が提案されている．

2.1

RI

RIはクエリをフラッディングするかわりに，隣接するピアのもつ情報を考慮し，応答の期待できるピアへのみクエリを転送する方式である．ピアは隣接するピアのもつ情報を管理する．クエリを受信すると，ピアは管理する情報をもとにして，隣接する各ピアから得られる応答の期待値を算出し，期待値の一番大きいピアへクエリを転送する．これを繰り返すことにより，要求される情報を保持するピアへクエリを転送することができる．この手法では応答の期待できるピアにのみクエリを転送するため，不必要なクエリの発生を抑えることができる．しかしRIにおいて論理ネットワークは静的である．これにより情報を保持するピアが論理ネットワーク上の離れたところに存在する場合，ピアは情報を取得できない可能性がある．

2.2

SONs

SONsではピアのもつ情報を考慮し，情報のジャンル別にネットワークを形成する．SONsでは情報のファイル名とその情報に対応するジャンル名を格納するデータベースが存在す
る．このデータベースを参照することにより，情報に対応す日本データベース学会 Letters Vol.4, No.1

論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――るジャンルを一意に決定することができる．ジャンルはroot，style，substyleの順に階層化されている．ピアは，自身が持つファイルのジャンルに該当するネットワーク(SON)に参加し，そのSON内に属する他のピアとリンクする．検索の際は，情報の分類と同様にクエリをジャンルに分類し，該当するSONへ転送する．SONsでは情報のジャンルごとにネットワークを形成するため，検索精度が非常に高い．ただしこの手法は情報が明確にジャンルに分類できる場合に限る．情報が明確に分類できない場合は，一般的な条件比較などを含むクエリに対してはどのSONにそれを転送すればよいか判別できないため適用できない．また，一つのSON内においてクエリはフラッディングされるため，トラフィック増大の問題は部分的にしか解決できていない．

3. 提案アルゴリズム
3.1

想定環境

ピアは必ず 1 つ以上のピアとリンクを保持するものとし，リンク先のピアを隣接ピアとする．ピアは全体で 1 つの論理ネットワークを形成し，ピアのネットワークへの参加，ネットワークからの脱退，ピアの故障については考慮せず，論理ネットワークが複数に分断されることはないものとする．情報を検索する際の検索手法にはフラッディングを用いた．

3.2

評価値の算出リンクの繋ぎ換えが行われると論理ネットワークのトポロジが変化する．ホップ数が短縮される経路においては，小さいホップ数で検索できるが，ホップ数の延長される経路では，検索時に大きなホップ数が必要になるためリンクを繋ぎ換えないほうが良い可能性がある．そこでリンクを繋ぎ換えることによって，得られるレスポンス数が減少する可能性を考慮するために，ピアはリンクの繋ぎ換え前に，繋ぎ換えによるレスポンス数の増減を評価値として算出する．ピアは繋ぎ換えを行うかを評価値をもとに判断する．
評価値は∑i(N(Qi)×HQi)の式を用いて計算する．Qiは注目しているレスポンスの流れる経路上にあるピアを表す．
N(Qi)は，ピアQi+1を経由せず，ピアQi〜Q1を経由してQ0に流れるレスポンスの件数を表す．HQiは繋ぎ換えにより増減するQiQ0間のホップ数を表す．そしてN(Qi)とHQiの積をとることで，リンクの繋ぎ換えによって増減するQiQ0間を流れるレスポンス数を得ることができる．最後にQiQ0間の全てのピアについてN(Qi)×HQiの総和をとることで，リンクの繋ぎ換えるによって増減するメッセージ数を算出できる．算出結果が負数の場合はリンクの繋ぎ換えによって良い影響を与え，正数の場合は悪い影響を与えると判断する．
例えば図 1 のように，Q0とQ1を結ぶリンクを切断し，新しくQ0とQ3をリンク接続する場合を考える．
Q3
H-HQ3=1(H-HQ3)-HQ3=-2

N(Q3)=75
HQ3=3Q2

N(Qi)：Qi⇒Q0を流れるレスポンス数
H-HQi：繋ぎ換え後のHQi,HQ0間のホップ数
HQi：繋ぎ換え前のHQi,HQ0間のホップ数(H-HQi)-HQi：ホップ数の増減

H-HQ2=2(H-HQ2)-HQ2=0

N(Q2)=75
HQ2=2Q1

H-HQ1=3(H-HQ1)-HQ1=2

N(Q1)=50
HQ1=1(Q3における影響)=N(Q3)×((H-HQ3)-HQ3)=75×(-2)=-150(Q2における影響)=20×0=0(Q1における影響)=50×2=100Q0

繋ぎ換え前

繋ぎ換え後

図1
Fig.12(繋ぎ換え全体での影響)=-150+0+100=-50

影響の算出

Calculation of Influence

まずQ3について影響を算出すると，繋ぎ換えによるホップ数の増減はHQ3=-2 となる．N(Q3)=75 であることから，繋ぎ換えによるQ3における影響はN(Q3)×HQ3=-150 となる．同様に，Q2についてはN(Q2)×HQ2=0 となり，Q1についてはN(Q1)×HQ1=100 となる．Q3〜Q1におけるそれぞれの評価値の合計が-150+0+100=-50 であることから，ピアQ0は，Q1とのリンクを切断してQ3へリンクを繋ぎ換えることがネットワークへ良い影響を与えると判断する．

3.3 転送履歴チェック
ピアはレスポンスの転送履歴を保持する．保持する転送履歴情報は，転送元，転送先，情報の種類とする．ここでは簡単のため，ピアへレスポンスを転送してきた隣接ピアを転送元とし，ピアがレスポンスを転送した先の隣接ピアを転送先とする．ピアは，自身の保持するレスポンスの転送履歴を不定期にチェックする．そして転送元，転送先，情報の種類の組み合わせの中で，一番多い組み合わせのレスポンスに関して次節に示すアルゴリズムを実行する．

3.4 アルゴリズムの実行
ピアは転送履歴チェックによって，転送した数の一番多いレスポンスに関して繋ぎ換えのアルゴリズムを実行する．繋ぎ換えのアルゴリズムを実行するピアを実行ピア，リンクの繋ぎ換え先となるピアをソースピアとする．以下図 1 を例に挙げてアルゴリズムの実行手順を説明する．なお初期状態として，ピアQ1を実行ピア，ピアQ3をソースピアとする．
(1)Q1は，転送頻度が高いと判断したレスポンスについて，そのレスポンスの転送先のQ0に対してソースピアとリンクを張り，実行ピアとのリンクを切るように促す．
(2)繋ぎ換えを促されたQ0は，自身を経由するレスポンスにおいて，Q1とのリンクを切断し，Q3へリンクを繋ぎ換えた場合の影響を評価値として算出する．評価値の算出方
法は 3.2 節の通りである．
(3)評価値が負数である場合，Q0はQ1から実行ピアの権限を引き継ぎ(1)に戻る．
(4)評価値が正数である場合，Q0は繋ぎ換えを拒否する．このときQ1はQ3へリンクを繋ぎ換える．ただし実行ピアがソースピアに既にリンクしている場合，リンクの繋ぎ換えは行わない．例えばアルゴリズムを実行した最初の実行ピアは，既にソースピアとリンクしているため，拒否メッセージを受信しても繋ぎ換えは行わない．
こうして判定依頼メッセージを受けたピアが，実行ピアに拒否メッセージを送信し，実行ピアがソースピアへのリンクの繋ぎ換えを行うまで上記の手順が繰り返される．

4. 評価
4.1 評価環境
提案アルゴリズムについて 2 種類の評価を行う．評価項目
は以下の通りである．
評価1. ネットワークトポロジの変化
評価2. 提案アルゴリズムの性能
評価 1 では，小規模なネットワークにおいて提案アルゴリズムを適用し，論理ネットワークトポロジの変化を確認する．
評価 2 では大規模なネットワークにおいて，レスポンス 1 つを得るために必要なメッセージ数，ピアのもつリンク数，及びネットワーク内のトラフィック量を評価する．
上記の評価項目における主な評価環境を表 1 に示す．
まずピアおよびピアの保持する情報についての評価環境を述べる．ピアの保持する情報や検索する情報に偏りをもた

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

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

表 1 評価環境
Table 1 Simulation Parameters
評価環境
ピア数
情報の種類
情報のグループ数
保有可能な情報の種類数
クエリの発行確率
TTL
管理するレスポンスの転送履歴数
レスポンス転送履歴のチェック確率
シミュレーション時間

評価 110080
4100.05
41000.0540000

評価 210000
40020100.003
5~71000.003
20000

4.2 ネットワークトポロジの変化
提案アルゴリズムを適用した際の，ネットワークトポロジの変化を図 2 に示す．ネットワークトポロジの描画にはGraphExplore[3]を利用した．左側が提案アルゴリズム適用前，右側が提案アルゴリズムを適用して 20000 タイムスロッ
ト経過後の論理ネットワークトポロジを表す．情報のグルー
プ別のピア数および，同じグループに属するピア同士で接続されているリンク数の変化は表 2 に示すとおりである．
図 2 および表 2 より，提案アルゴリズムを適用することによってランダムに構成されていた論理ネットワークのトポロジが変化し，同じグループのピア同士が論理ネットワーク上の近くに配置されていることが分かる．

3：グループ1
クラスタ1：グループ2
クラスタ2：クラスタ3
グループ3
グループ4：クラスタ4

図2Fig.2

トポロジの変化Change of network topology

表 2 同一グループに属するピア同士のリンク数
Table 2 The number of links between peers in the samegroup
グループ
ピア数
適用前
適用後
1231221230152932181142614114.3 提案アルゴリズムの性能
まず 1 検索あたりの平均被覆率は，ピアが 1 度の検索で得たレスポンス数と，検索に該当するネットワーク全体の情報数との商の平均によって得ることができ，検索に該当する情報の取得率を表す．提案アルゴリズムを適用しない状態で2000 タイムスロット経過させた後に提案アルゴリズムを適用し，その際の時間推移による 1 検索あたりの平均被覆率の変化についての評価結果を図 3 に示す．
図 3 によると TTL を 7 に設定した際，提案アルゴリズム適用前における 1 検索あたりの平均被覆率は 0.2 で一定であった．しかし提案アルゴリズムを適用することにより，タイムスロットの経過に伴い平均被覆率は増加し，6000 タイムスロット経過後には平均被覆率が 0.8 に到達している．このことからタイムスロットの経過に伴いリンクの繋ぎ換えが実行され，リンクの繋ぎ換えによってピアの論理ネットワー
ク上の周辺に，検索したい情報をもつピアが集合したことが分かる．
1TTL=7
TTL=6
TTL=50.9
0.80.7平均被覆率せるために，ピアおよび情報を 20 のグループに分類した．
各グループに属する情報数は 25 とし，グループ i に属する情報のうち 5 つはグループ i+1 にも属する．ピアの保持する情報は次のようにして決定する．ピアは 20 のグループの 1つをランダムに選択する．ピアが保有可能な情報の種類数を10 種類とし，そのうち 80%をピアの属するグループからランダムに選択する．残りは他のグループからランダムに選択する．ネットワーク内では，ピアは必ず一つ以上の隣接ピアをもつものとし，予めピアが一つの大きな論理ネットワークをランダムに形成しているものとする．またピアのネットワークへの参加，ネットワークからの退出，ピアの故障は考慮しない．
ピアは検索の際，検索するグループを選択し，そのグループからランダムに検索する情報を決定する．検索手法にはフラッディングを用いる．またピアがレスポンスを転送する際に，レスポンス転送先へのリンクが切断されていた場合，ピアはそのレスポンスに対応するクエリを発行したピアへレスポンスを直接転送する．ピアは，レスポンスの情報を転送履歴として管理する．ピアは履歴として転送元，転送先，情報の種類を管理する．
評価対象は，ピアの検索する情報に相関性があるネットワークとした．評価対象において，ピアは検索するグループを選択する際，80%の確率で自身の属するグループを選択し，20%で他のグループを選択する．ピアの検索する情報がピアの保持する情報に関連付けられていることから，実世界の想定により近い環境といえる．ピアは P(i) = {f(A(i))- f(A(i+1))}/{f(A(i))-0}の式を用いてグループ i を決定する． P(i)はグルー
プ i が選択される確率を表す．A(i)はグループ i の重みを表し，A(i)= i とする． f(x)は Zipf 分布の式 f(x)=10×((X+1)×0 . 01 − 1 . 08 )により決定する．なお評価項目は次のとおりである．以下シミュレーション評価の結果を示し，考察を行う．

0.60.50.40.30.20.1
0-202

図34681012
タイムスロット[×1000]

14161820

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

Fig.3

Average cover rate

次に 1 レスポンスあたりに必要なメッセージ数を図 4 に示
す．1 レスポンスあたりに必要なメッセージ数はレスポンスを 1 つ得るために必要なメッセージ数を表し，クエリの総数

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

論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――とレスポンスの総数の和を，レスポンスの総数で割ることによって得られる．現状では時間の経過，TTL によらずレスポンスを１つ得るために発生するメッセージ数は一定である
ことが分かる．これはリンクが繋ぎ換えられ，得られるレスポンス数が増加するものの，同時にトラフィックも増大したことが原因である．
最後に提案アルゴリズムを適用後 20000 タイムスロット
経過時における，ピアの保持するリンク数分布を図 5 に示す．
リンク数が 2，または 3 であるピアが全体の約 75%を占め，リンクが極少数のピアに集中している．このことからクエリがリンクの集中するピアを経由することでトラフィックが増大していることがわかる．

１レスポンス辺りのメッセージ数

4030
TTL=5
TTL=6

[文献］

片山 肇
02000040000
60000
タイムスロット80000

図4

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

Fig.4

The number of message per a response

100000

6000
5000

TTL=7
TTL=6
TTL=54000
3000
2000
10000

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
リンク数

図5

ピアの保持するリンク数

Fig.5

The number of links

5 まとめと今後の課題
レスポンスの転送状況を監視し，転送頻度の高いレスポンスを発見した場合に，そのレスポンスの経路に関して論理ネットワークを繋ぎ換えるアルゴリズムを提案した．これにより情報を要求するピアと，その情報を保持するピアを論理ネットワーク上の近傍に再配置することができた．またシミュレーションによる評価を行った．その結果から，提案アルゴリズムを適用することにより，論理ネットワークトポロジが組織化され，検索時に得られる情報数が増加することを確認した．なお提案アルゴリズムはまだ初期的なアルゴリズムであり，今後はピアの参加，退出，故障時のアルゴリズム，リHajime KATAYAMA

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

中野 宏一

Hirokazu NAKANO

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

金子 雄

7000

ピア数

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

TTL=71004[謝辞][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] W. Quanli, Y. Guang, N. Joseph, W. Mike and D.
Adrian: “GraphExplore: A Software Tool for Network
Visualization,” Duke University, 2004.

5020

ンク接続･切断アルゴリズム，トラフィックの削減などを考慮したアルゴリズムへの拡張を行う予定である．

Yu KANEKO

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

春本 要

Kaname HARUMOTO

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

西尾 章治郎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.1