第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

1

ユーザ選好に基づく分散コンテンツキャッシュ
ポリシ
中塚 康介

八槇 博史

構内にキャッシュを設置し，コンテンツのキャッシュ

Abstract.

を行うことによって，ネットワークや web サーバへ

To deliver multimedia contents efficiently, a con-の負荷を減少させるコンテンツデリバリネットワー

tent delivery network (CDN) is used in the Inter-ク (Content Delivery Network; CDN) が利用されてnet. CDN has caches in points-of-presence of in-いる．

ternet service providers and stores multimedia con-

コンテンツデリバリネットワークでは，各キャッtents actively. In CDN, it is important to choose

シュにどのようなコンテンツをキャッシュするかは，contents to cache, because the caching policy is im-

コンテンツ配信者の決定に委ねられている．現在コン

portant to effectiveness.

テンツデリバリネットワークは大規模なコンサートのIn this paper, we formulate the preference of end-

ライブ中継や，社内教育などの一定の利用が見込ま

users and describe the mechanism for helping con-

れるコンテンツに対して適用されており効果を上げ

structing caching policy. Our approach is basedているが，キャッシュコンテンツの選択にユーザの個

on market mechanism where producer agents and別の選好が集約できず，エンドユーザの要求に応じてconsumer agents negotiate and trade resource. We

キャッシュするコンテンツを選択・配信し，コストをbelieve that it not only reaches effective resource al-回収するモデルが求められている．

location but also matches with business model for

本稿では，この問題に対して，エンドユーザの潜在CDN.

的な選好 (preference) のモデルを構築し，収集した

1 はじめにエンドユーザの選好を反映しながらコンテンツ配信

現在，web が普及し，その上でマルチメディアコンに対する無駄のないネットワーク資源の利用，及び，テンツが流通しているが，音声や動画などのマルチネットワーク事業者，コンテンツ配信者，エンドユー

メディアコンテンツは，帯域幅などのネットワーク資ザのコストの配分への応用を考えたキャッシュポリシ源を多く使用し，ネットワークや web サーバに大きを提案する．これにより，効率的なネットワーク資源な負荷をもたらすことが問題となっている．この問題の利用をはかるとともに，コンテンツ配信におけるビの解決のために，インターネットサービスプロバイダジネスモデルへの応用が考えられコンテンツ配信に貢献するものであると考えている．

Kosuke NAKATSUKA, 京都大学 大学院 情報学研究科
社会情報学専攻, Department of Social Informatics,
Kyoto University
Hirofumi YAMAKI, 京都大学 大学院 情報学研究科 社会情報学専攻, Department of Social Informatics, Kyoto
University

本稿で提案するモデルは，これまで研究・開発が行われている分散キャッシュ技術により構築されたコン
テンツデリバリネットワークの中で，ネットワーク事業者，コンテンツ配信者，及び，エンドユーザの各54

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

2

主体のコスト負担，特にエンドユーザに対する課金れるが，実際にはその要求は，経路上に存在するを含めて，キャッシュの置くコンテンツの選択を支援

キャッシュが中間で横取り (intercept) する．要することを目標としており，従来のキャッシュ技術と求を横取りしたキャッシュは，“どこからのアク共に，コンテンツデリバリネットワークの効率的，かセスか”，“何を要求しているか” を調べ，ユーザつ，持続的な運用を図るものである．

から近く負荷の低いサーバへの要求振り分けや，データがキャッシュされている場合は，サーバに2 コンテンツデリバリネットワークかわり，そのデータの送信を行う．

コンテンツデリバリネットワークは，図 1 を一例とクライアントからの要求は経路上で横取りされるため，web ブラウザなどを変更する必要はなする構造を持つ仮想的なネットワークである．

く，透過的に CDN を用いることができる．
従来 CDN に類似する技術としてプロキシ型のキャッシュサーバが用いられてきたが，ユーザからの要求によってキャッシュがはじめて行われ，キャッシュを行うポリシをサービス提供者が設定することができないという問題や，• 要求は多くのコンテンツに対して行われ，一部の人気のあるコンテンツのみをキャッシュするこ
図1

CDN のアーキテクチャとは，ある程度有効ではあるが，十分ではない• web ページのアクセス頻度とページサイズには
図 1 において，サーバはテキスト文書，画像，音弱い相関しかない• web ページのアクセス頻度と更新頻度には弱い

