論文 / 著書情報
Article / Book Information
論題(和文)

Webコンテンツの偏在性に着目したP2Pコンテンツ流通システム

Title(English)

A System of P2P Contents Distribution Taking Advantage of Uneven
Web Contents Distribution

著者(和文)

高橋昭裕, 小林亜樹, 山岡克式, 横田治夫, 曽根原登Authors(English)

Akihiro Takahashi, Aki KOBAYASHI, Katunori YAMAOKA, Haruo
YOKOTA, Noboru SONEHARA

掲載誌(和文)DEWS2007論文集

Citation(English)

Proceedings of DEWS2007

Vol, no, pages

Vol. , No. , pp. B9-8

発行日 / Pub. date2007, 3

URL

http://search.ieice.org/

権利情報 / Copyright

本著作物の著作権は電子情報通信学会に帰属します。
Copyright (c) 2007 Institute of Electronics, Information andCommunication Engineers.

Powered by T2R2 (Science Tokyo Research Repository)

DEWS2007 B9-8

Web コンテンツの偏在性に着目した P2P コンテンツ流通システム
高橋 昭裕†

小林 亜樹††

山岡 克式†

横田 治夫†

曽根原 登†††† 東京工業大学 〒 152–8552 東京都目黒区大岡山 2–12–1†† (独) メディア教育開発センター 〒 261–0014 千葉県千葉市美浜区若葉 2–12††† 国立情報学研究所 〒 101–8430 東京都千代田区一ツ橋 2–1–2
E-mail: †akihiro@de.cs.titech.ac.jp, ††aki@nime.ac.jp, †yamaoka@ss.titech.ac.jp, †yokota@cs.titech.ac.jp,†††sonehara@nii.ac.jp
あらまし

P2P コンテンツ流通システムにおいて，コンテンツ，クエリの各ピアに投入される意味的なカテゴリのうち，最も優勢なカテゴリの比率を各ピアの優勢度とすると，優勢度は大きいほど効率がよく，また，同じ優勢カテゴ
リを持つピア同士を近くに配置すると効率が良いことを示す．一方，Web コミュニティの研究に見るように，Web サ
イトには優勢カテゴリが明確に存在し，同じ優勢カテゴリを持つサイト間はハイパーリンクで密に繋がっている．このことを利用して， Web リンク情報を用いてピアの優勢度を大きくし，同一優勢カテゴリを持つピア同士を近くに配置する手法を提案する．Web リンク情報を取得するため，協調型 Web アーキテクチャ上のシステムとして試作する．
キーワード P2P, Web とインターネット, オーバレイネットワーク

A System of P2P Contents Distribution
Taking Advantage of Uneven Web Contents Distribution
Akihiro TAKAHASHI† , Aki KOBAYASHI†† , Katunori YAMAOKA† , Haruo YOKOTA† , andNoboru SONEHARA†††† Tokyo Institute of Technology Ookayama 2–12–1, Meguro-ku, Tokyo, 152–8552 Japan†† National Institute of Multimedia Education Wakaba 4–5–6, Mihama-ku, Chiba-shi, Chiba 261–0014 Japan††† National Institute of Informatics Hitotsubashi 2–1–2, Chiyoda-ku, Tokyo, 101–8430 Japan

E-mail: †akihiro@de.cs.titech.ac.jp, ††aki@nime.ac.jp, †yamaoka@ss.titech.ac.jp, †yokota@cs.titech.ac.jp,†††sonehara@nii.ac.jp
Abstract In a peer-to-peer content distribution system, when the contents and queries classiﬁed by the semantic
categories are submitted to a peer, the dominant rate is deﬁned as the largest rate of the category distribution ofeach peer. We show that the higher the dominant rate, the more eﬃcient distribution can be achieved in the system.
It is also showed that the eﬃcient distribution is achieved when the peers which have the same dominant category
were neer one another. There is a dominant category in each web site. As many researches of web community, theweb sites which have a same dominant category were strongly connected by hyperlink. Our proposed system takes
advantage of such uneven distribution of web contents. We propose the peer-to-peer content distribution systemwith the way to enlarging dominant rate of each peer and to put the peers in the neighborhood that have a same
dominant category. A prototype system is built on the cooperative Web architecture.
Key words P2P, Web and the Internet, Overlay Network

1. は じ め に

ワークトポロジを物理トポロジに近づけるような検索用ネット
ワークトポロジ構築手法 [1] [2] [3] [4] [5] [6] [7] である．具体的

ピュア型 P2P コンテンツ配送システムにおける検索用ネッには，ピア間の遅延や帯域幅を計測，または推定し，その値か

トワークトポロジ構築手法は，構築方針によって大きく二つにら実トポロジにおいて近くにあると考えられるピア同士を接分類することが出来る．

続する．これらの手法では，検索効率を維持したまま，実ト

まず一つ目は，実トラヒック抑制を企図して，検索用ネット

ラヒックを抑制することが出来る．特に分散ハッシュテーブル

(DHT:DistributedHashTable) を用いた検索手法 [8] [9] [10] を映像，音声や複合コンテンツに対しては，個々に特徴量の抽出利用するシステムにおいては，これらの手法が用いられる．

手法を開発しなければならないと考えられる．

二つ目は，検索効率の向上を企図して，同種のコンテンツ，クSONs ではピアの保持しているコンテンツを考慮し，コンテ

エリを，検索用ネットワーク上において集中させるような検索用

ンツのカテゴリ別にネットワークを形成する．具体的にはピア

ネットワークトポロジ構築手法 [11] [12] [13] [14] [15] [16] [17] [18]を，保持しているコンテンツの種類を基に，あらかじめ用意さである．これらの手法では，Flooding など，検索開始ピアの，れている意味的なカテゴリに分類する．その上で，ピアが，カ

検索用ネットワークにおける近くの情報を利用する検索アルゴ

テゴリごとにネットワークを形成し，ユーザはコンテンツ，ク

