ｽﾗｲﾄﾞﾀｲﾄﾙなし

Size: px

Start display at page:

Download "ｽﾗｲﾄﾞﾀｲﾄﾙなし"

いとはこやぎ
5 years ago
Views:

1 画像情報特論 (9) - CDN/P2P マルチキャスト情報理工学専攻甲藤二郎 katto@waseda.jp

2 IP マルチキャスト

3 サーバマルチキャストルータホスト ( 受信端末 ) サーバマルチキャストルータ (a) ユニキャストホスト ( 受信端末 ) サーバ (b) マルチキャストスプリッタホスト ( 受信端末 ) (c) スプリッタ ( アプリケーション層マルチキャスト )

4 IP マルチキャスト (1) マルチキャストサーバマルチキャストルータマルチキャストルーティングプロトコル (S,G): マルチキャストグループ S: 送信者アドレス G: マルチキャストアドレス 2 経路の確立削除 IGMP 1 Join/Leave マルチキャストルータクラス D アドレス : ~

5 IP マルチキャスト (2) Shortest Path Tree と Shared Tree 送信者 (S) Shortest Path Tree : (S, G) フラッディング : 各ルータはパケットを受信したインタフェース以外のすべてのインタフェースにパケット転送 (S,G) エントリによる経路管理下流のルータは状況に応じて転送停止再開要求を出し経路を確定送信者 (S) Shared Tree : (*, G) コアルータコアルータ : マルチキャストグループ毎に特定のコアルータにパケットをいったん集約ここまでは (S, G) エントリによる経路管理下流のルータは必要に応じてコアルータに参加要求を出し経路を確定コアルータ以下は (*, G) エントリによる経路管理

6 DVMRP version 3 IP マルチキャスト (3) Prune メッセージ Prune ( 刈り取り ): 下流にマルチキャストグループ参加者が送信者 Prune Prune いない場合上流ルータにパケット配送停止を要求途中のルータ : (S, G) エントリ削除 Prune Graft メッセージ Graft ( 接ぎ木 ): 下流にマルチキャストグループ参加者が現れた場合上流ルータにパケット配送送信者 Graft 再開を要求 Graft 途中のルータ : (S, G) エントリ追加 Distance Vector Multicast Routing Protocol

7 IP マルチキャスト (4) PIM-SM Join メッセージ Join ( 参加 ): 下流にマルチキャストグループ参加者が送信者 Join Join 現れた場合上流ルータにパケット配送開始を要求途中のルータ : (*, G) エントリ追加コアルータ Prune メッセージ Prune ( 離脱 ): 下流のマルチキャストグループ参加者が送信者 Prune Prune 離脱した場合上流ルータにパケット配送停止を要求途中のルータ : (*, G) エントリ削除コアルータ Protocol Independent Multicast Sparse Mode

8 IP マルチキャスト (5) SSM Any Source ASM (Any Source Multicast: 従来 ) 受信者 (R2, G) 同じマルチキャストアドレス G を使用するセッションのすべての参加者にパケット配信送信者 (S1, G) 送信者 (S2, G) 同じマルチキャストグループに複数の送信者が送信可能 (many-to-many) 多人数会議 Source Specific 送信者 (S1, G) 受信者 (R2, G) 受信者 (R1, G) 送信者 (S2, G) SSM: 送信者によって限定される (S, G) セッション参加者のみにパケット配信送信者を一人に限定 (one-to-many) インターネット放送受信者 (R1, G) ( ~ ) Source Specific Multicast

9 IP マルチキャスト (6) まとめプロトコル名特徴長所短所 DVMRP 最小経路 (S, G) 送信者がパケットを投げるとフラッディングによって最小経路を確定配信 PIM-SM 送信者コアルータ : 最小経路 (S, G) コアルータ受信者 : 共有経路 (*, G) 送信者がコアルータに登録すると最小経路を確定受信者がコアルータに参加すると共有経路を確定配信 SSM 最小経路 (S, G) 受信者が送信者に subscribe すると最小経路を確定配信最小経路フラッディングが不要拡張性 1 対多の放送型アプリケーション PIM-SM とのハイブリッド構成 (PIM-SSM) フラッディングによる不要なトラヒックの増加拡張性共有経路が必ずしも最短経路にならないコアルータの決定方法プロトコルが若干複雑 ( 最短経路と共有経路の動的切替え ) 1 対多に限定 IGMP v3 が必須