声，動画などのコンテンツが保存されるホストであ相関しかないり，クライアントは，コンテンツを利用するエンドといった問題 [1] から，ポリシ設定が困難であり，まユーザを表している．
従来のクライアント/サーバモデルでは，サーバにた，有効性にも限界がある．これに対して，コンテンクライアントが直接要求を出してデータを入手する

ツデリバリネットワークでは，サーバとクライアントものであり，サーバの負荷が高くなる，また，ネッの間にキャッシュを導入し，このキャッシュにサーバトワークにより大きな帯域幅を要するなどの問題がから特定のコンテンツを前もってコピーしておき，クあった．

ライアントからの要求に備えることで，負荷を分散

これに対して，CDN では，サーバとクライアントし，配信に必要な資源を減少させている．の間にキャッシュを導入することにより，負荷をサーバとキャッシュで分散し，必要な帯域幅を減少させて2.1 CDN の利点いる．CDN は，以下のように動作する．

CDN は，インターネットサービスプロバイダによ

1. インターネットサービスプロバイダの POP†1 にる配信など，コンテンツ配信者が明らかであり，コンキャッシュを設置する．

テンツ利用者が限られている，あるいは，コンテンツ

2. キャッシュは，サーバからデータをコピーし，ク利用が十分に見込まれる場合のように，単一のポリライアントからの要求に備える．どのデータをコシが定義できる場合の負荷分散・高速配信に有効であピーするかは，管理者が設定として与える．

る．このような条件を満たすものとして，各地に支社

3. クライアントからの要求はサーバに対して行わのある企業での企業内教育や，コンサートのライブ配†1 Point-of-Presence，サービスプロバイダへのアクセスポイントを意味する信など，特定のイベントにおけるストリーミング配信などがあり，負荷分散が実現されている．

55

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

2.2 CDN における問題

3

エンドユーザは，図 2 に示すように最寄りのインCDN では，どのコンテンツをどのキャッシュにコターネットサービスプロバイダの POP に設置されたピーするかを決定する必要がある．現在の CDN でキャッシュに対して接続されており，サーバに対するは，キャッシュ技術については， [2] にあげられるよ

要求は，このキャッシュを経由するものとする．

うなキャッシュアルゴリズムが適用され，効果を上げている．一方で，どういったコンテンツをコピーする
かのポリシについては，CDN プロバイダがコンテンツプロバイダと契約し，その契約に基づいてコンテンツを優先的にキャッシュするようになっており，各エンドユーザの要求に応じてコンテンツを配信し，配信についてのコンテンツやネットワークのコストを回収するモデルとはなっていない．このため，• コンテンツプロバイダにとっては，コンテンツ

図2

プロバイダが提供するコンテンツに対し，エンドエンドユーザ・キャッシュ間プロトコルユーザの利用を見通して，CDN を運用する必要
以下，キャッシュコンテンツ決定のプロトコルを記があること，• CDN プロバイダにとっては，ネットワークや計述する．

算機等の性能の向上に対して配信設備を維持し，継続して事業を行う必要があること，

1. エンドユーザはどのコンテンツがどの程度望ましいのかを表す効用情報を効用関数として送信• エンドユーザにとっては，高速なコンテンツ配する．効用関数はコンテンツに対して十分小さ信が望ましい

く，コンテンツ配信そのものに影響を与えないと考えられる．

といった各主体の要求を満たすようなビジネスモデルの構築とそれに対応したキャッシュポリシが必要と

2. キャッシュは，キャッシュの CPU 能力・ストレーなっている．この問題に対し，エンドユーザの選好をジ・ネットワークの帯域幅などの制約条件の中で集約し集められた効用関数を最大化するようなコンテ• エンドユーザ，コンテンツプロバイダ，ネットンツ集合を計算する．

3. キャッシュは得られたコンテンツ集合のコンテワークプロバイダの各主体にとって効率的なコンンツをキャッシュプロトコルに従い取得する．

テンツ選択• 各主体に対するコスト負担の決定

4. エンドユーザはコンテンツに対する要求を行いの 2 点が可能なポリシの構築を目標として，市場機コンテンツを取得する．

構による最適化手法を適用したキャッシュコンテンツ

以上のプロトコルにより，クライアントの効用情報が決定手法を提案する．

収集され，最適なコンテンツ集合が決定される．

3 キャッシュコンテンツ決定プロトコル

4 キャッシュ・エンドユーザ間のキャッシュ決
定アルゴリズム

