LOLCAST Layered Overlay Multicast Protocol 階層構造を持つデータの配信に適した オーバーレイ・マルチキャストプロトコル 慶応義塾大学環境情報学部　小椋康平 <koh39@sfc.wide.ad.jp> 親　今泉英明 <hiddy@sfc.wide.ad.jp>

Presentation on theme: "LOLCAST Layered Overlay Multicast Protocol 階層構造を持つデータの配信に適した オーバーレイ・マルチキャストプロトコル 慶応義塾大学環境情報学部　小椋康平 <koh39@sfc.wide.ad.jp> 親　今泉英明 <hiddy@sfc.wide.ad.jp>"— Presentation transcript:

1 LOLCAST Layered Overlay Multicast Protocol 階層構造を持つデータの配信に適した オーバーレイ・マルチキャストプロトコル
慶応義塾大学環境情報学部　小椋康平 親　今泉英明 サブ親　石原知洋

2 本研究の概要 インターネットを利用した個人による情報発信が盛んになった 映像中継等の情報発信は困難
既存の配信技術は乏しい資源を持つ一般の利用者を対象不可能 新たなオーバーレイマルチキャスト技術(LOLCAST)を提案 階層構造を持つデータを用い受信者資源環境の抽象化 多くの受信者を対象可能 発信者・受信者は共に限られた資源内で多くの受信者に対しその環境に応じた配信が可能となり、問題を解決 インターネットを利用した個人による情報発信が非常に盛んになった しかし、現状では資源環境の乏しい一般利用者による映像中継等の表現を用いた配信は困難 この問題を新たなOLM技術であるLOLCASTを用いて解決 配信を行うデータとして新たに階層構造を持つデータを用いた。 これにより、受信者の資源環境を抽象化することが可能となり、より多くの受信者を対象とでる。 発信者・受信者は共に限られた資源内で多くの受信者にたいしてその環境に応じた配信が可能となり問題を解決できた。

3 問題意識 インターネット上で行われる創作活動 リアルタイム性の高いコンテンツ配信を行う事が困難 成果物の発信
共通の興味・目的を持った人々がグループを形成 様々な表現メディア 文字・音声・映像 人々の表現の場としてのインターネット リアルタイム性の高いコンテンツ配信を行う事が困難 実時間性ではなく中継等の用途 家庭までのネットワークの広帯域化、コンテンツ作成の機材が非常に安価になることにより、 個人によるインターネット上での創作活動とその成果物の情報発信が非常に活発になってきました このような人々は個人で活動している事もあれば、共通の興味や目的により集まり、グループを形成している場合もあります。 このような情報発信は様々な表現メディアを用いて行われています 文字-小説・日記 音声-ラジオ・個人制作の曲 映像-映画・演劇 しかし、現状ではリアルタイム性の高いコンテンツ配信を個人ベースで行う事が困難になってしまっています。 この根本的な原因は受信者・発信者が共に我々の様な一般利用者であるということです。

4 既存配信技術の問題点 (1) サーバクライアントモデル IP Multicast 受信者数の帯域的な負荷が発信者に発生
多くの受信者を対象不可能 IP Multicast 様々な理由によりdeployされていない IANAへのマルチキャストアドレス申請, ISP間のポリシの違い, 全ルータのマルチキャスト対応, etc. 一般利用者を対象とした、リアルタイム性の高いコンテンツ配信が行えない理由は既存配信技術にあります。 それ今でもできるんじゃないの？で、問題はなにさ。 既存技術はdeployしてなかったり、受信者の資源環境に適応できなかったりで一般利用者を対象とできない。

5 既存配信技術の問題点 (2) Overlay Multicast (OLM) IP Multicastの代替技術 単一的なデータの配信
Deploy可能 マルチキャストに関わる機能をアプリケーションレイヤへ エンドホストのUnicast OLMプロトコル Narada, Overcast, Hostcast 単一的なデータの配信 映像・音声等は品質を制御可能 複数品質でのサービス 品質毎のマルチキャストツリー 管理のオーバーヘッド 帯域的な負荷の増加 提供できるサービスの品質が限定 近年IP Multicastの代替技術としてOLMが登場し、活発に研究が行われています。 OLMはマルチキャストに関わる機能をIP MulticastにおけるIPレイヤからアプリケーションレイヤに委任を行います。 ルータに変わりエンドホスト同士のユニキャスト通信によって配信が行われます。 OLM技術ではマルチキャストに関わる機能をそれぞれのOLMプロトコルが提供しています。 OLMによりIP MulticastのDeployに関わる諸問題が解決されました。 しかし、OLMにも依然として問題があります。 それは単一的品質での配信しか考えられていないという点です。 本来音声映像は〜

6 達成目標 発信者 受信者 一般利用者にとって現実的な資源で配信網を構築・管理可能 受信者の環境に合わせた複数品質での配信
資源環境による参加の制限を受けない 環境に合わせた品質を選択可能

