エンドホストの動画像フィルタリングを用いた アプリケーション層 QoS マルチキャストの実現 中村嘉隆 山口弘純 廣森聡仁† 安本慶一‡ 東野輝夫 大阪大学 大学院情報科学研究科 †大阪大学 大学院基礎工学研究科 ‡奈良先端科学技術大学院大学 情報科学研究科

研究目的 ネットワークの普及によりグループ通信需要増加 電子会議アプリケーションの実現 Internet 複数ビデオの同時並行配信 要求されるビデオの偏り Internet 2003/6/4 DICOMO2003

実現手段 ユニキャスト 利点 欠点 a b c d 現状のインターネット上で利用可能 グループの増大により非効率になる 2003/6/4 DICOMO2003

実現手段 IP マルチキャスト 利点 欠点 a b c d 経路管理等の特定のサーバを必要としない データの重複がないため効率がよい インフラの整備問題（対応ルータ等） a b c d 2003/6/4 DICOMO2003

実現手段 アプリケーションレベルマルチキャスト（ALM） a b c d a b c d オーバレイネットワーク上でエンドホストが配信木を管理 エンドホスト間ユニキャストトンネリングで構築 トンネリング間のパケット複製、転送で実現 d a c b a b c d 2003/6/4 DICOMO2003

アプリケーションレベルマルチキャスト 利点 マルチキャスト用のインフラが不要 ユニキャストトランスポートプロトコルが利用可能 a b c d 2003/6/4 DICOMO2003

アプリケーションレベルマルチキャスト 欠点 エンドホスト付近の帯域制約，データ重複 エンドホスト離脱によるネットワークの流動性 a b c d a c b 2003/6/4 DICOMO2003

ALM に関する従来研究 Overcast，CAN，RMX HBM Narada，ALMI，Yoid 大規模グループにおける効率的な配信 HBM 移動端末向けの安定したオーバレイネットワーク構築 Narada，ALMI，Yoid 小規模グループでの単一ビデオの配信 会議アプリケーションも対象としている 電子会議に必要な性質と考えられる，複数ビデオを同時継続的に配信するものはない 2003/6/4 DICOMO2003

研究目標 電子会議アプリケーション向け ALM プロトコル設計 配信経路木の効率 オーバレイネットワーク堅牢性 経路のパスストレスを短く パスストレス：2 ノード間オーバレイリンク上ユニキャストホップ数と 実リンク上最短ホップ数比 配信木の多重度（ツリーストレス）を少なく オーバレイネットワーク堅牢性 離脱・障害への対応 各参加者のビデオに対する要求度を反映したビデオ配信 ネットワーク利用効率の高いビデオ配信 要求の棄却率を低く 利用帯域を多く 2003/6/4 DICOMO2003

Emma （End-user Multicast for Multi-party Application) 特徴 遅延と帯域をメトリックとした配信経路木構築 離脱・障害時の配信経路木維持 ユーザの要求度を考慮したビデオ配信 各参加者の各ビデオへの要求度をプリファレンスとして各参加者が設定（持ち点配分方式など） 話者の映像はプリファレンスを上げ，話者以外の映像はプリファレンスを下げるなど 帯域制約により転送制御が必要な場合 →全参加者のプリファレンスの総和を最大化するように行う 2003/6/4 DICOMO2003

配信経路木構築 ソースベースのスパニング木に継ぎ木方式で構築 新規参加ノードは遅延の短い数ノードとオーバレイ構築 各ソースごとに配信経路木構築 遅延制約を満たしながら，（パスストレッチ制限） リンク帯域をメトリックとして構築（ツリーストレス分散） c 2 2 e a 1 1 2 d 3 数字はリンク帯域を抽象化したもの ホップ数制約を 2 とする 2 b 2003/6/4 DICOMO2003

離脱・障害管理 各ビデオ配信木の葉ノードから、自らの空き帯域情報をビデオ維持要求に付加して親ノードに送出 空き帯域情報を受け取ったノードは子ノード集合の空き帯域情報からホップ数の小さい数個を選んで親ノードに送出 b,c,d a 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 2003/6/4 DICOMO2003

離脱・障害管理 あるビデオ配信木についてノード e の親ノード b が離脱した場合 b,c,d a,c,d a b が離脱 c d h e ノード b の親ノード a に a 以下の空き帯域情報を問い合わせる 空き帯域情報内の各ノードに再接続要求を送出 b,c,d a,c,d a b が離脱 c d h e f g 1 ノードは 3 リンクまで 許容 i j k l m n 2003/6/4 DICOMO2003

