放送通信融合環境における帯域幅を考慮したスケジューリング手法

(1)

DEIM Forum 2016 B8-4

放送通信融合環境における帯域幅を考慮したスケジューリング手法

後藤佑介

†

義久

智樹

††

†

岡山大学大学院自然科学研究科〒 700–8530 岡山県岡山市北区津島中 3–1–1

††

大阪大学サイバーメディアセンター〒 567-0047 大阪府茨木市美穂ヶ丘 5–1

E-mail:

†

††

あらまし近年の放送通信融合環境の普及にともない，放送と通信を同時に利用して，音声や映像といった連続メディ

アデータを配信する技術への注目が高まっている．放送通信融合環境における連続メディアデータの配信では，クラ

イアントは，放送チャネルを用いた放送型配信でデータの一部を受信しながら，通信チャネルを用いたオンデマンド

型配信で残りの部分を受信することで，データ再生時に発生する待ち時間を短縮できる．我々の研究グループでは，

放送型配信およびオンデマンド型配信それぞれについて，データを複数の部分に分割した上でどのようにクライアン

トに配信するかを決定するスケジューリング手法を提案してきた．本研究では，放送通信融合環境において，帯域幅

を考慮したスケジューリング手法を提案する．提案手法では，サーバは，クライアントの再生レートとサーバが使用

できる放送チャネルの帯域幅を考慮して配信スケジュールを作成することで，クライアントは再生時の待ち時間を既

存手法に比べて短縮できる．

キーワード

放送通信融合環境，スケジューリング手法，帯域幅

1. はじめに

デジタルネットワーク技術の急速な発達[1]により，音楽や映像といった連続メディアデータを受信しながら再生するストリーミング配信が注目されている．ストリーミング配信では，クライアントが連続メディアデータの受信をサーバに要求すると，サーバは連続メディアデータを複数の部分（以下，セグメント）に分割してクライアントに配信する．連続メディアデータは再生中に途切れが発生しない一続きのデータであるため，サーバは，クライアントが最後まで途切れなく再生できるようにデータを配信することが重要になる．クライアントは，現在再生しているセグメントの再生終了時刻までに次のセグメントの受信を完了できない場合，再生が中断する．そこで，この待ち時間を短縮するさまざまな手法が提案されている[2], [3], [4], [5], [6], [7]．これらの手法は，放送を用いる手法（以下，放送型配信）と通信を用いる手法（以下，オンデマンド型配信）の二つに分類される．放送型配信では，サーバは一定の帯域幅で複数のクライアントにデータを繰返し配信することでサーバの負荷を軽減できるが，クライアントは受信を要求してから再生を開始するまで待つ必要がある．一方，オンデマンド型配信では，サーバはクライアントの視聴要求に応じてセグメントを送信することで，クライアントは所望するデータをすぐに再生できる．しかし，サーバはデータを要求するクライアントごとに送信する帯域幅を確保するため，クライアントの視聴要求が集中する人気番組を送信する場合，必要となる帯域幅が使用できる帯域幅を上回り，クライアントの待ち時間は長大化する．放送と通信それぞれのシステムにおける問題点は，相補的な関係である．そこで，サーバが放送型配信とオンデマンド型配信の両方を使用してクライアントにデータを配信する環境（以下，放送通信融合環境）に関する研究が行われている．放送通信融合環境では，クライアントは放送チャネルと通信チャネルの両方を用いてサーバからデータを受信することで，待ち時間を短縮する．これまでの研究では，サーバは放送型配信で連続メディアデータを構成する複数のセグメントを順番に繰返し配信し，クライアントは，受信を要求した時刻より後のセグメントを放送型配信で受信しながら，受信要求時刻より前に配信していた前半部のセグメントをオンデマンド型配信で受信することで，待ち時間を短縮していた．しかし，サーバが使用できる帯域幅に上限があり，連続メディアデータの配信に必要な帯域幅を下回る場合，セグメントの配信時間が再生時間を上回るため，セグメントの再生が終了するたびに中断が発生し，待ち時間は長大化する．そこで本研究では，放送通信融合環境において，帯域幅を考慮したストリーミング配信の待ち時間短縮手法を提案する．提案手法では，サーバが使用できる帯域幅に制限がある状況で，連続メディアデータを複数の部分に分割して，論理的に分割した複数の放送チャネルで配信する分割放送型配信を用いる．その上で，放送チャネルで配信するセグメント数を決定するスケジューリング手法を用いることで，これまでの配信方式に比べて待ち時間を短縮する．

