內容中心網絡中一種降低自治域內內容傳輸代價的緩存策略

楊曉非 丁志鵬 張宏宇 牛翠翠 黃 勝

內容中心網絡中一種降低自治域內內容傳輸代價的緩存策略

楊曉非 丁志鵬 張宏宇 牛翠翠 黃 勝

(重慶郵電大學光纖通信技術重點實驗室 重慶 400065)

內容中心網絡(CCN)是未來互聯網中一種有前景的網絡架構。它通過網內緩存機制加強內容的傳輸減少網絡傳輸代價或提高網絡吞吐量。針對同一個自治域內的內容分布情況以及熱門內容對網絡的影響，提出一種以降低內容傳輸代價為目標的緩存機制——DCR策略。該策略能夠將熱門內容推向用戶同時降低內容的冗余度。實驗結果表明：該緩存策略能有效地降低自治域內內容的傳輸代價，提高了域內緩存命中率。

內容中心網絡 緩存機制 冗余度 內容傳輸代價 緩存命中率

0 引 言

現如今，內容數據的爆炸式增長使得內容傳輸開始成為網絡中最為關鍵的一環。因此，傳統的TCP/IP網絡開始顯露它的靈活性和可靠性等方面的缺陷。在這種情況下出現了一批關于未來互聯網體系架構的研究。這其中有UC Berkeley RAD實驗室提出的“面向數據的網絡架構”DONA(Data-Oriented Network Architecture)[1]、“發布/訂閱式互聯網路由范例”PSIRP(Publish-Subscribe Internet Routing Paradigm)[2]。內容中心網絡(CCN)[3,4],這個由施樂公司帕洛阿托研究中心的Van Jacobson等人提出的網絡架構現在已經成為了未來互聯網的研究熱點。

緩存策略是當前CCN中的一個研究熱點。在CCN中，每一個節點都包含一個內容庫用來存儲數據。CCN中的內容庫可以長時間存儲經過的數據包以便服務其他節點發來的請求。最近已經有不少文獻致力于CCN中內容存儲策略的研究。文獻[3]提出了一種叫作LCE(Leaving copies everywhere)的緩存策略，該策略中，節點存儲每個經過的數據包，該策略由于復雜度低和易用性得到了廣泛的使用。文獻[5]提出了一種叫做PCP的緩存策略，該策略主要的目標是盡量避免邊緣節點存儲冷門內容，而將熱門內容盡可能推向離用戶更近的敵方。文獻[6]中提出的ProbCache機制決定在內容傳輸路徑上依概率存儲內容。文獻[7]中的MPC機制提出當內容被請求的次數超過一個門限值時就將該內容存儲在其鄰居節點中。文獻[8]中提出的合作緩存機制是節點根據鄰居節點的內容存儲情況來決定自身存儲的內容。文獻[9]中提出了一種叫做WAVE的存儲機制，該機制為每一個內容維持了一個用來記錄該內容流行度信息的值來決定該內容需要被存儲的數據塊的數量。文獻[10]中提出了一種依概率存儲的緩存機制，該策略中節點以一定概率存儲經過的數據包，相比LCE策略降低了數據的冗余度。

然而，上述的緩存合作機制都只考慮了內容在單一路徑上傳輸時如何進行緩存，并且沒有考慮內容在自治域中時的特殊性，因此會造成網絡中的內容冗余度較高和命中率較低。全球的因特網被分成很多個自治域，不同的運營商往往在不同的自治域內，用戶請求的內容在自治域內被滿足和在自治域外被滿足有著明顯的區別。由文獻[3]可知，由于CCN網絡協議與TCP/IP協議的相似性，使得CCN可以架構在任何底層協議之上甚至是IP協議。因此，CCN可以保持現有的互聯網域內域間特征并且在現有的TCP/IP網絡之上運行CCN。因為域內的鏈路帶寬資源通常要比域間鏈路帶寬的更充裕，而且在域內獲取資源比在域外的代價更小。所以我們希望用戶發出的請求盡可能在域內被滿足。這樣，如何在域內合理地分配內容成為了一個問題。針對上述問題，本文提出一種以降低自治域內內容傳輸代價為目標的緩存策略，該策略可以有效地減少內容在自治域內傳輸的代價，同時提高內容在域內的平均命中率。

1 CCN基本原理及DCR策略

1.1 CCN基本原理