10 マルチキャスト放送 (1) (1) WWW による番組案内サーバクライアント HTTP 1 ファイル要求メタファイル WWW サーバ 2 メタファイル IGMP Web ブラウザ 3 ビューアの起動 4 参加ライブ入力ストリームサーバビューアストリームファイル 5 ストリーミング IP Multicast

11 マルチキャスト放送 (2) (2) SAP による番組案内 SAP: Session Announcement Protocol 定期的に番組案内 (SDP) をマルチキャストサーバクライアント SAP (by IP Multicast) 1 番組案内ライブ入力ストリームサーバ IGMP 2 参加ビューアストリームファイル 3 ストリーミング IP Multicast RFC 2974: vic/rat/sdr

12 マルチキャスト放送の長所と短所ユニキャスト放送マルチキャスト放送長所既存のシステムの変更が不要クライアントの接続状況に合わせたふくそう制御が可能トラヒックの削減 ( 原理的に冗長なパケットは発生しない ) およびサーバ負荷の削減短所クライアントの増加に伴うトラヒックの爆発ならびにサーバ負荷の増大 ( 線形増加 ) マルチキャストルータの普及と各種設定クライアント毎のふくそう制御が困難課題マルチキャストルーティングプロトコルふくそう制御アルゴリズム例 : 階層化マルチキャスト

13 階層化マルチキャスト

14 スケーラブル符号化レイヤ 3 空間スケーラビリティ or SNR スケーラビリティ EI EP EP ベースライン I B P B P B レイヤ 1 レイヤ 2 時間スケーラビリティ空間解像度の階層化 : 空間スケーラビリティ時間解像度の階層化 : 時間スケーラビリティ SNR の階層化 :SNR スケーラビリティレイヤ 1 のみ : 低品質低レートすべてのレイヤ : 高品質高レート

15 階層化マルチキャスト (1) マルチキャストサーバマルチキャストルータ広帯域階層化されたマルチキャストストリーム = 複数のマルチキャストグループ Receiver-Driven Layered Multicast Leave 狭帯域受信者主導で各端末の帯域に合わせて階層の取捨選択 (= マルチキャストグループへの加入と離脱 ) を行う S.MaCanne et al: Receiver-driven Layered Multicast, SIGCOMM 96.

16 Join Experiment 階層化マルチキャスト (2) Join Leave ( ふくそう検出 ) バックオフを繰り返しレートを安定させる廃棄廃棄廃棄レイヤ 4 detection time Join Leave レイヤ 3 レイヤ 2 Join Join 1 回目 2 回目 join timer *= α ( バックオフ ) レイヤ 1 join timer ( レイヤ毎 ) TCP タイムアウトと同様のバックオフメカニズム

17 Shared Learning 階層化マルチキャスト (3) Join 実験の他の端末への通知 R H R L 広帯域狭帯域 R L S R L Join 実験 R L R L 端末数の増加に伴う Join 実験の回数の増加を防ぐ上流の広帯域 Join 実験と下流の狭帯域 Join 実験の結果の混同を防ぐ

18 階層化マルチキャスト (4) RLM の状態遷移図 Join 実験成功 ( レイヤ増加 ) Steady S Join 実験失敗 ( レイヤ削減 ) Hysterisis H Join 実験以外の廃棄 D Drop 遷移状態 M 廃棄率大 ( レイヤ削減 ) Measurement detection time の終了

19 CDN Content Delivery Network

20 CDN サーバの負荷分散 & 転送遅延の改善サーバ負荷の集中複数サーバによるサイト内負荷分散複数サイトによる負荷分散遅延改善サーバ群サーバ群オリジンサイト CDN オリジンサイトリモートサイト #1 接続要求 & コンテント配信インターネット接続要求インターネットクライアント遅延の増大クライアントコンテント配信リモートサイト #n サーバ群

21 サイト内負荷分散 (1) L3 スイッチサーバ群インターネット L3 スイッチミラーリングラウンドロビンミラーリングとラウンドロビンによる負荷分散 : 長所 : スイッチの負荷が軽い短所 : ミラーリングの効率が悪い ( すべてのサーバが同じデータを持つ )