キャッシュポリシは，エンドユーザとキャッシュ間で効用情報をやりとりするプロトコル，及び，得られ前節のように集められた効用情報は，映画よりも音た効用情報をもとに適切なコンテンツを決定するア

楽が望ましいといったコンテンツ種別毎の選好が記述

ルゴリズムからなる．本章では，キャッシュポリシをされているが，ストレージや帯域幅など資源に制約が運用するためのエンドユーザとキャッシュの間のプロある中で，このような選好を反映した資源割当てが可トコル記述する．

能な手法に経済学の知見を応用した市場機構による

56

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

4

資源割当てがある [3]．市場機構による資源割当ては，

トは，複数あるキャッシュのうちの 1 つであり，このストレージや帯域幅など資源が限られた状況でも，利キャッシュが，エンドユーザの対価を用いてストレー

用者間の要求の衝突を調停しながら利用者の選好に応ジやネットワークなどキャッシュの各資源からコンテじた資源の分配を可能にする最適化手法であり，ネッンツキャッシュサービスを生成する．

トワークの QoS 制御などに適用されている [4]．

以下，エンドユーザを代表する消費者エージェント

コンテンツデリバリネットワークでは，ネットワーと，キャッシュを代表する生産者エージェントの行動

ク事業者，コンテンツ提供者，エンドユーザの各主体について記述する．

が存在し，どの主体がどのように運用コストを負担す

4.2 消費者エージェント

るのかも問題となるが，配信ポリシに価格機構を用いた市場機構による資源割当てを応用することにより，エンドユーザの効用関数の例として，CES 型の効コストの問題を系に含めて最適化問題として記述す用関数をあげる．ユーザ数を n とし，エンドユーザることができ，また，流通するコンテンツの価値を考k (1 ≤ k ≤ n) に対応して消費者エージェント k がエえた応用も可能であると考える．

ンドユーザの効用情報を持つとする．消費者エージェ
ント k の CES 効用関数 uk は以下のように表される．
uk (x1k , · · · , xlk , ek )
ρ−1³P(1)
ρ ´ρρ
l
ρ−1
ρ−1 + aea
x=ekikik
ki=1

以下，市場機構分散資源割当てに基づいて，エンドユーザの効用関数の記述，および，コンテンツ決定アルゴリズムについて記述する．

式 (1) において、xik は，消費者エージェント k に

4.1 市場モデル

割り当てられる資源 i の量，l は資源の種類の数，ek

消費者エージェント・生産者エージェントと消費者

はキャッシュサービス利用のために用いる対価としてエージェントの支払う対価，生産者エージェントの生の初期財を表す．

産するキャッシュサービスの関係を図 3 に示す．

すなわち，ネットワーク上には映画や音楽などの l種のコンテンツがあり，その各コンテンツの中で，エンドユーザが xik だけの個別のコンテンツを要求すると理解できる．aik は資源 i が消費者エージェント kにとってどの程度価値があるのかを示し，ρ はある一つの資源が他の資源をどの程度代替するかを示す．
消費者エージェントは，消費者エージェントが初期に持つ予算を制約条件としてこのような効用関数を図3最大化するように行動する．すなわち，pi を資源 i に付けられた価格†2 とすると，

CDN における市場モデル

max uk (x1k , · · · , xlk , ek )図 3 において，左側の円は消費者エージェントを示

s.t.

し，右側の円は生産者エージェントを示す．また，図

lX

(2)

pi xik ≤ ek

i=1

中の長方形は各エージェント間で流通する財を表す．の最大化問題の解としてエンドユーザの選好を得ることができる．

流通するコンテンツは，直接提供されるのではな

式 (2) のためのエンドユーザの効用情報の取得は，く，ネットワークやストレージなどを含めて，コンテキャッシュコンテンツ決定のプロセスを行う前に，ブンツキャッシュサービスとしてエンドユーザに提供さラウザやマルチメディアプレイヤ上のカテゴリ選択なれる．消費者エージェントは，対応するエンドユーどで行うことが可能であると考えている．

ザの選好情報をエンドユーザから取得し，キャッシュ†2 提供されるキャッシュサービスの価格にあたるサービスに対する需要を決定する．生産者エージェン

57

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

5

4.3 生産者エージェント

することにより，利益が得られることを示しており，エンドユーザの選好を効用関数で表わし，前述のプ

