情報指向ネットワークにおける ISP ドメイン間キャッシュ共有に関する研究
代表研究者
共同研究者

ショウ シュン 北見工業大学 工学部 特任助教
朝枝 仁
情報通信研究機構 ネットワークシステム研究所 研究マネージャー

1 はじめにインターネット接続サービスを提供する ISP（インターネット・サービス・プロバイダー）は、グローバルバックボーンを提供する tier-1 ISP、地域バックボーンを提供する tier-2 ISP とエンドユーザーにインターネットアクセスサービスを提供する tier-3 ISP に分類されている（図１）。接続している ISP 間には、主にトランジットとピアリングという接続関係がある。トランジット関係においては、下位 ISP がトラヒックをインターネットに届けるために、上位 ISP にトランジット料金を支払うのに対して、ピアリング関係では、ISP 間は対等な位置関係にあり、トラヒックをお互いが所有するネットワークに届けるのに、料金は発生しない。そのため、ISP はピアリング関係にある ISP に優先的にトラヒックを送る傾向がある。
近年、情報指向ネットワーク(ICN)が進んでおり、それに基づいたコンテンツピアリングといった新たな ISP 間の接続関係が注目されつつある[1][2]。図１を用いてコンテンツピアリングの仕組みを説明する。図１の B と C がピアリング ISP 同士であり、それぞれが異なるコンテンツをキャッシュしていたとする。B と C がコンテンツピアリング関係にある場合、それぞれが周期的に自分のネットワークにキャッシュするコンテンツ情報を広告し、お互いが自分のキャッシュにアクセスできるようにする。コンテンツピアリングはピアリング ISP 同士間でしか確立できないため、キャッシュの導入によるメリットが充分に発揮できないという問題がある。この問題を解決するために、我々はリモートコンテンツピアリングという新たな接続方式の提案を行いたい。リモートコンテンツピアリングとは、共通のトランジットプロバイダーISP を持つ直接には接続していないカスタマーISP 同士がそのトランジットプロバイダー経由でお互いのキャッシュを利活用可能にする方式である。図１の例で説明すると、A が E に B のキャッシュコンテンツへのリクエストを送信する場合、E は H からそのコンテンツを調達するのではなく、代わりにB からそのコンテンツを調達する。現在のインターネット上では、このようなコンテンツの調達方法は実現できない。その原因は B の利益損失にある。つまり、B は自分のキャッシュコンテンツを A に提供するに当たり、E にトランジット料金を支払っているにもかかわらず、A からの対価をもらえないため、損失を受けることになる。リモートピアリングを可能にするためには、E は B に対して一定のインセンティブを与えなければならない。しかし、現在のインターネットの構造上、それは簡単には実現できない。図１で、C が A と Bの両者がキャッシュするコンテンツを E にリクエストする場合を考えてみよう。その場合、A と B はコンテンツを E（そして C に）に提供するに当たり、E に対して競合関係にあることから、コンテンツ提供の価格を極端に下げているとする。一方、B が C のキャッシュするコンテンツを取得しようとする場合、E と F の間でC のキャッシュへのアクセスに対する競合が起こり、C に支払う対価を極端に上げる恐れがある。そのようなことが起これば、ナッシュ均衡が達成できなくなり、ISP の接続戦略とドメイン間トラヒックエンジニアリングの安定性に大きな影響を及ぼす。
上述の問題を解決するために、本研究では：１）ピアリング関係にない ISP 同士が共通のトランジットプロバイダーISP 経由でお互いのキャッシュの利用を可能にするリモートコンテンツピアリングを提案している。２）リモートコンテンツピアリングを用いた時のマーケットをモデル化することにより、そのマーケットが持つ、複数のトランジット ISP が共通のカスタマーISP に対して持つキャッシュアクセス権利の競合と、共通のトランジットプロバイダーを持つ複数のカスタマーISP がコンテンツ提供に当たり、その共通のトランジットプロバイダーに対する競合が同時に発生し得る、といった両面性(double-sided)の属性を明らかにする。３）本研究では、ナッシュバーギニングを用いて、価格交渉とトラヒックエンジニアリング問題を同時に解決できるメカニズムを提案している。さらに、ISP とコンテンツの数が膨大になっていても拡張性に1問題が起きないように、効率的な分散アルゴリズムを提案している。４）本研究では、厳密な理論分析とシミュレーションにより、研究成果の評価を行っている。

