DEIM Forum 2017 E1-1

分割放送型配信における待ち時間算出式を用いた
スケジューリング手法の実現と評価
井上 祐輔†

木村 明寛†

後藤 佑介†† 岡山大学大学院自然科学研究科 〒 700-8530 岡山県岡山市北区津島中 3-1-1
E-mail: †inoue-y@mis.cs.okayama-u.ac.jp, gotoh@cs.okayama-u.ac.jp
あらまし

多数の視聴者に特定の動画データを配信する方法として，動画データを複数の部分に分割して複数のチャネルで配信する分割放送型配信が提案されている．分割放送型配信では，分割した動画データの各部分をどのチャネ
ルでどの時間帯に配信するかを定めた配信スケジュールを作成する必要がある．本研究では，遺伝的アルゴリズムを用いて，ロード時間と途切れ時間の合計で求められる待ち時間の値が最小になるように動画データの分割比率を決定することで，分割放送型配信の環境に応じて待ち時間を最短にするスケジューリング手法を提案する．また，我々の研究グループで実現している分割放送型配信システム上に提案手法を導入し，シミュレーション環境，および計算機
ネットワーク環境における評価結果を比較することで，スケジューリング手法の有用性を確認する．
キーワード

分割放送型配信，スケジューリング手法，待ち時間

1. は じ め に

再生中に発生する途切れ時間の合計である待ち時間が最短になる動画データの分割比率を決定するスケジューリング手法を提近年，Netflix，およびアマゾン・プライムビデオといったユ

案する．提案手法では，遺伝的アルゴリズムを用いて動画デー

ニキャストを利用した動画配信サービス (Video on Demand)

タの分割比率を決定することで，配信条件が変化しても待ち時が普及している．また，IP マルチキャストを利用した 4K 映像

間は最短となる．シミュレーション環境における評価では，提配信サービスを検討する共同実験 [1] が進んでおり，動画デー

案手法による待ち時間の短縮効果を確認する．また，これまで

タの配信方法に注目が集まっている．

に実現してきた分割放送型配信システムに提案手法を導入し，本研究では，動画データの配信方法の一つである放送型配信について考える．多数の視聴者に同じ動画データを配信する放送型配信では，動画データの配信時刻を定めたタイムテーブル
に従って動画データを配信することで，クライアントの受信要求に応じて動画を配信する Video on Demand (以下，VoD) に計算機ネットワーク環境における提案手法の評価を行い，有用性を確認する．

2. 動画データの配信方式
2. 1 VoD

比べ，サーバは処理負荷を抑制できる．一方で，サーバは事前サーバとクライアントが一対一で通信するユニキャストを使に動画データを配信するタイムテーブルを決定する必要があり，用して動画を配信するサービスである VoD では，サーバはク

クライアントは視聴したい動画データを見逃す可能性がある．

ライアントの要求に応じて帯域幅を確保して動画データを配信

そこで，多数の視聴者に特定の動画データを配信する方法としするため，クライアントの増加にともないサーバの処理負荷はて，分割放送型配信が提案されている．特定の動画データを繰

増加し，動画データの配信に必要な帯域幅は増加する．このたり返し配信する分割放送型配信では，分割した動画データをどめ，サーバは，配信する動画データの画質を下げることで，配のチャネルでどの時間帯に配信するかを定めた配信スケジュー

信に必要な帯域幅を削減する必要がある．

ルを用いることで，動画データの受信要求から先頭部分を受信するまでの時間 (以下，ロード時間) を短縮する．

2. 2 放送型配信
AbemaTV といった多数の視聴者に同じ動画データを配信す

配信スケジュールを作成する既存のスケジューリング手法でるサービスとして，放送型配信が挙げられる．放送型配信では，事前に想定した配信環境において，動画データの再生中には，動画データの配信時刻を定めたタイムテーブルに従って動発生する待ち時間を最短にする算出式を用いて，動画データの画データを配信することで，クライアントの受信要求に応じて分割比率を決定する．このため，作成できる配信スケジュール

動画を配信する VoD に比べ，サーバは処理負荷を抑制できる．

の数は制限され，配信スケジュールが最適となる環境は限定さ

しかし，放送型配信は，VoD と異なり，クライアントは配信される．実際に，動画データの配信システムでスケジューリング

れている複数の動画から好きな動画を受信して再生する必要が手法を適用する場合，最適な配信スケジュールを作成するスケある．サーバは事前に複数の動画データの配信時刻を定めたタ

ジューリング手法を導入することは難しい．

イムテーブルを決めるため，クライアントは見たい動画の配信

本研究では，分割放送型配信において，最適化アルゴリズムの一つである遺伝的アルゴリズムを用いて，ロード時間および開始時刻を意識する必要がある．