2. 放送通信融合環境

2. 1 概要対象とする放送通信融合環境について述べる．放送通信融合環境におけるストリーミング配信システムでは，クライアントは，放送チャネルと通信チャネルを両方使用してデータを受信する．1.で説明したように，セグメントはデータの分割単位であり，クライアントはセグメントごとにデータを再生する．

(2)

図 1 オンデマンド型配信図 2 放送型配信放送通信融合環境で利用される放送システムで行われるストリーミング配信は，さまざまな方式が考えられる．本研究では，待ち時間を短縮するニアオンデマンド型のストリーミング配信を想定する．ニアオンデマンド型では，複数の放送チャネルを用いて各チャネルでセグメントを繰返し配信する分割放送型配信を用いることで，クライアントが最初のセグメントを受信できる機会が増え，待ち時間を短縮できる．分割放送型配信は，電波放送やIPマルチキャストといった放送形態を想定しており，マルチキャストによる比較的単純な放送でも利用できる．一方，通信システムで行われるストリーミング配信もさまざまな方式が考えられる．本研究では，サーバ・クライアント型のストリーミング配信を想定して，サーバはクライアントの要求ごとに帯域幅を確保した上で，クライアントが所望するセグメントを順番に送信する．

3. データ配信方式

3. 1 サーバ・クライアント間のデータ配信従来のサーバとクライアントで構築されたネットワーク環境におけるデータ配信方式は，オンデマンド型配信と放送型配信の二つがある．以下で順番に説明する． 3. 2 オンデマンド型配信オンデマンド型配信でサーバが動画データを配信する様子を図1に示す．オンデマンド型配信では，サーバはデータの受信を要求するクライアントごとにチャネルを設定し，チャネルの帯域幅を確保してデータを配信する．一方で，クライアントの数に比例して，サーバの処理負荷や通信に必要となる帯域幅は Internet 通信サーバ配信側クライアント放送サーバ Communication Broadcasting クライアントクライアントクライアント図 3 ハイブリッド型配信増加する．通信に必要となる帯域幅が使用できる帯域幅を上回ると，サーバにデータの受信を要求する新たなクライアントに対して帯域幅を確保できず，待ち時間は長大化する． 3. 3 放送型配信放送型配信でサーバがデータを配信する様子を図2に示す．放送型配信は，マルチキャストを用いて，あらかじめ指定した複数のクライアントに同じ動画データをまとめて配信する方式である．サーバは一定の帯域幅でデータを配信でき，クライアントの数が増加しても配信サーバの処理負荷や使用する帯域幅の増加を抑制できる．一方で，クライアントは，データの受信を要求してから再生を開始するまでの間に待ち時間が発生する． 3. 4 ハイブリッド型配信放送通信融合環境において，放送チャネルと通信チャネルを同時に利用してクライアントにデータを配信するハイブリッド型配信について説明する．ハイブリッド型配信のネットワーク構成を図3に示す．ハイブリッド型配信のネットワークは，サーバとクライアントで構成される．ハイブリッド型配信では，サーバはデータを複数のセグメントに分割して，クライアントに配信する．ハイブリッド型配信では，サーバはネットワークに接続しているすべてのクライアントを管理し，放送チャネルを用いてすべてのクライアントにデータを繰り返し配信する．また，クライアントがサーバにデータを要求すると，サーバはデータを複数のセグメントに分割した上で，通信チャネルを用いてクライアントに送信する．このときクライアントは，サーバからセグメントを受信してバッファに保存し，データの最初のセグメントを受信すると，再生を開始できる． 3. 5 データ配信方式の比較 3. 2, 3. 3,および3. 4節で説明した配信方式の特徴を表1に示す．オンデマンド型配信では，サーバはクライアントからの受信要求に応じて直ちにクライアントにデータを送信できるが，クライアント数に比例してサーバの処理負荷や使用する帯域幅は増加する．次に，放送型配信では，サーバの処理負荷や使用する帯域幅の増加を抑制できるが，クライアントのデータ受信時に待ち時間が発生する．最後に，ハイブリッド型配信で

