論文
DBSJ
DBSJ Letters Vol.2, No.1
Data Stream――――――――――――――――――――――――――――――――――――.......

Caching Strategy
Strategy Considering ThinkThink-timeof Data Access for PushPush-based Broadcast

内田 渉♥

原 隆浩♦

本論文では，クライアントが相関性をもつ複数のデータアイテムに対して，時間間隔をおいて連続的にアクセス要求を発行するようなプッシュ型情報システムを想定し，データア発行するようなプッシュ型情報システムを想定し，データアクセスの平均応答時間短縮のためのキャッシング方式を提案する．提案方式では，データ間の相関性およびデータ利用時間を考慮して，次回，および次々回のアクセス要求に対する応答時間の利得が大きいデータアイテムをあらかじめキャッシュする．
In this paper, to reduce the response time of data access,we propose new caching strategies assuming apushn which clientspush-based information system iin
consecutively issue access requests for multiple data
items with think time. The proposed strategies takes into
account each client's access characteristics such ascorrelations among data items and thinkthink-time between adata access and the next access request and caches data
items with long expected response times of next and after
the next access requests.

1. はじめに
近年，サーバが放送型通信を用いてクライアントにデータを配送するプッシュ型情報システム（以下では単にプッシュ型情報システムと呼ぶ）への関心が高まっている．プッシュ型情報システムでは，クライアントはアクセス要求をサーバに送信せずにサーバの放送帯域を監視し，そのデータが放送された時点でアクセスを完了する（図1）．プッシュ型情報シ
ステムでは，サーバは各クライアントから離散的に発生する要求を一度の放送により満たすため，クライアント数が増加してもシステム全体の負担コストはほとんど変化しない．また，アクセス要求がサーバへ送信されないため，クライアン
ト数が増加した場合の上り帯域での競合も発生しない．したがってクライアント数が非常に多い環境において，アクセススループットの向上が期待できる．
プッシュ型情報システムの性能向上のために，平均応答時間を短縮を目的とする方式がこれまでに多数提案されている．
それらは主に，サーバ側でのスケジューリング戦略[1,4,9]とクライアント側でのデータアイテムのキャッシュ戦略[2,5,6]の二つに分類される．これらの従来研究では，各デー♥

学生会員 大阪大学情報科学研究科マルチメディア工学専
wataru@ist.osaka-u.ac.jp♦
正会員 大阪大学情報科学研究科マルチメディア工学専攻{hara, nishio}@ist.osaka-u.ac.jp
攻1

Data1

4
2

3

Server

西尾 章治郎♦Wataru UCHIDA Takahiro HARA
Shojiro NISHIO

5

Broadcast

プッシュ型放送のためのデータ利用時間を考慮したキャッシング法

Clients

図1Fig.1

プッシュ型情報システム

A push‑push‑based information system.

