アプリケーションレベル マルチキャスト Emma の 性能向上に関する検討

Presentation on theme: "アプリケーションレベル マルチキャスト Emma の 性能向上に関する検討"— Presentation transcript:

1 アプリケーションレベル マルチキャスト Emma の 性能向上に関する検討
中村嘉隆 廣森聡仁 山口弘純 安本慶一 東野輝夫 大阪大学 大学院情報科学研究科 大阪大学 大学院基礎工学研究科 奈良先端技術大学院大学 情報科学研究科

2 発表の概要 研究内容 研究グループが提案しているアプリケーションレベルマルチキャストプロトコル Emma のロバストネス向上のための機能設計 シミュレーションによる性能評価 発表内容 研究の背景 Emma の概要 追加機能の概要 シミュレーション実験と性能評価 中村嘉隆、山口弘純、廣森聡仁、安本慶一、東野輝夫、谷口健一： “ 映像による複数人のコミュニケーション向けのアプリケーションレベルマルチキャスト Emma の性能評価，” DICOMO2002 シンポジウム論文集, pp (2002) 2002/11/21 第 110 回 DPS 研究会

3 研究の背景 Emma の概要 追加機能の概要 シミュレーション実験と性能評価 2002/11/21 第 110 回 DPS 研究会

4 研究の背景 Internet 複数人の電子会議等、グループ通信アプリケーションの需要増加
数百台規模のエンドホストが同時並行かつ継続的に他のエンドホストにメディア送出 それらのメディアのいくつかを受信 Internet 2002/11/21 第 110 回 DPS 研究会

5 研究の背景 ユニキャスト グループの増大で非効率に A B C D 2002/11/21 第 110 回 DPS 研究会

6 研究の背景 IP マルチキャスト 特定のサーバを必要とせず、効率も良い インフラ整備の問題 A B C D 2002/11/21
第 110 回 DPS 研究会

7 ALM（アプリケーションレベルマルチキャスト）
オーバレイネットワーク上でエンドホストが配信木を管理 エンドホスト間ユニキャストトンネリングで構築 トンネリング間のパケット複製、転送で実現 D A C B A B C D 2002/11/21 第 110 回 DPS 研究会

8 ALM（アプリケーションレベルマルチキャスト）
オーバレイネットワークにする利点 マルチキャストインフラが不必要 制御機能はユニキャストプロトコルのものが利用可能 D A C B 2002/11/21 第 110 回 DPS 研究会

9 ALM（アプリケーションレベルマルチキャスト）
オーバレイネットワークでの制約 エンドホスト付近での帯域制約 実リンク上でのパケット重複 エンドホストからなるために流動的である D A C B 2002/11/21 第 110 回 DPS 研究会

10 研究の背景 Emma の概要 追加機能の概要 シミュレーション実験と性能評価 2002/11/21 第 110 回 DPS 研究会

11 Emma （End-user Multicast for Multi-party Application)
電子ビデオ会議アプリケーション対象 特徴 ALM 各参加者の各ビデオへの要求度 プリファレンスとして各参加者が設定 会議における話者の映像はプリファレンスを上げ、話者以外の映像はプリファレンスを下げるなど 複数ビデオ配信時において、エンドホスト付近での帯域制約により転送制御が必要な場合 全参加者のプリファレンスの総和を最大化するように行う 2002/11/21 第 110 回 DPS 研究会

12 研究目的 分散制御 動的に効率の良い配信木を構築 帯域制約を満たすビデオ配信 参加者の入れ替わりの際の配信木維持
特定のサーバを持たず、エンドホスト自身が制御 動的に効率の良い配信木を構築 パケット重複が多くない 経路重複も少ない 帯域制約を満たすビデオ配信 各参加者に要求度の高いビデオを優先的に配信 参加者の入れ替わりの際の配信木維持 2002/11/21 第 110 回 DPS 研究会

13 遅延をメトリックとした、各エンドホストを根とするソースベースの配信木を構築
Emma ビデオ配信木 遅延をメトリックとした、各エンドホストを根とするソースベースの配信木を構築 各ソースに対してそれぞれ配信木を持つ A B C D H E F G I J K L M N 2002/11/21 第 110 回 DPS 研究会

14 遅延をメトリックとした、各エンドホストを根とするソースベースの配信木を構築
Emma ビデオ配信木 遅延をメトリックとした、各エンドホストを根とするソースベースの配信木を構築 各ソースに対してそれぞれ配信木を持つ A B C D H E F G I J K L M N 2002/11/21 第 110 回 DPS 研究会

15 オーバレイでの帯域制約により、全てのエンドホストに全てのビデオを流すことは不可能
Emma ビデオ配信木 オーバレイでの帯域制約により、全てのエンドホストに全てのビデオを流すことは不可能 プリファレンスを用いて配信するビデオを制御 構築された配信木を用いて受信要求を送出する際に、自分以下の部分配信木におけるプリファレンス総和を計算 これによって配信するビデオ、配信停止するビデオを判定 2002/11/21 第 110 回 DPS 研究会