7 本研究のアプローチ 階層的な構造を持つデータの配信を行う新たなOLMプロトコル(LOLCAST)で解決 階層的な構造を持つデータ
単一のデータを複数のレイヤに分割 レイヤ数により品質制御可能 ex.階層符号化, マルチチャンネル, 既存表現のコンポジット マルチキャストツリーの構成 発信者が最高品質のデータを提供 各ノードは親と子の関係 親が子にデータを提供 発信者は単一の配信網の管理により受信者の資源環境に適応した複数品質での配信が可能 階層的な構造を持つデータの配信を行うOLMプロトコルによって既存技術の問題を解決します。 階層的なデータ構造を新たに定義した。 データは複数のレイヤにより分割され 下位のレイヤが上位のレイヤを保管する形で存在します。 レイヤ数を上下させることにより品質を制御可能。 LOLCASTでは階層構造により品質の抽象化を行った この抽象化により既存OLMと比べ、複数ツリーの管理に伴う冗長な管理コストや冗長なデータを軽減できる こちらがLOLCASTで構築するマルチキャストツリーの簡単な一例です レイヤ数に基づくツリーを構成しています まとめると、 発信者は〜 ----- んでどうやってそれを解決するのさ 階層的な構造を持つデータの配信を行う新たなOLMプロトコルで解決 階層的な構造を持つデータによって複数品質を一つのデータにまとめられる 発信者は単一の配信網の管理で受信者の資源環境に適応した配信ができる

8 要件 想定規模 発信者、受信者の資源環境 発信者は配信網を構築でき、運用コストも許容できる範囲 受信者は資源環境に左右されず参加可能
数千人 個人レベルで運営される最大のコミュニティの大きさを想定 発信者、受信者の資源環境 多種多様であり一般利用者にとって現実的 Ex. FTTH (100Mbps), ADSL (40Mbps), Dialup (56kbps) 発信者は配信網を構築でき、運用コストも許容できる範囲 受信者は資源環境に左右されず参加可能 各ノードの保持品質の異なりへの対処 一つのメトリックに沿ったマルチキャストツリーの構築が不可能 レイヤ数を考慮した上で参加や繋ぎ変えが必要 --- 設計要件 どういう人を対象にするの？対象はなに？　それを実現するために必要なことってなに？ レイヤに分割されてるから既存OLMの配信手法は使えない。 一つのメトリックに沿って自由に繋ぎ変えできない。つまりツリーを自由に作れない 数千人　最大のコミュニティのサイズ 受信者発信者共に資源が乏しい

9 プロトコル設計概要 マルチキャストツリーの構成 ノード間の情報のやり取り 発信ノード(Source Node)
全ノード情報・現在のツリー構造を管理 受信ノード(Recipient Node) 最低限の情報を管理 親ノード・子ノードのノード情報 Source Nodeからの要求に沿った処理を実行 処理の終了後に必ずSource Nodeにツリーの更新を伝達 参加の際にSource Nodeに参加先のノードリストを要求 ノード間の情報のやり取り メッセージパッシング 設計概要 ふーん。で、具体的にどうやってツリーとか作るの？ ツリーはソースが全部管理し受信ノードは最低限の情報を管理 受信ノードはソースにどこに繋がるべきか聞く 情報のやり取りはメッセージング

10 各ノードの保持する情報 Source Node A Recipient Node B C ノード情報 G F 1. 自身のノード情報
2. 現在のマルチキャストツリー構造 3. 全ノード情報を含む Source Node Source Node A 10 1. 自身のノード情報 2. SourceNodeのノード情報 3. 親ノード情報 4. 子ノード情報のリスト Recipient Node B 6 C 8 Recipient Node *はじめに ノードは２種類に分けられる (Source Node / Recipient Node) それぞれ所持する情報が異なる *ノードの情報 NodeID -> 各ノードを判別するuniqueなID 1. ノード識別子 (Nodeid) 2. 所持／要求レイヤ数 3. 木の深さ 4. 対応するネットワーク層プロトコル 5. アドレスのリスト ノード情報 6 1 G F

11 PPL Extraction PPL (Potential Parent List) の抽出 マルチキャストツリーを規定
新規ノードが参加をする条件を満たす親ノードのリスト マルチキャストツリーを規定 ツリーの品質に大きく関わる処理 要求レイヤ数が処理に渡され条件を元にPPLを抽出 所持レイヤ数が要求レイヤ数を満たす 管理子ノード数に空き 現在処理中のノードではない (離脱処理中 etc.)

