Document

物理網構成を考慮したハイブリッド型
P2P 動画像ストリーミング配信機構の提案と評価
大阪大学大学院情報科学研究科
＊末次信介
若宮直紀
村田正幸
NEC インターネットシステム研究所
小西弘一
Sep. 22, 2004
谷口邦弘
ソサイエティ大会
1
はじめに





研究の背景
研究の目的
提案機構の紹介
シミュレーションによる評価
まとめと今後の課題
Sep. 22, 2004
ソサイエティ大会
2
研究の背景

動画像ストリーミング配信の普及
• 動画像データを受信しながら再生
• 映画の予告編、ニュース映像などの配信

P2P 技術の発展
• P2P マルチキャストによる動画像配信
• サーバの負荷を軽減
サーバ
サーバ
クライアント
Sep. 22, 2004
配信ツリーの
構築
ピア
ソサイエティ大会
P2P マルチキャスト
3
研究の背景

適切な配信ツリーを構築するには？
• 遅延や帯域など、物理網特性を計測



長時間の観測が必要
観測のために新たにネットワークに負荷をかける
企業や大学などのネットワークでは……
• 組織構成にもとづいた物理網が構成されている



Sep. 22, 2004
支社や部署、学部や学科など
物理網特性の計測が不要
簡単に、かつ迅速に配信ツリーを構築
ソサイエティ大会
4
研究の目的

組織構成にもとづいて階層化されたネットワークを
対象とした動画像ストリーミング配信機構を提案
• 数千、数万のユーザを有する
• 実用的な配信機構を提案

提案機構の目標
• サーバやサーバ近傍の負荷集中の軽減
• ネットワークの負荷の軽減


物理網上で遠く離れたピアが繋がるのを避ける
同じデータが同じリンクを往復するのを避ける
• 再生開始までの待ち時間を短縮
• 障害による、再生の途切れ時間を短縮
Sep. 22, 2004
ソサイエティ大会
5
動画像ストリーミング配信機構の概観
支社
本社
サブネット代表 (STS)
部署
部署
拠点
スケジュール
サーバ (SS)
サブネット
ツリーサーバ
(GTS)
動画像サーバ
(ORG)
サブネット
拠点
部署
拠点代表 (LTS)
Sep. 22, 2004
サブネット
普通のピア（NP）
支社
ソサイエティ大会
拠点
支社
6
動画像ストリーミング配信機構の概要
１．セグメント受信スケジュール決定アルゴリズム
• ピラミッドブロードキャスティングを用いる

再生開始までの待ち時間を短縮
２．配信ツリー構築機構
• P2P マルチキャストを用いた動画像配信ツリー構築

サーバの負荷を軽減
• 物理網構成にもとづく階層化

ネットワークやピアの負荷を軽減
３．障害回復機構
• 分散自律制御により短時間で障害回復

Sep. 22, 2004
障害時の動画像の再生の途切れを削減
ソサイエティ大会
7
１．セグメント受信スケジュール決定アルゴリズム
ピラミッドブロードキャスティング
１
：
２
：
４
再生速度 b
動画像データ
ピア
セグメント
再生→
ｔ
ｔ
スケジュール
サーバ（SS）
スロット
転送速度2b
動画像サーバ
（ORG）
各セグメントを、異なるチャネルで繰り返し配信
Sep. 22, 2004
ソサイエティ大会
8
２．配信ツリー構築機構
セグメント、スロットごとに配信ツリーを構築
Sep. 22, 2004
ソサイエティ大会
9
２．配信ツリー構築機構
拠点間ツリーの構築
本社
拠点代表（LTS）
この拠点での
初めての参加要求
参加要求
拠点B
ツリーサーバ
（GTS）
動画像サーバ
（ORG）
接続要求
動画像サーバのアドレスを通知
拠点代表
拠点C
拠点A
Sep. 22, 2004
ソサイエティ大会
10
２．配信ツリー構築機構
拠点間ツリーの構築
本社
子のアドレスを通知
拠点B
ツリーサーバ
（GTS）
動画像サーバ
（ORG）
拠点C
祖先リスト:
動画像サーバ → 拠点B
子の数に制限
拠点A
ファンアウト数＝２
Sep. 22, 2004
紹介された子に接続できない場合は、さらに
その子を紹介してもらう
ソサイエティ大会
11
ピアは、紹介されたピアのリストを保存する
２．配信ツリー構築機構
サブネット間ツリーの構築
拠点代表（LTS）
その拠点の
拠点代表のアドレスを通知
サブネットB
ツリーサーバ
（GTS）
参加要求ファンアウト数を考慮
接続要求
動画像サーバ
（ORG）
サブネットC
サブネット代表（STS）
サブネットＡ
このサブネットでの
初めての参加要求
Sep. 22, 2004
拠点Ａ
ソサイエティ大会
サブネットD
12
２．配信ツリー構築機構
サブネット内ツリーの構築

