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

ピアツーピアネットワークにおけるトピック主導型問合せルーチン
グアルゴリズムの提案
Proposal of hierarchical routing algorithms
of topic driven queries over P2P network

中辻 真♥
河野 浩之♣

岸 浩史♦
川原 稔♠

Makoto NAKATSUJI Hiroshi KISHI
Hiroyuki KAWANO Minoru KAWAHARA

近年，P2P ネットワークにおける情報交換システムが普及しつつある．検索手法もファイル名依存の検索から，内容を考慮した検索へ発展しているが，超分散環境のため，応答時間や問合せ多発によるネットワーク帯域の圧迫が問題である．本研究では，従来のブロードキャスト式問合せ発行法ではなく，問合せにリソースの特性を反映した記述を与え，各ピアで問合せに合致するリソースを持つピアから検索ピアへ送り返される問合せ応答の内容を監視する．そして，隣接ピア経由で到達可能な複数ピアの格納データの特性を蓄積しておき，問合せ受信時に問合せと照合し，転送先に対するルーチングを行う．更に，リソースの特性を階層化し，蓄積情報の簡素化と管理コストの削減を行う手法の提案も行う．
また，提案手法の有効性をシミュレーションにより検証する．
P2P information retrieval systems are becoming one of
the most popular Internet applications and occupy amajor traffic in Internet. Searching methods haverecentlychanged
fromfile-namedqueries
tocontents-based queries. But because of widely distributedsystems, it spends much response time and thebandwidths of traffic increase. In this paper, we propose
techniques to manage routing tables by utilizing thecharacteristics of queries, so that users can deal withquery based on topics instead of query broad casting. We
adopt hierarchical routing tables to reduce storage andmanagement costs. We evaluate the performances
between original query routing algorithm and ourproposed algorithms.

1. 導入
現在， P2P(ピアツーピア)ネットワーク環境下で，個対個♥

正会員 日本電信電話株式会社NTTネットワークサービ
スシステム研究所 nakatsuji.makoto@lab.ntt.co.jp♦
京都大学大学院情報学研究科博士前期課程
kishih@sys.i.kyoto-u.ac.jp♠
正会員 京都大学大学院情報学研究科
kawano@i.kyoto-u.ac.jp♠
京都大学学術情報メディアセンター
minoru@media.kyoto-u.ac.jp

1や，グループ対グループでリソースの交換を実現するクライアント・クライアント型のシステムが注目されている[4]．
この種の情報交換システムは，パーソナルコンピュータ上の比較的小規模な蓄積データを対象とするだけでなく，広範囲に分散する膨大な数のWebサーバ上の多様なデータを統合的に扱う可能性を備えており，情報流通機構を実現する基盤となる広域分散型データベースシステムとしても興味深い[1]．
もっとも，現在のP2P型情報交換システムは，ネットワークトポロジ生成時のネットワーク帯域の圧迫といった問題を抱えており，検索応答時間の保証も課題となっている．
本研究では，P2Pネットワーク上の情報流通技術課題の解決のため，動的なネットワークに対応したトピック主導型検索機構を実現する手法を提案する．本手法は，蓄積リソースの特性をルーチングに反映させ，効率良い問合せ実行を行う．
なお，各ピアの登録情報や問合せの基本的フォーマットは
Sun Microsystems社(SUN)で開発されているJXTAサーチで提案されたQRP(Query Routing Protocol)に基づく[7]．

