黒宮 佑介（学籍番号： ） 政策・メディア研究科 修士課程2年 主査：村井 純、副査：斉藤 賢爾・中村 修・江崎 浩

Presentation on theme: "黒宮 佑介（学籍番号： ） 政策・メディア研究科 修士課程2年 主査：村井 純、副査：斉藤 賢爾・中村 修・江崎 浩"— Presentation transcript:

1 黒宮 佑介（学籍番号：80924567） 政策・メディア研究科 修士課程2年 主査：村井 純、副査：斉藤 賢爾・中村 修・江崎 浩
2010年度秋学期 修士論文中間発表 構造化P2Pオーバーレイネットワークにおける オブジェクトの属性を用いた適応型高速データ展開 Adaptive and Fast Data Dissemination for Structured Peer-to-Peer Overlay Network with Object Attributes 黒宮 佑介（学籍番号： ） 政策・メディア研究科 修士課程2年 主査：村井 純、副査：斉藤 賢爾・中村 修・江崎 浩 2019/7/17 2010年度秋学期 修士論文中間発表

2 研究背景 P2Pの価値 問題 目的：P2Pを利用したデータ展開の高速化 様々なデータの共有をみんなで実現することが可能
概要→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ 研究背景 P2Pの価値 様々なデータの共有をみんなで実現することが可能 見たかったあの○○○が！！ 問題 「P2Pは間に合わない」 データ展開時の需要に対応できない データ展開＝データをネットワーク上に配置すること 待ち時間が発生する 待ち時間なしでデータにアクセスしたい！！ 目的：P2Pを利用したデータ展開の高速化 サーバ・クライアントモデルと同じように「間に合う」 2019/7/17 2010年度秋学期 修士論文中間発表

3 広範囲でデータの発見が行われ需要は増え続ける
概要→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ データ展開時における問題点 ボトルネックが存在 オリジネータ ！ ！ ！ ！ ！ ノード 待ち時間が発生 待ち時間が発生 広範囲でデータの発見が行われ需要は増え続ける 2019/7/17 2010年度秋学期 修士論文中間発表

4 オリジネータが最初にデータを公開する際の待ち時間は不可避
概要→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ データ展開時における問題点 P2Pの負荷分散が動作し始める しばらく経つと… オリジネータ キャッシュノード ノード オリジネータが最初にデータを公開する際の待ち時間は不可避 2019/7/17 2010年度秋学期 修士論文中間発表

5 既存のデータ展開高速化手法 P2Pを利用したデータ展開手法 配信サーバを静的に設置して配信を行う SkeedCast（Winny）(1)
概要→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ 既存のデータ展開高速化手法 P2Pを利用したデータ展開手法 SkeedCast（Winny）(1) ShareCast(2) 配信サーバを静的に設置して配信を行う P2Pの価値を最大限に活かせない 配信サーバという専用のインフラを必要としている 個人レベルでの情報配信が困難 ShareCast 配信サーバ P2P 配信サーバ P2P SkeedCast (1) SkeedCast: (2) ShareCast: 2019/7/17 2010年度秋学期 修士論文中間発表

6 既存のデータ展開：一部P2P ！ ！ ！ ！ ！ ボトルネックは存在しない 待ち時間は発生しない
概要→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ 既存のデータ展開：一部P2P ボトルネックは存在しない オリジネータ 配信サーバ ！ ！ ！ ！ ！ ノード 待ち時間は発生しない 2019/7/17 2010年度秋学期 修士論文中間発表

7 既存のデータ展開：一部P2P P2Pの負荷分散も動作し始める 着眼点：配信サーバでなくても実現可能では？
概要→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ 既存のデータ展開：一部P2P P2Pの負荷分散も動作し始める しばらく経つと… オリジネータ 着眼点：配信サーバでなくても実現可能では？ 配信サーバ ノード データを公開してから配布し終わるまでスムーズに配信可能 2019/7/17 2010年度秋学期 修士論文中間発表

8 待ち時間は発生しない＋ノードの需要を事前に満たす＝高速
概要→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ 本研究の提案手法：全部P2P 最初からP2Pの負荷分散が働く オリジネータ データ公開前にキャッシュ データの公開は遅延する アップロードノード ！ ！ 待ち時間は発生しない＋ノードの需要を事前に満たす＝高速 2019/7/17 2010年度秋学期 修士論文中間発表

9 提案手法に対する要求 キャッシュノードの動的な選択と配置 適切なキャッシュノードを選出する手法が必要 キャッシュノードの条件
概要→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ 提案手法に対する要求 キャッシュノードの動的な選択と配置 適切なキャッシュノードを選出する手法が必要 キャッシュノードの条件 ダウンロードを行うノードと近隣となる キャッシュするデータを将来ダウンロードする キャッシュノードになることが不利にならない！ Originator Originator Bottleneck Cache Nodes 動的に選択 Data Request Nodes Data Request Nodes 2019/7/17 2010年度秋学期 修士論文中間発表

10 ユーザの振る舞い方に着目 ユーザの振る舞い方に以下の特徴がある （ユーザ＝ダウンローダー・アップローダー）
概要→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ ユーザの振る舞い方に着目 ユーザの振る舞い方に以下の特徴がある （ユーザ＝ダウンローダー・アップローダー） ある分野に以前から興味を持っている ある分野に含まれるデータを持っている 今後もある分野に興味を持つ ユーザの振る舞い方をノードに反映させる ノードは以前からある分野のデータを探している ノードはある分野のデータをダウンロードしている ある分野のキャッシュデータを持っている ノードは今後もある分野のデータをダウンロードする 2019/7/17 2010年度秋学期 修士論文中間発表