H-AHB 法を用いた配信スケジュールを用いて，3 種類のクライアントがそれぞれ動画データを受信して再生する例を説明する．クライアント 1 の帯域幅を 1.5 Mbps，クライアント 2の帯域幅を 3.0 Mbps，クライアント 3 の帯域幅を 4.5 Mbpsとし，クライアント 1 が動画データを受信して再生する例を図1 に示す．サーバが使用する帯域幅を 4.5 Mbps，動画データの再生レートを 1.5 Mbps，および動画データの再生時間を 60 秒とする．サーバは，帯域幅を 1.5 Mbps の三つのチャネル C1 ,C2 , C3 に分割した上で，一続きの動画データを三つのセグメ
ント S1 , S2 , S3 に分割して，C1 で S1 ，C2 で S2 , C3 で S3をそれぞれ繰り返して配信する．
クライアント 3 が動画データを受信して再生する場合，すべ図 1 H-AHB 法の配信スケジュール例 (クライアント 1)てのチャネルからセグメントを受信でき，動画再生中に途切れ時間は発生しない．このため，待ち時間は S1 を受信完了するまでのロード時間と同じであり，10 秒となる．クライアント 2

2. 3 分割放送型配信 (Near Video on Demand)

も同様に，待ち時間は 10 秒となる．次に，クライアント 1 が放送型配信において，多数の視聴者に特定の動画データを配

動画データを受信する場合，同時に一つのチャネルからしかセ

信する方法として，分割放送型配信 (Near Video on Demand)

グメントを受信できず，動画データのシミュレーション再生にが提案されている．分割放送型配信では，サーバは動画データ

おいて途切れ時間が発生する．実際にユーザが動画データを再を複数の部分（以下，セグメント）に分割して，複数のチャネ

生する場合は，途切れ時間を発生させず，ロード時間と途切れ

ルで複数のセグメントを繰り返し配信する．クライアントは，時間の合計分だけ再生開始時間を遅らせる必要がある．このた

動画データを要求してから再生を開始するまでに一定時間待つ

め，待ち時間は S1 の受信を完了するまでのロード時間 (10 秒)

ことで，動画データをはじめから途切れなく視聴できる．

とシミュレーション再生中に発生する途切れ時間 (20 秒) の合

分割放送型配信では，サーバとクライアントが一対多で通信計となり，30 秒となる．以上より，クライアント 1，2，3 の平するマルチキャストを使用して，サーバは一定の帯域幅で複数

均待ち時間は， (30 + 10 + 10)/3 ≃ 16.7 秒となる．一方，のクライアントに同じ動画データを繰り返して配信する．この動画データを分割しない場合，クライアント 1，2，3 の平均待ため，分割放送型配信はクライアントごとに帯域幅を確保する

ち時間は 60 × 1.5/(1.5 + 3.0 + 4.5)/3 ≃ 36.7 秒となる．

必要が無く，人気があるアーティストのコンサートやスポーツ

このため，スケジューリング手法を用いて動画データを分割すイベントの中継といった多数のクライアントが同じ動画データることで，待ち時間を短縮できる．

を視聴する環境において，サーバの負荷，および帯域幅の増加

3. 2 既存のスケジューリング手法における問題点

を VoD に比べて抑制できる．また，放送型配信と異なり，ク

既存のスケジューリング手法は，分割比率を算出する式から

ライアントは一定時間待つことで，動画データを最初から再生セグメントのデータサイズを決定するため，最適な配信スケ

できる．

ジュールを実現できる環境は限定される．この問題を解決する

3. スケジューリング手法

ため，想定する配信状況，および分割放送型配信で考慮すべき条件に応じて最適な配信スケジュールを作成するスケジューリ

3. 1 分割放送型配信におけるスケジューリング手法

ング手法が提案されている．しかし，想定する配信環境が同じ

分割放送型配信において，待ち時間を短縮するスケジューリ

場合，待ち時間がより短くなる配信スケジュールを選ぶ必要がング手法 [2], [3], [4] が提案されている．これらのスケジューリ

ある．

ング手法では，動画データに代表される一続きの連続メディア

例えば，異種クライアント環境を考慮したスケジューリング

データの再生中に途切れが発生しないようにした上で，ロード手法である H-AHB 法では，チャネル数を上限として配信スケ

時間と途切れ時間の合計である待ち時間ができるだけ短くなる

ジュールを作成できる．H-AHB 法において，配信に利用できる

配信スケジュールを作成する．

チャネル数が 3 の場合，サーバはクライアントが同時に受信可

分割放送型配信におけるスケジューリング手法の例として，

能なチャネル数 (以下，連続可能チャネル数) をもとに配信スケ

Hierarchical Asynchronous Harmonic Broadcasting method

ジュールを作成するため，配信スケジュールは図 2，図 3，およ(以下，H-AHB 法) [5] を説明する．H-AHB 法では，帯域幅がび図 4 の 3 種類のいずれかになる．サーバは，これら 3 種類の異なる複数種類のクライアントが存在するネットワーク環境

配信スケジュールのうち，配信環境で想定するクライアントの(以下，異種クライアント環境) において，すべてのクライアン

種類に応じて平均待ち時間が最短になる一つを選び，配信する．

トで発生する待ち時間の平均が最短になるようにセグメントの3. 1 節で示した配信環境における平均待ち時間は，図 2 の場合

データサイズを決定する．