2. P2P におけるリソース検索と関連研究
現在の P2P 情報検索システムの特徴を表 1 に示す[2]．
著者らは，過去の検索で用いたインデックスを利用し，検索の効率化を図った[1,5]．メタ情報とピアの ID を結びつけるインデックスは，問合せメッセージ数を抑えた効率的なトピック主導型検索を実現する．但し，ネットワークトポロジが動的に変化するため，各ピアの保持するインデックス管理機構がシステム性能上の課題となる．
その他，DHT(Distributed Hash Table)を用いる手法[6]では，分散型システムにおけるデータにキーを付加し，これに基づいたルーチングテーブルを用い，データ識別を行うことでシステム内の検索効率の向上を試みている．
本研究では，従来の問合せブロードキャスト型(NQR 手法)や分散インデックス型ではなく，トピック主導分散型にトピック主導の問合せルーチング機構を付け加える事を考える．
これにより，現在の P2P 情報検索システムの持つ主要な課題，例えば，単純な検索機能しか備えないため利用者の意図する問合せ結果を得る事が困難な点や，動的ネットワーク環境下での不安定な検索性能，各ピアの持つリソース情報の管理コストの増大，問合せパケットの頻発によるネットワーク帯域圧迫等を包括的に解決する可能性があり，有用性が高い．
以下，本研究の検索処理に用いるJXTAサーチを説明する．
JXTAサーチ[7]は，ピアが相互作用を行うコミュニケーシ
ョン基盤の標準化を目指すSUNのプロジェクトJXTAの為のデフォルトの検索手法を提供する．JXTAサーチ上の通信はQRPと呼ばれるXMLプロトコルを通し実行される．QRPはJXTAサーチネットワーク上で問合せを送受信する機能と，ネットワーク内のノードに対するメタ情報を定義する機能を提供する．
JXTAサーチネットワークは，問合せに応答しリソースを提供する情報プロバイダ，問合せを作成するコンシューマ，メッセージ監視とルーチング提供を行うハブから構成される．
QRP は問合せ，問合せ応答，登録情報というコンポーネントから成る XML プロトコルである．各プロトコルが用いるタグを以下に示す．QRP は構造化され，軽量な問合せメッセージ交換の提供により，XML のエンコーディング処理や問合せ転送処理によるオーバヘッドの低減を試みている．
1.
問合せメッセージz request：問合せメッセージのメタ情報格納z query：問合せメッセージの本体格納

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

論文
DBSJ Letters Vol.2, No.3――――――――――――――――――――――――――――――――――――
Table 1

表 1 P2P 情報検索システムのタイプ別比較
Comparison of the P2P information retrieval systems.

タイプ

集中管理型

ブロードキャスト型

分散インデックス型

トピック主導分散型

特徴
利点
欠点

S/C 型システム
集中管理機構サーバ障害に弱い

問合せブロードキャスト
インデックス不要
問合せ頻発

各ピアのインデックス管理
ルーチング
インデックス管理複雑化

リソースの属性メタ情報利用
トピック指向の検索
メタデータ管理複雑化

2.

応答メッセージ
responses：応答メッセージのメタ情報格
response：応答メッセージの本体格納
3.
登録メッセージz register：登録メッセージ格納z query-server：情報プロバイダ（問合せサーバ)格納z predicate：論理状態である述語格納z query-space：指定する問合せ空間情報格納
zz

3. トピック主導型問合せルーチング手法
3.1 QR(Query Routing)手法
本節では，問合せをブロードキャストするのでは無く，要求リソースに付随する複数属性値に基づき転送するトピッ
ク主導型問合せルーチング手法である QR 手法を提案する[2]．
（1）リソースの特性を反映する問合せの記述
まず，問合せにリソース特性を反映する事を考える．そのため，問合せの記述形式とし，JXTA サーチにおける QRP にMPEG7 で標準化されている，リソース特性を示す属性であるメタ情報の記述形式を付加する事を提案する．
z MPEG-7：リソース
z CreationMetaInformation：作成に関する情報
z MultimediaContent：フォーマット，拡張子等
また，問合せ記述には，問合せの到達範囲を制限するTTL(Time To Live)や，問合せの重複受け付け防止識別子である query-uuid(query unique ID)を与える．以下に，本研究で提案する問合せの構成を簡単にまとめる．
1. 名前空間や問合せ ID の指定等の記述に QRP 採用
2. 問合せメッセージを request タグ内に格納
3. MPEG7 の記述形式を，問合せメッセージ要素や属性の名前を一意に指定する名前空間 xmlns の値として指定（2）各ピアの蓄積データを反映する登録情報
ネットワーク内の各ピアは，自身に転送されてきた問合せを受け取るか，また，隣接ピアに転送するかを判断するための登録情報をもつ．本研究では，各ピアに自身の蓄積するデータ特性を反映したメタ情報を与えており，問合せが転送されると，各ピアは，登録情報の中の predicate タグに格納されている述語が指定する記述と，問合せに含まれる query タグに含まれる記述を照合し，問合せを自身と自身の隣接ピアに転送するか判断する．登録情報の構成を以下に示す．
1. 名前空間の指定等の記述には QRP を採用
2. 登録メッセージを register タグ内に格納
3. 名前空間において，MPEG7 の記述形式を指定し，xmlnsの値として含む．これにより，情報プロバイダにルーチングされるために問合せがマッチしなければならない論
理状態である述語を格納する predicate タグ内を構成する要素や属性の名前の記述形式は，MPEG7 で提唱されているメタ情報の記述形式に従う．
4. 述語とマッチする問合せは，問合せサーバで示される情報プロバイダへ転送し，問合せサーバを query-serverタグ内に格納する．
5. 述語と問合せを照合する問合せ空間の URL を query-2

