陳香伊， 王興偉， 李 婕， 易 波， 黃 敏

(1.東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院 遼寧 沈陽(yáng) 110169； 2.東北大學(xué) 信息科學(xué)與工程學(xué)院 遼寧 沈陽(yáng) 110819)

0 引言

隨著互聯(lián)網(wǎng)數(shù)據(jù)的快速增長(zhǎng)和網(wǎng)絡(luò)應(yīng)用的日趨豐富，用戶(hù)需求逐漸從主機(jī)之間的通信演進(jìn)為主機(jī)對(duì)網(wǎng)絡(luò)信息的重復(fù)訪(fǎng)問(wèn)[1-2].與傳統(tǒng)網(wǎng)絡(luò)架構(gòu)中以IP地址進(jìn)行路由的方式不同，信息中心網(wǎng)絡(luò)(information-centric networking，ICN)[3-4]通過(guò)唯一的內(nèi)容名稱(chēng)對(duì)用戶(hù)請(qǐng)求進(jìn)行路由，且每個(gè)節(jié)點(diǎn)除了具有處理、轉(zhuǎn)發(fā)的功能之外，還具有存儲(chǔ)的功能[5].網(wǎng)內(nèi)緩存作為ICN最大特點(diǎn)之一[6-7]，在提高用戶(hù)服務(wù)質(zhì)量、減少用戶(hù)訪(fǎng)問(wèn)時(shí)延、減輕服務(wù)器負(fù)載上功不可沒(méi)[8].ICN緩存領(lǐng)域中很多關(guān)鍵技術(shù)已有了階段性的創(chuàng)新，但仍值得深入分析和研究[3].

在ICN眾多研究項(xiàng)目中，最具代表性且最有發(fā)展前景的范例當(dāng)屬命名數(shù)據(jù)網(wǎng)絡(luò)(named data networking，NDN)項(xiàng)目[9-10].文獻(xiàn)[11]為了充分利用ICN的內(nèi)置緩存，提出了一種基于內(nèi)容空間分區(qū)和哈希路由的緩存機(jī)制，將內(nèi)容緩存在指定的劃分區(qū)域中，能夠解決哈希路由引起的路徑拉伸問(wèn)題.文獻(xiàn)[12]提出了一種新型智能資源管理系統(tǒng)，旨在分析請(qǐng)求模式，充分利用通用緩存內(nèi)容.該系統(tǒng)能夠根據(jù)用戶(hù)需求變化實(shí)時(shí)高效地進(jìn)行緩存資源分配.文獻(xiàn)[13]通過(guò)在轉(zhuǎn)發(fā)信息庫(kù)中添加路由緩存，包括原子緩存和即時(shí)緩存，來(lái)緩解轉(zhuǎn)發(fā)信息庫(kù)的爆炸問(wèn)題.目前國(guó)內(nèi)外學(xué)者在ICN體系結(jié)構(gòu)、路由算法、緩存決策等方面已經(jīng)取得了一定的成果，但是卻鮮有針對(duì)緩存容量分配機(jī)制的研究.

ICN緩存容量分配面臨著巨大的緩存對(duì)象與有限的緩存空間之間的矛盾[14].絕大多數(shù)的ICN中都默認(rèn)均勻部署路由器(即緩存容量相同).考慮到節(jié)點(diǎn)位置、網(wǎng)內(nèi)流量分布以及用戶(hù)請(qǐng)求特征不同，從根本上導(dǎo)致了節(jié)點(diǎn)負(fù)載不均衡.因此，如何將有限的總緩存容量適當(dāng)?shù)夭渴鸬礁P(guān)鍵的位置，以平衡節(jié)點(diǎn)負(fù)載并提高緩存利用率尤為關(guān)鍵.

