Higashino Lab. インセンティブにより自律ユーザに 高品質なオーバーレイマルチキャスト木を 構築させるプロトコルの提案 清水佳範 中村嘉隆 山口弘純 東野輝夫 大阪大学大学院情報科学研究科 2015/9/30 DICOMO2005 1 Higashino Lab. 背景 多人数への P2P ストリーミング配信では サーバによるユニキャスト通信では送信元付近で大量の データパケットが発生する IP マルチキャストでは広域で利用することが難しい ⇒オーバーレイネットワーク上でマルチキャスト配信を行う 制御プロトコルを自由に設計できる 中継ノードに転送負荷 ⇒コスト負担に対し報償（インセンティブ）を与える 一般に、このように報償（インセンティブ）を与えることで、自発的な リソース貢献を誘導するようなモデルをインセンティブモデルと呼ぶ 2015/9/30 DICOMO2005 2 Higashino Lab. 既存の研究 オーバーレイネットワーク上での通信においてインセ ンティブモデルを取り入れている既存の研究 他のユーザに多くのファイルを提供することでシステム全 体を流れるファイルが増加* 貢献度が上がると能力の高い Peer と接続可能** 複数の送信者から１つのストリーミングを受信 良い Peer と接続することで質の高いストリーミングを受信可能 本研究ではマルチキャスト木全体の遅延を改善 *P. Golle, K. Leyton-Brown, and I.Mironov, “Incentive for sharing in peer-to-peer networks”. In Proceedings ACM Electronic Commerce,New York, May 2004. **A.Habib and J. Chuang, “Incentive mechanism for peer-to-peer media streaming”. In Proceedings of the 12th IEEE International Workshop on Quality of Service, June 2004 . . 2015/9/30 DICOMO2005 3 Higashino Lab. 研究の目的と内容 目的 マルチキャスト木全体の遅延を改善し、ソースから発信す る情報を全ユーザに効率よく配信 内容 ユーザがインセンティブ増大を目指して自律的に移動する ことで、マルチキャスト木全体の遅延が改善されるプロトコ ルの提案 2015/9/30 DICOMO2005 4 Higashino Lab. 提案プロトコルの概要 (イメージ図) インセンティブ：アプリケ ーション上で使えるお金 ビデオ配信など インセンティブモデル $100 $10 非協力ユーザ 木全体の最大 ホップ数が減少 2015/9/30 DICOMO2005 5 Higashino Lab. 提案プロトコルの概要 最大ホップ数最小木 提供可能次数が多いノードが木の上部に配置されている 空き次数が埋まっている 提供可能次数 = 5 接続可能なノード数 枝のバランスがよい 3 提案プロトコル 2015/9/30 1 1 2 3 1 1 1 インセンティブを与え、各ノードがホップ数最小木をつくる 方向に自律的に動くよう誘導する DICOMO2005 6 Higashino Lab. 提案するインセンティブモデル 遅延最小木を作るのに必要な要素 プラス要素 現在の使用次数（子ノード数+1） マイナス要素 使用次数が多い と葉までの最大 ホップ数が減少 使用可能次数を多く持つ子ノードの存在 長い枝の存在 以上の３要素で獲得インセンティブを決定 木の全体の 遅延に影響 を及ぼす 2015/9/30 提供可能次数を 多く持つノード を木の上部に DICOMO2005 自身 6 使用次数 3 3 2 7 Higashino Lab. ノードの動作（参加、離脱時） 参加時 空き次数があり、最もリンク遅延が短いノードと接続 離脱時 親ノードとの接続を切り、下流ノードごと移動 空き次数があり、最もリンク遅延が短いノードと接続 離脱ノード 離脱時の動作 2015/9/30 DICOMO2005 8 Higashino Lab. ノードの動作（木の再構築） 隣接ノードからの情報のみで分散的に木を再構築 自身のインセンティブが改善される場合に以下を目 的としたオペレーションを葉ノードから実行 空き次数をつめる 提供可能次数を多く持つ子ノード木の上位に移動させる 枝のバランスをよくする マルチキャスト木のソースから葉までの最大ホップ 数の減少が期待できる 2015/9/30 DICOMO2005 9 Higashino Lab. 情報の収集 インセンティブ計算に必要な情報を分散で収集、計算 各ノードは、すべての子ノードから受信した情報メッセージを 集約して親ノードに情報送信 最大遅延=3 f,d,a v a b f,d d c 最小遅延=1 c 収集する情報 ・最大ホップ数 ・最小ホップ数 ・子ノード名 e f f 2015/9/30 DICOMO2005 10 Higashino Lab. 自身と子ノードとの交換 子ノードに提供可能次数を多く持つノードがいる場合 接続可能次数の多いノードが木の上部に移動 P P u v v i u i Tv Ti Tv Ti u :オペレーションを実行するノード 2015/9/30 DICOMO2005 11 Higashino Lab. 孫ノードを子ノードへ変更 自身に空き次数がある場合 u v j 使用時数が増え、uの インセンティブが増加 空き次数が埋まる 最大ホップ数が減少する u i w Tj v w j Ti Tj u :オペレーション を実行するノード i Ti Tw 最大ホップ数が減 少し、u のインセ ンティブが増加 Tw 2015/9/30 DICOMO2005 12 Higashino Lab. 子ノードと孫ノードの交換 自身から葉までの最大ホップ数が短くなる場合 最大ホップ数を実現する孫ノードと最小ホップ数を実現する 子ノードを交換 u v w x Tx u i v w i x Ti Tw Ti Tx Tw u :オペレーションを実行するノード 2015/9/30 DICOMO2005 最大ホップ数が短くなり、 インセンティブが増加 13 Higashino Lab. シミュレーション実験 以下の３つの動作の優先度を変え、木全体の最大 遅延がどの程度改善するか調査 自身と子ノードとの交換 （オペレーション ①） 子ノードと孫ノードの交換 （オペレーション ②） 孫ノードを子ノードへ変更 （オペレーション ③） 実験環境 2015/9/30 ノード数 1,000 次数制約 2~7 ノード間遅延 40 ~ 60 ms DICOMO2005 初期状態の木に対し、葉 ノードからソースにむけて オペレーションを適用 14 Higashino Lab. 3 つの動作の優先度の変化による最大遅延の変化 12 540 520 ソースから葉までの最大遅延 11 500 480 10 460 2155回 2173 回 1721 回 1650回 1909回 1623回 9 440 420 ①<②<③ ①<③<② ②<①<③ オペレーション実行回数合計 2015/9/30 ②<③<① ③<①<② ソースから葉までの最大遅延(ms) ソースから葉までの最大ホップ数 ソースから葉までの最大ホップ数 ①提供可能 次数を多い ノードを木の 上位に ②枝のバラ ンスをよく する ③空き次数 をつめる ③<②<① ホップ数、最大遅延 DICOMO2005 ともに最小 15 Higashino Lab. ソースから葉までの最大ホッ プ数 140 120 6,000 131 ソースから葉までの最大ホップ数 5,447ms ソースから葉までの最大遅延 100 4,000 80 ベストに近い 最大ホップ数 60 3,000 2,000 40 10 461ms 20 7 1,000 350ms 0 0 初期状態 提案モデル 最大ホップ数最小 ③、①、② の順序で実行した場合 2015/9/30 5,000 ソースから葉までの最大遅延 (ms) 構築される木の最大ホップ数、最大遅延の比較 DICOMO2005 提供可能次数を 多く持つノードを 16 木の高い位置に Higashino Lab. 獲得インセンティブ決定式の提案 評価実験より、効果的なオペレーションの実行順序 がわかった 1. 2. 3. 空き次数をつめる（①） 提供可能次数を多く持つ子ノードを木の上位に移動（②） 枝のバランスをよくする（③） インセンティブモデルを実現するための式を提案 3 獲得インセンティブ＝ 6-3=3 + α * （現在の使用次数） 6 – β * （子ノードとの次数差の最大値） – γ * （葉までの最大ホップ数 – 葉までの最小ホップ数） 2 (α>β>γ>0) 2015/9/30 DICOMO2005 17 Higashino Lab. まとめと今後の課題 まとめ インセンティブモデルを用いて、最大ホップ数最短のオー バーレイマルチキャスト木を構築するプロトコルの提案 評価結果よりインセンティブモデルを実現するための式を 提案 今後の課題 2015/9/30 リンクの切断回数を減らすようオペレーション実行のタイミ ングを調整 他のインセンティブ方式で行った場合と比較評価 インセンティブを誰が与えるかという問題 獲得インセンティブの効果的な利用法 偽装の問題 DICOMO2005 18
© Copyright 2024 ExpyDoc