第１セグメントと第２セグメント以降で異なる
サブネット代表（STS）
ツリーサーバ
（GTS）
そのサブネットの
サブネット代表のアドレスを通知
ツリーサーバを介さず
前セグメントのサブネット代表へ
ファンアウト数を考慮
普通のピア（NP）
第２セグメント以降の場合
第１セグメントの場合
Sep. 22, 2004
ソサイエティ大会
サブネットA
13
３．障害回復機構
同じ階層内での障害回復

障害
ファンアウト数
の制限
• ピアの離脱



様々な原因
様々なタイミング
同じ階層内での障害回復
• 各ピアは、その階層の
ツリーの根までの情報を
持っている
• どの階層のツリーでも同じ



Sep. 22, 2004
接続要求
障害回復
拠点間ツリー
サブネット間ツリー
サブネット内ツリー
ソサイエティ大会
14
３．障害回復機構
異なる階層間での障害回復

祖先の情報を持っていない
ツリーサーバ
（GTS）
障害回復
昇格
参加要求
障害回復
障害回復:
祖先の情報があるときは祖先に接続要求
サブネットA
祖先の情報がないときはツリーサーバに参加要求
Sep. 22, 2004
ソサイエティ大会
15
シミュレーション

評価項目
•
•
•
•

サーバやピアの負荷
再生開始までの待ち時間
障害回復時間
再生の途切れ時間
シミュレーション条件
• 拠点数、拠点内サブネット数: 5
• 1 秒間に平均 30 のピアが一様分布で到着

•
•
•
•
ある時刻に配信ツリーに参加しているピア数: 平均 2,790
ピア間の転送遅延: 20 （ミリ秒）
サーバ・ピア間の転送遅延: 200 （ミリ秒）
ファンアウト数: 3
いずれのピアも毎秒 0.004 の確率で離脱

およそ 47% のピアが最後まで動画像を受信
• 動画像の長さ: 186 （秒）
• 5つのセグメント（6秒、12秒、24秒、48秒、96秒）
Sep. 22, 2004
ソサイエティ大会
16
再生開始までの待ち時間の分布
累
積
確
率
再生開始までの待ち時間 [sec]
平均 2.94 秒
最大でも 6 秒未満
Sep. 22, 2004
ソサイエティ大会
17
再生の途切れ時間の分布
累
積
確
率
再生の途切れ時間 [sec]
およそ 0.5 % のピアだけが途切れを経験
最大でも途切れ時間は 1 秒以下
Sep. 22, 2004
ソサイエティ大会
18
まとめと今後の課題

動画像ストリーミング配信機構の提案



セグメント受信スケジュール決定アルゴリズム
配信ツリー構築機構
障害回復機構
• 提案機構により、再生開始までの待ち時間、
再生の途切れ時間が十分小さい動画像
ストリーミング配信が提供できることを示した

問題点と今後の課題
• ツリーサーバに負荷が集中している
• 冗長な拠点間ツリーが構築されている

Sep. 22, 2004
物理網上で遠く離れたピアが繋がっている
ソサイエティ大会
19

ご静聴ありがとうございました。
Sep. 22, 2004
ソサイエティ大会
20

Download Report