羅蘭花,袁淑丹,何巧萍
(1.賀州學院人工智能學院,廣西 賀州 542899; 2.賀州學院公共基礎教學部,廣西 賀州 542899)
根據(jù)Cisco VNI預測,全球數(shù)字化轉(zhuǎn)型將對互聯(lián)網(wǎng)需求產(chǎn)生深遠影響,全球互聯(lián)網(wǎng)用戶急速增長,互聯(lián)網(wǎng)總流量在2016—2021年間將增長大約2倍,即從2016年的年均1.2 ZB(96 EB/月)增長到2021年的3.3 ZB(278 EB/月),視頻總流量占比將從2016年的73%提高到82%[1]。網(wǎng)絡應用需求逐漸向內(nèi)容獲取和信息服務演進,互聯(lián)網(wǎng)中大量視頻內(nèi)容的獲取將對內(nèi)容提供商(Content Provider, CP)(如YouTube、Bit Torrent、Netflix、百度、網(wǎng)易等)在數(shù)據(jù)高效傳輸方面帶來新的挑戰(zhàn)。為了適應互聯(lián)網(wǎng)應用模式的轉(zhuǎn)變,從根本上解決網(wǎng)絡可擴展性、移動性支持、面向內(nèi)容的安全性、數(shù)據(jù)一致性和擁塞控制等問題,研究者們提出了以信息/內(nèi)容為中心(Information Centric Networking, ICN)的網(wǎng)絡體系架構(gòu)。ICN的典型代表有Named Data Networking (NDN)[2]、Publish Subscribe Internet Routing Paradigm (PSIRP/PURSUIT)[3]、Data Oriented Network Architecture (DONA)[4]、Network of Information (NetInf)[5]、Scalable & Adaptive Internet Solutions (SAIL)[6]、Named Function Networking (NFN)[7-8]。
ICN的通信原理是基于內(nèi)容(Content)或數(shù)據(jù)(Data)的接收端驅(qū)動的內(nèi)容路由,以識別內(nèi)容取代識別終端。因此,ICN在進行路由和數(shù)據(jù)包傳送時不存在位置依賴,能有效解決移動性問題。ICN呈現(xiàn)出一系列的緩存新特征使得已有緩存技術(shù)不能完全移植到ICN。ICN默認的緩存機制采用LCE (Leave Copy Everywhere)[9]與LRU (Least Recently Used)結(jié)合的策略,即在返回路徑的每個節(jié)點均緩存數(shù)據(jù)。該算法思想簡單,易于實現(xiàn),由于本質(zhì)上沒有采用協(xié)同緩存,會導致大量緩存冗余,降低了緩存內(nèi)容多樣性。正因如此,如何高效利用緩存資源,優(yōu)化緩存性能成為ICN網(wǎng)絡的研究熱點之一。
針對上述存在的問題,本文提出將節(jié)點中心性近似度量和節(jié)點熱度相結(jié)合的ICN協(xié)作緩存策略CMAA (Centrality Metric Approximation Algorithm),將節(jié)點熱度引入最短路徑近似估計,提高了節(jié)點中心性的計算效率,從而減少網(wǎng)絡延遲。CMAA算法具有較高的命中率,同時引入緩存利用率作為緩存影響因子,避免了節(jié)點處于高頻替換狀態(tài),減少同質(zhì)化現(xiàn)象產(chǎn)生,從而改善緩存系統(tǒng)性能。
緩存機制是ICN的核心技術(shù)之一。其目的是通過網(wǎng)絡中的路由器節(jié)點緩存數(shù)據(jù)資源,使數(shù)據(jù)請求在最近的緩存副本獲取相應內(nèi)容,提高數(shù)據(jù)傳輸效率,降低網(wǎng)絡流通量以及緩解服務器的訪問壓力等,從而提高網(wǎng)絡的性能。緩存機制設計對ICN的數(shù)據(jù)分發(fā)效率具有極其重要的影響,而緩存放置策略是緩存機制設計的核心,因此,設計一個好的緩存放置策略是提高ICN緩存性能的關鍵內(nèi)容。
目前ICN緩存研究內(nèi)容主要包括2個方面:1)緩存策略的設計與實現(xiàn),包括緩存的資源分配、內(nèi)容緩存方式、緩存放置策略、緩存置換算法、協(xié)作緩存、緩存對象可用性和可靠性;2)緩存系統(tǒng)模型的建立與分析,包括緩存網(wǎng)絡拓撲模型、興趣分組到達模型、對象流行度模型、外生請求到達模型、請求關聯(lián)性模型、緩存系統(tǒng)狀態(tài)模型、緩存系統(tǒng)穩(wěn)態(tài)分析等[10]。
LCE是ICN默認的緩存策略。該方法要求數(shù)據(jù)分組返回路徑的所有節(jié)點均無差別地緩存數(shù)據(jù),因此,LCE存在緩存冗余大及緩存效率較低等問題。
LCD (Leave Copy Down)[11]的基本原理是將內(nèi)容緩存在其所在節(jié)點的下一跳節(jié)點,該方法存在到達邊緣節(jié)點速度慢、浪費節(jié)點空間和緩存內(nèi)容冗余等缺陷。MCD (Move Copy Down)[6]將緩存內(nèi)容緩存至命中節(jié)點的下游節(jié)點,該方案能有效減少緩存冗余,但存在當請求者來自不同的邊緣網(wǎng)絡時,會出現(xiàn)緩存節(jié)點搖擺現(xiàn)象,從而造成更大的網(wǎng)絡開銷。
Prob[9]以固定的概率緩存對象至數(shù)據(jù)返回路徑的所有路由節(jié)點。文獻[12]提出了Prob的改進方法ProbCache,該算法的基本原理是使用基于加權(quán)的概率緩存機制,即緩存對象的概率與請求節(jié)點的距離成反比。該方法將數(shù)據(jù)緩存到離用戶更近的緩存節(jié)點,但考慮因素單一,未實現(xiàn)協(xié)作緩存,可能引起邊緣節(jié)點競爭,以及較易出現(xiàn)同質(zhì)化現(xiàn)象。RCOne[13]在數(shù)據(jù)分組返回路徑上隨機地選擇一個節(jié)點緩存數(shù)據(jù)。對于一條跳數(shù)為n的路徑來說,該策略近似以跳數(shù)的倒數(shù)作為概率保留緩存副本。該方法易于實現(xiàn),緩存冗余度低,但是沒有使用內(nèi)容請求的分布等信息。
文獻[14]提出基于介數(shù)中心性的CLFM (Cache “Less for More”)策略,該策略通過網(wǎng)絡拓撲圖計算轉(zhuǎn)發(fā)路徑上各節(jié)點的介數(shù)中心性值,選取介數(shù)中心性值最大的節(jié)點作為緩存節(jié)點。CLFM策略沒有考慮到內(nèi)容替換頻率及同質(zhì)化現(xiàn)象,可能導致部分緩存請求無法實現(xiàn)。
為了獲取更好的緩存系統(tǒng)性能,合理利用節(jié)點中心性,協(xié)同緩存機制是行之有效的改進思路。通過協(xié)同機制的使用,其目的是讓用戶更快地獲取到所需內(nèi)容,同時減少同質(zhì)化現(xiàn)象的產(chǎn)生,充分利用節(jié)點緩存空間。
對于復雜網(wǎng)絡而言,節(jié)點中心性反映了節(jié)點的價值和所需的信息處理能力。中心性是復雜網(wǎng)絡分析的核心內(nèi)容之一,然而,根據(jù)節(jié)點中心性的定義,要準確計算中心性的工作量非常大,關鍵部分是計算最短路徑長度。因此,選擇快速有效的最短路徑近似算法非常必要。本章將對節(jié)點中心性的3個度量及平均最短路徑近似算法進行分析。
針對網(wǎng)絡連通圖G(V,E)(|V|=n,|E|=m),其中V={v1,v2,…,vn}表示G的頂點集合,E={e1,e2,…,em}表示G的邊集合,圖G的鄰接矩陣Ann=(aij)n×n,當vi和vj有相連邊時,則aij=1,否則,aij=0。
度中心性(Degree Centrality)是網(wǎng)絡分析中最常用的刻畫節(jié)點中心性(Centrality)的度量指標。度中心性通過統(tǒng)計直接相鄰邊數(shù)描述網(wǎng)絡中心性,一個節(jié)點的度越大,則越趨于網(wǎng)絡中心。其計算公式為:
(1)
其中,CD(vi)表示節(jié)點vi的度中心性。為消除網(wǎng)絡規(guī)模對度中心性的影響,可通過除以最大可能的連接數(shù)n-1進行歸一化處理,因此,度中心性的取值范圍為CD(vi)∈[0,1]。
緊密中心性(Closeness Centrality)用于描述網(wǎng)絡中某一節(jié)點與其他節(jié)點之間的緊密程度。緊密中心性定義為從某一節(jié)點出發(fā)到其它所有節(jié)點的最短路徑長度總和的倒數(shù)。其計算公式為:
(2)
其中,CC(vi)表示節(jié)點vi的緊密中心性,dG(vi,vj)表示G中節(jié)點vi到節(jié)點vj的最短路徑長度。公式(2)僅適用于G為連通圖的情況,而現(xiàn)實網(wǎng)絡可能存在多個連通塊,則會出現(xiàn)dG(vi,vj)=∞的情況,導致無法有效計算圖G的緊密中心性。為此,本文使用指數(shù)函數(shù)對公式(2)做歸一化處理,節(jié)點vi的緊密中心性計算表達式為:
(3)
介數(shù)中心性(Betweenness Centrality)描述一個節(jié)點出現(xiàn)在其他2個節(jié)點之間最短路徑的概率,用于評價該節(jié)點在整個網(wǎng)絡傳播數(shù)據(jù)的重要性。節(jié)點的介數(shù)值越大則表示在該網(wǎng)絡中的重要性越高。其計算公式為:
(4)
其中,CB(vi)表示節(jié)點vi的介數(shù)中心性,σs,t(vi)表示(s,t)節(jié)點之間經(jīng)過vi的最短路徑數(shù),σs,t表示(s,t)節(jié)點之間所有最短路徑數(shù)。
綜上可知,上述3個中心性度量均能從一定的角度衡量節(jié)點的重要程度,但是不同的中心性度量均存在一些不足和局限性,使用不同的方法對相同的網(wǎng)絡進行度量其結(jié)果不盡相同,為此,有研究者提出將3個中心性度量融合作為度量標準。文獻[15]將度中心性、緊密中心性和介數(shù)中心性作為TOPSIS多屬性決策模型的輸入,該算法有效地解決了3個中心性度量各自存在的局限性。文獻[16]中采用更為簡單的方法,將3個節(jié)點中心性度量進行加權(quán)融合作為節(jié)點重要度的度量,能夠有效折中3個中心性的差異,根據(jù)融合后的度量值作為緩存節(jié)點選擇的標準。本文采用文獻[16]簡單加權(quán)疊加的方法,計算節(jié)點中心性的度量值作為評估標準。
文獻[16]提出的將3個節(jié)點中心性度量進行加權(quán)融合的方法確實能有效地折中3個中心性的差異,但其計算量仍然非常大,這是因為緊密中心性和介數(shù)中心性的計算均基于最短路徑的識別和路徑長度的計算。而精確計算最短路徑工作量極大,為此,本文采用文獻[17]提出的基于界標節(jié)點的最短路徑近似估計,該方法能快速有效地估計出最短路徑長度。
根據(jù)圖論中最短路徑長度的定義,最短路徑長度估計可以分為跳數(shù)估計和物理距離估計2類,本文采用最短跳數(shù)估計作為最短路徑長度。
針對復雜網(wǎng)絡連通圖G(V,E)(|V|=n,|E|=m),設π(s,t)={s,u1,u2,…,ur,t}表示節(jié)點s與t之間路由長度為r的路徑,d(s,t)表示G中任意2個節(jié)點的最短路徑長度,SP(s,t)表示節(jié)點s和t所有長度為d(s,t)的最短路徑集合。在網(wǎng)絡G中選取l個界標點(Landmark)LM={u1,u2,…,ul},則任意節(jié)點v∈V到界標點的最短路徑的集合可以表示為:
?(v)={d(v,u1),d(v,u2),…,d(v,ul)}
定理1在G中任取3個節(jié)點s,u,t∈V,d(s,t)表示節(jié)點s和t的最短路徑長度,根據(jù)三角不等式,則有:
d(s,t)≤d(s,u)+d(u,t)
d(s,t)≥|d(s,u)-d(u,t)|
推論1若存在路徑π(s,t)∈SP(s,t)且u∈π(s,t),則:
d(s,t)=d(s,u)+d(u,t)
推論2若存在路徑π(s,t)∈SP(s,t)且s∈π(s,u),或π(s,u)∈SP(s,u)且t∈π(s,u),則:
d(s,t)=|d(s,u)-s(u,t)|
假定已經(jīng)得到界標點LM={u1,u2,…,ul}與網(wǎng)絡中所有節(jié)點的最短路徑,根據(jù)三角不等式可得:
其中,si表示節(jié)點s與第i個界標點的距離。
為了充分體現(xiàn)節(jié)點中心性和節(jié)點熱度對緩存性能的影響,本文設計一種基于節(jié)點中心性近似算法的緩存策略,記為CMAA緩存策略。該策略根據(jù)節(jié)點的中心性近似度量、節(jié)點熱度和緩存利用率計算轉(zhuǎn)發(fā)路徑上各節(jié)點的緩存優(yōu)先級,基本過程為先將節(jié)點緩存優(yōu)先級由高到低排序,然后按照緩存優(yōu)先級選擇若干節(jié)點作為緩存節(jié)點。本策略引入最短路徑近似算法,降低了節(jié)點中心性度量的計算復雜度,同時將節(jié)點中心性、節(jié)點熱度和節(jié)點緩存利用率三者結(jié)合計算得到節(jié)點的緩存優(yōu)先級,避免了節(jié)點處于高頻替換狀態(tài),減少同質(zhì)化現(xiàn)象產(chǎn)生,同時獲得較高的緩存命中率,提高了緩存系統(tǒng)性能。
CMAA緩存策略:假定興趣包轉(zhuǎn)發(fā)路徑上共經(jīng)過K個路由器節(jié)點,各節(jié)點的中心性度量總值為S(vi),節(jié)點的緩存空間利用率為R(vi),節(jié)點熱度值為H(vi),節(jié)點的緩存優(yōu)先級為P(vi),其計算公式為:
(5)
其中,路由器節(jié)點的中心性度量值S(vi)由度中心性、緊密中心性和介數(shù)中心性經(jīng)過歸一化處理后再按所占權(quán)重分別為α、β和γ構(gòu)成,其計算公式為:
S(vi)=αCD(vi)+βCC(vi)+γCB(vi)
(6)
CMAA緩存策略首先獲得全局網(wǎng)絡拓撲G′、各路由器節(jié)點的緩存空間利用率為R(vi)和節(jié)點熱度值為H(vi),然后分別根據(jù)式(1)、式(3)和式(4)計算得到各路由器節(jié)點的CD(vi)、CC(vi)和CB(vi),依據(jù)不同需求確定所占權(quán)重分別為α、β和γ,并根據(jù)式(6)計算得出興趣包轉(zhuǎn)發(fā)路徑上各路由器節(jié)點的中心性度量總值S(vi),再依據(jù)節(jié)點中心性值S(vi)、節(jié)點緩存空間利用率R(vi)和節(jié)點熱度值H(vi)通過式(5)計算得到各路由器節(jié)點的優(yōu)先級P(vi),最后對路徑上各路由器節(jié)點優(yōu)先級排序,并按優(yōu)先級高低選出k個節(jié)點作為緩存節(jié)點并進行內(nèi)容緩存。
當緩存空間不足時,需要將緩存內(nèi)容置換為新的內(nèi)容,目前ICN中常用的緩存置換算法有LRU (Least Recently Used)和LFU (Least Frequently Used)。本文采用LFU算法,LFU基本原理是根據(jù)數(shù)據(jù)的訪問頻率將數(shù)據(jù)依次記錄在緩存中,頻率最高的數(shù)據(jù)保留在緩存的最頂端,反之,頻率最低的數(shù)據(jù)放置于緩存最底端,當緩存空間不足時將最低端的數(shù)據(jù)替換為新內(nèi)容。其實質(zhì)是以“最近經(jīng)常訪問”的特性來預測數(shù)據(jù)將來被訪問的可能性。
CMAA緩存策略的偽代碼如算法1所示。
算法1CMAA緩存算法。
輸入:全局網(wǎng)絡拓撲結(jié)構(gòu)G′;緩存空間利用率R={R(v1),R(v2),…,R(vn)};節(jié)點熱度值H={H(v1),H(v2),…,H(vn)}。
輸出:緩存節(jié)點集CacheList()。
1) for (i=1;i≤n;i++)
2) for (j=1;j≤n;j++)
4) for (i=1;i≤n;i++) {
8)S(vi)←αCD(vi)+βCC(vi)+γCB(vi); //vi的中心性度量值 }
9) for (i=1;i≤n;i++)
11)P′(vj)←sort(P(vj)); //vi的緩存優(yōu)先級排序
12) for (j=1;j≤k;j++)
13)CacheList()←vj; //記錄優(yōu)先級高的前k個路由器節(jié)點
14)Return CacheList();
本文實驗考慮緩存系統(tǒng)3個關鍵性能指標:緩存命中率(Cache Hit Ratio, CHR)、平均接入代價(Average Access Cost, AAC)和平均請求時延(Average Request Delay, ARD)。其中,緩存命中率為某節(jié)點命中的請求數(shù)與其接收的請求數(shù)的比值;平均接入代價為用戶請求到達內(nèi)容節(jié)點的平均最短跳數(shù);平均請求時延為用戶發(fā)出請求到返回內(nèi)容的平均時延。
實驗環(huán)境。實驗平臺軟件環(huán)境基于Ubuntu12.04操作系統(tǒng),使用NDNSim[18]模擬器進行仿真實驗,采用Matlab7.0作為數(shù)據(jù)分析工具;硬件環(huán)境為:CPU Intel(R) Core(TM) 3.40 GHz,內(nèi)存6.00 GB,硬盤480 GB。
實驗參數(shù)。隨機生成節(jié)點和網(wǎng)絡拓撲,節(jié)點數(shù)取值范圍為[100,300],其默認值為100;總內(nèi)容數(shù)量為1000個,假定每個內(nèi)容為單一數(shù)據(jù)塊。用戶的請求分布服從Zipf-Mandelbrot分布[19],且用戶的請求到達符合泊松分布。用戶數(shù)量100個,節(jié)點緩存容量C指節(jié)點緩存內(nèi)容的最大數(shù)量,C的取值范圍為[10,100],其默認值為10,取緩存節(jié)點數(shù)k為節(jié)點數(shù)的1%。
本文以LCE和CLFM作為對照實驗,采用LFU緩存置換算法,中心性度量值S(vi)的計算式中的權(quán)重α、β和γ均取為1/3,即均衡看待各中心性值對網(wǎng)絡中心性的影響,以檢驗CMAA緩存策略的有效性。
4.3.1 節(jié)點緩存容量的影響
為衡量節(jié)點緩存容量對實驗的影響,考慮對緩存容量取不同值。當節(jié)點緩存容量取不同值時,LCE、CLFM和CMAA的緩存命中率如圖1所示。由圖1可以看出,3種策略的緩存命中率均隨節(jié)點緩存容量的增加而增大。其中,CMAA的緩存命中率最高,比LCE提升約25.8%,比CLFM提升約7.2%。
圖1 緩存容量對緩存命中率的影響
圖2 緩存容量對平均接入代價的影響
平均接入代價隨節(jié)點緩存容量的變化如圖2所示。由圖2可知,3種策略的平均接入代價均隨節(jié)點容量的增加而減少,這是因為緩存容量的增加使得節(jié)點緩存內(nèi)容多樣性,增加就近獲得內(nèi)容的概率。
平均請求時延隨節(jié)點緩存容量的變化如圖3所示。由圖3可知,3種策略的平均請求時延均隨節(jié)點緩存容量的增加逐漸減少,這是因為緩存容量的增加提高了獲取請求內(nèi)容的概率。此外,CMAA平均請求時延略微高于LCE和CLFM,這是因為CMAA在計算節(jié)點緩存優(yōu)先級時增加了計算量,從而增加了網(wǎng)絡平均時延。
圖3 緩存容量對平均請求時延的影響
4.3.2 用戶請求數(shù)的影響
考慮用戶請求數(shù)對實驗的影響。當用戶請求數(shù)取不同值時,LCE、CLFM和CMAA的緩存命中率如圖4所示。由圖4可知,3種策略的緩存命中率無明顯變化。
圖4 用戶請求數(shù)對緩存命中率的影響
平均接入代價隨用戶請求數(shù)的變化如圖5所示。由圖5可知,3種策略的平均接入代價無明顯變化。
圖5 用戶請求數(shù)對平均接入代價的影響
平均請求時延隨用戶請求數(shù)的變化如圖6所示。由圖6可知,3種策略的平均請求時延均隨用戶請求數(shù)目的增加而增大。
圖6 用戶請求數(shù)對平均請求時延的影響
通過實驗可以看出,當節(jié)點緩存容量和用戶請求數(shù)變化時,CMAA在緩存命中率、平均接入代價2個性能指標上均優(yōu)于LCE和CLFM,平均請求時延略微高于LCE和CLFM。CMAA使用緩存利用率作為緩存影響因子,有效地利用了緩存空間。相對于緩存機制LCE和CLFM,CMAA具有更高的緩存性能,具有一定的實際意義。
本文提出了一種基于節(jié)點中心性近似算法的協(xié)作緩存策略CMAA。CMAA利用最短路徑近似估計提高節(jié)點中心性的計算效率,將節(jié)點中心性近似度量加權(quán)融合值、節(jié)點熱度和緩存利用率三者作為緩存影響因子,計算得出興趣包轉(zhuǎn)發(fā)路徑各節(jié)點的緩存優(yōu)先級。在計算量略微增加的前提下,在緩存命中率與平均請求跳數(shù)方面,該策略的性能均優(yōu)于LCE和CLFM策略,在平均請求時延方面CMAA的時延也只是略長一些。下一步將在本文的研究基礎上,結(jié)合ICN網(wǎng)絡數(shù)據(jù)需求的多樣性[20-21],分析當前邊緣緩存策略存在的關鍵問題,研究結(jié)合用戶數(shù)據(jù)需求的邊緣緩存策略[22],進一步優(yōu)化網(wǎng)絡緩存性能。