針對(duì)上述問(wèn)題，本文在互聯(lián)網(wǎng)主干網(wǎng)絡(luò)的ICN網(wǎng)絡(luò)架構(gòu)下，分別從用戶(hù)角度和節(jié)點(diǎn)角度對(duì)全局流量分布進(jìn)行分析.首先分析網(wǎng)絡(luò)拓?fù)鋵傩砸约傲髁刻卣餍畔?，然后基于分析結(jié)果對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行聚類(lèi)劃分，并重新分配節(jié)點(diǎn)容量，旨在將有限的總緩存容量以最優(yōu)的方式合理地分配給各節(jié)點(diǎn)，從而實(shí)現(xiàn)網(wǎng)絡(luò)的負(fù)載均衡.

1 網(wǎng)絡(luò)數(shù)據(jù)模型

1.1 拓?fù)湫畔?/h3>

網(wǎng)絡(luò)拓?fù)渲械墓?jié)點(diǎn)位置從根本上影響著該節(jié)點(diǎn)處理興趣請(qǐng)求的概率，即位于網(wǎng)絡(luò)中相對(duì)“樞紐”位置的節(jié)點(diǎn)可能需要處理更多的請(qǐng)求.因此，基于圖論基礎(chǔ)，選取了節(jié)點(diǎn)度數(shù)中心性C_d、節(jié)點(diǎn)介數(shù)中心性C_b、節(jié)點(diǎn)緊密中心性C_c3個(gè)中心性指標(biāo)作為網(wǎng)絡(luò)拓?fù)鋵傩詠?lái)區(qū)分節(jié)點(diǎn)的重要程度.

1.2 流量特征信息

流量特征信息能夠很好地反映網(wǎng)絡(luò)流量的分布情況，為區(qū)分節(jié)點(diǎn)的重要程度，本文從節(jié)點(diǎn)負(fù)載和用戶(hù)偏好兩方面共選取5個(gè)指標(biāo)作為流量特征信息屬性.在節(jié)點(diǎn)負(fù)載方面，選取接收興趣包個(gè)數(shù)Rec_I、響應(yīng)請(qǐng)求次數(shù)Res_I以及內(nèi)容替換次數(shù)Rep_C3個(gè)指標(biāo).在用戶(hù)偏好方面，選取興趣聚合率Aggr和興趣影響度Impact兩個(gè)指標(biāo).其中，節(jié)點(diǎn)負(fù)載方面的3個(gè)指標(biāo)可以通過(guò)采樣單位時(shí)間段內(nèi)的測(cè)量值累加統(tǒng)計(jì)得出.下面給出本文對(duì)興趣聚合率和興趣影響度的定義.

1.3 信息整合模型

本文將提出的3個(gè)拓?fù)鋮?shù)和5個(gè)流量信息參數(shù)作為評(píng)價(jià)節(jié)點(diǎn)重要程度的指標(biāo).使用xi(t)表示，在單位取樣時(shí)間段T內(nèi)，節(jié)點(diǎn)vi收集到的流量特征信息的數(shù)據(jù)，如公式(1)，

xi(T)={Rec_Ii(T),Res_Ii(T),Rep_Ci(T),Aggri(T),Impacti(T)}，

(1)

其中：xi(T)是五維數(shù)據(jù)，簡(jiǎn)寫(xiě)為xi.單獨(dú)收集一個(gè)時(shí)間段內(nèi)的流量信息不能全面反映網(wǎng)內(nèi)流量的變化情況，因此，總共需要選取T′個(gè)采樣時(shí)間段進(jìn)行流量信息的收集.用Xi表示在T′個(gè)采樣時(shí)間段內(nèi)節(jié)點(diǎn)vi收集到的數(shù)據(jù)集為

Xi={xi(T1),xi(T2),…,xi(T′T),C_di,C_bi,C_ci},i∈[0,n).

(2)

結(jié)合公式(1)，可將公式(2)中的Xi展開(kāi)

Xi={Rec_Ii(T1),Res_Ii(T1),Rep_Ci(T1),Aggri(T1),Impacti(T1),…,Rec_Ii(T′T),Res_Ii(T′T),

Rep_Ci(T′T),Aggri(T′T),Impacti(T′T),C_di,C_bi,C_ci}，

其中：Xi是(5T′+3)維的數(shù)據(jù).考慮到拓?fù)渲泄灿衝個(gè)節(jié)點(diǎn)，因此，本文收集的數(shù)據(jù)集為n個(gè)(5T′+3)維的數(shù)據(jù).