22 サイト内負荷分散 (2) L4 スイッチサーバ群インターネット L4 スイッチポート番号で振り分け Web (80 番 ) ストリーミング (RTSP: 554 番 ) アプリケーション ( ポート番号 : L4 情報 ) に応じた分散サーバ配置 : 長所 : アプリケーションに応じたきめこまかい負荷分散が可能 ( 短所 : L3 スイッチよりはスイッチの負荷が大きい )

23 サイト内負荷分散 (3) L4/L7 スイッチサーバ群インターネット L4/L7 スイッチテキスト画像コンテンツ (URL) 単位の振り分けストリームコンテンツ (URL: L7 情報 ) に応じた分散サーバ配置 : 長所 : コンテンツ単位のさらにきめこまかい負荷分散が可能短所 : スイッチの負荷が大きい

24 Delayed Bound (1) サイト内負荷分散 (4) クライアント L4/L7 スイッチサーバ #1 サーバ #2 SYN/ACK SYN ACK HTTP GET SYN/ACK SYN ACK クライアントスイッチ間スイッチサーバ間で複数の TCP コネクションを終端 = Delayed Bound SYN/ACK SYN ACK HTTP GET #1 HTTP GET #2 HTTP 1.1 の例

25 Delayed Bound (2) サイト内負荷分散 (5) クライアント L4/L7 スイッチサーバ #1 サーバ #2 Data #1 Data #2 Data #1+ #2 サーバ #1 サーバ #2 からのデータを集約 = Aggregate HTTP 1.1 の例

26 サイト間負荷分散サイト間負荷分散 & 転送遅延の改善サーバ群オリジンサイトサーバ群リモートサイト #1 複数サイト ( サーバ群 ) の分散配置接続要求インターネットクライアントからの要求に応じて適切なサイトを選択誘導クライアントストリーム配信リモートサイト #n サイト間負荷分散 & 転送遅延の改善サーバ群

27 リクエストルーティング (1) DNS リダイレクション (1) CDN s DNS サーバオリジンサイトリモートサイト #1 2 DNS 要求 3 DNS 応答インターネットローカル DNS サーバ 1 DNS 要求 5 接続要求リモートサイト #n サロゲート (surrogate) 4 DNS 応答 6 ストリーミングクライアント解像度 : ドメイン単位 ( 粗い )

28 リクエストルーティング (2) DNS リダイレクション (2) DNS リダイレクション Single Reply Multiple Reply NS Redirection CNAME Redirection Object Encoding 方式 CDN 内 DNS サーバが最適サロゲートを A レコード (IP アドレス ) で返す方式 ( 例 : stream.com ) CDN 内 DNS サーバが複数のサロゲート候補を A レコードで返しラウンドロビンでサロゲートを選択する方式 ( 例 : stream.com , , ) CDN 内 DNS サーバが第三の DNS サーバに NS レコード ( ネームサーバ ) を返しその DNS サーバが最適サロゲートを A レコードで返す方式 ( 例 : stream.com server1.site1.stream.com ) CDN 内 DNS サーバが第三の DNS サーバに CNAME レコード ( エイリアス ) を返しその DNS サーバが最適サロゲートを A レコードで返す方式 ( 例 : stream.com site1.stream.com ) DNS の名前にオブジェクトのタイプ等を埋め込んでしまいそれに応じてサロゲートの IP アドレスを振り分ける方式 ( 例 : stream.com mpeg_content1.site1.stream.com )

29 リクエストルーティング (3) DNS リダイレクション + L4 スイッチ CDN s DNS サーバオリジンサイトリモートサイト #1 サロゲート (surrogate) 2 DNS 要求 3 DNS 応答インターネット 6 接続要求ローカル L4 スイッチ DNS サーバ 1 DNS 要求 5 接続要求 ( サイト選択 ) 4 DNS 応答 7 ストリーミングクライアントサロゲートの IP アドレスを返す代わりに L4 スイッチの IP アドレスを返す ( 負荷分散 )

30 リクエストルーティング (4) URL リライティング (L7 スイッチ ) CDN s L7 スイッチ 1 メタファイルレイアウト記述要求オリジンサイトリモートサイト #1 2 メタファイルレイアウト記述応答インターネット rtsp://server-n 3 接続要求リモートサイト #n サロゲート (surrogate) URL の書き換えクライアント 4 ストリーミング解像度 : クライアント単位 ( 細かい )

