DEIM Forum 2017 E1-2

クラウド上での CDN 事業展開における仮想サーバのスケーラビリティを活用した配信サーバ群選択
長尾

翼†

春本

†
要 ††

†
滝根 哲哉 ††††,††,††† 大阪大学大学院工学研究科 〒 565–0871 大阪府吹田市山田丘 2–1
E-mail: †t-nagao@post.comm.eng.osaka-u.ac.jp, ††harumoto@eng.osaka-u.ac.jp,†††takine@comm.eng.osaka-u.ac.jp
あらましクラウドプロバイダが提供しているコンピュータ資源を利用して CDN 事業を展開する際，配信するコン

テンツに対する遅延時間や転送速度等の QoS 要求を考慮しつつ，利用コストを低減できるような配信サーバ群の選択が重要である．クラウドプロバイダは多様なスケールの仮想サーバをコンピュータ資源として提供しており，配信サーバ群の選択においてこれを活用するためには，配信サーバの位置だけでなくコンテンツ配信にかかる負荷に適したスケールの仮想サーバを適切に選択しなければならない．しかし，既存の配信サーバ群選択手法では，配信サーバの位置しか考慮されていなかった．本稿では，配信サーバの位置に加え，仮想サーバのスケーラビリティを活用した配信サーバ群選択手法を提案する．また，実際のクラウドプロバイダに近いコスト設定を用いた数値実験を行い，提案手法の有効性を評価する．
キーワード

クラウド，CDN，配信サーバ群選択

1. は じ め に事業を展開することが可能である．

CDN において配信されるコンテンツには，遅延時間や転送

近年，スマートフォンやタブレットといった個人用情報端末

速度といった，コンテンツに対する QoS 要求が存在する．この普及に伴い，Web ページや動画などのコンテンツに対するアれを考慮せずに配信サーバ群を配置すると，ユーザはサービス

クセスが増加していることから，インターネット上でのコンテに不満を覚えて利用しなくなり，事業収入の減少につながる．

ンツ配信サービスが注目されている．従来より，安定したコン

そのため，配信するコンテンツに対する QoS 要求を満たした

テンツ配信のために，CDN (Content Delivery Network) が広配信が可能となるように配信サーバ群を配置することが必要でく用いられてきた．CDN では，地理的に分散させた配信サーある．また，多数の配信サーバを配置するとコンテンツ配信に

バに，配信したいコンテンツの複製を配置する．これによって，かかるコストが上昇し，事業支出が増加する．したがって，ク

コンテンツを要求するユーザは，自身の近くの配信サーバからラウド上での CDN 事業展開によって利益を生み出すためには，

コンテンツの配信を受けることができ，配信の際の遅延時間を配信するコンテンツに対する QoS 要求を満たした上で，コン抑えることが可能となる．また，コンテンツへのアクセスが各テンツ配信にかかるコストを可能な限り抑えた配信サーバ群の配信サーバに分散されることから，配信サーバやネットワーク

選択が非常に重要である．

の負荷も抑制される．

この問題に対して，文献 [1] では，コンテンツに対する QoS

一方で，クラウドコンピューティングと呼ばれる，新たなコ要求として，配信の際の遅延時間を考慮した手法を提案していンピュータ資源の利用形態が普及してきている．これは，自身る．しかし，CDN で配信されるコンテンツは様々であり，コンでコンピュータ資源を導入し運用するのではなく，クラウドプ

テンツの種類によって QoS 要求が異なる場合も存在する．まロバイダによって世界各地に設置されたデータセンタで提供さた，クラウド上で提供される仮想サーバのコスト設定には，仮れるコンピュータ資源を利用することで，情報システムの構築

想サーバを使用する際の定額コストが存在するが，文献 [1] にや運用にかかるコストが抑えられるという利点をもつ．クラおけるコスト設定ではそれが考慮されていない．それに対し，

ウドコンピューティングでは仮想サーバ，ストレージ，ネット

文献 [5] では，仮想サーバの使用コストが存在するときには，異ワーク等のコンピュータ資源の実際の使用量に応じた従量制課

なる QoS 要求を考慮して配信サーバ群の選択を行うことで，配金が採用されているため，適切なスケールのコンピュータ資源

信の際のコストを抑えることができる場合が存在することが示を選択することによって利用コストを最適化することが可能でされている．

ある．

しかしながら，現実的に考えると，文献 [5] にはいくつか不このクラウドコンピューティングを用いた，CDN 事業の展開十分な点が存在する．まず，配信サーバの位置のみを考慮してが注目されている [1] [2] [3] [4]．クラウドプロバイダが世界各地おり，その位置に存在するデータセンタ内のどのスケールの仮に設置したデータセンタから適切な仮想サーバを選択して配信

想サーバを使用するかということは考慮されていない．本稿でサーバとして利用することで，設備投資を行うことなく CDN

は，ユーザからのリクエストサイズやコンテンツに対する QoS

要求に応じてデータセンタ内の仮想サーバのスケールを選択可
能な配信サーバ群選択手法を提案する．
また，文献 [5] では遅延時間に関する QoS 要求について，各˸ƪˈʼ˼ˊ̅ˇƪˢ

