動画像品質調整可能なプロキシキャッシュのためのキャッシングメカニズム 大阪大学 大学院 基礎工学研究科 情報数理系専攻 宮原研究室 博士前期課程1年 笹部昌弘 大阪大学の笹部です． 本日は，動画像品質調整可能なプロキシキャッシュのためのキャッシングメカニズムというタイトルで私の研究報告をさせていただきます． 2001/6/22

研究の背景 コンピュータの高性能化 アプリケーションのマルチメディア化 ネットワークの広帯域化 動画像ストリーミングサービスの増加 研究の背景といたしましては，コンピュータの高性能化やアプリケーションのマルチメディア化，ネットワークの広帯域化にともない，近年動画像ストリーミングサービスが増加しています．そこで，応答性や画質の高い動画像配信というものが求められています． 応答性，画質の高い動画像配信

応答性を高める手段 プロキシ技術 WWW上で広く用いられている ネットワークの負荷を抑える データ配送遅延を小さくする 動画像配信システムへの適用 応答性を高める手段として近年WWWシステムで広く用いられているプロキシ技術があります．サーバとクライアントの間にプロキシを置くことで，ネットワークの負荷を抑えると同時にデータ配送遅延を小さくすることが可能となります．そこで，このプロキシ技術を動画像配信システムにも適用することで，応答性の高い動画像配信が行えると考えられます．しかしながら，現在のプロキシ技術では，ファイルを単位とした処理をおこなうため，データサイズが非常に大きい動画像にはそのまま適用することができません．また，ネットワークへの接続形態やシステム性能，あるいはユーザの再生動画像品質への要求をクライアントごとに考慮しなければならないという問題があります． 問題点 ・動画像データは非常に大きいためファイルを単位とした取得，蓄積 には適していない ・ネットワークへの接続形態などによって異なる動画像品質への要求を クライアントごとに考慮しなければならない

研究の目的 動画像品質調整機能を組み込んだ プロキシキャッシングメカニズムの提案 クライアントへの応答性の向上 必要となるキャッシュバッファ容量の削減 そこで本研究では，動画像品質調整機能を組み込んだプロキシキャッシングメカニズムを提案しました．提案手法では，クライアントへの応答性の向上や必要となるキャッシュバッファ容量の削減を目標とします．

動画像品質調整機能を組み込んだ プロキシキャッシュを用いた動画像配信 サーバ クライアント 要求（高品質） プロキシ 要求（高品質） 転送（高品質） 読み出し 蓄積 転送（高品質） 高品質 加工 転送（低品質） 低品質 要求（低品質） それでは，動画像品質調整機能を組み込んだプロキシキャッシュを用いた動画像配信について説明させていただきます．まず，このクライアントから高品質な動画像データの要求がプロキシに届くと，プロキシはキャッシュバッファにそのデータがないため，サーバに高品質な動画像データを要求します．サーバは，要求されたデータをプロキシに転送し，プロキシではそのデータをキャッシュバッファに蓄積すると同時にクライアントに転送します．次に，このクライアントから同じ動画像データに対する低品質な要求がプロキシに届けられたとします．この場合，プロキシはキャッシュバッファに蓄積された先ほどのデータを加工しクライアントに転送します．これにより，応答性が向上し，またサーバ－プロキシ間のネットワークへの負荷を減らすことができます． MPEG-2動画像 キャッシュバッファ ネットワーク クライアント

動画像配信メカニズムにおける前提 MPEG-2動画像を対象 動画像データ通信のレート制御には TFRC (TCP Friendly Rate Control) を用いる GoP (Group of Pictures)を単位としたデータ配信 クライアントは定期的にデータ転送を要求品質とともに プロキシに要求 品質は量子化スケールの逆数によって表され，平均レートと量子化スケールの関係から決定されるものとする 提案する動画像配信メカニズムに関する前提について説明させていただきます．まず，対象とするのはMPEG-2動画像です．そして，動画像データ通信のレート制御にはTFRC (TCP Friendly Rate Control)とよばれるマルチメディアデータ通信のためのレート制御手法を用います．TFRCについて簡単に説明させていただきますと，end-to-endでコントロールパケットを交換し，得られたRTTやパケット棄却率といったフィードバック情報をもとにTCPのレートに近づけるというものです．サーバ－プロキシ間，プロキシ－クライアント間で動画像通信に対して利用可能な帯域はこのTFRCにより得られた帯域であるとみなします．また，GoPと呼ばれるピクチャの集まりを単位としたデータ配信を想定し，クライアントは，定期的にGoPを単位としてデータ転送を要求品質とともにプロキシに要求します．ただし，品質は量子化スケールの逆数によって表されるものとし，量子化スケールは平均レートと量子化スケールの関係をもとにTFRCによって得られた帯域から決定されるものとします．

