インセンティブにより自律ユーザに 高品質なオーバーレイマルチキャスト木を 構築させるプロトコルの提案 清水佳範　 中村嘉隆　　山口弘純　　東野輝夫 大阪大学大学院情報科学研究科 2019/9/19 DICOMO2005

背景 多人数への P2P ストリーミング配信では サーバによるユニキャスト通信では送信元付近で大量のデータパケットが発生する IP マルチキャストでは広域で利用することが難しい ⇒オーバーレイネットワーク上でマルチキャスト配信を行う 制御プロトコルを自由に設計できる 中継ノードに転送負荷 ⇒コスト負担に対し報償（インセンティブ）を与える 一般に、このように報償（インセンティブ）を与えることで、自発的なリソース貢献を誘導するようなモデルをインセンティブモデルと呼ぶ 2019/9/19 DICOMO2005

既存の研究 オーバーレイネットワーク上での通信においてインセンティブモデルを取り入れている既存の研究 他のユーザに多くのファイルを提供することでシステム全体を流れるファイルが増加* 貢献度が上がると能力の高い 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 . . 2019/9/19 DICOMO2005

研究の目的と内容 目的 内容 マルチキャスト木全体の遅延を改善し、ソースから発信する情報を全ユーザに効率よく配信 ユーザがインセンティブ増大を目指して自律的に移動することで、マルチキャスト木全体の遅延が改善されるプロトコルの提案 2019/9/19 DICOMO2005

提案プロトコルの概要 (イメージ図) インセンティブモデル インセンティブ：アプリケ ビデオ配信など ーション上で使えるお金 $100 非協力ユーザ 木全体の最大ホップ数が減少 2019/9/19 DICOMO2005

提案プロトコルの概要 最大ホップ数最小木 提案プロトコル 提供可能次数が多いノードが木の上部に配置されている 空き次数が埋まっている 枝のバランスがよい 提案プロトコル インセンティブを与え、各ノードがホップ数最小木をつくる方向に自律的に動くよう誘導する 提供可能次数 = 接続可能なノード数 5 3 2 3 1 1 1 1 1 2019/9/19 DICOMO2005

提案するインセンティブモデル 遅延最小木を作るのに必要な要素 プラス要素 マイナス要素 以上の３要素で獲得インセンティブを決定 3 6 現在の使用次数（子ノード数+1） マイナス要素 使用可能次数を多く持つ子ノードの存在 長い枝の存在 以上の３要素で獲得インセンティブを決定 使用次数が多い と葉までの最大 ホップ数が減少 使用次数 3 木の全体の 遅延に影響 を及ぼす 自身 提供可能次数を 多く持つノード を木の上部に 3 6 2 2019/9/19 DICOMO2005

ノードの動作（参加、離脱時） 参加時 離脱時 空き次数があり、最もリンク遅延が短いノードと接続 親ノードとの接続を切り、下流ノードごと移動 離脱ノード 離脱時の動作 2019/9/19 DICOMO2005

ノードの動作（木の再構築） 隣接ノードからの情報のみで分散的に木を再構築 自身のインセンティブが改善される場合に以下を目的としたオペレーションを葉ノードから実行 空き次数をつめる 提供可能次数を多く持つ子ノード木の上位に移動させる 枝のバランスをよくする マルチキャスト木のソースから葉までの最大ホップ数の減少が期待できる 2019/9/19 DICOMO2005

情報の収集 インセンティブ計算に必要な情報を分散で収集、計算 各ノードは、すべての子ノードから受信した情報メッセージを集約して親ノードに情報送信 v f,d,a c 最小遅延=1 収集する情報 ・最大ホップ数 ・最小ホップ数 ・子ノード名 a b c f,d 最大遅延=3 d e f f 2019/9/19 DICOMO2005

自身と子ノードとの交換 子ノードに提供可能次数を多く持つノードがいる場合 接続可能次数の多いノードが木の上部に移動 u v v i u i P P u v v i u i Tv Ti Tv Ti u :オペレーションを実行するノード 2019/9/19 DICOMO2005

孫ノードを子ノードへ変更 自身に空き次数がある場合 空き次数が埋まる 最大ホップ数が減少する 使用時数が増え、uのインセンティブが増加 u を実行するノード v i v i w j j w Ti Ti 最大ホップ数が減少し、u のインセンティブが増加 Tw Tj Tj Tw 2019/9/19 DICOMO2005

最大ホップ数が短くなり、インセンティブが増加 子ノードと孫ノードの交換 自身から葉までの最大ホップ数が短くなる場合 最大ホップ数を実現する孫ノードと最小ホップ数を実現する子ノードを交換 u u v x i v w i Tx x w Ti Tw Ti Tx Tw 最大ホップ数が短くなり、インセンティブが増加 u :オペレーションを実行するノード 2019/9/19 DICOMO2005

シミュレーション実験 以下の３つの動作の優先度を変え、木全体の最大遅延がどの程度改善するか調査 実験環境 自身と子ノードとの交換 （オペレーション ①） 子ノードと孫ノードの交換 （オペレーション ②） 孫ノードを子ノードへ変更 （オペレーション ③） 実験環境 ノード数 1,000 次数制約 2 ~ 7 ノード間遅延 40 ~ 60 ms 初期状態の木に対し、葉ノードからソースにむけてオペレーションを適用 2019/9/19 DICOMO2005

3 つの動作の優先度の変化による最大遅延の変化 ①提供可能 次数を多い ノードを木の 上位に ②枝のバラ ンスをよく する 2155回 2173 回 1721 回 1650回 1909回 1623回 ③空き次数 をつめる オペレーション実行回数合計 ホップ数、最大遅延 ともに最小 2019/9/19 DICOMO2005

構築される木の最大ホップ数、最大遅延の比較 ベストに近い 最大ホップ数 提供可能次数を多く持つノードを木の高い位置に ③、①、② の順序で実行した場合 2019/9/19 DICOMO2005

獲得インセンティブ決定式の提案 評価実験より、効果的なオペレーションの実行順序がわかった インセンティブモデルを実現するための式を提案 空き次数をつめる（①） 提供可能次数を多く持つ子ノードを木の上位に移動（②） 枝のバランスをよくする（③） インセンティブモデルを実現するための式を提案 獲得インセンティブ＝ 　+ α * （現在の使用次数） 　– β * （子ノードとの次数差の最大値） – γ * （葉までの最大ホップ数 – 葉までの最小ホップ数） 　　 (α>β>γ>0) 6-3=3 3 6 2 2019/9/19 DICOMO2005

まとめと今後の課題 まとめ インセンティブモデルを用いて、最大ホップ数最短のオーバーレイマルチキャスト木を構築するプロトコルの提案 評価結果よりインセンティブモデルを実現するための式を提案 今後の課題 リンクの切断回数を減らすようオペレーション実行のタイミングを調整 他のインセンティブ方式で行った場合と比較評価 インセンティブを誰が与えるかという問題 獲得インセンティブの効果的な利用法 偽装の問題 2019/9/19 DICOMO2005