エンドホストの動画像フィルタリングを用いたアプリ

エンドホストの動画像フィルタリングを用いた
アプリケーション層 QoS マルチキャストの実現
中村嘉隆山口弘純廣森聡仁†
安本慶一‡ 東野輝夫
大阪大学大学院情報科学研究科
†大阪大学大学院基礎工学研究科
‡奈良先端科学技術大学院大学情報科学研究科
研究目的
 ネットワークの普及によりグループ通信需要増加
 電子会議アプリケーションの実現
複数ビデオの同時並行配信
要求されるビデオの偏り
Internet
2003/6/4
DICOMO2003
2
実現手段
ユニキャスト
利点
現状のインターネット上で利用可能
欠点
グループの増大により非効率になる
• A 付近のリンクでは全受信者分のデータが通る
a
b
d
c
2003/6/4
DICOMO2003
3
実現手段
IP マルチキャスト
利点
経路管理等の特定のサーバを必要としない
データの重複がないため効率がよい
欠点
インフラの整備問題（対応ルータ等）
a
b
d
c
2003/6/4
DICOMO2003
4
実現手段
 アプリケーションレベルマルチキャスト（ALM）
 オーバレイネットワーク上でエンドホストが配信木を管理
 エンドホスト間ユニキャストトンネリングで構築
 トンネリング間のパケット複製、転送で実現
a
c
b
d
a
b
d
c
2003/6/4
DICOMO2003
5
アプリケーションレベルマルチキャスト
利点
マルチキャスト用のインフラが不要
ユニキャストトランスポートプロトコルが利用可能
a
c
b
d
a
b
d
c
2003/6/4
DICOMO2003
6
アプリケーションレベルマルチキャスト
欠点
エンドホスト付近の帯域制約，データ重複
エンドホスト離脱によるネットワークの流動性
a
c
b
d
a
b
d
c
2003/6/4
DICOMO2003
7
ALM に関する従来研究
Overcast，CAN，RMX
大規模グループにおける効率的な配信
HBM
移動端末向けの安定したオーバレイネットワーク構築
Narada，ALMI，Yoid
小規模グループでの単一ビデオの配信
会議アプリケーションも対象としている
電子会議に必要な性質と考えられる，複数ビデ
オを同時継続的に配信するものはない
2003/6/4
DICOMO2003
8
研究目標
 電子会議アプリケーション向け ALM プロトコル設計
 配信経路木の効率
 経路のパスストレスを短く
•
パスストレス：2 ノード間オーバレイリンク上ユニキャストホップ数と
実リンク上最短ホップ数比
 配信木の多重度（ツリーストレス）を少なく
 オーバレイネットワーク堅牢性
 離脱・障害への対応
 各参加者のビデオに対する要求度を反映したビデオ配信
 ネットワーク利用効率の高いビデオ配信
 要求の棄却率を低く
 利用帯域を多く
2003/6/4
DICOMO2003
9
Emma
（End-user Multicast for Multi-party Application)
特徴
遅延と帯域をメトリックとした配信経路木構築
離脱・障害時の配信経路木維持
ユーザの要求度を考慮したビデオ配信
各参加者の各ビデオへの要求度をプリファレンスとして各参
加者が設定（持ち点配分方式など）
 話者の映像はプリファレンスを上げ，話者以外の映像はプリ
ファレンスを下げるなど
帯域制約により転送制御が必要な場合
→全参加者のプリファレンスの総和を最大化するように行う
2003/6/4
DICOMO2003
10
配信経路木構築
 ソースベースのスパニング木に継ぎ木方式で構築
新規参加ノードは遅延の短い数ノードとオーバレイ構築
各ソースごとに配信経路木構築
 遅延制約を満たしながら，（パスストレッチ制限）
リンク帯域をメトリックとして構築（ツリーストレス分散）
c
2
2
a
e
1
1
2
d
3
数字はリンク帯域を抽象化したもの
ホップ数制約を 2 とする
2
b
2003/6/4
DICOMO2003
11
離脱・障害管理
 各ビデオ配信木の葉ノードから、自らの空き帯域情報をビデオ維
