蔡君，劉燕，羅建楨，余順爭，吳曉萍

?

社團感知的ICN緩存策略

蔡君1，劉燕1，羅建楨1，余順爭2，吳曉萍1

(1. 廣東技術(shù)師范學院 電子與信息學院，廣東 廣州，510665；2. 中山大學 數(shù)據(jù)科學與計算機學院，廣東 廣州，510006)

為了使以信息為中心的網(wǎng)絡(luò)緩存內(nèi)容在空間和時間上分布更合理，提出一種社團感知的緩存策略(SCCNC)；以社團為單位，社團重要度高的節(jié)點緩存原始塊，其他節(jié)點緩存編碼塊，在不增加緩存空間的條件下，提高緩存命中率和緩存多樣性。研究結(jié)果表明：SCCNC策略與其他3種策略相比，能更好地提升包括緩存命中率和傳輸流量等緩存性能。

信息中心網(wǎng)絡(luò)；緩存；節(jié)點社團重要度；網(wǎng)絡(luò)編碼

隨著新應(yīng)用的不斷涌現(xiàn)，流量產(chǎn)生和傳輸?shù)姆绞揭矊l(fā)生根本性變換，其中大部分流量來源于用戶驅(qū)動的內(nèi)容獲取類應(yīng)用，這使得當前基于端到端通信的TCP/IP網(wǎng)絡(luò)架構(gòu)遇到前所未有的挑戰(zhàn)。為了適應(yīng)用戶和應(yīng)用的需求，增強互聯(lián)網(wǎng)架構(gòu)的移動性、安全性和可擴展性，國內(nèi)外研究者提出了一系列以信息或內(nèi)容為中心的全新網(wǎng)絡(luò)體系架構(gòu)[1?4]，這些架構(gòu)統(tǒng)稱為以信息為中心的網(wǎng)絡(luò)(information-centric networking，ICN)[5]。為緩解網(wǎng)絡(luò)流量快速增長對網(wǎng)絡(luò)帶寬造成的巨大壓力，ICN通過為全網(wǎng)節(jié)點增加緩存功能，讓內(nèi)容距離用戶更近，減少網(wǎng)絡(luò)流量。緩存策略決定了內(nèi)容在網(wǎng)絡(luò)中的時空分布，影響網(wǎng)絡(luò)的流量行為。ICN中原始緩存策略是LCE(leave copy everywhere)，即網(wǎng)絡(luò)中的每個節(jié)點都緩存收到的內(nèi)容，這會造成極大的緩存冗余。為此，國內(nèi)外研究學者提出了多種緩存機 制[6?12]?，F(xiàn)有的緩存機制主要存在以下問題：在緩存位置上，大多從全局角度出發(fā)，而緩存的目的是為了滿足局部用戶的需求；在替換策略上，每個節(jié)點采用相同的替換策略，導(dǎo)致緩存內(nèi)容同質(zhì)化。近年來，不少研究者認為將網(wǎng)絡(luò)編碼引入ICN可以提升網(wǎng)絡(luò)性 能[13?18]。然而，由于ICN的網(wǎng)內(nèi)緩存機制，同一個編碼塊有可能會被轉(zhuǎn)發(fā)路徑上的多個節(jié)點緩存；相同或是線性相關(guān)的編碼塊有可能會響應(yīng)給同一個用戶，造成用戶收到線性相關(guān)的編碼塊無法解碼的情況。有研究表明[19]，Internet網(wǎng)絡(luò)拓撲結(jié)構(gòu)呈現(xiàn)社團特性，在同一社團中，節(jié)點社團重要度大的節(jié)點不僅易被社團內(nèi)的節(jié)點訪問，也易被社團外的節(jié)點訪問。為此，本文作者提出社團感知的緩存與緩存替換策略(SCCNC)，以不同流行度的內(nèi)容在網(wǎng)絡(luò)中分布更合理。在SCCNC中，把原始內(nèi)容塊緩存在其經(jīng)過的各社團內(nèi)節(jié)點社團重要度最大的節(jié)點上，編碼塊緩存在節(jié)點社團重要度較低的節(jié)點上。同時，本文作者提出用編碼代替移除的緩存替換策略，在不增加節(jié)點緩存空間的條件下，提升緩存內(nèi)容多樣性和緩存命中率。

