利己的なエンド間でマルチキャストを実現するためのインセンティブ配分法

Presentation on theme: "利己的なエンド間でマルチキャストを実現するためのインセンティブ配分法"— Presentation transcript:

1 利己的なエンド間でマルチキャストを実現するためのインセンティブ配分法
清水佳範　 中村嘉隆　　山口弘純　　東野輝夫 大阪大学大学院情報科学研究科 2019/5/14 DPS研究会

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

3 関連研究 オーバーレイネットワーク上でのマルチキャスト配信においてインセンティブモデルを取り入れている研究 関連研究 1* 関連研究 2**
【目標】各ノードでの受信帯域の大きさの合計 P を最大に 【手法】P の値が増加するようなノードの参加を許可 関連研究 2** 【目標】送信元から受信者までの遅延を最小に 【手法】ソースがデータの配信経路（中継ノード）を決定 *S.Yuen and B.Li, “Strategyproof mechanisms for dynamic multicast tree formation in overlay networks.” In Proceedings of the Conference on Computer Communications (IEEE INFOCOM 2005), pp , March **W.Z.Wang,X.Y.Li,Z.Sun, “Design Multicast Protocols for Non-Cooperative Networks”. In Proceedings of the Conference on Computer Communications (IEEE INFOCOM 2005), pp , March 2019/5/14 DPS研究会

4 本研究の概要 目標 手法 マルチキャスト木全体の遅延を改善し、ソースから発信する情報を全ユーザに効率よく配信
　インセンティブを与えることでソースからの遅延がなるべく小さいマルチキャスト木を利己的なノード*間で構築させる *利己的なノードとは他ノードのために自身の リソースを無償で使われることを嫌うノード 2019/5/14 DPS研究会

5 アプリケーション上で使えるお金．各ノードから集めたお金を分配
本研究の概要 インセンティブ アプリケーション上で使えるお金．各ノードから集めたお金を分配 各ノードがインセンティブ 増大を目指して移動を 繰り返す 映像配信など 提供可能帯域に応じた位置へ移動 $100 $10 こうした最大遅延の長いマルチキャスト木をこうした最大遅延の短いマルチキャスト木に変えることを目的とする。データをより速く届けたい、また、より品質のよいデータをとどけたい。 インターネット上の各ユーザは一般的に自分のことしか考えない。ただ受信だけしている存在でいたいと願う。報酬を与えることで、計算機資源、帯域などを提供してもらい、結果的に全てのユーザが満足するようにしたい。 狭帯域ユーザ 木全体の最大遅延が減少 2019/5/14 広帯域ユーザ DPS研究会

6 情報の信頼性保証 十分信頼できるノード（管理ノード）の存在を仮定 木の構造情報の管理 排他制御
各ノードから、定期的にその親ノードおよび子ノードの情報を受信し、木の構造を把握する 各ノードから出次数の申告を受ける 　（管理ノードと各ノードとの通信路の暗号化や電子署名を用いるなどして、データの改ざんや成りすましが行われないとする） 排他制御 ノードの移動処理の逐次性を保証する 獲得値（ノードが受け取るインセンティブ）の管理 インセンティブモデルに従って各ノードの獲得値を計算し、管理する 管理ノードの存在を仮定。 この管理ノードの役割は、主にこの３つ。 また、各ノードは基本的に自身の獲得値を最大とすることを目標とするとする。 2019/5/14 DPS研究会

7 ノードの動作 u i w v j Ti Tj Tv 参加時 参加後 空き次数があり、最もリンク遅延が短いノードと接続
現在の親ノードと離脱 新たな親ノードと接続 受け入れ先ノード（例：右図ノード u ） 　 は以下の動作を実行可能 現在の子ノードを切断 新たな子ノードと接続 u i w 接続要求 j どのような動作が許されるか？ v Ti Tj トークン Tv 2019/5/14 DPS研究会

8 遅延改善のための基本アイデア 以下を繰り返す ⇒遅延が改善 木の下流で密度の高い部分木を構築する 多くのノードを含む部分木を下流から上流へ
最大遅延 *密度＝ノード数÷最大遅延 2019/5/14 DPS研究会