リズムを用いたシステムにおいて，検索成功率の向上や 1 クエ

エリを，同じカテゴリのピアへ投入する．

リあたりのホップ数の低減が可能とされる．

各カテゴリのピア数，コンテンツの種類数が少ない時は非常

その前提として，ピアに投入されるコンテンツ，クエリの内に効率が良い．そのため，流通するコンテンツが明確にカテゴ

容カテゴリに偏りがあることと，この偏在を利用したトポロジ

リに分けられるときは有効な手段といえるが，カテゴリを事前構成によって効率が改善されることが挙げられるが，これらのに用意しておく必要があり，また，各カテゴリに対応する，ピ点の検証は不十分である．

アの数，コンテンツの数が多いと効果が期待できない．

ところで，コンテンツの内容的なカテゴリが偏在することを

2. 2 検索アルゴリズム示す事例として，Web コミュニティに関する研究がある．Web

コンテンツの偏在性と検索効率の実験で用いる検索アルゴリ

グラフにおいて密に結合された Web ページ群を抽出すること

ズムは Flooding [26],RandomWalkSearch [27],NISHA [29] [30]で，互いに関連するページの集合を得る手法として，WWWである．一般には，検索元のピアにおいて，ユーザなどから入の部分グラフから密に結合された Hub と Authority を抽出す力された検索クエリをピアが直接，接続しているピア (以下，

る提案 [19] がなされている．これを応用，発展させた類似ペー

隣接ピア) へ転送し，受け取ったピアがコンテンツを保持してジを探す手法 [20] [21] のほか，Web グラフ中の完全二部グラフ

いれば検索成功，保持していなければさらに隣接ピアへ転送す構造に着目した手法 [22] [23] や，これらの手法を意味的なまとる．これを繰り返すことによって分散環境での検索を行ってい

まりを持った Web ページ群である Web サイトに対して適用する．特に，クエリ転送時における，転送先ピアの選択方法が，ることで，Web コミュニティを抽出する研究 [24] [25] もなされ各検索手法の特徴となる．

ており，互いに関連する Web サイトは Web グラフにおいて近Flooding では，検索の際，ピアは隣接ピアすべてにクエリをくに存在することが示されている．これは，Web におけるグラ転送する．クエリにはクエリループの防止およびネットワーク

フ構造を形成する鍵となるハイパーリンクが，制作者主導で利負荷の低減を目的として，Hops-To-Live（以下，HTL）と呼ば用者の誘導を促す仕組みであることから，グラフ空間上に自然れる値が付与されており，クエリが 1 回転送されるごとに，ピに形成されるものと考えられる．

アにおいて 1 減少させる．ピアは HTL が 0 になるまでクエリ

そこで本論文では，まず，コンテンツ，クエリが属する意味

を転送する．

的なカテゴリの概念を導入し，各ピアに同カテゴリのコンテン

RandomWalkSearch（以下，RWS）では，検索元のピアはツ，クエリの集中する度合，また，同カテゴリのピア同士の接クエリをランダムに選ばれた k 個の隣接ピアへ転送する．ク

続集中度が，検索効率に与える影響について検証する．次に，エリを受け取ったピアは，クエリ送信元以外のピアの中から検索成功率の向上，1 クエリあたりの転送回数の期待値の低減

ランダムに一つのピアを選び，そのピアへクエリを転送する．

を企図して，Web リンク情報を反映させることで，各ピアに特Flooding と同様の理由でにクエリには HTL が付与されている．

定カテゴリのコンテンツ，クエリが集中する利用方式および，

NISHA は，各ピアがその時点でのコンテンツ配置に応じて同カテゴリのコンテンツ，クエリが集まるのピア同士を近くに自律的にコンテンツ間検索オーバレイネットワークを構築する，配置する検索用ネットワーク構築手法を提案する．最後に，提筆者らが提案している検索アルゴリズムである．NISHA では，案手法を実現する試作システムを Perl/CGI により実装を行う．

各ピアが他ピアからコンテンツの位置情報を収集し，保持して2. 関 連 研 究
2. 1 検索用ネットワークトポロジの構築手法
検索効率向上を企図して，同種のコンテンツ，クエリを，検いるコンテンツにその情報を保持させることによって，検索用コンテンツ間グラフを分散構築，分散管理する．

3. コンテンツ偏在性と検索効率

索用ネットワーク上において近くに集中させるような手法であ

意味的なカテゴリを考えたとき，コンテンツ，クエリはカテ

る TellaGate [11] と Semantic Overlay Networks(SONs) [12]ゴリに属するものとすると，ピアネットワークにおける，同じについて述べる．

カテゴリのコンテンツ，クエリの集中度合いが検索効率に与え

TellaGate は, コンテンツ発見率を維持した状態でのネットる影響を，理論解析，およびシミュレーションを用いて検証す

ワークの通信負荷抑制を企図して，ピアに投入されるコンテン

る．実験では，検索手法として Flooding，RWS，NISHA を使ツ，クエリの内容からピアの嗜好を定義し，嗜好が類似したピ

用した．

ア同士をピアネットワーク上で近くになるよう動的に再配置す

本論文では，ピアに投入されるコンテンツ，クエリのカテゴる手法である．TellaGate では，対象をテキストコンテンツとリ分布をそれぞれコンテンツ分布，クエリ分布と呼ぶ．一つのしているため，自然言語処理を用いて嗜好を決定しているが，ピアに対応するコンテンツ分布，クエリ分布が同じである場合，

シミュレーション設定

ࠞ࠹ࠧ࡝ߩഀว=?

表1

優勢度 rprime

20-100%

同カテゴリピア接続率 rconn

20-100%コンテンツ ID Scon

[0–999](1000 種類)

カテゴリ Scat[A–E](5 種類)

各ピアのコンテンツ数 Spc

10

ピア平均次数 Spd

4

ઁࠞ࠹ࠧ࡝

