グラフ信号処理によるトラヒック量推定に基づいた動的 VCCN 構築法に関する研究
代表研究者

浦山康洋

高知工業高等専門学校

ソーシャルデザイン工学科

助教

1 はじめに
光回線をはじめとするブロードバンドの普及に伴い，現在のインターネットでは動画や電子書籍など様々なディジタルコンテンツが配信されるようになった．特に，近年は動画コンテンツの増加が凄まじく，2022
年にはビデオトラヒックが全通信トラヒックの 82%を占める予想も発表されている[1]．これらのコンテンツを効率的に配信することを目的とした次世代のネットワークとして，コンテンツ指向ネットワーク（CCN：
Content Centric Network）[2]の活用が期待されており，研究開発が盛んに行われている[3,4,5]．
従来の IP ネットワークとは異なり，CCN ではコンテンツごとに設定されたユニークな識別子を用いてデータ転送を行う．図 1 に，CCN におけるデータ転送の流れを示す．はじめに，ユーザが Interest パケットと呼ばれるコンテンツの取得要求をサーバに向けて送信する．ここで，Interest パケットには要求コンテンツの識別子が含まれていることに注意する．Interest パケットを受信したサーバは，識別子が一致するコンテンツを探索し，ユーザへ返信する．このとき，当該コンテンツは Interest パケットが辿ってきた転送経路を遡ることでユーザのもとへと転送される．コンテンツを中継した各ルータはコンテンツストア（CS：ContentStore）と呼ばれるバッファ領域に，当該コンテンツをキャッシュとして保存する．CS に保存されたキャッシュは後で再利用でき，ユーザが同一のコンテンツを繰り返し要求してきた際には，遠方に位置するサーバだけでなく近隣のルータからもコンテンツを獲得することができる．結果として，CCN では転送ホップ数の減少，さらには通信網内における輻輳の解消が期待される[6]．

図1

CCN によるデータ通信

本研究では，情報が煩雑する現代の通信ネットワークにおいて迅速なコンテンツ配信を実現することを目的とし，CCN とネットワーク仮想化技術を組み合わせた VCCN（Virtual Contents Centric Network）の効率的な構築法について研究・調査を行った．

2 CCN と仮想化
ネットワーク仮想化技術を用いると，基盤となる物理網のネットワーク資源（ルータの CPU やメモリ，通信回線の伝送帯域など）を仮想化でき，仮想化した資源を組み合わせることで論理的に独立した複数の仮想網を構築できる．これらの仮想網は有限の物理資源を共有して構築されるため，ネットワーク仮想化ではどの仮想網にどれだけの資源を分配するかを検討することが重要となる．
上記の検討は，CCN の仮想化においても必要不可欠である．[7]では，構築する各 VCCN とネットワーク全体の性能は，VCCN 内のルータに割り当てる CS（バッファ領域）の容量によって大きく変化することが示されている．さらに，[8]では CCN のトポロジに応じて最適な CS の割当方法が異なることが明らかにされており，VCCN の性能を最大限に引き出すためにはネットワークトポロジの検討も重要となる．

1
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

3 多目的最適化問題を用いた VCCN 構築法
3-1 概要本章では，本研究調査において提案・確立した，多目的最適化問題を用いて複数の VCCN を効率的に構築する方式について説明する．本方式では，VCCN のキャッシュヒット率に基づいて設定された二つの目的関数を最小化する組み合わせ最適化問題を考え，本問題に対する近似解を遺伝的アルゴリズムで導出することで各VCCN のトポロジと配分する資源量を決定する．
今，ノード集合𝑉で表される CCN があり，ノード𝑣𝑖 (∈ 𝑉)の直下に位置するユーザがコンテンツの取得要求を送信した仮定する．ノード𝑣𝑖 の CS に保存可能なキャッシュの数を𝐶𝑖 ，CCN に存在する全コンテンツ数を𝐶𝑎𝑙𝑙とするとき，ノード𝑣𝑖 の CS で当該ユーザが要求コンテンツのキャッシュを発見できる確率𝑝𝑖 は以下の式で与えられる．
𝐶𝑖𝐶𝑎𝑙𝑙𝑝𝑖 =…(1)