12 PPL Extractionの流れ n *n 2 *a 1 *b 5 *c Search Temporary PPL ツリーノード情報リスト
KEY (nodeid) 2 VALUE (nodeinfo) *a 1 *b 5 *c 全ノードのテーブル Search ノード識別子 ツリー上の深さ 管理子ノード数 etc. 要求レイヤ数＜所持レイヤ数 管理子ノード数に空き ノード識別子 ツリー上の深さ 管理子ノード数 etc. ノード識別子 ツリー上の深さ 管理子ノード数 etc. ノード識別子 ツリー上の深さ 管理子ノード数 etc. ノード識別子 ツリー上の深さ 管理子ノード数 etc. PPL ツリーノード情報リスト 処理中のノードのエントリを削除 (ツリーから離脱中 etc.) マップを線形探索 ツリー上の深さでソート ノード識別子 ツリー上の深さ 管理子ノード数 etc. ノード識別子 ツリー上の深さ 管理子ノード数 etc. ノード識別子 ツリー上の深さ 管理子ノード数 etc. ノード識別子 ツリー上の深さ 管理子ノード数 etc. ツリーノード情報

13 Join Procedure E A B C E D +Address capability E +Layer of E 5
1:RendezvousRequest 　+Address capability E 3:PPLRequest 　+Layer of E 5 E SourceNodeinfo: A ParentNodeinfo: - ChildNodeinfo: - Child Slot: 0/3 PPL: - SourceNodeinfo: A ParentNodeinfo: C ChildNodeinfo: - Child Slot: 0/3 PPL: B-D SourceNodeinfo: A ParentNodeinfo: - ChildNodeinfo: - Child Slot: 0/3 PPL: C-B-D SourceNodeinfo: - ParentNodeinfo: - ChildNodeinfo: - Child Slot: 0/3 PPL: - A 4:PPLData 　+PPL C-B-D 2:RendezvousAccept 　+Nodeinfo of A + Nodeid of E 6:JoinAccept 　+Nodeinfo of C 10 PPL Extraction Update tree 5:JoinRequest 　+Nodeinfo of E 9:NotifyJoinComplete 　+Nodeinfo of E +Nodeinfo of C B 8 C 6 SourceNodeinfo - A ParentNodeinfo - A ChildNodeinfo D, E Child Slot 1/3 SourceNodeinfo - A ParentNodeinfo - A ChildNodeinfo D Child Slot 1/3 8:Data 5 E 7:DataStartRequest だめだった場合を述べる Cと通信が出来なかった場合 timeoutを与え再度join procedureを実行 6 D

14 Leave Procedure A C B D D 10 +Nodeinfo of C +Nodeinfo of C 6 8
1:NotifyLeaveProgress 　+Nodeinfo of C 7:PruneRequest 　+Nodeinfo of C 9:NotifyLeaveComplete +Nodeinfo of C 6 C 8:PruneComplete 6:NotifyParentChanged +Nodeinfo of D B 8 2:LeaveRequest 　+Nodeinfo of C 6 D 5:LeaveCompleted +Nodeinfo of D 4:DataStopRequest 6 D 3:Data (Join Completed) 以上終了時のprocedure 1,6,7が無い 生存確認メッセージが一定時間届かなくなる->生存確認の取れなくなった子ノードは再度Joinを行うことで復旧 子が他の親からデータを受け取ったことを確認してから離脱 -データの配信の停止を防ぐ

15 Protocol Administration
実装 モジュールに分割されたシステム LOLCASTのプロトコルによる評価、アプリケーションによる評価 単一のプロトコル処理部で行う ４つのモジュールから構成 プロトコル処理モジュール アプリケーションモジュール ネットワークモジュール シミュレータモジュール Application LOLCAST API Protocol Administration Module Joint Network Simulator

16 生成されたマルチキャストツリーの出力例

17 評価の目的 目標を達成できたか ノードの増加に伴うSource Nodeで発生する処理時間の増加 発信者 受信者
一般利用者にとって現実的な資源で配信網を構築・管理可能 受信者の環境に合わせた複数品質での配信 受信者 資源環境による参加の制限を受けない 環境に合わせた品質を選択可能 ノードの増加に伴うSource Nodeで発生する処理時間の増加

18 再度JoinProcedure(ALMI)
定性評価 評価項目/配信技術 LOLCAST 既存OLM 提供可能な品質 複数の品質 単一な品質 複数品質提供による 配信網の維持コスト 単一な マルチキャストツリー 品質毎の 予期しない離脱への対処 データパスの冗長化, 輻輳回避 配信パスの冗長化(Host Cast) 再度JoinProcedure(ALMI) 単一なデータの配信により複数の品質を提供 複数品質提供に伴うマルチキャストツリーの管理コストが減少 予期しないノードの離脱への対処手法を提供

19 定量評価 ノードの増加に伴うSource Nodeにおける処理時間の増加 計測対象 計測環境 シミュレータを用い計測
シミュレータモジュールとアプリケーションモジュールを利用 計測対象 Join Procedure Source Nodeに対するインタラクションの総処理時間 PPL Extraction Join Procedureに含まれる PPL生成の処理時間 計測環境 参加ノードの要求レイヤ数 固定レイヤ数 (Fixed layer) 最悪なケースを想定 PPL Extractionにおいて全ノードの含まれるテーブルを線形にサーチ テーブルの上位から順に管理子ノードのスロットがうまり、最悪の場合となる ランダムレイヤ数 (Random layer) 10,000ノードを追加 1ノード追加毎に処理時間を計測