由Jacobson等人在文獻[3]中提出的內容中心網絡(CCN)的核心是以內容為主體，每個內容都被它的名字所標識，而不再關心內容所在的位置。CCN通信過程中存在兩種類型的包：興趣包和數據包。興趣包由用戶發出用來請求用戶需要的內容，數據包包含了被興趣包請求的數據。每一個CCN節點包含了以下三種結構：內容庫CS、未決請求表PIT和轉發信息庫FIB。其中，CS可以在內容被轉發到別的接口之后也長時間保存經過的內容的副本；PIT建立了一個列表用來存放每一個沒有被滿足的興趣包的信息；FIB用來記錄內容應該被發往的下一個接口信息。當節點收到一個興趣包時，會依次在CS、PIT和FIB中進行查找，若CS中沒有匹配的內容，則在PIT中查找；若PIT中有相應的條目，則將請求接口加入PIT請求接口列表中，并丟棄該興趣包，否則繼續在FIB表中查找，若找到相應條目，則將該興趣包轉發到對應的鄰居節點，同時建立相應的PIT條目；若FIB中未查找到相關條目，則丟棄該興趣包。興趣包被滿足之后，數據包嚴格按照興趣包的發送路線原路返回至用戶。

CCN的網內存儲使得它比傳統的TCP/IP網絡傳輸內容更快，但同時也帶來了一個問題，那就是，怎么樣在網絡中分配內容數據才能使網絡的性能最優。這里的最優指的是內容在自治域內的傳輸代價最小，本文中考慮內容傳輸的跳數為代價。鑒于CCN網絡中內容的請求服從特定的流行度模型，所以絕大部分的請求都發生在少數的熱門內容上，因此，我們的重點是如何減少熱門內容的傳輸代價。當一個節點接收到數據包時，它首先會檢查PIT列表中有沒有相應的條目，如果有的話就給相應條目的接口發送數據包的副本，否則的話就根據需要選擇存儲該數據包或者將其丟棄。在傳統的CCN中，默認的緩存策略是數據包經過興趣包所經過的路徑上的每一個節點時都被存儲在該節點的CS中。這樣的存儲策略簡單快捷，但是，卻會使網絡的中冗余的內容副本過多，從而導致大量的用戶請求不得不發往更遠的服務器或者域外獲取內容，使得網絡的傳輸代價過高。

考慮到上述問題，本文提出了一種基于貪婪算法的緩存策略——DCR(Delivery Cost Reduce)策略來降低內容的傳輸代價。該策略的主要思想是盡可能將更多的熱門內容保存在當前自治域中，并通過將熱門內容分布在更合理的位置降低自治域中總的內容傳輸帶價。

1.2 DCR策略

在本文中，網絡中內容的“冷熱”程度是根據內容的流行度來劃分的，內容的流行度定義為單位時間內該內容收到的請求數。也就是內容的流行度越高，該內容就越“熱門”。根據Zipf定律，絕大部分的請求往往是針對少部分熱門內容的。因此，合理的調整熱門內容在自治域中的數量和位置，可以有效地降低自治域中總的內容傳輸帶價，降低用戶獲取內容的時延。

當一個節點接收到一個熱門內容并且需要發生替換行為時，傳統的緩存策略往往是簡單地將流行度最低的內容替換掉。而如果當該內容也是熱門內容且在自治域中只有一個或很少數量的副本時，這種替換就可能使得用戶需要從域外獲取該內容，反而增大網絡的負擔和消耗。因此，在本文提出的DCR策略中，提出了將兩內容“交換”的概念來處理上述的情況。此外，每當有內容在節點中存儲時，我們讓該節點通知所有邊緣節點建立相應的FIB條目，使得用戶發出的請求的目的地址更明確，這有利于減少自治域中冗余內容副本的數量。

我們定義交換增益Gijic，表示將從ij處發出的熱門內容j到達熱門內容c所在的節點ic時，若交換j和c的位置所帶來的全局代價節省。

其中Mic和Mij分別表示從ic和ij處獲取內容c和j的邊緣節點的集合，uoicc、uoijj、uoijc和uoicj分別表示邊緣節點o從ic獲取內容c、邊緣節點o從ij獲取內容j、邊緣節點o從ij獲取內容c和邊緣節點o從ic獲取內容j的請求數，coic和coij分別表示邊緣節點o到節點ic以及邊緣節點o到節點ij的傳輸代價。當需要進行是否緩存內容的決策時，計算需要緩存的內容j和當前緩存流行度最低的熱門內容c的交換增益。若增益大于零則將兩內容進行交換，否則不進行交換。具體算法步驟如下：

第一步 任意熱門內容j到達節點，若該節點有剩余空間則存儲j，通知邊緣節點建立相應的FIB條目，算法結束，否則跳至第二步；