(3)

表 1 各配信方式の特徴配信手法長所短所オンデマンド型配信クライアントの受信要求に応じて_{直ちに送信可能} クライアント数に比例して処理負_{荷や使用する帯域幅が増加} 放送型配信サーバの処理負荷や使用する帯域_{幅の増加を抑制} クライアントのデータ受信時に待_{ち時間が発生} ハイブリッド型配信オンデマンド型配信および放送型_{配信の長所をもつ．} データの配信処理が複雑Ｃ1 ・・・Ｓ2 ・・・クライアントが再生している様子・・・ Time Ｓ1 (5.0 Mbps) (0.83 Mbps) 153.9 秒・・・Ｓ₃ Ｓ1 Ｓ₅ Ｓ6 Ｓ₄ ・・・・・・・・・・・・ t0 Ｓ6 Ｓ₄ Ｓ2 Ｓ₃ Ｓ1 Ｓ2 Ｓ₃ Ｓ1 Ｓ2 Ｓ1 Ｓ2 Ｓ1 Ｓ1 Ｓ1 再生開始待ち時間 t2 Ｓ5 t1 240秒Ｃ2 Ｃ3 Ｃ4 Ｃ5 Ｃ6 ・・・・・・・・・・・・Ｓ2 Ｓ3 Ｓ4 Ｓ5 Ｓ6 (0.83 Mbps) (0.83 Mbps) (0.83 Mbps) (0.83 Mbps) (0.83 Mbps) 図 4 途切れが発生しない配信スケジュール例（BE-AHB 法）は，サーバがオンデマンド型で送信しながら放送型で配信することで，オンデマンド型配信と放送型配信の長所をもつ．一方で，データの配信処理は複雑になるため，サーバが使用できる帯域幅や再生レートといったネットワーク条件を考慮したスケジューリング手法が必要となる．

4. 関連研究

4. 1 スケジューリング手法 4. 1. 1 分割放送型配信放送型配信では，クライアントがデータの受信をサーバに要求してから受信を完了するまでの間に待ち時間が発生する．受信要求からデータの最初の部分を受信するまでの間は受信開始を待つため，データを繰り返して放送している場合，この待ち時間は，連続メディアデータの受信時間分発生する．例えば，受信に60分かかる連続メディアデータを1つのチャネルで受信する場合，60分の待ち時間が発生する．このため，一般的には，連続メディアデータを分割して，初めの部分を頻繁に放送することで，待ち時間を短縮している．このような放送形式を分割放送型と呼ぶ．分割放送型では，連続メディアデータをいくつかのセグメントに分割し，複数の放送チャネルを用いて放送する．サーバは，データの初めの部分のセグメントを頻繁に放送することで，クライアントの待ち時間を短縮する．このような放送形態は，電波放送や帯域が保証された IPマルチキャストといった放送を想定している．分割放送型では，クライアントのデータ再生中に途切れが発生しないようにスケジューリングすることが重要である．これまでの研究では，クライアントが使用できる帯域幅を用いて，複数のチャネルから同時に受信することで，途切れのない再生を実現していた．このことについて，以下に説明する．クライアントがデータの受信要求を出してから再生が終了するまでの様子を図4に示す．理解しやすい例として，ここでは，サーバがBE-AHB法[8]を用いて6分割し，計6つのチャネルで放送する場合を考える．映像データはMPEG-2で符号化されており，データの再生時間は240秒とする．BE-AHB法では，各チャネルの帯域幅はすべて等しい．使用するチャネルを C1,· · · , C6とし，使用できる帯域幅を5.0 Mbpsとすると，各チャネルの帯域幅はC1=· · · = C6= 5.0/6 = 0.83 Mbpsとなる．再生レートは5.0 Mbpsとする．S1は，連続メディアデータをS1,· · · , S6に6分割したときの1番目の部分であり，再生時間が25.5秒のデータである．また，S2は再生時間が29.8 秒となり，S6は再生時間が55.3秒のデータとなる．S1,· · · , S6 のデータサイズは，数式で与えられる[8]．C1では，再生時間が25.5秒で再生レートが5.0 MbpsのS1を0.83 Mbpsの帯域を用いて放送するため，25.5× 5.0/0.83 = 153.9秒ごとに繰り返して放送する．同様に，C2では29.8× 5.0/0.83 = 179.5 秒，C6では55.3× 5.0/0.556 = 333.1秒ごとに繰り返して放送する．BE-AHB法の場合，最初のセグメントの受信が完了した後で再生を開始するため，6分割して放送する場合の待ち時間はS1の受信時間のみとなり，153.9秒となる．分割せずに放送する場合，再生時間が合計240秒で再生レートが5.0 Mbpsのデータを5.0 Mbpsの帯域を用いて放送するため，240秒ごとに繰り返して放送することになり，待ち時間は240秒となる．このため，6分割したときの平均待ち時間は，分割していない場合に比べて(240− 153.9)/240 × 100 = 35.9%短縮できる． 4. 1. 2 放送通信融合環境放送通信融合環境において，待ち時間を短縮する研究はいく