持要求に付加して親ノードに送出
 空き帯域情報を受け取ったノードは子ノード集合の空き帯域情報
からホップ数の小さい数個を選んで親ノードに送出
a
b,c,d
b,f,i
g,h,l
b
i,j,k
1 ノードは
3 リンクまで
許容
2003/6/4
i
c
e
g,l,m
f
g
j
k
DICOMO2003
l
d
h,n
h
m
n
12
離脱・障害管理
 あるビデオ配信木についてノード e の親ノード b が離脱した場合
 ノード b の親ノード a に a 以下の空き帯域情報を問い合わせる
 空き帯域情報内の各ノードに再接続要求を送出
1 ノードは
3 リンクまで
許容
2003/6/4
i
a
a,c,d
b,c,d
b が離脱
c
d
e
f
g
j
k
l
DICOMO2003
h
m
n
13
離脱・障害管理
 あるビデオ配信木についてノード e の親ノード b が離脱した場合
 ノード b の親ノード a に a 以下の空き帯域情報を問い合わせる
 空き帯域情報内の各ノードに再接続要求を送出
a,c,d
 ソースからの配信を維持したまま，速や
a
かに再接続先を決定
 ソースノードからのホップ数等，配信木
c
d
の効率も悪化しない
1 ノードは
3 リンクまで
許容
2003/6/4
i
e
f
g
j
k
l
DICOMO2003
h
m
n
14
ビデオ配信制御
以下の 2 つの値を比較することで，配信するビ
デオ・配信停止するビデオを決定する
ユーザ利得
ビデオが新たに配信された場合に得られるプリファレンス総
和
ユーザ損失
ビデオ配信が停止された場合に失うプリファレンス総和
2003/6/4
DICOMO2003
15
ビデオ配信制御
d がビデオ e を要求
ビデオ配信要求を上げていく過程でユーザ利得
集約
a
e:9
i
2003/6/4
e:6
b
c
e
f
g
j
k
l
DICOMO2003
e:3
d
h
m
a:1
e:3
i:2
n
16
ビデオ配信制御
 ビデオ a，i が既に配信されている
 a，i のユーザ損失も同様にビデオ維持要求を用いて集
約されている
a:1
a:6
e:9
i:8
1 リンク
2 ビデオまで
2003/6/4
Ii
a
b
c
E
e
f
g
j
k
l
DICOMO2003
e:6
i:4
a:6
e:3
i:2
d
h
m
a:1
e:3
i:2
n
17
ビデオ配信制御
 ビデオ a，i が既に配信されている時，e-b 間で帯域制
約を満たせない
a:6
e:9
i:8
1 リンク
2 ビデオまで
2003/6/4
Ii
a
b
c
E
e
f
g
j
k
l
DICOMO2003
a:1
e:6
i:4
a:6
e:3
i:2
d
h
m
a:1
e:3
i:2
n
18
ビデオ配信制御
 b における各ビデオのユーザ利得とユーザ損失を比較
 a の損失＜ i の損失＜ e の利得より
a:6
e:9
i:8
1 リンク
2 ビデオまで
2003/6/4
Ii
a
b
c
E
e
f
g
j
k
l
DICOMO2003
d
h
m
a:1
e:3
i:2
n
19
ビデオ配信制御
 e-b 間での a の配信を停止し、 e の配信を開始
a:6
e:9
i:8
1 リンク
2 ビデオまで
2003/6/4
Ii
a
b
c
E
e
f
g
j
k
l
DICOMO2003
a:1
e:6
i:4
a:6
e:3
i:2
d
h
m
a:1
e:3
i:2
n
20
ビデオ配信制御
 e-b 間での a の配信を停止し、 e の配信を開始
a:1
a:6
e:6 a:6
 各参加者からの各ビデオへの要求度を