タに対するアクセス確率が時間的に一定と仮定して，効果的スケジューリングおよびキャッシングを行っている．
一方，クライアントがアクセスするデータ間には，相関性が存在するのが一般的である．例えば，実環境におけるプッシュ型放送の代表的なサービスであるテレビ朝日データのADAMS[3]では，サーバは複数のカテゴリに分けられた様々なWebページ形式のデータを地上波テレビ放送の隙間帯域を利用して放送する．このとき，サービスの利用者はあるデー
タを閲覧した後，そのデータと同じカテゴリに属するデータを連続してアクセスすることが多い．つまり，同じカテゴリに属するデータは相関性をもち，それらに対するアクセス要求は，ある時間間隔をおいて連続的に発行されることが多い．
このような場合，各データに対するアクセス確率は時間的に一定とはならない．そこで筆者らは，相関性に基づくアクセス要求が時間間隔をおいて発生する環境におけるスケジューリング方式を，文献[7],[10]において提案した．また，文献[8]において，クライアント側のキャッシング方式である
RIB-PT（Request Interval Based PT）法を提案した．RIB-PT法はデータ間の相関性およびアクセス要求の発行間隔を考慮し，次回に発行されるアクセス要求に対する応答時間の利得が大きくなるようにキャッシュを管理する．しかし，次回に発行されるアクセス要求のみを考慮するため，アクセス要求の発行間隔が短く，次々回のアクセス要求がすぐに発行されるような場合は，性能が劣化する．そこで本論文では，次回および次々回に発行されるアクセス要求の応答時間を考慮するようにRIB-PT法を拡張したキャッシング方式を提案する．
本論文では，次のようなシステム環境を想定する．
サーバは一つとし，オンデマンド型放送は行わない．
サーバで放送されるデータはデータアイテムと呼ばれる単位で放送される．データアイテムは M 種類存在し，1から M の識別子を用いて区別する．
各データアイテムのサイズは全て等しいものとし，1 アイ
テムの放送にかかる時間を 1 タイムスロットとする．
クライアントはキャッシュをもつ．キャッシュに保持しているアイテムに対するアクセス要求の応答時間は 0 とし，保持していないアイテムに対する応答時間は，アクセス要求が発行されてから，そのアイテムの次回の放送時刻までの時間とする．
クライアントは放送プログラムを知っている．
各クライアントにおけるデータ間の相関性などのアクセ
ス特性は，各クライアントで異なり，これらは各クライアントにおいて既知とする．
データの更新は発生しない．
以下，2章で放送アイテム間の相関性およびアクセス要求の発生に関する本論文の想定について述べる．3章で従来方式に

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

論文
DBSJ
DBSJ Letters Vol.2, No.1――――――――――――――――――――――――――――――――――――ついて述べ，4章で提案方式を説明する．5章で性能評価について述べ，最後に6章で本論文のまとめを行う．

2. 相関性とアクセス要求
一般に，サーバから放送されている様々なデータアイテムは，あるデータアイテム集合がまとめてアクセスされることが多いといったように，互いに相関性をもつことが多い．例
えば，1 章における ADAMS の例のように，サーバが HTML
ファイルや画像ファイルなどの Web ページを構成する要素をまとめて一つのデータアイテムとして，様々な Web ページを，デジタル放送帯域などを利用して多数のクライアントにプッシュ型配信する場合を考える．クライアントが，ある Web サイトのページを閲覧する場合，まずはトップページにアクセス要求を発行する．トップページを取得すると，クライアン
トはある時間，そのページを閲覧し，そのページからリンクされる別のページにアクセス要求を発行する．したがって，各ページからリンクされている他のページは，リンク元のページと相関性をもつ．
本論文では，上記の例のように，クライアントが配信されたデータアイテムを利用する時間が，そのデータアイテムの配信に要する時間に比べて充分大きく，相関性をもつ個々のデータアイテムすべてが時間間隔をおいてアクセス要求される環境を想定する．以下では，この時間間隔をデータ利用時間と呼ぶ．ここでクライアントは，一つ目のデータアイテムに対して，ある確率で無記憶性のアクセス要求を発行した後，それと相関性をもつデータアイテムに，ある確率密度関数に従ったデータ利用時間をおいて連鎖的にアクセスを複数回行うものと想定する．その一連のアクセスをプロセスと呼び，各プロセスにおいて始めにアクセスされるアイテムを先頭アイテムと呼ぶ．
相関性の強さは，クライアントがあるデータアイテムにアクセスした後の，他のデータアイテムへの連続したアクセス要求の発生確率として定義することができる．実環境において，各クライアントにおけるアイテム間の相関性や，データ利用時間を示す確率密度関数は，クライアントのアクセス履歴を調べることで決定できる．

3. 従来のキャッシング方式
プッシュ型情報システムのためのキャッシング方式として，
文献[2]において PT 法が提案されている．PT 法は，データアイテム間の相関性は考慮せず，すべてのアクセス要求が無記憶に発生する環境を想定している．一方，筆者らは文献[10]において，クライアントが相関性のあるアイテム集合に対して，データ利用時間をおいてアクセス要求を発行する環境を想定し，PT 法を拡張した RIB-PT 法を提案した．
以下では，PT 法および RIB-PT 法の概要を説明する．

3.1

PT 法