この式が満たされない場合，キャッシュサービスのみロトコルによってキャッシュに集められると，キャッを独立して運用することは，損失が生じることから不シュはこれらの効用関数の総和として表記されるよう可能であると言える．
また，ストレージやネットワーク等のリソースにおな社会的効用を最大化する．
キャッシュを代表する生産者エージェントは，生産関いて大容量なものを用意することが困難であるなど数であらわされる技術内でキャッシュの資源からコンの収穫逓減の性質を示すのに対し，コンテンツは従量テンツキャッシュを生産する．各コンテンツ i に対して課金あるいは固定の料金体系となりうるため，生産関

Pnは，Pnk=1

xik だけの需要があり，Pk=1lpi xik だけのPn数が不連続，あるいは，収穫不変となりうる．

xik

図 4 に，x，y 軸をキャッシュサービスを生産するを用いて，キャッシュコンテンツとストレージを購入ために必要なストレージなどのリソース，及び，コンし，キャッシュサービスを構築する．キャッシュサー

テンツをとり，z 軸に生産されるキャッシュサービス

ビスは，各コンテンツ種別 i 毎にをとり，このような狭義凸関数とならない生産関数を財が割当てられる．キャッシュは，

i=1

Pn

k=1

pi

k=1

xik だけの需例示する．

要がなされ，この範囲内で，個別のコンテンツを購入

図 4(a) は，コンテンツの費用が定数で，一定額支し，キャッシュに置く．
各コンテンツ i に対するキャッシュj の行動は，コ払えば制限なくコンテンツを利用できる場合であり，ンテンツ価格を pci ，ストレージ価格を ps ，コンテン

図 4(b) は，コンテンツの費用は従量制で，利用するツの購入量，ストレージの購入量，そこから生産されコンテンツ量に対して線型にコストが増加する場合

るキャッシュサービスをそれぞれ，cij ，sij ，yij としを示している．このようなコンテンツに特有の性質にて，式 (3) の最大化問題の解として与えられる．

より，式 (4) より得られる均衡解は，大域的な最適解

maxlX
i=1

ではなく局所的な最適解に留まる，あるいは，利潤に(pi yij − (pci cij + ps sij ))上限がなくなり式 (3) を満たす解が存在しない可能性(3)がある．

yij = fj (cij , sij )以上のように，生産者エージェントは，ここで，f (cij , sij ) は，コンテンツとそれを提供す

1. キャッシュサービスを提供して正の利潤を得るるためのストレージ等の資源からキャッシュサービスための条件を生産する生産関数となっている．
∗∗
式 (3) の均衡解を yijとする．yijを与える 2 財 cij ，sij の組みを (c∗ij , s∗ij ) で表わすと，c∗ij ，s∗ij は，式 4) s∂p=f (c∗ij , s∗ij )4.4 価格調整機構

pi∂sij(4)pc∂ i =f (c∗ij , s∗ij )pi∂cij
式 (4) を満たす解 (c∗ij , s∗ij ) が得られても，キャッ各生産者エージェント・消費者エージェントは対応する財について最大化問題を解き，その解を競売人エージェントに入札する．競売人エージェントは，生シュは必ずしもサービスを提供するとは限らない．価産者エージェントと同じくキャッシュシステム内のソ格の調整が終了し，最終的な均衡 (c∗ij , s∗ij ) が得られフトウェアエージェントであり，各資源・コンテンツた時，式 (5) を満たしている必要がある．

i=1(pci cij + ps sij ) ≤lX
i=1

pinXを考えて実装する必要があり，今後この条件を明らかにしていく予定である．

を満たす．

lX

2. 最適なコンテンツ集合が得られるための条件の需給がつりあうように価格を調整する．

Pn

競売人エージェントは，

xik

(5)

k=1

xik と，あるキャッシュj での yij が表明された場合に，関数 θi を単調増

k=1加な関数として，新しい価格を式 (6) に従い変更し，

式 (5) は，キャッシュがキャッシュサービスを提供

58

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

service6serviceserviceservice

10108866442

20010

108086123445storage

60content

612278934storage

10 0(a) コンテンツ費用定数

衡解 p∗

Pnx−y67content

28910 0(b) コンテンツ費用線型

図4

キャッシュj において45収穫逓減でない生産関数= 0 となる均の無い割り当てがなされていることを表している．

ij
k=1 ik∗∗= (p1 , · · · , pl ) を探す．この時の yij が，コンテンツ種別 i に対するキャッシュサービスの最適供