space タグ内に格納する．
（3）問合せ応答の記述
問合せのブロードキャストによるネットワーク帯域の圧迫を避けるため，各ピアは，受け取った問合せを隣接ピアのうちどのピアに転送すべきかを判断する必要がある．そこで，各ピアは，返送される問合せ応答の response，data タグ内に含まれる記述を監視する事により，隣接ピアを経由して到達可能な複数のピアの蓄積するデータの特性を反映した登録情報を保持する．本研究では，問合せ応答の記述形式として，JXTA サーチにおける QRP に，MPEG7 で用いられているメタ情報記述形式として以下の 4 項目を付加する事を提案する．
1. 名前空間の指定等の記述は QRP を採用
2. 問合せ応答メッセージを responses タグ内に格納
3. 問合せ応答メッセージの本体は response タグ内に格納
4. 名前空間において，MPEG7 の記述形式を指定し，xmlnsの値として含む．これにより，問合せ応答の本体であるresponse タグ内を構成する要素や属性の名前の記述形
式は MPEG7 で提唱されるメタ情報記述形式に従う．
（4）QR 手法の問合せルーチングアルゴリズム（図１）
ネットワークに存在する各ピアはそれぞれ上記で述べた記述形式を持つ問合せを発行し，情報登録を行う．
（３）追加情報をCへ返送
C（５）追加情報で隣接ピアの持つリソース情報更新
A（１）問合せ発行，自己の登録情報と照合し，転送（４）問合せ転送（TTL減少）PB（２）問合せと登録情報を照合

図 1 QR における問合せルーチングアルゴリズムの例
Fig.1 An example of query routing algorithm in QR.
1. 検索ピア(C)は問合せを発行する．そして，自身の登録情報と問合せを照合し，隣接ピアの内，適切と判断されるピア(A)へと問合せを発行する．
2. 問合せを受け取ったピア(A)は， 問合せメッセージに含まれる query-uuid を用い，以前受け取った問合せで無ければ，自身の登録情報と問合せを照合する．そして，マッチする部分を持つ場合は，検索ピア(C)へ問合せ応答を送り返し，更に，隣接ピア(P,B)の内，適切と判断されるピア(P)へ，問合せを送信する．また，TTL により，問合せの到達範囲を確認・制御する．
3. ピア(A)は，問合せ応答を受け取ると，その情報をチェックし，どのようなリソース情報を含んだ応答が隣接ピアのうちどのピアから返送されてきたかを登録する．これにより，次に同様の問合せが来た場合は，各ピアの登録情報を参照し，適切と判断されたピアへと転送する．
QR 手法はルーチングを行うことで，問合せによるネットワークの帯域圧迫の問題を緩和する．また，各ピアは，動的なネットワークトポロジの下でも，信頼性のあるトピック主導型検索を行う事が可能となる．しかし，QR 手法では，各ピアによる登録作業や管理が複雑化し，また，問合せメッセージと登録情報の照合に関するオーバヘッドも問題である．そこ
で，次節では，各ピアがリソースを階層的に登録する事で，日本データベース学会 Letters Vol.2, No.3

論文
DBSJ Letters Vol.2, No.3――――――――――――――――――――――――――――――――――――
登録情報のサイズの縮小を行い，管理の容易化や問合せルーチングによるオーバヘッドの抑制を試みる．