ユーザへのコンテンツ配信が設定した遅延時間を満たしているかいないかの 2 状態で考えている．しかし実際には，サービスに対するユーザの不満は，配信の際の遅延時間が長ければ長いˇƪˢ‫ڿ‬ൊ

ほど大きくなると考えられる．さらに，どのような状況においても QoS 要求を満たさないコンテンツ配信が最小になるように配信サーバ群を選択するため，少数のアクセスしか処理しな
い配信サーバが選択されてしまい，配信コストが上昇してしまうという問題がある．そこで提案手法においては，QoS 要求をどの程度満たしているかを示す指標として QoS 違反度を新たに定義し，QoS 違反をある程度許容した配信サーバ群選択が行
図 1 既存手法における想定環境

えるようにする．
また，提案手法の評価に際しては，現実のクラウドプロバイ
ダのコスト設定をモデルとした数値実験を行い，クラウド上でˁʴ˕˩˿ƪ˛˅ˋ˚の CDN 事業展開における提案手法の有効性を示す．

ʵ

˕

˧

˚

本稿の構成は以下の通りである．まず，2 章で既存手法におຌける想定環境と定式化について紹介する．次に，3 章で既存手˻௬

法の問題点を考慮した手法を提案する．さらに，4 章で数値実験により提案手法の有効性の検証を行う．最後に，5 章で本研究のまとめと今後の課題について述べる．

ެ๑˅ˋ˚ˋ˚˾ƪˊ˅ˋ˚

2. 既 存 手 法ˁ

文献 [5] では，クラウド上の仮想サーバの利用を想定した環

ʵ

ˋ˚˾ƪˊ

˻

境において，配信するコンテンツに対する QoS 要求として遅延時間に関する QoS 要求と転送速度に関する QoS 要求という

˕

˧

ࡰ

ຌ

˚

˒ʸ̅˿ƪ˛˅ˋ˚

2 種類の QoS 要求を考慮した配信サーバ群選択手法を，0-1 整
数計画問題として定式化している．本章ではその想定環境と定

図 2 サーバ候補の利用コスト

式化の方法について述べる．

2. 1 想 定 環 境

納されたコンテンツのストレージ量に応じた従量コスト，サー

図 1 に文献 [5] における想定環境を示す．想定領域内に，配信

バに流入するトラフィック量に応じた従量コスト，サーバからするコンテンツを格納するオリジンサーバ，地理的に分散して流出するトラフィック量に応じた従量コストが存在する．これ存在するサーバ候補，コンテンツをリクエストする多数のユーらをそれぞれ使用コスト，ストレージコスト，アップロードコ

ザが存在する．これらのサーバ候補の中から，各コンテンツにスト，ダウンロードコストと呼び，これら 4 つのコストを総称

対する QoS 要求を考慮した上で，配信に必要なコストが最小して利用コストと呼ぶ．

となるように配信に用いるサーバを選択することを考える．コ2. 2 定 式 化

ンテンツに対する QoS 要求として，遅延時間に関する QoS 要

オ リ ジ ン サ ー バ を C0 ，サ ー バ 候 補 の 集 合 を C求と，転送速度に関する QoS 要求という 2 種類の QoS 要求を{C1 , C2 , . . . , Cn }，ユーザの集合を U = {U1 , U2 , . . . , Um } と考慮する．遅延時間に関する QoS 要求とは，ユーザからのリし，サーバ候補を文字 λ, µ，ユーザを文字 ρ を用いて表す．オ

クエストを受信してからその応答がユーザに到着するまでの遅リジンサーバ，サーバ候補とユーザをまとめてノードと呼び，延時間が定められた時間以内であることを要求するものである．

文字 α, β, γ を用いて表す．配信するコンテンツは QoS 要求=

一方，転送速度に関する QoS 要求とは，ユーザへのコンテンによって l 種類に分類され，このうち k 種類のコンテンツがツ配信を定められた速度以上で転送することを要求するもので転送速度に関する QoS 要求をもつ．k 種類のコンテンツの中ある．どちらの QoS 要求についても配信するコンテンツの種には，遅延時間に関する QoS 要求と転送速度に関する QoS

類によって要求する QoS レベルが異なる場合がある．また，一要求の両方をもつものも含まれている．l 種類の QoS 要求の方の QoS 要求だけをもつものと，両方の QoS 要求をもつもの

集合を Q = {Q1 , Q2 , . . . , Ql }，k 種類の QoS 要求の集合をがある．

′
Q′ = {Q1 , Q2 , . . . , Qk } とする．すなわち，k <= l，Q ⊂
=Q であ各サーバ候補には利用する際に必要なコストが設定されている．図 2 に示すように，サーバの使用に必要な定額コスト，格り，QoS 要求を文字 ω を用いて表す．以上の記号の定義と文字表1

定式化における記号の定義と文字の意味

記号

定義

文字

意味

C0

オリジンサーバ

λ, µ

サーバ候補
ユーザ

C

サーバ候補の集合