20 1000ノード毎の平均処理時間 固定レイヤ数 (Fixed) ランダムレイヤ数 (Random) Worst Case ノード数 Join
Procedure (μsec) PPL Extraction (μsec.) 1000 75 39 2000 174 134 3000 355 311 4000 527 480 5000 692 643 6000 860 809 7000 1032 980 8000 1234 1180 9000 1468 1411 10000 1714 1654 ノード数 Join Procedure (μsec) PPL Extraction (μsec.) 1000 73 37 2000 146 108 3000 304 262 4000 475 430 5000 618 573 6000 770 722 7000 920 870 8000 1078 1026 9000 1254 1200 10000 1443 1386 固定レイヤ数のノードの追加に対する処理時間の方が大きい理由 PPL抽出時の手法の問題 レイヤ数によってソートを行っておく マルチマップに変更しレイヤ数毎にノードを抽出 固定レイヤ数 (Fixed) Worst Case ランダムレイヤ数 (Random)

21 Join Procedure/10000Nodes/Fixed layer size
Gettimeofday()を用いたため100μsec以下の値は信用できないため、1000ノードいかのデータは有効ではないと見て

22 PPL Extraction/10000Nodes/Fixed layer size
１

23 Average/10000Nodes/Fixed layer size

24 Join Procedure/10000 Nodes/Random layer size

25 PPL Extraction/1000 Nodes/Random layer size

26 Average/10000Nodes/Random layer size

27 評価結果 既存OLMとの比較 数千にを対象とした配信 単一の配信網により複数の受信者環境に適応した配信 発信者の帯域的資源に対する負荷が減少
品質毎のデータが必要ない 数千にを対象とした配信 ランダムなレイヤ数 5000ノード 0.6msec 10000ノード 1.4msec 最悪なケース 5000ノード 0.7msec 10000ノード 1.7msec 大幅な処理時間の増加は発生しない

28 まとめ 階層的な構造を持つデータの配信を行うLOLCASTを提案 発信者 受信者 既存OLMとの比較評価 単一の配信網の構築・管理
受信者の資源環境に適応した配信可能 受信者 資源環境による配信網への参加が制限されない 環境に合わせた品質を選択可能 既存OLMとの比較評価 発信者にかかる配信のためのコストを削減 より多くの受信者を対象可能

29 今後の課題 PPL Extractionの性能改善 LOLCASTを利用したアプリケーションの提供
Join Procedureにおける処理時間の大半を占める 全ノードのテーブルより、レイヤ数を満たすノードを線形に検索・抽出した後に木の深さが最小となるノードを抽出 O(n)の計算量 解決手法 レイヤ数によるソート キー(レイヤ数)に対し複数の値を持つテーブル LOLCASTを利用したアプリケーションの提供

30 Join Procedure message passing

31 Leave Procedure message passing

32 メッセージフォーマット

33 … … Recipient Node ノード情報 ノードの種類 自身のノード情報 ノード識別子 親ノード情報 所持/要求レイヤ数
IPv4/IPv6/etc. ノード情報 ノード識別子 所持/要求レイヤ数 対応ネットワークプロトコル ツリー内の深さ アドレス情報のシーケンス Node ID アドレス長 アドレスの種類 アドレス アドレス情報 ノードの種類 SourceNode/RecipientNode 自身のノード情報 親ノード情報 管理している子ノード 子ノード情報のリスト 全ノードを含むツリー構造 PPLのリスト 親ノードとなり得るノード ノード情報 (子ノード) … ノード情報 (PPL) …

34 … … … Source Node ツリー構造 ノードの種類 自身のツリーノード情報 自身のノード情報 全ノードを含むテーブル
SourceNode/RecipientNode 自身のツリーノード情報 自身のノード情報 全ノードを含むテーブル 子ノード情報のリスト 管理している子ノード 処理中のノードのリスト ツリー構造 全ノードを含むツリー構造 ツリーノード情報 (処理中のノード) ノード情報 (子ノード) … … VALUE ツリーノード情報 KEY ノード識別子 *i i *j j *k k *m m 全ノードを含むテーブル *n n *o o *p p ツリーノード情報 ノード情報 親ツリーノード情報 子ツリーノード情報のリスト … ツリーノード情報 (子ノード)

35 背景 インターネット上で行われる創作活動 リアルタイム性の高いコンテンツ配信を行う事が困難 発信者・受信者が共に一般利用者 成果物の発信
共通の興味・目的を持った人々がグループを形成 様々な表現メディア 文字・音声・映像 人々の表現の場としてのインターネット リアルタイム性の高いコンテンツ配信を行う事が困難 実時間性ではなく中継等の用途 発信者・受信者が共に一般利用者 家庭までのネットワークの広帯域化、コンテンツ作成の機材が非常に安価になることにより、 個人によるインターネット上での創作活動とその成果物の発信が非常に活発になってきました このような人々は個人で活動している事もあれば、共通の興味や目的により集まり、グループを形成している場合もあります。 このような情報発信は様々な表現メディアを用いて行われています 文字-小説・日記 音声-ラジオ・個人制作の曲 映像-映画・演劇 しかし、現状ではリアルタイム性の高いコンテンツ配信を個人ベースで行う事が困難になってしまっています。 この根本的な原因は受信者・発信者が共に我々の様な一般利用者であるということです。