3.2 HQR(Hierarchical Query Routing)手法
本節では，各ピアの登録情報に，リソースをトピック別に階層的に管理する機能を付加した HQR 手法を提案する．
（1）リソースの階層化
リソースをトピック別に階層的に分類するため，本研究では，MPEG7 で標準化されているリソース属性を利用する．
MPEG7 で表現されるメタ情報は木構造形式でモデル化され，リソースの特徴を基に階層的に分類できる．なお，新しい種類のリソースが出現した際は，MPEG7 のメタ情報に従う．
（2）HQR 手法の問合せルーチングアルゴリズム
図 2 を用い HQR 手法のルーチングアルゴリズムを述べる．
（３）追加情報をCへ返送（５）追加情報で隣接ピアの （４）問合せ転送（TTL減少）
持つリソース情報更新
AC（１）問合せ発行，自己の登録情報と照合し，転送(MP3検索)「音声ファイルならA」<MP3保持>P<音声ファイル>（２）問合せと登録情報を照合「MP3ならP」

B<WAVE保持>図 2 HQR における問合せルーチングアルゴリズムの例
Fig.2 An example of query routing algorithm in HQR.
1. 検索ピア(C)は問合せを発行する．そして，自身の登録情報と問合せを照合し，隣接ピアの内，適切と判断されるピア(A)へと問合せを発行する．
2. ピア(A)は，query-uuid をチェックする．次に，自身の登録情報と問合せを照合し，問合せの要求リソースが所属するトピックの転送を許可する部分がある場合，検索ピア(C)へ問合せ応答を送り返し，更に，隣接ピア(P,B)の内，適切と判断されるピア(P)へと問合せを送信する．
又，TTL を用い，問合せ到達範囲を制御する．
3. ピア(A)は，問合せ応答を受け取ると，その情報を用い，どのようなトピックに関する応答が隣接ピアのうちどのピアから返送されてきたかを登録する．そして，次に同じトピックに所属するリソースを要求する問合せが来た
場合は，登録情報により，適切と判断されたピアへと転送できる．これにより，ピア(A)の管理者は，管理コストを削減でき，また，登録作業を簡単化する事が出来る．

3.3 ピアの登録情報の更新提案手法では，各ピアは，経由する問合せを監視しながら登録情報を構築していくが，各ピアの持つリソースが動的に変化する P2P ネットワークでは，以前記憶した登録情報が現在の問合せルーチングに使用できなくなる場合が頻繁に
起 こ る ． そ こ で ， 本 研 究 で は あ る ピ ア hi の 検 索 頻 度 をSearchFrequencyi ，ユーザが与えるヒューリスティックなパラメータを ξ とし， SearchFrequencyi ≥ ξ を満たす場合，ブロードキャストを行い，各ピアの持つ登録情報を更新する．

4. シミュレーションによる性能評価
4.1 P2P ネットワークのモデル化（1）検索評価モデル
現在の P2P 検索システムでは，頻発される検索メッセー
ジによるネットワーク帯域圧迫の解決が重要である．例えば，Sandvine 社（http://www.sandvine.com/）の 2002 年 12 月の調査によると，サービスプロバイダの提供するネットワーク帯域の約 60%を P2P アプリケーションが使用している．
本稿では，動的な P2P ネットワーク環境における帯域圧迫の解決とピアの持つ登録情報の更新の簡単化を目的とし，3ネットワーク性能に注目する．評価コスト C を，ネットワー
クに発行される問合せ数 N q と各ピアの管理する登録情報数
N r を用い，C = η × N q + θ × N r と表す．なお，定数 η と θ はヒューリスティックなパラメータである．
（2）シミュレーションに利用するパラメータ値
シミュレーションでは，ピアの接続形態を決定するネットワークトポロジ Topo log y は木構造とし，各ピアの隣接ピア数である分岐数 BranchingFactor と TTL を，一般的 P2P ア
プリケーションの平均値を基に，各々4，8 とする．よって，到達できる全ピア数 NumNodes は，87381(= (48 − 1) / 1) となる．
また，ネットワーク内のリソース種類 Type Re source を 81 とする．この値は，様々にモデル化する事が望ましいが，本研究では，簡単な評価を与えるため固定値を用いた．各リソースに対する平均問合せ応答数 Query Re sult は，一般的 P2P ア
プリケーションでは，Query Re sult = NumNodes × 0.0052 となるため，4500 とする[3]．
（3）シミュレーションで用いるネットワーク特性
ネットワーク内のリソース分布形態を示すリソース配分
率 Re sourceDistribution は，80%のピアが 20%のリソースをランダムに蓄積し，残り 20%のピアが残り 80%のリソースをランダムに蓄積するという P2P システムの分布モデルを仮定する．また，ネットワークにおける問合せ発行率
QueryFrequency は，その 80%を 20%の数の決まったピアが発行し，残り 20%の問合せを残り 80%の決まったピアが発行すると仮定する．更に，各ピア内のリソース変化形態を示すパラメータ Change については，各ピアは検索を終了する度に要求リソースを獲得するとし，各ピアの所有リソースは，検索進行につれ増加するとする．また，3.3 節で述べた，各ピアの保持するリソース数が動的に変化する場合の各ピアの持つ登録情報の更新頻度を決定するパラメータ Update を，更新効果を明確に確認するため，ピアが検索を一定回数行う度に一度問合せをブロードキャストする事で，各ピアの登録情報を更新する事にする．シミュレーション実験では，Typeresource 種のリソースを階層的に分類可能と仮定する．
また，問合せルーチングのカバー率のモデル化について考察する．本稿では，問合せルーチングのカバー率 Cover を，問合せが任意のリソース γ を要求する際，問合せルーチングによる γ のヒット数を Hit γ とし，ネットワークにおけるリソース γ の総数を Tγ とし， Cover = Hitγ / Tγ と定義する．

