基于ICN的未來媒體網絡緩存放置策略

許 朝 謝人超,2 張亨洋 黃 韜,2 劉 江,2 楊 磊

1 北京郵電大學 網絡與交換國家重點實驗室 北京 100876

2 北京未來網絡科技高精尖創新中心 北京 100124

3 中央電視臺 北京 100020

引言

經過半個多世紀的發展，互聯網已經成為當今社會發展與信息生活的重要基礎設施，視頻、音樂、圖片等媒體內容的獲取和分發成為當今互聯網的主要模式。然而，隨著全球數字媒體的深刻變革，媒體數據以驚人的速度快速增長，Cisco公司的統計預測數據表明，在過去五年當中，全球IP流量增長超過了4倍，并且在接下來的5年當中，全球IP流量還將會增加2倍。在2014年至2019年期間，全球的IP流量將以23%的年均復合增長率快速增長；到2019年，視頻流量將占到互聯網流量的80%[1]。網絡流量的增長速度，特別是視頻流量的增長遠遠超過了摩爾定律和路由性能提升的速度，現有的傳輸網絡已經無法滿足龐大媒體數據的高效傳輸。同時，大量新的業務形態與產業發展模式隨著網絡媒體深度融合如雨后春筍般涌起，更使得傳統服務模式和產品面臨嚴峻考驗。

隨著移動接入、普適計算、分布式信息處理、海量流媒體等新應用的發展，導致服務器負載過重，難以及時響應用戶的請求。同時，受網絡帶寬和傳輸時延的限制，用戶體驗也受到一定程度的影響，傳統TCP/IP體系結構的計算機網絡性能已經開始趨于極限，成為阻礙當今網絡中應用層發展的主要因素[2]。雖然“改良”式的發展解決了當今網絡存在的大量問題，對網絡性能的提高也起到很大作用，但其本質只是對網絡結構“修補式”的循環，使網絡結構變得越來越復雜，并同時帶來一些新的問題[3]。在這種情況下，人們試圖提出一種全新的網絡體系結構來代替TCP/IP結構，在提出的各種未來網絡體系結構方案中[4-10]，信息中心網絡(Information-Centric Networking,ICN)成為當今研究的一個熱點。

ICN是以信息為中心的網絡概念[11]，讓信息成為網絡的發起者和主導者。相比傳統網絡，數據位置對于ICN網絡而言已不再重要，用戶需要關注的只是所要獲取內容本身，而不再是網絡中的終端和所要獲取內容的具體位置；因此，在視頻等媒體數據業務爆炸式增長的背景下，本文結合奇異值分解算法(Singular Value Decomposition,SVD)算法，提出了基于ICN網絡的未來媒體網絡緩存放置算法，旨在通過提高層次節點間的協作來減少互聯網服務提供商之間的跨域傳輸，減小網絡傳輸開銷，通過降低網絡中數據的傳輸時延和提高網絡中的數據請求響應速率來優化用戶體驗。為深入分析ICN網絡緩存放置算法，本文從較為成熟的NDN網絡出發，對網絡緩存放置算法進行仿真和分析。

本文后續章節主要包括以下內容。1)主要介紹ICN緩存放置策略。2)主要介紹基于ICN的未來媒體網絡緩存放置策略的原理以及其與傳統IP網絡相比體現出的優勢。3)將對NDN中CS結構進行簡單修改，利用ndnSIM[12]對基于ICN的未來媒體網絡緩存放置策略進行仿真和分析。4)將對仿真結果和基于ICN的未來媒體網絡緩存放置策略做簡單總結。

1 緩存放置策略

和傳統的P2P、Web緩存相比，ICN網絡緩存呈現出新的特征，這些新特征主要體現在緩存透明化、緩存泛在化和緩存細粒度化[13]。ICN緩存放置問題主要研究在ICN緩存大規模和動態自生長的背景下，各節點如何篩選緩存內容，優化性能指標，提高緩存魯棒性等問題，主要包括緩存替換策略和緩存決定策略。緩存放置策略的優劣直接決定了網絡的性能優劣，優化的緩存放置策略可以大大降低網絡平均負載，降低網絡運營成本并提高用戶體驗。不止對ICN網絡，網絡緩存放置問題的研究對于云網絡、服務中心網絡等都具有普適意義。

1.1 緩存替換策略

緩存替換策略主要研究在緩存空間已滿的情況下將哪個內容替換出去的問題。目前，緩存替換策略主要有LRU(Least Recently Used)、LFU(Leave Frequently Used)、TTL(Time To Leave)和RAD(Random Replace Policy)。

