インセンティブにより自律ユーザに高品質なオーバーレイマルチキャスト木を

Higashino Lab.
利己的なエンド間でマルチキャストを
実現するためのインセンティブ配分法
清水佳範中村嘉隆
山口弘純
東野輝夫
大阪大学大学院情報科学研究科
2015/10/1
DPS研究会
1
Higashino Lab.
背景

多人数への P2P ストリーミング配信では

サーバによるユニキャスト通信では送信元付近で大量の
データパケットが発生する
⇒オーバーレイネットワーク上でマルチキャスト配信を行う
制御プロトコルを自由に設計できる
 中継ノードに転送負荷
⇒コスト負担に対し報償（インセンティブ）を与える

一般に、このように報償（インセンティブ）を与えることで、自発的な
リソース貢献を誘導するようなモデルをインセンティブモデルと呼ぶ
2015/10/1
DPS研究会
2
Higashino Lab.
関連研究

オーバーレイネットワーク上でのマルチキャスト配信
においてインセンティブモデルを取り入れている研究

関連研究 1*
【目標】各ノードでの受信帯域の大きさの合計 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.2135-2146, March 2005 .
**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.1596-1607, March 2005 .
2015/10/1
DPS研究会
3
Higashino Lab.
本研究の概要

目標
マルチキャスト木全体の遅延を改善し、ソースから発信す
る情報を全ユーザに効率よく配信

手法
インセンティブを与えることでソースからの遅延がなるべく
小さいマルチキャスト木を利己的なノード*間で構築させる
*利己的なノードとは他ノードのために自身の
リソースを無償で使われることを嫌うノード
2015/10/1
DPS研究会
4
Higashino Lab.
本研究の概要
映像配信など
各ノードがインセンティブ
増大を目指して移動を
繰り返す
インセンティブ
アプリケーション上で使え
るお金．各ノードから集
めたお金を分配
提供可能帯域に応
じた位置へ移動
$100
$10
狭帯域ユーザ
2015/10/1
広帯域ユーザ DPS研究会
木全体の最大
遅延が減少
5
Higashino Lab.
情報の信頼性保証

十分信頼できるノード（管理ノード）の存在を仮定

木の構造情報の管理
各ノードから、定期的にその親ノードおよび子ノードの情報を受信し、
木の構造を把握する
 各ノードから出次数の申告を受ける
（管理ノードと各ノードとの通信路の暗号化や電子署名を用いるな
どして、データの改ざんや成りすましが行われないとする）


排他制御


ノードの移動処理の逐次性を保証する
獲得値（ノードが受け取るインセンティブ）の管理

2015/10/1
インセンティブモデルに従って各ノードの獲得値を計算し、管理する
DPS研究会
6
Higashino Lab.
ノードの動作

参加時


空き次数があり、最もリンク遅延が短いノードと接続
参加後

管理ノードからトークンメッセージを受け取ったノード（例：右
図ノード v ）は以下の動作を実行可能



u
現在の親ノードと離脱
新たな親ノードと接続
受け入れ先ノード（例：右図ノード u ）
は以下の動作を実行可能


現在の子ノードを切断
新たな子ノードと接続
i
接続要求
j
Ti
トークン
2015/10/1
DPS研究会
w
v
Tv
Tj
7
Higashino Lab.
遅延改善のための基本アイデア

以下を繰り返す

木の下流で密度の高い部分木を構築する

多くのノードを含む部分木を下流から上流へ
最
大
遅
延
⇒遅延が改善
*密度＝ノード数÷最大遅延
2015/10/1
DPS研究会
8
Higashino Lab.
獲得値の計算

以下の条件を満たせば獲得値を増加させる
1.
ソースまでの遅延 up(v) を短くする
2.
下流密度と下流ノード数の積 down(v) を増加させる

下流密度：下流ノード数÷葉まで最大遅延
S
up(v)  2  1  3
3
9
down (v)  下流密度 (v)  下流ノード数 (v)   3 
2
2
下流ノード数 (v)
3
下流密度(v) 

葉までの最大遅延 (v) 2
2015/10/1
DPS研究会
2
1
b
1
a
1
v
c
1
d
9
Higashino Lab.
例：ノードの選択 1
ソースまでの遅延 up(v) が短くなる
u
i
⇒ 獲得値が増大
接続要求
テーブル（管理ノード）
u,・・・
w
参照
j
Ti
トークン
v w
j
v
Ti
i
u
Tv
Tj
Tj
Tv
down(u)  下流密度 下流ノード数 
下流ノード数 2
葉までの最大遅延
最大遅延の減少により down(u) は増大⇒
2015/10/1
獲得値が増大DPS研究会
10
Higashino Lab.
例：ノードの選択 2
c2 を切断して、
v と接続する
ほうが獲得値
が増大
テーブル（管理ノード）
p,・・・
g
p
o
c1
c2
c3
トークン
q
l
v
2015/10/1
DPS研究会
11
Higashino Lab.
接続先ノード情報の収集方法