2 システムモデル
本章では、リモートコンテンツピアリングを導入してマーケットの数学モデルを構築する。本研究の対象
は、地域における複数の tier-2 ISP と tier-3 ISP のネットワークである。全ての ISP がキャッシュ設備を導入し、コンテンツをローカルにキャッシュすると想定している。Tier-1 ISP はキャッシュ設備を導入する明確なメリットがないため、本研究の対象外とする。各 ISP はキャッシュ情報をまとめる機能を持っており、異なる ISP 間で周期的にキャッシュ情報の交換を行う。ある tier-3 ISP から特定のコンテンツへのリクエストが来る度に、そのトランジットプロバイダーISP はそのリクエストを自分のピアリング ISP に転送するか、バックボーン ISP に転送するか、あるいは自分の他のカスタマーISP に転送するかを決める。もしそのコンテンツが tier-2 ISP のキャッシュになければ、コンテンツ調達先として、その tier-2 ISP はバックボーン ISP よりも自分のカスタマーISP を好むことにする。本モデルで用いている概念は表 1 のようにまとめられる。
概念TCOWd io
AxijxijoxixDiui ()v j ()bjKtiKcjpijp定義
T={ti}, tier-2 ISP の集合、|T|=N
C={cj},tier-3 ISP の集合、|C|=M
コンテンツ全体の集合

W  (wij )N M、wij = 1 は ti と cj が接続することを意味している
ti の o に対する集約的デマンドインテンシティ

A  (a jo )M O、aij = 1 は o が cj のキャッシュにあることを意味している
ci が tj に振当てるキャッシュのアップロード帯域
ti が o を獲得するために利用する cj のキャッシュアップロード帯域
xi = (xi1, xi2, … , xiM)
x = (x11, … , x1M, x21, … , xNM)
o に対する dio による xi の値域
ti が全てのカスタマーISP からもらったキャッシュアップロード帯域全体に対する評価
cj がトランジットプロバイダーにキャッシュを提供することによる運営コスト
cj のキャッシュのアップロード帯域の上限
ti のバーギニングパワー
cj のバーギニングパワー
ti が cj のキャッシュを利用することに対して cj に支払う対価
p = (p11, … , p1M, p21, … , pNM)
表１：主要な概念の定義

ti と cj は tier-2 トランジットプロバイダーISP と tier-3 カスタマーISP を表している。ti はインテンシ
ティ dio でコンテンツ o を自分のカスタマーISP から調達しようとする。そのデマンドは無限に分割できると想定する。W は ISP 間のトポロジーを表すマトリックスであり、wij=1 は、ti が cj のトランジットプロバイダーであることを意味している。ti と cj がリモートコンテンツピアリングを導入する場合、cj はキャッシュのxij   xijo

アップロード帯域の xij を ti に提供し、ti はそれを用いて複数のコンテンツを調達する。よって、oは自明である。ti は関数 ui () であり、カスタマーISP からもらったトータルのキャッシュのアップロード帯域を評価する。 ui () は非負の凹関数であり、増加関数である。 ui () は ti がコンテンツを全てのカスタマー
2

ISP のキャッシュから調達するに当たった利得と認識してよい。pij は ti が cj のキャッシュのアップロード帯域を使うために支払う対価である。よって、ti の利得関数は以下の通りである：

s.t.

一方で、tier-3 ISP cj がキャッシュを tier-2 ISP に提供することにより、運営コストが発生するが、それをv j ()v ()で表す。 jは、非負の凸関数で、連続増加関数である。cj のキャッシュのアップロード帯域には上限があり、それを bj で表す。cj はキャッシュを ti へ提供することにより、pij の収入をもらえる。よって、cjの利得関数は以下の通りである：

注意したいのは、本研究では、xij を xijo により間接的に制約をかけることである：

A=(ajo)はキャッシュコンテンツの分布情報を表すマトリックスであり、ajo=1 はコンテンツ o が cj のキャッシュにあることを意味している。