1 SCCNC緩存策略

1.1 節(jié)點社團重要度定義

1.2 Interest包和Data包轉(zhuǎn)發(fā)機制

在SCCNC中，Interest記錄其轉(zhuǎn)發(fā)路徑上的每個社團中節(jié)點社團重要度的最大值，即{1max,2max, …,Imax}，其中Imax表示Interest轉(zhuǎn)發(fā)路徑上第個社團中節(jié)點重要度的最大值。當Data沿Interest轉(zhuǎn)發(fā)路徑返回用戶時，中間節(jié)點通過對比自己的節(jié)點重要度I及Data攜帶的該社團的節(jié)點重要度最大值Imax，制定對應(yīng)的緩存方案。本文作者設(shè)計了Interest合并機制，用于合并節(jié)點收到的多個Interest，目的是減少Interest包和Data包的通信開銷。當節(jié)點N收到Interest時，將自己的節(jié)點重要度I與Interest中攜帶的當前社團的重要度最大值Imax進行對比，若I＞Imax，則令Imax=I。當Interest被轉(zhuǎn)發(fā)到1個新的社團時，遇到的第1個節(jié)點N1(記為FirstNode)，記錄下游社團的節(jié)點重要度最大值，即(i?1)max。這樣Interest只需攜帶當前社團的節(jié)點重要度最大值，以減少Interest的通信開銷。SCCNC示例如圖1所示。由圖1可知：當社團2中的節(jié)點21收到Interest(,1,4)時，用自己的節(jié)點社團重要度21替換Interest中節(jié)點社團重要度最大值4，然后將新的Interest即Interest(,1,21)轉(zhuǎn)發(fā)給上游節(jié)點，同時新建1條PIT(pending interest table)條目記錄Interest(,1,4)。

圖1 SCCNC示例

表1所示為擴展的PIT表。

表1 擴展的PIT表

當節(jié)點N從接口收到Interest時，首先檢查其PIT表。

Imax,(i?1)max>

其中：“ContentName”為內(nèi)容名；“ClunkID”為內(nèi)容塊的名字；“Faces”為收到Interest的接口號；“Imax”為Interest轉(zhuǎn)發(fā)路徑上當前社團c的節(jié)點重要度的最大值；“(i?1)max”為Interest轉(zhuǎn)發(fā)路徑上當前社團c的下游社團(i?1)的節(jié)點重要度最大值，只有當前社團c中的FirstNode記錄(i?1)max。若PIT中已有對應(yīng)的表項，則將新到的Interest與其合并，同時丟棄該Interest；否則，新建1條PIT表項。Interest的轉(zhuǎn)發(fā)過程如算法1所示。

算法1 Interest轉(zhuǎn)發(fā)過程 Initialize Ii=0; foreach node Njreceiving Interest from face k do if cache hit then send Data Dp(Ii); else ifPIT exists then add face k into face list; ifnode Nj- is the FirstNode then add Ii into I(i?1)max, let Iimax=0; else add Ii into Iimax; end if else ifIj＞Iithen let Ii=Ij; end if end if establish a new PIT entry for Interest, let Iimax=Ii, I(i?1)max=0; forward Interest to next hop; end if end for

在SCCNC中，Data包攜帶從Interest或PIT表中提取的節(jié)點社團重要度信息Imax，沿Interest轉(zhuǎn)發(fā)路徑返回用戶。中間節(jié)點在收到Data包時，對比自己的節(jié)點社團重要度I和Data包攜帶的節(jié)點社團重要度最大值Imax，根據(jù)對比結(jié)果制定相應(yīng)的緩存策略。Data包的轉(zhuǎn)發(fā)過程的偽代碼如算法2所示。

算法2 Data轉(zhuǎn)發(fā)過程 When an Data (Iimax) arrived for each node Njdo cache Data according to Algorithm 3; check PIT table; foreach face k in face list of PIT table do ifIik≠0 then Iimax=max{Iimax, Iik}; else Iimax=I(i?1)max; end if send Data out of face k; end for end for