PT 法では，次の手順でキャッシュの置き換えを行う．
各アイテムの放送開始時に，キャッシュ内のアイテムおよび放送されるアイテムに PT 値と呼ばれる値を与える．
アイテム i に与える PT 値 Li は次式で表される．
Li = pi ⋅ (ui (t ) − t )(1)

ただし，pi はアイテム i に対するそのクライアントのアクセス確率，t は現在時刻，ui(t)は時刻 t におけるアイテム iの次回の放送時刻とする．
放送されるアイテム B の PT 値 LB が，キャッシュ内で2PT 値が最小となるアイテム j の PT 値 Lj より大きい場合，アイテム B と j を置き換える．
PT 法では，各アイテムの放送開始時に，各々のアイテムをキャッシュから追い出すことにより増加する待ち時間（PT値）を比較し，最も応答時間の利得が大きいようにキャッシュを管理する．しかし，アイテム間に相関性が存在する場合，各アイテムのアクセス確率は時間的に一定とはならないため，正確に応答時間の利得を計算することができない．

3.2

RIBRIB-PT 法

現在時刻 τ において，クライアントが最近にアクセス要求を発行したアイテムを i とし，i のアクセス（予定）時刻を ζとする．時刻 τ におけるアイテム j の次回の放送時刻を u j (τ )とすると，時刻 t（ τ ≤ t ≤ u j (τ ) ）に発生する j へのアクセス要求の応答時間は，j がキャッシュにない場合，( u j (τ ) − t )となる．したがって，j をキャッシュに格納しないことで生じる，次回のアクセス要求に対する平均応答時間の増加分（期待値）
Rj は次式のように表される．この値を，アイテム j の RIB-PT値と呼ぶ．

∫u j (τ )f ij (t − ζ ) ⋅ (u j (τ ) − t )dt(2)ただし，Sj は次式で表される．
(τ < ζ )c ij
Sj = τc ij 1 − ∫ζ f ij ( t − ζ )dt (ζ ≤ τ )(3)

Rj = S j ⋅τ()

RIB-PT 法では，次の手順でキャッシュの置き換えを行う．
各アイテムの放送開始時に，キャッシュ内および放送中のアイテムに対して，式(2)で表される RIB-PT 値を計算する．
放送されるアイテム B の RIB-PT 値 RB がキャッシュ内で RIB-PT 値が最小となるアイテム j の RIB-PT 値
Rj より大きい場合，アイテム i と j を置き換える．

4. RIBRIB-PT 法の拡張
RIB-PT 法は，次回に発行するアクセス要求の応答時間のみを考慮してキャッシュの置き換えを行う．そのため，キャッシュのヒット率が高く，放送待ち時間が存在しないことが多い場合や，データ利用時間が短い場合には，効果的なキャッシュの置き換えが行えないため，性能が劣化する．
そこで，現時点を基準として次々回に発行するアクセス要求に対する応答時間も考慮するように，RIB-PT 法を拡張する．
以下では，現時点を基準として，次回に発行するアクセス要求に対する応答時間を第一応答時間，次々回に発行するアクセス要求の応答時間を第二応答時間と呼ぶ．
ここで，直前にアクセス要求を発行したデータアイテムをi，そのアクセス（予定）時刻を ζ とし，次回はデータアイテ
ム x（ x ≠ i , j ）にアクセスするものと仮定する．このとき，xのアクセス時刻を r とすると，j の次回の放送時刻 u j (τ ) 以前に x をアクセスしたクライアントが，j に対して発行するアクセス要求の応答時間の期待値は，次式で求められる．

∫u j (τ )rc xj ⋅ f xj (t − r ) ⋅ (u j (τ ) − t )dt(4)

ここで，x が常にキャッシュに存在する場合，x のアクセス時刻 r は x に対するアクセス要求が発行された時刻と等しい．
そのため，x のアクセス時刻 r の確率密度関数は次式で与えられる．
S x ⋅ f ix (r − ζ )(5)
式(4)および式(5)より，次回にキャッシュ内に存在するアイ

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