で 20 秒，図 3 の場合で約 16.7 秒，および図 4 の場合で 20 秒となる．このため，平均待ち時間が最短となる配信スケジュール

図 2 H-AHB 法の配信スケジュール

図 3 H-AHB 法の配信スケジュール

図 4 H-AHB 法の配信スケジュール（連続受信可能チャネル数 1）（連続受信可能チャネル数 2）（連続受信可能チャネル数 3）

は，連続受信可能チャネル数が 2 の場合となる．しかし，配信

データの受信中にチャネルの切り替えを想定しないスケジューに利用できるチャネルが 3 の場合，3. 1 節で示したクライアン

リング手法の場合，サーバは一つの通信路で複数の論理チャネ

ト環境が変化しても，配信スケジュールはこれら 3 種類のうちルを実現するため，使用できる帯域幅をもとにチャネル数を設の一つになる．このとき，H-AHB 法が作成する配信スケジュー

定する．

ルで発生する待ち時間は，他の異種クライアント環境を考慮提案手法におけるチャネル数と待ち時間の関係について，サーしたスケジューリング手法である Optimized Heterogeneous

バの帯域幅を 4.5 Mbps，クライアントの帯域幅を 4.5 Mbps とPeriodic Broadcast [6] が作成する配信スケジュールに比べて設定し，他の配信条件は 3. 1 節と同じとする．チャネル数を 5，長大化する可能性がある．このため，サーバは，これら二つのチャネル帯域幅を 0.9 Mbps と設定した場合，想定するクライ

スケジューリング手法が作成する配信スケジュールの待ち時間

アントにおいて途切れ時間が発生しないように配信スケジューを比較する必要がある．

ルを作成するため，待ち時間はロード時間と同じとなり，約以上より，実際に動画データの配信システムでスケジューリ

6.76 秒となる．また，チャネル数を 9，チャネル帯域幅を 0.5ング手法を適用する場合，想定する配信環境，および分割放送

Mbps と設定した場合，待ち時間は約 5.01 秒となる．以上よ型配信で考慮すべき条件に応じてスケジューリング手法を決定

り，想定するクライアントが 1 種類の場合，論理チャネル数のする必要があり，実際のネットワーク環境において最適なスケ増加にともない待ち時間は短縮されるため，各チャネルの帯域

ジューリング手法を導入することは難しい．

幅を小さくして論理チャネル数をできるだけ増やす必要がある．

4. 提 案 手 法

4. 2. 2 複数の通信路で一つの動画データを配信する場合想定するクライアントが複数種類の場合，チャネルを切り替

4. 1 DB-GA 法

える必要がある．動画データの受信中にチャネルの切り替えを分割放送型配信において待ち時間を短縮するスケジューリ

想定するスケジューリング手法を動画配信システムに導入する

ング手法として，Division-based Broadcasting method with

場合，これまでの研究 [9] では，一つの通信路で一つの論理チャ

Genetic Algorithm (以下，DB-GA 法) を提案する．DB-GA

ネルを実現している．このため，サーバは配信に利用できる通法は，最適化アルゴリズムの一つである遺伝的アルゴリズム [7]

信路の数を上限としてチャネル数を設定する必要がある．

を用いて，待ち時間を最短にするセグメントの分割比率を算出

例えば，サーバが配信に利用できる帯域幅を 4.5 Mbps，通する．3. 1 節で述べたように，待ち時間は，クライアントの帯信路を 5 個とする場合，各チャネルの帯域幅は 0.9 Mbps とな

域幅，動画データの再生レート，配信に使用するチャネル数，

る．また，通信路を 9 個とする場合，各チャネルの帯域幅は 0.5

各チャネルの帯域幅，およびセグメントデータサイズをもとにMbps となる．

算出されるロード時間と途切れ時間の合計となる．提案手法で

4. 3 スケジューリング手順

は，最適化アルゴリズムを用いてセグメントのデータサイズを

表 3.1 に示す変数を用いて，提案手法のスケジューリング手

決定するため，既存のスケジューリング手法と比べて，配信環境が変化しても待ち時間は最短となる．

4. 2 チャネルの設定
動画データの配信システムにスケジューリング手法を導入す順を下記に示す．
（ 1 ） チャネル数 n，およびチャネル帯域幅 bi (i = 1 , · · ·, n) を設定する．
（ 2 ） 既存のスケジューリング手法を用いて，ei の初期値をる上で，配信に利用できる帯域幅や通信路の数，および想定す決定する．

るクライアント環境に応じて，チャネルの設定方法は異なる．

（ 3 ） 遺伝的アルゴリズムにもとづき，以下に示す待ち時間

このため，スケジューリング手法で使用するチャネル数およびの算出式 (4.1) の値 w を最小にする ei を求める．

チャネル帯域幅は，サーバの配信環境にもとづいて設定する必
要がある．

4. 2. 1 一つの通信路で一つの動画データを配信する場合想定するクライアントが 1 種類の場合，動画データの受信中にチャネルの切り替えは発生しない．例えば，Fast data broad-casting and receiving scheme (以下，FB 法) [8] といった動画