LRU是根據內容到達的時間，將最新到達的內容緩存，替換最下面的內容，這種方法目前使用最多，但脫離于先驗的流行性。LFU是緩存新到達的內容，將最不流行的內容替換掉。TTL是在內容到達時設定一個緩存時間，類似于生存時長，時間一到便替換內容。RAN是隨機緩存替換，其優點是不需要查找現有緩存中是否已經存在該內容。

緩存替換策略在傳統的Web緩存中已經得到廣泛研究，詳細內容可參考文獻[14]。但ICN中的緩存要求線速執行，因此緩存替換策略應盡量簡單。從整個網絡研究內容來看，緩存替換算法并不是ICN研究的重點，ICN對緩存替換算法簡單性的要求勝于緩存替換算法之于緩存系統性能提升(如命中率)的要求[15]。文獻[16,17]的研究表明，在ICN中采用簡單的隨機替換算法基本上就能達到LRU替換算法的性能；因此，本文重點研究緩存放置策略中的緩存決定策略。

1.2 緩存決定策略

緩存決定策略主要研究在某個節點是否緩存某個內容。在集中式的管理架構中，集中管理節點可以通過全局信息來計算每個內容應該存放在哪個節點；而在分布式架構中，節點通過自身的信息來判斷是否緩存內容。鑒于NDN網絡分布式架構，本文主要研究分布式節點的緩存決定策略。

依據協同決策點的不同，分布式緩存策略又分為節點之間合作與不合作兩種方式。其中不合作方式主要包括都緩存(Leave Copy Everywhere, LCE)和下一跳緩存(Leave Copy Down, LCD)[18]。其中，LCE是NDN默認的緩存決定策略，具體方法是在所經過路徑的每個節點都緩存內容，其缺點是導致網絡中產生大量的內容冗余。LCD則是只在命中節點的下一節點緩存內容，這使得內容流行度高的內容需要請求多次才能到達邊緣節點，數據響應速率不高。

合作緩存決定策略主要是下移一跳緩存(Move Copy Down, MCD)[18]，MCD類似于LCD，也是在命中節點的下一跳緩存內容，主要區別是MCD需要刪除內容命中節點的緩存(源服務器除外)。MCD存在的主要問題是，當請求用戶來自不同的邊緣網絡時，會出現內容緩存節點的搖擺，增加網絡開銷。

結合上述三種決定策略的優缺點，我們可以從以下兩方面出發，提高緩存的整體效用。一方面，可以在邊緣緩存節點緩存流行度較高的內容，從而減小用戶下載內容的平均時延和提高網絡中資源的利用率。另一方面，可以提高整個網絡緩存系統的緩存多樣性，特別是同一自治系統內容路由器所緩存的對象的多樣性，盡量使得用戶請求由自治系統內的緩存節點予以滿足，從而降低域間操作和域間流量[15]。

為更好地適應視頻等媒體業務對于網絡緩存機制的要求，本文從緩存決定策略的角度，結合SVD算法，提出基于ICN網絡的未來媒體網絡緩存放置算法。

2 基于ICN的未來媒體網絡緩存放置策略

在傳統IP網絡下，用戶獲取內容需要從特定的主機獲取，而在視頻流量占據互聯網大部分流量的情況下，這一機制必然造成相關鏈路、特別是靠近內容源的鏈路的堵塞。同時，由于處理時延、鏈路帶寬等問題，同一主機上的內容請求也會相互影響，造成網絡利用率下降，浪費網絡資源。而ICN網絡將數據與位置相分離，內容數據分布在整個網絡當中，而非特定主機。當用戶發起數據請求之后，在網絡中查找數據，一方面減輕了內容源附近鏈路的負荷，另一方面對于合理利用帶寬、提高網絡利用率都具有重要意義。

ICN雖然解決了數據與位置綁定所帶來的問題，但當數據不在本地網絡中時，就需要進行域間操作，這必然引起較大的時延，對用戶體驗造成影響。為解決這一問題，本文結合SVD算法設計基于ICN的未來媒體網絡緩存放置算法。該算法通過判斷本地網絡請求數據與其他網絡數據的相似性來決定將緩存在本地網絡中的內容。

這里的相似性概念是從用戶的角度來看的，對于計算機而言，它只能進行計算。為了讓計算機能夠計算出網絡中內容的相似性，可以將網絡中的各個內容在不同網絡中的請求次數定義為一個M行N列的矩陣，同一內容在不同網絡的請求次數構成了一個M維向量。有了這些多維向量之后就可以利用式(1)，通過余弦相似度來判斷內容之間的相似度，其中符號“g” 表示向量間的點積，“||”表示向量的歐氏長度，即向量的模。由定義可以看出，相似度介于0到1之間，越接近1表示相似度越高。