ρU

ユーザの集合α, β, γ

ノード

Q, Q′

QoS 要求の集合

ω

QoS 要求の意味は以降で何度も使用するため，これらを表 1 に示す．
次に，遅延時間に関する QoS 要求について考える．サーバ
候補 λ からユーザ ρ へコンテンツを配信する際の遅延時間は，その距離 Lλρ に比例すると仮定する．QoS 要求 ω ∈ Q によって定められる遅延時間 Tω に対応する距離を Bω としたとき，

Lλρ <= Bω となるようなサーバ候補 λ とユーザ ρ の組 (λ, ρ) は

図3

エッジであるといい，エッジの集合を Eω と定義する．QoS 要
求 ω が転送速度のみを要求している場合においても，Tω を十分に大きな値とすることで，QoS 要求 ω におけるエッジの集ち，xρω
αβ は以下で定義される．

合 Eω を考えることができる．また，他のサーバ候補を経由す
ることなく，直接コンテンツを配信可能なサーバ候補 λ とサーρω

記号 xαβ の例

xρω
αβ =

バ候補 µ の組 (λ, µ) について，すべての QoS 要求 ω における


 1,

ユーザ ρ への配信で (α, β) を使用する

 0,

ユーザ ρ への配信で (α, β) を使用しない

エッジであると定義する．Eω に含まれるエッジのみを使用す

図 3 に xρωαβ の例を示す．オリジンサーバ C0 からユーザ U1 へ，る配信の遅延時間は，QoS 要求 ω によって定められる遅延時

QoS 要求 Q1 をもつコンテンツの配信を行うことを考える．U1間以下となることが保証される．

の近くに存在する C1 と C2 の二つのサーバ候補のうち，配信

また，転送速度に関する QoS 要求について考える．サーバ

サーバとして C1 が選択されたと仮定する．このとき，エッ候補 λ からユーザ ρ へコンテンツを配信する際の転送速度は，

U1 Q1
= 1，
ジ (C0 , C1 ) とエッジ (C1 , U1 ) は使用されるため，xC
1 C2

サーバの負荷 Oλ に反比例するとし，サーバの負荷 Oλ はその

1 Q1xU
C2 U1 = 1 となるが，エッジ (C1 , C2 ) とエッジ (C2 , U1 ) は使

サーバに対するユーザからのリクエストサイズの総和で表され

U1 Q1
U1 Q1
= 0 となる．
= 0，xC用されないため，xC
2 U1
1 C2

′

ると仮定する．転送速度に関する QoS 要求 ω ∈ Q によって次に，この xρω
αβ に対して，すべてのエッジ (α, β) について

サーバ候補 λ において定められる転送速度に対応する負荷をGωλ としたとき，配信サーバとして利用するすべてのサーバ候ω
補 λ について Oλ <= Gλ となるような配信における転送速度は，転送速度に関する QoS 要求 ω によって定められる転送速度以上となることが保証される．
さらに，サーバ候補 λ における使用コストを Rλ ，ストレー
ジコストを Sλ ，アップロードコストを Pλ ，ダウンロードコス
トを Dλ とする．また，オリジンサーバ上でのコンテンツの更新を反映させるために，オリジンサーバがコンテンツの再配信を行う頻度を F とする．QoS 要求 ω をもつコンテンツについて，その配信サイズを Wω ，ユーザ ρ からのリクエストサイズを wρω とする．このとき，ノード α からノード β に QoS 要求ωω をもつコンテンツを配信する際にかかるコスト Vαβ
は，ノー

< ω
xρω
αβ = yαβ ,ωωを満たす二値変数 yαβを定義する．定義から，yαβ
は以下の意

味をもつ．

 1,
ω
yαβ
=
 0,

ある．これを用いて，サーバ候補 λ の負荷 Oλ を，サーバ候補

λ に対するユーザからのリクエストサイズの総和として，以下の式 (1) で表すことができる．

Oλ =

∑

∑

ω
yλρ
wρω

(1)

ω∈Q′ (λ,ρ)∈Eω (Sβ + Pβ F + Dα F )Wω ,β∈C

 wω D ,β∈Uα

どのユーザへの配信でも (α, β) を使用しない

エッジ (α, β) を使用するユーザが存在するか否かを表す変数で

ω
る．Vαβの定義を以下に示す．

β

任意のユーザへの配信で (α, β) を使用する

ω
すなわち，yαβは QoS 要求 ω をもつコンテンツの配信の際に，ド β がサーバ候補であるかユーザであるかによって定義が異な

ω
Vαβ
=

∀ρ ∈ Uさらに，定式化を行うために必要となる変数を定義する．文献 [5] では，0-1 整数計画問題として定式化を行っているため，すべての変数が 0 か 1 の二値をとる．まず，オリジンサーバか

さらに，QoS 要求 ω をもつコンテンツの配信について，サーバ候補 λ の使用に関する二値変数 zλω を以下で定義する．

zλω =


 1,

ω をもつコンテンツの配信で λ を使用する

 0,

ω をもつコンテンツの配信で λ を使用しない