第二步 判斷j的流行度是否高于當前節點流行度最低的熱門內容c的流行度，若否，算法結束，否則跳至第三步；

第三步 判斷c在整個自治域內的副本數量是否大于1，若是，則用j替換c，通知邊緣節點建立和刪除相應的FIB條目，算法結束，否則跳至第四步；

第四步 計算j和c的交換增益Gijic，若Gijic>0則將j和c交換存儲位置，通知邊緣節點更新相應的FIB條目，算法結束，若Gijic<0則算法結束。

在DCR算法中，我們假設從域外獲取內容的代價遠高于從域內獲取相同內容的代價。興趣包在被邊緣節點發出時會攜帶該邊緣節點的信息，當其在某個節點或服務器被滿足時，相應的數據包從該興趣包上獲取邊緣節點的信息，同時，每個數據包會記錄其被請求的次數信息以供計算增益。每隔一段時間，數據包會將記錄的請求次數信息更新。我們利用CCN中某一時間段某內容所在節點的PIT列表中接口數目來判斷該內容在自治域中存在的數量。若某一段時間內該內容所對應的PIT列表接口數目小于邊緣節點的數目，則說明該內容的副本在自治域內不止一個，反之亦然。該算法基于分布式方式實現，能以較小的代價和較低的復雜度完成內容的分配。

2 DCR策略性能仿真

本文使用基于NS-3的仿真軟件ndnSIM[13,14]來搭建仿真平臺。仿真使用的網絡拓撲為NSFNet，如圖1所示。其中，A、B、C、D四個節點為邊緣節點，邊緣節點發出的請求如果未在域內被滿足會被發往代表域外的X節點，假設用戶發出的請求總可以在域外被滿足。每個邊緣節點依據Zipf定律以500個/秒的速率同時產生興趣包，假設內容的總數為10 000個，Zipf指數a=0.75，熱門內容占總內容數的20%，數據包更新請求信息間隔為2 s。我們比較不同緩存容量對網絡性能的影響，本文的緩存容量指的是緩存大小占總內容大小的百分比，取值范圍為1.8%～60%。

圖1 NSFNet

本文考慮的對比算法如下：(1) LCE[3]。LCE策略是目前CCN網絡中使用最廣泛的緩存策略。在LCE中，節點將經過的每個數據包都保留一份副本在其CS中，替換策略使用LRU策略。(2) 依概率存儲策略[15]，節點以一定概率存儲經過的數據包，本文中用Prob表示這種策略，存儲概率設為0.7。

本文考慮的網絡性能評價指標如下：(1) 域內緩存命中率。域內緩存命中率是指在自治域內被滿足的興趣包的數量占用戶發出的所有興趣包的總大小的比值。(2) 平均訪問時延。平均訪問時延指的是用戶發出興趣包到收到數據包所消耗的時間的均值。(3) 域內跳數節省率[15]。域內跳數節省率指的是使用緩存策略時數據包的平均響應跳數與不使用緩存策略時數據包的平均響應跳數的比值。其中，數據包的平均響應跳數指的是數據包從節點或者服務器到達用戶所經過的跳數。

圖2顯示了不同緩存容量下各緩存策略域內緩存命中率的情況?？梢钥闯?，DCR策略由于對自治域內熱門內容的全局考慮和合理分配，獲得了更高的域內命中率。相比之下，由于其余兩種策略沒有從全局考慮內容對網絡性能的影響，因此造成了命中率低下。

圖2 域內緩存命中率隨緩存容量變化曲線

圖3顯示的是不同緩存容量下各緩存策略平均訪問時延的情況。從圖中可以看出，DCR策略的平均訪問時延大大低于其他兩種緩存策略。這是因為DCR策略將用戶的請求更多地導向自治域內的資源，從而使得用戶可以在更近的地方獲取到內容，減少了用戶獲取內容的時間。而其他兩種策略因為沒有考慮內容的流行度區別，使得更多的冷門資源存在于自治域內，從而導致大量熱門內容請求需要到域外被滿足，因而增大了訪問時延。

圖3 平均訪問時延隨緩存容量變化曲線

圖4顯示的是不同緩存下各緩存策略域內跳數節省率的情況?？梢钥闯?，本文提出的DCR策略的域內跳數節省率明顯高于LCE和Pro策略，也就說明了DCR策略可以有效地減少內容在自治域中傳輸的代價。這得益于DCR策略對自治域內熱門內容的全局考慮。

圖4 域內跳數節省率隨緩存容量變化曲線

3 結 語