1.3 基于網(wǎng)絡(luò)編碼的緩存機制

以社團為單位，在同一社團內(nèi)，根據(jù)Interest轉(zhuǎn)發(fā)路徑上各節(jié)點的社團重要度制定不同的緩存策略：重要度最高的節(jié)點緩存原始內(nèi)容塊，這是因為重要度高的節(jié)點更容易被其他節(jié)點訪問；重要度低的節(jié)點緩存編碼塊，以節(jié)省緩存空間，提高緩存多樣性。當節(jié)點N收到Data包，且Data包中攜帶的是內(nèi)容的原始內(nèi)容塊時，將自己的節(jié)點重要度I與Data中攜帶的當前社團的重要度最大值Imax進行對比，若I=Imax，則將該內(nèi)容塊存儲到本地緩存中；否則，查看本地緩存CS(content store)中是否有內(nèi)容的內(nèi)容塊′，若存在，則對和′進行隨機網(wǎng)絡(luò)編碼，生成新的編碼塊″，并用″替換′。將網(wǎng)絡(luò)編碼應(yīng)用到緩存中，1個編碼塊包含多個內(nèi)容塊的信息，可以響應(yīng)多個內(nèi)容塊的請求。該緩存機制實現(xiàn)了緩存在網(wǎng)絡(luò)空間上的合理分布，減少了網(wǎng)絡(luò)延遲，提高網(wǎng)絡(luò)的傳輸效率。緩存機制的偽代碼如算法3所示。

算法3 SCCNC緩存策略 When an Data (Iimax) arrived if Data is an original block then if Ij=Iimaxthen cache original block into ContentStore; else ifcache exist then encoded original block with other coded blocks in ContentStore; end if end if end if

1.4 基于網(wǎng)絡(luò)編碼的緩存替換策略

在SCCNC中，以社團為單位，同一社團內(nèi)根據(jù)各節(jié)點的節(jié)點社團重要度不同，執(zhí)行不同的緩存替換策略。節(jié)點社團重要度大的節(jié)點，流行度低的緩存內(nèi)容被替換的概率大；而節(jié)點社團重要度小的節(jié)點，流行度高的緩存內(nèi)容被替換的概率大，這樣可以實現(xiàn)緩存在時間和空間上的合理分布。

當緩存替換發(fā)生時，假設(shè)內(nèi)容是待移除的內(nèi)容，若緩存的是個原始塊，則對個原始塊進行隨機網(wǎng)絡(luò)編碼，生成1個編碼塊，緩存該編碼塊，移除個原始塊。這樣做的好處是可以釋放?1個內(nèi)容塊的緩存空間，同時保留個內(nèi)容塊的信息，以響應(yīng)后續(xù) 請求。

2 仿真實驗與分析

1) 平均下載時間。平均下載時間是指平均每個用戶從發(fā)送第1個Interest到該用戶接收最后1個內(nèi)容塊所需的時間。

2) 緩存命中率。緩存命中率被定義為由緩存響應(yīng)Interest的概率而不是內(nèi)容服務(wù)器響應(yīng)的概率，是衡量緩存性能的重要指標。緩存命中率越高，代表網(wǎng)絡(luò)的緩存效率越高。

5) 傳輸流量。傳輸流量被定義為從第1個用戶發(fā)送Interest 到最后1個用戶收到最后1個內(nèi)容塊的整個過程中網(wǎng)絡(luò)傳輸?shù)腄ata包數(shù)據(jù)量。

(a) 平均下載時間隨Zipf參數(shù)的變化；(b) 平均下載時間隨用戶請求數(shù)量的變化

圖6所示為4種緩存方案的跳數(shù)減少率。由圖6可知：SCCNC在跳數(shù)減少率方面比其他緩存方案具有更佳的性能表現(xiàn)。其原因是，SCCNC中各節(jié)點根據(jù)其節(jié)點重要度做出不同的緩存替換決策。在緩存耗盡時，利用編碼代替移除的方法，釋放緩存空間，同時保留多個內(nèi)容塊信息。由此可見，本文作者提出的基于節(jié)點社團重要度和網(wǎng)絡(luò)編碼的緩存替換策略使不同流行度的內(nèi)容在時間和空間的分布更合理。