現在の子ノードに不満を持つノードは自身からソースまでの
遅延を定期的に上流に送信
すべての子ノードから受信した情報メッセージの一部(k%)を
親ノードに送信
ソース(管理ノード)
収集する情報
・ノードID
・ソースまでの遅延
k %を
上流へ
a
d
f
2015/10/1
f
S
d,b,c
g
c
v
d,a
f,d
テーブル
d,b,c ・・・
b,c
g
b
書き込む
トークンを持った
ノードが参照
c
e
k : 参加ノード数、
平均出次数により変化
e
DPS研究会
12
Higashino Lab.
短時間で遅延の短い木に
参加ノード
目標値
申告出次数
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))
2015/10/1
DPS研究会
13
Higashino Lab.
獲得値の与え方

ソースまでの遅延、下流密度と下流ノード数の積が
目標値に近づけば獲得値が増大
|目標値－現在値|が小さくなる
申告出次数に
より決定
現在の位置に
より決定
目標値
•down_G(dmax(v))
•up_G(dmax(v))
現在値
•down(v)
•up(v)
獲得値 Get(v) が大きくなる

申告出次数 k であるノードが目標の位置に到達した
ときの獲得値 Get_G(k) は以下の条件を満たすよう
設定 Get_G(1)< Get_G(2)< ・・・・< Get_G(K)
2015/10/1
DPS研究会
K : k の最大値
14
Higashino Lab.
申告出次数の虚偽報告を防ぐために

以下の条件を満たすとする
使用可能出次数より低い
出次数を申告した場合
虚
偽
申
告
2015/10/1
<
使用可能出次数 5
申告出次数 3
の場合の最大獲得値
使用可能出次数 5
申告出次数 5
の場合の最大獲得値
使用可能出次数を正直に
申告した場合、獲得値が最大に
使用可能出次数 5
使用可能出次数 5
<
申告出次数 10
の場合の最大獲得値
使用可能出次数より高い
出次数を申告した場合
DPS研究会
申告出次数 5
の場合の最大獲得値
15
Higashino Lab.
シミュレーション実験

提案手法を用いた場合、木全体の最大遅延がどの
程度改善するか実験

シミュレーション設定



ノード数
100 ~ 1,000
出次数制約
1 ~ 5（ランダムに設定）
ノード間遅延


2015/10/1
平均遅延=100ms
標準偏差=10ms,20ms,30ms
となる正規分布に従う
DPS研究会
初期木
リンク遅延が最も短
く、出次数の空きの
あるノードに接続
16
Higashino Lab.
実験結果 1
σ=10ms
初期木
3500
提案手法
集中制御型
（CTアルゴリズム）に
近い最大遅延を実現
最大遅延 (ms)
3000
集中制御型
2500
2000
1500
1000
500
0
平均ノード間遅延=100ms
300
400
最
大
遅
延
1000
500
700
800
900
1000
提案手法
1400
集中制御型
1200
最大遅延 (ms)
1500
600
初期木
1600
集中制御型
500
ノード数
提案手法
2000
最大遅延（ms）
200
ノード間遅延の差の度
合いを変化させて実験
初期木
2500
σ=10ms100
1000
800
600
400
200
0
σ=20ms
100
200
σ=20ms
2015/10/1
300
400
500
600
ノード数
700
800
900
0
1000
100
σ=30ms
σ=30ms
DPS研究会
200
300
400
500
600
700
800
900
1000
ノード数
ノード数
17
Higashino Lab.
実験結果 2

リンクの張り替え数
ノード数
100 300 500
張り替え数 38
700
900
213 423 1100 1580
（平均ノード間遅延100ms，標準偏差=20ms）
張り替え数は
ノード数の2倍以下
2015/10/1
DPS研究会
18
Higashino Lab.
実験結果 3

ノードの振舞いによる最大遅延の変化
初期木
提案手法
集中制御型
1400
集中制御型
の1.5倍以下
1200
最大遅延 (ms)
最
大
遅
延
1000
800
600
400
獲得値増大を目指さないノード
が存在しても遅延は改善
200
0
σ=20ms
2015/10/1
0%
10% 20%
30% 40%
50% 60% 70%
80% 90%
獲得値を増やす方向に行動するノードの割合 (%)
DPS研究会
100%
19
Higashino Lab.
まとめと今後の課題

まとめ



利己的なユーザに遅延最小のオーバーレイマルチキャス
ト木を構築させるためのインセンティブ配分法の提案
集中制御型と近い遅延を実現
今後の課題

遅延改善までの時間の短縮


2015/10/1
排他制御
Planet Lab 上で実験
DPS研究会
20
Higashino Lab.
2015/10/1
DPS研究会
21
Higashino Lab.
ノードの選択方法

親ノードの選択

接続後のソースまでの遅延 up(v) が現在よりも短くなるよ
うな親ノードを選択