31 リクエストルーティング (5) URL リライティング (2) URL リライティング Header Inspection (1) Header Inspection (2) Content Modification 方式 RTSP 記述内に仮想的なサロゲートの URL を記述しておきアクセスが来たら最適サロゲートへの 302 リダイレクションコードを返す ( 例 ) 302 Moved Temporarily MIME ヘッダ内の Language Cookie 等のフィールド情報に応じて適切なサロゲートへのルーティングを行う ( 例 ) stream.com japanese.stream.com クライアントからのリクエストに応じてメタファイルやレイアウト記述ファイル内の URL フィールドを最適サロゲートの URL に書き換えて返す ( 例 ) rtsp://stream.com rtsp://site1.stream.com

32 リクエストルーティング (6) 最適サロゲートの推定方法推定方法 Proximity Measurement Surrogate Feedback 方式クライアントに最も近いサロゲートの推定方法 (1) Active Probing : ping 等のプローブパケットの利用 (2) Passive Measurement : クライアントパケットのモニタリング基準 : 遅延パケットロスホップ数等関連分野 : インターネットの帯域測定技術管理サーバとサロゲートの情報交換 : エージェントを用いた Probing 基準 : CPU 負荷インターフェース負荷コネクション数等関連分野 : 負荷分散技術

33 オーバーレイネットワーク CDN #1 リモートサイト #1 オリジンサイトリモートサイト #2 CDN #2 オリジンサイトリモートサイト #1 リモートサイト #2 クライアントから見れば CDN はひとつのサイトインターネットクライアント

34 Akamai FreeFlow (1) Origin Site L7 swtich Origin DNS with Akamizer Akamai DNS Servers オリジナルデータのミラーリング ( オフライン ) 1 ファイル要求 & 応答 3 DNS 検索 2 DNS 検索 a100.g.akamaitech.net? ak.foo.com a100.g.akamaitech.net 監視 Akamai Contents Servers rtsp://ak.foo.com/ URL ARL (Akamai Resource Locator) クライアント 4 コンテンツ配信 1 URL リライテイング 3 DNS リダイレクション

35 Akamai DNS System Akamai FreeFlow (2) High-Level DNS Servers ( 世界中に 13 台?) za.akamaitech.net zb.akamaitech.net zr.akamaitech.net Low-Level DNS Servers (50 以上 ) n1g.akamaitech.net n2g.akamaitech.net n9g.akamaitech.net Contents Servers (2000 以上 ) a0000.g.akamaitech.net a0001.g.akamaitech.net annnn.g.akamaitech.net

36 P2P (peer-to-peer)

37 P2P (1) 基本 (1) 探索発見 (2) 通信 P2P ネットワーク P2P ネットワーク探索発見通信 Peer A Peer D Peer A Peer D Peer B Peer C Peer B Peer C 従来 : 検索エンジン Web サーバ等クライアント探索発見クライアント通信

38 P2P (2) Napster (1) 登録 + 探索発見 (2) 通信管理サーバ管理サーバ探索発見 Single point of failure P2P ネットワーク P2P ネットワーク登録通信 Peer A Peer D Peer A Peer D Peer B Peer C Peer B Peer C

39 P2P (3) Gnutella (1) 探索発見 (2) 通信ブロードキャスト冗長探索発見通信 Peer A Peer B Peer A Peer B

40 P2P (4) Plaxton s Algorithm ファイル名とノードアドレスをハッシュ関数で数値化 ( ObjectID, NodeID ) ノード番号が ObjectID に等しいノードにそのファイルの保有ノード情報を登録探索発見 : ***8 **98 * の順に探索 (ObjectID = 4598 の場合 ) Node 04F8 s Routing Table 04F8 14F8 *0F8 *1F8 **08 **18 ***0 ***1 04F 問合せノード 0325 通信 ObjectID = F8 34F8 *2F8 *3F8 **28 **38 **98 ***2 *** BB8 発見 (4598, 3425) 3425 IP アドレス探索登録 ( 事前 ) CA Structured P2P

P2P (5) CAN Plaxton s Algorithm の変形拡張各ノードは d 次元空間中の特定の範囲の ObjectID を有するファイルの保有ノード情報を保持 ObjectID の d 次元空間 ObjectID 問合せノード 1 2 通信 8 11 ( 例 ) ノード6におけるルーティング :

