アプリケーションレベルマルチキャスト Emma の性能

アプリケーションレベル
マルチキャスト Emma の
性能向上に関する検討
中村嘉隆廣森聡仁山口弘純
安本慶一東野輝夫
大阪大学大学院情報科学研究科
大阪大学大学院基礎工学研究科
奈良先端技術大学院大学情報科学研究科
発表の概要
• 研究内容
– 研究グループが提案しているアプリケーションレベルマルチキャストプロ
トコル Emma のロバストネス向上のための機能設計
– シミュレーションによる性能評価
• 発表内容
–
–
–
–
研究の背景
Emma の概要
追加機能の概要
シミュレーション実験と性能評価
中村嘉隆、山口弘純、廣森聡仁、安本慶一、東野輝夫、谷口健一：
“ 映像による複数人のコミュニケーション向けのアプリケーションレベルマルチキャスト
Emma の性能評価，” DICOMO2002 シンポジウム論文集, pp253-256 (2002)
2002/11/21
第 110 回 DPS 研究会
2
•
•
•
•
研究の背景
Emma の概要
追加機能の概要
シミュレーション実験と性能評価
2002/11/21
第 110 回 DPS 研究会
3
研究の背景
• 複数人の電子会議等、グループ通信アプリケーションの需要
増加
– 数百台規模のエンドホストが同時並行かつ継続的に他のエンドホストに
メディア送出
– それらのメディアのいくつかを受信
Internet
2002/11/21
第 110 回 DPS 研究会
4
研究の背景
• ユニキャスト
– グループの増大で非効率に
A
B
D
C
2002/11/21
第 110 回 DPS 研究会
5
研究の背景
• IP マルチキャスト
– 特定のサーバを必要とせず、効率も良い
– インフラ整備の問題
A
B
D
C
2002/11/21
第 110 回 DPS 研究会
6
ALM（アプリケーションレベルマルチキャスト）
• オーバレイネットワーク上でエンドホストが配信木を管理
– エンドホスト間ユニキャストトンネリングで構築
– トンネリング間のパケット複製、転送で実現
A
C
B
D
A
B
D
C
2002/11/21
第 110 回 DPS 研究会
7
ALM（アプリケーションレベルマルチキャスト）
• オーバレイネットワークにする利点
– マルチキャストインフラが不必要
– 制御機能はユニキャストプロトコルのものが利用可能
A
C
B
D
A
B
D
C
2002/11/21
第 110 回 DPS 研究会
8
ALM（アプリケーションレベルマルチキャスト）
• オーバレイネットワークでの制約
– エンドホスト付近での帯域制約
– 実リンク上でのパケット重複
– エンドホストからなるために流動的である
A
C
B
D
A
B
D
C
2002/11/21
第 110 回 DPS 研究会
9
•
•
•
•
研究の背景
Emma の概要
追加機能の概要
シミュレーション実験と性能評価
2002/11/21
第 110 回 DPS 研究会
10
Emma
（End-user Multicast for Multi-party Application)
• 電子ビデオ会議アプリケーション対象
• 特徴
– ALM
– 各参加者の各ビデオへの要求度
プリファレンスとして各参加者が設定
– 会議における話者の映像はプリファレンスを上げ、話者以外の映像は
プリファレンスを下げるなど
– 複数ビデオ配信時において、エンドホスト付近での帯域制
約により転送制御が必要な場合
• 全参加者のプリファレンスの総和を最大化するように行う
2002/11/21
第 110 回 DPS 研究会
11
研究目的
• 分散制御
– 特定のサーバを持たず、エンドホスト自身が制御
• 動的に効率の良い配信木を構築
– パケット重複が多くない
– 経路重複も少ない
• 帯域制約を満たすビデオ配信
– 各参加者に要求度の高いビデオを優先的に配信
• 参加者の入れ替わりの際の配信木維持
2002/11/21
第 110 回 DPS 研究会
12
Emma
ビデオ配信木
• 遅延をメトリックとした、各エンドホストを根とするソー
スベースの配信木を構築
– 各ソースに対してそれぞれ配信木を持つ
A
I
2002/11/21
B
C
E
F
G
J
K
L
第 110 回 DPS 研究会
D
H
M
N
13
Emma
ビデオ配信木
• 遅延をメトリックとした、各エンドホストを根とするソー
スベースの配信木を構築
– 各ソースに対してそれぞれ配信木を持つ
A
I
2002/11/21
B
C
E
F
G
J
K
L
第 110 回 DPS 研究会
D
H
M
N
14
Emma
ビデオ配信木
• オーバレイでの帯域制約により、全てのエンド
ホストに全てのビデオを流すことは不可能
– プリファレンスを用いて配信するビデオを制御
• 構築された配信木を用いて受信要求を送出する際に、
自分以下の部分配信木におけるプリファレンス総和を計
算
• これによって配信するビデオ、配信停止するビデオを判
定
2002/11/21
第 110 回 DPS 研究会
15
Emma
ビデオ配信木
• リンクに新たなビデオを流すための空き帯域が
ない場合
– 既存の配信を停止する場合のプリファレンス損失
の最小値をビデオ配信要求の転送過程で計算
– 計算結果を配信木の上流に転送
– 最小のプリファレンス損失を計算し、利得と比較
– プリファレンス損失＜プリファレンス利得なら配信受
け入れ
– プリファレンス値はビデオ維持要求を用いて常に更
新
2002/11/21
第 110 回 DPS 研究会
16
転送制御例
• D がビデオ E を要求
• ビデオ配信要求を上げていく過程でプリファレ
ンス集約
A
E:9
I
2002/11/21
E:6
B
C
E
F
G
J
K
L
第 110 回 DPS 研究会
E:3
D
H
M
A:1
E:3
I:2
N
17
転送制御例
• ビデオ A、I が既に配信されている
• A、I のプリファレンス総和も同様に計算
A:1
E:6
A I:4
A:6
E:9
I:8
B
C
E
F
G
J
K
L
A:6
E:3
I:2
D
H
A:1
E:3
I:2
1リンク2ビデオまで
I
2002/11/21
第 110 回 DPS 研究会
M
N
18
転送制御例
• ビデオ A、 I が既に配信されている時、E-B 間で帯域
制約を満たせない
A:1
E:6
A I:4
A:6
E:9
I:8
B
C
E
F
G
J
K
L
A:6
E:3
I:2
D
H
A:1
E:3
I:2
1リンク2ビデオまで
I
2002/11/21
第 110 回 DPS 研究会
M
N
19
転送制御例
• B における各ビデオのプリファレンス総和を比較
• Aのプリファレンス総和＜Eのプリファレンス総和より
A:6
E:9
I:8
A
B
C
E
F
G
J
K
L
D
H
A:1
E:3
I:2
1リンク2ビデオまで
I
2002/11/21
第 110 回 DPS 研究会
M
N
20
転送制御例
• E-B 間での A の配信を停止し、 E の配信を開始
A:1
E:6
A I:4
A:6
E:9
I:8
B
C
E
F
G
J
K
L
A:6
E:3
I:2
D
H
A:1
E:3
I:2
1リンク2ビデオまで
I
2002/11/21
第 110 回 DPS 研究会
M
N
21
転送制御例
• E-B 間での A の配信を停止し、 E の配信を開始
A:1
E:6
A I:4
A:6
E:9
I:8
B
C
E
F
G
J
K
L
A:6
E:3
I:2
D
H
A:1
E:3
I:2
1リンク2ビデオまで
I
2002/11/21
第 110 回 DPS 研究会
M
N
22
•
•
•
•
研究の背景
Emma の概要
追加機能の概要
シミュレーション実験と性能評価
2002/11/21
第 110 回 DPS 研究会
23
Emma
追加機能
• 従来の Emma では中継ノードとなるエンドホストの離
脱時に離脱ノードの親ノードに再接続
– 実際に電子ビデオ会議等で用いた場合、エンドホストの離
脱・参加が頻繁に繰り返されることが予想される
→ビデオ配信木が偏っていく可能性
• ノードの離脱を管理する機能 Leave を Emma に追加
• セッションへの参加機能 Join は Emma のものを利用
2002/11/21
第 110 回 DPS 研究会
24
配信木の偏り例
• 離脱ノードの親ノードと再接続する方針
A
I
2002/11/21
B
C
E
F
G
J
K
L
第 110 回 DPS 研究会
D
H
M
N
25
配信木の偏り例
• E が離脱
• E の子ノード I、J、K は E の親ノード B と再接
続
A
I
2002/11/21
J
B
C
F
G
K
L
第 110 回 DPS 研究会
D
H
M
N
26
配信木の偏り例
• B が離脱
• B の子ノード I、J、F、K は B の親ノード A と再
接続
A
C
I
2002/11/21
J
F
G
K
L
第 110 回 DPS 研究会
D
H
M
N
27
配信木の偏り例
• 結果 A の持つリンクが多くなる
• １ノードのリンク数を制限すると孤立するノード
が発生
A
C
I
2002/11/21
J
F
G
K
L
第 110 回 DPS 研究会
D
H
M
N
28
Emma
ノード離脱時における要求
• 中継ノードであるエンドホストの離脱時
– ノード間の相互接続性、ユーザ満足度の維持のた
め、ビデオ配信木を維持したい
– このとき、機能 Leave では Emma の利点を失わな
いために
• 分散制御を維持する
• 新たなメッセージはなるべく定義しない
• ソースノードからのホップ数はなるべく小さくする
を満たす再接続方針が求められる
2002/11/21
第 110 回 DPS 研究会
29
Emma
機能 Leave の概要
• 各ビデオ配信木の葉ノードから各ノードの空き帯域情
報を集約
– 帯域に余裕のあるノードとしか新たなリンクは確立できない
• あるビデオ配信木に関する親ノードの離脱時
– 離脱したノードの親ノードに集約されている空き帯域情報を
問い合わせ
– 空き帯域情報から、ソースノードからのホップ数が小さい
ノードを選んで再接続要求を送出
– 受け入れられたら再接続
• これにより、ビデオ配信木を大きく変化させることなく
維持可能
2002/11/21
第 110 回 DPS 研究会
30
Emma
空き帯域情報の集約
• 各ビデオ配信木の葉ノードから、自らの空き帯域情報をビデオ
維持要求に付加して親ノードに送出
• 空き帯域情報を受け取ったノードは子ノード集合の空き帯域情
報からホップ数の小さい数個を選んで親ノードに送出
A
B,C,D
B,F,I
G,H,L
B
I,J,K
1ノードは
3リンクまで
2002/11/21
I
C
E
G,L,M
F
G
J
K
L
第 110 回 DPS 研究会
D
H,N
H
M
N
31
Emma
ノード離脱後の再接続
• あるビデオ配信木についてノード w の親ノード v が離脱した場
合
– ノード v の親ノード u に u 以下の空き帯域情報を問い合わせる
– 空き帯域情報内の各ノードに再接続要求を送出
1ノードは
3リンクまで
2002/11/21
I
A
B,C,D
A,C,D
Bが離脱
C
D
E
F
G
J
K
L
第 110 回 DPS 研究会
H
M
N
32
Emma
ノード離脱後の再接続
• あるビデオ配信木についてノード w の親ノード v が離脱した場
合
– ノード v の親ノード u に u 以下の空き帯域情報を問い合わせる
– 空き帯域情報内の各ノードに再接続要求を送出
1ノードは
3リンクまで
2002/11/21
I
A
A,C,D
C
D
E
F
G
J
K
L
第 110 回 DPS 研究会
H
M
N
33
Emma
機能 Leave
• 以上の方針に従って実現した場合
– 各ノードで再接続処理を行えるので分散制御を維
持できる
– 新たなメッセージは離脱ノードの親への空き帯域情
報要求のみ
– ソースノードからのホップ数が著しく多くなることは
ない
を満たしながら再接続が可能
2002/11/21
第 110 回 DPS 研究会
34
Emma
機能 Join
• ロビーサーバからセッション参加エンドホストの
IPアドレス入手
• エンド間遅延を測定し、遅延の小さい数ノードと
オーバレイリンク構築
B
A
H
C
2002/11/21
D
G
第 110 回 DPS 研究会
35
•
•
•
•
研究の背景
Emma の概要
追加機能の概要
シミュレーション実験と性能評価
2002/11/21
第 110 回 DPS 研究会
36
シミュレーションによる性能評価
• スクリプト型言語 ruby によって Emma を実装し、シ
ミュレーション評価
– 評価したネットワークモデル
• Tiers モデルに基づく階層型トポロジ
• LAN にあるノードのうち約 50% がエンドホスト
– 評価項目
• ユーザ満足度が維持できているか
• ユーザ満足度が維持できていた場合も
– オーバレイリンクあたりの木の分布
– 実リンクあたりの経路重複度
が悪化していないか
– 全ユーザが参加して安定した後の状態 A と、参加/離脱を繰り返した後
の状態 B について比較
• 全ユーザ数の 10% を入れ替え
2002/11/21
第 110 回 DPS 研究会
37
ユーザ満足度変化
• ノード数の異なるネットワークにおいて、１エンドホスト当たりのプリファレン
ス総和平均を比較
• 全ユーザが参加して安定した後の状態 A と、参加/離脱を繰り返した後の状
態 B について比較
B/A (preference values par
receiver (ave.) )
1.6
1.4
1.2
1
A
B
0.8
0.6
0.4
0.2
0
56
66
76
86 96 106 116 126 136
# of receivers
• ユーザ満足度が低下することはない
2002/11/21
第 110 回 DPS 研究会
38
オーバレイリンクあたりの木の分布
• 一つのオーバレイリンク上での配信木の重複度を比
較
• 全ユーザが参加して安定した後の状態 A と、参加・離
脱を繰り返した後の状態 B について比較
– オーバレイリンク上での重複度は低い方が効率的
– 機能追加後は、空き帯域のあるノードを選んで再接続する
ので、一般にオーバレイリンク上での重複度はそれほど悪
化しないはずである
2002/11/21
第 110 回 DPS 研究会
39
50
1
45
0.9
40
0.8
35
0.7
30
A
0.6
25
B
0.5
20
A (cumulative)
15
B (cumulative)
10
0.4
0.3
0.2
5
0.1
0
0
1
4
7
cumulative ratio
# of links (ave.)
オーバレイリンクあたりの木の分布
10 13 16 19 22 25 28 31 34 37
# of SPTs on link
•全ユーザが参加して安定した後の状態 A
•参加・離脱を繰り返した後の状態 B
•状態 B のほうがわずかに小さくなっているが、ほぼ差異は無い
2002/11/21
第 110 回 DPS 研究会
40
実リンクあたりの経路重複度
• 同様の実験を各実リンクに対しても行う
– オーバレイでのノード間経路は単一の実リンクを複
数回含んでいる可能性
• 単一のパケットが単一実リンクで複数回配信される可能
性がある（実リンクでのパケット重複）
– 配信木での実リンクあたりの重複度が低いままなら
よい
2002/11/21
第 110 回 DPS 研究会
41
500
1
450
0.9
400
0.8
350
300
250
A
B
A (cumulative)
B (cumulative)
0.7
0.6
0.5
200
0.4
150
0.3
100
0.2
50
0.1
0
cumulative ratio
# of links (ave.)
実リンクあたりの経路重複度
0
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
# of SPTs on link
•全ユーザが参加して安定した後の状態 A
•参加・離脱を繰り返した後の状態 B
•状態 A、B の間では大きな変化はなく、 Emma の効率は保たれている
2002/11/21
第 110 回 DPS 研究会
42
まとめと今後の課題
• まとめ
– アプリケーションレベルマルチキャストプロトコル
Emma のロバストネス向上のための機能設計
– 機能追加後のシミュレーションによる性能評価
• 今後の課題
– メディア配信時のジッタやパケットロスの計測
2002/11/21
第 110 回 DPS 研究会
43
2002/11/21
第 110 回 DPS 研究会
44
実リンク上経路数
16
14
オーバレイ
ユニキャスト
ネイティブマルチキャスト
12
リンク数
10
8
ノード数 122
エンドホスト数 42
6
4
2
0
0
20
40
60
80
リンク上の経路数
100
120
140
• 経路数はネイティブマルチキャストに近い
– オーバレイの経路重複によるオーバヘッドは抑えられる
2002/11/21
第 110 回 DPS 研究会
45

Download Report