㪈㪇㪇
㪏㪇
㪍㪇
㪋㪇

ఝ൓ࠞ࠹ࠧ࡝

㪉㪇
㪇

㪉㪇

㪋㪇

㪍㪇

ఝ൓ᐲ rprime =?

㪏㪇

㪈㪇㪇

図 2 優勢度によるカテゴリ分布の変化

ᩮ

ࠢࠛ࡝ᛩ౉

N all1=3


EQPPGEVKQP4CVG rconn

ઁࠞ࠹ࠧ࡝

⥄ࠞ࠹ࠧ࡝

R m0

d=0
d=1

R m1

R o1

d=2

R m2

R o2



N all2=6
図1 トポロジ

図 3 Flooding の探索範囲

単にピアのカテゴリ分布と呼ぶ．それぞれのカテゴリ分布において最も大きな割合を占めるカテゴリを優勢カテゴリ，またそ

3. 1. 1 Flooding の理論解析の割合を優勢度とする．優勢度が大きい時，ピアに同カテゴリ

検索成功確率 Rf (rprime ) を求める．Flooding の探索範囲は
クエリのループを考えないとき，図 3 のように，投入されたピのコンテンツ，クエリが集中していることを表す．

アを根とする木構造となる．

3. 1 実 験 内 容

根のカテゴリを自カテゴリ，他のカテゴリをまとめて，他カ

カテゴリの種類数を Scat とした時，優勢度 rprime (1/Scat <rprime <= 1) と，同カテゴリのコンテンツ，クエリが集まるピ

テゴリとするとき，Rf (rprime ) は，自カテゴリに属するコンテ

ア同士が接続されている確率である，同カテゴリピア接続率
rconn (1/Scat < rconn <= 1) を変数とし，検索成功率，および 1

探索成功率 Rdf o とすると，クエリに対するホップ数の期待値を調べ，その値の変化状況などについて検証する．本論文では検索効率を効率性とし(効率性) =

(検索成功率)(1 クエリあたりのホップ数の期待値)

ンツの探索成功率 Rdf m と，他カテゴリに属するコンテンツのRf (rprime ) = rprime Rdf m + (1 − rprime )Rdf o(2)と書ける．それぞれの探索成功率は，各カテゴリに属するコン(1)

テンツが探索範囲内にいくつ入っているかを調べることができれば求める事ができる．すなわち，自カテゴリコンテンツが探とする．

Flooding,RWS は理論解析を用い，NISHA ではシミュレー
ションを行った．理論解析およびシミュレーション共通の設定

索範囲内に n 個あるとすると，自カテゴリのコンテンツを発見できる確率 Rdf m (n) は

Nam = Scon /Scatは表に示す通りである．
トポロジの構成において，それぞれのピアは Scat = 5 種類のカテゴリ A–E のいずれかに属し，トポロジは各ピアが平均

Rdf m (n) = 1 −{Nam − 1
Nam

}n

(3)
(4)

次数に相当するピアと接続されるようにする．このとき，同カと表せる．Nam は自カテゴリに属するコンテンツの種類数でテゴリピアとの接続数は同カテゴリピア接続率 rconn によってある．

決める．図 1 のように，同カテゴリピア接続率 rconn が大きい

同様に，探索範囲内の他カテゴリコンテンツ数を n とするとと同カテゴリのピア同士が近くに集まるようになる．逆に同カ

Nao = (Scon /Scat )(Scat − 1)

テゴリピア接続率が小さい時はランダムなグラフとなる．
各コンテンツはコンテンツ ID を持っており，0–999 まで

Rdf o (n) = 1 −{Nao − 1
Nao

}n

(5)
(6)

Scon = 1000 種類のコンテンツ ID が存在するものとする．コとなる．Nao は他カテゴリに属するコンテンツの種類数である．

ンテンツ ID が等しいコンテンツは同一コンテンツである．ま

探索範囲内のコンテンツ数の期待値を求めるため，各ピアのた，各コンテンツはそれぞれいずれか 1 つのカテゴリに属してコンテンツ数の期待値を求める．探索範囲内の自カテゴリコン

いるものとする．

テンツ数の期待値 Ndf m および他カテゴリコンテンツ数の期待

各カテゴリのコンテンツ数は均等に，各カテゴリ 200 種類と値 Ndf o は，根からの距離 d のピア数を Ndall ，根からの距離 d

し，各ピアにコンテンツを 10 個配置する．コンテンツを配置のあるピアに存在する自カテゴリのコンテンツ数の期待値をする際，ピアのカテゴリと同カテゴリのコンテンツを配置する

