自己組織化 P2P ネットワークシステムの構築
2002MT052 森下 広史
指導教員

1 はじめに従来のサーバ・クライアント型の通信に対して，Peerto-Peer(P2P) と呼ばれる通信形態が取り組まれている．
ネットワークを制御するためのアクティブネットワーク(active network) [1][2] を P2P システムに応用することも研究されている．P2P システムにおいて検索効率の維持とトラフィック量の低減を同時に解決する．ユーザの嗜好情報に基づく確率的ルーティングを行うことにより P2P ネットワーク上に類似した嗜好によるグループを形成する．類似した嗜好のグループ内のピアを優先的に扱う．これにより，クエリーのブロードキャストによるトラフィック量を効果的に低減する．

2 P2P とアクティブネットワーク
P2P システムは自律分散のオーバレイネットワークなので，全体的な管理機構が欠如している．そのため検索効率の低さや不安定な構造などの問題点を抱えている．
アクティブノード (active node) によって構成される
アクティブネットワーク [1][2] は，上位オーバレイネッ
トワークを制御するネットワークである．転送されるパケットの操作や制御を行うことができる．従来のネットワークとオーバレイの P2P ネットワークの間にアクティブネットワークを応用することによって，上位のP2P アプリケーションを制御する．
アクティブ仮想ピア (Active Virtual Peer, AVP)[3]が提案されている．P2P システムの制御をアクセス制
御 (access control)，資源管理 (resource management)，オーバレイ負荷制御 (overlay load control)，トポロジ
制御 (topology control) の 4 項目に着目している．この AVP は 3 層の レ イ ヤに よる 階層構 造で 構 成 さ れる．アプリケーション最適化層 (Application Optimization Layer) と，仮想制御キャッシュ (Virtual ControlCache) と，ネットワーク最適化層 (Network Optimization Layer) である．AVP では，特定の P2P アプリケーションに基づかず，特定の P2P コンポーネントも必要としない．また，AVP は遺伝的性能管理フレームワークを提供する．AVP の主な機能は，制御ドメイン(controlled domain)，確率的ルーティング (probabilistic routing)，トポロジ制御 (topology control)，プロトコルのトンネリング (tunneling) である．

3 嗜好情報によるルーティング制御
本研究では， 確率的ルーティング に着目する．確率的ルーティングは，閾値は接続の状態によって決定され，トラフィックを確率的に低減する．ピアの嗜好に基

河野 浩之
づいて，パケットの転送先が類似した嗜好のピアとなるような閾値の調整を行う．ブロードキャストの対象ピアを制限しても，目的のピアにパケットが届く十分な機会が得られる．ピアの嗜好情報は，クエリーの応答を測定することで獲得される．
ルーティングは，送信許可閾値とランダム値の比較によって制限される．式 1 のように送信許可閾値 T は，保証重み W と応答率重み R によって決定する．ピアの接続数を N とする．式 2 のように，ピアの仮想的な接続PP数である接続設定数 NS は N W と N R の和であPPる．また， N W = N R とする．
T =W +R
NS =X

W+N

X

(1)
R

(2)

N

式 3 は，W が各ピアに均等に分配される最低限の重みであることを示す．ピアの応答率を h，正規化した応答率を hn とする．式 4 は，R が各ピアの hn 大きさによって分配する重みであることを示す．式 5 は，T が上限値 L に等しくなる基準の値を基準値 D として示す．
hn が D より大きな場合，T は L より大きな値となる．

W =( NNS )NS=2(N · 2)(3)N

ShNS · hn
R = ( N · N) · (P)=
22hN

(4)

N

D=( NS )2( N2S )L−=L·21−NSN(5)T が上限値 L(= 1) より大きな場合は，W を増加する．また，hn の最大値を M とする．式 6 は，L と Mの関係を示す．これより式 7 は，修正する保証重み Wrを示す．NS は一定なので，W が増加すると，R は減少して，T は修正される．
(NS − N · Wr ) · M + Wr = L(= 1)L − NS · M
Wr =1−N ·M(6)(7)