16 リンクに新たなビデオを流すための空き帯域がない場合
Emma ビデオ配信木 リンクに新たなビデオを流すための空き帯域がない場合 既存の配信を停止する場合のプリファレンス損失の最小値をビデオ配信要求の転送過程で計算 計算結果を配信木の上流に転送 最小のプリファレンス損失を計算し、利得と比較 プリファレンス損失＜プリファレンス利得なら配信受け入れ プリファレンス値はビデオ維持要求を用いて常に更新 2002/11/21 第 110 回 DPS 研究会

17 転送制御例 D がビデオ E を要求 ビデオ配信要求を上げていく過程でプリファレンス集約 A E:9 E:6 E:3 B C D A:1
I:2 H E F G I J K L M N 2002/11/21 第 110 回 DPS 研究会

18 転送制御例 ビデオ A、I が既に配信されている A、I のプリファレンス総和も同様に計算 A:1 E:6 I:4 A:6 E:9 I:8
B C D A:1 E:3 I:2 H E E E F G 1リンク2ビデオまで I I J K L M N 2002/11/21 第 110 回 DPS 研究会

19 転送制御例 ビデオ A、 I が既に配信されている時、E-B 間で帯域制約を満たせない A:1 E:6 I:4 A:6 E:9 I:8
C D A:1 E:3 I:2 H E E E F G 1リンク2ビデオまで I I J K L M N 2002/11/21 第 110 回 DPS 研究会

20 転送制御例 B における各ビデオのプリファレンス総和を比較 Aのプリファレンス総和＜Eのプリファレンス総和より A:6 E:9 I:8 A
C D A:1 E:3 I:2 H E E E F G 1リンク2ビデオまで I I J K L M N 2002/11/21 第 110 回 DPS 研究会

21 転送制御例 E-B 間での A の配信を停止し、 E の配信を開始 A:1 E:6 I:4 A:6 E:9 I:8 A:6 E:3 I:2
C D A:1 E:3 I:2 H E E E F G 1リンク2ビデオまで I I J K L M N 2002/11/21 第 110 回 DPS 研究会

22 転送制御例 E-B 間での A の配信を停止し、 E の配信を開始 A:1 E:6 I:4 A:6 E:9 I:8 A:6 E:3 I:2
C D A:1 E:3 I:2 H E E E F G 1リンク2ビデオまで I I J K L M N 2002/11/21 第 110 回 DPS 研究会

23 研究の背景 Emma の概要 追加機能の概要 シミュレーション実験と性能評価 2002/11/21 第 110 回 DPS 研究会

24 従来の Emma では中継ノードとなるエンドホストの離脱時に離脱ノードの親ノードに再接続
実際に電子ビデオ会議等で用いた場合、エンドホストの離脱・参加が頻繁に繰り返されることが予想される →ビデオ配信木が偏っていく可能性 ノードの離脱を管理する機能 Leave を Emma に追加 セッションへの参加機能 Join は Emma のものを利用 2002/11/21 第 110 回 DPS 研究会

25 配信木の偏り例 離脱ノードの親ノードと再接続する方針 A B C D H E F G I J K L M N 2002/11/21
第 110 回 DPS 研究会

26 配信木の偏り例 E が離脱 E の子ノード I、J、K は E の親ノード B と再接続 A B C D H F G I J K L M N
2002/11/21 第 110 回 DPS 研究会

27 配信木の偏り例 B が離脱 B の子ノード I、J、F、K は B の親ノード A と再接続 A C D H F G I J K L M N
2002/11/21 第 110 回 DPS 研究会

28 配信木の偏り例 結果 A の持つリンクが多くなる １ノードのリンク数を制限すると孤立するノードが発生 A C D H F G I J K L
M N 2002/11/21 第 110 回 DPS 研究会

29 中継ノードであるエンドホストの離脱時 Emma ノード離脱時における要求
ノード間の相互接続性、ユーザ満足度の維持のため、ビデオ配信木を維持したい このとき、機能 Leave では Emma の利点を失わないために 分散制御を維持する 新たなメッセージはなるべく定義しない ソースノードからのホップ数はなるべく小さくする を満たす再接続方針が求められる 2002/11/21 第 110 回 DPS 研究会

30 各ビデオ配信木の葉ノードから各ノードの空き帯域情報を集約
Emma 機能 Leave の概要 各ビデオ配信木の葉ノードから各ノードの空き帯域情報を集約 帯域に余裕のあるノードとしか新たなリンクは確立できない あるビデオ配信木に関する親ノードの離脱時 離脱したノードの親ノードに集約されている空き帯域情報を問い合わせ 空き帯域情報から、ソースノードからのホップ数が小さいノードを選んで再接続要求を送出 受け入れられたら再接続 これにより、ビデオ配信木を大きく変化させることなく維持可能 2002/11/21 第 110 回 DPS 研究会