4.2 性能評価
ピア間を流れる問合せ数を，トピック主導の問合せルーチングを考慮しないブロードキャスト手法である NQR 手法と本研究の提案手法とで比較した結果を表 2 に示す．ここで，
HQR 手法の階層の深さは，2 階層，3 階層の場合を考える．
NQR 手法QR 手法
HQR 手法（2 階層）
HQR 手法（3 階層）

問合せ数2134349437
6956643006

表 2 NQR 手法と提案手法における問合せ数の比較
Table 2 Comparison of the number of queries between
NQR approach and our proposed approaches.
表 2 によると，ルーチング機構をもたない NQR 手法に比較し，本研究で提案した QR 手法の問合せメッセージ数が著しく減少している．これは，QR では登録情報を用いるため，

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

論文
DBSJ Letters Vol.2, No.3――――――――――――――――――――――――――――――――――――
NQR より効率よく問合せ処理ができるためである．また，問合せメッセージ数は QR 手法の方が階層構造を利用するHQR 手法よりも低い．これは，QR では，リソースの存在する経路上のピアにのみ問合せを転送するのに対し，HQR ではあるリソースを要求する問合せは，そのリソースと同じトピック集合に分類されるリソースを持つ経路上のピア全てに転送されるためである．また， 3 階層 HQR の方が 2 階層
HQR よりネットワークに発行される問合せ数が少ない．これはトピック集合を小さく絞り込む事が出来るためである．
QR 手法
HQR 手法（2 階層）
HQR 手法（3 階層）

登録情報数
81912

表 3 QR 手法と HQR 手法の登録情報数の比較
Table 3 Comparison of the number of registrations
between QR approach and HQR approach.
しかしながら，表 3 に示した，ピアの登録情報数を QR 手法と HQR 手法で比較した結果からは，HQR はリソース属性を利用して登録情報を減らしていることが分かる．これにより，各ピアの登録情報管理は，HQR の方が容易になる．
次に，リソース数が頻繁かつ動的に変化する場合の登録情報の更新問題について考察する．シミュレーションでは，ピアがある特定のリソース δ を一定回数検索する度に一度問合せをブロードキャストする事で，各ピアの登録情報を更新する． 図 3 に，HQR 手法に対して，リソース δ に関する問合せルーチングのカバー率の変化を調べ，問合せメッセージ数と，動的ネットワークへの問合せルーチング適応性のトレードオフを示した．検索が進むにつれ，ヒューリスティックなメッセージ転送機構が働くため，各ピアの登録情報を利用する問合せルーチングのカバー率は低下する．カバー率低下により，ネットワーク中の問合せメッセージ数は減少し，情報資源 δ に関する適合率が上昇する．しかし，カバー率が低下すると，動的なネットワーク環境下で，情報資源 δ を発見しにくくなる問題が発生する．そのため，定期的に問合せをブロードキャストする事で，各ピアの登録情報を更新し，問合せルーチングのカバー率を向上させる必要がある．なお，
図 3 からは，検索過程が進行するにつれ，各ピアの持つ登録情報が詳細なものとなり，カバー率の減少度が小さくなる．