図 1 のフローチャート図でルーティング制限のアルゴリズムを示す．まず，送信数と最低送信数を比較する．
送信数が最低送信数以下であった場合は，ルーティングを許可する．そうでない場合は，最大の応答率の割合と基準値を比較する．最大応答率割合が基準値以下であった場合は，保証重みは修正せずに応答率重みを分配する．

)( $*+   

グループ内では平均で約 97% であった．図 2 は，ピアが送信するクエリーの送信許可率を示したものである．
優先的に扱うグループを形成するピアに対して送信許可 ( , $*+     (A)     (B)  (   ! "  "   $ *+  # "   $&% '図1

$ ルーティング制限のフローチャート

図2

クエリーの制限による送信許可率率が高いことが分かる．

5 おわりにそうでない場合は，保証重みを修正して応答率重みを分配する．それぞれの場合で，分配された重みから送信許可閾値を決定する．送信許可閾値とランダム値を比較して，確率的にルーティングを許可又は制限する．

4 シミュレーションによる実験
本 研 究 で は ，jnutella *1 で 提 供 さ れ て い る “GTKt(Gnutella Tool Kit)” を用いて実装した．
ここでは，嗜好情報に基づくルーティング制御をシミュレーションにより実験した．PC を 5 台用いてクエリーを送信して提案するルーティング制御の機能を評価した．また，この実験の結果に基づいてピアをグループ化した．各ピア毎にクエリー送信を行った．ここでは各ピアに関して，それぞれのオーバレイネットワークを構成している．メッシュ形状にオーバレイネットワークを構成すると，クエリーの転送によってフラッディングを引き起こしてしまう可能性がある．この実験では，嗜好情報としてキーワードを含むクエリーをランダムに合計5000 回送信した．
トラフィック量の低減は，クエリーの送信を制限することによって達成する．実験では 5 台の PC を用いて実験を行った．あるピアが他の 4 ピアに対して接続しており，仮想的な接続数を 3 としている．よって期待する送信の制限は，0.75 であり約 75% である．ここでは，送信許可率によってクエリーの送信が制限されていることが確認できる．各ピアの平均の送信率は，0.776 である．また，嗜好情報によって形成されているグループ内
では，送信許可率の平均は，0.974 である．よって，クエリー量は平均で約 78% であった．また，優先される*1 jnutella (http://www.jnutella.org) ：Gnutella に関する日本語サイト

本研究では，P2P ネットワークに対してアクティブネットワークに基づいたアプローチを行った．ピアが嗜好に関する情報によってルーティングを制御することを提案した．嗜好情報によってグループ化される P2Pネットワークシステムの自己組織化を実装した．本研
究では，送受信されるクエリーの応答率の割合に応じて重みを分配した．分配された重みに応じた閾値に基づいて，ルーティングの制限を実現した．実験の結果，その効果が有効であることを確認した．
次は，本研究で残った課題である．嗜好情報の学習期間がピアの接続時間に依存する．学習によって重み及び閾値が収束するよりも早くピアが P2P ネットワークから離脱してしまうことが考えられる．動的な嗜好情報の更新や閾値によるルーティング処理のオーバヘッドの問題がある．フラッディングを引き起こしてしまう可能性がある．これは送受信するクエリーの頻度やフォワーディングされるクエリー量に依存する．

参考文献[1] 池田博昌，山本幹，“アクティブネットワーク技術とその応用,” 東京情報大学研究論集，vol.4，no.2・3
合併号，pp.181-194，2001 ．
[2] 若宮直紀，“アクティブネットワークにおける P2P型 情 報 通 信 に 関 す る 研 究,” http://www.taf.or.jp(accessed/publication/kjosei 19/pdf/046.pdf
2005.8)．
[3] Theofrastos Koulouris，Robert Henjes，Kurt
Tutschku，Hermann de Meer，“Implementationof Adaptive Control for P2P Overlays,” IWAN，
Lecture Notes in Computer Science，vol.2982，
pp.292-306，Springer，2004．