このとき，すべてのサーバ候補 λ について

らユーザ ρ へ QoS 要求 ω をもつコンテンツを配信する際に，エッジ (α, β) を使用するか否かを二値変数 xρωαβ で表す．すなわ

ω < ω
yλα
= zλ ,∀(λ, α) ∈ Eω

が成立する．前述の通り，転送速度に関する QoS 要求を満たした配信を行うためには，配信サーバとして利用するすべてのω
サーバ候補 λ について Oλ <= Gλ が成り立っていればよい．こ˸ƪˈʼ˼ˊ̅ˇƪˢのことは，zλω を用いることで，以下の制約条件式として表現可能である．
ωzλω Oλ <= Gλ ,∀ω ∈ Q′˙ƪˑˍ̅ˑ

また，zλω に対し，すべてのサーバ候補 λ についてzλω <= zλ ,∀ω ∈ Qを満たす二値変数 zλ を定義する．定義から，zλ は以下の意味
をもつ．

zλ =


 1,

任意のコンテンツの配信で λ を使用する

 0,

どのコンテンツの配信でも λ を使用しない

図 4 提案手法における想定環境

うことは，クラウド上で CDN 事業を展開する際には非常に重これを用いて，配信の際に必要なコスト DC （Delivery Cost）

要である．したがって，本稿では想定領域内に多数存在するのを以下の式 (2) で表すことができる．

はサーバ候補ではなくデータセンタであり，そのデータセンタ

DC =

∑

∑

ω
ω
yαβ
Vαβ
+

ω∈Q (α,β)∈Eω

∑

zλ Rλ

(2)

文献 [5] における配信サーバ群選択手法は，配信の際に必要なコストを最小化するために，DC を目的関数として以下のよ
うに定式化される．

P1 : minimize
subject to内からスケールの異なる仮想サーバを配信サーバとして選択可能であるとする．本稿における想定環境を図 4 に示す．

λ∈Cスケールの異なる仮想サーバの選択を可能にするために，文献 [5] の定式化における記号と変数の定義を変更する．集合

C = {C1 , C2 , . . . , Cn } をサーバ候補ではなくデータセンタの集合とする．データセンタ λ 内では様々なスケールの仮想サーバ

DCが提供されているが，ストレージコスト Sλ ，アップロードコ∀ρ ∈ U , ∀ω ∈ Q,

スト Pλ ，ダウンロードコスト Dλ はデータセンタごとに定義



1,

∑ ρω
∑ ρω xαβ −xγα = −1,(α,β)∈Eω(γ,α)∈Eω0,

α = C0

される．使用コスト Rλ については，仮想サーバごとに異なる

α∈Uため，データセンタ λ 内で最小スケールの仮想サーバの使用コ

α∈C

ストを表すとする．
この最小スケールの仮想サーバをスケール 1 の仮想サーバと< ωxρω∀(α, β) ∈ Eωαβ = yαβ ,ω < ω
yλα = zλ , ∀(λ, α) ∈ Eω呼ぶ．データセンタ λ 内で提供されているすべての仮想サーバzλω <= zλ , ∀λ ∈ Cωω′zλ Oλ <= Gλ , ∀λ ∈ C, ∀ω ∈ Q

し，n 倍のスケールの仮想サーバをスケール n の仮想サーバとは，このスケール 1 の仮想サーバの整数倍のスケールであると呼ぶ．スケール n の仮想サーバは，スケール 1 の仮想サーバの

ただし，Oλ ，DC の定義はそれぞれ式 (1)，式 (2) で与えられn 倍の使用コストを必要とするが，スケール 1 の仮想サーバのる．なお，最後の制約条件式は線形化が可能である [5]．

n 倍の負荷を処理可能であるとする．この仮想サーバのスケー

3. 提 案 手 法

ルの倍率を，本稿の定式化では変数 zλ で表すことにする．すなわち zλ = 1 のときには，データセンタ λ において配信サー

文献 [5] の想定環境と定式化には，不十分であると考えられバとして選択された仮想サーバはスケール 1 の仮想サーバである点が存在する．まず，文献 [5] では，想定領域内に分散して存り，zλ = 3 のときには，スケール 3 の仮想サーバが選択され在するのはサーバ候補であり，データセンタではない．各サーたことを意味する．したがって，文献 [5] では zλ は二値変数でバ候補が存在する位置には，それぞれ 1 台のサーバ候補のみあったが，本稿では非負の整数値をとる変数とする．なお，二が存在するものと仮定しており，同じ位置に複数のサーバ候補

値変数 zλω は提案手法では用いない．

が存在することを想定していない．しかし，現実のクラウドプ

データセンタ内で提供される仮想サーバにおける，転送速度

ロバイダは，世界各地にデータセンタを分散して設置し，そのに関する QoS 要求について考える．文献 [5] と同じく，サーバ

データセンタ内では様々なスケールの複数の仮想サーバが提供

候補 λ からコンテンツを配信する際の転送速度は，サーバ候補される．大きいスケールの仮想サーバは，利用するためによりλ の負荷に反比例すると仮定する．データセンタ λ 内のスケー