つか行われている．Uniﬁed Video-on-Demand (UVoD) [9]法

は，複数の放送チャネルを使用して，同じデータを繰り返し放送する．チャネルごとにデータの最初の部分の放送開始時刻をずらすことで，クライアントが再生を開始できる機会を増加させ，待ち時間を短縮する．また，待ち時間をより短縮するために，次の放送開始時刻までの待ち時間が長い場合，もしくはある再生端末が要求したデータを別の再生端末がもっているとき，通信帯域を使用してデータをもっている端末からユニキャストで受信できる．

Super-Scaler VoD [10]法は，UVoD法の改良版である．データの最初の部分が放送されるまでの時間があらかじめ設定した待ち時間より長い場合，同じデータを要求している複数の再生端末にマルチキャストすることで，データを配信する．サーバは一度ですべてのクライアントにデータを配信できるため，人

(4)

向上する．

4. 1. 3 ハイブリッド型配信

価

6. 1 評価環境提案手法DHB法の性能評価を行う．ユーザが連続メディアデータの視聴を要求してから再生が開始されるまでの待ち時間が短いほど，ユーザは満足する．一方で，再生開始待ち時間を設定して放送と通信の両方でデータを受信することで，サーバの処理負荷を軽減できる．本節では，既存手法と比べてDHB 法の待ち時間が短縮されることを示し，DHB法の有効性を示す．評価は計算機シミュレーションで行った．初めに，DHB法と既存のスケジューリング手法である BE-AHB法を用いて，使用できる帯域幅とセグメント数の変化に応じた待ち時間の変化を示す．次に，放送チャネルのデータ配信割合の変化について評価する． 6. 2 待ち時間使用する帯域幅や分割するセグメント数に応じて待ち時間が変化するため，平均待ち時間の長さを考慮したうえで，使用する帯域幅を決定することが考えられる．そこで，帯域幅を変化させた場合の平均待ち時間の評価を行った．使用する帯域幅とセグメント数をそれぞれ変化させた場合の評価結果を図7, 8に示す．横軸は，図7では使用する帯域幅，図8ではセグメント数である．縦軸は，待ち時間である．図7で用いるセグメント数は5，図8で用いる放送チャネルの帯域幅は 12.5 Mbpsとする．“DHB”は，提案手法 DHB法の場合，“BE-AHB”は，既存手法BE-AHB法の場合である．図7より，帯域幅の増加にともない待ち時間は短縮する．使用できる帯域幅が11.5 Mbps未満の場合，BE-AHB法で発生する待ち時間は再生開始待ち時間より長くなる．一方で，提

(6)