(a) 緩存命中率隨Zipf參數(shù)的變化；(b) 緩存命中率隨用戶請求數(shù)量的變化

1—SCCNC；2—NC-CCN；3—CC；4—LCD。

(a) 傳輸流量隨Zipf參數(shù)的變化；(b) 傳輸流量隨用戶請求數(shù)量的變化

1—SCCNC；2—NC-CCN；3—CC；4—LCD。

3 結(jié)論

1) 提出一種社團感知的ICN緩存策略(SCCNC)，具有不同節(jié)點社團重要度的節(jié)點采取不同的緩存決策和緩存替換策略，使緩存內(nèi)容在時間和空間分布上更加合理。

2) 將網(wǎng)絡(luò)編碼引入緩存決策和緩存替換策略，在不增加緩存空間的情況下，提高緩存命中率和緩存多樣性。

3) 在多種實驗條件下對SCCNC策略進行仿真驗證。與其他3種緩存策略相比，該策略能更好地提升包括緩存命中率和跳數(shù)減少率等在內(nèi)的網(wǎng)絡(luò)緩存 性能。

[1] AHLGREN B, DANNEWITZ C, IMBRENDA C, et al. Second NetInf architecture description[EB/OL]. [2010?01?14]. http:// www.4ward-project.eu/

[2] VISALAK, LAGUTIN D, TARKOMA S. Lanes: an inter- domain data-oriented routing architecture[C]// Proceedings of the 2009 Workshop on Re-architecting the Internet. Rome, Italy: ACM, 2009: 55?60.

[3] JACOBSON V, SMETTERS D K, THORNTON J D, et al. Networking named content[C]// Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies. Rome, Italy: ACM, 2009: 1?12.

[4] KOPONEN T, CHAWLA M, CHUN B G, et al. A data-oriented (and beyond) network architecture[C]// SIGCOMM Computer Communication Review. Kyoto, Japan: ACM, 2007: 181?192.

[5] AHLGREN B, DANNEWITZ C, IMBRENDA C, et al. A survey of information-centric networking[J]. IEEE Communications Magazine, 2012, 50(7): 26?36.

[6] LI Zhe, SIMON G. Time-shifted tv in content centric networks: the case for cooperative in-network caching[C]// IEEE International Conference on Communications (ICC). Kyoto, Japan: IEEE, 2011: 1?6.

[7] SAINO L, PSARAS I, PAVLOU G. Hash-routing schemes for information centric networking[C]// Proceedings of the 3rd ACM SIGCOMM workshop on Information-Centric Networking. Hong Kong, China: ACM, 2013: 27?32

[8] WANG Sen, BI Jun, WU Jianping, et al. CPHR: in-network caching for information-centric networking with partitioning and hash-routing[J]. IEEE/ACM Transactions on Networking, 2016, 24(5): 2742?2755.

[9] PSARAS I, WEI K C, PAVLOU G. Probabilistic in-network caching for information-centric networks[C]// Proceedings of the Second Edition of the ICN Workshop on Information-Centric Networking. Helsinki, Finland: ACM, 2012: 55?60.

[10] CHAI W K, HE D, PSARAS I, et al. Cache “l(fā)ess for more” in information-centric networks (extended version)[J]. Computer Communications, 2013, 36(7): 758?770.

[11] LIM S H, KO Y B, JUNG G H, et al. Inter-chunk popularity- based edge-first caching in content-centric networking[J]. IEEE Communications Letters, 2014, 18(8): 1331?1334.

[12] CHO K, LEE M, PARK K, et al. Wave: Popularity-based and collaborative in-network caching for content-oriented networks[C]// IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS).Orlando, FL, USA: IEEE, 2012: 316?321.

[13] WANG Jin, REN Jing, LU Kejie, et al. An optimal cache management framework for information-centric networks with network coding[C]// 2014 IFIP Networking Conference. Trondheim, Norway: IEEE, 2014: 1?9.