多くの使用コストを必要とするが，配信サーバとして利用する

ル 1 の仮想サーバは，その負荷が Hλ 以下であるとき，転送速際にはより大きな負荷に対応することができる．このような仮度に関する QoS 要求を満たした配信が可能であるとする．す想サーバのスケーラビリティを考慮した配信サーバ群選択を行

るエッジ (α, β) は，直接コンテンツを配信可能なサーバ候補

4R6 ν౩୩

の組か，時間 Tω 以内に配信可能なサーバ候補とユーザの組であったが，後者の定義を前者にそろえ，直接コンテンツを配信可能なノードの組とする．すなわち，ノード α からノード β
へ，QoS 要求 ω をもつコンテンツを配信時間に関わらず直接配信可能であるとき，(α, β) はエッジとなる．
また，文献 [5] では，コンテンツに対する QoS 要求を満たすことが可能なサーバが存在する場合には，必ずそのサーバを選択している．しかしながら，これでは少数のユーザにしか配信ధऊߢԨ

を行わないようなサーバ候補も，配信サーバとして選択されてしまう．現実的には，少数のユーザからのリクエストに対応す

図5

配信時間に対する QoS 違反度の定義

るためだけに，新たな配信サーバを立ち上げて多大なコストをかけるとは考えにくい．したがって，ある程度の QoS 違反

なわち，スケール倍率 zλ の仮想サーバでは，転送速度に関すを許容することによって配信サーバ群の数を低減させることがる QoS 要求を満たした配信が可能な負荷の上限値は zλ Hλ でできるような制約条件を考える．QoS 違反度の合計値を QVD

ある．

（QoS Violation Degree）とすると以上の変更点を考慮し，P1 から以下の制約条件を取り除く．

∀λ ∈ C, ∀ω ∈ Q′Oλ <= zλ Hλ ,

ω
Qω
yλρ
λρ

(3)

とすると，定式化に制約条件

QVD <= QVDLimit

そして，以下の制約条件を追加する．
ω <yλα= zλ ,∑と表すことができる．許容可能な QVD の上限値を QVDLimit∀λ ∈ Cωzλω Oλ <= Gλ ,∑

ω∈Q (λ,ρ)∈Eω

∀(λ, α) ∈ Eω

ω < ω
yλα
= zλ ,zλω <= zλ ,QVD =∀(λ, α) ∈ Eω∀λ ∈ Cを追加することで，QVD が QVDLimit 以下であることが保証される．すべての QoS 要求が満たされた配信を行いたいときには，QVDLimit = 0 とすればよい．また，目的関数を変更しまた，文献 [5] では遅延時間に関する QoS 要求について，配DC + θQVD

信に要した時間がある値以下であればその QoS 要求は満たされ，そうでなければその QoS 要求に違反しているとしており，

QoS 要求を満たしているかいないかの 2 状態で考えていた．しかし実際には，サービスに対するユーザの不満は，配信の際の遅延時間が長ければ長いほど大きくなると考えられる．そこで
本稿では，遅延時間に関する QoS 要求にどの程度違反しているとする．ただし，係数 θ は十分に小さい値とする．これにより，

DC を最適化するような配信サーバ群が選択されると同時に，同じ DC となるような配信サーバ群の候補の中で QVD が最小となるような配信サーバ群を選択することが可能になる．
以上より，提案手法を定式化すると以下のようになる．

かを表現する新たな指標として，QoS 違反度を定義する．これには様々な定義が考えられるが，本稿では図 5 のように，QoS

P2 : minimize

要求 ω ∈ Q によって定められる遅延時間 Tω 以内に配信可能な

subject to

場合には 0 であり，QoS 要求で定められた遅延時間を超過した
場合には超過した分だけ線形に増加するような QoS 違反度の定義を使用する．その他にも，ユーザの効用を考慮した一般の増加関数を用いた定義や，リクエストサイズと超過した時間のじく，配信の際の遅延時間はサーバ候補からユーザまでの距離
補 λ からユーザ ρ までの距離 Lλρ を用いると，サーバ候補 λからユーザ ρ まで QoS 要求 ω をもつコンテンツを配信する際の QoS 違反度 Qωλρ は以下で定義される．

より簡単なものに変更することが可能である．文献 [5] におけ



1,

∑ ρω
∑ ρω xαβ −xγα = −1,(α,β)∈Eω(γ,α)∈Eω0,

α = C0α∈Uα∈C∀(α, β) ∈ Eω∀(λ, α) ∈ EωOλ <= zλ Hλ , ∀λ ∈ C
QVD <= QVDLimitに比例するものとし，時間 Tω に対応する距離 Bω ，サーバ候

この QoS 違反度の定義を導入することで，エッジの定義を∀ρ ∈ U , ∀ω ∈ Q,< ωxρωαβ = yαβ ,ω <yλα = zλ ,積を QoS 違反度とするような定義も考えられる．文献 [5] と同Qωλρ = max(0, Lλρ − Bω )DC + θQVDxρωαβ ∈ {0, 1},∀(α, β) ∈ Eωωyαβ
∈ {0, 1},∀(α, β) ∈ Eωzλ ∈ {0, 1, 2, . . .},∀λ ∈ C