a i:4 e:3
e:9
i:8
反映したビデオ配信が可能
i:2
1 リンク
2 ビデオまで
2003/6/4
Ii
b
c
E
e
f
g
j
k
l
DICOMO2003
d
h
m
a:1
e:3
i:2
n
21
研究目標
 電子会議アプリケーション向け ALM プロトコル設計
 配信経路木の効率
 経路のパスストレスを短く
•
パスストレス：2 ノード間オーバレイリンク上ユニキャストホップ数と
実リンク上最短ホップ数比
 配信木の多重度（ツリーストレス）を少なく
 オーバレイネットワーク堅牢性
 離脱・障害に対する対応
 各参加者のビデオに対する要求度を反映したビデオ配信
 ネットワーク利用効率の高いビデオ配信
 要求の棄却率を低く
 利用帯域を多く
2003/6/4
→Emma/QoS
DICOMO2003
22
Emma/QoS
 帯域をユニット単位で管理（帯域ユニット）
 帯域を効率的に利用できるため，要求棄却率低下などの利点が見込める
 utility 値×プリファレンスより各値を算出
 ユーザ利得（（獲得後の utility – 獲得前の utility）×プリファレンス）
 各ノードで新たに帯域ユニットを獲得した場合
 ユーザ損失（（削減前の utility – 削減後の utility）×プリファレンス）
 帯域ユニットを削減された場合
h：単位帯域ユニット
2003/6/4
DICOMO2003
23
Emma/QoS
 新たに定義したユーザ利得，ユーザ損失を用いてビデオ配信制
御を行う
 これにより
 ユーザの要求に従ったビデオ配信が可能
→最終的にプリファレンスは最大化される
 1 つ目のユニットに大きなユーザ利得，損失を与えることで，
 多数の配信要求を受入
 既配信ビデオの配信停止を回避
→棄却率低下
 空きユニットがある限り，帯域ユニットを多数獲得することも可能
電子会議アプリケーションの特徴を満足する
2003/6/4
DICOMO2003
24
ビデオ配信制御
 ビデオ a が 2 ユニット，i が 1 ユニット既に配信されている
 a2，i のユーザ損失はビデオ維持要求を用いて集約
 a2：2 ユニット目のビデオ a
a2:1
e:6
a i:4
a2:6
e:9
i:8
1 リンク
3 ユニットまで
2003/6/4
Ii
b
c
E
e
f
g
j
k
l
DICOMO2003
a2:6
e:3
i:2
d
h
m
a2:1
e:3
i:2
n
25
ビデオ配信制御
 ビデオ a，i が既に配信されている時，e-b 間で帯域制
約を満たせない
a2:1
e:6
a i:4
a2:6
e:9
i:8
1 リンク
3 ユニットまで
2003/6/4
Ii
b
c
E
e
f
g
j
k
l
DICOMO2003
a2:6
e:3
i:2
d
h
m
a2:1
e:3
i:2
n
26
ビデオ配信制御
 b における各ビデオのユーザ利得とユーザ損失を比較
 a2 の損失＜ i の損失＜ e の利得より
a2:6
e:9
i:8
1 リンク
3 ユニットまで
2003/6/4
Ii
a
b
c
E
e
f
g
j
k
l
DICOMO2003
d
h
m
a2:1
e:3
i:2
n
27
ビデオ配信制御
 e-b 間での a の 2 ユニット目を削減し、 e の配信開始
a2:1
e:6
a i:4
a2:6
e:9
i:8
1 リンク
3 ユニットまで
2003/6/4
Ii
b
c
E
e
f
g
j
k
l
DICOMO2003
a2:6
e:3
i:2
d
h
m
a2:1
e:3
i:2
n
28
ビデオ配信制御
 e-b 間での a の 2 ユニット目を削減し、 e の配信開始
a2:1
a2:6
e:6
a2:6
 ビデオ配信要求の棄却率を減少させ