[14] WANG Jin, REN Jing, LU Kejie, et al. A minimum cost cache management framework for information centric networks with network coding[J]. Computer Networks, 2016, 110: 1?17.

[15] LLORCA J, TULINO A M, GUAN K, et al. Network-coded caching-aided multicast for efficient content delivery[C]// IEEE International Conference on Communications (ICC). Budapest, Hungary: IEEE, 2013: 3557?3562.

[16] ZHANG Guoqiang, XU Ziqu. Combing CCN with network coding: an architectural perspective[J]. Computer Networks, 2016, 94: 219?230.

[17] WU Qinghua, LI Zhenyu, XIE Gaogang. CodingCache: multipath-aware CCN cache with network coding[C]// Proceedings of the 3rd ACM SIGCOMM Workshop on Information-Centric Networking. Hong Kong, China: ACM, 2013: 41?42.

[18] LIU Yan, YU Shunzheng. Network coding-based multisource content delivery in content centric networking[J]. Journal of Network and Computer Applications, 2016, 64: 167?175.

[19] ERIKSEN K A, SIMONSEN I, MASLOV S, et al. Modularity and extreme edges of the internet[J]. Physical Review Letters, 2003, 90(14): 148701?148704.

[20] CHAUHAN S, GIRVAN M, OTT E. Spectral properties of networks with community structure[J]. Physical Review E, 2009, 80(5): 056114?056123.

[21] WANG Yang, DI Zengru, FAN Ying. Identifying and characterizing nodes important to community structure using the spectrum of the graph[J]. PloS One, 2011, 6(11): e27418

[22] MEDINA A, LAKHINA A, MATTA I, et al. BRITE: an approach to universal topology generation[C]// Proceedings. Ninth International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems. Cincinnati, USA: IEEE, 2001: 346?353.

[23] MEDINA A, MATTA I, BYERS J. On the origin of power laws in Internet topologies[J]. ACM SIGCOMM Computer Communication Review, 2000, 30(2): 18?28.

[24] LAOUTARIS N, CHE Hao, STAVRAKAKIS I. The LCD interconnection of LRU caches and its analysis[J]. Performance Evaluation, 2006, 63(7): 609?634.

(編輯 伍錦花)

Social community-aware caching strategy in information-centric networking

CAI Jun1, LIU Yan1, LUO Jianzhen1, YU Shunzheng2, WU Xiaoping1

(1. School of Electronic and Information, Guangdong Polytechnic Normal University, Guangzhou 510665, China;2. School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510006, China)

In order to make content cached more reasonable in temporal and spatial distribution in information-centric networking(ICN), a social community-aware caching strategy (SCCNC) was proposed. For each community, original blocks were cached by nodes with more importance to community, and coded blocks were cached by other nodes. Thus, cache diversity and cache hit rate were enhanced without increasing cache capacity. The results show that the proposed scheme achieves better cache performance than other three schemes in terms of cache hit rate and traffic etc.

information centric networking; caching; node importance to community; network coding

10.11817/j.issn.1672-7207.2018.05.016

TN915.9

A

1672?7207(2018)05?1141?07

2017?05?19；

2017?06?29

國家自然科學基金資助項目(61571141)；國家自然科學基金-通用技術(shù)基礎(chǔ)研究聯(lián)合基金資助項目(U1636118)；廣東省自然科學基金資助項目(2014A030313637)；廣東省高校優(yōu)秀青年教師基金資助項目(YQ2015105)；廣東省應(yīng)用型科技研發(fā)專項基金資助項目(2015B010131017) (Project(61571141) supported by the National Natural Science Foundation of China; Project(U1636118) supported by the National Natural Science Foundation of China?General Technical Fundamental Research Joint Foundation; Project(2014A030313637) supported by the Natural Science Foundation of Guangdong Province; Project(YQ2015105) supported by the Science Foundation for Excellent Young Teachers of Universities in Guangdong Province; Project(2015B010131017) supported by the Guangdong Provincial Application-oriented Technical Research and Development Special Fund)

劉燕，博士，講師，從事未來網(wǎng)絡(luò)研究；E-mail: liuyan_sysu@163.com