Ndf mc ，他カテゴリのコンテンツ数の期待値を Ndf oc とすると，確率は優勢度 rprime によって定める．カテゴリ数を 5 とした{∑dNiall Nif mc∑di=0 allf oc

ため，図 2 に示すように，優勢度 20% がコンテンツ，クエリ

Ndf m =とも，ランダムに投入される状態を表す．逆に，優勢度 100%

Ndf o =

はコンテンツ，クエリとも，完全にピアのカテゴリに則した状
態である．

i=0

Ni Ni

と書く事ができる．
一方，根からの距離 d のピア数 Ndall は

(7)

表2

ピア

ピアにあるコンテンツ数の期待値

3. 1. 2 RWS の理論解析

コンテンツ

RWS を行う根からの距離が d までの自カテゴリに属するあ

自カテゴリ 他カテゴリ

るコンテンツの探索成功率 Rdrm と他カテゴリに属するあるコ

自カテゴリ

m
Pmc

m
Poc

他カテゴリ

o
Pmc

o
Poc

N0all = 1
Ndall = Spd (Spd − 1)(d−1)

ンテンツの探索成功率 Rdro は，{Ndro =

(8)

(d >
= 1)

{

である．

Ndf mc ，Ndf oc は，ピアに存在するコンテンツ数の期待値を表∑i=d f mc
Ni
i=0
∑i=d
f oc

Ndrm =

i=0{ Nam −1 }Ndrm
Nam
{ Nao
} ro
−1 Nd

Rdrm = 1 −Rdro = 1 −

{

(19)

Nao

2 の様に表すとし，根からの距離 d のピアが自カテゴリである
確率を Rdm ，および他カテゴリである確率を Rdo とすると，

(18)

Ni

となる．探索する深さを Dr とすると，Flooding とほぼ同様に，根からの距離が d の，あるノードを根とした部分検索木のom
Rdo
Rdm + Pmc
Ndf mc = Pmc

(9)

o
m m
Rdo
Rd + Poc
Ndf oc = Poc

自カテゴリクエリのホップ数の期待値 Ndrsm ，他カテゴリクエ
リのホップ数の期待値 Ndrso は，帰納的に，mmooとなる．Pmc
，Poc
，Pmc
，Poc
はそれぞれ


m

= Spc rprime
Pmc



m
 Poc
= Spc (1 − rprime )

sm
so
ND
r = 0, ND r = 0{1−rprimeoPmc= Spc Scat
−1



{
}

1−rprimeo Poc= Spc rprime +(Scat − 2)

(10)

sm
Ndrsm = (Nd+1+ 1)(1 − Rdf mc )so
Ndrso = (Nd+1+ 1)(1 − Rdf oc )

(20)

r
(0 <
= d < D ) (21)Scat −1となる．

である．
最後に根からの距離 d のピアが自カテゴリである確率 Rdm ，他カテゴリである確率 Rdo は，帰納的に，

3. 1. 3 NISHA のシミュレーション
NISHA は理論解析を行うことが難しいため，シミュレーショ


Rmm = rconn
ンによる解析を行った．ピア数は 200，各カテゴリに属するピ
Rom = (1 − rconn )/(Scat − 1)

(1−rconn )(Scat −2)

クス構築のための情報交換は隣接ピアとのみ行う．全ピアからアの数は等分し，各 40 とした．NISHA における検索インデッ

Rmo = 1 − rconn

Roo = rconn +(11)

全コンテンツを検索し，自カテゴリに属するコンテンツの探索

Scat −1

成功率 Rf m と，他カテゴリに属するコンテンツの探索成功率

R0m = 1, R0o = 0

{

(12)

m
o
Rdm = Rd−1
Rmm + Rd−1
Rommo
Rdo = Rd−1
Rmo + Rd−1
Roo

(d >
= 1)

(13)

Rf o を求め，検索成功率 Rn (rprime ) を，Rn (rprime ) = rprime Rf m + (1 − rprime )Rf o(22)

として求めた．1 クエリあたりのホップ数の期待値も，同様に

となる．

求めた．

次にクエリホップ数の期待値を考える．ルートからの距離 d

3. 2 結果の，あるピアで，ある自カテゴリコンテンツが発見できる確率

Flooding の実験結果を図 4–6 に示す．結果のグラフは各を Rdf mc ，ある他カテゴリコンテンツが発見できる確率 Rdf oc ，

アルゴリズムにおいてほぼ同様の傾向を示した．次に，図探索する深さ，すなわち HTL の値を D としたとき，根からの7–9 はそれぞれ，検索成功率，ステップ数，効率性のグラフを距離が d の，あるノードを根とした部分検索木の自カテゴリク

rconn = rprime の平面で切ったときのグラフである．nishaRan-

エリのホップ数の期待値 Ndsm ，他カテゴリクエリのホップ数のdom の直線は各メトリックで (rprime , rconn ) = (20%, 20%) の

期待値 Ndso は，帰納的に，

とき，すなわち，トポロジ，コンテンツ配置，クエリがすべて

sm
so
ND
= 0, ND
=0

{
{

(14)

優勢度 rprime ，同カテゴリ接続率 rconn がともに大きいとき，
f mc
Ndsm = (Spd −1)(Ndsm)+1 +1)(1−Rdso
Ndso = (Spd −1)(Nd+1+1)(1−Rdf oc )N0sm = Spd (N1sm + 1)(1 − R1f mc )N0so = Spd (N1so + 1)(1 − R1f oc )(0 < d < D) (15)

Rdf mc = 1 −Rdf oc = 1 −

である．

{N

am −1
Nam

3. 2. 1 Flooding の考察(16)

検索成功率は優勢度，同カテゴリピア接続率を大きくすることによって，非常に良くなる．これは図 10 のように両パラメ
タが大きいときに同カテゴリが集中している場所と，Flooding}N f mc

による探索範囲が，ほぼ同一であるためである．

d{ Nao −1 }N f oc
dNao

検索効率は良くなることがわかる．
次に各アルゴリズムについて個別に考察する．

と書ける．ただし，Rdf mc ，Rdf oc は{

ランダムの時の値である．すべての検索アルゴリズムにおいて，(17)

一方，クエリホップ数の期待値はよくならなかった．これは，ピアの近くでコンテンツを発見できても，他のルートを通っているクエリは探索を続けるためである．図 5 において，優勢度

0.7

successRate[%]
0.6
0.55
0.45
0.35
0.25
0.15

r

Flooding
rws
nisha
nishaRandom

100
90
80
70
60
50
100
conn[%] 40
80 90
30
60 70
20 20 30 40 50
prime[%]

successRate[%]

0.6
0.5
0.4
0.3
0.2
0.1
20

30

40

50

60

70

80

90

100

90

100

90

100

rconn,rprime[%]r

図 7 検索成功率:接続率＝優勢度
図 4 Flooding:検索成功率

16

step

14

15.8
15.6
15.4
15.2
15
14.8
14.6

12

step

10

Flooding
rws
nisha
nishaRandom

8
6

100
90
80
70
60
50
40
conn[%] 3020

r

4
2
20

30

r

図8
0.35

図 5 Flooding:1 クエリあたりのホップ数

0.3

successRate/step

successRate/step
0.04
0.035
0.03
0.025
0.02
0.015
0.01
0.005

r

100
90
80
70
60
50
40
conn[%] 3020

40

50

60

70

80

rconn,rprime[%]

100
80 90
60 70
40 50
30
20
prime[%]

ホップ数:接続率=優勢度

Flooding
rws
nisha
nishaRandom

0.25
0.2
0.15
0.1
0.05
0
20

80 90
60 70
40 50
30
20
prime[%]

30

図 6 Flooding:効率性

50

60

70

80

rconn,rprime[%]

100

r

40

図 9 効率性:接続率＝優勢度

㪝㫃㫆㫆㪻㫀㫅㪾

ห䉦䊁䉯䊥䈱䊏䉝䈏㓸䉁䉎▸࿐

rprime が大きくなるにつれて，全体的に値が下がっているのは，クエリが投入されたピアで探索を終了する確率が高くなるため

㪩㪮㪪

である．

3. 2. 2 RWS の考察ᬌ⚝䉕㐿ᆎ䈜䉎䊏䉝

優勢度，同カテゴリピア接続率が極端に大きくないと Flood-ing に比べ検索成功率は低い．これは RWS による探索範囲が

図 10 検索範囲の概念図

Flooding のように，自カテゴリピアが集中する近傍から探索る．このグラフにおいて，同カテゴリピア接続率 rconn が高くするのではなく，図 10 に見るように，模式的に遠くまで調べなると検索成功率が悪くなっている．これに対する明確な理由

るためである．同カテゴリピア接続率 rconn が 100 になると値はわかっていないが，隣接ピア同士が共通の隣接ピアを持つこが高くなるのは，どこまで遠くに行っても自カテゴリピアにしとが多くなるからではないかと考えられる．例えば，優勢度がか到達しないためである．

20% のとき，コンテンツのカテゴリ分布はすべてのピアにおい

図 8 を見ると，クエリホップ数の期待値は Flooding に比べ，て同じであるため，rconn が大きくなるにつれ検索成功率が悪よくなっている．これは，RWS のクエリが 1 本のルートしかくなる原因はトポロジにあると考えられる．ここで同カテゴリ通らないため，ルートの途中で検索が成功すれば，以降クエリ

ピア接続率が 100% の時を考えると，図 1 の最右図のように，が転送がされなくなり，検索成功率が上がれば，クエリがルー

それぞれカテゴリのピア同士のみで繋がる 5 つのネットワーク

トの途中で止まる可能性が高くなるためである．

に分割される．このとき，各ネットワークのピア数は 40 しか3. 2. 3 NISHA の考察

なく，ピアの平均次数が 4 であるので，例えば，図 12 のよう

図 11 は，rrate = 20(%) の時の NISHA の検索成功率であに隣接するピア同士が共通する隣接ピアを一つ以上持っているsuccessRate[%]

0.44
0.42
0.4
0.38
0.36
0.34
0.32
0.3
0.28
0.26
NISHA
0.24 NISHARandom
0.22
20
30
40
50

䉺䉫

䊡䊷䉱

図 13
60

70

80

90

従来の P2P

図 14

ᬌ⚝⚿ᨐ߆ࠄ࠲ࠣ
9GDࠨࠗ࠻ߩࠕ࠼࡟ࠬ
ࠍขᓧ‫ޕ‬

図 11 NISHA 検索成功率:優勢度=20%䊡䊷䉱䈏䉮䊮䊁䊮䉿䇮䉪䉣䊥䈱ౝኈ䈮䉋䈦䈩
ᛩ౉䈜䉎䊏䉝䉕ㆬᛯ৻ੱ䈱䊡䊷䉱㩷䈲
৻䈧䈱䊏䉝䈮
䉮䊮䊁䊮䉿䇮䉪䉣䊥䉕ᛩ౉ࠦࡦ࠹ࡦ࠷‫ߩ࡝ࠛࠢޔ‬
ౝኈࠍᬌ⚝

100

rconn [% ]䉮䊮䊁䊮䉿䇮䉪䉣䊥ᛩ౉䊏䉝䉮䊮䊁䊮䉿䇮䉪䉣䊥ᛩ౉䊏䉝౒ㅢߩ㓞ធࡇࠕ
࠲ࠣߩߟ޿ߚࡇࠕߦ
ࠦࡦ࠹ࡦ࠷‫ࠍ࡝ࠛࠢޔ‬ᛩ౉

提案手法の P2Pᬌ⚝ࠨࠗ࠻

JVVRYYYCCCEQODDD
JVVRYYYEEEEQOFFF
JVVRYYYGGGEQOHHH㪮㪼㪹䉰䉟䊃䊏䉝JVVRYYYCCCEQODDD

㓞ធࡇࠕ
図 15
図 12

コンテンツ，クエリ投入方法の例

共通する隣接ピアを持っている状態のタグとする．また，タグの示すカテゴリが類似するピア同士
確率 R(n) は，ネットワークに存在するピアの数を n とするとR(n) =(n − 2) × n−3 C2 × n−3 C2
9=n−2
n−2 C3 × n−2 C3(23)を接続することにより，同種のコンテンツがネットワーク上において近くになるようにする．
本提案モデルでは，利用者の手元にある端末をピアとするよとなり，n = 200 すなわち，同カテゴリピア接続率 rconn = 20%

りもむしろ，Web サーバのような常時稼働するサーバをピアとのとき R(200) = 0.045 なのに対し，n = 40 すなわち，同カテ

しても機能させることを志向している．このような形態では，

ゴリピア接続率 rconn = 100% のとき R(40) = 0.238 と非常にピアの安定性などでは優れるが，コンテンツの最終配送がボト大きくなる．NISHA において検索インデックスを作成する際，ルネックとなる可能性が指摘される．しかし，現在のコンテン

各ピアは必要のないコンテンツの参照を他ピアに送る．このとツ配信の主流である Web においては，それぞれのユーザにとっき，隣接するピアが同じ情報を収集するのは効率が悪いと考えて十分なアクセス速度を提供できるサーバが相当数あることをられる．

前提としているため，これは問題とならない．

また，クエリホップ数の期待値は同カテゴリピア接続率が60% を越えたあたりから良くなる．

4. 提 案 手 法

4. 2 提 案 手 法
Web サイトは 1. 章で述べたとおり，ハイパーリンクによって同種の Web サイトとつながっており，Web コミュニティを形成している．したがって，Web サイトが示すカテゴリは Web サ

3. 章では優勢カテゴリが同じピアを近くに配置し，さらに，

イト自体の内容と，そのサイトからハイパーリンクによって繋ピアの優勢度を大きくすることで，検索効率が向上する事を示がっている他の Web サイトから特徴付けられると考えられる．

した．すなわち，ある検索意図（クエリ）およびコンテンツへ

そこで，本論文ではまず，以下の二つの理由からピアと Webの適合度が高いコンテンツ群をクエリ，コンテンツのカテゴリ

サイトを関連付け，ピアに関連付けられた Web サイトと同種とし，2 つのカテゴリが類似しているときそのクエリ，コンテのコンテンツ，クエリを集めることにする．

ンツは同種であるとすると，ネットワーク上において同種コン

まず，一つ目の理由は，既存の Web サイトは多様であるた

テンツ同士を近くに配置し，同種のコンテンツが集まる場所かめである．Web サイトの集合である WWW は分散型のデータ

ら検索を始めることで効率的な検索ができる．そこで本章では，ベースとみなすことが出来，内容は非常に多種にわたる．また，

3. 章の実験結果を基に，効率的な検索を行うことができるモデ本方式では目的としていないが，WWW は単一障害点を持た

ル，および実現手法を提案する．

ず，ピュア型 P2P の利点である可用性を損なわないという利

4. 1 提案モデル

点もある．

従来の P2P コンテンツ配送システムでは図 13 のように 1 人

二つ目は，コンテンツ，クエリのカテゴリに類似するカテゴのユーザに対して 1 つのピアを割り当て，ユーザは 1 つのピアリを示す Web サイトを発見することは，容易であると考えらに対してコンテンツ，クエリを投入するが，各ユーザが，コンれるためである．なぜなら，既存のサーチエンジンはコンテン

テンツ，クエリの内容に応じて，投入するピアを選ぶことが出

ツ，クエリのカテゴリと類似したカテゴリを示す Web サイト

来れば，各ピアに投入されるコンテンツ，クエリの内容の分布を発見するには十分な精度を持っているからである．

は，多くの P2P システムに比べ，さらに大きな偏りを作るこ

例えば，図 15 のようにコンテンツ，クエリの内容，もしくとが出来る．そこで，提案モデルではまず，利用者が検索を始

はコンテンツの名前などを用いて Web サーチエンジンで Web

める場所を指定することができるよう，図 14 のように利用者

サイトを検索し，検索結果として表示されるサイトに対応付け

がどのピアでも使えるようにする．ここで，利用者がクエリおられたピアにコンテンツ，クエリを投入すればよい．

よびコンテンツと同種のコンテンツが集まる場所に投入できる

次に，Web リンクの情報を利用し，同種のコンテンツを保持よう，ピアにカテゴリを示す情報を付加する．この情報をピアするピア同士を近くに配置するピアネットワーク構築手法を提ࠦࡦ࠹ࡦ࠷ߩㅍା

ࡇࠕ22ᬌ⚝㧘㈩ㅍࡕࠫࡘ࡯࡞
ࠦࡦ࠹ࡦ࠷㈩ㅍᯏ᭴

ࠢࠛ࡝ߩฃା

ࠦࡦ࠹ࡦ࠷ߩฃା

㓞ធࠨ࡯ࡃ࡝ࠬ࠻ࠢࠛ࡝ಣℂᯏ᭴ ᬌ⚝ᚻᴺࠢࠛ࡝ߩㅍା

X#95ࡕࠫࡘ࡯࡞

9GD࡝ࡦࠢ

9GD࡝ࡦࠢᖱႎࠍ
⛽ᜬߔࠆߚ߼ߩ
ㅢା

9GDࠨࠗ࠻

9GD࡝ࡦࠢᖱႎ
9GDࠨࠗ࠻
▤ℂᯏ᭴

9GD࡝ࡦࠢᖱႎ
#95#95%QPVGPV%QPVGPV%QPVGPV%QPVGPVࠝ࡯ࡃ࡟ࠗࡀ࠶࠻ࡢ࡯ࠢ᭴▽%QPVGPV%QPVGPV%QPVGPV%QPVGPV%QPVGPV#95

図 16

オーバレイネットワーク構築
図 17

ブロック図

案する．
各ピアは Web サイトのカテゴリと類似するカテゴリを持つコンテンツを保持しているものとすると，1. 章で述べたとおり，た手法を用いる．

5. 1 vAWS モジュール

内容の類似する Web サイト同士はハイパーリンクによって密CWA では，Web サーバが自身の保持するコンテンツの更新に繋がっているため，図 16 のように，Web グラフに倣って構を確実に検知できる特性を利用して，Web サーバの付加機能

築することで，同種のコンテンツを保持するピア同士を近くにとしてサーバ内 HTML コンテンツの Web グラフ構築，なら

配置することが出来る．

びに管理を行う．同時に各 Web サーバが近隣の最新の Web グ

そこで本論文では，Web リンクからピアネットワークを構築

ラフ（以下，部分 Web グラフ）を保持することが出来るよう，する簡単な手法の一つとして，ピア間の Web リンクが多いピ

近傍コンテンツの更新時に当該コンテンツを保持するサーバ

ア同士を接続することでピアネットワークを構築する．ここでからの通知，およびリンク情報の提供を受ける仕組みを導入す

言うピアの Web リンクとはピアに関連付けた Web サイトのる．このような付加機能を導入した Web サーバのことを AWS

Web リンクのことである．

（AdvancedWebServer) と呼んでおり，アクセスした利用者に具体的に，次に示すアルゴリズムによる自律分散なピアネッ
トワーク構築手法を提案する．ピアが他ピアとの接続する際，対してコンテンツだけでなく，部分 Web グラフ情報を提供することが出来る．

ピアは接続要求を行い，相手のピアが接続を許可すると，ピア

CWA の理念としては，付加機能は完全に Web サーバと一体同士が接続した状態になる．まず，接続要求を行おうとしていで動作すべきだが，ここでは導入の容易さなどから CGI によるるピアを自ピアとすると，Web リンクにおける隣接ピアを自ピ実装とし，これを virtualAWS（以下，vAWS) と呼ぶ．vAWS

アとの Web リンク数が多い順に並べる．次にピアとしての接モジュールはサーバの持つ HTML コンテンツから周囲 n ホッ

続要求をその順番で行い，自ピアが接続要求を出した先のピア

プの Web リンク情報を維持，管理するモジュールであり，ディとの Web リンク数の累計を Nsum ，自ピアの総 Web リンク数
を Nall ，パラメタを p(0 <=p<= 1) とした時，レクトリ単位で Web リンク情報を管理できるようになっていNsum /Nall > p(24)となるまで接続要求を行う．また，接続要求を受けたピアは，
ピアネットワークに参加できないピアが出ないよう，必ず接続を許可する．

5. 実装システム
ピアと Web サイトを結びつけるための簡単な手法として，ピアの機能を CGI/Perl で実装し，Web サイトに付加する形で利用できるようにする．提案方式はオーバレイネットワーク構
築時に Web リンク情報を取得する必要がある．筆者らは，周辺リンク情報を容易に取得できるようにする協調型 Web アー
キテクチャ [31]（Cooperative Web Architecture; 以下 CWA）
を提案している．
そこで，試作システムは図 17 のように，CWA を実現する

vAWS モジュールと P2P 検索，配送モジュールから構成する．
CWA は P2P 系とは独立に既存の Web に追加される形で機能し，周辺リンク情報を他の Web サーバと協調して維持，管理する機能を持つ．

vAWS により Web グラフを保持し，この情報から，P2P コる．また，筆者らは Web リンク情報の同期方式 [32] を提案しているが，本システムでは基礎的な方式を用いた．

5. 2 P2P 検索，配送モジュール
P2P 検索，配送モジュールは，ユーザからのクエリを受け，他ピアと協調動作することで，コンテンツを検索，配送するモジュールであり，次の三つの機能を有する．

• vAWS が保持している Web リンク情報から他ピアを発見し，接続要求を出す• ユーザもしくは他ピアからのクエリを受信した時にコンテンツの返送，もしくは検索アルゴリズムに応じて適切なピアへクエリを転送する• コンテンツを検索ルートに沿って配送する
5. 3 考察本実装システムは，DEWS2006 デモセッションにおいて用意した数台の PC を接続した動作デモを行い，数 10query/s 程
度の処理が可能であることなどを示した．本システムの現実のWeb 空間における効率性や負荷の検証は今後の課題である．しかしながら，3. 章の結果と Web コミュニティの研究成果を考慮すると，ある程度のカテゴリに関する偏在性は実現可能であり，かつまた，その場合に相応の検索効率の向上が期待できる．

6. お わ り にンテンツ配送システムが関連付けられた Web サイトと密に接続されている Web サイトを見つけることによって，内容の類似する Web サイトを発見する．具体的な手法は 4. 2 節で述べ

本論文では，まず，P2P コンテンツ配送システムにおいて，優勢度および，同カテゴリピア接続率の変化による検索効率に

ついて分析を行い，優勢度および，同カテゴリピア接続率がともに大きい時に検索効率が良くなることを明らかにした．
次に，優勢度および，同カテゴリピア接続率が大きくなるよ[12]う，ピアと Web サイトを関連付け，ユーザがコンテンツ，クエ
リの内容に対応する Web サイトに関連付けられたピアへ投入[13]する手法と，意味的に同じカテゴリに属する Web サイト同士
が Web リンクによって密に繋がっている事を利用し，Web リ[14]

ンク情報に倣ってピアネットワークを構築することで，類似するピア同士をネットワークにおいて近くに配置する手法を提案した．また，実システムによる性能評価は行っていないが，3.

[15]

章の実験より，明確なカテゴリ分類がされていない提案手法においても検索効率の向上が期待できる．

[16]

最後に，Perl/CGI を用いて Web リンク情報に倣ってピア
ネットワークを構築する P2P コンテンツ配送システムの実装を行った．
今後の課題として，トポロジ構築アルゴリズムの改善や，本[17]

論文では対象外とした，コンテンツ配置法などが挙げられる．
本提案は，Web におけるコンテンツ流通モデルを考慮した[18]

とき，ピアの機能をサーバ側に持たせ，利用者の嗜好毎に接続するピアを検索エンジンなどを用いて選択させることが，3. 章
での検証によって合理的であるとの発想に基づく．また，Web[19]

コミュニティの研究を踏まえた上で，Web リンク情報を利用したトポロジ構成法を提案し，容易に導入可能な実装システム[20]として実現することで，実システムへの導入を今後進めていき
たい．

[21]

文

献

[1] Miguel Castro, Peter Drushel, Y.C. Hu, and Antony Rowstron: “Exploiting Network Proximity in Peer-to-peer Networks. Technical Report,” MSR-TR-2002-82, Microsoft Research, 2002.
[2] Kirsten Hildrum, John D. Kubiatowicz, Satish Rao, and
Ben Y. Zhao: “Distributed Object Location in a Dynamic
Environment,” In Proc. of the ACM SPAA, 2002.
[3] Sushant Jain, Ratul Mahajan, and David Wetherall: “A
Study of Performance Potential of DHT-based Overlays,”
In Proc. of the 4th USITS, 2003.
[4] David R. Karger and Matthias Ruhl: “Finding Nearest
Neighbours in Growth-restricted Metrics,” In Proc. of the
ACM STOC, 2002.
[5] Sylvia Ratnasamy, Mark Handley, Richard Karp, and Scott
Shenker: “Topologically-Aware Overlay Construction andServer Selection,” In Proc. of the INFOCOMM, 2002.
[6] Ben Y. Zhao, Anthony Joseph, and John D.Kubiatowicz:“Locality Aware Mechanisms for Large-scale Networks,” In
Proc. of the FuDiCo 02, 2002.
[7] 阿武孝文, 朝香卓也, 高橋達郎: “Unstructured 型 P2P ネット
ワークにおける検索メッセージ転送方式,” 電子情報通信学会論
文誌，vol.J88-B, no.2, pp.372-382, 2005.
[8] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard
Karp, and Scott Shenker: “A Scalable Content-Addressable
Network,” In Proc. of the ACM SIGCOMM 2001, 2001.
[9] Ion Stoica, Robert Morris, David Karger, Frans Kaashoek,
and Hari Balakrishnan: “Chord: A Scalable Peer-to-peer
Lookup Service for Internet Applications,” In Proc. of the
ACM SIGCOMM 2001, 2001.
[10] A.Rowstron and P.Druschel: “Pastry : Scalable, decentralized object location and routing for large-scale peer-to-peer
systems,” Middleware, 2001.
[11] K.Kojima: “Self-Organizable P2P Search Engine for Knowl-

[22]

[23]
[24]
[25]

[26]

[27]
[28]

[29]

[30]

[31]

[32]

edge Management,” the ﬁrst International Workshop on
Peer-to-Peer Knowledge Management, 2004.
A. Crespo and H. Garcia-Molina: “Semantic overlay networks for p2p systems,” Technical report, Computer Science
Department, Stanford University, 2002.
H. Zhang, A. Goel, and R. Govindan: “Using the SmallWorld Model to Improve Freenet Performance,” In Proc. ofIEEE Infocom, 2002.
V. Kalogeraki, D. Gunopulos, and D. Zeinalipour-Yazti:“A Local Search Mechanism for Peer-to-Peer Networks,”
In Proc. of the Eleventh International Conference on Information and Knowledge Management, pp. 300-307, 2002.
S. Joseph: “NeuroGrid: Semantically Routing Queries inPeer-to-Peer Networks,” In Proc. of the International Workshop on Peerto-Peer Computing, 2002.
P. Haase, R. Siebes, and F. van Harmelen: “Peer Selection in Peer-to-Peer Networks with Semantic Topologies,”
In Proc. of the International Conference on Semantics in
Networked World (ICNSW 04), volume 3226 of LNCS, pp.
108-125, 2004.
Ka Cheung Sia. P2P information retrieval: “A selforganizing paradigm,” Technical report, 2002.
Tsunenori Mine, Daisuke Matsuno, Akihiro Kogo, Makoto
Amamiya: “Design and Implementation of Agent Community Based Peer-to-Peer Information Retrieval Method,”CIA 2004, pp.31-46, 2004.
Jon M. Kleinberg: “Authoritative sources in a hyperlinked
environment,” In Proc. of the ninth annual ACM-SIAM
symposium on Discrete algorithms, p.668-677, 1998.
Jeﬀrey Dean and Monika R. Henzinger: “Finding related
pages in the World Wide Web,” In Proc. of the 8th WWW
Conference, 1999.
豊田正史: “WWW における関連コミュニティ群の発見,” 情処
研報 DBS122-40, IPSJ, 2000.
R. Kumar, P. Raghavan, S. Rajagopalan and A.Tomkins,“Trawling the web for emerging cybercommunities,” In
Proc. of the 8th WWW Conference, 1999.
村田剛志: “参照の共起性に基づく Web コミュニティの発見,”
人工知能学会誌、Vol.16 No.3, pp.316-323, 2001.
原田昌紀, 風間一洋, 佐藤進也: “参照共起分析の Web ディレク
トリへの適用,” IPSJ 研究報告 NL-142-007, 2001.
浅野泰仁、吉田雄介、西関隆夫、豊田正史、喜連川優：“サイト間グラフの最小カットを用いたウェブ上のコミュニティ発見法,”
アルゴリズム研究会 情処研報, AL-095-8, pp.51-58, 2004.
Gnutella. The Gnutella Protocol Speciﬁcation:
www9.limewire.com/developer/gnutella protocol 0.4.pdf,
2004.
Qin Lv et al: “Search and Replication in Unstructured Peerto-Peer Networks,” In Proc. of the 16th ACM ICS, 2002.
N. Bisnik and A. Abouzeid: “Modeling and Analysis of Random Walk Search Algorithms in P2P Networks,” to appear
in HOT-P2P 2005, 2005.
スレスタサンブ, 小林亜樹, 山岡克式, 酒井善則 : “CDN における近傍ノードのコンテンツによる検索木の分散構成に基づく効率的コンテンツ検索手法,” 情処研報 DBS-137-28, pp.207-214,
2005.
Shambhu Shrestha, Aki Kobayashi, Yoshinori Sakai, Katsunori Yamaoka, Noboru Sonehara: “Eﬃcient Content Location Algorithm for Content Destribution Networks basedon Distributed Construction of Search Tree from Contenttsof Proximal Nodes,” In Proc. of IASTED DBA2006, pp.101108, 2006.
Kobayashi Aki, Yamaoka Katsunori, Sakai Yoshinori : “Cooperative Web Architecture for Search and Navigation Assistance,” In Proc. of ICWI2002, IADIS, 2002.
高砂幸代、小林亜樹、山岡克式、酒井善則: “Web サーバ間での部分 Web グラフ同期方式の提案,” DEWS2006 7C-o2, 2006.