CCN作為未來互聯網中一種新興的網絡架構，能有效地緩解網絡擁塞狀況，提升用戶體驗，然而，它也存在著一些問題。本文將CCN中內容放入自治域內考慮，提出了一種以降低內容傳輸代價為目的的緩存策略——DCR策略。該策略將自治域內的熱門內容作為考慮對象，通過計算內容能給網絡帶來的代價增益合理分配內容的位置。仿真結果驗證了本策略的有效性。接下來的工作中，將考慮DCR策略對網絡其他性能的影響，例如網絡帶寬消耗等。

[1] Koponen T,Chawla M,Gon C B,et al.A data-oriented (andbeyond) network architecture[C]//Proceedings of the ACMSIGCOMM 2007 Conference,Kyoto,Japan,2007:181-192.

[2] European Union.Project PSIRP[OL].[2010-10-1].http://www.psirp.org.

[3] Jacobson V,Smetters D K,Thornton J D,et al.Networkingnamed content[C]//Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies,Rome,Italy,2009:1-12.

[4] Jacobson V,Smetters D K,Thornton J D,et al.Networkingnamed content[J].Communications of the ACM,2012,55(1):117-124.

[5] Wang J M,Bensaou B.Progressive caching in ccn[C]//IEEE GLOBECOM’12,Anaheim,CA,2012:2727-2732.

[6] Psaras I,Chai W K,Pavlou G.Probabilistic in-network caching for information-centric networks[C]//Proceedings of the second edition of the ICN workshop on Information-centric networking,New York:ACM,2012:55-60.

[7] Bernardini C,Silverston T,Festor O.MPC:Popularity-Based Caching Strategy for Content Centric Networks[C]//Communications(ICC),2013 IEEE International Conference on.IEEE,2013:3619-3623.

[8] Fiore M,Mininni F,Casetti C,et al.To Cache or Not To Cache?[C]//INFOCOM 2009,IEEE.IEEE,2009:235-243.

[9] Cho K,Lee M,Park K,et al.Wave:Popularity-based and collaborative in-network caching for content-oriented networks[C]//INFOCOM Workshops,2012:316-321.

[10] Psaras I,Chai W K,Pavlou G.Probabilistic in-network caching for information-centric networks[C]//Proceedings of the second edition of the ICN workshop on Information-centric networking,ser.ICN ’12.New York,NY,USA:ACM,2012:55-60.

[11] Wang Z,Crowcroft J.Quality of service routing for supporting multimedia applications[J].IEEE Journal on Selected Areas in Communications,1996,14(7):1228-1234.

[12] Kangasharju J,Roberts J,Ross K.Object replication strategies in content distribution networks[J].Computer Communications,2002,25(4):376-383.

[13] Afanasyev A,Moiseenko I,Zhang L X,et al.ndnSIM[OL].[2012].http://irl.cs.ucla.edu/ndnSIM.html.

[14] Afanasyev A,Moiseenko I,Zhang L X,et al.ndnSIM: NDN simulator for NS-3[R].California: PARC,2012.

[15] Li J,Wu H,Liu B,et al.Popularity-Driven Coordinated Caching in Named Data Networking[C]//Proceedings of the Eighth ACM/IEEE Symposium on Architectures for Networking and Communications Systems,ACM New York,2012:15-26.

A CACHING STRATEGY FOR REDUCING CONTENT DELIVERY COST OF AUTONOMOUS SYSTEM IN CONTENT CENTRIC NETWORK

Yang Xiaofei Ding Zhipeng Zhang Hongyu Niu Cuicui Huang Sheng

(KeyLabofOpticalFiberCommunicationsTechnology,ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China)

Content centric network (CCN) is a promising network architecture of future internet. It enhances the content delivery, reduces content delivery cost and improves network throughput by utilising intra-network caching mechanism. In light of the content distribution situation within same autonomous system and the influence of hot contents on networks, we proposed a caching mechanism aimed at reducing content delivery cost, i.e., delivery cost reduction (DCR) strategy. DCR strategy can push hot contents to users while reducing contents redundancy. Experimental results showed that the caching strategy proposed could effectively reduce content delivery cost within AS and improved the intra-AS hit ratio as well.

Content centric network (CCN) Caching strategy Redundancy Content delivery costs Cache hit ratio

2014-09-01。國家自然科學基金項目(61371096)；重慶市自然科學基金項目(cstc2013jcyA40052)；重慶市教委科學技術研究項目(KJ130515)。楊曉非，副教授，主研領域：電路，信號與系統。丁志鵬，碩士生。張宏宇，碩士生。牛翠翠，碩士生。黃勝，教授。

TP393

A

10.3969/j.issn.1000-386x.2016.04.029