離脱・障害管理 ソースからの配信を維持したまま，速やかに再接続先を決定 ソースノードからのホップ数等，配信木の効率も悪化しない あるビデオ配信木についてノード e の親ノード b が離脱した場合 ノード b の親ノード a に a 以下の空き帯域情報を問い合わせる 空き帯域情報内の各ノードに再接続要求を送出 ソースからの配信を維持したまま，速やかに再接続先を決定 ソースノードからのホップ数等，配信木の効率も悪化しない a,c,d a c d h e f g 1 ノードは 3 リンクまで 許容 i j k l m n 2003/6/4 DICOMO2003

ビデオ配信制御 以下の 2 つの値を比較することで，配信するビデオ・配信停止するビデオを決定する ユーザ利得 ユーザ損失 ビデオが新たに配信された場合に得られるプリファレンス総和 ユーザ損失 ビデオ配信が停止された場合に失うプリファレンス総和 2003/6/4 DICOMO2003

ビデオ配信制御 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 2003/6/4 DICOMO2003

ビデオ配信制御 ビデオ a，i が既に配信されている a，i のユーザ損失も同様にビデオ維持要求を用いて集約されている a:1 e:6 b c d a:1 e:3 i:2 h E e E f g 1 リンク 2 ビデオまで i I j k l m n 2003/6/4 DICOMO2003

ビデオ配信制御 ビデオ 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 2003/6/4 DICOMO2003

ビデオ配信制御 b における各ビデオのユーザ利得とユーザ損失を比較 a の損失 ＜ i の損失 ＜ e の利得より 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 2003/6/4 DICOMO2003

ビデオ配信制御 e-b 間での a の配信を停止し、 e の配信を開始 I E j k b f a c d g l m h n i e 1 リンク 2 ビデオまで 2003/6/4 DICOMO2003

ビデオ配信制御 e-b 間での a の配信を停止し、 e の配信を開始 各参加者からの各ビデオへの要求度を反映したビデオ配信が可能 a:1 i:4 a:6 e:9 i:8 a:6 e:3 i:2 各参加者からの各ビデオへの要求度を反映したビデオ配信が可能 a b c d a:1 e:3 i:2 h e E E f g 1 リンク 2 ビデオまで I i j k l m n 2003/6/4 DICOMO2003

研究目標 電子会議アプリケーション向け ALM プロトコル設計 →Emma/QoS 配信経路木の効率 オーバレイネットワーク堅牢性 経路のパスストレスを短く パスストレス：2 ノード間オーバレイリンク上ユニキャストホップ数と 実リンク上最短ホップ数比 配信木の多重度（ツリーストレス）を少なく オーバレイネットワーク堅牢性 離脱・障害に対する対応 各参加者のビデオに対する要求度を反映したビデオ配信 ネットワーク利用効率の高いビデオ配信 要求の棄却率を低く 利用帯域を多く →Emma/QoS 2003/6/4 DICOMO2003

Emma/QoS 帯域をユニット単位で管理（帯域ユニット） utility 値×プリファレンスより各値を算出 帯域を効率的に利用できるため，要求棄却率低下などの利点が見込める utility 値×プリファレンスより各値を算出 ユーザ利得（ （獲得後の utility – 獲得前の utility）×プリファレンス ） 各ノードで新たに帯域ユニットを獲得した場合 ユーザ損失（ （削減前の utility – 削減後の utility）×プリファレンス ） 帯域ユニットを削減された場合 h：単位帯域ユニット 2003/6/4 DICOMO2003

電子会議アプリケーションの特徴を満足する Emma/QoS 新たに定義したユーザ利得，ユーザ損失を用いてビデオ配信制御を行う これにより ユーザの要求に従ったビデオ配信が可能 →最終的にプリファレンスは最大化される 1 つ目のユニットに大きなユーザ利得，損失を与えることで， 多数の配信要求を受入 既配信ビデオの配信停止を回避 →棄却率低下 空きユニットがある限り，帯域ユニットを多数獲得することも可能 電子会議アプリケーションの特徴を満足する 2003/6/4 DICOMO2003

ビデオ配信制御 ビデオ a が 2 ユニット，i が 1 ユニット既に配信されている a2，i のユーザ損失はビデオ維持要求を用いて集約 a2：2 ユニット目のビデオ a a2:1 e:6 i:4 a2:6 e:9 i:8 a2:6 e:3 i:2 a b c d a2:1 e:3 i:2 h E e E f g 1 リンク 3 ユニットまで i I j k l m n 2003/6/4 DICOMO2003

ビデオ配信制御 ビデオ a，i が既に配信されている時，e-b 間で帯域制約を満たせない a2:1 e:6 i:4 a2:6 e:9 i:8 c d a2:1 e:3 i:2 h e E E f g 1 リンク 3 ユニットまで i I j k l m n 2003/6/4 DICOMO2003