論文DBSJDBSJ Letters Vol.2, No.1――――――――――――――――――――――――――――――――――――
テム x をアクセスし，さらにアイテム j をアクセス要求する場
合の応答時間の期待値は，次式で与えられる．
E jx = S x ⋅∫∫u j (τ )τu j (τ )rf ix (r − ζ ) ⋅(6)c xj ⋅ f xj (t − r ) ⋅ (u j (τ ) − t )dtdr

一方，データアイテム x が常にキャッシュに存在しない場
合，x のアクセス時刻 r は，アクセス要求発生後の最初の x の放送時刻となる．ここで，時刻 max( τ , ζ )と uj( τ )の区間における，x の全ての放送時刻の集合を A とする．ただし，max( τ , ζ )は，τ と ζ のうちで大きい方の値を表している．このとき，vx(t)を時刻 t 以前の前回の x の放送時刻とすると，クライアントが区間内の各放送時刻 r ( r ⊂ A )において x をアクセスする確率は，次式で与えられる．
Sx ⋅∫rmax(τ ,ζ ,v x ( r ))f ix (t − ζ )dt(7)

式(4)および式(7)より，データアイテム i を最近にアクセス要求したクライアントが，次にキャッシュに存在しないデー
タアイテム x をアクセスし，続いて j をアクセス要求する場合，
時刻 τ の時点での応答時間の増加分（期待値）Njx は次式で与えられる．
 r
N jx = S x ⋅f ix (t − ζ )dt
max(τ ,ζ ,v x ( r ))r⊂A(8)u j (τ )⋅c xj ⋅ f xj ( t − r ) ⋅ (u j (τ ) − t )dt r
以上より，データアイテム x がアクセス要求される時点でのキャッシュ状態が既知であれば，全てのデータアイテム xに対して Ejx もしくは Njx を計算し，総和をとることによって，j に対する第二応答時間の期待値を求めることができる．しかし，キャッシュの状態はは，キャッシング方式の動作に依存して，各タイムスロット毎に変化する．また，Rj や Njx は，あらかじめ不定積分の形で求めておけば定数時間での計算が可能であるが，Ejx を計算するためには，二重積分が必要となり，各タイムスロット毎に実時間で計算を終了することは困難である．そこで，計算量の削減のために，第二応答時間の期待値を近似的に求めるヒューリスティックなアプローチをとる，
TR-NC（Two step RIB-PT, Neglect of Cache）法と呼ぶ方式を提案する．
TR-NC 法では，第二応答時間の計算の際に，次回アクセスするデータアイテム x は常にキャッシュに存在しないものと仮定する．Ejx の計算に伴う二重積分が省かれるため，計算量を削減できる．具体的な手順は次の通りである．

∑∫∫TRTR-NC 法
各アイテムの放送開始時に，キャッシュ内および放送中のアイテムに対して，式(2)で表される RIB-PT 値を計算する．
上記のアイテムに対して，次回にアクセスするデータアイテムが全てキャッシュに存在しないものと仮定した第二応答時間の期待値を RIB-PT 値に加えたものを，アイ
テム i の TR-NC 値 Wi として次式のように求める．
MW i = Ri +

∑N

ix

(9)

x =1

放送されるアイテム B の TR-NC 値 WB がキャッシュ内で TR-NC 値が最小となるアイテム j の TR-NC 値 Wj より大きい場合，アイテム B と j を置き換える．

35. 性能評価
本章では，提案方式の性能評価のために行ったシミュレーション実験の結果を示す．

