論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――

プリフェッチを伴う連続メディア
データ放送における待ち時間短縮のためのスケジューリング手法
A Scheduling Method for Waiting Time
Reduction on Continuous Media Data
Broadcasting with Prefetching

義久 智樹♥
西尾 章治郎♠

塚本 昌彦♦

Tomoki YOSHIHISA Masahiko TSUKAMOTO
Shojiro NISHIO

近年の放送のデジタル化にともない，映像や音声といった連続メディアデータを放送型で配信する連続メディアデー
タ放送に対する注目が高まっている．連続メディアデータ放送では，一般に，クライアントは所望のデータが放送されるまで待つ必要がある．このため，クライアントがあらかじめ
データの初めの部分を受信してプリフェッチを行うことで，待ち時間のない再生を可能にする幾つかの手法が提案されている．しかし，これらの手法では，放送帯域に制限がない
ため，実用性に乏しい．本稿では，プリフェッチを伴う連続メディアデータ放送において，放送帯域に制限を設けたうえで，サーバ側のスケジューリングにより待ち時間を短縮する手法を提案する．
Due to the recent digitalization of broadcast systems,
broadcasting continuous media data such as video andaudio has attracted great attention. In continuous media
data broadcasting, generally, clients have to wait until
their desired data is broadcast. In some previous methods,
clients avoid this waiting time by prefetching the data inadvance. These methods do not set limit to the bandwidth.
However, practical systems have limit to it. In this paper,
we propose a scheduling method on continuous media
data broadcasting with prefetching the data. Our
proposed method reduces the waiting time under thecondition that the system has limit to the broadcast
bandwidth.

1. はじめに
地上波デジタル放送や衛星放送といった近年のデジタル放送の普及にともない，映像や音声といった連続メディアデータを放送型で配信する連続メディアデータ放送に対する注目が高まっている．放送型配信では，一般に，サーバは同
じデータを繰り返して放送する．複数のクライアントにまと♥正会員 京都大学学術情報メディアセンター
yoshihisa@media.kyoto-u.ac.jp♦
正会員 神戸大学工学部 tuka@kobe-u.ac.jp♠
正会員 大阪大学大学院情報科学研究科
nishio@ist.osaka-u.ac.jp

1

めてデータを配信できるため，クライアント数が多い場合に有効だが，クライアントは所望のデータが放送されるまで待つ必要がある．一方，クライアントは連続メディアデータを最初から最後まで途切れなく再生できることが重要になり，
この条件を考慮したうえでクライアントの待ち時間を短縮する様々な配信手法が提案されている[2, 3, 5, 6, 7, 8]．
幾つかの手法では，クライアントはあらかじめデータの初めの部分を受信してプリフェッチを行う．プリフェッチを行うことで，待ち時間のない再生が可能になるが，途切れなく再生できるために必要な帯域が大きくなる．このため，これらの手法では，データを幾つかの部分に分割し，データの再生中に残りの部分を受信できるように，サーバが分割されたデータをスケジューリングすることで，必要な帯域を削減している．しかし，変調方式やハードウェア構成といった理由
から，一般に，放送帯域には制限がある．例えば，地上波デジタル放送では，システム構成の都合上，放送帯域は23Mbps
である．BS (Broadcast Satellite)，CS (Communication
Satellite) デジタル放送では52Mbpsである[1]．放送帯域に制限があるにも関わらず，既存手法では放送帯域に制限を設けていない．簡単な拡張で，放送帯域に制限を設けたうえで
スケジューリングできるが，待ち時間が発生する．
そこで，本稿では，プリフェッチを伴う連続メディアデー
タ放送において，放送帯域に制限を設けたうえで，待ち時間を短縮するスケジューリング手法を提案する．提案手法では，使用できる放送帯域を考慮して分割したデータをスケジューリングすることで，既存手法を拡張した手法よりも待ち時
間を短縮する．これまでに筆者らが提案してきた手法と異なる点は，プリフェッチをともなっている点である．クライア
ントがプリフェッチしていたデータを再生している間に残りのデータを受信することで，待ち時間を効率的に短縮できるため，これまでとは異なったデータの分割が必要になる．

