社團感知的ICN緩存策略

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

?

社團感知的ICN緩存策略

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

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

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

信息中心網絡；緩存；節點社團重要度；網絡編碼

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

1 SCCNC緩存策略

1.1 節點社團重要度定義

1.2 Interest包和Data包轉發機制

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

圖1 SCCNC示例

表1所示為擴展的PIT表。

表1 擴展的PIT表

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

Imax,(i?1)max>

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

算法1 Interest轉發過程 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表中提取的節點社團重要度信息Imax，沿Interest轉發路徑返回用戶。中間節點在收到Data包時，對比自己的節點社團重要度I和Data包攜帶的節點社團重要度最大值Imax，根據對比結果制定相應的緩存策略。Data包的轉發過程的偽代碼如算法2所示。

算法2 Data轉發過程 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 基于網絡編碼的緩存機制

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

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

當緩存替換發生時，假設內容是待移除的內容，若緩存的是個原始塊，則對個原始塊進行隨機網絡編碼，生成1個編碼塊，緩存該編碼塊，移除個原始塊。這樣做的好處是可以釋放?1個內容塊的緩存空間，同時保留個內容塊的信息，以響應后續 請求。

2 仿真實驗與分析

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

2) 緩存命中率。緩存命中率被定義為由緩存響應Interest的概率而不是內容服務器響應的概率，是衡量緩存性能的重要指標。緩存命中率越高，代表網絡的緩存效率越高。

5) 傳輸流量。傳輸流量被定義為從第1個用戶發送Interest 到最后1個用戶收到最后1個內容塊的整個過程中網絡傳輸的Data包數據量。

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

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

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

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

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

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

3 結論

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

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

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

[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 “less 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)；國家自然科學基金-通用技術基礎研究聯合基金資助項目(U1636118)；廣東省自然科學基金資助項目(2014A030313637)；廣東省高校優秀青年教師基金資助項目(YQ2015105)；廣東省應用型科技研發專項基金資助項目(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)

劉燕，博士，講師，從事未來網絡研究；E-mail: liuyan_sysu@163.com