36 一般利用者の二つの側面 発信者 受信者 計算機資源・ネットワーク帯域資源に限界 計算機資源環境・ネットワーク通信路品質が多種多様 受信者数
提供可能なコンテンツの品質が限定 受信者 計算機資源環境・ネットワーク通信路品質が多種多様 発信者から受信者までの通信路はそれぞれ性質が異なる 単一的品質のサービスでは資源環境の多様性に適応できない この問題には発信者側、受信者側の二つの側面が存在しています。 まず発信者は一般利用者であるため、計算機資源・ネットワーク帯域資源に限界があります。 この理由により、受信者の数が制限され多くの受信者を対象とできません。 さらに受信者に提供可能なコンテンツの品質も限定されてしまいます 受信者も同様の理由により計算機資源環に限界があり、さらに発信者までの通信路の品質が多種多様です。 この理由により、単一的な品質のサービスでは受信者も所持する資源環境の多様性に対応できません。 一般利用者を対象としたときにはこの２点を考慮する必要があります

37 既存OLMと異なる点 各ノードの情報量が異なる レイヤに分割されている マルチキャストツリーの構築が行えない 好き勝手に繋ぎ変えはできない

38 Join Procedureの流れ 新規ノードはSource Nodeに参加要求
Source Nodeは親ノードの条件を満たしたノードを含むリスト(PPL)を返す 新規ノードはPPLを利用し参加要求を送信 条件を満たし親ノードは新規ノードにデータの送信開始 新規ノードは参加完了をSource Nodeに伝える

39 メッセージ群 Rendezvous Message PPL Message Join Message Data Message
Request Accept Reject PPL Message Data Join Message Data Message Start Request Stop Request Leave Message Request Complete Prune Message Notify Message Join Complete Parent Changed Leave Progress Leave Complete LOLCASTで用いるメッセージは機能別に7つの群に分けられています それぞれのメッセージ群にはあるノードへの処理の要求やその返答を行うメッセージが用意されています Rendezvous - ツリー参加に必要となる情報のやり取り PPL - PPLの送受信を行う Join - PPに対して自身を子ノードとして受け入れる様、要求を行う Data - データの送信開始要求、送信停止要求 Leave - ツリーからの離脱を行うノードが管理する子ノードに対して離脱を広告する Prune - 親ノードに対して、自身の切り離し要求 Notify - Source Nodeに対して、マルチキャストツリーの更新を要求

40 各モジュールの役割 (1) LOLCASTプロトコル処理モジュール モジュール結合部 シミュレータモジュール プロトコルに関連する処理
メッセージに伴うデータ構造への処理 応答メッセージとその送信先をモジュール接合部に引き渡す モジュール結合部 アプリケーションモジュールとシミュレータモジュールからのメッセージのプロトコル処理モジュールの処理へ振分け メッセージヘッダにより判断 プロトコル処理モジュールからのメッセージをアプリケーションモジュール、シミュレータモジュールに引き渡す シミュレータモジュール 仮想的な複数のノードを管理 モジュール結合部からのメッセージを仮想ノードに引き渡す ノード識別子により振分け

41 各モジュールの役割 (2) アプリケーションモジュール ネットワークモジュール データのレイヤへの分割・結合 データの表示
ネットワークモジュールへのメッセージ、データの送信要求 ネットワークモジュール メッセージ、データを指定されたアドレスに対し送信 データの中身は判断しない

42 想定環境 対象規模 発信者、受信者の資源環境 数千人 個人レベルで運営される最大のコミュニティの大きさを想定 ネットワーク資源 計算機資源
多種多様であり一般利用者にとって現実的 Ex. FTTH (100Mbps), ADSL (40Mbps), Dialup (56kbps) 計算機資源 Ex. Pentium 4 2.4Ghz / 512MB, Athlon64 3Ghz / 1GB 数千を超えると、既に一般利用者ではない それほどの参加者のいるコミュニティであれば何かしらのバックアップが存在する

43 評価結果 目標環境 階層的な構造を持つデータの配信によるオーバーヘッドの増加 一般的なネットワーク・計算機資源で配信網を構築
単一のマルチキャストツリーの管理 自由な参加、脱退 資源環境に左右されず参加可能 ネットワーク層プロトコル (IPv4, IPv6), ネットワーク帯域資源, 計算機資源 受信者の要求に基づく品質 レイヤによる配信 複数品質を選択可能 受信者へ途切れのない映像を提供 最低品質のデータ保証, 輻輳回避手法 階層的な構造を持つデータの配信によるオーバーヘッドの増加 ランダムレイヤ数10000ノード参加時でも1500μsec程度 大きなオーバーヘッドとはならない