2. 関連研究
プリフェッチを伴う連続メディアデータ放送において，ク
ライアントがデータを途切れなく再生できるために必要な帯域を削減する手法が提案されている．これらの手法は，拡張することで，放送帯域に制限を設けたうえでスケジューリ
ングできるが，待ち時間が発生する．まず，データを分割せずに放送する場合（単純繰り返し手法）を考える．クライア
ントが60分の映像データの初めの1%をプリフェッチすると，残り59.4分のデータを繰り返して放送することになる．デー
タの再生レートを5Mbps (MPEG2[1]) とし，地上波デジタ
ル放送を想定した23Mbpsの帯域を用いて放送する場合，残りのデータの放送には59.4×5M/23M=12.9分かかるため，待ち時間は12.9-0.6=12.3分になる．
PHB-PP (PolyHarmonic Broadcasting protocol with
Partial Preloading) 法[5]では，データをn個の部分に等分割してn個のチャネルを用いて放送する．例えば，初めの7%をプリフェッチし，地上波デジタル放送を想定した13個のチャネルを用いて放送すると，データの再生レートが5Mbpsの場
合には，16Mbpsの放送帯域が必要になる．地上波デジタル放送で放送する場合，必要な帯域が23Mbps以下であるため，待ち時間はなしになる．1%のプリフェッチでは，14個以上のチャネルが必要になり，放送スケジュールが作成できないため，先程と異なり7%のプリフェッチとした．
PHB-PP法では，nの値を大きくして多くのチャネルを使用するほど必要な帯域を削減できるが，システムが複雑にな

日本データベース学会 Letters Vol.4, No.1

論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――
Broadcast Stream

3. 提案手法

3.1 想定環境
CSやBSデジタル放送では，ユーザが好みの時間に映像を最初から最後まで途切れなく再生できるように，人気のある1作の映画をほぼ一日中繰り返して放送する場合がある．こういった放送形態は擬似オンデマンド型と呼ばれ，1つの連続メディアデータを繰り返して放送することは現実的といえる．以下に，提案手法の想定環境を箇条書きで示す．
z 放送帯域には制限がある．
z 使用チャネル数には制限がある．
z 連続メディアデータは受信開始と同時に再生できず，再生の単位を受信しなければ再生を開始できない．
z サーバは擬似オンデマンド型の放送を行い，複数のチャネ
ルを用いてセグメントを繰り返して放送する．
z クライアントがデータの再生を開始すると，最後まで途切れずに再生できる．
z クライアントはバッファを持ち，受信したデータを再生している間も放送されているデータを受信し，バッファに保存できる．
z クライアントはデータをプリフェッチする．
サーバは複数のコンテンツを放送し，再生するコンテンツ
はユーザの嗜好によって異なる．したがって，すべてのデー
タをプリフェッチすると，データサイズが膨大になるため，
一部のデータをプリフェッチする．

3.2 スケジューリング手順
連続メディアデータの再生時間をD，再生レートをr，使用チャネル数をN，プリフェッチするデータの全データサイズに対する割合をdとする．例えば，5Mbpsの60分のデータ
を13チャネル用いて放送する場合(D=60分，r=5Mbps，
N=13)，d=1%とすると，初めの0.6分をプリフェッチすることになる．放送帯域をBとし，チャネルCi (i=1，…，N) の帯域をbiとする．B=b1+…+bNとなる．セグメントのデータサ
イズを算出するための変数として，piおよびWを導入する．
piおよびWは以下の式で与える．

2

(1)

S1

S1

C2 ・・・
C4 ・・・

S5

C13 ・・・

S13
0.58min 0.6min 0.42min

t3

1.77
Mbps

S4・・・

C5 ・・・

t2

・・・

・・・

S3
S4

Prefetch
Client Stream Data・・・

S2 ・・・

S2
S3

1.77
Mbps
1.77
Mbps
1.77
Mbps
1.77
Mbps
1.77
Mbps

・・・

S1

S2

C3 ・・・

t1