2 緩存容量分配機(jī)制

2.1 基于改進(jìn)t-SNE算法的數(shù)據(jù)集處理

本文所收集的數(shù)據(jù)呈現(xiàn)高維特征，且對(duì)于每個(gè)節(jié)點(diǎn)而言高維數(shù)據(jù)之間存在數(shù)據(jù)冗余、信息重疊的問(wèn)題.本文將使用改進(jìn)的t-SNE算法[15]對(duì)原數(shù)據(jù)進(jìn)行降維，并通過(guò)VP樹(shù)(vantage point tree)[16]構(gòu)建K-近鄰.在高維空間中，已知xi和xj為任意的兩個(gè)數(shù)據(jù)點(diǎn)，xk為非xi的數(shù)據(jù)點(diǎn)，Neii為xi鄰居集合，可通過(guò)對(duì)稱(chēng)化兩個(gè)條件概率分布得到點(diǎn)對(duì)相似性的聯(lián)合概率分布pij.而在本文收集的高維數(shù)據(jù)點(diǎn)中，兩個(gè)相距較遠(yuǎn)的數(shù)據(jù)點(diǎn)的相似性概率pij非常小，因此取條件概率作為pij的近似.基于此，高維空間中數(shù)據(jù)點(diǎn)的點(diǎn)對(duì)相似性可定義為

(3)

高維數(shù)據(jù)是基于流形的[17]，在高維空間中如果直接使用歐式距離會(huì)存在誤差，因此本文將以測(cè)地線(xiàn)距離代替歐式距離.但是，高維數(shù)據(jù)中的真實(shí)測(cè)地線(xiàn)距離難以獲得.考慮到每個(gè)輸入對(duì)象xi已有最近鄰居集合Neii，本文將鄰域內(nèi)兩個(gè)數(shù)據(jù)點(diǎn)間的最短路徑計(jì)算值作為真實(shí)測(cè)地線(xiàn)距離的近似.xi鄰域Neii內(nèi)任意兩個(gè)數(shù)據(jù)點(diǎn)間的歐式距離記為dX(xi,xj)，測(cè)地線(xiàn)距離記為dG(xi,xj)，兩者關(guān)系如公式(4)，然后計(jì)算xi鄰域Neii內(nèi)任意兩個(gè)數(shù)據(jù)點(diǎn)間的最短路徑，如公式(5)，

(4)

dG(xi,xj)=min{dG(xi,xj),dG(xi,xk)+dG(xk,xj)}，k∈[0,n).

(5)

基于此，公式(3)可改進(jìn)為

(6)

2.2 緩存容量分配

在通過(guò)構(gòu)造K-近鄰表征相似性的方式改進(jìn)了t-SNE算法后，對(duì)收集到的高維數(shù)據(jù)進(jìn)行處理，得到低維空間的嵌入結(jié)果Y(I).本文以該降維結(jié)果作為節(jié)點(diǎn)相似性的劃分標(biāo)準(zhǔn)，根據(jù)節(jié)點(diǎn)重要程度不同，設(shè)置不同的權(quán)重，進(jìn)而按權(quán)重為節(jié)點(diǎn)分配不同大小的容量空間.

假設(shè)低維嵌入結(jié)果Y(I)將節(jié)點(diǎn)劃分為k_class類(lèi)，numj表示類(lèi)別j中包含的節(jié)點(diǎn)個(gè)數(shù).令W表示類(lèi)別對(duì)應(yīng)的權(quán)重值，W={w1,w2,…,wk}，W中的變量按降序排列且滿(mǎn)足公式(7)的約束，

(7)

假設(shè)整個(gè)網(wǎng)絡(luò)拓?fù)涞目偩彺嫒萘坑肅total表示，在類(lèi)別j中，節(jié)點(diǎn)的分配緩存大小用Cji表示，

Cji=Ctotal·wj/numj,j∈[1,k],i∈[1,numj).

(8)