図 7 帯域幅と待ち時間図 8 セグメント数と待ち時間案手法では，再生開始待ち時間を一定値以下にすることで， BE-AHB法に比べて待ち時間を短縮できる．また，図8では，セグメント数が 1から3の場合，BE-AHB法で配信するS1 のデータサイズは大きくなり，S1の受信時間は再生開始待ち時間より長くなる．一方で，DHB法では，通信チャネルで残りのデータを配信することで，再生開始待ち時間を一定値以下にできる．以上より，使用できる帯域幅とセグメント数を考慮することで，実際の配信サービスで想定される再生開始待ち時間を算出できることが分かる． 6. 3 データ配信割合 S1の放送周期が再生開始待ち時間より長くなると，通信チャネルでデータを配信する割合は大きくなる．クライアントのデータ要求頻度に応じて放送と通信でデータを配信する割合を決定することは重要である．そこで，使用する帯域幅とセグメント数をそれぞれ変化させた場合について，データ配信割合の評価結果を図9, 10に示す．横軸は，図9では使用する帯域幅，図10ではセグメント数である．縦軸は，放送チャネルのデータ配信割合である．再生開始待ち時間は30秒とし，図9で用いるセグメント数は5，図10で用いる放送チャネルの帯域幅は12.5 Mbpsとする．図9より，使用する帯域幅の増加にともない，放送チャネルで配信するデータの割合は増加する．また，帯域幅が13 Mbps 以上の場合は，すべてのデータサイズを放送チャネルで配信しても再生開始待ち時間を 30秒未満に抑えることができる．また，図10では，セグメント数が3以下の場合，放送チャネルで配信するデータサイズの割合は41.7%から86.0%の幅とな図 9 帯域幅と放送チャネルのデータ配信割合図 10 セグメント数と放送チャネルのデータ配信割合る．再生開始待ち時間に応じて放送チャネルで配信するデータの残りを通信チャネルで配信する場合，データの受信を要求するクライアントが増加すると，配信に必要となる帯域幅が増加する．このため，クライアントの要求頻度を考慮して通信チャネルの帯域幅やセグメント数を設定することで，通信チャネルで配信するデータサイズを決定できることが分かる．

7. おわりに

放送通信融合環境における帯域幅を考慮したスケジューリング手法として，Division-based Hybrid Broadcasting (DHB)

法を提案した．提案手法では，サーバが使用できる帯域幅に制限がある状況で，分割放送型でデータを配信することで，放送チャネルを用いてできるだけ多くのデータを配信する．また，再生開始待ち時間を事前に設定し，途切れのない再生に必要なセグメントの受信時間が再生開始待ち時間を上回る場合は，通信チャネルを用いて配信することで，再生開始待ち時間が一定値以下になるようにスケジューリングする．評価の結果，DHB 法は既存のスケジューリング手法にくらべて待ち時間を短縮できることを確認した．今後の予定として，複数の連続メディアデータを配信する場合のスケジューリング手法や，データを選択して視聴する選択型コンテンツ[13]を用いた場合のスケジューリング手法が考えられる．

謝

辞

本研究の一部は，JSPS科研費26730059，15H02702，（公財）

(7)

ウエスコ学術振興財団，ならびに総務省戦略的情報通信研究開発推進事業（SCOPE）による成果である．ここに記して謝意を表す．文献 [1] 総務省，“情報通信白書平成 27 年版，” 総務省（オンライン），入手先〈http://www.soumu.go.jp/johotsusintokei/ whitepaper/ja/h27/index.html〉（参照 2016-01-07）． [2] Y. Guo, K. Suh, J. Kurose, and D. Towsley, “A

Peer-to-Peer on-demand streaming service and its performance eval-uation,” Proc. of 2003 IEEE International Conference on Multimedia & Expo (ICME 2003), 2003.

[3] D. Tran, K. Hua, and T. Do, “Zigzag: an eﬃcient peer-to-peer scheme for media streaming,” Proc. of 22nd IEEE INFOCOM Conference, 2003.

[4] B. Cohen, “Incentives build robustness in BitTorrent,” Proc. of 1st Workshop on Economics of Peer-to-Peer Sys-tems, 2003.

[5] Y. Guo, K. Suh, J. Kurose and D. Towsley, “P2Cast: Peer-to-peer Patching Scheme for VoD Service,” Proc. of 12th International Conference on World Wide Web (WWW), pp.301-309, 2003.