44 背景 一個人による情報発信 配信の特徴 -> 発信者, 受信者が共に一般利用者 リアルタイム性の高い映像の配信への要求
コンテンツを作成する機材が安価 一手軽に高品質なコンテンツを作成可能 文字, 画像, 音声, 映像 etc. 配信の特徴 -> 発信者, 受信者が共に一般利用者 発信者 資源(帯域等)が限られる 受信者 広域に分散 資源環境 (ネットワーク資源, 計算機資源) が多様 リアルタイム性の高い映像の配信への要求 エンドまでのネットワークが広帯域化するとともに、インターネットを介した情報発信が盛んになってきた コンテンツ業者ではなく一個人による情報発信が非常に盛んになってきた 起因 - コンテンツを作成する機材が非常に安価になってきた - ex. 映像におけるDVカムコーダ 特徴 - 文字、画像、音声、映像等の様々な表現が利用されている - ex. 小説、絵画、音楽 これらの配信の特徴は発信者、受信者が共に一般利用者であると言う点です 様々な表現を利用した配信が行われている中、 リアルタイム性の高い映像を利用した映像配信を利用した情報発信が行われていない このリアルタイム性の高いという言葉は、中継等の用途を想定しています

45 目的 一般利用者がリアルタイム性の高い映像を配信できる手法の実現 発信者 受信者 規模 配信網を自由に構築
効率的な受信者の資源環境に適応する配信 受信者 資源環境に適応したサービスを受けられる 規模 数百人を想定 *最初 このような現状を踏まえた上で、僕の研究の目的とは〜 *何故このような規模になるのか 個人が活動し参加しているグループにおいて最も大きな参加者は数百人程度であると想定 今後は数千人単位も考えているが、それ以上大規模な配信を考えた際にはもっと適切な配信手法が存在している (サービスとしてCDN等が行われている)

46 既存の配信技術 複数のUnicast IP Multicast Overlay Multicast (OLM)
1:n の n 分の帯域的な負荷が発信者に発生 多くの受信者を対象不可能 IP Multicast 様々な理由によりdeployされていない IANAへのマルチキャストアドレス申請, ISP間のポリシの違い, 全ルータのマルチキャスト対応, etc. Overlay Multicast (OLM) IP Multicastの代替技術として登場 *最初に 何故現状でリアルタイム性の高い映像配信を一般利用者は利用できないのでしょうか cf. 一般利用者による文字や画像、音声等による情報発信は現在気軽になされています cf. コンテンツ作成のデバイスも価格が下がり、作成も容易になってきています これは既存の配信技術に問題があると考えられます *複数のUnicast 1:n　例 *OLM 今日からでもdeploy可能

47 OLMとは OLMプロトコル マルチキャストに関わる機能をアプリケーションレイヤに委任
データの複製, マルチキャストルーティング, グループ管理 エンドホストによってデータ複製 グループに属するエンドホスト同士で構成する論理的なリンクを構成 エンドホスト間のユニキャスト通信 OLMプロトコル マルチキャストツリーを構成 Ex. Overcast, Narada, HMTP IPマルチキャストにおけるIPレイヤからアプリケーションレイヤに委任 IPマルチキャストにおけるルータからエンドホストにデータ複製機能を委任 この論理的なリンクはオーバーレイネットワークともよばれています *OLMプロトコル これらのOLM技術の核となり機能を提供しているのがOLMプロトコルです

48 OLMプロトコル 様々な設計目標をもつプロトコル 参加ノードを二種のトポロジに体系化 コントロール・トポロジ データ・トポロジ
Narada, HostCast, Overcast etc. 参加ノードを二種のトポロジに体系化 コントロール・トポロジ 各ノードがお互いの生存確認 トポロジの分離を回避 メッシュ データ・トポロジ コントロールトポロジの一部である事が多い データの流れを規定 ツリー Control Topology Narada 遅延を最小に抑える ALMI 遅延を最小に抑える Overcast 帯域を最大限にする それぞれのトポロジの機能を述べる Data Topology

49 既存OLM技術の問題点 単一的なデータの配信 品質毎のマルチキャストツリー 映像・音声等は品質を制御可能 複数品質でのサービス
管理のオーバーヘッド 帯域的な負荷の増加 提供できるサービスの品質が限定 然し乍ら、既存のOLM技術にも一般利用者を対象とした際の配信を考えた際に問題があります 多くの映像や音声などの配信においても受信者の環境に合わせて品質が選択できるようになっています OLMを用いてこのようなことをするためには〜

50 LOLCASTの提案 階層的な構造を持つデータの配信に適した新たなOLMプロトコルによって解決 要件
受信者の資源環境(映像品質)に対する多様な要求を満たす 一般発信者にとって現実的な資源内で提供 発信者は単一の配信網の管理により受信者の資源環境に適応した複数品質での配信が可能