緩存容量分配機(jī)制中，首先初始化參數(shù)并構(gòu)建VP樹(shù)；然后根據(jù)VP樹(shù)構(gòu)建K-近鄰并計(jì)算點(diǎn)對(duì)之間的測(cè)地線(xiàn)距離；再計(jì)算高維空間聯(lián)合概率分布；最后使用梯度下降法進(jìn)行訓(xùn)練，得到低維嵌入的結(jié)果.通過(guò)構(gòu)造K-近鄰表征相似性的方式改進(jìn)t-SNE算法，既考慮了高維數(shù)據(jù)的流形特征，也大大降低了高維空間點(diǎn)對(duì)相似性的計(jì)算量.

3 性能評(píng)價(jià)

3.1 拓?fù)溆美?/h3>

在進(jìn)行仿真實(shí)現(xiàn)的過(guò)程中，本文使用了中國(guó)的cernet和美國(guó)的deltacom兩種拓?fù)浣Y(jié)構(gòu).cernet網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)含有36個(gè)節(jié)點(diǎn)、49條鏈路，平均節(jié)點(diǎn)度數(shù)為2.72.deltacom網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)含有113個(gè)節(jié)點(diǎn)、161條鏈路，平均節(jié)點(diǎn)度數(shù)為2.85.

3.2 評(píng)價(jià)指標(biāo)

本文在Ubuntu下搭建基于NS-3的仿真模塊NDNSIM并進(jìn)行仿真實(shí)現(xiàn)，同時(shí)將搜集的歷史流量數(shù)據(jù)導(dǎo)入到matlab軟件中進(jìn)行處理.

本文基于兩種拓?fù)浣Y(jié)構(gòu)、采用多個(gè)性能指標(biāo)對(duì)基于t-SNE算法的緩存容量分配機(jī)制進(jìn)行性能評(píng)價(jià)，評(píng)價(jià)指標(biāo)如下.

1) 緩存命中率. 緩存命中率的計(jì)算公式CacheHitRatio=NumcacheHit/Numsuccess，其中：NumcacheHit為從路由器節(jié)點(diǎn)的內(nèi)容存儲(chǔ)庫(kù)(content store,CS)獲得內(nèi)容的興趣請(qǐng)求數(shù)；Numsuccess為路由成功的興趣請(qǐng)求數(shù).緩存命中率能夠在很大程度上表征緩存內(nèi)容的利用率.

2) 路由成功率. 路由成功率的計(jì)算公式SuccessRatio=Numsuccess/Numtotal，其中：Numsuccess為路由成功的興趣請(qǐng)求數(shù)；Numtotal為用戶(hù)向網(wǎng)絡(luò)中發(fā)起的興趣請(qǐng)求總數(shù). 路由成功率能夠表征路由機(jī)制的效率.

3)緩存開(kāi)銷(xiāo). 節(jié)點(diǎn)緩存開(kāi)銷(xiāo)的計(jì)算公式Overi=Rep_Ci·Volaver/ci，其中：Rep_Ci為節(jié)點(diǎn)內(nèi)容替換次數(shù)；Volaver為內(nèi)容平均大??；ci為節(jié)點(diǎn)緩存容量.緩存開(kāi)銷(xiāo)能夠表征采樣時(shí)間段內(nèi)節(jié)點(diǎn)的負(fù)載情況.

3.3 性能評(píng)估

為驗(yàn)證本文設(shè)計(jì)的基于t-SNE算法的緩存容量分配機(jī)制，在全網(wǎng)發(fā)起了5 000次請(qǐng)求進(jìn)行節(jié)點(diǎn)聚類(lèi)，所有節(jié)點(diǎn)都能正常執(zhí)行緩存替換機(jī)制(緩存空間已滿(mǎn))并收集50個(gè)采樣時(shí)間段的流量特征信息.

