黒宮 佑介（学籍番号： ） 政策・メディア研究科 修士課程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/11/10 2010年度秋学期 修士論文中間発表

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

3 ダウンロードの要求からダウンロード開始までの待ち時間が発生する
背景→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ データ展開時における問題点 オリジネータノード データの一次配信者 データの配信方法 データの要約を配布 要求が来たら転送開始 一般ノード データの取得者 データの取得方法 オリジネータからの広告 検索クエリを投げる ボトルネックが発生 オリジネータノード 一般ノード ！ ！ ！ ！ 広範囲でデータ発見需要は増え続ける ダウンロードの要求からダウンロード開始までの待ち時間が発生する 2019/11/10 2010年度秋学期 修士論文中間発表

4 オリジネータが最初にデータを公開する際の待ち時間は不可避
背景→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ データ展開時における問題点 しばらく経つと… キャッシュノード 元ダウンローダー 過去にダウンロード 現アップローダー データを他のノードへ 増えるほど効果大だが 資源が無駄になるかも 負荷分散が動作し始める オリジネータノード キャッシュノード 一般ノード キャッシュノードが現れる オリジネータが最初にデータを公開する際の待ち時間は不可避 2019/11/10 2010年度秋学期 修士論文中間発表

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

6 ダウンロードの要求からダウンロード開始までの待ち時間は不要
背景→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ 既存のデータ展開：一部P2P 配信サーバ 配信専用の計算機 複数台用意される 分散して設置される 特徴 巨大なストレージ 超高速な回線 配信の順序 オリジネータサーバ サーバ一般ノード ボトルネックは発生しない オリジネータノード 配信サーバ 配信サーバでなくても実現可能では？ 一般ノード ！ ！ ！ ！ ！ ！ 広範囲でデータ発見需要は増え続ける ダウンロードの要求からダウンロード開始までの待ち時間は不要 2019/11/10 2010年度秋学期 修士論文中間発表

7 待ち時間は発生しない＋ノードの需要を事前に満たす＝高速化
背景→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ 本研究の提案手法：全部P2P キャッシュノード 動的に選択される 配信の順序 オリジネータノード 一般ノード キャッシュノードになる 最初からP2Pの負荷分散が働く オリジネータノード キャッシュノード 遅延が発生 オンデマンド 一般ノード ！ ！ ！ ！ ！ ！ データ公開前にキャッシュ公開は遅延する 待ち時間は発生しない＋ノードの需要を事前に満たす＝高速化 2019/11/10 2010年度秋学期 修士論文中間発表

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

9 ユーザの振る舞い方に着目 ユーザの振る舞い方に以下の特徴がある （ユーザ＝ダウンローダー・アップローダー）
背景→問題→既存手法→提案手法→設計→検証方法→スケジュール→まとめ ユーザの振る舞い方に着目 ユーザの振る舞い方に以下の特徴がある （ユーザ＝ダウンローダー・アップローダー） ある分野に以前から興味を持っている ある分野に含まれるデータを持っている 今後もある分野に興味を持つ ユーザの振る舞い方をノードに反映させる ノードは以前からある分野のデータを探している ノードはある分野のデータをダウンロードしている ある分野のキャッシュデータを持っている ノードは今後もある分野のデータをダウンロードする 出典：コンテンツ類似度に基づくP2Pネットワークの動的再構成 山口 拓也, 松本倫 子, 吉田 紀彦 2019/11/10 2010年度秋学期 修士論文中間発表

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

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

12 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/11/10 2010年度秋学期 修士論文中間発表

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

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

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

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