検討課題 応答性の向上（キャッシュミス発生の抑制） 必要となるバッファ容量の削減 要求品質を考慮した動画像データ取得 近い将来に必要となる動画像データの先読み 必要となるバッファ容量の削減 キャッシュデータの効果的な置き換え このような前提のもとで，検討すべき課題といたしましては，「応答性の向上」と「必要となるバッファ容量の削減」が考えられます．応答性の向上に関しては，キャッシュミスの発生が応答性を悪くすると考えられるため，いかにしてキャッシュミスを防ぐがということを検討する必要があると考えられます．具体的には，クライアントの要求品質を考慮した動画像データ取得や，近い将来に必要となる動画像データの先読みといった対策方法が考えられます．一方，必要となるバッファ容量の削減に関しては，新しく取得したデータとキャッシュデータを効果的に置き換えることで実現できると考えられます．

キャッシュミス発生時にサーバから 動画像データを取得する際の問題 クライアントからのデータ転送要求は定期的にプロキシに到着 要求発生間隔内で要求されたデータを 転送できなければ遅延が発生してしまう 動画像データ取得の際には，クライアントの要求品質だけでなく，サーバｰプロキシ間の利用可能な帯域の状態も考慮しなければならない まず，キャッシュミス発生時にサーバから動画像データを取得する最さきほど申し上げたようにクライアントからのデータ転送要求は定期的にプロキシに到着します．そのため，クライアントからの要求発生間隔内に要求されたデータを転送できないと次の要求データの転送開始が遅れ，遅延が発生してしまいます．このため，動画像データをサーバから取得する際には，クライアントの要求品質だけでなく，サーバ－プロキシ間の動画像データ転送に利用可能な帯域の状態も考慮しなければなりません． サーバｰプロキシ間の利用可能な帯域の 状態によってはクライアントの要求品質 どおりのデータを時間内に取得できない

要求品質を考慮した動画像データ取得 サーバｰプロキシ間の利用可能な帯域が大きく， 要求品質を満たせるデータを時間内に取得できる場合 将来そのデータを参照すると予測されるクライアントを考慮し， それらの要求品質のうち最大のものを要求する 各クライアントが参照しているGoP まず，要求品質を考慮した動画像データ取得について説明させていただきます．動画像データ取得の際には，サーバ－プロキシ間の利用可能な帯域が大きく，要求品質を満たせるデータを取得できる場合とそうでない場合があります．ここでは，まず前者の場合について説明します．この場合，キャッシュデータの再利用性を高めるため，現在の要求品質どおりのデータをサーバから取得するのではなく，将来そのデータを参照すると予測されるクライアントを考慮し，それらの要求品質のうち最大のものを要求します．具体的には，このように1本の動画像ストリームを4人のクライアントがそれぞれこのような場所を見ているとします．この場合，このデータに対してはこれら3人が対象となります． Start End 動画像ストリーム

画質と実時間性の優先 サーバｰプロキシ間の利用可能な帯域が小さく， 要求品質を満たせるデータを時間内に取得できない場合 ユーザは画質と実時間性のどちらを優先したいのか？ ユーザの動画像配信サービスに対する要求を表す指標bの導入 ・ b → 0 ならユーザは実時間性の高いサービスを要求 ・b → 1 ならユーザは高品質な動画像を要求 b はユーザ側のアプリケーションからプロキシに伝えられる 要求品質 提供される品質 b はユーザが許容する の下限 一方，サーバ－プロキシ間の利用可能な帯域が小さく，要求品質を満たせるデータを取得できない場合には，画質を優先する手法と実時間性を優先する方法の2とおりが考えられます．そこで，ユーザの動画像配信サービスに対する要求を表す指標βを導入します．βはクライアントへの提供品質のクライアントからの要求品質に対する比で表され，βが０に近いほどユーザが実時間性の高いサービスを要求していることを，βが1に近いほどユーザが高品質な動画像を要求していることを表します．βの値はクライアントの使用するアプリケーションからプロキシに伝えられるものとします．