プリフェッチを伴う連続メディアデータ放送において，放送帯域に制限を設けたうえで，待ち時間を短縮するスケジュ
ーリング手法 AHB-PB (AHB with Prefetching considering
Bandwidth) を提案する．待ち時間とは，ユーザがデータの再生を要求してから，再生が開始されるまでの時間を意味す
る．AHB-PB 法は，使用できる放送帯域を考慮して分割したデータをスケジューリングすることで，既存手法を拡張した手法よりも待ち時間を短縮する．AHB-PB 法のアイデアは
AHB 法[7]に基づいているが，プリフェッチをともなっている点が異なる．

i-1⎛ bj ⎞
p = (dD + W )∏ ⎜⎜1 + ⎟⎟ir ⎠j =1 ⎝

C1 ・・・

・・・るという問題がある．MTB (Mayan Temple Broadcasting)
法[5]は，必要な帯域がPHB法より大きくなるものの，使用
チャネル数を抑えることができる．MTB法では，残りのデー
タを，データサイズの異なるm個の部分に分割して放送する．
例えば，5Mbpsの60分のデータの初めの1%をプリフェッチ
し，各チャネルの帯域をデータの再生レートと等しくすると，7個のチャネルを用いることになる． 23Mbpsの帯域を用いて放送する場合，データの受信開始からS7の受信完了まで
54.7分かかるため，待ち時間は54.7-38.4=16.3分になる．

S1

Time

S2

S3

S4

・・・

t4

図 1 AHB-PB 法の放送スケジュールの例
Fig.1 An Example of Broadcast Schedule under the
AHB-PB Method

⎛
⎞
⎜
⎟
⎜
⎟
(2)
1− d
W =⎜
-d ⎟ DN⎜ ⎛⎜1 + b j ⎞⎟ − 1 ⎟
⎜
⎜∏
⎟
r ⎟⎠
⎝ j =1 ⎝⎠Wは必要な待ち時間である．Siのデータサイズが以下になるように，N個のセグメントに分割する．
(3)
bi pi
Siのデータサイズを式(3)で与えることで，クライアントは，セグメントの再生開始時刻にそのセグメントを受信完了でき，データを最初から最後まで途切れずに再生できる．分割
したデータを，C1でS1，C2でS2といったように1個のチャネ
ルで1個のセグメントを繰り返して放送するようにスケジューリングする．
例えば，地上波デジタル放送を想定した23 Mbpsの帯域を用いて13チャネルで5Mbpsの60分のデータを放送し，初めの0.6分をプリフェッチ (d=1%) する場合を考える．プリフェッチの割合は放送環境によって異なり，放送するコンテンツの数と必要なバッファサイズから決定される．この例の場合，
プリフェッチに必要なバッファサイズは5M×0.6×60/8=
23Mバイトとなる．近年の受信機には，数十Gバイトのハードディスクをもつものもあり，現実的と考える．放送スケジ
ュールは図1のようになる．待ち時間は0.58分になる．
図1において，“Broadcast Stream”はサーバが放送するデータを示し，“Client Stream”はクライアントが再生するデータを示す．時刻t1にユーザが再生ボタンを押すなどしてデー
タの再生を要求すると，クライアントは放送されているデー
タの受信を開始する．0.58分待った後，t2からデータの再生が開始される．クライアントはまずプリフェッチしていた初めの0.6分のデータを再生する．プリフェッチしていたデー
タの再生が終了するt3では，クライアントはS1の受信を完了しているため，続けてS1の再生を開始する．S1の放送には1.18分かかるが，再生レートが5Mbpsなので，S1の再生時間
は 0.42分になる．S1の再生終了時刻t4=t3+0.42分にはS2を受信完了しているため，S1の再生終了後，続けてS2の再生を開始する．他のセグメントについても，再生開始時刻までに受信完了できるため，クライアントは最初から最後まで途切れずに再生できる．この例では，各チャネルの放送周期の始まりとユーザの再生要求の時刻t1が一致しているが，そうではなくt2でユーザが再生要求を出すような場合にも，セグメン

日本データベース学会 Letters Vol.4, No.1

論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――
0.5

0.35

C=2
C=5
C=10
C=20

Waiting Time/Playing Time

Waiting Time/Playing Time