41 P2P (5) CAN Plaxton s Algorithm の変形拡張各ノードは d 次元空間中の特定の範囲の ObjectID を有するファイルの保有ノード情報を保持 ObjectID の d 次元空間 ObjectID 問合せノード 1 2 通信 8 11 ( 例 ) ノード6におけるルーティング : 隣接 peer に限定 ObjectID に近い peer に転送探索登録 ( 事前 ) 発見 (ObjectID, 8) S.Ratnasamy et al: A Scalable Content-Addressable Network, SIGCOMM 01.

P2P (6) Chord Plaxton s Algorithm の変形拡張各ノードは 1 次元円周上の特定の範囲の ObjectID を有するファイルの保有ノード情報を保持 ( 例 ) Key (ObjectID) = 46 の探索 : ノード数 64 NodeID = 0, 4, 13, 35, 43, 50 の場合 K44~K50 N50 K51~K0 N0 発見 (K46,

42 P2P (6) Chord Plaxton s Algorithm の変形拡張各ノードは 1 次元円周上の特定の範囲の ObjectID を有するファイルの保有ノード情報を保持 ( 例 ) Key (ObjectID) = 46 の探索 : ノード数 64 NodeID = 0, 4, 13, 35, 43, 50 の場合 K44~K50 N50 K51~K0 N0 発見 (K46, N13) N4 問合せノード K1~K4 Node 4 の finger table Key 5 (=4+2 0 ) 6 (=4+2 1 ) 8 (=4+2 2 ) Interval [5,6) [6,8) [8,12) Successor (=4+2 3 ) 20 (=4+2 4 ) 36 (=4+2 5 ) [12,20) [20,36) [36,4) Key = 46 N43 K36~K43 探索登録 ( 事前 ) 通信 N13 ObjectID 46 K5~K13 Node 43 の finger table Key 44 (= ) Interval [44,45) Successor (= ) 48 (= ) [46,48) [48,51) N35 51 (= ) 59 (= ) [51,59) [59,11) 0 0 K14~K35 11 (= ) [11,43) 13 I.Stoica et al: Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, SIGCOMM 01.

43 アプリケーション層マルチキャスト (1) スプリッタサーバスプリッタホスト ( 受信端末 ) P2P (Peer-to-Peer) ユニキャストユニキャスト送信者 (S) 受信端末兼送信端末

44 アプリケーション層マルチキャスト (2) P2P マルチキャストストリームサーバ管理サーバ (2) Peer 選択ルーティングテーブル Peer (1) 接続要求 (3) 配信新ノード長所 : 簡単既存ルータの変更不要短所 : 転送トラヒックの増加経路の準最適性管理サーバの負荷検討事項 : ノードの追加と削除への対応動的な経路変更負荷分散

45 P2P 型 VoIP システム Skype (1) - 音質向上 : Global IP Sound ( 広帯域音声符号化 ) - NAT 超え : UDP TCP HTTP (80) HTTPS (443) proxy - 暗号化 : AES (Advanced Encryption Standard, 256 bit) - SkypeIn / SkypeOut : 黒電話との発着信ゲートウェイ Skype Client Skype ネットワーク電話網黒電話

46 Skype (2) システムの構成要素 Login Server Bootstrap Super Node Super Node 2 ログイン 1 問合せ 3 ユーザ探索 1 問合せ (first time) Skype Client 4 通話

47 Skype (3) Global IP Sound 広帯域音声 (16/32kHz) ~ 狭帯域音声 (8kHz)

48 Skype (4) NAT 超え Super Node 探索 Super Node (1) Public ~ Public 通話 Skype Client Skype Client (2) Public ~ NAT (3) NAT ~ NAT Super Node 探索 Super Node firewall 通話 Skype Client UDP Hole Punching Skype Client UDP TCP HTTP (80) HTTPS (443) proxy

ｽﾗｲﾄﾞﾀｲﾄﾙなし

ｽﾗｲﾄﾞﾀｲﾄﾙなし画像情報特論 (10) - その他の話題 (1) マルチキャスト CDN P2P 2004.07.02 情報ネットワーク専攻甲藤二郎 E-Mail: katto@waseda.jp マルチキャストマルチキャストサーバルータホスト ( 受信端末 ) サーバマルチキャストルータ (a) ユニキャストホスト ( 受信端末 ) サーバ (b) マルチキャストスプリッタホスト ( 受信端末 )

ｽﾗｲﾄﾞ ﾀｲﾄﾙなし

ｽﾗｲﾄﾞﾀｲﾄﾙなし