サービスに対する要求を考慮した 動画像データ取得 b にもとづく制御 要求品質 キャッシュデータの品質 £ b データ取得は行わずクライアントにはキャッシュデータを提供 サーバから取得可能な品質 £ b 要求品質 サーバからデータを取得 プロキシが提供可能な品質 それでは，βに基づく具体的な制御の方法について説明させていただきます．まず，1番目の場合についてですが，この場合キャッシュデータでクライアントの要求をほぼ満たせるため，データ取得は行わずクライアントにはキャッシュデータを提供します．2番目の場合についてですが，この場合サーバから取得可能な品質でクライアントの要求をほぼ満たせるためサーバからデータを取得します．最後に，キャッシュデータの品質が低く，またサーバ－プロキシ間の利用可能な帯域も小さい場合には，クライアントからの要求を最低限満たせるだけの品質，すなわち要求品質のβ倍のデータをサーバから取得することにより，できるだけ転送遅延を少なくします． < b b ×要求品質のデータを取得 要求品質

先読みメカニズム キャッシュデータの品質 現在の要求品質 先読みの対象となるデータ 先読みの必要性を 検索する範囲 現在の参照位置 次に，先読みメカニズムについて説明します．まず，キャッシュデータの状態がこのようになっているとし，現在の参照位置がここであるとします．すると，先読みの必要性を検索する範囲はこのようになります．そうすると，現在の要求品質を下回るこのデータが先読みの対象となります．先読みの対象となったデータは先ほど述べたキャッシュミス時の品質決定手法に基づきサーバから取得されます． 動画像ストリーム内の時刻

キャッシュデータ置き換えアルゴリズム 動画像ストリーム 置き換えの対象となるデータを検索 動画像品質調整機能によるデータ量削減， およびバッファ内の空き容量の確保 キャッシュからデータを掃き出すことによる バッファ内の空き容量の確保 動画像の先頭のデータもしくは クライアントの要求データ 参照性の低いデータ 先読みの必要性を検索する範囲内のデータ 1 置き換えの対象となるデータ 動画像ストリーム Start 次に，キャッシュデータの置き換えアルゴリズムについて説明します．手順といたしましては，まず置き換えの対象となるデータを検索します．具体的な検索方法としましては，まず，このように1本の動画像ストリームがあるとします．そうすると，各クライアントの参照しているデータと動画像の先頭のデータがもっとも参照性が高く，ついでそれぞれに対する先読みの範囲内のデータが参照性が高いと考えられます．これら以外のデータに関しては，比較的参照性が低いと考えられます．これら参照性の低いデータの数が各クライアントごとにこのように求められ，この数が大きいところから優先して置き換えの対象とします．この場合ですと，最後のデータになります．このようにして，置き換えの対象となったデータに関してはまず動画像品質調整機能を用いることでデータ量を削減します．これによって得られた空き容量が新しいデータを蓄積するのに十分である場合には置き換え終了，不十分である場合には，そのデータをキャッシュから掃き出します．それでも空き容量が不十分である場合には，新しい置き換えの対象となるデータを検索します．この場合ですと，このデータになります．以下，このように決定されます． End 8 7 5 3 6 4 2 7 2 6 4 5 6 高 キャッシュに残される優先度 低

評価モデル 動画像配信サービスへの参加クライアント数は10 すべてのクライアントは同一の動画像ストリームを鑑賞する TCP sessions TCP sessions Client Server Router Router Proxy Router Router UDP sessions UDP sessions 150 Mbps 50 Mbps 動画像配信サービスへの参加クライアント数は10 すべてのクライアントは同一の動画像ストリームを鑑賞する クライアントあたりの動画像再生時間は2時間 クライアントの到着間隔は平均30分の指数分布に従う 以上の提案メカニズムをシミュレーションにより評価しました．評価モデルは，このようになっており，サーバ－プロキシ間の帯域は150Mbps，プロキシ－クライアント間の帯域は50Mbps，それぞれの帯域をTCPとUDPのセッションが共有しています．動画像配信サービスへの参加クライアント数は10で，すべてのクライアントは同一の動画像ストリームを鑑賞するものとします．クライアントあたりの動画像再生時間は2時間，クライアントの到着感覚は平均30分の指数分布に従うものとします．