ノード𝑣𝑖 の CS 内に該当コンテンツが存在しなかった場合，𝑣𝑖 は自身が持つ経路制御情報に従って，要求を次ノードへ転送する．𝑣𝑖 からコンテンツの配信用サーバまでの経路長（ホップ数）を𝑁，𝑣𝑖 と配信用サーバを結ぶ経路において𝑛 (< 𝑁)番目に通過するノードを𝑣𝑛 ，𝑣𝑛 の CS に保存可能なキャッシュの数を𝐶𝑛 とする．このとき，当該ユーザがノード𝑣𝑛 の CS から要求コンテンツのキャッシュを取得できる確率𝑝𝑛 は，式(1)を拡張して以下のように与えられる．
𝑛−1

𝐶𝑖𝑝𝑛 =∏(1 − 𝑝𝑚 )𝐶𝑎𝑙𝑙…(2)𝑚=1

ここで，式(2)の総乗部分は，1 番目から𝑛-1 番目に通過したいずれのノードにおいても要求コンテンツのキャッシュを発見できない確率を計算している．
本研究では，各 VCCN へ分配する資源量を決定する組み合わせ最適化問題を，式(1)および式(2)を用いて次のように定式化した．以下では基盤となる CCN 上に𝐾個の VCCN を構築するものとし，各 VCCN には専用のコンテンツ配信サーバ𝑆 𝑘 (𝑘 = 1, ⋯ , 𝐾)が設置されるものとする．また，ノード𝑣𝑖 (∈ 𝑉)に備わっている CS の最大容量を𝑈𝑖 ，ノード𝑣𝑖 とサーバ𝑆 𝑘 を最短経路で結んだ時のホップ数を𝑁𝑖,𝑘 とする．
min𝑧1 , 𝑧2…(3)𝑁𝑖,𝑘subject toℎmax ∑ ℎ {𝛼 ∏ (1 −𝑖,𝑘ℎ=0𝑛=1𝑘𝐶𝑖,𝑛)} < 𝑧1
𝐶𝑎𝑙𝑙𝑁𝑖,𝑘ℎℎ=0𝑛=1…(4)𝑘𝐶𝑖,𝑛1∑ ∑ (∑ ℎ {𝛼 ∏ (1 −)}) < 𝑧2
𝐾|𝑉|𝐶𝑎𝑙𝑙𝑘