候補となるノードからソースまでの遅延を管理ノードに問合わせる
自身とそのノードとの遅延を計測する
子ノードの選択

接続後の下流ノード数と下流密度の積 down(v) が現在よ
りも大きくなるような子ノードを選択

2015/10/1
必要であれば現在接続している子ノードを切断する
DPS研究会
22
Higashino Lab.
ノードの切断
S
獲得値増大に満足
j
上流へ
獲得値減少に不満
なノードは離脱
j
下流へ
2015/10/1
DPS研究会
j
23
Higashino Lab.
獲得値の計算方法 1/3

各ノードの獲得値
 G1 (v )



基本的にソースまでの遅延 up(v) が短くなれば大きくなる
up(v) が目標値 Up(申告出次数) に近ければ大きい
G2 (v)


基本的に下流ノード数と下流密度の積 down(v) が大きくなれば大
きくなる
down(v) が目標値 Down(申告出次数) に近ければ大きい
S
2015/10/1
Get(v)  G1 (v)  G2 (v)
S
DPS研究会
ソースまでの遅延に
よって G1(v) が決定
下流ノード数、葉ノード
までの最大遅延よって
G2(v) が決定
24
Higashino Lab.
獲得値の計算方法 2/3

G1(v) の計算式
ソースまでの遅延が
目標値より長いとき
up(v)  Up(申告出次数)のとき
G1 (v)  (1 
Up(申告出次数)  up(v)
Up(申告出次数)
)  S1 (申告出次数)
G1(v) の最大値
単調増加関数
up(v)  Up(申告出次数)のとき
G1 (v)  S1 (申告出次数)
ソースまでの遅延が目標値
に近づけば G1(v) が増加
2015/10/1
DPS研究会
25
Higashino Lab.
獲得値の計算方法 3/3

G2(v) の計算式
下流ノード数と下流密度
の積が目標値以下のとき
down(v)  Down(申告出次数)のとき
G2 (v)  (1 
Down(申告出次数)  down(v))
Down(申告出次数)
down(v)  Down(申告出次数)のとき
G2 (v)  S2 (申告出次数)
理想の位置より上位
へ移動した場合はそ
れ以上移動するメ
2015/10/1
リットがない
)  S2 (申告出次数)
G2(v) の最大値
単調増加関数
下流ノード数と下流密度の積が目
標値に近づけば G2(v) が増加
DPS研究会
26
Higashino Lab.
獲得値の割り当て 1/3

G1(v) の最大値 S1(申告出次数) が満たすべき条件
使用次数 n のときの G1(v) の最大値を以下のように定義
E1 (申告出次数, n)
 (1 
Up(申告出次数)  Up(n)
Up(申告出次数)
)  S1 (申告出次数)
ただし E1 (申告出次数, n)は以下の条件を満たす
0  i  k , 0  x
E1 (k  i, k  i)  E1 (k , k  i)
E1 (k , k )  E1 (k  i, x)
2015/10/1
DPS研究会
使用可能出次数より
高い出次数を申告し
てもメリットがない
使用可能出次数より低
い出次数を申告しても
27
メリットがない
Higashino Lab.
獲得値の割り当て 2/3

G2(v) の最大値 S2(申告出次数) が満たすべき条件
使用次数 n のときの G2(v) の最大値を以下のように定義
E2 (申告出次数, n)
 (1 
Down(申告出次数)  Down(n)
Down(申告出次数)
)  S 2 (申告出次数)
ただし E2 (申告出次数, n)は以下の条件を満たす
0  i  k , 0  x
E2 (k  i, k  i)  E2 (k , k  i)
E2 (k , k )  E2 (k  i, x)
2015/10/1
DPS研究会
使用可能出次数より
高い出次数を申告し
てもメリットがない
使用可能出次数より低
い出次数を申告しても
28
メリットがない
Higashino Lab.
提案するインセンティブモデルの説明

提案するインセンティブモデルでは




目標値に近い場所に存在するほど獲得値が増大
理想の位置より上位に移動した場合はそれ以上移動する
メリットがない
各ノードが獲得値増大を目指すことで目標木に近づ
いてゆき、遅延が改善されてゆく
切断回数が減り、短時間で遅延が改善する
2015/10/1
DPS研究会
29
Higashino Lab.
獲得値の割り当て 3/3


全ノードはデータの受信料として一定額 P を管理
ノードに支払うとする
・・・・・
受信料 P
集めた受信料を獲得値にまわす
関数 S1(k)、S2(k) は以下の条件を満たす管理ノード N×P

N
 S (d
i 1
1
N
max
(vi ))  S 2 (d max (vi ))  N  P
G1(vi) の最大値
i 1
G2(vi) の最大値
Dmax(v) :ノード v の申告出次数
N :ノード数
Get(v)  G1 (v)  G2 (v)
2015/10/1
管理ノード N×P
DPS研究会
獲得値
・・・・・
30

Download Report