評価指標 必要となるバッファ容量 再生開始までの待ち時間 受信動画像品質に対する満足度 キャッシュ内データ量の変化 動画像全体を通した，各データに対する フレームレートから求められる理想的な到着時刻と 実際の到着時刻とのずれの最大値 受信動画像品質に対する満足度 要求品質に対する受信動画像品質の比の平均 次に，評価指標ですが，まず必要となるバッファ容量があげられます．これは，キャッシュないデータ量の変化を調べることにより評価を行いました．次に，応答性の評価のために再生開始までの待ち時間を評価しました．再生開始までの待ち時間とは，動画像全体を通した，各データに対するフレームレートから求められるクライアントへの理想的な到着時刻と実際の到着時刻とのずれの最大値によってあらわされます．最後に，クライアントの受信動画像品質に対する満足度を評価しました．これは，動画像全体を通して要求品質に対して実際に受信した品質がどのていどのものであったかをあらわすもので，要求品質に対する受信動画像品質の比の平均で表されます．

シミュレーション結果 （キャッシュ内データ量の変化） 動画像品質調整機能なし（無限バッファ） 160 キャッシュ内データ量 提案手法（無限バッファ，先読みなし，β=1） 140 提案手法（バッファ20 Gbit，先読みあり，β=0.6） 120 100 80 60 まず，キャッシュ内データ量の変化についてですが，赤い線は従来の動画像品質調整機能を持たないプロキシを用いた場合の無限バッファにおけるキャッシュ内データ量の変化です．品質調整機能を持たないため，同じ動画像データに対して異なる品質のデータを複数保持するため必要となるバッファ容量が非常に大きくなっていることがわかります．これに対して緑の線は，提案手法で同じく無限バッファとした場合の結果です．動画像品質調整機能を導入することにより，同じ動画像データに対して異なる品質のデータを複数保持するということがないため必要となるバッファ容量が大きく削減できていることがわかります．さらに，黄色の線は提案手法において，バッファ容量を20Gbit，先読みありとした場合の結果を表しています．ただし，クライアントはある程度画質に対して寛容であると仮定しβ=0.6としました．ごらんのように制約どおり20Gbitを満たせていることがわかります． 40 （Gbit） 20 5000 10000 15000 20000 時間 （秒）

シミュレーション結果 （再生開始までの待ち時間） 動画像品質調整機能なし（無限バッファ） 再生開始までの待ち時間 （秒） 25 提案手法（無限バッファ，先読みなし，β=1） 提案手法（バッファ20 Gbit，先読みあり，β=0.6） 20 15 10 次に，再生開始までの待ち時間に関するシミュレーション結果を示します．赤と緑の線により，動画像品質調整機能を導入することで全体的に再生開始までの待ち時間を減らせていることがわかります．なお，従来手法においてクライアント５に対する性能がほかに比べて著しく悪くなっていますが，これはクライアント５の要求品質が全体的にみてそれまでのクライアントの要求品質よりも高く，かつサーバ－プロキシ間の利用可能な帯域が小さかったためです．また，バッファ容量を有限の20Gbitとした場合にも，画質に対してある程度寛容なユーザを想定した場合，先読みメカニズムと置き換えアルゴリズムにより，再生開始までの待ち時間を減らせていることがわかります． 5 1 2 3 4 5 6 7 8 9 クライアント番号

シミュレーション結果 （受信動画像品質に対する満足度） 1 動画像品質調整機能なし（無限バッファ） 提案手法（無限バッファ，先読みなし，β=1） 提案手法（バッファ20 Gbit，先読みあり，β=0.6） 0.8 0.6 0.4 最後に，受信動画像品質に対する評価ですが，赤と緑の線により従来手法と提案手法で無限バッファとした場合にはユーザの要求どおりの品質の動画像を受信できていることがわかります．また，黄色の線で示すように，βを0.6とした場合にも全体的に0.8を上回る品質の動画像データを提供できており，高品質な動画像データ配信が実現できていると言えます． 0.2 1 2 3 4 5 6 7 8 9 クライアント番号

まとめと今後の課題 まとめ 今後の課題 ネットワーク環境やキャッシュバッファ容量などを 考慮したキャッシングメカニズムの提案 提案手法により応答性の高い動画像配信サービスをクライアントに提供できることを明らかにした 今後の課題 再生開始までの待ち時間の短縮 早送り，巻き戻し操作への対応 最後に，まとめといたしましては，ネットワーク環境やキャッシュバッファ容量などを考慮したキャッシングメカニズムの提案を行いました．そして，提案手法により応答性の高い動画像配信サービスをクライアントに提供できることを明らかにしました．今後の課題といたしましては，再生開始までの待ち時間のさらなる短縮，早送り，巻き戻し操作への対応といったことがあげられます． これで，私の研究報告を終わらせていただきます．