在cernet拓?fù)湎聢?zhí)行本文的緩存容量分配機(jī)制得到的二維嵌入結(jié)果如圖1所示，其中每個(gè)數(shù)據(jù)點(diǎn)代表一個(gè)路由器節(jié)點(diǎn).根據(jù)節(jié)點(diǎn)在網(wǎng)絡(luò)中的相對(duì)位置可以發(fā)現(xiàn)，X值越大，Y值越小，節(jié)點(diǎn)在網(wǎng)絡(luò)中越重要.由該圖可見(jiàn)cernet的36個(gè)節(jié)點(diǎn)被聚簇為2類(lèi)，含有重要節(jié)點(diǎn)8個(gè)，含有普通節(jié)點(diǎn)28個(gè).在deltacom拓?fù)湎聢?zhí)行本文的緩存容量分配機(jī)制得到的二維嵌入結(jié)果如圖2所示. deltacom中的113個(gè)節(jié)點(diǎn)被聚簇為4類(lèi)，其中節(jié)點(diǎn)個(gè)數(shù)分別為6、40、30、37.

圖1 cernet拓?fù)湎碌牡途S嵌入結(jié)果Fig.1 The low dimension result in cernet

圖2 deltacom拓?fù)湎碌牡途S嵌入結(jié)果Fig.2 The low dimension result in deltacom

為了驗(yàn)證本文提出的緩存容量分配機(jī)制的性能，選取LCE(leave copy everywhere)以及Betw[18]作為基準(zhǔn)緩存決策機(jī)制.其中，LCE是ICN的默認(rèn)緩存決策機(jī)制，它在數(shù)據(jù)包傳輸路徑上的每個(gè)路由器節(jié)點(diǎn)都進(jìn)行緩存；而B(niǎo)etw機(jī)制對(duì)LCE進(jìn)行了改進(jìn)，它將內(nèi)容緩存在興趣包轉(zhuǎn)發(fā)路徑上介數(shù)中心性最大的節(jié)點(diǎn)中.本文在cernet和deltacom兩種網(wǎng)絡(luò)拓?fù)湎?，將兩種基準(zhǔn)機(jī)制分別在默認(rèn)等量分配和基于t-SNE算法的緩存容量分配(t-LCE、t-Betw)兩種情況下進(jìn)行仿真實(shí)驗(yàn).在網(wǎng)內(nèi)發(fā)起3 000個(gè)興趣請(qǐng)求，并統(tǒng)計(jì)對(duì)應(yīng)緩存命中率、路由成功率、緩存開(kāi)銷(xiāo)3個(gè)指標(biāo).實(shí)驗(yàn)結(jié)果如表1所示.

從表1中我們可以看出，在引入緩存容量分配機(jī)制后，t-LCE與t-Betw均在不同程度上提升了基準(zhǔn)緩存機(jī)制的緩存命中率和路由成功率，且降低了網(wǎng)絡(luò)平均緩存開(kāi)銷(xiāo).本文提出的緩存容量分配機(jī)制基于低維嵌入的結(jié)果，為節(jié)點(diǎn)分配不同大小的緩存容量.cernet拓?fù)湎?，均勻分布時(shí)每個(gè)節(jié)點(diǎn)緩存容量為1 G，重要節(jié)點(diǎn)權(quán)重w1=0.6，普通節(jié)點(diǎn)權(quán)重w2=0.4，基于低維嵌入結(jié)果，每個(gè)重要節(jié)點(diǎn)需分配2.7 G容量，每個(gè)普通節(jié)點(diǎn)需分配0.5 G容量(2.7 G×8+0.5 G×28≈36 G).deltacom拓?fù)湎拢瑯泳鶆蚍植紩r(shí)節(jié)點(diǎn)緩存容量為1 G，4類(lèi)節(jié)點(diǎn)權(quán)重分別設(shè)為w1=0.4、w2=0.3、w3=0.2、w4=0.1.根據(jù)公式(8)可知，4類(lèi)節(jié)點(diǎn)分別需要分配7.5 G、0.85 G、0.75 G、0.3 G容量(7.5 G×6+0.85 G×40+0.75 G×30+0.3 G×37≈113 G).

表1 Cernet與deltacom兩種拓?fù)湎聦?duì)比實(shí)驗(yàn)結(jié)果Tab.1 Comparative experimental results over cernet and deltacom %