ビデオ配信制御 b における各ビデオのユーザ利得とユーザ損失を比較 a2 の損失 ＜ i の損失 ＜ e の利得より a2:6 e:9 c d a2:1 e:3 i:2 h e E E f g 1 リンク 3 ユニットまで i I j k l m n 2003/6/4 DICOMO2003

ビデオ配信制御 e-b 間での a の 2 ユニット目を削減し、 e の配信開始 a2:1 e:6 i:4 a2:6 e:9 i:8 c d a2:1 e:3 i:2 h E e E f g 1 リンク 3 ユニットまで i I j k l m n 2003/6/4 DICOMO2003

ビデオ配信制御 ビデオ配信要求の棄却率を減少させることが可能 帯域をユニット単位で管理するため，利用可能な帯域を効率よく利用 e-b 間での a の 2 ユニット目を削減し、 e の配信開始 a2:1 e:6 i:4 a2:6 e:9 i:8 a2:6 e:3 i:2 ビデオ配信要求の棄却率を減少させることが可能 帯域をユニット単位で管理するため，利用可能な帯域を効率よく利用 a b c d a2:1 e:3 i:2 h e E E f g 1 リンク 3 ユニットまで I i j k l m n 2003/6/4 DICOMO2003

シミュレーション結果 スクリプト型言語 ruby によって Emma/QoS シミュレータを実装し，性能評価 評価したネットワークモデル Tiers モデルに基づく階層型トポロジ ノード数 200，ユーザ数 55 利用可能なオーバレイ帯域総量は LAN 帯域の半分 総オーバレイリンク容量は 12 帯域ユニット シミュレーションシナリオ セッション開始時にユーザ数急増 その後，ユーザの離脱，参加が繰り返される 2003/6/4 DICOMO2003

オーバレイネットワークの効率 リンクストレス 実リンクに配送される単一パケットの重複度 重複が少ないほど効率がよい a b c d 2003/6/4 DICOMO2003

最大のリンクストレスがユニキャストの半分で収まっている オーバレイネットワークの効率 リンクストレスの分布を評価 ユニキャストでの値と比較 Emma ユニキャスト 物理リンク数 リンクストレス値 最大のリンクストレスがユニキャストの半分で収まっている 2003/6/4 DICOMO2003

オーバレイネットワークの効率 パスストレッチ 1 2 3 4 5 6 1 2 オーバレイ上ノード間ホップ数と実リンク上ノード最短ホップ数比 オーバレイネットワーク上 2 エンドホスト間の最短経路に含まれる実リンク数 1 オーバレイリンクは複数の実リンクからなるため，オーバレイ上ホップ数は実リンク上のホップ数より多くなる 1 2 3 4 5 6 a 1 2 b 2003/6/4 DICOMO2003

（実ネットワーク上での遅延の 4 倍以内に収まっている） オーバレイネットワークの効率 パスストレッチ分布 0.8 経路数 累積 4 パスストレッチ値 80% の経路で 4 以下で収まっている （実ネットワーク上での遅延の 4 倍以内に収まっている） 2003/6/4 DICOMO2003

90% は最大ストレス値の半分程度に収まっている 配信経路木の特性 ツリーストレス（経路木多重度）の分布 オーバレイリンク上の帯域利用効率を示す 経路木数 累積 ツリーストレス値 90% は最大ストレス値の半分程度に収まっている （おおよそ一様に分散しているといえる） 2003/6/4 DICOMO2003

FCFS 方式に比べ，0 であるユーザ数が少なく，ほとんど 0.8 程度 ユーザの要求満足率 要求満足率 =(受け入れられた要求のユーザ利得)／(全要求のユーザ利得値) First-Come-First-Serve 方式と比較 Emma FCFS ユーザ数 0.8 FCFS 方式に比べ，0 であるユーザ数が少なく，ほとんど 0.8 程度 （低品質ながら複数のビデオを受信可能） 2003/6/4 DICOMO2003

FCFS 方式に比べ， 高い値を達成し，それを維持している ユーザ利得値の変動 ユーザ利得値総和のシミュレーション時間による変動 Emma FCFS ユーザ利得値 ユーザ数 シミュレーション時間 FCFS 方式に比べ， 高い値を達成し，それを維持している 2003/6/4 DICOMO2003

シミュレーション結果 これらの結果より は，電子会議アプリケーションに用いるのに適しているといえる 配信経路木の効率 現在のインターネット上で実現しても問題はない ビデオ配信時の要求棄却率 最高品質ではなくても，多数のビデオを配信可能 ユーザ利得 ユーザのプリファレンスに応じて配信可能 は，電子会議アプリケーションに用いるのに適しているといえる 2003/6/4 DICOMO2003

まとめ オーバレイネットワークにおける複数ビデオの同時配信時に QoS を分散制御で実現する ALM プロトコル Emma/QoS の提案 2003/6/4 DICOMO2003