ただし，Oλ ，DC ，QVD はそれぞれ式 (1)，式 (2)，式 (3) で与えられる．

4. 性 能 評 価

表2

各クラウドプロバイダにおけるサーバの利用コストの設定値

Rλ

Pλ

Dλ

Sλ

本章では，後述の評価モデルに従って問題を設定し，前章に

CP1

77.76

0

0.09

0.023

て整数計画問題 P2 として定式化した提案手法を CPLEX [6] をCP2

105.12

0

0.87

0.017

用いて解き，性能評価を行う．

4. 1 評価モデル
本評価では，40 × 40 の正方形の領域を想定し，この領域上に 16 人の仮想ユーザを等間隔に配置する．この仮想ユーザは自身の周囲の 10 × 10 の正方形の領域内のユーザ群を仮想的に集約したものであり，これをコンテンツをリクエストするユー
ザとみなす．個々のユーザではなく集約された仮想ユーザを用いるのは，ユーザ数が多数となると CPLEX による求解が困難になるためである．
この領域に，配信するコンテンツを格納しているオリジン
サーバが 1 台，データセンタが複数存在する．オリジンサーバ
からは任意のデータセンタにコンテンツを配信可能であるが，ユーザへ直接配信を行うことは不可能とする．これは，通常オリジンサーバはクラウドの外に存在するためである．各データセンタからは任意のユーザへとコンテンツを配信可能である．

図 6 ケース 1 におけるデータセンタの配置

仮想サーバを提供するクラウドプロバイダには，CP1 と CP2の 2 社が存在するものとする．これらはそれぞれ Amazon Web

Services [7] と Microsoft Azure [8] をモデルとしており，その仮想サーバの利用コストには，両社の Web サイト上で公開されている仮想サーバの利用コストの表から，同スケール程度とユーザからのリクエストサイズを全て 3,000 GB とした上で，

QVDLimit を 0 から 50 まで 5 刻みに変化させて，次の三種類のケースについて比較した．

思われるものの利用コストを用いた．使用コストについては両

ケース 1 CP1 と CP2 の両方の仮想サーバが提供されるデー

社ともに 1 時間当たりの使用コストであったため，720 倍してタセンタを，図 6 に示す通りに等間隔に 9ヵ所配置

1ヵ月当たりの使用コストとした．その他の 3 つのコストにつしたケース

いては 1 GB 当たりのコストである．このようにして設定した両社の利用コストを表 2 に示す．CP1 の提供する仮想サーバは

ケース 2 CP1 と CP2 の両方の仮想サーバが提供されるデー
タセンタを，想定領域内にランダムに 9ヵ所に配置

使用コストが低くダウンロードコストとストレージコストが高したケース

く設定されており，CP2 の提供する仮想サーバでは使用コストが高くダウンロードコストとストレージコストが低く設定されケース 3 CP1，CP2 のそれぞれの仮想サーバのみが提供されている．

るデータセンタを，想定領域内にランダムに 9ヵ所配信するコンテンツは一種類とし，遅延時間に関する QoSずつ計 18ヵ所に配置したケース

要求と，転送速度に関する QoS 要求の両方を持っているとする．遅延時間に関する QoS 要求については，B1 = 10 と定める．転送速度に関する QoS 要求については，配信を行うデータセンタにおいて，50Mbps の転送速度を必要であるとする．こケース 2 とケース 3 において，データセンタをランダムに配置する際には，同じクラウドプロバイダの仮想サーバが提供されるデータセンタは，少なくとも距離 10 は離して配置した．このとき，各ケースにおいて，CP1 の仮想サーバのみをサーバ候補のとき，H1 はとしたとき，CP2 の仮想サーバのみをサーバ候補としたとき，

H1 = 50 × 106 bps × 60 s × 60 m × 24 h × 30 d × 0.125 B= 16,200 × 10 B = 16,200 GB
9となる．配信するコンテンツのサイズを 100 GB，オリジンサー
バがコンテンツの再配信を行う頻度 F を 1 とする．また，目的関数における係数 θ の値を 10−4 とする．

4. 2 評 価 結 果
前節の評価モデルに従い，性能評価を行った．

4. 2. 1 QVDLimit を変化させた評価
まず，許容可能な QVD の上限 QVDLimit を変化させたと
きの，配信の際に必要なコスト DC について評価を行った．各CP1 と CP2 の両方の仮想サーバをサーバ候補としたときの 3
つの場合における，QVD と DC の値を散布図としてプロットした結果を，それぞれ図 7，図 8，図 9 に示す．なお，ケース

2 とケース 3 においては，ランダムにデータセンタを配置する
ため，同じ評価を 10 回ずつ行い，それら全ての結果を示している．
図 7 から，QoS 違反度の増加を許容するとコストを下げられることが分かる．比較した 3 つの場合のいずれにおいてもコストを下げることができているが，特に CP1 と CP2 の両方の仮想サーバをサーバ候補としたときにはコストが顕著に下がって

