お知らせ 2023年度・2024年度 学生員 会費割引キャンペーン実施中です
お知らせ 技術研究報告と和文論文誌Cの同時投稿施策(掲載料1割引き)について
お知らせ 電子情報通信学会における研究会開催について
お知らせ NEW 参加費の返金について
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2013-12-19 08:35
災害システムのCCN応用に関する研究
余 娜Arifuzzaman Mohammad余 恪平佐藤拓朗早大NS2013-134
抄録 (和) 1. はじめに
都市型災害においては災害が集中し,大きな被害をもたらす.インターネット,携帯などの情報通信の手段を用いて,リアルタイムで災害場所の情報を把握することが必要である.東日本大震災も含めて災害時にはtwitter やFacebookのようなsocial networkが比較的通信回線を維持している.このことから,インターネットを使った災害時に適用可能なsocial networkの開発は重要である.そのために,膨大な被災情報を被災者が逐次,写真は音声でweb上へアップデートし,その情報を共有化することでお互いが被災状況を理解判断してより安全は対応をとることを目的として災害情報共有システムを開発した.
災害における情報共有システムを利用するユーザは,大都市圏において災害が発生した場合は,同時に数百万件以上となることが予測され,通常の数十倍にも及ぶ被災地向けの通信が集中し,それら通信サービスに対応するための通信処理能力が大幅に不足する.膨大なアクセスでサーバへの負担が増加させ,通信途絶等の状態が生ずる恐れもある.そのため,通信ネットワークの耐災害性強化に向けて通信処理資源をより効率的に利用するネットワークを統合的に構成することが必要である.
Van Jacobsonが提案した新世代コンテンツ中心ネットワーク((Contents Centric Network; CCN)を用い,耐災害性強化に向けるネットワークを構成する方法を考えられる[1]. CCNはコンテンツ指向ネットワークの一つとして提案され,近年活発に研究されている.CCNはIP アドレスではなくコンテンツ ID をベースにネットワーク制御を行うアーキテクチャであり,コンテンツの発見および転送をコンテンツ指向な方法で実現する.CCN において,従来のネットワークと違い,コンテンツをサーバのみならず,任意の中継ルータにもキャッシングさせることにより,ネットワークトラヒックの削減やリクエスト応答時間の短縮に期待できる.さらにユーザのリクエストに対し,サーバのみならず,中継ルータからでもコンテンツのキャッシュ取得できるため,サーバがどこにあっても,またサーバは実際に稼動しているか否かも,通信の問題にならない.特に災害時にネットワークが切断された時においても被災地等の通信を確保できると考えられる[2].
一方で,大量なコンテンツを効率的に発見し,転送するためには,CCNのキャッシング能力が非常に重要である.コンテンツのサイズやキャッシュの容量が上昇すると,適切なキャッシュ判断が求められる.近年はキャッシュ置換ポリシー(Cache Replacement Policy: CRP)を検討する研究に比べて,キャッシュデシジョンポリシー(Cache Decision Policy: CDP)を検討する研究が少ない[3].さらに,従来のキャッシュデシジョンポリシー方式はネットワークリソースを合理的に利用していなかった,また,コンテンツの人気度が考慮されないなどの理由で,キャッシュヒット率が低下していた[3].その中でIoannis Psarasにより提案されたProbCacheでは,同じパスでキャッシュの多重化を公平に行うことで,キャッシュヒット率などのパフォーマンスを向上させることが明らかにする[4].しかし,従来のProbCache方式はコンテンツの人気度を考慮しないため,現実上特に災害時に災害地情報を中心にして集中アクセスする場合,キャッシュヒット率の向上効果を発揮できない.
そこで本研究では,コンテンツ中心ネットワークにおけるキャッシュヒット率を向上させるために効率的なキャッシュデシジョンポリシーを提案する.具体的には,単なるコンテンツをネットワークトポロジ全体で均一に分散させるのではなく,経路パスのキャパシティとコンテンツの人気度を組み合わせ,コンテンツそれぞれのキャッシュされる確率を算出する.これによって,人気度の高いコンテンツとそれほど高くないコンテンツをネットワーク全体でより合理的に分散させるキャッシュデシジョンポリシーである.

2. コンテンツ中心ネットワークとは
従来のネットワークはホスト間の通信が中心であるが,現在のインターネットの利用は情報検索や情報配信・取得が中心になった.ユーザがコンテンツの場所(where)により,コンテンツ自体(what)に興味があるため,ネットワークはホスト中心ではなく,コンテンツに基づくより効率的にコンテンツを配信・取得できるネットワークアーキテクチャを求められる[1].
コンテンツ中心のネットワークアーキテクチャの一つとして,Van Jacobsenが提案したコンテンツ中心ネットワーク(Content Centric Network: CCN)が注目されている.CCNはコンテンツの名前に基づいて通信を行うため,通信相手の場所を意識する必要はない.従来のend-to-end通信と違い,コンテンツは中継ルータにキャッシュされるため,特に災害時にトラヒックの削減や応答時間の短縮が望まれる.
CCNでは,ユーザからのコンテンツリクエスト(Interestと呼ばれる)とコンテンツ(Dataと呼ばれる)の2種類のパケットがある.中継ルータはコンテンツキャッシュのみならずコンテンツ発見・転送などにも役割を果たす.ルータはルーティングテーブルFIB(Forwarding Information Base),コンテンツバッファCS(Content Store),フォワーディングテーブルPIT(Pending Interest Table)から構成される.コンテンツリクエストはルーティングテーブルFIBによりコンテンツへと転送され,コンテンツ発見が行われる同時に,経路情報がフォワーディングテーブルPITに残され,これを辿ることでコンテンツIDに基づくコンテンツ転送が実現される[3].
災害時には災害情報の発信と受信するために,膨大なアクセスが短時間でネットワークで行われるが,CCNにおいてはユーザがコンテンツ配信サーバのみならず中継ルータからでもコンテンツを取得できるため,通信トラヒックを減少させる.さらに,コンテンツのキャッシュを中継ルータで保持していれば,オリジナルのコンテンツを持つノードがどこにあっても,そのノードが稼働しているか否かも,通信上一切問題とならない.災害時におけるネットワーク切断された時おいても被災地等の通信を確保できると考えられる.CCNネットワークが通信ネットワークの耐災害性強化に向いているとも言える.図1は災害時におけるCCNネットワークの動作である.

図1 災害時におけるCCNネットワーク

3. 関連研究
CCNにおいて多量のコンテンツを効率的に発見,転送をするためには,キャッシングの能力が非常に重要であると考えられる.特に,近年の技術向上により中継ノードにおいて大容量のストレージを実装することで,大容量のキャッシュを実装することは可能である.しかし,一方ではコンテンツ数やサイズの顕著な上昇ことを考慮すると,依然として慎重なキャッシュ判断が要求されることは十分に考えられる.このため,効率的なキャッシュデシジョンポリシー(Cache Decision Policy)に関する研究が進められているに対して,CCN に関する研究はまだ黎明期である.キャッシュ性能に関する評価についても基礎検討段階のものが多い[5,6].
CCNが実装しているLCE(Leave Copy Everywhere)方式については,データ保持ノードから取得要求発行ノードまでの経路上すべてのノードをキャッシュする.それに対し,LCD(Leave Copy Down), MCD(Move Coy Down),Probなどの方式では,コンテンツが一部のノードのみをキャッシュする[7].各方式は下図に示す.
? LCE
LCEについては,経路上にすべてコピーされるため,ノードへのコンテンツの冗長性が高く,アクセスの集中するノードでは,キャッシュの置き換えが多発し,キャッシュヒット率が低下という不足がある.LCEは図2に示す.








図2 LCE
? LCD
ヒットしたノードの 1 段端末よりにコピーするため,コンテンツを下位階層のノードにコピーするまで多数のリクエストの必要である.LCDは図3に示す.








図3 LCD
? MCD
LCDと似て,ヒットしたノードの 1 段端末よりに移動する.MCDは図4に示す.
? Prob
経路上に確率pでコピーする.pは1の場合,ProbはLCEと同じである.Probは図5に示す.
Prob方式の一つとして,Ioannis Psarasが提案したProbCacheアルゴリズムはほかの方式より効率的にネ







図4 LCD









図5 LCD
ットワークリソースを利用することが明らかになった.サーバへヒット率は20%減少し,ヒットまでのホップ数は10%減少した.さらに,キャッシュの置換も大幅に減少した.しかしながら,probCacheにはコンテンツの人気度を考慮してないため,人気度は偏りがあると,キャッシュヒット率を減少させる[4].
WEB上コンテンツの人気分布はZipfの法則に従い,各コンテンツへの要求頻度を与える.コンテンツ要求される頻度を ,コンテンツの人気の順位を , を常数,ɑをパラメータとすると,コンテンツの人気度は下記になる[8].



コンテンツ10000とし,ɑは1と1.5とした場合,コンテンツリクエスト頻度は図6に示す.上位コンテンツの個数だけのコンテンツリクエストを占める割合は図7に示す.図の示すのように,コンテンツの人気度が違うとコンテンツがリクエストされる頻度が大幅に変わる.具体的に,ɑ=1場合は90%のリクエストは3500個のコンテンツに集中しているに対し,ɑ=1.5の場合,わずか50個のコンテンツがリクエスト全体の90%を示している.人気の偏りが大きいほどリクエストが人気コンテンツに集中する.ProbCacheはコンテンツキャッシュの多重化を考慮していったが,コンテンツの人気度を考慮してなかった.災害時に災害地を中心としてコンテンツがリクエストされる場合,キャッシュヒット率の向上に大きな課題がある.

図6 コンテンツ人気度分布
図7 上位コンテンツの個数ごとの
コンテンツリクエストを占める割合

4. 提案手法
本研究では,従来のProbCacheアルゴリズムのパスキャパシティとキャッシュウェイトを用いてコンテンツをネットワークトポロジ全体で均一に分散させるではなく,コンテンツ人気度も考慮し,コンテンツをより効率的に分散させ,キャッシュヒット率を向上させる改善方法を提案する.
probCacheでは,パスのキャパシティ定量的に分析し,コンテンツコピーの多重化を公平に行う.パスのキャパシティを示すに,TSI(Time Since Inception)とTSB (Time Since Birth)が2つの要素がある.TSIはユーザがコンテンツをリクエストする時に,経由したノードの数を記録し,リクエストメッセージに格納される.TSBはコンテンツがサーバからユーザに返送される時に,経由したノードの数を記録する.TSBは大きいほど,サーバに遠くなり,ユーザに近くなる.また,コンテンツが返送される時はTSIの値は変わらない.下図はTSIとTSBの例である[4].







図8 ProCacheデザイン
? パスキャッシングキャパシティ
上図のように,リクエスト1とリクエスト2がサーバまでホップ数はそれどれ5と4である.パスのトータルキャッシュキャパシティは ,リクエスト1の ,リクエスト2の になる.グレーのノードがユーザ1とユーザ2を共有するに対し,白いノードがユーザ1のみ使い,黒いノードはユーザ2にのみ使う.パスはパケットをキャッシュできる回数(パスキャパシティ)を で表すと,下記の計算式になる.

はTSIの値, はTSBの値である.図8を例とすると,ノード2に対し,ユーザ1が要求したコンテンツが返送される時,TSI=5,TSB=2,ユーザ2が要求したコンテンツが返送される時,TSI=4,TSB=2.計算式の は残りのキャッシュキャパシティを示す.
? キャッシュウェイト
キャッシュのコピーをパスに公平に配置できるために,多数のコンテンツフォローを考慮することが求められる.そのために,コンテンツをパスのどのノードにキャッシュするかを示すために, ファクターを考える.

はTSIの値, はTSBの値である. の値が大きくなると,ノードがユーザに近いことになる.
従来のProbCacheの計算式は下記になる。


? コンテンツの人気度
キャッシュヒット率を向上させるため,コンテンツの人気度が不可欠な要素である.そこで,従来ProbCacheアルゴリズムを改善する方法として,コンテンツの人気度分布を考慮する.上記に示すように,コンテンツの人気度がZipf法則を用いて表す. の値が大きくなると,コンテンツの人気度が高くなる. は出現頻度が 番目に大きい要素がリクエストされる確率,ɑはリクエスト集中レベルを示すパラメータである.



本研究では,提案される改善アルゴリズムは下記の計算式で示す. はノード にコンテンツ をキャッシュする確率である.





例として,コンテンツ1,2,3,4,5,6がある.コンテンツ3の人気度が一番高い,コンテンツ1の人気度が一番低い.

図9 従来のProbCacheコンテンツ配置

図10 ProbCache+コンテンツ配置
ProbCacheアルゴリズムとProbCache+アルゴリズムでは理想なコンテンツ配置はそれぞれ図9と図10に示す.従来のProbcacheでは,コンテンツを均一に経路パスに分散させることに対し,Probcache+では,コンテンツの人気度分布を考慮されることで,人気度高いコンテンツと人気度低いコンテンツは合理的に分散させる.具体的に、コンテンツ3が各ノードずつキャッシュされ、合計3回に対し、コンテンツ1は1回のみキャッシュされる。これにより、人気コンテンツにリクエストを集中しても、キャッシュヒット率を向上させることが実現できる。

5. シミュレーション結果と分析
各方法の性能をシミュレーションにより評価する.ccnSimはチャンクレベルのシミュレータで,大規模のネットワークに適用する[9].また,ネットワークトポロジはAbileneを使用する.Abileneの各基幹ノードごとにそれぞれ8個の端末ノードが接続される.その結果,Abileneではノード数88,ノード間の最大ポップ数であるネットワークの直径が7となる.Abileneネットワークトポロジは下図に示す.








図11 Abileneネットワークトポロジ
シミュレータを搭載するコンピュータのオペレーティングシステムはUbuntu12.04,メモリは8GB,シミュレータはOmnet++4.1を使用する.シミュレーション各パラメータは表1のように示す.
Node number 88
Chunk size 10KB
File size 10chunks
Cache size 1000chunks
Cache Replacement Policy LRU
Ttw 10secs
Zipf exponent (a) 1
表1 シミュレーションパラメータ
評価性能として,平均キャッシュヒット率と平均パスストレッチを使用する[10,11].キャッシュヒット率はリクエストが各ノードに転送されてきた時に,求めるデータチャックがキャッシュに存在する確率である.パスストレッチとは,リクエストがヒットまで経由したポップ数をユーザとサーバの最短ポップ数で割った値の平均値である.LCE,Probcacheと提案手法ProbCache+のそれぞれの平均キャッシュヒット率と平均パスストレッチは下図に示す.図12により,コンテンツの人気度を使用するProbcache+は,パスのキャパシティが不足になると,従来のProCacheよりキャッシュヒット率が10%向上させることが分かる.また,図13により平均パスストレッチも短縮させることも分かる.災害時に,災害地を中心としてリクエスト集中するため,コンテンツの人気度を考慮されるProbCache+の効果が明らかにした.

図12 キャッシュヒット率

図13 パスストレッチ

6. 今後の課題
この研究ではCCNにおけ経路パスのキャパシティとコンテンツの人気度を組み合わせ,コンテンツそれぞれのキャッシュされる確率を算出することで,人気度高いコンテンツとそれほど高くないコンテンツをネットワーク全体でより合理的に分散させる配置手法の提案ProbCache+を行う.この手法を用いることにより,単なるコンテンツをネットワークトポロジ全体で均一に分散させるだけではなく,コンテンツ人気度も考慮する.そのため,従来のProCacheよりキャッシュヒット率の向上,パスストレッチの短縮が得られることを示した.災害時にリクエストが災害地を中心として集中する場合,提案手法はネットワークの性能の改善が期待できる.
今後の課題として,キャッシュサイズが固定ではなく,動的な場合において,ProbCache+のパフォーマンスを検討する.一方,より簡単なアルゴリズムを得られるためには,複雑な計算を削減する方法を検討する.されに,キャッシュデシジョンポリシーとキャッシュ置換ポリシーを組み合わせで,より効率的なキャッシング方式を検討する.

文 献
[1] V. Jacobson and et al., “Networking Named Content,” in CoNEXT ’09. New York, NY, USA: ACM, 2009, pp. 1–12.
[2] 北出雄麻, “CCN におけるエンコードアドレスによるコンテンツ分散配置手法とその評価,” 大阪大学基礎工学部情報科学科特別研究報告, February 2013.
[3] D. Rossi, G. Rossini, Caching performance of content centric networks under multi-path routing (and more) . Technical report, Telecom ParisTech, 2011.
[4] I. Psaras, W. Chai, G. Pavlou, Probabilistic in-network caching for information-centric networks, in: Proceedings of the 2nd edition of the ICN workshop on Information-centric networking, ACM, 2012, pp. 55-60.
[5] G. Carofiglio, M. Gallo, L. Muscariello, and D. Perino, “Modeling data transfer in content-centric networking,” in Proceedings of 23rd International Teletraffic Congress (ITC 23), pp. 111–118, Sept. 2011.
[6] G. Carofiglio, M. Gallo, and L. Muscariello, “Bandwidth and storage sharing performance in information centric networking,” in Proceedings of ACM SIGCOMM Workshop on Information-Centric Networking (ICN-2011), pp. 26–31, Aug. 2011.
[7] N. Laoutaris, H. Che, and I. Stavrakakis, “The LCD interconnection of LRU caches and its analysis,” Performance Evaluation, vol. 63, no. 7, 2006.
[8] D. Rossi and G. Rossini, “Caching performance of content centric networks under multi-path routing (and more),” Technical report, Telecom ParisTech, July 2011.
[9] Chiocchetti, Raffaele, Rossi, Dario and Rossini, Giuseppe, ccnSim: an Highly Scalable CCN Simulator . In IEEE International Conference on Communications (ICC), june 2013.
[10] G. Pavlou, N. Wang, W.Chai, I. Psaras, Internet-scale content mediation in information-centric networks, Annals of Telecommunications (2012) 1-11
G. Kamel, N. Wang, A. Beben, J. Sliwinski, J. Batalla, P. Wisniewski, W. Burakowski, W. Chai, I. Psaras, J. Araujo, et al., Final specication of mechanisms, protocols and algorithms for enhanced, Tech. rep., FP7-2010-ICT-248784-STREP (2007). 
(英) (Not available yet)
キーワード (和) コンテンツ中心ネットワーク / 災害時 / キャッシュデシジョンポリシー / キャッシュヒット率 / / / /  
(英) CCN / Disaster Time / Cache Decision Policy / Cache Hit Rate / / / /  
文献情報 信学技報, vol. 113, no. 360, NS2013-134, pp. 1-6, 2013年12月.
資料番号 NS2013-134 
発行日 2013-12-12 (NS) 
ISSN Print edition: ISSN 0913-5685    Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード NS2013-134

研究会情報
研究会 RCS NS  
開催期間 2013-12-18 - 2013-12-20 
開催地(和) 高松市文化芸術ホール 
開催地(英) Sunport Hall Takamatsu 
テーマ(和) モバイル、アドホック、ユビキタス、無線、セキュリティ、マルチアクセス、アクセスネットワーク・UserNetworkInterface、Homeネットワーク、一般 
テーマ(英) Mobile Ad-hoc Network, Ubiquitous Network, Wireless Communication, security, Multi-Access Network 
講演論文情報の詳細
申込み研究会 NS 
会議コード 2013-12-RCS-NS 
本文の言語 日本語 
タイトル(和) 災害システムのCCN応用に関する研究 
サブタイトル(和)  
タイトル(英) Study on CCN Based Disaster System 
サブタイトル(英)  
キーワード(1)(和/英) コンテンツ中心ネットワーク / CCN  
キーワード(2)(和/英) 災害時 / Disaster Time  
キーワード(3)(和/英) キャッシュデシジョンポリシー / Cache Decision Policy  
キーワード(4)(和/英) キャッシュヒット率 / Cache Hit Rate  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 余 娜 / Yo Na / ヨ ナ
第1著者 所属(和/英) 早稲田大学 (略称: 早大)
Waseda University (略称: Waseda Univ.)
第2著者 氏名(和/英/ヨミ) Arifuzzaman Mohammad / Arifuzzaman Mohammad /
第2著者 所属(和/英) 早稲田大学 (略称: 早大)
Waseda University (略称: Waseda Univ.)
第3著者 氏名(和/英/ヨミ) 余 恪平 / Keping Yu / ヨ カクヘイ
第3著者 所属(和/英) 早稲田大学 (略称: 早大)
Waseda University (略称: Waseda Univ.)
第4著者 氏名(和/英/ヨミ) 佐藤 拓朗 / Takuro Sato / サトウ タクロウ
第4著者 所属(和/英) 早稲田大学 (略称: 早大)
Waseda University (略称: Waseda Univ.)
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者 第1著者 
発表日時 2013-12-19 08:35:00 
発表時間 25分 
申込先研究会 NS 
資料番号 NS2013-134 
巻番号(vol) vol.113 
号番号(no) no.360 
ページ範囲 pp.1-6 
ページ数
発行日 2013-12-12 (NS) 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会