0.3

AHB-PB
Simple
拡張MTB

0.45

0.25

0.2

0.15

0.1

0.4
0.35
0.3
0.25
0.2
0.15
0.1

0.05
0.05
0

0
2

3

4

5

6

7

8

9

10

2

3

Bandwidth/Consumption Rate

Fig.2

図 2 AHB-PB 法の放送帯域と待ち時間
The Broadcast Bandwidth and the Waiting Timeunder the AHB-PB Method

トを途中から受信することで，クライアントは最初から最後まで途切れずに再生できる．

4. 評価
地上波デジタル放送では，すべてのチャネルの帯域は等しいため，b1=…=bN=B/Nとした．再生の単位として，実際にMPEG2で符号化した60分の映像データのGOP[7]を用いた．
評価結果は計算機シミュレーションによる理論値である．

4.1 放送帯域と待ち時間
AHB-PB法の性能を評価するため，放送帯域によって待ち時間がどの程度になるか示す．d=1%の場合の放送帯域と待ち時間の関係を図2に示す．縦軸は待ち時間をデータの再生時間で除した値，横軸は放送帯域をデータの再生レートで除した値とする．“C=i ” (i=2，5，10，20) は使用チャネル
数がi個の場合の待ち時間を示す．放送帯域が大きいほど待ち時間が短くなっているのは，放送帯域が大きいほどデータの放送にかかる時間が短くなるためである．例えば，23Mbpsの帯域を用いて，10チャネルで5Mbpsの60分のデータを放送する場合，d=1%とすると，待ち時間は0.78分になる．

4.2 比較
本節では，既存手法で，各チャネルの帯域を数倍し，放送帯域を考慮するように拡張した手法と比較し，提案手法の有効性を示す．例えば，MTB法で，d=1%とし，13チャネルまで用いて5Mbpsの60分の映像データを放送する場合，
32.8Mbpsの放送帯域が必要になる．放送帯域を考慮して
23Mbpsで放送する場合，各チャネルの帯域を0.7倍すること
で，23Mbpsで放送できる．しかし，放送帯域を考慮せずに32.8 Mbps用いて放送する場合とは異なり，待ち時間が発生する．この場合，待ち時間は16.3分になる．
そこで，提案手法AHB-PB法と既存手法を拡張した手法の待ち時間を比較する．d=1%とし，13チャネルまで用いてデータを放送する場合の待ち時間を図3に示す．縦軸は待ち時間をデータの再生時間で除した値，横軸は放送帯域をデータの再生レートで除した値とする．“AHB-PB”は提案手法，“Simple”は2章で述べた単純繰り返し手法，“拡張MTB”は
MTB法を拡張した手法の待ち時間を示す．PHB-PP法では，
プリフェッチの割合が少なく，放送スケジュールを作成できないため，図中に含まれていない．MTB法における各チャネ
ルの帯域は，データの再生レートと等しくした．
このグラフより，AHB-PB法の待ち時間が最も短いことが分かる．これは，AHB-PB法では，セグメントの受信完了時
刻がそのセグメントの再生開始時刻と同時になるように，効

3

4

5

6

7

8

9

10

Bandwidth/Consumption RateFig.3

図 3 待ち時間の比較
The Comparison of Waiting Time

率的にスケジューリングしているためである．セグメントの受信開始から再生開始時刻までの時間全体を使ってセグメントを放送するため，帯域の削減につながり，待ち時間を効
率的に短縮できる．他の既存手法では，単純に帯域を数倍しているため，セグメントの再生開始時刻以前に受信完了できており，放送帯域を有効に利用できておらず，待ち時間が長くなる．例えば，23Mbps用いて5Mbpsの60分の映像データを放送する場合，AHB-PB法の待ち時間は0.58分，単純繰り返し手法では12.3分，拡張MTB法では16.3分となっている．