5050

4.5

&3ʍʞ
&3ʍʞ
ຜൣਮ‫ݥ‬

5000

4

4950

3.5

4R6ν౩୩

˅ˋ˚

4900
4850
4800
4750
4700

3
2.5
2
1.5

4650

1

4600

0.5

4550

0
0

5

10

15

20

25

30

35

40

45

50

1

2

3

4

4R6ν౩୩

5050

7

8

9 10 11 12 13 14 15 16

図 10 QoS 違反度の分布

&3ʍʞ
&3ʍʞ
ຜൣਮ‫ݥ‬

5000

˅ˋ˚

6

˸ƪˈಀ܎

図 7 ケース 1 における結果

することが不可能な場合も存在する．特にケース 2 では，デー4950

タセンタが 9ヵ所にしか存在しないため，QVDLimit = 0 の4900

ときには解が存在しないことも多く，存在した場合でもケース

4850

1 と比較すると DC は割高なものとなっていることがわかる．

4800

QVDLimit を大きく設定し，QVD が 10 を超えるような配信

4750を許容すると，DC はほぼ一定値をとるようになっている．例

4700
4650

えば 1 ユーザにつき QoS 違反度が 1 増加することを許容する

4600とし，図 8 における QVD = 16 付近の DC を見ると，QoS 違

4550
0

5

10

15

20

25

30

35

40

45

50

反を許容しない場合と比較して 5%以上のコストを削減できる
ことがわかる．

4R6ν౩୩しかし，QVD が 16 程度であっても，それぞれのユーザの

図 8 ケース 2 における結果
5050

QoS 違反度が高々1 程度となっているとは限らない．そこで，
図 8 にプロットされている点のうち，CP1 と CP2 の両方の仮

&3ʍʞ
&3ʍʞ
ຜൣਮ‫ݥ‬

5000

想サーバをサーバ候補としたときにおける，QVDLimit = 204950のときの，ユーザごとの QoS 違反度の分布を図 10 に示す．こ

4900

˅ˋ˚

5

れをみると，1 ユーザ当たりの QoS 違反度の平均は 1 であって

4850
4800

も，実際には半分以上のユーザは QoS 違反度が 0 となる一方，

4750

3 ユーザに QoS 違反度が集中してしまっていることがわかる．

4700

この 3 ユーザに関しては，遅延時間に関する QoS 要求で定め4650られた配信時間の 1.5 倍近い配信時間がかかっており，サービ

4600

スから離脱してしまう可能性がある．それゆえ，DC が最適化

4550
0

5

10

15

20

25

30

35

40

45

50

4R6ν౩୩
図 9 ケース 3 における結果されていても，事業の収入を考えた時に最適な結果になっているとは断言できない．
ケース 3 は，ケース 2 とほぼ同じ結果となっている．しかし，
ケース 2 では CP1 と CP2 のどちらの仮想サーバから配信をいる．これは，CP1 と CP2 の両方の仮想サーバをサーバ候補

受けても QoS 違反度は変わらないため，グラフにおいて CP1としたときには，ユーザからのリクエストサイズの総和が少なのみの場合と CP2 のみの場合の QoS 違反度は同じとなる（〇

いデータセンタでは CP1 の仮想サーバを用い，多いデータセ

印と△印が縦に並ぶ）が，ケース 3 では CP1 と CP2 のデータ

ンタでは CP2 の仮想サーバを用いることができるためである．

センタの配置が異なるため，QoS 違反度は CP1 のみの場合と図 8 においても，ケース 1 の結果と同じ傾向を見ることがCP2 のみの場合で同じにはならない点で，ケース 2 の結果と異できる．ケース 1 では，全ユーザにおいて QoS 要求に違反せなっている．

ずに配信を受けることのできるデータセンタの存在が保証されこれらの図を用いると，あるコストを上限に CDN を運用しており，特に想定領域の中心付近のユーザでは 4ヵ所のデータたいと考えたときに QoS 違反度がどの程度になるのかといっセンタから QoS 要求に違反することなく配信を受けることがたことや，逆にある QoS 違反度以下で CDN を運用するためできる．しかし，データセンタをランダムに配置したケースでにはどの程度のコストが必要になるかといったことがわかり，は，QVDLimit の値が小さいときには制約条件を満たして配信

CDN 事業を展開する上での判断材料とすることが可能である．

5

&3
&3

є৳ˇƪˢॐ
Ƹˋ˃ƪ˽ƹ

є৳ˇƪˢॐ
Ƹˋ˃ƪ˽ƹ

5

4

3

2

1

0

4

3

2

1

0
1000

1500

2000

2500

3000

3500

4000

1000

˼ˁʺˋ˚ˇʶˌ
図 11

&3
&3

選択された仮想サーバ数（QVDLimit=20 のとき）

1500

2000

2500

3000

3500

4000

˼ˁʺˋ˚ˇʶˌ
図 12

選択された仮想サーバ数（QVDLimit=80 のとき）

4. 2. 2 リクエストサイズを変化させた評価存在するデータセンタ内で提供される仮想サーバのスケーラビ