11 属性を用いたオブジェクトの紐付け オブジェクト（データ・ノード）は属性のタグを持つ データタグ ノードタグ ユーザが指定を行う
概要→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ 属性を用いたオブジェクトの紐付け オブジェクト（データ・ノード）は属性のタグを持つ データタグ ユーザが指定を行う 複数個のタグを付加 ノードタグ 各ノードはタグのテーブルを持つ（例） ダウンロードしたデータによりタグの優先度を決定する 優先度によりノードのタグを選択（上位N個、閾値、etc…） タグ 攻殻機動隊 ヱヴァンゲリヲン 化物語 バクマン。 出現数 16 2 3 4 攻殻機動隊 データ 士郎正宗 自動的に決定 ノード アニメ 攻殻機動隊 アニメ ダウンロードしたデータ 2019/7/17 2010年度秋学期 修士論文中間発表

12 P2Pネットワークの構成（1/2） 非構造化P2Pと構造化P2P 目的：P2Pを利用したデータ展開の高速化
概要→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ P2Pネットワークの構成（1/2） 非構造化P2Pと構造化P2P 非構造化P2P（例：Winny、Share） 特徴：広く複製されているデータを見つけることが得意 検索：任意のキーワードで検索が可能 構造化P2P（例：Chord, CAN, Pastry, Kademlia） 特徴：効率的にどんなデータでも確実に見つける 検索：（直接的には）キーによる検索しか可能ではない 目的：P2Pを利用したデータ展開の高速化 キャッシュをヒットしやすくする ノードをクラスタリングする ・・・非構造化P2Pが得意 基本的にどんなデータも検索可能 稀少なデータも検索可能に ・・・構造化P2Pが得意 2019/7/17 2010年度秋学期 修士論文中間発表

13 P2Pネットワークの構成（2/2） 構造化P2Pに非構造化P2Pの特徴を持ち込む Kademliaを用いる理由
概要→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ P2Pネットワークの構成（2/2） 構造化P2Pに非構造化P2Pの特徴を持ち込む クラスタリングした環境において 高速なオブジェクトの発見が可能になる データの属性にマッチするノードの発見が容易になる 方法：Kademlia（1）を拡張する Kademliaの中にグループ化の概念を導入 Kademliaを用いる理由 トポロジー自体が特定の構造を持たない（非構造的） Kademliaの構造を適応的に変化させることが可能になる 経路を複数持つことが可能 複数のグループに属する場合に有効に作用する ノードが頻繁に出入りする状況を想定している Kademlia以外の構造化P2Pは専用のメッセージが必要 A B C （1）Kademlia: A Peer-to-peer Information System Based on the XOR Metric P Maymounkov, D Mazieres - Peer-to-Peer Systems, Springer 2019/7/17 2010年度秋学期 修士論文中間発表

14 評価指標と方針 シミュレーションを用いて評価 評価項目（1/2） データの展開の実験を行う P2Pネットワーク ある1個のデータに着目
概要→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ 評価指標と方針 シミュレーションを用いて評価 データの展開の実験を行う ある1個のデータに着目 ネットワークの規模：複数の環境で行う 評価項目（1/2） P2Pネットワーク 規模拡張性 ノード数 タグ数 経路数 Churn耐性 V.S Kademlia グループ A B C Kademlia グループ グループ 2019/7/17 2010年度秋学期 修士論文中間発表

15 評価指標と方針 評価項目（2/2） キャッシュの効果 待ち時間の減少 キャッシュがローカルにある確率 オリジネータがデータを公開したとき
概要→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ 評価指標と方針 評価項目（2/2） キャッシュの効果 待ち時間の減少 オリジネータがデータを公開したとき キャッシュが有効に働いているのか ネットワーク中にデータを配置中の場合 十分なアップロードノード数は確保できるのか キャッシュがローカルにある確率 ダウンロード要求が行われたノードにキャッシュが存在 オブジェクトのマッチングに成功している確率は キャッシュノードでダウンロード要求が行われなかった オブジェクトのマッチングに失敗する確率は 失敗した場合の原因は何か（ノード側・データ側） 2019/7/17 2010年度秋学期 修士論文中間発表

16 スケジュール アルゴリズム設計 ネットワーク設計 概要→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ 予定 10/ 24
31 11/ 7 14 21 28 12/ 5 12 19 26 1/ 2 9 アルゴリズム設計 ネットワーク設計 シミュレータ実装 評価（データ分析） 論文執筆 アルゴリズム設計 ネットワーク設計 ノードタグ決定 想定環境 ダウンロードしたデータからのタグ抽出方法 ノード数・データ数・タグ数 Kademlia タグの変更があった場合は？ グループ数 ユーザからのタグ指定の受付 グループ内のノード数 キャッシュノード選択 ノード 閾値の設定 経路数 ノード発見の方法 データ・タグ数 ネットワーク規模の測定方法 Churn耐性 2019/7/17 2010年度秋学期 修士論文中間発表

17 まとめ 目的 手法 評価 期待される効果 P2Pを利用したデータ展開の高速化 待ち時間なしで手に入れたい！
概要→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ まとめ 目的 P2Pを利用したデータ展開の高速化 待ち時間なしで手に入れたい！ 手法 P2Pネットワークをタグ毎にグループ化 構造化P2PのKademliaを拡張 構造化P2Pに非構造化P2Pの特徴を持ち込む 評価 設計したP2Pネットワークの性能 キャッシュを事前に配置することの効果 期待される効果 データ配信プラットフォームとしての P2Pオーバーレイネットワークの応用範囲の拡大 2019/7/17 2010年度秋学期 修士論文中間発表