w=

m
n
∑
∑

max(xi − yi , 0)j=1 i=1

なお，xi ，および yi は，以下の値とする．

(1)

表1

定式化のための変数

記号 説明

r

動画データの再生レート

V

動画のデータサイズに占める再生に使用する割合

Rj

クライアント j が同時に受信できるチャネル数

D

動画データのデータサイズ

cj,i

クライアント j が i 番目のチャネルから受信できる帯域幅

Si

i 番目のセグメントei

Si の分割比率を算出する値

di

Si のデータサイズ， D× ∑nei
k=1

{
xi =

{
yi =

ek

図5

0
di
+ xmax(i−Rj ,0)cj,i

ロード時間の長大化(i = 0)(1 ≦ i ≦ n)

6. 設

0

(i = 1)di−1max(xi−1 , yi−1 ) +×Vr(2 ≦ i ≦ n)

計

6. 1 分割放送型配信システム T eleCaS
分割放送型配信における多くのスケジューリング手法では，計算機上のシミュレーション環境で待ち時間の短縮効果を評価（ 4 ） 算出した ei をもとに，配信するセグメントのデータする．このため，動画データの配信中に発生するシステムの処

サイズ di を求める．

理負荷，および動画データの再生中に発生するパケット損失に（ 5 ） チャネル Ci でセグメント Si を繰り返し配信する．

よる再生中断を考慮していない．

5. 関 連 研 究

我々の研究グループでは，計算機ネットワーク環境でスケ
ジューリング手法を導入，および評価できる分割放送型配

5. 1 複数動画の同時配信
複数動画の同時配信を考慮したスケジューリング手法として，

Multiple-Video broadcasting scheme with Repairing (以下，MV-R 法) [10]，および Multiple-Video broadcasting method
considering Data size [11] が提案されている．これらの既存手法では，一つの通信路で複数の動画データを配信することを想定している．しかし，実際にシステム上で複数動画を同時配信する場合，一つの通信路で一つの動画データを配信し，異なる
動画データを視聴するときは通信路を切り替えることが想定される．このため，実際のシステム上でこれらの既存手法を運用することは難しい．
提案手法では，複数動画の同時配信を考慮していないが．提案手法で作成する 1 種類の動画データの配信スケジュールを複数用いることで，複数動画の同時配信を実現できる．

5. 2 パケット欠損
パケット欠損を考慮したスケジューリング手法として，Syn-chronized Double Buﬀering Broadcasting [12]，および Data
Packet Broadcasting (以下，DPB 法) [13] が提案されている．
これらのスケジューリング手法は，パケットが欠損する可能性が高いセグメントの配信回数を増加することで，欠損したパケットを再び受信するまでの待ち時間の長大化を抑える．しかし，配信回数が増えたセグメントの受信において，パケット欠
損が連続的に発生した場合，待ち時間は短くならない．また，
実際の動画配信サービスで配信中にパケット欠損が生じた場合，
オンデマンド型配信で欠損したパケットを再送する方法，もしくは欠損前後のパケットを用いて欠損した部分を補完する方法が考えられる．これらの方式は配信システムにおける課題であり，動画データの分割比率を決定する提案手法では考慮しない．

信システム T elecommunication and BroadCasting System(T eleCaS) [14] を提案してきた．これまでの T eleCaS の研
究で，FB 法，および MV-R 法といったスケジューリング手法を導入し，有用性を確認してきた．

T eleCaS では，動画データの受信に必要な情報（以下，配信開始部），およびセグメントを等分割した各部分をもとにセグメントに復元する情報（以下，情報部）の 2 種類のデータ
フォーマットで動画データを配信する．また，T eleCaS 上で
動画データを視聴する場合，データフォーマットの影響で，待ち時間の長大化，および動画再生中に発生する途切れ時間 (以下，再生中断時間) の長大化が発生する．そこで，待ち時間の短縮および再生中断時間の短縮を実現するための課題と対処をそれぞれ述べる．また，設計内容をもとに，T eleCaS における提案手法の実現について述べる．

6. 2 待ち時間の短縮
T eleCaS では，データフォーマットの影響でロード時間が長大化する．シミュレーション評価の待ち時間は，ロード時間と途切れ時間の合計で算出するため，待ち時間は長大化する．

T eleCaS 上でロード時間が長大化する例を図 5 に示す．
T eleCaS では，動画データを分割したセグメントに関する情報は配信開始部に格納されているため，クライアントは配信開始部を受信した後に情報部の受信を開始できる．図 5 に示すよ
うに，配信開始部は第 1 セグメントの配信前にのみ配信される
ため，T eleCaS における動画データのロード時間は，シミュレーション環境における評価に比べて平均で 1.5 倍長大化する．
これまでの T eleCaS では，第 1 セグメントの先頭となるサ
ブセグメントを受信するとすぐに再生を開始する逐次再生方式

図 6 配信開始部のデータフォーマット
図 8 設計手法に応じた待ち時間および再生中断時間までの待ち時間として算出していた．このため，T eleCaS 上で発生する動画データの再生中断時間は，IP ネットワーク上の処理を含む T eleCaS のシステム上で発生する時間，もしくはスケジューリング手法で発生する時間のどちらかを判別できな
い課題がある．
本研究で実現する T eleCaS では，シミュレーション環境
図 7 情報部のデータフォーマット

における評価で算出した途切れ時間を待ち時間に追加する．具
体的には，配信開始部に格納されているすべてのセグメントを用いることで，ロード時間を短縮してきた．しかし，各チャ
ネルの配信契機が同期しないスケジューリング手法の場合，逐次再生を行うことで，各チャネルから受信しているセグメントのデータサイズが逐次再生で必要となるデータサイズを下回る可能性がある．このとき，動画再生中に途切れ時間が発生する．
以上より，配信開始部を受信した後に情報部の受信を開始する
場合，ロード時間の長大化，および動画再生中における再生中
断時間の発生という二つの課題が考えられる．
そこで，対処として，T eleCaS 上でクライアントが配信開
始部の受信を完了していなくても動画データを受信できるように，情報部を拡張する．このとき，配信開始部を動画データの再生開始に必要な情報部として扱う．
実現方式における配信開始部のデータフォーマットを図 6，
および情報部のデータフォーマットを図 7 にそれぞれ示す．実
現方式における情報部では，識別子，セグメント番号，サブセ
グメント番号，セグメントデータサイズ，チャネル帯域幅，およびサブセグメントデータで構成する．図 7 に示す情報部を実現することで，クライアントは配信開始部を受信する前に動画データを受信でき，ロード時間を短縮できる．

6. 3 再生中断時間の短縮
図 1 で示したように，スケジューリング手法では，シミュレーション環境における再生で発生する途切れ時間の分だけ再生開始までの待ち時間を長大化することで，動画データの再生
中に途切れが発生しないようにスケジューリングする．これまでの T eleCaS は，図 1 のシミュレーション再生で示すように，クライアントが第 1 セグメントを受信完了すると動画デー
タの再生を開始するため，ロード時間を受信要求から再生開始のデータサイズ，およびクライアントで使用できる帯域幅をもとに，クライアントがシミュレーション環境で動画再生中に発生する途切れ時間を算出し，算出した時間分だけ再生開始までの待ち時間を長大化する．また，計算機ネットワーク環境とシミュレーション環境で待ち時間の比較評価を行うことで，T eleCaS 上で発生する再生中断時間の原因を特定できる．

7. 評

価

7. 1 評 価 環 境
評価環境として，T eleCaS を導入した計算機を用いてネッ
トワークを構築した．評価する計算機ネットワーク環境は，

IGMP-Snooping を利用できるスイッチングハブ [15] を経由して，T eleCaS を導入したサーバ計算機 1 台とクライアント計
算機 3 台を Gigabit Ethernet で有線接続により構築した．
評価では，T eleCaS 上で計算機ネットワーク環境における待ち時間，およびシミュレーション環境における待ち時間を比較することで，提案手法の有用性を確認する．T eleCaS 上で発生する待ち時間および再生中断時間は，評価で設定したパラメータの値をもとに，各種クライアントで 5 回測定を行った平均値とする．動画データの再生レートは 1.5 Mbps とする．また，シミュレーション評価では，途切れ時間が待ち時間に含むため，再生中断時間は動画再生中に発生しない．

7. 2 設 計 手 法
設計において，T eleCaS 上で発生する待ち時間および再生
中断時間の短縮方法を実現するための対処を 2 種類示した．これら 2 種類の対処の有無に応じて実装した 4 種類の設計手法 1
から 4 について，T eleCaS 上で発生する待ち時間と再生中断

時間を図 8 に示す．評価に使用するスケジューリング手法は，提案手法である DB-GA 法とする．縦軸は待ち時間とし，待ち時間と再生中断時間で構成される．横軸は，6. 2 節で述べた待ち時間の短縮を実現するための対処，および 6. 3 節で述べた再生中断時間の対処を実現するための対処の有無にもとづいて，4 種類の設計手法 1 から 4 を設定する．
本節では，チャネル切り替えを想定したスケジューリング手法を評価する．このため，クライアントで使用できる帯域幅は3 種類とし，クライアント 1 は 1.0 Mbps，クライアント 2 は
5.0 Mbps，およびクライアント 3 は 10 Mbps とする．また，評価環境におけるクライアントの存在確率は，すべての種類で同じとする．T eleCaS の評価では，設計手法の有用性を確認するため，帯域幅が 1.0 Mbps のクライアントのみ評価する．

図 9 データサイズにおける待ち時間と再生中断時間の合計 (単一クライアント環境)サーバが使用する帯域幅は 10 Mbps とする．
待ち時間について，DB-GA 法を用いたシミュレーション評
価では，第 1 セグメントは 201907 Bytes，第 1 チャネルの帯

本節では，チャネル切り替えを想定しないスケジューリング

域幅は 1.0 Mbps となり，ロード時間は約 0.2 秒，帯域幅が 1.0

手法を評価する．サーバが使用する帯域幅は 5.0 Mbps，配信

Mbps のクライアントにおける途切れ時間は約 32.5 秒となる．

に使用する通信路は一つとし，クライアントが使用できる帯域

このため，待ち時間は約 32.7 秒となる．また，設計手法 1 に幅を 5.0 Mbps とする．4. 2. 1 節で示したように，T eleCaS

おける待ち時間は約 0.39 秒，設計手法 2 における待ち時間は上で DB-GA 法を用いる場合，配信に使用する論理チャネルを

約 0.24 秒となり，6. 2 節で述べた対処を実現することでロードできるだけ増やす必要があるため，第 1 チャネルの帯域幅を時間を短縮し，待ち時間を短縮した．

0.038 Mbps，第 1 チャネル以外の帯域幅を 0.033 Mbps とし，再生中断時間について，DB-GA 法を用いたシミュレーショ

使用する論理チャネル数を 150 とする．比較手法である FB 法

ン評価では，途切れ時間の分だけ再生開始を遅らせるため，再は，配信に使用する論理チャネル数を 3，各チャネルの帯域幅

生中断時間は発生しない．また，設計手法 1 における再生中断

1.5 Mbps とする．

時間は約 36.6 秒，設計手法 3 における再生中断時間は約 2.76

シミュレーション評価について，提案手法である DB-GA 法

秒となり，6. 3 節で述べた対処を実現することで再生中断時間

では，セグメントの分割数が 150 となるため，第 1 セグメントを短縮した．

の大きさは 861 Bytes，および待ち時間は 2.35 秒となる．一方，

待ち時間と再生中断時間の合計について，設計手法 4 におけ既存手法である FB 法では，チャネルの帯域幅を動画データのる待ち時間および再生中断時間の合計は，他の 3 種類の設計手

再生レートと等しくする必要があるため，セグメントの分割数法に比べて短縮した．以上より，6. 2 節，および 6. 3 節で述べは 7 となる．このとき，第 1 セグメントの大きさは 1671053

た対処を実現することで，待ち時間および再生中断時間を短縮

Bytes となり，待ち時間は 8.9 秒となる．以上より，DB-GA 法

することを確認した．

におけるセグメントの分割数は FB 法に比べて多いため．待ち7. 3 動画のデータサイズ

時間は短くなる．また，FB 法では，サーバが配信に使用できサーバが配信する動画のデータサイズによる待ち時間の変化

る帯域幅である 5.0 Mbps のうち 4.5 Mbps しか使用できないを評価する．配信環境で想定するクライアントが 1 種類である

が，DB-GA 法では，5.0 Mbps すべてを使用できる．

単一クライアント環境における評価結果を 7. 4 節，およびクラT eleCaS における評価について，DB-GA 法における待ち

イアントが複数種類存在する異種クライアント環境における評時間と再生中断時間の合計は，FB 法に比べて短い．一方で，価結果を 7. 5 節でそれぞれ説明する．

T eleCaS における評価では再生中断時間が発生するため，シ7. 4 単一クライアント環境

ミュレーション評価との間で差が発生する．DB-GA 法では，配信環境で想定するクライアントが 1 種類である単一クライ

分割数の増加にともない，受信が完了しているセグメントの再アント環境において，動画のデータサイズに応じた待ち時間と生が終了するまでに次のセグメントを受信できず，再生中断時

再生中断時間の変化について評価する．図 10 に，T eleCaS ，間が発生する．シミュレーション評価では，動画のデータサイ

およびシミュレーション環境それぞれにおいて，各スケジューリ

ズをもとに配信スケジュールを作成するが，実際は動画データング手法で発生する待ち時間および再生中断時間を示す．評価

以外にデータ構造を作成するためのヘッダやフッダが追加されに使用するスケジューリング手法は，提案手法である DB-GAている．このため，実際に受信している動画のデータサイズは，

法，および既存手法である FB 法とする．縦軸は待ち時間とスケジューリング手法が想定している動画データのデータサイ

再生中断時間の合計である．横軸は動画のデータサイズであズに比べて減少する．

り，11.1 MBytes，17.0 MBytes，22.5 MBytes，28.1 MBytes，

7. 5 異種クライアント環境

33.8 MBytes の 5 種類を用いる．

配信環境で想定するクライアントが複数種類である異種ク

図 10

データサイズにおける待ち時間と再生中断時間の合計 (異種ク
ライアント環境)図 11 動画データの再生数における待ち時間と再生中断時間の合計完了したチャネルを離脱してから次のセグメントを受信する
ライアント環境において，動画のデータサイズに応じた待ち時間および再生中断時間の変化について評価する．図 10 に，T eleCaS ，およびシミュレーション環境それぞれにおいて，ス
ケジューリング手法ごとに発生する待ち時間と再生中断時間の合計を示す．評価に使用するスケジューリング手法は，提案手法である DB-GA 法，および異種クライアント環境を考慮した
スケジューリング手法である H-AHB 法とする．縦軸および横軸は，7. 4 節と同じとする．
本節では，チャネル切り替えを想定したスケジューリング手法を評価するため，クライアントの評価環境は 7. 2 節と同じとする．サーバが使用する帯域幅は 10 Mbps，配信に使用する通信路は 10，およびチャネルの帯域幅は 1.0 Mbps とする．
シミュレーション評価について，提案手法である DB-GA 法
では，最適化アルゴリズムを用いて待ち時間が最短になるデー
タサイズを決定するため，チャネル Ci における i の値が大きくなっても，チャネルで配信するセグメントのデータサイズは増加しない．一方，既存手法である H-AHB 法は，データサイズを算出式にもとづき決定するため，チャネル Ci における iの値が大きくなると，チャネルで配信するセグメントのデータ
サイズは増加する．このとき，帯域幅が小さい 1.0 Mbps のク
ライアント 1 で途切れ時間が発生するため，ロード時間と途切
れ時間の合計である待ち時間は長大化する．以上より，帯域幅が小さい 1.0 Mbps のクライアント 1 において，提案手法である DB-GA 法は，既存手法である H-AHB 法より途切れ時間が短くなり，平均待ち時間を短縮できる．

T eleCaS における評価について，DB-GA 法における待ち
時間と再生中断時間の合計は，H-AHB 法に比べて短い．また，二つのスケジューリング手法について，T eleCaS における評価とシミュレーション評価との間に差が発生する．これは，チャネルに参加するまでの間に，データを受信しない時間が発生する．

7. 6 複数動画の同時配信
単一クライアント環境において，同時に再生する動画データの種類に応じた待ち時間および再生中断時間の変化について評価する．図 11 に，T eleCaS における各スケジューリング手法の待ち時間と再生中断時間の合計を示す．評価に使用するス
ケジューリング手法は，DB-GA 法，および MV-R 法とする．
縦軸は待ち時間および再生中断時の合計，横軸はクライアント
が同時に再生する動画データの数とする．
本節では，サーバが配信する動画データを 5 種類，各動画のデータサイズは 11.1 MBytes，サーバが使用する帯域幅は 22.5

Mbps，配信に使用する通信路は一つとし，クライアントが使用できる帯域幅を 22.5 Mbps とする．クライアントは，5 種類の動画データすべてを受信するが，同時に再生する動画データの数を変化させる．DB-GA 法では，一つの動画データの配信に使用するチャネル数を 15，各チャネルの帯域幅を 0.3 Mbps
で作成する配信スケジュールを 5 個使用することで，5 種類の動画データを配信する．比較手法である MV-R 法は，配信に使用する論理チャネル数を 15，各チャネルの帯域幅を 1.5 Mbpsとする．
シミュレーションにおける評価では，DB-GA 法の待ち時間は約 4.39 秒，MV-R 法の待ち時間は約 6.0 秒となり，DB-GA
法の待ち時間と再生中断時間の合計は MV-R 法に比べて短い．

DB-GA 法では，一つの動画データに対するセグメントの分割
数は 15 となる．一方で，MV-R 法ではセグメントの分割数が10 となるため，第 1 セグメントのデータサイズが小さくなり．
待ち時間は短くなる．また，T eleCaS における待ち時間と再生中断時間について，同時再生する動画の数が増加すると，ク

IGMP-Snooping を用いてマルチキャストへの JOIN メッセー

ライアントはブラウザへ同時に送信するデータ量が増え，シスジ間で設定した時間による影響である．T eleCaS において，テム全体の処理量が増加する．このため，再生中断時間は長大

クライアントは受信中にチャネルを切り替えるため，セグメン
トの受信が完了したチャネルを離脱した後，ダミーとなるチャ

化する．

7. 7 パケット欠損

ネルの JOIN メッセージを出す．次に，受信したいチャネルに

パケット欠損が発生する場合について，単一クライアント環

JOIN メッセージを出す．このとき，クライアントは，受信が境において，パケット欠損率に応じた再生中断時間の変化につシステムの実装が挙げられる．

謝

辞

本研究の一部は，文部科学省科学研究費補助金・若手研究（B ）（26730059），基盤研究（B）（15H02702），基盤研究（C）（16K01065），および（公財）山陽放送学術文化財団の研究助成によるものである．ここに記して謝意を表す．

文

図 12

パケット欠損率における再生中断時間

いて評価する．T eleCaS における各スケジューリング手法の再生中断時間の変化を図 12 に示す．評価に使用するスケジューリング手法は，DB-GA 法，およびパケット欠損を考慮したス
ケジューリング手法を DPB 法とする．縦軸は再生中断時間，横軸はパケット欠損率とする．サーバが使用する帯域幅は 4.0

Mbps，配信に使用する通信路は一つとし，クライアントが使用できる帯域幅を 4.0 Mbps とする．また，7. 1 節に示す環境において，動画データを配信するサーバとスイッチングハブの間に Dummynet を搭載した計算機を経由することで，パケット欠損を発生させる．
待ち時間について，提案手法では，配信に使用する論理チャ
ネル数が多いほど待ち時間を短縮する．シミュレーションにおける評価において，チャネル数 20 における DB-GA 法の待ち時間は約 5.63 秒，DPB 法の待ち時間は約 7.04 秒となる．図12 より，T eleCaS においてパケット欠損が発生する場合，パケット欠損により再生に必要なセグメントが受信できず，再生中断が多く発生し，再生中断時間は長大化する．また，論理
チャネル数が少ない場合，パケット欠損に関する影響は少ない．
一方，既存手法である DPB 法では，パケット欠損を考慮してセグメントの配信回数を増加させるが，DPB 法における再生
中断時間は，提案手法に比べて長大化する．以上より，パケッ
ト欠損が発生する場合，再生中断時間ができるだけ短くなるよ
うにセグメントの分割数を決める必要がある．

8. お わ り に本研究では，分割放送型配信において最適化アルゴリズムを用いたスケジューリング手法を提案し，分割放送型配信システ
ムに実装した．また，提案したスケジューリング手法をシミュ
レーション環境，および計算機ネットワーク環境で評価を行い，待ち時間の短縮効果を確認した．評価結果より，動画のデータ
サイズ，再生する動画数，およびパケット欠損において．提案
手法の有用性を確認した．単一クライアント環境における評価
では，チャネル数の増加にともない，待ち時間の減少を確認した．異種クライアント環境における評価では，チャネル切替えによる再生中断時間が発生するが，待ち時間の短縮を確認した．
今後の課題として，パケット欠損を考慮した分割放送型配信

献[1] 東 京 メ ト ロ ポ リ タ ン テ レ ビ ジョン 株 式 会 社 ，株 式 会 社 ア ク
トビラ：ハイブリッドキャストを使用したＩＰマルチキャス
ト配信の共同実験を今夏に実施予定，（オンライン)，入手先⟨http://s.mxtv.jp/company/press/pdf/press2015 1060001.p
df⟩(参照 2016-11-14)．
[2] Hua, K.A., Bagouet, O. and Oger, D.: Periodic Broadcast
Protocol for Heterogeneous Receivers, Proc. ACM Multimedia Computing and Networking, Vol.5019, No.1, pp.220-231(2003).
[3] Mahanti, A., Eager, D., Vernon, M. and Sundaram-Stukel,
D.: Scalable On-Demand Media Streaming with Packet
Loss Recovery, IEEE/ACM Trans. on Networking, pp.195209 (2003).
[4] 義久智樹，塚本昌彦，西尾章治郎：分割放送方式におけるチャネ
ルの帯域幅を考慮した連続メディアデータの分割手法，情報処理学会論文誌 B，Vol.J91-B，No.3，pp.300-308 (2008).
[5] 後藤佑介，義久智樹，金澤正憲：異種クライアント環境における連続メディアデータ放送のための待ち時間短縮手法，電子情報通信学会論文誌 D，Vol.J91-D，No.3，pp.667-676 (2008)．
[6] Shi, L., Sessini, P., Mahanti, A., Li, Z. and Eager, D.L.:
Scalable Streaming for Heterogeneous Clients, Proc. ACM
Multimedia, pp.22-27 (2006).
[7] 佐藤浩，小野功，小林重信：遺伝的アルゴリズムにおける世代交代モデルの提案と評価，人工知能学会誌，Vol.12，No.5，
pp.734-744 (1997)．
[8] Juhn, L. and Tseng, L.: Fast Data Broadcasting and Receiving Scheme for Popular Video Service, IEEE Trans. on
Broadcasting, Vol.44, No.1, pp.100-105 (1998).
[9] 井上祐輔，木村明寛，後藤佑介：帯域幅が異なるクライアントの混在環境における分割放送型配信システムの実装と評価，マルチメディア通信と分散処理ワークショップ論文集，Vol.2016，
pp.109-117 (2016)．
[10] Chen, Y. and Huang, K.: Multiple Videos Broadcasting
Scheme for Near Video-on-Demand Services, Proc. IEEE
International. Conference. on Signal Image Technology andInternet Based Systems 2008, pp.52-58 (2008).
[11] Gotoh, Y.: A Scheduling Method for Division Based Broadcasting of Multiple Video Considering Data Size, Proc. 4thInternational Workshop on Advances in Data Engineeringand Mobile Computing, pp.464-469 (2015).
[12] 安里諒，青木輝勝，沼澤潤二：受信エラー耐性を有する分割放送型配信手法に関する一検討，電子情報通信学会技術研究報告，
Vol.109，No,.449，pp.31-36 (2010).
[13] 後藤佑介，谷口秀夫：連続メディアデータの放送型配信における誤り耐性を考慮したスケジューリング手法，情報処理学会研究
報告，Vol.2012-DPS-152，No.24，pp.1-8 (2012).
[14] 木村明寛，後藤佑介，谷口秀夫：動画データを分割配信するシ
ステムの実現と評価，電子情報通信学会論文誌 B，Vol.J96-B，
No.10，pp.1217-1225 (2013)．
[15] コ レ ガ:CO-BSW08GTXVL2，コ レ ガ (オ ン ラ イ ン)，入 手
先 ⟨http://corega.jp/prod/co-bsw08gtxvl2/⟩(参照 2016-0608)．