α={𝑖𝑘𝑘⁄𝐶𝑎𝑙𝑙𝐶𝑖,𝑛(ℎ ≠ 𝑁𝑖,𝑘 )1(𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒)…(5)…(6)𝐾∑ 𝑋𝑖,𝑘 ≤ 𝑈𝑖…(7)

𝑘=1𝑘∑ ∑ 𝑥𝑖,𝑗
≥ 1,𝑇 ⊂ 𝑉,

𝑇≠𝜙…(8)𝑖∈𝑇 𝑗∈𝑉∖𝑇2
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

本最適化問題の式(4)を満足することにより，各 VCCN における最大転送ホップ数の期待値が最小化される．
同様に，式(5)を満足することで，各 VCCN における平均転送ホップ数の期待値が最小化される．式(7)は VCCNの CS に割り当てられる仮想領域の総和が，基盤となるルータのバッファ容量を超えないことを意味してい𝑘る．式(8)はカットセット制約[9]を表しており，𝑥𝑖,𝑗は𝑘番目の VCCN のノード𝑖 − 𝑗間にエッジが存在するならば 1，さもなければ 0 となる変数である．本制約を満足することで設計する VCCN のトポロジに対する連結性が保証される．本方式を用いて構築した VCCN では，キャッシュヒット率の向上が期待できるため，転送ホップ数の削減に伴うコンテンツ配信の効率化が期待できる．
3-2 数値例（１）シミュレーション条件
提案方式の有効性は，図 2 に示す二つのネットワークトポロジに対する数値シミュレーションによって調査した．図 2(a)の一つ目のトポロジは，ノード数が 22 個，エッジ数が 37 本のトポロジである．また，図2(b)の二つ目のトポロジは Internet2[10]を模したネットワークトポロジであり，40 個のノードと 51 本のエッジで構成される．性能比較を行うために，本シミュレーションでは VCCN のトポロジ設計は行わず，CS には均等に資源を配分する単純な方式についても性能評価を行った．

(a)トポロジ 1
図2(b)トポロジ 2

シミュレーション用のネットワークトポロジ

以下では，基盤となる CCN 上に構築する VCCN の数は 4 とし，各 VCCN にはコンテンツ配信用の専用サーバが一台ずつ設置されると仮定する．ここで，本シミュレーションでは各 VCCN を利用するユーザが最短経路を用いて当該サーバへアクセスすることに注意する．さらに，𝑘 (𝑘 = 1, ⋯ ,4)番目の VCCN を利用するユーザが𝑘𝑗 (𝑗 = 1, ⋯ , 𝐶𝑎𝑙𝑙)番目のコンテンツを要求する確率𝑝𝑗𝑘 は，以下の式で与えられる Zipf 分布に従うものとする．
𝑝𝑗𝑘 =1⁄ 𝑗𝑘𝐶𝑎𝑙𝑙∑𝑖=1 1⁄ 2𝑖…(9)本シミュレーションでは，基盤となる CCN のトポロジおよびサーバの位置（図 2 参照）を表 1 のように変化させ，全三つの条件下でシミュレーションを行った．

基盤 CCN のトポロジ
配信サーバの位置
各ノードの資源量構築する VCCN の数
VCCN 内の総コンテンツ数

表 1 パラメータの設定
条件 1
条件 2
トポロジ 1
A-B-C-D
C-D-E-F𝑈𝑖 = 800
𝐾=4𝑘
𝐶𝑎𝑙𝑙= 25000

条件 3
トポロジ 2
A-B-C-D

3
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

（２）シミュレーション結果
図 3 は Zipf 分布のパラメータ𝑠を 0.5，0.75，1.0 と変化させた場合における VCCN のキャッシュヒット率を表している．図 3 より，条件 1 において提案法は，𝑠の値によらず，比較対象よりも高いキャッシュヒット率を示していることがわかる．その一方で，条件 2 と条件 3 において，提案法のキャッシュヒット率は𝑠=0.75,1.0 のときに比較対象よりも低い値を示していることがわかる．

(b)𝑠=0.75(a)𝑠=0.5
図3(c)𝑠=1.0

VCCN のキャッシュヒット率

図 4 は Zipf 分布のパラメータ𝑠を 0.5，0.75，1.0 と変化させた場合における転送ホップ数の削減率を表している．なお，この図ではユーザがキャッシュを一切使わずにコンテンツを取得した場合の平均転送ホップ数を 1 とし，その相対値を示していることに注意する．図 4 より，𝑠=0.5，0.75 のときは基盤 CCN のトポ
ロジおよびサーバの位置によらず，提案法は比較対象よりもコンテンツ配信時の転送ホップ数を削減できていることがわかる．中でも，𝑠=0.75 の条件 3 での効果が最も大きく，比較対象と比べて約 1.6%の性能向上が確認できる．その一方で，𝑠 =1.0 のときには提案法の効果が小さく，条件 1 と条件 2 においては比較対象よりも平均転送ホップ数が大きくなるという結果が得られた．

(a)𝑠=0.5(b)𝑠=0.75
図4(c)𝑠=1.0

転送ホップ数の削減率（３）考察
本節では，得られたシミュレーション結果について考察を述べる．まず，図 3 の条件 1 と条件 2 の結果から，コンテンツサーバの配置位置が提案法の性能に与える影響について考える．提案法には，サーバから遠方に位置するルータに対して多くの資源を配置し，サーバまでのホップ数が多いユーザ（遠方に位置するユーザ）が近隣のルータのキャッシュを利用しやすくなるよう誘導する特徴がある．ここで，条件 2 ではサーバ C と E，サーバ D と F がそれぞれ隣接しているため，提案法では資源を優先して割り当てたい遠方に位置するルータに関して，競合が発生してしまう．結果として，各 VCCN の CS に十分な資源を配分することがかなわず，条件 2 では条件 1 よりもキャッシュヒット率が低くなったと考えられる．

4
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

次に，図 3(c)と図 4(c)の結果に注目し，𝑠=1.0 のときに比較対象の性能が提案法よりも高くなった理由を説明する．今回のシミュレーションでは，各コンテンツの要求頻度を Zipf 分布によって決定している．ここで，図 5 に Zipf 分布の累積分布関数を示す．図 5 より，Zipf 分布では𝑠の値が大きくなるにつれて，一部のコンテンツが集中的に選ばれる傾向が強くなることが読み取れる．特に𝑠=1.0 のときには，約 53%の確率で上位 1%に含まれるコンテンツが選ばれるなど，要求頻度にかなりの偏りが生じている．この偏りにより，各ルータへ均等に CS の容量を配分する比較対象では，CS の容量が小さいにもかかわらずキャッシュヒット率の上昇が全ルータで発生し，提案法よりも高い性能を示したと推察できる．

図 5

Zipf 分布の累積分布関数

最後に，図 3(b)と図 4(c)の𝑠=0.75 時の結果に注目する．このとき，条件 3 の提案法は比較対象よりもキャッシュヒット率が低いにもかかわらず，平均転送ホップ数の大幅な削減に成功している．図 6 に𝑠=0.75，
条件 3 で行った数値シミュレーションの全要求に対する転送ホップ数の分布を示す．図 6 より，提案法では転送ホップ数が 7 ホップ以上となる要求の割合が比較対象よりも小さくなっていることがわかる．一方，提案法は転送ホップ数が 1 から 3 である低ホップの割合も高く，最大転送ホップ数と平均転送ホップ数の二つを最小化する目的関数の効果が適切に表れていると言える．

図 6

転送ホップ数の分布（𝒔=0.75，条件 3）

4 グラフ信号処理によるトラヒック量推定に基づいた動的 VCCN 構築法
本研究ではさらに，前章で確立した方式の拡張として，システム内の混雑度に応じて各 VCCN を動的に再構築する方式の検討を行った．本方式では，構築された各 VCCN 内に流れるトラヒック量をグラフ信号処理[11]によって推定し，推定結果から現状のトポロジではトラヒックを収容しきれないと判断された VCCN を動的に再構築する．しかしながら，グラフ信号処理による推定制度が予測よりも低く，当該方式を確立すること

5
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

は叶わなかった．以下に，グラフ信号処理によるトラヒック推定手法の処理手順を示す．
今，エッジ数が𝑀である VCCN 内に流れるトラヒック量を推定する場合を考える．本手法ではまず，𝑚 (𝑚 <𝑀)本のエッジに対してトラヒック量をセンシングし，得られた結果を信号値𝑓𝑖 (𝑖 = 1, ⋯ , 𝑚)とする．次に，ノード数が VCCN のエッジ数と同じ𝑀であるグラフ𝐺を用意し，ノード𝑣𝑖 (𝑖 = 1, ⋯ , 𝑚)と𝑓𝑖 を対応付けることでグラフ信号𝑓を生成する．このグラフ信号𝑓のスペクトル成分を L1 線形計画によって導出し，導出した結果に逆グラフフーリエ変換を施すことによって，VCCN 内すべて（𝑀本のエッジに流れる）トラヒック量を復元・推定する．本手法では，信号𝑓の基盤となるグラフ𝐺をどのように設計するかによって，推定精度が大きく変化することが確認された．本研究では，トポロジを“VCCN と同一”
・“完全グラフ”，グラフ𝐺におけるエッジの重みを“媒介中心性をもとに決定”・“次数中心性をもとに決定”・“すべて１”，といった具合にグラフ𝐺の設計方法を変更して推定制度の評価を行ったが，問題を解決するには至らなかった．

5 まとめ
本研究では，CCN とネットワーク仮想化技術を組み合わせた VCCN（Virtual CCN）を主な研究対象とし，限られた資源下においても迅速なコンテンツ配信を可能にする VCCN の構築法を提案した．提案方式では，構築する各 VCCN に対するトポロジと資源配分を決定する問題を，キャッシュヒット率の最適化を目的とした多目的最適化問題として定式化し近似解を導出する．提案法の性能は二つのネットワークトポロジに対する数値シミュレーションで評価し，資源を均等に配置する単純な方法との比較によって提案法の有効性を調査した．数値例から，提案法は VCCN のトポロジ設計と資源配置を適切に行うことができ，基盤となる CCN のトポロジやサーバの位置によらず，コンテンツの転送ホップ数を削減できることがわかった．
その一方で，本研究ではグラフ信号処理を用いたトラヒック量推定手法の精度を向上させることができず，システム内の混雑度に応じて各 VCCN を動的に再構築する方式を研究調査期間内に確立することは叶わなかった．
解決できなかった問題点については今後も引き続き研究調査を行い，当該方式の将来的な確立を目指す．

【参考文献】[1] Cisco Visual Networking Index: Forecast and Trends 2017-2022, 2018.
[2] V. Jacbson, D. K. Smetters, J. D. Thornton, M. F. Plass, N. H. Briggs and R. L. Braynard,``Networking Named Content,'' Proc. CoNEXT'09: the 5th International Conference on Emerging
Networking Experiments and Technologies, pp. 1-12, Dec. 2009.
[3] M. Zhang, H. Luo and H. Zhang, ``A Survey of Caching Mechanism in Information CentricNetworking,'' IEEE Communication Surveys & Tutorials, vol. 17, no. 3, pp. 1473-1499, Apr. 2015.
[4] Y. Gao and J. Zhou, ``Probabilistic Caching Mechanism Based on Software Defined ContentCentric Network,'' Proc. IEEE 11th International Conference on Communication Software andNetworks (ICCSN), Jun. 2019.
[5] F. Suzuki, S. Ohzahata, R. Yamamoto and T. Kato, ``An Efficient Dynamic Bandwidth Reservation
Method in Content-Centric Network,'' Proc. IEEE International Conference on Consumer
Electronics - Taiwan (ICCE-TW), May 2019.
[6] M. A. Naeem, M. A. U. Rehman, R. Ullah and B. Kim, ``A Comparative Performance Analysis ofPopularity-Based Caching Strategies in Named Data Networking,'' IEEE Access, vol. 8, pp. 5005750077, Mar. 2020.
[7] K. Tsukamoto, K. Ohsugi, H. Ohsaki, T. Hasegawa and M. Murata, ``Cache Performance Analysis
of Virtualized Router on Virtual Content-Centric Networks,'' International Journal of NextGeneration Networks (IJMGM), vol. 5, no. 4, Dec. 2013.
[8] D. Rossi and G. Rossini, ``On Sizing CCN Content Stores by Exploiting Topological Information,''Proc. IEEE INFOCOM Workshop, 2012.
[9] 梅谷俊治, ``組み合わせ最適化入門：線形計画から整数計画まで, '' 自然言語, vol. 21, no. 5, pp. 10591090, Sept. 2014.
[10] Internet2, https://www.internet2.edu/6公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

[11] 田中雄一, ``グラフ信号処理のすゝめ,” 電子情報通信学会 基礎・境界ソサイエティ Fundamentals
Review, vol. 8, no. 1, pp. 15-29, 2014.

〈発題名

仮想化 CCN における転送ホップ数を考慮したキャッシュ割当決定法
限られた資源下で効率的なコンテンツ配信を実現する多目的最適化問題を用いた仮想CCN 構築法

表資料〉

掲載誌・学会名等

発表年月

電気学会中国支部
第 12 回高専研究発表会

2020 年 3 月

電子情報通信学会
ネットワークシステム研究会

2020 年 5 月

7
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度