5. 考察
5.1 プリフェッチするデータの配信手法
本稿では，クライアントは全データのd%のデータをあらかじめプリフェッチしている．プリフェッチするデータの配信手法として「別チャネル配信手法」と「別時間配信手法」の2種類提案する．
5.1.1 別チャネル配信手法
放送帯域の一部をプリフェッチするデータの配信に用いる手法である．プリフェッチしていないクライアントも，プ
リフェッチを完了するまで待つことで最初から最後まで途切れずに再生できるが，プリフェッチされないデータの放送のために使用できる帯域が少なくなる．
5.1.2 別時間配信手法
ユーザがデータを再生する時間帯は，ほとんどの場合，限られている．例えば，ユーザは起床時刻から就寝時刻までの間でデータを再生する．現在の地上波放送では，主に午前5時から翌日の午前3時の間でデータを放送し，ユーザが就寝していると考えられる時間帯ではデータを放送していない．
そこで，別時間配信手法では，ユーザがデータを再生しないと考えられる時間帯にプリフェッチするデータを配信し，他の時間帯では残りのデータを配信する．放送帯域すべてをプ
リフェッチされないデータの放送に割り当てられるが，プリフェッチしていないクライアントは，初めから再生できない．
クライアントのデータの受信方法によってどちらの手法を用いるか異なる．例えば，クライアントが放送されている
データを常に受信しており，プリフェッチするデータを必ず受信できる場合には，別時間配信手法を用い，そうでない場
合には別チャネル配信手法を用いることが考えられる．

5.2 帯域の計算手法
AHB-PB法では，各チャネルの帯域を任意に与えることができるが，一般に，すべてのチャネルの帯域は等しい．このため，4章ではb1=…=bN=B/Nとした．本節では，すべてのチ
ャネルの帯域が等しくない場合の性能に関して考察する．比日本データベース学会 Letters Vol.4, No.1

論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――
0.5

Equivalent
Arithmetic
Geometric

Waiting Time/Playing Time

0.45
0.4
0.35
0.3
0.25
0.2
0.15
0.1
0.05
0
2

2.5

3

3.5

4

4.5

5

5.5

6

Bandwidth/Consumption RateFig.4

図 4 帯域計算手法と待ち時間
Methods for Calculating Bandwidth and the
Waiting Time under the AHB-PB Method

較対象として，等差数列および等比数列で各チャネルの帯域を与える．図4に，帯域の計算手法を変更した場合の待ち時間を示す．d=1%，N=13とした．“Equivalent”は4章と同じ
く，すべのチャネルの帯域を等しくした場合の待ち時間を示
す．“Arithmetic”は，b1=rとし，bi (i=1，…，N) を等差数列になるようにb1+a(i-1) で与えた場合の待ち時間を示す．公
差aは，b1+…+bN=Bとなるように算出した．“Geometric”は，
b1=rとし，等比数列になるようにbi=b1bi-1と与えた場合の待ち時間を示す．公比bは，b1+…+bN=Bとなるように算出した．
このグラフより，すべてのチャネルの帯域を等しくした場
合の待ち時間が最も短いことが分かる．これは，あるチャネルの帯域が小さいと，そのチャネルで放送するセグメントの配信に時間がかかり，待ち時間が長くなるためである．
ArithmeticやGeometricは，b1+…+bN=Bとなるようにaおよびbを算出したため，bNの帯域が比較的小さくなり，待ち時
間が長くなったと考えられる．