5. 結び
本研究では登録情報を活用する事で，問合せを，ネットワーク内で適切なリソースを持つサブネットワークへ転送する手法を提案した．又，リソースの階層化により，管理コスト削減と登録情報記述の簡単化を行う HQR 手法を提案した．
そして，シミュレーションにより，提案手法は NQR 手法と比較し，ネットワーク帯域の圧迫を抑制出来る事，HQR 手法は，登録情報の管理やサイズを削減出来る事を議論した．
今後の課題として，シミュレーションにおいて，ネットワークトポロジを，P2P ネットワークにおけるピアの接続形態に経験的に近いとされる power law グラフ等，様々に変化させた場合や，各ピアの接続性を考慮した場合，リソースの階層をより深くした場合の提案手法の有効性や，提案手法における問合せルーチングによるオーバヘッドの影響の検証が必要である．また，提案手法の実装を行い，実システムにおける性能検証を要する．なお，P2P ネットワーク上のセキュリティやプライバシーの観点から，ピアや問合せの信頼度情報等を考慮した問合せルーチング機構も検討が必要である．

4

図 3 リソース δ を動的に更新した際のルーチングカバー率
Fig.3 Cover ratio for dynamical updating resource δ .
[ 謝 辞 ] 本 稿 の 一 部 は ， 文 部 省 科 学 研 究 費 (15017248,13680482)の研究成果による．

[文献][1] 中辻真，川原稔，河野浩之, “トピック主導型 P2P 情報検索システムの提案と性能評価,” 電子情報通信学会論文誌
VOL.J87-DI No.2 (データ工学特集号), 2004.
[2] 中辻真，岸浩史，河野浩之，川原稔，``ピアツーピアネ
ットワークにおけるトピック主導型問合せルーチング の提案，''電子情報通信学会技術研究報告，vol.103，no.104,
pp.7-12，June 2003.
[3] A. Crespo, and H. Garcia-Molina, ``Routing Indices For
Peer-to-Peer Systems,'' Proceedings of the 22nd IEEE
International Conference on Distributed ComputingSystems, no.140, pp.23-32, Vienna, Austria, July 2002.
[4] D. Clark, ``Face-to-Face with Peer-to-Peer Networking,'' Computer, vol.34, no1, pp.18-20, Jan. 2001.
[5] M. Nakatsuji, M. Kawahara, and H. Kawano, ``Advanced index refinement by classifiers and distillers inP2P resource discovery,'' International Conference onIntelligent Agents Web Technology and Internet Commerce' 2003, pp.272-285, Vienna, Austria, Feb. 2003.
[6] S. Ratnasamy, S. Shenker, and I. Stoica, ``Routing algorithms for DHTs: Some open questions,'' In Proceedings of the 1st International Workshop on Peer-to-Peer Systems, no.LNCS2429, pp.45-52, June. 2002.
[7] S. Waterhousek, JXTA Search: Distributed Search forDistributed Networks, Sun Microsystems, Inc.,
California, 2001.

中辻 真

Makoto NAKATSUJI

日本電信電話株式会社ネットワークサービスシステム研究所．2003 京都大学大学院情報学研究科システム科学専攻修士課程修了．2001 同大工学部情報学科数理工学専攻卒業．

岸 浩史

Hiroshi KISHI

京都大学大学院情報学研究科システム科学専攻修士課程在学中．2002同大工学部情報学科数理工学コース卒業．

河野 浩之

Hiroyuki KAWANO

京都大学大学院情報学研究科システム科学専攻助教授.1990
京都大学大学院工学研究科数理工学専攻博士後期課程. 工
博.IEEE,ACM,電子情報通信学会，情報処理学会など会員.

川原 稔

Minoru KAWAHARA

京都大学学術情報メディアセンター助手．1990 京都大学大学
院工学研究科応用システム科学専攻修士課程修了．博士(情報学)．IEEE，人工知能学会，情報処理学会各会員．

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