9 獲得値の計算 以下の条件を満たせば獲得値を増加させる ソースまでの遅延 up(v) を短くする
下流密度と下流ノード数の積 down(v) を増加させる 下流密度：下流ノード数÷葉まで最大遅延 S 1 a ノードをそのように動かすにはどうすればよいか？ 各ノードにどのようにインセンティブを与えればよいか？ 2 1 1 v c b 1 d 2019/5/14 DPS研究会

10 最大遅延の減少により down(u) は増大⇒獲得値が増大
例：ノードの選択 1 u ソースまでの遅延 up(v) が短くなる ⇒ 獲得値が増大 u テーブル（管理ノード） u,・・・ i w i v w 接続要求 j j 参照 v Ti Ti Tv Tj Tj トークン Tv 最大遅延の減少により down(u) は増大⇒獲得値が増大 2019/5/14 DPS研究会

11 c2 を切断して、v と接続するほうが獲得値が増大
例：ノードの選択 2 c2 を切断して、v と接続するほうが獲得値が増大 g テーブル（管理ノード） p,・・・ p o c2 c3 トークン c1 q l v 2019/5/14 DPS研究会

12 接続先ノード情報の収集方法 現在の子ノードに不満を持つノードは自身からソースまでの遅延を定期的に上流に送信
すべての子ノードから受信した情報メッセージの一部(k%)を親ノードに送信 テーブル d,b,c ・・・ ソース(管理ノード) 収集する情報 ・ノードID ・ソースまでの遅延 S 書き込む d,b,c c d,a v トークンを持ったノードが参照 k %を上流へ b,c a c f,d g b d e g k : 参加ノード数、 平均出次数により変化 e f 2019/5/14 f DPS研究会

13 短時間で遅延の短い木に 参加ノード 管理ノード 目標値 申告出次数 S
up_G(dmax(v)) down_G(dmax(v)) 申告出次数 dmax(v) 管理ノード S 次数分布 平均リンク間遅延 参加ノード数 up_G(dmax(v)) down_G(dmax(v)) up(v)、down(v) の目標値up_G(dmax(v))、down_G(dmax(v)) 2019/5/14 DPS研究会

14 獲得値の与え方 ソースまでの遅延、下流密度と下流ノード数の積が目標値に近づけば獲得値が増大 |目標値－現在値|が小さくなる
申告出次数 k であるノードが目標の位置に到達したときの獲得値 Get_G(k) は以下の条件を満たすよう設定 目標値 down_G(dmax(v)) up_G(dmax(v)) |目標値－現在値|が小さくなる 申告出次数により決定 現在の位置により決定 現在値 down(v) up(v) 獲得値 Get(v) が大きくなる Get_G(1)< Get_G(2)< ・・・・< Get_G(K) 2019/5/14 DPS研究会 K : k の最大値

15 < < 申告出次数の虚偽報告を防ぐために 以下の条件を満たすとする 虚偽申告 使用可能出次数を正直に
申告出次数の虚偽報告を防ぐために　　　 以下の条件を満たすとする 使用可能出次数より低い出次数を申告した場合 使用可能出次数 5 申告出次数 3 の場合の最大獲得値 < 使用可能出次数 5 申告出次数 5 の場合の最大獲得値 虚偽申告 使用可能出次数を正直に 申告した場合、獲得値が最大に 使用可能出次数 5 申告出次数 10 の場合の最大獲得値 < 使用可能出次数 5 申告出次数 5 の場合の最大獲得値 使用可能出次数より高い出次数を申告した場合 2019/5/14 DPS研究会

16 シミュレーション実験 提案手法を用いた場合、木全体の最大遅延がどの程度改善するか実験 シミュレーション設定 ノード数 100 ~ 1,000
ノード数 ~ 1,000 出次数制約 ~ 5（ランダムに設定） ノード間遅延 平均遅延=100ms 標準偏差=10ms,20ms,30ms 　　　　　　となる正規分布に従う 初期木 リンク遅延が最も短く、出次数の空きのあるノードに接続 2019/5/14 DPS研究会

17 実験結果 1 集中制御型 （CTアルゴリズム）に近い最大遅延を実現 最大遅延 σ=10ms 平均ノード間遅延=100ms
ノード間遅延の差の度合いを変化させて実験 最大遅延 σ=20ms σ=30ms ノード数 2019/5/14 DPS研究会

18 実験結果 2 リンクの張り替え数 ノード数 100 300 500 700 900 張り替え数 38 213 423 1100 1580
（平均ノード間遅延100ms，標準偏差=20ms） 張り替え数は ノード数の2倍以下 2019/5/14 DPS研究会

