一種基于節(jié)點中心性近似算法的ICN協(xié)作緩存策略

羅蘭花，袁淑丹，何巧萍

(1.賀州學院人工智能學院，廣西 賀州 542899; 2.賀州學院公共基礎教學部，廣西 賀州 542899)

0 引 言

根據(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)性能。

1 相關工作

緩存機制是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é)點緩存空間。

2 節(jié)點中心性度量基本原理

對于復雜網(wǎng)絡而言，節(jié)點中心性反映了節(jié)點的價值和所需的信息處理能力。中心性是復雜網(wǎng)絡分析的核心內(nèi)容之一，然而，根據(jù)節(jié)點中心性的定義，要準確計算中心性的工作量非常大，關鍵部分是計算最短路徑長度。因此，選擇快速有效的最短路徑近似算法非常必要。本章將對節(jié)點中心性的3個度量及平均最短路徑近似算法進行分析。

2.1 度中心性

針對網(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]。

2.2 緊密中心性

緊密中心性(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)

2.3 介數(shù)中心性

介數(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é)點中心性的度量值作為評估標準。

2.4 最短路徑近似算法

文獻[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個界標點的距離。

3 基于中心性度量近似算法的緩存策略CMAA

3.1 CMAA工作原理

為了充分體現(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)

3.2 CMAA的算法實現(xiàn)

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();

4 仿真實驗

4.1 性能參數(shù)

本文實驗考慮緩存系統(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)容的平均時延。

4.2 實驗環(huán)境及參數(shù)設置

實驗環(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%。

4.3 仿真結(jié)果分析

本文以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具有更高的緩存性能，具有一定的實際意義。

5 結(jié)束語

本文提出了一種基于節(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)絡緩存性能。