余弦相似度判斷精度較高，但當N個內容兩兩之間的進行比較時，其復雜度為O(N2·M)，顯然不適用于大規模數據的計算；因此，我們可以先利用SVD算法對之前的矩陣進行粗略處理，然后利用余弦相似性進行精確判斷。

SVD算法的數學基礎為，對于任何行數大于或等于列數的M×N矩陣A，均可分解為M×N的列正交矩陣U、元素大于或等于零的N×N的對角矩陣∑和N×N的正交矩陣V的轉置的乘積，具體可表示為：

其中矩陣U的列稱為A的左奇異向量，矩陣V的列稱為A的右奇異向量，∑稱為A的奇異值標準型，∑的對角元素被稱為矩陣A的奇異值矩陣。其中，∑的每個對角元素非負，而且依次減小，在線性空間里，每個向量代表一個方向，所以特征值是代表該矩陣向著該特征值對應的特征向量的方向的變化權重，因此，可以取∑對角線上前k個元素為新的對角矩陣∑2，相應地，取U的前k列為U2，VT的前k行為VT2，A可近似表示為：

當k越大時，式(3)右邊與左邊越接近。

雖然SVD算法的復雜度與余弦相似度算法屬于一個量級，但由于網絡中大量低流行度內容的存在，可以利用矩陣的稀疏性大大縮短計算時間。在之后進行余弦相似度判斷時，因為去除大部分流行度較低的內容，復雜度也將遠小于O(N2·M)。兩種方法的先后使用，充分利用二者的優勢，既節省了計算時間，又獲得了較高的精確度。

基于ICN的未來媒體網絡可以采用IP與NDN混合網絡結構，核心網保持傳統的IP網絡架構，為邊緣網絡提供服務，邊緣網絡則采用NDN，作為研究ICN網絡的具體網絡。繼承IP協議對于第二層協議的寬松要求這一優點，NDN可以實施在任何的底層協議之上，甚至可以架構在IP層之上，保證了NDN網絡對傳統IP網絡的兼容性。

NDN中提出三種重要的數據結構用來實現路由轉發，這三者分別為待處理請求表(Pending Interest Table，PIT)、轉發信息庫(Forwarding Information Base，FIB)和內容存儲庫(Content Store，CS)。其中，PIT記錄未響應興趣包的內容名及其到達接口，FIB記錄當前節點到達內容提供節點的下一跳接口，CS保存路由節點的緩存內容。

NDN網絡中的通信由請求方(Consumer)驅動[12]，請求方請求數據時，首先廣播興趣包，當路由節點收到興趣包后，先對內容名進行最大匹配查詢，再依據查詢結果進行操作，興趣包一旦到達存儲所需數據的節點時，就會將相應的數據包發送到請求者。我們以NDN已有數據結構為基礎，在CS中加入新的條目“Count”，用來標記每個數據包的請求次數。Count初始化為0，每當返回一次數據，Count值加1，CS結構變為圖1。

圖1 加入Count條目的CS結構

通過CS統計每個NDN邊緣網絡中每個內容的請求次數構成Interest請求矩陣A，結構如表1所示。通過分解得到奇異向量VT，VT每行代表不同的特征，每列代表不同的數據對象，每個列向量表示每個數據對象對于各個特征所占的權重。

表1 Interest請求矩陣

根據這個結果將各個邊緣網絡請求數據中與本網絡已緩存數據相似性度最高的內容緩存在本網絡中，當用戶請求該數據時，即可快速得到響應，而不需要進行跨域操作，同時，也提高了緩存命中率，減少了網絡開銷。

3 仿真結果

本次仿真通過ndnSIM[12]模擬3個NDN網絡和核心網。每個NDN網絡包括3個user節點和1個p節點，其中user節點作為請求節點，發出數據請求。三個網絡通過Rtr節點實現通信并與IP核心網相連接。IP核心網中包括3個p節點。p緩存有數據包，用來響應來自本網絡或其它他網絡相應的數據請求。仿真拓撲如圖2所示。

圖2 仿真拓撲

本次仿真使用Packet-level trace helpers中的ndn::L3RateTracer獲得每個節點轉發的字節數和轉發包的個數等信息。表1列出了10s時間內每個網絡對各個內容發出的Interest包的個數。對Interest請求矩陣進行SVD分解后得到如表2所示的VT矩陣，取k=2，以VT第一行為橫坐標，第二行為縱坐標，得到圖3所示結果。

表2 SVD分解所得VT矩陣

圖3 SVD仿真結果