5.1 評価環境評価では，ADAMS のように，様々なカテゴリに分けられた Web ページ形式のデータを，一つの Web ページを 1 データアイテムとしてプッシュ型配送するシステムを想定した．
まずデータアイテム数を 500 とし，全データアイテムをアイテム数 100 の 5 つのグループ（グループ G1, G2, .., G5）に分割した．各グループは，上記のカテゴリを示している．cij（データアイテム間の相関性の強さ）は，乱数を用いて与え，i,j ⊂ Gk, ( 1 ≤ k ≤ 5 ) の 場 合 は 10% ， i ⊂ Gk , j ⊂ Gl ,( 1 ≤ k , l ≤ 5, k ≠ l )の場合は 40%の確率で cij > 0 とした．
つまり，各データアイテムは同じグループのデータアイテムとはそれぞれ 10%，別のグループのデータアイテムとはそれぞれ 40%の確率で相関性をもつ．ここで，それぞれの cij の値は，グループ内，グループ間でそれぞれ等しいものとし， ∑i , j⊂Gk c ij =0.8， ∑i ⊂Gk ∩ j⊂Gl ∩k ≠l c ij = 0.2 とした．
さらに，プロセス発生時の先頭アイテムがデータアイテム iである確率 qi は，グループ 1 に属するデータアイテムのみ高いものとし，他のグループに属するデータアイテムの 16 倍とした．タイムスロット毎のプロセス発生確率は 0.01，あるア
クセスを終了した時点でプロセスを終了する確率も 0.01 とした．
各アイテム間 i-j において，要求発生の時間間隔（データ利用時間）の確率密度関数を，次式で与えた（図 2）．
30 −2 (t − m ) + 30 −1

f ij (t ) = − 30 − 2 (t − m ) + 30 −1
0(m − 30 ≤ t < m )(m ≤ t ≤ m + 30)(t < m − 30, t > m + 30)(9)

評価では，i-j 間のデータ利用時間の平均値を表す m を，( µ -10,µ +10)の区間の一様分布で与えた．
サーバは，全てのアイテムを一度ずつランダムに配置したプログラムを，周期的に放送するものとした．評価では，PT法，および RIB-PT 法を比較対象とした．PT 法におけるアクセス確率 pi は，i が先頭アイテムである確率 qi で与えた．

5.2 評価結果

以上のような評価環境において，3,000,000 タイムスロットのシミュレーション実験によって，提案方式の性能評価を行った．
キャッシュに格納可能なデータアイテム数を 100 とし，平均データ利用時間 m の平均値 µ を 50 から 400 まで変化させた場合の平均応答時間を図 3 に示す．図 3 より，相関性およびデータ利用時間を考慮してキャッシュの置き換えを行う
RIB-PT 法と提案方式である TR-NC 法の二つの方式が，µ が大きくなるほど平均応答時間を短縮していることがわかる．
これは，平均のデータ利用時間が長い方が，次回に発行されるアクセス要求までに放送されるデータアイテムが多く，効果的なデータアイテムをキャッシュする機会が多くなるためである．
また，平均データ利用時間が短い場合は，第二応答時間を考慮する TR-NC 法が，RIB-PT 法よりも良い性能を示している．これは，次回のデータアクセスが行われてから，次々回のアクセス要求が発行されるまでの間隔が短いため，第一応答時間しか考慮しない RIB-PT 法ではキャッシュの入れ換えが十分行われないためである．
データ利用時間が非常に長い場合，次回のデータアクセス

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

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

6. おわりに
本論文では，クライアントが相関性のあるデータアイテムのアクセス要求を，データ利用時間をおいて連続的に発行するプッシュ型情報システムを想定して，応答時間短縮のためのキャッシング方式を提案した．提案方式では，データ利用時間およびデータアイテム間の相関性に基づいて，次回および次々回のアクセス要求に対する応答時間の利得を計算し，その利得が大きいようにキャッシュを置き換える．
さらに本論文では，シミュレーション実験により，提案方式の性能評価を行った．性能評価の結果，データ利用時間を考慮しない従来方式や第一応答時間のみを考慮する方式と比較して，応答時間を大幅に短縮することを確認した．今後は，提案方式をさらに簡単化することによって，PDA などの計算資源が乏しいクライアンに対応する予定である．

[謝辞]
謝辞]
本研究は，文部科学省 21 世紀 COE プログラム（研究拠点形成費補助），文部科学省特定領域研究(14019063)および文部科学省科学技術振興調整費「モバイル環境向 P2P 型情報共有基盤の確立」の研究助成によるものである．ここに記して謝意を表す．

f i,j ( t )-130t
0m -30mm +30