3 ナッシュバーギニングを用いた効率的なリモートコンテンツピアリング
リモートコンテンツピアリングの導入により、両面性のあるマーケットにおけるトラヒックエンジニアリングと価格交渉問題を同時に解決するために、本研究ではナッシュバーギニング[3]を用いることで効率的なリソースアロケーション手法を提案している。
3-1 ナッシュバーギニングソリューション
以下の式は各参加者（ISP）の利得関数の重み付き累乗を最大化するナッシュバーギニングの基本公式を表している：

その中で、Kti は ti のバーギニングパワーである。上記の式は以下の式と同等である：

x と p の制約条件を加えると、以下のリモートコンテンツピアリング問題(RCP)にまとめられる：

一つ目の制約条件は x が tier-2 ISP のデマンドと tier-3 ISP のキャッシュアップロード帯域の上限に依存

3

することを表している。二つ目の制約条件は tier-2 ISP にとってカスタマーISP のキャッシュを利用することによる利得が非負であることを意味している。それと同様に、三つ目の制約条件は tier-3 ISP にとってプロバイダーISP にキャッシュを提供することによる利得が非負であることを意味している。
3-2 分散アルゴリズムで RCP の解決
RCP 問題において、変数の x と p には複雑な依存関係があるため、分散アルゴリズムで解決するのは困難である。本章では、RCP の問題構造を分析し、それを効率的に解決できる分散アルゴリズムを提案している。
具体的には、新たにトラヒックエンジニアリング問題(TE)と価格交渉問題(PN)を構造化し、それぞれを解決して、それらの結果から RCP の解を復元する。
（１）RCP 問題のシーケンシャル的な解結合
RCP 問題のシーケンシャル的な解結合方法は以下の通りである。新たに構造化する TE 問題は：そして、PN 問題は：である。x*は TE の解である。以下の定理で上記の TE と PN をシーケンシャル的に解くことで RCP 問題の解を獲得できることを述べる。
定理１：x*は TE の解であり、p*は PN の解であった場合、(x*,p*)は RCP の解である。
（証明は省略）（２）ラグランジュ双対方法による解結合方法を用いて TE 問題を解く
TE 問題は tier-2 ISP によるデマンドと tier-3 ISP によるキャッシュアップロード帯域上限に制約された最適問題である。tier-2 ISP 毎のデマンド制約は独立しているが、キャッシュアップロード帯域上限は各tier-2 ISP と結合している。よって、ラグランジュ双対方法を用いて、キャッシュアップロード帯域上限の制約を緩和することで、TE の解結合を行う。具体的に、TE のラグランジュ双対問題を以下の通りに構造化する： はラグランジュ乗数である。そして、ラグランジュ双対関数は：であり、双対問題は：である。その双対問題は劣勾配方法を用いて解ける。具体的には、各 cj において、  を以下の通りに更新す
る：

その中で：

4

k は反復の周期番号であり、 1 は歩長である。この問題には、内在的な解結合構造を持っている。具体的に、
各 ti と cj において：この問題も制約付き最適化問題であり、劣勾配方法で解くことができる（具体的な方法の説明は省略する）。
（３）主問題解結合方法を用いて PN 問題を解く
PN 問題は TE 問題の解を入力し、ナッシュ累乗を最大化する解を求める。PN 問題を主問題解結合方法で解く。具体的には、適切な初期解から始め、反復周期 k において、tier-2 ISP ti は pij(k)の偏導関数を以下の通りに解く：

それに対し、tier-3 ISP cj は pij(k)の偏導関数を以下の通りに解く：

よって、pij は以下の通りに更新する：

 は歩長である。
４ 提案方式の評価
本章では、シミュレーションによる提案方式の評価を説明する。
４-１ シミュレーション設定
ISP 接続トポロジー。本研究では、典型的なランダムなトポロジーである ER と BA に加え、CAIDA[4]からの実際のデータの解析を行い、インターネットの一部のトポロジーを切り離し、それらのトポロジーを用いて提案手法の評価を行う。それぞれのトポロジーは HER、HBA と C2516 と表示する。
ISP のワークロード。ワークロードを生成するに当たり、コンテンツの人気度と地域的な偏りを考慮している。コンテンツの人気度に関しては、Zipf 分布を用いている。地域的な偏りというのは、同じコンテンツの異なる地域における人気度の差[5]を表す指標である。
キャッシュに関する設定。本研究では、tier-2 ISP と tier-3 ISP の全てにおいてキャッシュ設備の導入を想定している。ISP は人気順でコンテンツをキャッシュする。キャッシュのサイズに関して、tier-3 ISPのキャッシュサイズがコンテンツ全体のトータルサイズの 4%、tier-2 ISP のキャッシュサイズをそれの２倍に設定している。
４-２ シミュレーション結果
コンテンツ人気度と地域的な偏り。コンテンツ人気度の影響を研究する時に、地域的な偏りを 0.5 に固定