在兩種拓?fù)湎拢疚奶岢龅木彺嫒萘糠峙錂C(jī)制與默認(rèn)機(jī)制進(jìn)行對(duì)比分析，緩存命中率提高了3%～4%，路由成功率基本維持在95%，其性能的提升與緩存決策機(jī)制本身有關(guān).t-LCE機(jī)制對(duì)緩存命中率的提升更明顯.因?yàn)閺娜W(wǎng)角度來(lái)看，盡管普通節(jié)點(diǎn)容量減少，但重要節(jié)點(diǎn)分配更多的容量后，不僅特別流行的內(nèi)容副本數(shù)變化不大，還能夠在重要節(jié)點(diǎn)緩存更多的流行內(nèi)容，因此在緩存命中率指標(biāo)上提升很多.t-Betw機(jī)制則在路由成功率提升方面更加明顯，這是由于該機(jī)制在當(dāng)前路徑中的重要節(jié)點(diǎn)緩存內(nèi)容，緩存容量分配機(jī)制為網(wǎng)絡(luò)中相對(duì)重要的節(jié)點(diǎn)分配更多的緩存容量，這些節(jié)點(diǎn)能夠響應(yīng)更多的興趣請(qǐng)求，因此極大提升了路由成功率.

從全網(wǎng)節(jié)點(diǎn)的平均緩存開(kāi)銷(xiāo)來(lái)看，cernet拓?fù)湎聇-LCE的平均緩存開(kāi)銷(xiāo)減少了6.3%，t-Betw的平均緩存開(kāi)銷(xiāo)減少了23.4%.deltacom拓?fù)湎聇-LCE的節(jié)點(diǎn)平均開(kāi)銷(xiāo)減少了13.5%，t-Betw的節(jié)點(diǎn)平均開(kāi)銷(xiāo)減少了17.4%.由此可見(jiàn)，本文提出的緩存容量分配機(jī)制在Betw上提升效果更明顯，這是因?yàn)锽etw對(duì)節(jié)點(diǎn)按照節(jié)點(diǎn)介數(shù)中心性進(jìn)行劃分，而不是像LCE機(jī)制那樣對(duì)所有節(jié)點(diǎn)一視同仁.此外，本文提出的緩存容量分配機(jī)制，權(quán)衡了拓?fù)湫畔⒑土髁糠植?，將?jié)點(diǎn)按照重要程度進(jìn)行劃分，進(jìn)而能夠保證網(wǎng)絡(luò)流量按照節(jié)點(diǎn)重要程度均勻分布在網(wǎng)內(nèi)，不僅解決了部分節(jié)點(diǎn)負(fù)載過(guò)重的問(wèn)題，還解決了少數(shù)節(jié)點(diǎn)緩存利用率不高的問(wèn)題，從而降低了網(wǎng)絡(luò)的整體緩存開(kāi)銷(xiāo).

4 結(jié)束語(yǔ)

本文通過(guò)對(duì)現(xiàn)有緩存技術(shù)進(jìn)行分析，提出了基于t-SNE算法的緩存容量分配機(jī)制.通過(guò)構(gòu)造K-近鄰表征相似性的方式改進(jìn)t-SNE算法，對(duì)網(wǎng)絡(luò)拓?fù)鋵傩砸约傲髁刻卣餍畔⑦M(jìn)行分析，基于聚類(lèi)結(jié)果將有限的緩存空間合理分配給不同節(jié)點(diǎn)以達(dá)到平衡節(jié)點(diǎn)負(fù)載的目的.為驗(yàn)證本文方法的可行性和有效性，對(duì)算法進(jìn)行了仿真實(shí)現(xiàn)，并與基準(zhǔn)機(jī)制進(jìn)行對(duì)比分析.從實(shí)驗(yàn)結(jié)果可以看出，本文設(shè)計(jì)的機(jī)制在緩存命中率、路由成功率以及緩存開(kāi)銷(xiāo)等方面具有一定的優(yōu)勢(shì).下一步工作將對(duì)緩存分配機(jī)制的穩(wěn)定性進(jìn)行驗(yàn)證，進(jìn)一步完善本文提出的機(jī)制.