31 Emma 空き帯域情報の集約 各ビデオ配信木の葉ノードから、自らの空き帯域情報をビデオ維持要求に付加して親ノードに送出
空き帯域情報を受け取ったノードは子ノード集合の空き帯域情報からホップ数の小さい数個を選んで親ノードに送出 A B,C,D B,F,I G,H,L B C D G,L,M H,N I,J,K H E F G 1ノードは 3リンクまで I J K L M N 2002/11/21 第 110 回 DPS 研究会

32 Emma ノード離脱後の再接続 あるビデオ配信木についてノード w の親ノード v が離脱した場合 B,C,D A A,C,D Bが離脱 C
ノード v の親ノード u に u 以下の空き帯域情報を問い合わせる 空き帯域情報内の各ノードに再接続要求を送出 B,C,D A A,C,D Bが離脱 C D H E F G 1ノードは 3リンクまで I J K L M N 2002/11/21 第 110 回 DPS 研究会

33 Emma ノード離脱後の再接続 あるビデオ配信木についてノード w の親ノード v が離脱した場合 A A,C,D C D H E F G
ノード v の親ノード u に u 以下の空き帯域情報を問い合わせる 空き帯域情報内の各ノードに再接続要求を送出 A A,C,D C D H E F G 1ノードは 3リンクまで I J K L M N 2002/11/21 第 110 回 DPS 研究会

34 以上の方針に従って実現した場合 を満たしながら再接続が可能 Emma 機能 Leave 各ノードで再接続処理を行えるので分散制御を維持できる
新たなメッセージは離脱ノードの親への空き帯域情報要求のみ ソースノードからのホップ数が著しく多くなることはない を満たしながら再接続が可能 2002/11/21 第 110 回 DPS 研究会

35 ロビーサーバからセッション参加エンドホストのIPアドレス入手 エンド間遅延を測定し、遅延の小さい数ノードとオーバレイリンク構築
Emma 機能 Join ロビーサーバからセッション参加エンドホストのIPアドレス入手 エンド間遅延を測定し、遅延の小さい数ノードとオーバレイリンク構築 A B H C G D 2002/11/21 第 110 回 DPS 研究会

36 研究の背景 Emma の概要 追加機能の概要 シミュレーション実験と性能評価 2002/11/21 第 110 回 DPS 研究会

37 シミュレーションによる性能評価 スクリプト型言語 ruby によって Emma を実装し、シミュレーション評価 評価したネットワークモデル
Tiers モデルに基づく階層型トポロジ LAN にあるノードのうち約 50% がエンドホスト 評価項目 ユーザ満足度が維持できているか ユーザ満足度が維持できていた場合も オーバレイリンクあたりの木の分布 実リンクあたりの経路重複度 が悪化していないか 全ユーザが参加して安定した後の状態 A と、参加/離脱を繰り返した後の状態 B について比較 全ユーザ数の 10% を入れ替え 2002/11/21 第 110 回 DPS 研究会

38 ユーザ満足度変化 ノード数の異なるネットワークにおいて、１エンドホスト当たりのプリファレンス総和平均を比較
全ユーザが参加して安定した後の状態 A と、参加/離脱を繰り返した後の状態 B について比較 ユーザ満足度が低下することはない 2002/11/21 第 110 回 DPS 研究会

39 オーバレイリンクあたりの木の分布 一つのオーバレイリンク上での配信木の重複度を比較
全ユーザが参加して安定した後の状態 A と、参加・離脱を繰り返した後の状態 B について比較 オーバレイリンク上での重複度は低い方が効率的 機能追加後は、空き帯域のあるノードを選んで再接続するので、一般にオーバレイリンク上での重複度はそれほど悪化しないはずである 2002/11/21 第 110 回 DPS 研究会

40 オーバレイリンクあたりの木の分布 全ユーザが参加して安定した後の状態 A 参加・離脱を繰り返した後の状態 B
2002/11/21 第 110 回 DPS 研究会

41 実リンクあたりの経路重複度 同様の実験を各実リンクに対しても行う オーバレイでのノード間経路は単一の実リンクを複数回含んでいる可能性
単一のパケットが単一実リンクで複数回配信される可能性がある（実リンクでのパケット重複） 配信木での実リンクあたりの重複度が低いままならよい 2002/11/21 第 110 回 DPS 研究会

42 実リンクあたりの経路重複度 全ユーザが参加して安定した後の状態 A 参加・離脱を繰り返した後の状態 B
状態 A、B の間では大きな変化はなく、 Emma の効率は保たれている 2002/11/21 第 110 回 DPS 研究会

43 まとめと今後の課題 まとめ 今後の課題 アプリケーションレベルマルチキャストプロトコル Emma のロバストネス向上のための機能設計
機能追加後のシミュレーションによる性能評価 今後の課題 メディア配信時のジッタやパケットロスの計測 2002/11/21 第 110 回 DPS 研究会

44 2002/11/21 第 110 回 DPS 研究会

45 実リンク上経路数 経路数はネイティブマルチキャストに近い ノード数 122 エンドホスト数 42
オーバレイの経路重複によるオーバヘッドは抑えられる 2002/11/21 第 110 回 DPS 研究会