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

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

Download Report