[6] D. Xu, M. Hefeeda, S. Hambrusch and B. Bhargava, “On peer-to-peer media streaming,” Proc. of 22nd Inter-national Conference on Distributed Computing Systems (ICDCS2002), vol.1, pp.363-371, 2002.

[7] P. Shah and J.-F. Paris, “Peer-to-Peer Multimedia Stream-ing UsStream-ing BitTorrent,” Proc. of 26th International Per-formance of Computers and Communication Conference (IPCCC 2007), pp.340-347, 2007.

[8] 義久智樹，塚本昌彦，西尾章治郎, “再生単位を考慮したスケジューリング手法における使用チャネル数について，” 日本データベース学会 Letters，vol.4，no.3，pp.5-8, 2005．

[9] J.Y.B. Lee, “UVoD: An Uniﬁed Architecture for Video-on-Demand Services,” IEEE Communication Letters, vol.3, Is-sue 3, pp.277-279, 1999.

[10] J.Y.B. Lee and C.H. Lee, “Design, Performance Analysys, and Implementation of a Super-Scalar Video-on-Demand System,” IEEE Trans. Circuits and Systems for Video Tech-nology, vol.12, Issue 11, pp.983-997, 2002.

[11] T. Taleb, N. Kato, and Y. Nemoto, “Neighbors-Buﬀering-Based Video-on-Demand Architecture,” Signal Processing, Image Communication, vol.18, Issue 7, pp.515-526, 2003. [12] 後藤佑介，義久智樹，金澤正憲:, “異種クライアント環境におけ

る連続メディアデータ放送のための待ち時間短縮手法，” 電子情報通信学会論文誌 D, vol.J91-D, no.03, pp.667-676, 2008. [13] Y. Gotoh, T. Yoshihisa, M. Kanazawa, and Y. Takahashi,

“A Broadcasting Scheme for Selective Contents Considering Available Bandwidth,” IEEE Trans. Broadcasting, vol.55, Issue 2, pp.460-467, 2009.

[14] 後藤佑介，義久智樹，金澤正憲, “選択型コンテンツのオンデマンド配信における待ち時間短縮のためのスケジューリング手法，” 情報処理学会論文誌，vol.49, no.2, pp.716-726, 2008. [15] Y. Gotoh, K. Suzuki, T. Yoshihisa, and M. Kanazawa,

“A Scheduling Method to Reduce Waiting Time for P2P Streaming Systems,” Journal of Mobile Multimedia, vol.5, no.3, pp.255-270, 2009. [16] 木村明寛，後藤佑介，谷口秀夫, “動画データを分割配信するシステムの実現と評価，” 電子情報通信学会論文誌 B，vol.J96-B， no.10，pp.1217-1225, 2013. [17] 藤田拓郎，後藤佑介，“スケジューリング手法を用いた選択型コンテンツの放送型配信システムの実現と評価，” 第 14 回情報科学技術フォーラム (FIT2015), 第 4 分冊, pp.5-12, 2015. [18] 義久智樹，金澤正憲, “選択型コンテンツの放送型配信におけるスケジューリング手法，” 情報処理学会論文誌，vol.47，no.12， pp.3296-3307, 2006．

[19] Y. Gotoh,, T. Yoshihisa, M. Kanazawa, and Y. Takahashi, “A Broadcasting Scheme for Selective Contents Considering Available Bandwidth,” IEEE Trans. Broadcasting, vol.55, Issue 2, pp.460-467, 2009.

[20] Y. Gotoh, T. Yoshihisa, H. Taniguchi, and M. Kanazawa, “Brossom: A P2P Streaming System for Webcast,” Journal of Networking Technology, vol.2, Issue.4, pp.169-181, 2011. [21] 尾崎健志, 後藤佑介, “放送通信融合環境におけるデータ配信システムの設計と実装,” 情報処理学会研究報告 (マルチメディア通信と分散処理研究会 2015-DPS-164), vol.2015-DPS-164, no.3, pp.1-8, 2015.

放送通信融合環境における帯域幅を考慮したスケジューリング手法

DEIM Forum 2016 B8-4