51 階層的な構造を持つデータ 階層構造を持つデータを定義 特徴 レイヤ数により品質制御可能 下位のレイヤを上位のレイヤの情報を補完
Base Layerが最低品質を保証 Enhanced Layerを追加 レイヤ数により品質制御可能

52 階層的なデータ構造の例 映像 音声 情報量の異なる種類の表現 階層符号化 マルチビュー DV形式を用いたフレーム間引き マルチチャンネル
映像を階層的なデータとして扱う符号化方式 解像度/時間にスケール ex. MPEG2 SNR Scalable/Spatial Scalable Profile, JPEG2000 EBCOT (Embeeded Block Coding with Optimized Truncation) マルチビュー DV形式を用いたフレーム間引き 時間にスケール 音声 マルチチャンネル 情報量の異なる種類の表現 文字/音声/映像 軽く流す程度 EBCOT, MPEG2周りの話はしなくていい

53 プロトコル概要 データ マルチキャストツリーの構築 複数のレイヤで表現 各ノードはレイヤ数に応じた品質制御 ソースノードを頂点するツリー
階層的な構造を持つデータ 各ノードはレイヤ数に応じた品質制御 マルチキャストツリーの構築 ソースノードを頂点するツリー 多くのレイヤを所持するノード ツリーの上位に位置 親は子ノードに要求するレイヤを提供 小ノードレイヤ数を用い品質を要求 まず配信されるデータは前のスライドでお話ししたように〜 *特徴を述べる 発信者は資源環境の許す限りの最高品質の映像を最低一本、 下位のノードに対して渡してやれば受信者の資源環境に適応した配信が可能

54

55 プロトタイプ実装の設計 LOLCAST Protocol 処理部 lc_send(), lc_recv() Application
プロトコル処理部 メッセージをlc_send(), lc_recvに引き渡す その内容に従った処理をノードの保持するデータに行う lc_send(), lc_recv() 到着メッセージの振り分け プロトコル処理部との橋渡し Application lc_send()からのパケットを送出 映像データの送受信/表示 Simulator 仮想的に複数のノードを構築 仮想ノードの保持データに対して処理 Process Data Structure Based on Messages LOLCAST Protocol 処理部 lc_send(), lc_recv() Application Simulator このプロトタイプ実装というのは、プロトコルの評価を行うためのシミュレータと評価アプリケーションの事をさしています 本プロトタイプは２つのモジュールに分かれています Messagingにより処理が行われます Network Send Packet Send Video Data Process Data Structure on Virtual Nodes etc. Recv Packet Recv Video Data

56 各ノードの所持する情報 Aのノード情報 A 全ノードの情報を含むツリー構造 Cのノード情報 SourceNodeのノード情報
10 Source Node Cのノード情報 SourceNodeのノード情報 ParentNodeのノード情報 ChildNodeのノード情報のリスト B 6 C 8 Recipient Node *はじめに ノードは２種類に分けられる (Source Node / Recipient Node) それぞれ所持する情報が異なる *ノードの情報 NodeID -> 各ノードを判別するuniqueなID 6 1 ノードの情報 UniqueなNodeID 要求Layer数 Addressのリスト G F Child Node Child Node

57 各ノードの保持するデータ構造 struct nodeinfo {
　nodeid_t nodeid; /* unique id for every node */ 　unsigned char caps; /* address capability */ 　layer_t layer; /* requiring layer numbers */ 　addr_t addrs; /* list of addresses */ } プロトコルの処理部分では自身がSource NodeなのかRecipient Nodeなのかの判別を行う事ができないので 両者のノードを包む struct nodeを定義 typeでswitchしてやる struct node { 　unsigned char type; /* for switching rnode or snode*/ }

