基于ICN的未來媒體網(wǎng)絡緩存放置策略

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

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

2 北京未來網(wǎng)絡科技高精尖創(chuàng)新中心 北京 100124

3 中央電視臺 北京 100020

引言

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

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

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

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

1 緩存放置策略

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

1.1 緩存替換策略

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

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

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

1.2 緩存決定策略

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

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

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

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

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

2 基于ICN的未來媒體網(wǎng)絡緩存放置策略

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

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

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

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

SVD算法的數(shù)學基礎為，對于任何行數(shù)大于或等于列數(shù)的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算法的復雜度與余弦相似度算法屬于一個量級，但由于網(wǎng)絡中大量低流行度內容的存在，可以利用矩陣的稀疏性大大縮短計算時間。在之后進行余弦相似度判斷時，因為去除大部分流行度較低的內容，復雜度也將遠小于O(N2·M)。兩種方法的先后使用，充分利用二者的優(yōu)勢，既節(jié)省了計算時間，又獲得了較高的精確度。

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

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

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

圖1 加入Count條目的CS結構

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

表1 Interest請求矩陣

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

3 仿真結果

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

圖2 仿真拓撲

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

表2 SVD分解所得VT矩陣

圖3 SVD仿真結果

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

圖4 請求節(jié)點響應數(shù)據(jù)

圖5 數(shù)據(jù)命中率

4 結束語

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

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

參考文獻

[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] 吳超,張堯學,周悅芝,等.信息中心網(wǎng)絡發(fā)展研究綜述[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] 張行功,牛童,郭宗明.未來網(wǎng)絡之內容中心網(wǎng)絡的挑戰(zhàn)和應用[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].信息網(wǎng)絡安全,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] 張國強,李楊,林濤,等.信息中心網(wǎng)絡中的內置緩存技術研究[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