次に，選択された仮想サーバの特徴を示すために，ユーザかリティを活用して，コンテンツ配信に用いるサーバ群を選択す

らのリクエストサイズを変化させたときの，選択された仮想る手法を提案した．また，コンテンツに対する QoS 要求に対サーバ数について前節のケース 1 と同じ状況で評価を行った．

する違反度を定義し，提案した手法を配信コストと QoS 違反

各ユーザからのリクエストサイズを 1,000 GB から 4,000 GB ま

度のトレードオフを考慮できるような整数計画問題として定式

で 500 GB 刻みで変化させた上で，QVDLimit の値を 20 と 80化した．さらに，現実のクラウドプロバイダのコスト設定をモとした場合の，選択された仮想サーバ数をそれぞれ図 11 と図デルとした数値実験を行うことで，多少の QoS 違反度の増加

12 に示す．図 11 と図 12 において，縦軸は選択された仮想サーを許容するだけで 5%程度のコストを削減可能であることを示

バ数をスケールで換算した量であり，複数つながっているもの

した．また，CP1 と CP2 の仮想サーバの料金設定の特徴に基はつながっている分だけのスケールをもつ仮想サーバが選択さ

づき，どのようなときにそれぞれの仮想サーバが選択され，まれたことを示している．例えば，図 12 においてリクエストサ

たどのようなときに仮想サーバのスケーラビリティが活用されイズが 3,000 GB の時には，CP1 のスケール 1 の仮想サーバがるかを示した．今後の課題としては，ユーザのリクエストの時

1 台，CP2 のスケール 1 の仮想サーバが 1 台，CP2 のスケー間変化にも対応可能な手法の提案などがあげられる．

ル 2 の仮想サーバが 1 台選択されたことを意味する．図 11 をみると，リクエストサイズが小さいときには CP1 の仮想サー
バが選択され，リクエストサイズが大きくなるにつれて CP2の仮想サーバが選択されるようになることがわかる．これは，リクエストサイズの増加に伴って，使用コストの低い仮想サー
バを重視した選択から，ダウンロードコストの低い仮想サーバを重視した選択へと変化したことを示している．
また，図 12 をみると，リクエストサイズの増加に伴い，選択された仮想サーバの数が増加していることがわかる．これはスケール 1 の仮想サーバ 1 台につき Hλ までしかリクエストを処理できないことのよるものである．このとき，合計 Hλ を超えるサイズのリクエストを処理する際に，2 カ所のデータセンタでスケール 1 の仮想サーバを 2 台利用するよりも，1 カ所のデータセンタでスケール 2 の仮想サーバを 1 台利用することで，ストレージコストを削減できる．すなわち，スケーラビ
リティを活用した配信サーバ群の選択を行うことができているといえる．ただし，1 カ所のデータセンタからの配信の際には

QVD の増加を避けられないため，QVDLimit を小さく設定した図 11 の状況においては，仮想サーバのスケーラビリティは活用されていない．

5. お わ り に
本稿では，クラウド上での CDN 事業展開において，各地に文

献[1] Chen, F., Guo, K., Lin, J., et al.: Intra-cloud Lightning:
Building CDNs in the Cloud, Proc. IEEE INFOCOM 2012,
pp.433–441.
[2] Wang, M., Jayaraman, P.P., Ranjan, R., et al.: An
Overview of Cloud Based Content Delivery Networks: Research Dimensions and State-of-the-Art, Transactions on
Large-Scale Data- and Knowledge-Centered Systems XX,
pp.131–158 (2015).
[3] Wang, F., Liu, J., and Chen, M.: CALMS: CloudAssisted Live Media Streaming for Globalized Demands
with Time/Region Diversities, Proc. IEEE INFOCOM
2012, pp.199–207.
[4] Salahuddin, A.M., Elbiaze, H., Ajib, W., et al.: Social
Network Analysis Inspired Content Placement with QoS
in Cloud-based Content Delivery Networks, Proc. IEEE
GLOBECOM 2015.
[5] 長尾翼，春本要，滝根哲哉，“クラウド上での CDN 実現における異なる QoS 要求を考慮した資源選択手法,” 情報処理学会マルチメディア，分散，協調とモバイル（DICOMO2016）シンポ
ジウム論文集，5D-4，pp.1016–1023，2016 年 7 月．
[6] IBM: IBM ILOG CPLEX Optimization Studio, IBM(オンライン), 入手先 ⟨http://www-03.ibm.com/software/
products/ja/ibmilogcpleoptistud⟩ (参照 2016-05-11).
[7] Amazon Web Services: 料金 - Amazon EC2 | AWS, Amazon
Web Services (オンライン), 入手先 ⟨https://aws.amazon.
com/jp/ec2/pricing/⟩ (参照 2016-05-11).
[8] Microsoft Azure: 価格の概要 - Azure 価格の仕組み | Microsoft
Azure, Microsoft Azure（オンライン）, 入手先 ⟨https://
azure.microsoft.com/ja-jp/pricing/⟩ (参照 2017-01-01).