利用余弦相似性可以判斷p1與p5相似度最高，與p2、p3相似度最高的均為p6。根據該結果，每個邊緣NDN網絡可以選擇緩存與本網絡內容相似度最高的內容到本地p節點中。仿真結果給出了使用不同緩存決定策略時，3個NDN邊緣網絡中請求響應包的個數和請求命中率結果。圖4表明，在相同時間內，請求確定數量的相同內容，基于SVD算法的ICN緩存決定策略得到的數據請求響應明顯多于使用傳統的LCE、LCD和MCD策略得到的數據請求響應，即降低了請求響應時間。圖5表明，基于SVD算法的ICN緩存決定策略對提高緩存命中率有明顯改善，LCE則優于MCD和LCD。其中，MCD與LCD命中率相同，其原因是二者的區別只是在于是否刪除命中節點緩存，而二者都會在命中節點下一跳緩存內容，因此，不會影響到命中率。

圖4 請求節點響應數據

圖5 數據命中率

4 結束語

本文主要利用SVD算法，通過余弦相似度來分析不同網絡中請求內容的相似性來決定每個網絡的緩存內容，從而提高數據響應速率和網絡緩存命中率。

由仿真結果可以看出，基于SVD算法的緩存策略在響應時間和緩存命中率方面要明顯優于傳統LCE、MCD和LCD策略。由于頻率較高的請求內容都能在本網絡中得到響應，即不需要經過網絡之間的路由再去尋找數據源。所以基于SVD算法的緩存策略也起到了縮短平均請求響應時間的效果，減少了互聯網服務提供商之間的跨域傳輸和傳輸開銷，進而降低網絡中數據的傳輸時延。對提高網絡中的數據請求響應速率和優化用戶體驗都具有重要意義。

參考文獻

[1] Cisco Visual Networking Index: Forecast and Methodology: 2014–2019[EB/OL].[2016-03-12]http://www.cisco.com/c/en/us/solutions/collateral/serviceprovider/ip-ngn-ip-next-generation-network/white_paper_c11-481360.html

[2] Feldmann A. Internet Clean-Slate Design:What and Why?[J].Computer Communication Review,2007,37(3):59-64

[3] 吳超,張堯學,周悅芝,等.信息中心網絡發展研究綜述[J]. 計算機學報,2015,03:455-471

[4] Dannewitz C, Pentikousis K, Rembarz R. Scenarios and research issues for a network of information[EB/OL].[2016-01-06].https://www.researchgate.net/publication/228941601_Scenarios_and_Research_Issues_for_a_Network_of_Information

[5] Ahlgren B,D’Ambrosio M,Dannewitz C,et al.Design considerations for a network of information[C]//Proceedings of First International Workshop on Re-Architecting the Internet. Madrid: [s. n.], 2008

[6] Ohlman B, Ahlgren B, Brunner M. First NetInf architecture description, FP7-ICT-2007-1-216041-4WARD/D-6.1[R].2009

[7] Jacobson V, Smetters D K, Thornton J D. Networking named content[A].New York,NY,USA:ACM,2009.1-12

[8] L. Zhang et al. Named data networking (ndn) project[R].Technical Report NDN-0001, October 2010

[9] Lagutin D, Visala K, Tarkoma S. Publish/Subscribe for Internet:PSIRP Perspective[C]. Towards the Future Internet - Emerging Trends from European Research,2010:77-82

[10] 張行功,牛童,郭宗明.未來網絡之內容中心網絡的挑戰和應用[J].電信科學, 2013, 29(8):24-31

[11] Nelson T. Literary machines: the report on, and of,project Xanadu concerning word processing, electronic publishing, hypertext, thinkertoys, tomorrow' s intellectual revolution, and certain other topics including knowledge, education and freedom[M].Sausalito,California: Mindful Press,1981

[12] Afanasyev A, Moiseenko I, Zhang L, ndnSIM: NDN simulator for NS-3[EB/OL].[2016-01-06].http://nameddata.net/techreports.html

[13] 李軍,陳震,石希.ICN體系結構與技術研究[J].信息網絡安全,2012(4):75-80

[14] Podlipnig S, B?sz?rmenyi L. A survey of Web cache replacement strategies[J].ACM Computing Surveys,2003,35(4):374-398

[15] 張國強,李楊,林濤,等.信息中心網絡中的內置緩存技術研究[J].軟件學報,2014,25(1):154-175

[16] Eum S, Nakauchi K, Murata M, et al. CATT: Potential based routing with content caching for ICN[C]//the 2nd ICN Workshop on Information-Centric Networking.2012. 49-54

[17] Rossi D, Rossini G. Caching performance of content centric networks under multi-path routing (and more).Technical Report,Telecom ParisTech, 2011[EB/OL].[2016-01-06]http://perso.telecom-paristech.fr/～drossi/paper/rossi11ccn-techrep1.pdf

[18] Laoutaris N, Syntila S, Stavrakakis I. Meta algorithms for hierarchical web caches[C]//IEEE International Performance Computing and Communications Conference (IEEE IPCCC), Phoenix, April 15-17, 2004:445-452