19 獲得値増大を目指さないノードが存在しても遅延は改善
実験結果 3 ノードの振舞いによる最大遅延の変化 集中制御型の1.5倍以下 最大遅延 獲得値増大を目指さないノードが存在しても遅延は改善 2019/5/14 DPS研究会

20 まとめと今後の課題 まとめ 今後の課題 利己的なユーザに遅延最小のオーバーレイマルチキャスト木を構築させるためのインセンティブ配分法の提案
集中制御型と近い遅延を実現 今後の課題 遅延改善までの時間の短縮 排他制御 Planet Lab 上で実験 2019/5/14 DPS研究会

21 2019/5/14 DPS研究会

22 ノードの選択方法 親ノードの選択 子ノードの選択 接続後のソースまでの遅延 up(v) が現在よりも短くなるような親ノードを選択
候補となるノードからソースまでの遅延を管理ノードに問合わせる 自身とそのノードとの遅延を計測する 子ノードの選択 接続後の下流ノード数と下流密度の積 down(v) が現在よりも大きくなるような子ノードを選択 必要であれば現在接続している子ノードを切断する 各ノードは獲得値増大のためにどのようなノードと接続するかについて説明。 2019/5/14 DPS研究会

23 ノードの切断 S 獲得値増大に満足 j 上流へ 獲得値減少に不満なノードは離脱 j 下流へ j 2019/5/14 DPS研究会

24 下流ノード数、葉ノードまでの最大遅延よって G2(v) が決定
獲得値の計算方法 1/3 各ノードの獲得値 基本的にソースまでの遅延 up(v) が短くなれば大きくなる up(v) が目標値 Up(申告出次数) に近ければ大きい 基本的に下流ノード数と下流密度の積 down(v) が大きくなれば大きくなる down(v) が目標値 Down(申告出次数) に近ければ大きい S S ソースまでの遅延によって G1(v) が決定 下流ノード数、葉ノードまでの最大遅延よって G2(v) が決定 2019/5/14 DPS研究会

25 ソースまでの遅延が目標値に近づけば G1(v) が増加
獲得値の計算方法 2/3 G1(v) の計算式 ソースまでの遅延が目標値より長いとき G1(v) の最大値 単調増加関数 ソースまでの遅延が目標値に近づけば G1(v) が増加 2019/5/14 DPS研究会

26 獲得値の計算方法 3/3 G2(v) の計算式 下流ノード数と下流密度の積が目標値以下のとき G2(v) の最大値 単調増加関数
理想の位置より上位へ移動した場合はそれ以上移動するメリットがない 下流ノード数と下流密度の積が目標値に近づけば G2(v) が増加 2019/5/14 DPS研究会

27 獲得値の割り当て 1/3 G1(v) の最大値 S1(申告出次数) が満たすべき条件
使用次数 n のときの G1(v) の最大値を以下のように定義 使用可能出次数より高い出次数を申告してもメリットがない 使用可能出次数より低い出次数を申告してもメリットがない 2019/5/14 DPS研究会

28 獲得値の割り当て 2/3 G2(v) の最大値 S2(申告出次数) が満たすべき条件
使用次数 n のときの G2(v) の最大値を以下のように定義 使用可能出次数より高い出次数を申告してもメリットがない 使用可能出次数より低い出次数を申告してもメリットがない 2019/5/14 DPS研究会

29 提案するインセンティブモデルの説明 提案するインセンティブモデルでは
目標値に近い場所に存在するほど獲得値が増大 理想の位置より上位に移動した場合はそれ以上移動するメリットがない 各ノードが獲得値増大を目指すことで目標木に近づいてゆき、遅延が改善されてゆく 切断回数が減り、短時間で遅延が改善する 先ほどの式のいみですが、・・・。 2019/5/14 DPS研究会

30 獲得値の割り当て 3/3 全ノードはデータの受信料として一定額 P を管理ノードに支払うとする 集めた受信料を獲得値にまわす
関数 S1(k)、S2(k) は以下の条件を満たす ・・・・・ 受信料 P 管理ノード N×P 管理ノード N×P G1(vi) の最大値 G2(vi) の最大値 獲得値 ・・・・・ Dmax(v) :ノード v の申告出次数 N :ノード数 2019/5/14 DPS研究会