video-on-demand systems”, in Proc. of the ACM
SIGCOMM, pp. 89-100 (1997).
[3] Juhn, L.-S. and Tseng, L. M.: “Harmonic broadcastingfor video-on-demand service”, IEEE Trans. on
Broadcasting, Vol. 43, No. 3, pp. 268-271 (1997).
[4] NHK放送技術研究所：研究年報2000, p. 13 (2000)．
[5] Paris, J.-F., Long, D. D. E., Mantey, P. E.: “Zero-delay
broadcasting protocols for video-on-demand”, in Proc. of
the ACM Multimedia'99, pp. 189-197 (1999).
[6] Viswanathan, S. and Imilelinski, T.: “Pyramid
broadcasting for video on demand service”, in Proc. of
the SPIE Multimedia Computing and Networking Conf.
(MMCN'95), pp. 66-77 (1995).
[7] 義久智樹，塚本昌彦，西尾章治郎：“データの分割に関する制約を考慮した連続メディアデータ放送におけるス
ケジューリング手法”，情報処理学会論文誌：データベー
ス，Vol. 44, No. SIG3(TOD17), pp. 33-42 (2003)．
[8] 義久智樹，塚本昌彦，西尾章治郎：“早送りを考慮した
連続メディアデータ放送におけるスケジューリング手法”，
情 報 処 理 学 会 論 文 誌 ： デ ー タ ベ ー ス ， Vol. 45, No.
SIG7(TOD22), pp. 179—188 (2004)．
[9] 郵政省：“地上デジタル音声放送の導入へ向けて”，
http://www.soumu.go.jp/joho_tsusin/pressrelease/japan
ese/housou/000922j702.html (2000)．

義久 智樹

Tomoki YOSHIHISA

2002 年大阪大学工学部電子情報エネルギー工学科卒業．
2003 年同大学院情報科学研究科マルチメディア工学専攻博士前期課程修了．2005 年同専攻博士後期課程修了後，京都大学学術情報メディアセンター助手となり，現在に至る．博士（情報科学）．地上波デジタル放送に興味をもつ．日本データベース学会正会員，情報処理学会，電子情報通信学会，
各会員．

6. まとめと今後の課題

塚本 昌彦

プリフェッチを伴う連続メディアデータ放送において，放送帯域に制限を設けたうえで，待ち時間を短縮するスケジュ
ーリング手法AHB-PB法を提案した．AHB-PB法は，使用できる放送帯域を考慮して分割したデータをスケジューリン
グすることで，待ち時間を短縮する．既存手法で放送帯域を考慮するように拡張した手法と比較した結果，これらの手法よりも待ち時間を短縮できることを確認した．今後，途中から再生する場合の手法や，複数のデータを放送する場合のア
クセス頻度を考慮した手法を考えている．また，グリッドコ
ンピューティングへの応用を考えている．

1987 年京都大学工学部数理工学科卒業．1989 年同大学院工学研究科博士前期課程修了．同年，シャープ（株）入社．1995
年大阪大学大学院工学研究科情報システム工学専攻講師，
1996 年同専攻助教授，2002 年同大学院情報科学研究科マルチメディア工学専攻助教授，2004 年神戸大学工学部電気電子工学科教授となり，現在に至る．工学博士．NPO 法人ウェアラブルコンピュータ研究開発機構の理事長を務める．ウェアラブルコンピューティング・ユビキタスコンピューティ
ングに興味を持つ．ACM，IEEE など 8 学会の会員．

[謝辞]
本研究は，文部科学省21世紀COEプログラム「ネットワーク共生環境を築く情報技術の創出」，および科学研究費補助金(基盤研究(B)(2))「大規模な仮想空間システムを構築する
放送型サイバースペースに関する研究」(プロジェクト番号：
15300033)の研究助成によるものである．ここに記して謝意
を表す．

[文献］
[1] 藤原洋：“最新MPEG教科書”，マルチメディア通信研究会，アスキー出版局，東京，p. 152 (1997)．
[2] Hua, K. A. and Sheau, S.: “Skyscraper broadcasting: anewbroadcasting
schemefor
metropolitan

4

西尾 章治郎Masahiko TSUKAMOTO

Shojiro NISHIO

1975 年京都大学工学部数理工学科卒業．1980 年同大学院工学研究科博士後期課程修了．工学博士．京都大学工学部助手，
大阪大学基礎工学部および情報処理教育センター助教授，大阪大学大学院工学研究科情報システム工学専攻教授を経て，2002 年より同大学院情報科学研究科マルチメディア工学専
攻教授となり，現在に至る．2000 年より大阪大学サイバー
メディアセンター長，2003 年より大阪大学大学院情報科学研究科長を併任．この間，カナダ・ウォータールー大学，ビ
クトリア大学客員．データベース，マルチメディアシステムの研究に従事．現在，Data & Knowledge Engineering などの論文誌編集委員．本学会監事，情報処理学会フェロー，電子情報通信学会フェローをはじめ，ACM，IEEE を含め 8 学会の会員．

日本データベース学会 Letters Vol.4, No.1