a i:4
e:9
e:3
ることが可能i:8
i:2
b
c
d
 帯域をユニット単位で管理するため，
利用可能な帯域を効率よく利用
1 リンク
3 ユニットまで
2003/6/4
Ii
E
e
f
g
j
k
l
DICOMO2003
h
m
a2:1
e:3
i:2
n
29
シミュレーション結果
スクリプト型言語 ruby によって Emma/QoS シ
ミュレータを実装し，性能評価
評価したネットワークモデル
Tiers モデルに基づく階層型トポロジ
ノード数 200，ユーザ数 55
利用可能なオーバレイ帯域総量は LAN 帯域の半分
総オーバレイリンク容量は 12 帯域ユニット
シミュレーションシナリオ
セッション開始時にユーザ数急増
その後，ユーザの離脱，参加が繰り返される
2003/6/4
DICOMO2003
30
オーバレイネットワークの効率
リンクストレス
実リンクに配送される単一パケットの重複度
重複が少ないほど効率がよい
a
c
b
d
a
b
d
c
2003/6/4
DICOMO2003
31
オーバレイネットワークの効率
 リンクストレスの分布を評価
ユニキャストでの値と比較
ユニキャスト
Emma
物
理
リ
ン
ク
数
リンクストレス値
最大のリンクストレスがユニキャストの半分で収まっている
2003/6/4
DICOMO2003
32
オーバレイネットワークの効率
 パスストレッチ
オーバレイ上ノード間ホップ数と実リンク上ノード最短ホップ数比
 オーバレイ上ノード間ホップ数
• オーバレイネットワーク上 2 エンドホスト間の最短経路に含まれる実
リンク数
 1 オーバレイリンクは複数の実リンクからなるため，オーバレイ上
ホップ数は実リンク上のホップ数より多くなる
1
1
a
2
2
b
2003/6/4
6
3
5
DICOMO2003
4
33
オーバレイネットワークの効率
パスストレッチ分布
0.8
累
積
経
路
数
4
パスストレッチ値
80% の経路で 4 以下で収まっている
（実ネットワーク上での遅延の 4 倍以内に収まっている）
2003/6/4
DICOMO2003
34
配信経路木の特性
ツリーストレス（経路木多重度）の分布
オーバレイリンク上の帯域利用効率を示す
累
積
経
路
木
数
ツリーストレス値
90% は最大ストレス値の半分程度に収まっている
（おおよそ一様に分散しているといえる）
2003/6/4
DICOMO2003
35
ユーザの要求満足率
 要求満足率
=(受け入れられた要求のユーザ利得)／(全要求のユーザ利得値)
 First-Come-First-Serve 方式と比較
Emma
FCFS
ユ
ー
ザ
数
0.8
FCFS 方式に比べ，0 であるユーザ数が少なく，ほとんど 0.8 程度
（低品質ながら複数のビデオを受信可能）
2003/6/4
DICOMO2003
36
ユーザ利得値の変動
 ユーザ利得値総和のシミュレーション時間による変動
Emma
FCFS
ユ
ー
ザ
利
得
値
ユ
ー
ザ
数
シミュレーション時間
FCFS 方式に比べ，高い値を達成し，それを維持している
2003/6/4
DICOMO2003
37
シミュレーション結果
これらの結果より
配信経路木の効率
現在のインターネット上で実現しても問題はない
ビデオ配信時の要求棄却率
最高品質ではなくても，多数のビデオを配信可能
ユーザ利得
ユーザのプリファレンスに応じて配信可能
は，電子会議アプリケーションに用いるのに適し
ているといえる
2003/6/4
DICOMO2003
38
まとめ
オーバレイネットワークにおける複数ビデオの同
時配信時に QoS を分散制御で実現する ALM
プロトコル Emma/QoS の提案
Emma/QoS に対するシミュレーションによる性
能評価
今後は実際に Emma/QoS を用いたビデオ配信
時のパケットロス等の計測等を行う
2003/6/4
DICOMO2003
39

Download Report