58 各ノードの保持するデータ構造 struct sourcenode { struct nodeinfo _base;
　struct nodeinfo self; /* self node info */ 　nodeseq child; /* list of child node info */ 　struct disttree *tree; /* main tree structure */ struct recipentnode { 　struct nodeinfo _base; 　struct nodeinfo self; /* self node info */ 　struct nodeinfo source; /* source node info */ 　struct nodeinfo p_parent; /* primary parent node info */ 　nodeseq child; /* list of child node info */ 　nodeseq ppl; /* primary parental list */

59 Message群 Join Message PPL Request PPL data Request Redirect Accept
Reject Data Message StartRequest StopRequest Leave Message Request Complete Prune Message Notify Message JoinComplete ParentChanged LeaveComplete 各ノード間のデータ転送以外の通信はメッセージングによって成り立っています

60 Join Procedure E A B C E D DEPTH1 B-8, C-6 DEPTH2 D-6 DEPTH1 B-8, C-6
DEPTH2 D-6, E-5 5 E 1.PPL req. 5 A 2. PPL data. CBD Rendezvous Outband communicationによりソースノードの情報(Address, MaxLayer)を得る 10 3.Join req. 5 4.Join rep. 6.Join not. 木の深さが最小 要求レイヤを満たす最小値 子ノード最大数を満たす B 8 C 6 だめだった場合を述べる Cと通信が出来なかった場合 timeoutを与え再度join procedureを実行 5 E 5.Data PARENT - A CHILD X CHILD MAX X/X LAYER - 8 PARENT - A CHILD D-6, E-5 CHILD MAX -2/3 LAYER - 6 PARENT - A CHILD D-6 CHILD MAX -1/3 LAYER - 6 6 D

61 Leave Procedure A C B D D 子が他の親からデータを受け取ったことを確認してから離脱 DEPTH1 B-8, C-6
DEPTH2 D-6 DEPTH1 B-8 DEPTH2 D-6 DEPTH1 B-8, C-6 DEPTH2 D-6 A 10 6.Prune req. 6 C 2.PPL req. 6 notC 4. Parent Changed 7.Prune complete. B 8 以上終了時のprocedure 1,6,7が無い 生存確認メッセージが一定時間届かなくなる->生存確認の取れなくなった子ノードは再度Joinを行うことで復旧 5.Leave complete 6 D 1.Leave req. 3.Data 6 D PARENT - A CHILD X CHILD MAX X/X LAYER - 8 PARENT - A CHILD D-6 CHILD MAX -1/3 LAYER - 6 PARENT - A CHILD CHILD MAX -0/3 LAYER - 6

62 ノード障害時の効率的な復旧 既存のOLMプロトコルの手法 Baseレイヤを利用した冗長化 -> Repair Procedure
再度Join Procedure Narada, ALMI コントロールトポロジ上で事前に冗長化 Hostcast Baseレイヤを利用した冗長化 効率的な復旧手法を提供 A 10 8 B C 7 *はじめに OLMはエンドホストという不安定な通信基盤上で通信を行う 予期せぬノードの切断からのマルチキャストツリーの分断を復旧させることが大きな課題 *再度Join Procedureを行う あるノードが切断し、下位に位置するノードがデータを受け取れなくなった際に、これらのノードは再び参加のProcedureを行うことで復旧 *最後に 既存のプロトコルではフルレートのデータを提供する必要がある。 本プロトコルではBaseレイヤのみを使うため帯域的な負荷を押さえつつ確実に冗長化。 6 6/10 1 6 1/10 D E F -> Repair Procedure

63 要求品質の幅を利用した輻輳回避 要求品質に幅 輻輳発生時 回復後 Ex. 4〜6レイヤ 優先的に上位レイヤを廃棄 以前のレイヤ数に復旧 A
10 Multicast Source 10/10 5-7 8-10 C B 7/10 10/10 Congestion 5/10 Drop Quality 8/10 4-6 5-8 D E 6/10

64 評価指標 Stress Delay 特定のリンクにかかる負荷 A-R1のStress = 3 R1-R2のStress = 2
R2-CのStress = 1 Delay 特定のリンクでの遅延 A-C = 18 A-B = 5 A-D = 19 A C 1 2 15 R1 R2 B 4 3 D A C B D

65 評価手法 Link Stress Recovery Latency 品質制御にかかる遅延 ノードの増加による計算量の比較
同一リンク上に流れる同一データの重複回数 Multicast (DVMRP) = 1 レイヤ数によるStressの評価も必要 Recovery Latency ノードの離脱からのマルチキャストツリー復旧時間 Baseレイヤを利用した冗長化手法 品質制御にかかる遅延 各ノードが品質制御した際に値が反映されるまでの遅延 ノードの増加による計算量の比較 Joinするノードを増加させた際に他プロトコルと比較 Simulatorを用いる

66 フレームワークの提供 送信 受信 レイヤ分割 レイヤ結合 Sender/ Receiver App. Network
EBCOT MPEG2 DV プロトコル処理モジュール プロトタイプ実装を用いた評価を行った後にこのようなフレームワークを提供できればと考えています 2つのモジュール。 プロトコルを処理する部分、フォーマット依存の処理にわけられる フォーマット依存処理部ではレイヤの分割結合といった処理をする 下位に位置するプロトコル処理モジュールはフォーマットを意識せずレイヤという単位でデータを扱うことが出来る プロトコル処理モジュール Recv Send 10/10 Relay 5/10

67 階層的な構造を持つデータ 階層構造を持つデータを定義 特徴 レイヤ数により品質制御可能 データを複数のレイヤに分割
下位のレイヤを上位のレイヤの情報を補完 Base Layerが最低品質を保証 Enhanced Layerを追加 レイヤ数により品質制御可能

68 階層的な構造を持つデータの例 階層符号化 映像 音声 情報量の異なる種類の表現 映像や音声を階層的なデータとして扱う符号化方式
解像度/品質/時間にスケール MPEG2 SNR Scalable/Spatial Scalable Profile JPEG2000 EBCOT (Embeeded Block Coding with Optimized Truncation) AAC - SSR Profile 映像 マルチビュー DV形式を用いたフレーム間引き 音声 マルチチャンネル 情報量の異なる種類の表現 文字/音声/映像

69