図 2 評価実験における fij
Fig.2

fij in the evaluation.

180
average response time ( time slots )が行われた後，次々回のアクセス要求が発行されるまでに，第二平均応答時間の計算対象となるデータアイテムが再び放送される確率が高い．そのため，第二応答時間を考慮する効果は小さく，RIB-PT 法でも十分な性能を示している．

160140PT
RIB-PT
TR-NC

1201008060402050100150200250300

350

400µFig.3

図 3 µ と平均応答時間．
µ vs. average response time.

[文献］[1] Acharya, S., Alonso, R., Franklin, M., and Zdonik, S.:“Broadcast Disks: Data Management for AsymmetricCommunication Environments”, Proceedings of ACM
SIGMOD'95, pp. 199-210 (1995).
[2] Acharya, S., Franklin, M., and Zdonik, S.: “Prefetchingfrom a Broadcast Disk”, Proceedings of ICDE '96, pp.
276-285 (1996).
[3] テレビ朝日データ [ADAMS], <URL: http://www.tv-asahidata.com/>.
[4] Erçetin, Ö. and Tassiulas, L.: “Push-Based Information
Delivery in Two Stage Satellite-Terrestrial WirelessSystems”, IEEE Transactions on Computers, Vol. 50, No.
5, pp. 506-518 (2001).
[5] Su, C. J. and Tassiulas, L.: “Joint Broadcast
Scheduling and User's Cache Management for Efficient
Information Delivery”, Wireless Networks, Vol. 6, No. 4,
pp. 279-288 (2000).
[6] Tassiulas, L. and Su, C. J.: “Optimal Memory
Management Strategies For a Mobile User in aBroadcast Data Delivery System”, IEEE Journal on
Selected Areas in Communications, Vol. 15, No. 7, pp.
1226-1238 (1997).
[7] 内田渉，原隆浩，西尾章治郎: “アクセス要求発生頻度の時間的変化を考慮した相関データの放送スケジューリング”，情報処理学会論文誌：データベース，Vol. 43，No. SIG 9(TOD 15)，pp. 28-38 (2002)．
[8] 内田渉，原隆浩，西尾章治郎: “プッシュ型放送のためのデータ利用時間と相関性を考慮したキャッシング方式”，情報処理学会研究報告（DBS-129/BCC-4），pp. 67-74 (2003)．
[9] Vaidya, N. H. and Hameed, S.: “Scheduling Data Broadcast in Asymmetric Communication Environments”,

4Wireless Networks, Vol. 5, No. 3, pp. 171-182 (1999).
[10] 矢島悦子，原隆浩，塚本昌彦，西尾章治郎: “相関性をもつデータ間の放送時間間隔について”，情報処理学会論文誌，Vol. 40，No. 1，pp. 188-196 (1999)．

内田 渉

Wataru UCHIDA2002 年大阪大学大学院工学研究科博士前期課程修了．同年，同大学院情報科学研究科博士後期課程入学，現在に至る．データベースシステムおよび放送型通信に興味をもつ．日本データベース学会会員．

原 隆浩

Takahiro HARA

1997 年大阪大学大学院工学研究科博士前期課程修了．同年，博士後期課程中退後，同大学院工学研究科情報システム工学専攻助手．2002 年同大学院情報科学研究科マルチメディア工学専攻助手となり，現在に至る．工学博士．データベースシ
ステム，モバイルコンピューティングなどの研究に従事．
IEEE，電子情報通信学会，情報処理学会，日本データベース学会の各会員．

西尾 章治郎Shojiro NISHIO

1980 年京都大学大学院工学研究科博士後期課程修了．工学博
士．京都大学工学部助手，大阪大学基礎工学部および情報処理教育センター助教授，大阪大学大学院工学研究科教授を経て，2002 年より同大学院情報科学研究科教授となり，現在に至る．2000 年より大阪大学サイバーメディアセンター長を併
任．データベース，マルチメディアシステムの研究に従事．
現在，ACM Trans. on Internet Technology などの論文誌編集委員．本学会理事，情報処理学会フェロー含め，9 学会の会員．

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