2010
年度秋学期 修士論文中間発表構造化 P2P オーバーレイネットワークにおける データの属性による区分を用いた高速データ展開
Fast Data Dissemination for Structured Peer-to-Peer Overlay Network with Division by Data Attributes
黒宮 佑介（学籍番号： 80924567 ） 政策・メディア研究科 修士課程 2 年
主査：村井 純、副査：斉藤 賢爾・中村 修・江崎
浩
研究概要
• P2P オーバーレイネットワークの発展
–
誰もが自由にデータを発信できるプラットフォー–
ム様々な可能性秘めている•
放送をぶっ壊す•
大容量のデータを高速に転送• P2P オーバーレイネットワークが抱える問題 点 –
データ展開（配信）時の需要に対応できない•
需要に対して供給が非常に少ない–
必ずしもデータを高速に展開できない•
データ展開を待つ時間が発生 待ち時間なしで手に入れたい！
P2P のデータ展開における問題点 n umber of nodes
n umber of nodes
t imeline t imeline
データ公開
問題仮説
/
手法検証手法タイムラグ データ発見
アップロード可能ノード数
（供給）
需要最大 ボトルネック
ダウンロード要求ノード数
（需要）
供給最大
既存手法
• P2P ネットワークを利用したデータ展開
– SkeedCast – ShareCast
• 配信サーバを静的に設置して配信を行う
– P2P の価値をフルに活かせない
ShareCast SkeedCast
配信サーバ
配信サーバ 問題仮説
/
手法検証手法既存手法による対策（ Hybrid-P2P 型）
n umber of nodes
n umber of nodes
t imeline t imeline
データ公開
問題仮説
/
手法検証手法タイムラグ データ発見
ダウンロード要求ノード数 アップロード可能ノード数 （需要）
（供給）
配信サーバ供給分
需要・供給最大
本研究が目指す解き方（ Pure-P2P 型）
n umber of nodes
n umber of nodes
t imeline t imeline
データ公開
問題仮説
/
手法検証手法データ発見
ダウンロード要求ノード数 アップロード可能ノード数 （需要）
（供給）
キャッシュを作成
需要・供給最大
将来ダウンロードするノードにキャッシュを作成する
＝需要が無くなり供給が増える全体として高速化
研究目的
• キャッシュノードの動的な選択と配置
–
キャッシュノードの条件•
リソース（回線、ストレージなど）に余裕がある•
データのキャッシュがノードにとって有益に働く＝将来データをダウンロードするノードである！
–
適切なキャッシュノードを選出する手法が必要Bottleneck
Originator Originator
Data Request Nodes Data Request Nodes
Cache Nodes
動的に選択 問題仮説/
手法検証手法ユーザとデータのマッチング
• ユーザの振る舞い方に以下の特徴がある
1. ある分野に以前から興味を持っている 2. ある分野に含まれるデータを持っている 3. 今後もある分野に興味を持つ
• アップロード・ダウンロードの双方に共通
–
ダウンロードノードとキャッシュノードの関係•
互いに近隣となる（キャッシュがヒットしやすい）–
近い将来ダウンロードされるデータの推測•
直接的なデータ名だと揺らぎが大きい属性の表現方法として「タグ」を導入する
問題仮説
/
手法検証手法• データとノードはそれぞれタグを持つ
– データのタグ
•
アップロード時にユーザが指定•
複数個（10
個程度）のタグを付加する– ノード（＝ユーザ）のタグ
•
初期参加時はタグをユーザが指定•
ダウンロードしたデータに応じて自動的に変化す るデータのタグとノードのタグ
データ
Tag A Tag B Tag C
Tag A Tag C
ノード（ユーザ）
ダウンロードしたデータ
自動的に決定
問題仮説
/
手法検証手法P2P ネットワークの形成方法
• ポイント：同じタグを持つノードが近隣 1. タグ毎に になる P2P ネットワークを形成する
– ○P2P の構造が簡単になる
– × リソースを多く消費する（非効率）
– × 複数タグを走査することが難しい
2. P2P ネットワークをタグ毎にグループ化
– ○ リソースを有効に使用できる – ○ 複数タグを走査することが可能 – × 構造が複雑になる可能性がある
Tag A
Tag B Tag C
Tag A
Tag B Tag C
問題仮説
/
手法検証手法実装する P2P ネットワーク
（ 1/2 ）
• 非構造化 P2P か構造化 P2P か
–
非構造化P2P
•
特徴：広く複製されているデータを見つけることが得•
意検索：任意のキーワードで検索が可能•
例：Winny
–
構造化P2P
•
特徴：効率的にどんなデータでも確実に見つける•
検索：（直接的には）キーによる検索しか可能ではな•
い例：Chord, CAN, Pastry, Kademlia
• 研究目的：キャッシュノードの動的な選択と 配置 –
どちらかだけでは効率的ではない問題仮説
/
手法検証手法実装する P2P ネットワーク
（ 2/2 ）
• 構造化 P2P に非構造化 P2P の特徴を持ち込む
–
利点：高速なノード・データの発見が可能になる– Kademlia
を拡張する•
全体のKademlia
の中にグループ毎のKademlia
• Kademlia を用いる理由
–
トポロジー自体が特定の構造を持たない（非構 1.造）経路を複数持つことが可能•
複数のグループに属する場合に有効に作用する2. ノードが頻繁に出入りする状況を想定している
•
冗長性を高めるためにあらゆるメッセージを活用問題仮説
/
手法検証手法データのアップロード方法
• 各ノードはタグのテー ブルを持つ
–
ダウンロードしたデータ数により優先度を決定–
ノードタグの選択（上位N
個、閾値、etc…
）• データをアップロードする場合
1. それぞれのタグをグループに問い合わせ
•
テーブルにおいて重みを持つ上位N
ノードを選出– N
はグループの規模により決定2. 多くのタグにおいて
AND
がとれるノードを選択•
キャッシュノードとしてデータをキャッシュさせるタグ
A
タグB
タグC
タグD
タグE
タグF
タグG
1 4 6 7 20 2 4
問題仮説
/
手法検証手法評価指標と方針
•
シミュレーションを用いて評価–
規模拡張性•
ノード数•
データ数•
タグ（属性）数•
グループ内のノード数• Kademlia
の経路–
閾値•
ノードあたりのタグ数•
タグ選択（手法）– P2P
ネットワーク•
冗長性•
キャッシュ効率–
ノードとデータの距離–
データ展開時間ノード・タグの増加に対しての規模拡張性 規模に対しての効率性・研究の有効性
最適なパラメータ・汎用的な手法の導出
新しい
P2P
アーキテクチャを提案できたか 問題仮説/
手法検証手法まとめ
• 目的
– P2P を利用したデータ展開の効率化
待ち時間なしで手に入れたい！
• 手法
– P2P ネットワークをタグ毎にグループ化 – 構造化 P2P の Kademlia を拡張
•
構造化P2P
に非構造化P2P
の特徴を持ち込む• 評価
– 複数の視点から評価
– 規模性、閾値、 P2P ネットワーク