5 おわりに給量となる．

本稿では，コンテンツデリバリネットワークにおけXdpi= θi (∀i,xik − yij )dt

るコンテンツのキャッシュポリシについて記述した．

n(6)マルチメディアコンテンツが容易に作成され公開さk=1れるようになり，サーバの負荷，また，ネットワーク競売人エージェントは決定された新しい価格を各消費者エージェント・生産者エージェントに通知する．

トラフィックが増大している現在，コンテンツデリバリネットワークはこの問題に対して有効な解決策と言える．より多くのコンテンツに対してコンテンツデ4.5 計算手順

リバリネットワークを適用しエンドユーザにより速消費者エージェント・生産者エージェントはその時いサービスを提供するためには，どのコンテンツを点の価格における最大化問題の解を計算し，競売人キャッシュするのかの指針を定めることが必要となるエージェントにその解を伝える．競売人エージェントと考えられる．

は，キャッシュサービスの最適供給量を得られる均衡

本稿で取り上げた手法により，ユーザの要求に適応価格を計算し，消費者エージェント・生産者エージェし，経済機構を背景としたコストモデルを持つキャッントに伝える．この過程を収束するまで繰り返し，得シュの指針が与えられ，コンテンツデリバリネットられたキャッシュ集合に対応するように各コンテンツをキャッシュする．図 5 にこのアルゴリズムを示す．

ワークに貢献するものであると考えている．今後，

1. 式 (3) において，収穫逓減でない性質の市場に市場が適切な性質を持つ場合，上述のプロセスは収束し，需要・供給量は均衡することが知られている．

おける最適性の検討

2. 本稿のモデルに対応したシミュレーションによまた，均衡点での需要・供給量は実際に割り当てが可る評価能である，すなわち，実行可能な解であり，パレート

3. ネットワーク事業者，コンテンツ配信者，及び，最適性を示すことが知られている．

エンドユーザの各主体へのコスト負担を含めて，パレート最適性は，あるエージェントがそれより有ビジネスモデルを考慮したモデルへの改善

利な資源配分を得る時は，必ず他のエージェントが不の 3 点を行い，モデルの有効性を確認していく予定

利になる性質であり，パレート最適な割り当ては無駄である．

59

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

7¶³begin Auctioneer Agent
begin loop
for each Producer Agent, Consumer Agent
send Price Vector
end of forfor each Producer Agent
receive Production matrix
end of forfor each Consumer Agent
receive Demand matrix
end of forif balance ( Production matrix, Demand matrix) exit
Price Vector = θ( Price Vector, Demand matrix, Production matrix)
end of loop
end of Auctioneer Agent

begin Producer Agent
begin loop
receive Price Vector from Auctioneer Agent
Production matrix = Calculate production ( Price Vector )send Production matrix to Auctioneer Agentend of loop
end of Producer Agent

begin Consumer Agent
begin loop
receive Price Vector from Auctioneer Agent
Demand matrix = Calculate demand ( Price Vector )send Demand matrix to Auctioneer Agentend of loop
end of Consumer Agentµ´
図5

各エージェントのアルゴリズム

謝辞
本研究の機会を与えて下さり，また，的確な御指導を賜わりました京都大学大学院情報学研究科社会情報学専攻の 石田 亨 教授，NEC USA の 原 良憲 様，
京都大学大学院情報学研究科社会情報学専攻の亀田 弘行 教授に深く感謝申し上げます．

参考文献[1] Breslau, L., Cao, P., Fan, L., Phillips, G., andShenker, S.: Web Caching and Zipf-like Distribu-60

tions: Evidence and Implications, 1998.
[2] Karger, D. R., Lehman, E., Leighton, F. T., Panigrahy, R., Levine, M. S., and Lewin, D.: ConsistentHashing and Random Trees: Distributed Caching
Protocols for Relieving Hot Spots on the World
Wide Web, ACM Symposium on Theory of Computing, 1997, pp. 654–663.
[3] Wellman, M.: A Market-Oriented Programming
Environment and its Application to Distributed
Multicommodity Flow Problems, Journal of Artificial Intelligence Research, Vol. 1(1993), pp. 1–23.
[4] Yamaki, H., Wellman, M. P., and Ishida, T.:
A market-based approach to allocating QoS for
multimedia applications, Proceedings of the FirstInternational Conference on Multi–Agent Systems(Lesser, V.(ed.)), MIT Press, 1995.