5ISPの均⼀利得

均⼀トランジットトラヒック削減

し、コンテンツ人気度の偏りを 0.1 から 0.9 まで変化させる。トランジットトラヒックの減少は図２、ISPの平均利得は図３に示している。コンテンツ人気度の偏りが大きくなるに連れ、提案手法のメリットが減少する傾向にあるが、その偏りが最大の 0.9 になる時においても、提案手法を用いる時のトランジットトラヒ
ック削減と ISP の利得は、提案手法を用いていない時に比べると、0.9 倍の改善があることが明らかになる。

コンテンツ⼈気度の偏り
コンテンツ⼈気度の偏り
図２：均一トランジット
トラヒック削減 vs. コン
テンツ人気度の偏り

図３：均一利得 vs. コン
テンツ人気度の偏り

ISPの均⼀利得

均⼀トランジットトラヒック削減

地域的偏りの影響を研究するために、コンテンツの人気度の偏りを 0.5 と設定し、地域的な偏りを 0.1 から 0.9 へと変化させる。トランジットトラヒックの削減と ISP の利得は図５と図６に示している。グラフから、地域的偏りが増加するに連れ、提案方式のメリットが大きくなることが明らかになった。それは異なる
ISP は違うコンテンツをキャッシュする傾向にあることから、ISP 間で連携するメリットが大きくなるためと考えられる。

⼈気度の地域的偏り

⼈気度の地域的偏り

図４：均一トランジットト
ラヒック削減 vs. コンテンツ人気度の地域的偏り

図５：均一利得 vs. コンテ
ンツ人気度の地域的偏り

５ むすび
近年、情報指向ネットワークの発展による新たな ISP 間接続方式であるコンテンツピアリングが注目されているが、コンテンツピアリングはピアリング関係にある ISP 間にしか適用できず、キャッシュ導入のメリットが充分発揮できないという問題がある。それに対して、本研究ではリモートコンテンツピアリングの提案を行っている。その結果、リモートコンテンツピアリングによりピアリング関係にない ISP 間のキャッシュ連携を可能にすることで、キャッシュ導入のメリットを最大限引き出すことができた。そして、理論分析とシミュレーションによって、提案手法がトランジットトラヒックの削減と ISP の利得の向上につながることを明らかにした。

【参考文献】

6

[1]V. Pacifici, F. Lehrieder and G. Dan, “Coordinated Selfish Distributed Caching for Peering
Content-Centric Networks”, IEEE Transactions on Networking, Vol. 24, pp: 3690-3701, Mar. 2016[2]J. M. Wang, X. Dai, and B. Bensaou, “Content Peering in Content Centric Networks”, in Proc. LCN
2014, pp: 10-18, 2014[3]J. Nash, “Two-Person Cooperative Games”, Econometrica, Vol. 21, No. 1, pp: 128-140, Jan. 1953
[4] “CAIDA: Center for Applied Internet Data Analysis”, available online at http://www.caida.org[5]S. K. Fayazbakhsh, Y. Lin, A. Tootoonchian, A. Ghodsi, T. Kbponen, B. M. Maggs, K. C. Ng, V.
Sekar, and S. Shenker, “Less Pain, Most of the Gain: Incrementally Deployable ICN”, in Proc.
SIGCOMM 2013, pp: 147-158, 2013

〈発表題名資料〉
掲載誌・学会名等

CCNinfo: Discovering Content andNetwork Information in Content- The 101st IETF/IRTF meeting
Centric Networks
A
Cooperative
Mechanism
for
Efficient Inter-Domain In-network IEEE/ACM IWQoS 2017
Cache Sharing
A Study on Inter-Domain Cache
The 8th IEICE ICN workshop
Sharing Mechanism

7

発表年月2018 年 3 月

2017 年 6 月

2017 年 4 月